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

TL;DR

This paper introduces "Decomposition Search," a novel approach to solving combinatorial games by breaking them into independent subgames. This method leverages combinatorial game theory to achieve significant speedups and solve much larger problems than traditional minimax search, particularly demonstrated in complex Go endgames.

What Problem Does This Paper Address?

Traditional game-playing AI, like minimax search with alpha-beta pruning, has achieved remarkable success in games like chess and checkers, even solving some simpler games entirely. However, these methods struggle with games that can be naturally decomposed into smaller, independent "subgames," such as the game of Go. In Go, a position can be viewed as a sum of local interactions. Traditional minimax search treats the entire game state globally, making it computationally infeasible to explore the vast search space of complex games like Go endgames. This paper addresses the challenge of efficiently computing optimal play in such decomposable combinatorial games.

Methods

The core innovation is Decomposition Search, a four-step algorithm:

  1. Game Decomposition and Subgame Identification: The game is broken down into independent subgames. For Go, this involves identifying "safe stones and territories" that isolate parts of the board.
  2. Local Combinatorial Game Search (LCGS): For each subgame, a specialized search is performed to generate a "game graph" representing all relevant local move sequences. This differs from standard minimax by not assuming alternating turns within a subgame and handling local cycles.
  3. Evaluation: The game graphs of subgames are evaluated using combinatorial game theory to determine their "combinatorial game values." This involves recursively calculating values for interior nodes based on evaluated leaf nodes.
  4. Sum Game Play: The combinatorial game values of the subgames are combined using combinatorial game theory to determine the overall optimal move for the entire game.

This approach contrasts with standard alpha-beta search by restricting the search scope to local subgames and using the mathematical framework of combinatorial game theory for evaluation and combination.

Datasets

The paper uses two representative Go endgame puzzles from [Berlekamp and Wolfe, 1994] as benchmarks:

  • 20 Point Problem (Problem C.9): A 9x9 board endgame reduced to 20 points, further simplified into 6 regions (A-F) for testing.
  • 89 Point Problem (Problem C.II): A 19x19 board endgame with 89 unsettled points, partitioned into 29 distinct endgame areas.

These are not new datasets but existing challenging endgame positions used to evaluate the proposed method against traditional approaches.

Key Insights and Ideas

  • Divide and Conquer for Games: The paper demonstrates that a divide-and-conquer strategy, by decomposing a complex game into smaller, manageable subgames, can dramatically outperform global search methods.
  • Power of Combinatorial Game Theory: The mathematical framework of combinatorial game theory is crucial for evaluating and combining the results from local subgame searches, enabling globally optimal play.
  • Local Search Efficiency: Restricting search to local subgames (LCGS) is significantly more efficient than full-board minimax search, especially when the game structure allows for effective decomposition.
  • Handling Game-Specific Structure: The success of decomposition search relies on identifying game-specific structures (like safe territories in Go) that enable meaningful decomposition.
  • Reusability of Partial Results: The evaluated subgames and their combinatorial game values can be stored in a database, leading to further speedups by avoiding recomputation.

Key Results

The paper shows substantial performance improvements for Decomposition Search over standard alpha-beta search on Go endgames:

  • 20 Point Problem: Decomposition search solved the full 20-point problem in approximately 0.2-0.3 seconds. Alpha-beta search, even with a large transposition table, struggled immensely, taking over 28 hours for the full problem. Table 1 shows that as the number of subgames increases, the node count for alpha-beta explodes, while decomposition search remains efficient.
  • 89 Point Problem: Decomposition search solved an optimal 62-move sequence in 1.1 seconds. Alpha-beta search faced similar computational challenges, with node counts and solution times increasing dramatically with the problem size (Table 2).
  • Against World Champion Program: In two test games against "The Many Faces of Go," decomposition search playing as Black gained one point, and as White, gained five points, demonstrating its ability to achieve near-perfect play.

Limitations and Future Work

  • Cyclic Subgames: Decomposition search can only handle cyclic subgames if the cycles do not affect optimal play. If cycles do impact optimal play, the method may fail or require more complex handling.
  • Computational Resources: The method is still subject to computational resource limitations. Decomposition might fail for very large subgames, LCGS might exceed time/space limits, or intermediate combinatorial game expressions could become too complex.
  • Game-Specific Decomposition: Finding a good decomposition is highly game-specific and requires expert knowledge (e.g., for Go).
  • Future Work: The authors suggest that further complexity reduction in intermediate expressions during local evaluation and summation could lead to even greater efficiency. The potential for reusing partial results in a persistent database is also highlighted as a significant avenue for speedup.

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{1999decomposition,
  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