Mastering the game of Go with deep neural networks and tree search

The problem

Go had long been seen as the most challenging classic game for AI. Its search space is enormous, and it is hard to judge how good a board position is or which move is worth considering. The paper set out to address both difficulties.^[1]

How it works

AlphaGo uses two deep neural networks. Policy networks choose moves, and value networks evaluate positions. Both are deep convolutional networks that read the 19×19 board as an image. They were first trained by supervised learning from human expert games, then improved by reinforcement learning from games of self-play. The networks were combined with Monte Carlo tree search, which explores possible sequences of moves and uses the networks to guide and judge that search.^[1] In plain terms, the policy network narrows the search to moves worth examining, while the value network estimates how well a position is going for each side, so the program does not have to play every line to the end.

The supervised policy network had 13 layers and was trained on 30 million positions from the KGS Go Server. It predicted expert moves with 57.0% accuracy, compared with 44.4% for the previous best result from other groups.^[1] To avoid overfitting, the value network was trained on a new self-play dataset of 30 million distinct positions, each sampled from a separate game.^[1]

Results

The single-machine version of AlphaGo used 40 search threads, 48 CPUs and 8 GPUs. It won 494 of 495 games (99.8%) against other Go programs.^[1][2] A distributed version used 1,202 CPUs and 176 GPUs.^[2]

Over 5 to 9 October 2015, the distributed AlphaGo played Fan Hui, a professional 2 dan player who had won the European Go championships in 2013, 2014 and 2015. It won the formal match 5 games to 0. This was the first time a computer program had defeated a human professional in full-sized Go without handicap, a feat previously thought to be at least a decade away.^[2]

Why it mattered

The paper showed that a program could reach professional strength in Go by combining learned evaluation with search, rather than relying only on handcrafted rules. Its central lesson is that the two reinforce each other: the networks make the search more selective, and the search supplies positions for the networks to judge. The authors noted that against Fan Hui, AlphaGo evaluated thousands of times fewer positions than Deep Blue did against Kasparov. They also noted that, unlike Deep Blue's handcrafted evaluation function, AlphaGo's networks were trained directly from gameplay.^[2]

Later influence

The result was widely noted as a milestone, because a game that had resisted computer play for decades was now won by a program that learned its judgement from data. The approach of pairing deep networks with search became a reference point for later work in game-playing AI.^[1]