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

Martin Müller

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.

Introduction

Traditional game-tree search, exemplified by the alpha-beta pruning algorithm, has been the cornerstone of computer game play for decades. While highly effective in games like Chess, these methods struggle in games with high branching factors or those that can be decomposed into independent components. Go is a prime example of the latter. In the endgame phase of Go, the board often fragments into isolated areas separated by "safe" stones. A move in one corner typically has no impact on the status of a group in the opposite corner.

Standard alpha-beta search fails to exploit this independence. It continues to explore every possible interleaving of moves across all areas, leading to an exponential explosion of the search space. Consequently, alpha-beta becomes impractical in Go positions with as few as 15 remaining moves. This paper introduces Decomposition Search, a method that replaces global minimax search with local analysis rooted in Combinatorial Game Theory (CGT).

The Decomposition Search Algorithm

Decomposition Search treats a game not as a single monolithic puzzle, but as a collection of smaller, independent subgames. The algorithm follows a four-step process:

  1. Decomposition: The board is partitioned into independent subgames. In Go, this is achieved by identifying "safe" stones and territories that act as boundaries between isolated regions.
Visualizing the partition of a Go board into independent local areas.
  1. Local Combinatorial Game Search (LCGS): Instead of a global search, a specialized search is performed for each subgame. Unlike minimax, LCGS does not assume players alternate turns within that specific subgame, as a player might choose to play elsewhere on the board for several turns. It generates a game graph of all relevant local move sequences.
  2. Evaluation: These local game graphs are mapped to mathematical values using CGT. Each subgame is assigned a value (such as a number or a complex CGT expression) representing its worth and its "temperature" (the incentive for a player to move there).
  3. Sum Game Play: The "calculus" of CGT is used to combine these local values. By calculating the incentive—the improvement a move brings to a local position—the algorithm determines the globally optimal move across all subgames without ever searching the full board state space.

Experimental Results

The method was evaluated using Go endgame puzzles from Berlekamp and Wolfe’s Mathematical Go. The performance gap between decomposition search and traditional methods was found to be staggering.

A 9x9 Go board (Problem C.9) decomposed into six independent subgames (A-F) for local analysis.

In a test on Problem C.9 (a 20-point endgame on a 9x9 board), a standard alpha-beta search required over 28 hours to find the solution. In contrast, decomposition search solved the same problem in just 0.3 seconds. The scaling advantages became even more apparent on Problem C.11, an 89-point endgame on a 19x19 board. Decomposition search found the optimal 62-move sequence in 1.1 seconds. For comparison, alpha-beta search took nearly 7 hours (25,044 seconds) just to solve a small 24-point subset of that same problem.

When tested against "The Many Faces of Go," a world-champion level program of the era, the decomposition search-based solver consistently gained points by playing mathematically perfect endgames that the heuristic-based program could not calculate.

Conclusion and Future Work

The primary insight of this research is that the complexity of decomposition search is exponential only in the size of the largest subgame, whereas alpha-beta is exponential in the size of the entire game. This allows for the exact solution of problems previously considered intractable.

However, limitations remain. The current framework is designed for acyclic games; subgames containing cycles (like Ko in Go) require specialized handling. Additionally, the method relies heavily on the ability to correctly partition the board. If the "walls" between subgames are not truly safe, the independence assumption breaks down. Future work will focus on improving static rules for recognizing safe territories and integrating these techniques with broader endgame databases.

Summary updated

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.
BibTeX
@inproceedings{muller1999decomposition,
  author = {Martin Müller},
  title = {{Decomposition Search: A Combinatorial Games Approach to Game Tree Search, with Applications to Solving Go Endgames}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1999},
}
Figure