Evolving Neural Networks to Focus Minimax Search

David E. Moriarty, Risto MiikkulainenAAAI 1994 · OpenReview

Abstract

Neural networks were evolved through genetic algorithms to focus minimax search in the game of Othello. At each level of the search tree, the focus networks decide which moves are promising enough to be explored further. The networks effectively hide problem states from minimax based on the knowledge they have evolved about the limitations of minimax and the evaluation function. Focus networks were encoded in marker-based chromosomes and were evolved against a full-width minimax opponent that used the same evaluation function. The networks were able to guide the search away from poor information, resulting in stronger play while examining fewer states. When evolved with a highly sophisticated evaluation function of the Bill program, the system was able to match Bill's performance while only searching a subset of the moves.

Introduction

Most game-playing AI systems historically relied on minimax search paired with a heuristic evaluation function. While effective, this approach suffers from two primary flaws. First, heuristic error propagation: since heuristics are approximations, errors in these estimates propagate up the search tree, often leading the AI to choose moves based on misinformation. Second, the "perfect opponent" assumption: minimax assumes optimal play from the opponent, which prevents taking calculated risks in losing situations where a sub-optimal move might provoke an error.

To address these issues, Moriarty and Miikkulainen (1994) introduced "Focus Networks"—neural networks evolved via genetic algorithms to prune minimax search trees. By learning to ignore moves that lead to unreliable heuristic evaluations, these networks allow for stronger play while searching significantly fewer game states than traditional full-width minimax algorithms.

Methods

The core innovation is the Focus Network, a neural network that acts as a filter for the search process. At each node in the search tree, the network evaluates the board state and assigns a value to every legal move. Only moves exceeding a specific threshold are explored further.

The Focus Network architecture maps the Othello board state to separate output units for player and opponent moves.

Key technical aspects of the implementation include:

  • Neuro-evolution: Since "correct" labels for focus windows are unknown, the authors used Genetic Algorithms (GA) to evolve network weights and architecture.
  • Marker-Based Encoding: Inspired by biological DNA, a marker-based chromosome defined the network, allowing the number of hidden units and connectivity patterns to emerge through evolution.
  • Dual Output Units: The network featured separate outputs for the player's and the opponent's moves, enabling the development of distinct offensive and defensive strategies.

The system was evaluated using Othello on an 8x8 grid, training against 244 unique board positions. It was tested against two programs: Iago (weak positional strategy) and Bill (world-class program with Bayes-optimized evaluation).

Key Insights and Results

The most significant insight is that the Focus Network acts as a "shield." By pruning moves where heuristic evaluation is likely to be erroneous, the network prevents misinformation from reaching the root decision node.

Focus networks shield the minimax root from misleading heuristic evaluations by pruning unreliable branches.

The experimental results demonstrated several key advantages:

  • Search Efficiency: A focused search at depth 2 proved as strong as a full-width exhaustive search at depth 4. On average, Focus Networks examined only 79% to 84% of the positions required by full-width search.
  • Performance Gains: Against the Iago heuristic, the focused search achieved a 65% win rate. When paired with the sophisticated Bill evaluation function, the system matched Bill's performance (51% win rate) while significantly reducing the search space.
  • Generalization: Networks trained at a search depth of 2 continued to outperform full-width search even when the depth was increased to 6, suggesting they learned fundamental features of promising moves.

Limitations and Future Work

Despite its success, the approach has limitations. Neural networks struggled to evolve into full evaluation functions, which require absolute numerical values comparable across different board states. Additionally, scaling to games with larger branching factors, like Chess, would require a more complex output structure, perhaps using a two-network approach for piece and destination selection. Future work could also explore "co-evolution," where the opponent's strength increases alongside the network's evolution to foster more robust defensive strategies.

Summary updated

Abstract

Neural networks were evolved through genetic algorithms to focus minimax search in the game of Othello. At each level of the search tree, the focus networks decide which moves are promising enough to be explored further. The networks effectively hide problem states from minimax based on the knowledge they have evolved about the limitations of minimax and the evaluation function. Focus networks were encoded in marker-based chromosomes and were evolved against a full-width minimax opponent that used the same evaluation function. The networks were able to guide the search away from poor information, resulting in stronger play while examining fewer states. When evolved with a highly sophisticated evaluation function of the Bill program, the system was able to match Bill's performance while only searching a subset of the moves.
BibTeX
@inproceedings{moriarty1994evolving,
  author = {David E. Moriarty and Risto Miikkulainen},
  title = {{Evolving Neural Networks to Focus Minimax Search}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1994},
  url = {https://openreview.net/forum?id=rJZ0ZCgd-B},
}
Figure