[Link] Neural networks trained on expert Go games have just made a major leap

ESRogs

From the arXiv:

Move Evaluation in Go Using Deep Convolutional Neural Networks

Chris J. Maddison, Aja Huang, Ilya Sutskever, David Silver

The game of Go is more challenging than other board games, due to the difficulty of constructing a position or move evaluation function. In this paper we investigate whether deep convolutional networks can be used to directly represent and learn this knowledge. We train a large 12-layer convolutional neural network by supervised learning from a database of human professional games. The network correctly predicts the expert move in 55% of positions, equalling the accuracy of a 6 dan human player. When the trained convolutional network was used directly to play games of Go, without any search, it beat the traditional search program GnuGo in 97% of games, and matched the performance of a state-of-the-art Monte-Carlo tree search that simulates a million positions per move.

This approach looks like it could be combined with MCTS. Here's their conclusion:

In this work, we showed that large deep convolutional neural networks can predict the next move made by Go experts with an accuracy that exceeds previous methods by a large margin, approximately matching human performance. Furthermore, this predictive accuracy translates into much stronger move evaluation and playing strength than has previously been possible. Without any search, the network is able to outperform traditional search based programs such as GnuGo, and compete with state-of-the-art MCTS programs such as Pachi and Fuego.

In Figure 2 we present a sample game played by the 12-layer CNN (with no search) versus Fuego (searching 100K rollouts per move) which was won by the neural network player. It is clear that the neural network has implicitly understood many sophisticated aspects of Go, including good shape (patterns that maximise long term effectiveness of stones), Fuseki (opening sequences), Joseki (corner patterns), Tesuji (tactical patterns), Ko fights (intricate tactical battles involving repeated recapture of the same stones), territory (ownership of points), and influence (long-term potential for territory). It is remarkable that a single, unified, straightforward architecture can master these elements of the game to such a degree, and without any explicit lookahead.

On the other hand, we note that the network still has weaknesses: notably it sometimes fails to understand the global picture, behaving as if the life and death status of large groups has been incorrectly assessed. Interestingly, it is precisely these global aspects of the game for which Monte-Carlo search excels, suggesting that these two techniques may be largely complementary. We have provided a preliminary proof-of-concept that MCTS and deep neural networks may be combined effectively. It appears that we now have two core elements that scale effectively with increased computational resource: scalable planning, using Monte-Carlo search; and scalable evaluation functions, using deep neural networks. In the future, as parallel computation units such as GPUs continue to increase in performance, we believe that this trajectory of research will lead to considerably stronger programs than are currently possible.

H/T: Ken Regan

Edit -- see also: Teaching Deep Convolutional Neural Networks to Play Go (also published to the arXiv in December 2014), and Why Neural Networks Look Set to Thrash the Best Human Go Players for the First Time (MIT Technology Review article)

As someone who used Convolutional Neural Networks in a Master's Thesis, this doesn't surprise me. CNNs are especially well suited to problems that involve two dimensional input where spatial information matters. I especially like that they were willing to go deep and make the net 12 layers deep, as that fits well with some of my own research that seemed to be showing that deeper networks were the way to go in terms of performance efficiency.

It's also quite interesting that they didn't use any pooling layers, which is a break from the traditional way that CNNs are constructed, which usually consists of alternating convolutional and pooling layers. I've actually been curious for some time about whether or not pooling layers were actually necessary, or if you could get away with just using convolutional layers, since the convolutional layers seem to be the ones that actually do the important stuff, while the pooling layers seemed like just a neat way to make the input for the next layer smaller and easier to handle.

Regardless, I'm definitely happy to see CNNs making progress for a problem that seemed intractable not so long ago. Score one more for the neural nets!

Intuitively, it makes sense to me that pooling layers would be useful in image/visual applications, since downsampling an image gives another image that's related to the original one. Downsampling a Go board, OTOH, gives nothing useful. (I mean, it's not devoid of information, but it gives up way more than a proportional amount of information, as compared with downsampling a photograph.)

Interestingly one of the authors Amos Storkey proposes to marry machine learning with information markets.

Ilya is awesome. He keeps breaking benchmarks in a way that causes me to predict that he will keep breaking more benchmarks in the future...

Winning competitions in image recognition is pretty similar to Go (same basic neural net architecture), but he's also been cooking up stuff in natural language understanding and translation with "deep" LSTMs.

Interesting, thanks.