Martin Müller
NTT Communication Science Laboratories
Atsugi, Japan
mueller@rudolph.brl.ntt.co.jp
Minimax search has been used with great success to solve a number of games including Gomoku and Nine Men's Morris, and to reach a performance approaching or surpassing the best human players in other well-known games such as checkers, Othello and chess. All these high-performance game-playing programs use global search methods, which evaluate complete game positions.
Local search is an alternative approach that works well in the case where a game can be partitioned into independent subgames. The method of decomposition search (Mueller1999d) can solve such games by a combination of local combinatorial game search with evaluation techniques from combinatorial game theory.
We compare local and global search in endgame problems in the game of Go, which has been traditionally regarded as beyond the range of exact search-based solution methods. An endgame solver based on decomposition search can solve problems with solution lengths exceeding 60 moves.