Decomposition search (DS) is a method for computing minimax solutions to games that can be partitioned into independent subgames. DS does not use traditional minimax search algorithms, but relies on concepts from combinatorial game theory to do locally restricted searches and then combine the results. This divide-and-conquer approach allows the exact solution of much larger problems than is possible with classical methods such as alpha-beta. The main application is to Go endgames, but the approach is suitable for any game that can (at least sometimes) be broken down into independent subgames. Examples are Amazons or Snort.
M. Müller. Decomposition search: A combinatorial games approach to game tree search, with applications to solving Go endgames. In IJCAI-99, volume 1, pages 578-583, 1999.
M. Müller. Not like other games - why tree search in Go is different. In Proceedings of Fifth Joint Conference on Information Sciences (JCIS 2000), pages 974-977, 2000. Extended abstract, invited paper for special session on Heuristic Search and Computer Game Playing.
M. Müller and R. Gasser. Experiments in computer Go endgames. In R. Nowakowski, editor, Games of No Chance, pages 273-284. Cambridge University Press, 1996.
M. Müller. Computer Go as a Sum of Local Games: An Application of Combinatorial Game Theory. PhD thesis, ETH Zürich, 1995. Diss. ETH Nr. 11.006.
Martin Müller