Abstract: It is known that bounds on the minimax values of nodes in a game tree can be used to reduce the computational complexity of minimax search for two-player games. We describe a very simple method to estimate bounds on the minimax values of interior nodes of a game tree, and use the bounds to improve minimax search. The new algorithm, called forward estimation, does not require additional domain knowledge other than a static node evaluation function, and has small constant overhead per node expansion. We also propose a variation of forward estimation, which provides a tradeoff between computational complexity and decision quality. Our experimental results show that forward estimation outperforms alpha-beta pruning on random game trees and the game of Othello.
Introduction
In two-player zero-sum games like Chess or Othello, computers rely on minimax search to identify optimal moves. However, the exponential growth of game trees limits search depth. While alpha-beta pruning is the standard for reducing this complexity, it often explores branches that are unlikely to influence the final decision. Previous "selective search" methods aimed to prune these unpromising branches but often required complex domain-specific knowledge or introduced significant computational overhead.
This paper introduces Forward Estimation (FE), a low-overhead method for pruning game trees. By estimating the range of possible minimax values for interior nodes using only a static evaluation function, FE allows for significantly deeper searches than standard alpha-beta pruning with minimal computational cost.
Methodology: The Forward Estimation Algorithm
Forward Estimation treats the game tree as an "incremental random tree," where a node's value is the sum of "edge costs" (the change in evaluation) from the root. The algorithm operates on three core principles:
- Bounding the Future: Given a minimum ($l$) and maximum ($u$) possible change an edge can introduce, a subtree of depth $d$ with a current root evaluation $c$ will have a final minimax value within the range $[c + l \cdot d, c + u \cdot d]$.
- Pruning Conditions: FE enhances standard alpha-beta pruning with two new conditions:
- MIN node: Prune if the maximum possible future value ($c + u \cdot d$) is $\le$ the current $\alpha$ bound.
- MAX node: Prune if the minimum possible future value ($c + l \cdot d$) is $\ge$ the current $\beta$ bound.
- Selective Search Parameter ($\delta$): To enable more aggressive pruning, a parameter $\delta \in [0, 1]$ is introduced. Using $u \cdot \delta$ and $l \cdot \delta$ allows the algorithm to trade off decision quality for significantly greater search depth.
Bounds ($l$ and $u$) can be determined via evaluation function analysis, offline pre-sampling, or online tracking during the search itself.
Experimental Evaluation
The algorithm was evaluated using two primary benchmarks:
- Incremental Random Trees: Synthetic trees with uniform and random branching factors and integer edge costs, providing a controlled environment to test mathematical properties.
- Othello: A real-world test using the evaluation function from "Bill," a world-class Othello program.
Results and Performance Analysis
Experimental results demonstrate that FE consistently outperforms alpha-beta pruning. In random trees, FE reached a depth of 11 in the same time alpha-beta reached depth 10. Remarkably, FE can achieve a smaller effective branching factor than alpha-beta even when the latter has perfect node ordering, as FE prunes based on future potential that alpha-beta is forced to verify.
In head-to-head Othello tournaments, FE consistently beat alpha-beta. When the alpha-beta search horizon was set to 8, FE searched three levels deeper using the same computational resources. The results indicate that searching deeper with a "near-exact" value (via FE) is often superior to searching shallower with an "exact" value (via standard alpha-beta).
Discussion and Future Work
While FE shows significant promise, its effectiveness depends on the correlation between parent and child node evaluations. In games with highly volatile evaluations, the bounds may be too wide for effective pruning. Additionally, while offline learning was successful for Othello, the online learning scheme struggled, likely due to the "locality" of evaluations in that domain. Future work will investigate dynamic tuning of the $\delta$ parameter and methods to improve online learning across diverse game types.
Summary updated