TL;DR
This paper argues that the traditional focus on "game trees" has led researchers to overlook crucial graph properties of game states, resulting in an overestimation of current AI performance. By treating game states as graphs and exploiting properties like transpositions and irregular branching, the authors demonstrate significant improvements in search efficiency, suggesting new avenues for application-independent advancements in game AI.
What Problem Does This Paper Address?
For decades, artificial intelligence research in game playing, particularly for two-player, zero-sum games like chess and checkers, has centered around "game-tree search." This approach, heavily influenced by the Alpha-Beta algorithm, has traditionally viewed the search space as a tree. While this has led to impressive successes, the authors contend that this tree-centric view has obscured important underlying graph structures. Specifically, they argue that the concept of the "minimal tree" – the smallest tree an algorithm needs to search to find the optimal game value – is actually a "minimal graph" in real-world applications. This distinction matters because the minimal graph is significantly smaller than previously assumed, implying that current algorithms are not as efficient as believed and that there's more room for improvement than commonly thought. The paper aims to bridge this gap by exploring how to exploit these graph properties for more efficient game-tree search.
Methods
The paper introduces several novel application-independent search techniques that leverage graph properties:
- Minimal Graph (RMG) vs. Minimal Tree: The core idea is to redefine the performance benchmark. Instead of the "minimal tree" (Knuth & Moore, 1975), which assumes a perfect tree structure and move ordering, the authors propose the "real minimal graph" (RMG). The RMG accounts for transpositions (multiple paths leading to the same game state) and variable branching factors, leading to a much smaller theoretical search space. They propose an "approximate real minimal graph" (ARMG) computation method, which provides an upper bound on the RMG size.
- Enhanced Transposition Cutoffs (ETC): This technique aims to maximize the reuse of information stored in transposition tables. Before exploring a node's children, ETC checks if any of these children (or their descendants) have already been encountered and analyzed. If a cutoff is found through such a transposition, it can significantly prune the search.
- Exploiting Irregular Branching Factor (EIB): This method addresses games with variable branching factors (e.g., checkers, where capture moves drastically change the number of available moves). EIB prioritizes moves that lead to positions with smaller branching factors, as these are more likely to result in cheaper cutoffs. This is implemented as a bonus to the history heuristic.
Datasets
The authors evaluated their methods on two well-known game-playing programs:
- Chinook: A world-champion checkers program.
- Phoenix: A strong chess program.
These programs were used to test the effectiveness of the proposed techniques across games with varying average branching factors (low for checkers, high for chess). The experiments involved searching to fixed depths (17 ply for checkers, 8 ply for chess) on a set of test positions.
Key Insights and Ideas
- Game States are Graphs, Not Just Trees: The most fundamental insight is that the traditional "tree" model is an oversimplification. Transpositions mean states can be reached via multiple paths, making the search space a directed acyclic graph.
- The "Minimal Graph" is Much Smaller: The real minimal search space (RMG) is significantly smaller than the theoretical "minimal tree," especially in games with irregular branching and many transpositions. This implies that current high-performance programs are not as close to optimal as previously assumed.
- Information Reuse is Key: By actively looking for transpositions (ETC), algorithms can leverage past computations more effectively, leading to substantial search space reductions.
- Branching Factor Matters: In games with variable branching, intelligently ordering moves based on the expected branching factor of subsequent states (EIB) can lead to more efficient cutoffs.
- Even-Ply Search is Misleading: The paper highlights that reporting search efficiency based on odd-ply data can be misleading, as even-ply data often reveals more room for improvement, particularly in games like chess.
Key Results
- RMG vs. LFMG: The authors found that the "left-first minimal graph" (LFMG), an approximation of the RMG, was 25% larger than their upper bound on the RMG for chess and an astonishing 122% larger for checkers. This indicates that high-performance programs are not searching as efficiently as assumed.
- ETC Effectiveness: Enhanced Transposition Cutoffs (ETC) improved search efficiency by 28% for Phoenix (chess) and 22% for Chinook (checkers) at depth 8.
- EIB Effectiveness: Exploiting Irregular Branching Factor (EIB) provided an 8% improvement in checkers.
- Combined ETC + EIB: The combination of ETC and EIB yielded a cumulative 28% reduction in search nodes for checkers.
- Othello Results: For Othello, the LFMG was roughly 42% larger than the ARMG(2), suggesting room for improvement. ETC showed limited benefits (around 4%) due to infrequent transpositions, while EIB was not experimented with.
Limitations and Future Work
- ARMG Computation: Computing the exact RMG is intractable. The ARMG is an approximation and an upper bound. The procedure for computing ARMG(d) is still computationally intensive.
- Real-time vs. Off-line: The paper focuses on fixed-depth search. While ETC and EIB are presented as practical enhancements for real-time search, the off-line computation of RMG and ARMG is too slow for direct use.
- Game-Specific Effectiveness: The effectiveness of ETC and EIB is shown to be game-dependent. ETC is highly effective in games with many transpositions (chess), while EIB is more beneficial in games with irregular branching factors (checkers).
- Future Work: The authors suggest that their findings warrant more research into application-independent methods that exploit graph properties. They also mention that the new methods, along with MTD(f), represent the first major improvements to fixed-depth Alpha-Beta searching since 1983, indicating that the field is far from closed. They also note that while ETC and EIB are application-independent, their performance is tied to game properties, and further research into how to best apply them across different games is needed.
Summary updated