Communications of the ACM
BLOG@CACM
Better Game Playing Using Parallel Algorithms
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.
Up to a few years ago the software algorithms to play "Go" were good but never competitive with anything more than amateur players. Recently, an algorithmic change was introduced in 2006 to perform Monte Carlo tree search in exploring the "Go" board space. The Monte Carlo tree search algorithm would either try high scoring moves or in the absence of information begin randomly pursuing moves and speculatively searching down some of the tree search space. This speculative method increased the amount of search space explored and lead to better game states for the computer. Given the success of speculatively exploring the “Go” board, the algorithms were further enhanced by searching the space in parallel and innovations included the creation of multithreaded Monte Carlo search algorithms. The end result of these innovations resulted in the first defeat of a top human players in a tournament by 2009.
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
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
No entries found