The game of Go

Cambridge researchers have analysed millions of patterns of potential moves to model the uncertainty of play in the ancient game of Go.

However, the game that emerges from these simple rules has defeated all attempts by AI researchers to program a computer to play it. Indeed, there is currently no Go program that can play better than a beginner on the full-size board.

The ancient Chinese two-player strategy game Go is presenting a ‘grand challenge’ to current artificial intelligence (AI) research. At first sight it appears straightforward: the players take it in turns to place black and white ‘stones’ on a grid with the aim of gaining control of the most territory. However, the game that emerges from these simple rules has defeated all attempts by AI researchers to program a computer to play it. Indeed, there is currently no Go program that can play better than a beginner on the full-size board.

Tree of possible futures

It might seem surprising that Go is so difficult to model, given the notorious defeat of World Champion Garry Kasparov by the chess computer Deep Blue in 1997. The trouble with Go is that the brute force technique that proved so successful for chess simply cannot be applied. Deep Blue worked by considering billions of possible future move sequences (searching about 12 moves into the future) and estimating the strength of the resulting game positions. This fails when applied to Go for two main reasons. First, the tree of possible futures is too big to explore usefully (on average, there are 220 legal moves for each turn in Go compared with about 35 in chess). Second, it is difficult to estimate the strength of a Go position: in chess we can sum the point values of the pieces on the board but no such simple heuristic exists for Go (all of a player’s stones are identical and take on their value from their relationship with surrounding stones).

Predicting human play

Go is an excellent test-bed for new techniques in AI because it is well defined by a set of simple rules yet remains sufficiently complex to challenge the state of the art. Also, a wealth of data exists about how humans play, in the form of records of historical games.

Professor David MacKay’s Inference Group at the Cavendish Laboratory, in collaboration with Dr Thore Graepel of the Applied Games Group at Microsoft Research, has focused on applying probabilistic modelling techniques to Go. By modelling the play of human experts, the aim is to predict human moves in the game records. One successful approach has been to represent each potential Go move by the pattern of stones surrounding the move location. Millions of these patterns were automatically harvested from 180,000 records of historical games. The decisions made by the players in all the game records were then used to determine the relative value of each of the patterns. This is possible because each recorded game position contains a set of legal moves, one of which we know was selected by the player, so we can infer that one move was more valuable than all of the other moves in that position. After being trained on all the game positions, the resulting system was able to predict the moves of human players more accurately and much more rapidly than other published results and was capable of playing the game surprisingly well.

Way to Go

We are still a long way from producing professional-level Go play. Formidable challenges remain, leading some researchers to argue that a strong Go-playing computer is still decades away. However, the fact that humans learn the game with relative ease provides tantalising evidence that, one day, it will be possible to create a strong Go program and, in so doing, perhaps increase our understanding of human intelligence.

For more information, please contact the author David Stern(dhs26@cam.ac.uk) at the Cavendish Laboratory, or visit the Inference Group website (www.inference.phy.cam.ac.uk/is) or the Applied Games Group website (http://research.microsoft.com/en-us/groups/apg/default.aspx). This work was supported by a grant from Microsoft Research through the PhD scholarship program (http://research.microsoft.com/en-us/collaboration/global/apply-europe.aspx).


This work is licensed under a Creative Commons Licence. If you use this content on your site please link back to this page.