Abstract
This paper presents ITERSSS, a game tree search algorithm that adaptively utilizes available memory to optimize search efficiency. By parameterizing the size of the search's priority queue (the OPEN list), ITERSSS bridges the gap between the memory-efficient Alpha-Beta procedure and the node-efficient SSS algorithm. Experimental results on uniform game trees demonstrate that ITERSSS consistently outperforms Alpha-Beta even with minimal memory and matches SSS* performance when sufficient memory is provided, offering a flexible "memory-efficiency slider" for game tree search.
Introduction
In the field of artificial intelligence, game tree search has traditionally been dominated by two distinct paradigms. Alpha-Beta Pruning is the industry standard due to its minimal memory footprint—$O(d)$, where $d$ is the tree depth—but it often visits more terminal nodes than strictly necessary. Conversely, SSS, introduced by Stockman in 1979, is a best-first search that visits significantly fewer nodes but requires exponential memory—$O(b^{d/2})$—to maintain its priority queue. For many practical applications, SSS is unusable because it exceeds available RAM.
The ITERSSS* Algorithm
ITERSSS (Iterative SSS) addresses this "efficiency gap" by making the size of the OPEN list a user-defined parameter, $M$. The algorithm manages memory through four distinct node states:
- LIVE: Unexplored nodes.
- SOLVED: Nodes with a determined value.
- ACTIVE: Nodes currently participating in the best-first search.
- INACTIVE: Nodes suspended due to memory limits.
When the OPEN list reaches the limit $M$, new nodes are marked as INACTIVE and held in "suspended animation." These nodes do not participate in selection until space is freed by solved nodes. This mechanism allows for graceful degradation: with large $M$, ITERSSS behaves like SSS; with minimal $M$, it approximates the depth-first behavior of Alpha-Beta.
The authors identified a minimum memory threshold, $M_0 = \lceil d/2 \rceil \cdot (b - 1) + 1$, which is comparable to Alpha-Beta's requirements. Crucially, they proved that ITERSSS* will never examine a terminal node that Alpha-Beta would have pruned, making it a guaranteed improvement over Alpha-Beta whenever extra memory is available.
Experimental Evaluation
The researchers evaluated ITERSSS* using synthetic uniform game trees with varying branching factors ($b$) and depths ($d$). Terminal node values were generated randomly, and the algorithm was tested on a VAX 11/750.
As shown in the experimental data, search efficiency scales directly with available memory. For a tree with $b=3$ and $d=10$, Alpha-Beta visited 10.44% of terminal nodes. ITERSSS with minimal memory ($M=11$) already improved this to 10.11%. As $M$ increased to 243, ITERSSS matched the 6.44% efficiency of SSS*.
Conclusion
ITERSSS* provides a robust framework for trading memory for search speed. While it introduces some bookkeeping overhead due to priority queue management, its ability to outperform Alpha-Beta with even modest memory gains makes it a valuable tool for resource-constrained environments. Future work remains to analyze its average-case performance mathematically and to test its efficacy on non-uniform trees found in complex games like Chess or Go.
Summary updated