Chess and Go are both simplified examples of "inexact problems" that have no clear solution algorithm. Humans can be quite skilled at these problems, even if it is not clear how they do it. Go is a whole new challenge... Because global changes occur slowly in Go, the game is much better suited to studying complex information management and decision making than is chess.
- Bruce Wilcox, from Computer Go, reprinted in Computer Games II, ed. by David L. Levy, 1988. New York: Springer Verlag.
If you want to understand intelligence, the game of Go is much more demanding ... It doesn't have the silver bullet: deep search. Chess has somewhat outlived its usefulness. It turned out to be easier than we thought.
- Jonathan Schaeffer, in Chess - Man vs. Machine Plays Out
Go is the last of the classical two-player board games where humans are still clearly superior to programs, a traditional strategy game played in Japan, China (weiqi), and Korea (baduk). Humans have studied this game intensely for centuries, and there are hundred of professional Go players. The rules of the game are very simple but play is complex. In Go, no successful evaluation function for non-terminal positions has ever been found. Therefore, it is not merely a problem that will be solved with faster search, but an interesting test case for AI --- it pushes the boundaries of what is possible with new algorithms such as Monte Carlo methods.
Work on computer Go started in the 1960's and accelerated in the mid 1980's with the appearance of personal computers and the advent of regular computer Go competitions. Until 2006, programs were based on:
- large amounts of game-specific heuristics such as patterns
- goal-oriented searches, for example to try to capture blocks of stones of the same color, or make life with groups of stones.
- very limited, selective global alpha-beta search
Despite large-scale efforts, progress was limited, and programs remained prone to embarassing blunders caused by gaps and inconsistencies in their knowledge bases. Performance was much better for specialized subtasks than for the full game of Go. Programs could solve difficult endgame puzzles by using a divide and conquer approach based on combinatorial game theory, and became expert in solving so-called Life and Death (Tsume Go) problems, which are amenable to deep, exhaustive search.
From 2006 on, the new approach of Monte Carlo Tree Search was developed, and it took the world of Computer Go by storm. Programs have almost drawn level with top human professionals on the small 9x9 board. In the full game, top programs can now win with occasionally with 7 stones handicap against top human players.