How did AlphaGo become the first program to beat a professional Go player?

For decades, the ancient board game Go was the game computers could not crack. Programs had beaten the best humans at checkers and, in 1997, at chess. At Go, the strongest programs of the early 2010s played like good amateurs, and many experts thought beating a professional was at least ten years away.

Then, on 27 January 2016, the London AI company DeepMind, owned by Google, announced that its program AlphaGo had already done it. Three and a half months earlier, behind closed doors, AlphaGo had beaten Europe's champion, Fan Hui, in all five games of a formal match. The same day, the science journal Nature published a paper explaining how.

What happened, when and where

Fan Hui was a professional 2-dan player (professional ranks run up to 9 dan) and had won the European Go championship in 2013, 2014 and 2015. DeepMind invited him to its London office, and the match took place over five days, from 5 to 9 October 2015. AlphaGo won the first game by 2.5 points; Fan Hui resigned the other four.

Fan Hui himself chose the time limits before the match. Each formal game gave each player one hour, plus three 30-second overtime periods called byo-yomi. Alongside the formal games, the two also played five informal games with much faster time controls. Those were closer: AlphaGo won three and Fan Hui won two.

DeepMind kept the result secret until its paper, "Mastering the game of Go with deep neural networks and tree search," was ready. The journal received it on 11 November 2015 and accepted it on 5 January 2016. Its twenty authors were led by David Silver and Aja Huang, with DeepMind's co-founder Demis Hassabis among them, as well as Ilya Sutskever of Google. The program that played Fan Hui ran on a network of computers with 1,202 ordinary processors and 176 graphics processors.

How AlphaGo worked

Go is played on a 19-by-19 grid. Two players take turns placing black and white stones, trying to surround territory and capture each other's stones. The rules are simple, but the number of possible games is astronomically large, so a program cannot simply try everything (more on that below).

AlphaGo combined three ingredients:

• A policy network that looks at the board and suggests which moves are worth considering. It narrows hundreds of legal moves down to a handful of promising ones.
• A value network that looks at a position and estimates who is likely to win from there, without playing the game out.
• Monte Carlo tree search, a method that explores possible future moves, guided by the two networks, and settles on the move that leads to the best outcomes.

The networks learned in stages:

A neural network here is a program with millions of adjustable connections that learns patterns from examples; the board goes in as a grid of numbers, and a move or a win probability comes out. Reinforcement learning means learning by trial and error from rewards, here simply winning or losing.

Why it mattered

AlphaGo was the first program to beat a human professional at Go on a full-size board with no handicap stones. Just as important was how it won. The paper points out that against Fan Hui, AlphaGo examined thousands of times fewer positions than IBM's Deep Blue did against Garry Kasparov in chess. It made up for that by choosing which positions to look at more cleverly and judging them more accurately, an approach the authors suggest is closer to how people play. And unlike Deep Blue, whose evaluation rules were handcrafted, AlphaGo's knowledge came from general-purpose learning methods.

Not everyone was convinced it was a "Deep Blue moment" yet. Fan Hui was a strong professional, but far from the world's best. Korean champion Lee Sedol judged that AlphaGo played like a top amateur rather than a professional. DeepMind's announcement already named the next test: a five-game match against Lee in Seoul that March, which AlphaGo went on to win four games to one.

Why was Go so much harder for computers than chess?

The short answer is the size of the search. In chess, a player typically has about 35 legal moves, and a game lasts about 80 moves. In Go, there are about 250 legal moves per turn, and games run about 150 moves. Multiply those choices out and Go's game tree dwarfs chess's. DeepMind's announcement put it vividly: Go has more possible positions than there are atoms in the universe.

The second problem is judging a position. In chess, counting material (a queen is worth about nine pawns, and so on) gives a rough sense of who is ahead, and Deep Blue built on hand-tuned rules like that. In Go, all stones are equal, and whether a group is strong or weak depends on subtle patterns across the whole board. Strong players often describe their judgments as intuition.

That is why AlphaGo's two networks mattered so much. The policy network cut the number of moves to consider, and the value network supplied something like learned intuition about who is winning. Together they turned a search that was hopeless by brute force into one a computer could manage.