Watch an AI bot play Go [video](facebook.com) |
Watch an AI bot play Go [video](facebook.com) |
I have recently become interested, again, in Go programming. I have started setting up a framework for using GnuGo to generate training data for a deep learning network. I am starting with a tiny 7x7 board just to see if the general approach works.
If it works (at all) then I will post the entire project to github.
You should prototype it in Lisp :-)
I was just this weekend going through my go library, and most of the books I have focus on precisely this sort of pattern training. In fact, there's a whole branch of study in go called in Japanese "Tesuji", essentially brilliant moves that come from bad-looking patterns.
The idea is that you lull your opponent into complacency with your bad-looking pattern, then "BAM", a surprise comes out. My guess is that an RNN could be discovering new tesuji, which would be super cool. If the RNN can look ahead deep enough, then I would think that's a path forward against strong players.
There's also the reverse, Anti-suji, essentially things that look brilliant, but are really terrible.
Facebook's AI lab will probably reveal more technical details at NIPS 2015. Here's the workshop on Reasoning, Attention, Memory (RAM) they are organizing that will seek to address some of the challenges around advancing from classification and prediction tasks to simple cognition:
At the same time, there's something amusing about the idea that a six year-old programming language should cause a 2000 year old game to change its name.
Using the label gogame or baduk I think are adequate solutions. Also a go board is referred to as a goban.
This is potentially a really big breakthrough if true, as Go is much harder than Chess computationally. Nobody knows about Go in the West though so don't expect any headlines.
Making good analogies is hard, but here's mine: current go programs are probably somewhere in the range of runners running a 2:45 marathon. They're beyond what most people can hope to reach, perhaps even with intensive training, but they're not world-class. In fact, they're not just below world-class: there are thousands of people better than them who are themselves not yet world class. (Context: I play go and run at a level far below the ones quoted above, but know people who play/run at that level. And I've seen those people get their butts kicked by stronger players/runners).
I would bet that in a few years is going to be clear who is superior, the machine or the human.
The two breakthrough papers using Deep Conv Nets to play Go - trained on Expert Games to predict the Experts Next Move.
This is made possible by the huge archives of expert play from online Go servers that have reached Big Data sizes in the last few years.
Teaching Deep Convolutional Neural Networks to Play Go - Clark & Storkey Edinburgh Informatics 2015 http://arxiv.org/abs/1412.3409
Move Evaluation in Go Using Deep Convolutional Neural Networks Maddison, Huang, Silver, Sutskever Deepmind 2015 http://arxiv.org/abs/1412.6564
David Silver has work on Reinforcement Learning and Go: Reinforcement Learning of Local Shape in the Game of Go Silver et al 2007. https://scholar.google.co.uk/citations?view_op=view_citation...
Go is scored by occupying and surrounding territory and the opponents pieces taken.
The current State of the Art programs use Monte Carlo Tree Search with each move being evaluated using random playouts - this is well suited to Go as it reasnoble estimate for comparison of the territory that will result from a move.
As the Go search tree branches a lot (~200 branches per play) tree search takes some time and cannot be exhaustive.
The Expert Move Predicting Convnets provide very good moves very quickly, and can provide and provide probabilities the expert would move for each square in a single forward pass.
Most of the current development now centers around using the Convnets to prune the search trees for the random playout MCTS engines.
Go is useful from an AI perspective because it is a huge state space and the patterns are subtle with long term implications. No computer can yet beat the best humans - so it is an area where natural intelligence beats artificial.
Yet the convnets are not doing planning, only predicting what an expert human would do next, the planning is implicit in the dataset but not a part of the convnet itself (though the internals of deepnets are mysterious so who knows).
The Computer Go mailing list is very lively and full of the best program creators with regular computer tournaments against each other. http://computer-go.org/mailman/listinfo/computer-go
The Facebook video shows GnuGo is the opposing player, this is not the best computer player and suggests Facebooks player is not as strong as the Convnets as yet - it also does not detail how deep the playouts of the tree search are, i.e. what level GnuGo is playing at, so this cannot really be compared to recent work.
Hopefully Facebook will publish more details soon - if they are learning through play then their results may well be interesting.
Remi Coulom's excellent slides detail the Monte Carlo revolution in Go programs. http://www.remi-coulom.fr/JFFoS/JFFoS.pdf
AFAIK MCTS with Random playout and hand coded heuristics are still SOTA.
When I visited in the summer Edinburgh Uni Informatics Department convnet Go was in active development.
Here's a chart of current ratings of popular engines on online forums. The rating system is one of "kyu" and "dan" going from 25k to 1k to 1d to 9d.
http://senseis.xmp.net/?KGSBotRatings
Informally there's another rating system the "pro" rating system which is a bit ceremonial but also broadly assumed to be often higher than the amateur dan rankings.
I guess Facebook is claiming they're upending that, but that remains to be seen.
However, the ELO figure seems high to me. A go handicap stone is probably more than 100 ELO at those levels, because high level players are good at conserving small advantages. Additionally, the players in these exhibition matches are usually themselves not the top players in the world. For instance, Zhou Junxun or Ishida Yoshio are two I recall off the top of my head.[2]
[1] http://europeangodatabase.eu/EGD/createalleuro3.php?country=...
[2] If you know how many humans can run a 2:45 marathon, let me know! I know Boston lets you in with a 3:05 time if you're 18-34, and tens of thousands of people run that (some of them are older or women, but many eligible people don't compete...). I'm kinda spitballing on the exact times, but that's roughly how I want to do the comparison.
[3] (http://www.goratings.org/).
A good way to do comparison might be to do the percentile. 2:45 would put you in the 76 percentile.