Due to the incredible complexity of the game of Go the computer programs playing it could not utilise the brute force approach which has cracked chess. The method used by most Go programs instead is known as Monte Carlo tree search. The name is quite apt in that the algorithm runs through possible play sequences (game tree) using a random generator of moves (like a roulette in a Monte Carlo casino).
Instead of applying any strategic thought most Go computer programs start from the current board position and play millions of games consisting of completely random moves made by both players. When each games finishes the result is stored in the cells of computer memory corresponding to the moves selected. After millions of searches a picture is beginning to emerge of which move about to be made by the computer tends to statistically end up with a high probability of the computer winning – in multiple random sequences of games played to the end.
It is important to note that a Go program relying on Monte Carlo tree search does not need to “know” anything about the strategy of the game. It only needs to know which moves are legal (even if completely nonsensical) and play enough random simulations to arrive at statistically significant conclusions. This approach is devoid of any analysis and, predictably, Monte Carlo programs are not great at playing Go. While they reached a decent amateur level a while ago they had no chance against Go professionals who spend their lives studying the intricacies of the game and developing strategies to play it.
The challenge for the programmers was to improve the performance of the Monte Carlo algorithm by adding more Go-specific depth to it. The breakthrough was finally made by the DeepMind software team formed around 2014 and funded by Google. In October 2015 their creation, AlphaGo, managed to beat a competent professional player Fan Hui by 5 games to 0. The Go community was perplexed but most experts still believed AlphaGo stood no chance against a top human player. This was proved wrong when in March 2016 AlphaGo defeated a top ranking Go champion Lee Sedol by 4 games to 1. Following this match the program was awarded an honorary rank of 9 dan – the highest awarded to any human player.
So how did AlphaGo manage to deafeat Lee Sedol? Read on to find out!