Proceedings

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

Martin Müller

Download BibTeX Cite

Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence. Computer Game Playing. Pages 578-582.

Abstract

We develop a new method ca ll ed 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 alphabe ta 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 .

Martin Müller. 1999. Decomposition Search: A Combinatorial Games Approach to Game Tree Search, with Applications to Solving Go Endgames. In Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, IJCAI-99. IJCAI, 578–582. https://ijcai.org/proceedings/1999/83
Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards