Searching Game Trees Under Memory Constraints

AAAI 1996

TL;DR

This paper introduces MemSSS, a novel memory-controlled game-tree search algorithm that significantly improves upon existing methods like Alpha-Beta and IterSSS. MemSSS* achieves a superior balance of pruning power, running time, and memory efficiency, making best-first search competitive with depth-first search in complex game environments.

What Problem Does This Paper Address?

Game tree search algorithms are fundamental to artificial intelligence, particularly in games like chess and Go. A classic algorithm, Alpha-Beta pruning, is a depth-first search that efficiently prunes branches of the game tree that are unlikely to lead to an optimal solution. However, another algorithm, SSS, offers superior pruning power but suffers from high memory requirements and slow execution, limiting its practical use. While various modifications to SSS have been proposed, they often address only one of these limitations, either increasing memory needs or remaining slow. This paper tackles the challenge of developing a game-tree search algorithm that simultaneously offers strong pruning, fast execution, and efficient memory management, aiming to bridge the gap between the theoretical advantages of best-first search and the practical constraints of real-world applications.

Methods

The core contribution of this paper is the MemSSS algorithm, a new memory-controlled best-first search scheme. MemSSS is presented as a synthesis of two previous algorithms: RecSSS (which offers good speed but high memory usage) and IterSSS (a memory-controlled version of SSS* that is slower).

MemSSS* achieves its efficiency through several key innovations:

  • Recursive Structure: Like RecSSS, MemSSS employs a recursive approach, which helps manage the search frontier and avoid the overhead of explicit queue management.
  • Controlled Memory Allocation: Unlike IterSSS, which uses a global pool for memory, MemSSS allocates memory to individual non-terminal MAX nodes. This memory is then used to search the subtree rooted at that node.
  • Dynamic Memory Distribution: When a node is expanded, its allocated memory is distributed among its children. This distribution is guided by minimum and maximum memory requirements for subtrees, ensuring that memory is used effectively even when it's scarce. Inactive nodes (those whose exploration is deferred due to memory limitations) are managed to ensure that the lexicographically smallest inactive node is activated when memory becomes available.
  • No Node Purging: Similar to RecSSS, MemSSS avoids the need to purge nodes from its search frontier (OPEN list) when a node is solved. This is achieved by maintaining information about non-terminal MAX predecessors, which significantly speeds up execution.

Datasets

The paper does not describe specific datasets in the traditional sense of pre-existing benchmark collections. Instead, it focuses on generating uniform game trees with varying branching factors (b) and depths (d) for experimental evaluation. These trees are either:

  • Randomly ordered: Terminal node scores are generated using random number generators.
  • Strongly ordered: These trees are designed such that the optimal move is consistently among the first few choices, mimicking more realistic game scenarios.

The generation of these trees and the assignment of static evaluation scores to terminal nodes are described as part of the experimental setup.

Key Insights and Ideas

  • Best-First Search Can Compete: The paper convincingly argues that best-first search algorithms, when properly designed, can rival or even surpass depth-first search algorithms like Alpha-Beta in terms of performance across multiple metrics.
  • Memory Management is Key: The success of MemSSS* hinges on its sophisticated memory management. By allocating memory dynamically to individual nodes and distributing it intelligently, it can adapt to varying memory constraints far more effectively than previous methods.
  • Recursive Structure Simplifies and Speeds Up: Adopting a recursive structure, inspired by RecSSS, eliminates the need for explicit node purging, a significant bottleneck in earlier SSS variants.
  • Pruning Power Increases Uniformly with Memory: A crucial finding is that MemSSS*'s pruning power scales smoothly with available memory, offering a predictable performance improvement as more resources are allocated.
  • Never Worse Than Alpha-Beta (in pruning): A significant theoretical and practical insight is that MemSSS* never examines a terminal node that would have been pruned by Alpha-Beta, even at its minimum memory configuration. This guarantees a baseline level of efficiency.

Key Results

The experimental results demonstrate MemSSS*'s strong performance across various scenarios:

  • Strongly Ordered Trees: MemSSS examined fewer terminal nodes and ran faster than Alpha-Beta, especially on trees with odd depths, even when using significantly less memory than required by RecSSS. For instance, on a (6,9) uniform tree with limited memory, MemSSS* outperformed Alpha-Beta in both terminal count and running time.
  • Randomly Ordered Trees: While MGame (specifically QuickGame) was superior at minimum memory, MemSSS showed significant improvements as memory increased. At maximum memory, MemSSS examined about a third of the terminal nodes and ran twice as fast as Alpha-Beta.
  • Memory Efficiency: MemSSS* effectively utilizes any available memory, unlike MGame which operates on discrete memory "slabs."
  • Comparison with IterSSS*: MemSSS was significantly faster than IterSSS, especially at higher memory allocations, becoming 2.5 to 3 times faster than IterSSS* at maximum memory.

Limitations and Future Work

  • Exact Pruning Conditions: The paper acknowledges that determining the exact pruning conditions for MemSSS is an area for future work. While partial conditions for IterSSS exist, the different memory allocation schemes in MemSSS* mean these would not be identical.
  • MemDual* Potential: The authors suggest that a counterpart to MemSSS, named MemDual, could be developed by modifying RecDual* to achieve better performance than Alpha-Beta on strongly ordered trees of even depth.
  • Direct Coding of RecSSS*: The paper notes that a direct coding of RecSSS might offer slightly better performance than MemSSS or MGame at maximum memory due to lower overhead, implying that further micro-optimizations are possible.

Summary updated

BibTeX
@inproceedings{1996searching,
  title = {{Searching Game Trees Under Memory Constraints}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1996},
}
Figure