Source-linked AI summary
Move Evaluation in Go Using Deep Convolutional Neural Networks
Chris J. Maddison, Aja Huang, Ilya Sutskever, David Silver
TL;DR
Go poses a difficult move-evaluation problem, and this paper tests whether deep CNNs can learn that knowledge from professional games. The resulting network reaches 55% move-prediction accuracy and, without search, beats GnuGo in 97% of games while competing with Monte-Carlo search programs.
Problem
Constructing an evaluation function that distinguishes good moves from bad in Go positions is difficult.
Source: §1 · p. 1Method
Results
55% held-out move-prediction accuracy matched the 6 dan author; without search, the CNN beat GnuGo in 97% of games and matched state-of-the-art Monte-Carlo programs.
Source: §1 · p. 2Takeaways & Limitations
A deep CNN can represent a strong move-evaluation function and play competitively without explicit search.
Source: §1 · p. 1, §7 · p. 7The network sometimes misjudges the life-and-death status of large groups, reflecting weakness in assessing the global picture.
Source: §7 · p. 7
Abstract
from arXiv · showhide
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.
1 INTRODUCTION
Go is difficult partly because a move-evaluation function is hard to construct, and the paper tests whether deep convolutional networks can learn this knowledge. A 12-layer CNN trained on professional games achieves strong move-prediction accuracy and plays competitively without search.
1 INTRODUCTION
- The motivating challenge is constructing an evaluation function that distinguishes good moves from bad in Go positions.The introduction also describes prior Monte-Carlo methods as strong at amateur level, with a remaining gap to top professionals.Source: §1 · p. 1
- The paper uses a 12-hidden-layer CNN with several billion connections to represent and learn Go knowledge, addressing earlier architectures’ limits in depth and size.The authors report that the larger, deeper network produces a qualitative jump in performance.Source: §1 · p. 1
- The study uses supervised learning to predict expert moves from a large database of professional 19 × 19 games.Source: §1 · p. 1
- 55% held-out move-prediction accuracy matched the 6 dan author and exceeded Go programs’ reported 35% and 39% predictive accuracy.The comparison is on the same data set for the author; the program accuracies are reported for some of the strongest Go programs.Source: §1 · p. 2
- Without search, CNN move selection beat GnuGo in 97% of games and equalled state-of-the-art Monte-Carlo programs Pachi and MoGo.Pachi used 10,000 rollouts per move and MoGo used 100,000 rollouts per move.Source: §1 · p. 2
- A delayed-prior procedure combined the CNN with Monte-Carlo tree search, whose 100,000-rollout search defeated the raw CNN in 87% of games.CNN evaluations ran asynchronously on a GPU and were incorporated into the search when available.Source: §1 · p. 2
2 PRIOR WORK
Prior Go CNNs used reinforcement learning or small supervised networks, while strong contemporary programs relied on Monte-Carlo tree search and learned policies. Deep CNN advances in image recognition motivated applying larger networks to Go.
2 PRIOR WORK
- Schraudolph et al. (1994) and NeuroGo used CNNs to predict territory and other board properties, while Sutskever & Nair (2008) trained a small supervised CNN to predict expert moves.NeuroGo with alpha-beta search matched GnuGo on 9 × 9 and reached around 13 kyu on 19 × 19; the supervised model achieved 34.6% accuracy but could not play at a reasonable level.Source: §2 · p. 2
- Monte-Carlo tree search underpinned leading Go programs, with prior knowledge used to bootstrap value estimates, accelerate search, and bias move selection and rollouts.CrazyStone achieved 35% move-prediction accuracy using expert-game patterns combined in a linear softmax.Source: §2 · p. 2
- Deep CNNs had substantially improved image-recognition performance, motivating their investigation in the “visual” domain of computer Go.The cited progression reduced top-5 error from 15.3% to 7.0%.Source: §2 · p. 2
3 DATA
The study builds a position-to-move dataset from KGS games and represents board states with rule-based feature planes. It also conditions on player rank to address uneven representation of skill levels and augments training with board symmetries.
3 DATA
- The KGS data comprise 29.4 million board-state/next-move pairs from 160,000 games, with moves encoded as indicators over the 361 intersections of a 19 × 19 board.The games were played by humans of varying rank.Source: §3 · pp. 2–3
- Input feature planes encode stones, liberties, captures, legality, turns since, and ladders; the ladder feature adds a small performance benefit.The feature inventory is listed in Table 1.Source: §3 · p. 3, Table 1 · p. 3
- Because KGS contains more games from lower-dan players, the network receives nine rank-indicator planes that provide a rank-dependent bias.Training only on stronger players would greatly reduce the available data.Source: §3 · p. 3
- Training examples are augmented by uniformly sampling among eight rotations and reflections, and the game-level split leaves 27.4 million pairs for training and 2 million for testing.The split was made before shuffling, so the test set contains distinct games.Source: §3 · p. 3
4 ARCHITECTURE & TRAINING
The network is a deep, position-preserving CNN with separate move distributions for each player. Training uses asynchronous SGD followed by fine-tuning, while experiments also examine weight symmetry and note limits on feature testing.
4 ARCHITECTURE & TRAINING
- A 12-layer CNN uses rectified linear units, 5 × 5 first-layer filters, 3 × 3 later filters, and no pooling; the best model has 2.3 million parameters and 630 million connections.Every layer operates on a 19 × 19 space, with 64–192 filters per layer and zero-padding of outputs.Source: §4 · p. 3
- Two convolutional output filters produce separate 361-way softmax move distributions for black and white.The network uses position-dependent biases; the optimal policy may select different moves for each player.Source: §4 · pp. 3–4
- Because extensive experiments were computationally costly, some input features may be unnecessary or redundant.Source: §4 · p. 3
- Weight symmetry experiments aggregated updates across the eight rotations and reflections, enforcing local filter symmetry beyond whole-board data augmentation.Source: §4 · p. 4
- Training used asynchronous SGD on 50 GPU replicas followed by three epochs of single-GPU fine-tuning; a 10-layer model reached 55% training and 54.5% test accuracy.The authors report very minor overfitting and suggest the model is in an underfitting regime; reported accuracies use a held-out test set.Source: §4 · p. 4
5 RESULTS
The results show that network depth and player rank influence Go move prediction and playing strength, while weight symmetry benefits were limited to smaller, shallower networks. The 12-layer CNN performed strongly against Go programs, and its top-10 predictions included the expert move in most test positions.
5.1 INVESTIGATION OF WEIGHT SYMMETRIES
- Weight symmetries strongly affected move prediction in small, shallow networks, but the effect appeared to disappear in larger, deeper networks.This was tested with 3- and 6-layer networks trained on a reduced feature set.Source: §5.1 · p. 4
5.2 ACCURACY AND PLAYING STRENGTH
- 97% winning rate against GnuGo for the large 12-layer network compared with 3.4% for the small 3-layer network.Prediction accuracy was strongly correlated with playing performance; the networks selected moves directly from the softmax output.Source: §5.2 · p. 5
- 94% of the time, the correct expert move appeared within the network’s top 10 predictions.The passage notes that a small top-n set could reduce the program’s effective search space.Source: §5.2 · p. 5
- KGS rank 1, 5, and 9 yielded 49.2%, 60.1%, and 67.9% wins, respectively, against the 10-layer CNN.The network played significantly better when asked to imitate a stronger player.Source: §5.2 · p. 5
- The CNN was considerably stronger than GnuGo, matched MoGo at 100,000 rollouts and Pachi at 10,000 rollouts per move, and won more than 10% against Fuego and strong Pachi.The Pachi comparison used approximately 2 million positions per move.Source: §5.2 · p. 6
6 SEARCH
The authors integrated the CNN with Monte Carlo Tree Search by evaluating batches of new search nodes asynchronously on a GPU. With 100,000 rollouts per move, the combined system substantially outperformed the CNN used without search.
6 SEARCH
- Because the CNN is slower than search, evaluating every node with it is not feasible.A 12-layer network took 0.15 seconds to evaluate a minibatch of 128.Source: §6 · p. 6
- Asynchronous evaluation batches new search nodes for GPU inference while MCTS continues, then adds the CNN move recommendations to the tree in FIFO order.The system sustained approximately 47,000 rollouts per second, with about 0.15 seconds of lag before new information was used.Source: §6 · p. 6
- The MCTS engine also used RAVE, a UCT-like exploration strategy, and simple rollouts based solely on 3 × 3 patterns.Source: §6 · p. 6
- At 100,000 rollouts per move, MCTS-CNN won 86.7 ± 3.5% against the no-search CNN; at 10,000 rollouts, it won 67.6 ± 2.6%.The paper describes the 100,000-rollout result as 87% of games.Source: §6 · p. 6
7 DISCUSSION
The 12-layer CNN showed stronger move evaluation and playing strength than previously possible, including competition with search-based Go programs without search of its own. The network still sometimes misjudges the global status of large groups, a weakness the authors suggest may complement Monte-Carlo search.
7 DISCUSSION
- The CNN predicted expert moves with accuracy exceeding previous methods and approximately matching human performance.The discussion describes the network as predicting Go experts' next moves with approximately human-level accuracy.Source: §7 · p. 6
- 56% and 33% of games were won by the 12-layer CNN against Fuego 1.1 at 5 and 10 seconds per move, respectively.The tests used two 3.1 GHz cores; an earlier 8-layer network won 12% against Fuego 1.1 at 10 seconds per move on two 1.6 GHz cores.Source: §7 · p. 6
- Reducing the minibatch size did not significantly speed up end-to-end computation in the GPU implementation.Source: §7 · p. 6
- Without search, the CNN outperformed traditional search-based programs such as GnuGo and competed with state-of-the-art MCTS programs such as Pachi and Fuego.A sample game against Fuego, which searched 100,000 rollouts per move, was won by the CNN.Source: §7 · p. 7, Figure 2 · p. 7
- The CNN's move recommendations reflected sophisticated Go concepts, including shape, opening sequences, tactical patterns, territory, and influence.The authors point to these elements in the sample game against Fuego, played without explicit lookahead.Source: §7 · p. 7
- The network sometimes misjudged the global status of large groups, while Monte-Carlo search excels at these global aspects.The authors describe the two techniques as potentially complementary and report a preliminary proof-of-concept for combining them.Source: §7 · p. 7