Decomposition Search: A Combinatorial Games Approach to Game Tree Search, with Applications to Solving Go Endgames

Abstract

We develop a new method called decomposition search for computing minimax solutions to games that can be partitioned into independent subgames. The method does not use traditional minimax search algorithms such as alpha-beta, but relies on concepts from combinatorial game theory to do locally restricted searches. This divide-and-conquer approach allows the exact solution of much larger problems than is possible with alpha-beta. We show an application of decomposition search to the game of Go, which has been traditionally regarded as beyond the range of exact search-based solution methods. Our experiments with solving endgames show that alpha-beta searches already become impractical in positions with about 15 remaining moves. However, an endgame solver based on decomposition search can solve a much larger class of endgame problems with solution lengths exceeding 60 moves.