A friend of mine who works at IBM recently introduced me to his latest work which involved the “Go” playing computer program Fuego (http://fuego.sourceforge.net/). Computationally, Go is much more difficult game for a computer to play then chess for the reasons that:
- The number of moves available on a chess board is around 40 possible moves vs 350 possible moves for a 19x19 “Go” board. This means that the search tree for next possible board states in "Go" expands much quicker then the next possible states for a chess board.
- It is much more difficult to evaluate which "Go" board states are better than other "Go" boards. This results in making it more difficult to search the game space as if each state is only slightly better or worse, you have to search farther to find a decidedly better game board.
The technology enabling this has type of innovation has not been faster CPU’s but the use of multiple CPU’s and the multi-threaded parallelism available in modern hardware architecture. The massive amount of extra computation cycles is used to investigate uncertain paths in the game space in parallel. The amazing part of this is that the basic Monte Carlo algorithm and how to do tree search in a game space has long been well known. What has changed is the algorithms to capitalize on the hardware are now just emerging. As the power of hardware increases, the ability to search more of the game space will increase. In the near future, either a future hardware upgrade, or another algorithmic innovation will lead to yet another game where humans take second place to the machines we have built.
If you want to read more about the innovations in Fuego and the revolution for “Go” playing software a fantastic summary of the innovation in Go playing is available in this PDF presentation (6 MB):
Monte-Carlo Simulation Methods in Games and Planning by Martin Müller