---
title: "Decomposition Search: A Combinatorial Games Approach to Game Tree Search, with Applications to Solving Go Endgames"
authors:
  - "Martin Müller"
doi: ""
url: "https://ijcai.org/proceedings/1999/83"
pdf: "https://ijcai.org/proceedings/1999/0083.pdf"
venue: "Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence"
year: 1999
pages: "578-582"
track: "Computer Game Playing"
keywords:
---

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

Martin Müller

*Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence*, 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 .