Best-First Minimax Search: Othello Results

Richard E. Korf, David Maxwell ChickeringAAAI 1994

Abstract

This paper presents Best-First Minimax Search, a selective search algorithm for two-player games that prioritizes expanding the "principal leaf"—the specific node currently determining the root's value. By focusing on the most promising lines of play, the algorithm can reach significantly greater depths than traditional fixed-depth alpha-beta search. Experiments in Othello demonstrate that a hybrid model combining shallow alpha-beta search with best-first extensions achieves a ~67% win rate against standard alpha-beta, highlighting the advantages of selective deep-searching over exhaustive breadth-first approaches.

Introduction

In the early 1990s, game-playing AI primarily utilized full-width, fixed-depth minimax search with alpha-beta pruning. These algorithms evaluate every possible move sequence up to a predetermined depth. However, this approach differs significantly from human cognition, which ignores obviously poor moves to explore critical lines dozens of plies ahead. While selective search algorithms like B* existed, they were often computationally expensive or memory-intensive. The authors sought a selective algorithm as simple as alpha-beta that could "tunnel" deeper into the most important parts of the game tree.

Methods

The research introduces three iterations of the search strategy:

  1. Best-First Minimax: This algorithm identifies the principal variation—the path from the root to a leaf where every node shares the same minimax value—and expands the principal leaf at its terminus.
  2. Recursive Best-First Minimax Search (RBFMS): To address the exponential memory requirements of standard best-first search, RBFMS provides a linear-space implementation ($O(bd)$). It utilizes Alpha and Beta bounds to determine when to backtrack and "forget" branches, mimicking depth-first search while maintaining best-first behavior.
  3. Best-First Extension (The Hybrid): To mitigate "blind spots" where a node appears poor statically but leads to a win, the authors developed a hybrid approach. It performs a shallow alpha-beta search to ensure minimum breadth coverage before using best-first search to explore promising branches much deeper.
Sequence of tree expansions in Best-First Minimax Search showing the iterative growth of the search tree.

Key Insights and Results

The study revealed several critical properties that distinguish best-first search from its fixed-depth counterparts:

  • The Tempo Effect: A common concern with selective search is that it might descend into an infinite "rabbit hole" on a single branch. However, the authors observed a natural self-balancing mechanism termed the "tempo effect." When the algorithm expands a MAX node, the node's value typically increases. Because the parent is a MIN node, this increase makes the branch less attractive to the parent, which then shifts the search focus to explore sibling nodes. This ensures the search remains relatively balanced without explicit breadth-first constraints.
  • Tree Persistence: Standard alpha-beta implementations often discard the search tree between moves. In contrast, Best-First Minimax benefits significantly from tree persistence. Because it focuses on the most likely lines of play, a large portion of the previously explored tree remains relevant for the next move, allowing the engine to build upon its previous computations.
The RBFMS process illustrating how alpha and beta bounds guide the selective expansion and backtracking.

In Othello tournaments involving 488 games per data point, pure best-first search demonstrated remarkable depth, reaching up to 23 plies in the same time alpha-beta reached only 7. This led to a peak 78% win rate at moderate search depths. However, performance eventually plateaued and degraded at extreme depths because pure selectivity can be "blind" to moves that appear weak statically but are strategically sound.

The Best-First Extension hybrid addressed this by combining a shallow alpha-beta "look-around" with deep best-first "tunnels." This model was the clear champion, consistently defeating standard alpha-beta across all tested depths with a 2-to-1 win ratio (67%). These results were further validated on synthetic random game trees, proving the algorithm's robustness across different branching factors.

Conclusion

Best-First Minimax Search offers a robust alternative for games with large branching factors or expensive evaluation functions. While RBFMS solves memory constraints, the authors found that in practice, retaining the search tree in memory and pruning less promising branches was more efficient for Othello. Future work will focus on tighter integration of endgame play and the implementation of "singular extensions" to further refine move selection.

Summary updated

BibTeX
@inproceedings{korf1994best,
  author = {Richard E. Korf and David Maxwell Chickering},
  title = {{Best-First Minimax Search: Othello Results}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1994},
}
Figure