Partition Search

AAAI 1996

TL;DR

This paper introduces "partition search," a novel game-tree search algorithm that significantly reduces the search space by grouping similar game positions. By leveraging dependency analysis and extending transposition tables to store sets of positions, partition search achieves substantial performance improvements, particularly in games like bridge.

What Problem Does This Paper Address?

Traditional game-tree search algorithms, like minimax and alpha-beta pruning, often explore redundant branches of the game tree. For instance, in chess, if a player has a forced win, a machine might still spend considerable effort analyzing every possible losing move for the opponent, even if the refutation is identical for many of them. Conventional pruning techniques struggle with this redundancy because they analyze moves individually. The paper aims to address this inefficiency by developing a method that can recognize and exploit situations where multiple distinct game states lead to the same outcome, thereby avoiding redundant computation.

Methods

The core innovation is partition search, which builds upon existing techniques like alpha-beta pruning and transposition tables. Instead of storing individual game positions in the transposition table, partition search stores sets of positions that are known to lead to a particular outcome. This is achieved by:

  • Dependency Analysis: Inspired by dependency maintenance in AI, the algorithm identifies the underlying reasons for a game state's evaluation.
  • Partition System: A formal framework is introduced with functions (P, R, C) that define how to group positions that evaluate similarly and how to approximate the sets of positions that can reach a known winning or losing state.
  • Extended Transposition Tables: Transposition tables are modified to store sets of positions along with their computed values and cutoff bounds.
  • Zero-Window Search: To handle games that don't have simple win/loss outcomes (like bridge, which can have draws or intermediate values), the algorithm incorporates zero-window search, a technique for efficiently determining if a position's value is above or below a certain threshold.

Datasets

The paper evaluates partition search on 1000 randomly generated bridge hands. No new benchmarks are introduced; instead, the performance is compared against conventional alpha-beta pruning with transposition tables on this existing domain.

Key Insights and Ideas

  • Exploiting Redundancy: The fundamental insight is that many distinct game states can be evaluated identically because the underlying reason for their outcome is local and shared. Partition search formalizes and exploits this redundancy.
  • Sets over Singletons: Extending transposition tables to store sets of positions, rather than just single positions, is the key to achieving significant pruning. This allows the algorithm to "back up" conclusions about entire groups of similar states.
  • Bridge as a Suitable Domain: Bridge is highlighted as an ideal domain because its rules allow for the abstraction of specific cards into general categories (e.g., "small cards"), and the outcomes of many situations are local, making partition search highly effective.
  • Dependency Maintenance in Adversarial Search: The paper successfully bridges the gap between dependency maintenance techniques (often used in planning) and adversarial game-tree search, leveraging the existing infrastructure of transposition tables.

Key Results

  • Partition search achieves substantial performance improvements in bridge, leading to an order of magnitude or more reduction in the number of nodes expanded on fairly small search spaces (around 10^6 nodes).
  • The effective branching factor reduction is estimated to be around b^0.76, significantly outperforming conventional alpha-beta pruning.
  • The algorithm is capable of analyzing hands to termination, with search depths varying from 12 to 48.

Limitations and Future Work

  • Computational Representation: The effectiveness of partition search relies on finding computationally effective ways to represent and approximate the sets of positions (Ro and Co functions). The paper assumes such methods exist but doesn't detail their implementation for all games.
  • Domain Specificity: While bridge is a strong domain, the paper acknowledges that the suitability of partition search depends on the game's properties, specifically the ability to perform partition-like analysis and build accurate approximating functions.
  • Future Work: The paper suggests that further research could explore more sophisticated approximation functions and data structures for partition systems, potentially extending the benefits to a wider range of games.

Summary updated

BibTeX
@inproceedings{1996partition,
  title = {{Partition Search}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1996},
}

Loading related content...

Figure