MCTS-Minimax Hybrids with State Evaluations (Extended Abstract)

Hendrik Baier, Mark H. M. WinandsIJCAI 2018 · DOI

TL;DR

This paper explores how to combine the strengths of Monte-Carlo Tree Search (MCTS) and minimax search by integrating heuristic state evaluations. They propose three novel ways to use these evaluations within MCTS, finding that using them to inform node priors (MCTS-IP) yields the most promising results, especially when combined with advanced search techniques like move ordering and k-best pruning.

What Problem Does This Paper Address?

Monte-Carlo Tree Search (MCTS) has achieved remarkable success in games like Go, leveraging simulations to explore vast game trees. However, in tactical games with many shallow traps (like Chess), MCTS can sometimes miss critical moves due to its selective sampling. Traditional minimax search, on the other hand, excels at tactical precision but can struggle with the sheer size of game trees. This paper aims to bridge this gap by creating MCTS-minimax hybrids that leverage heuristic state evaluation functions to improve MCTS's performance, particularly in tactical domains. The challenge is to effectively integrate these evaluations without incurring prohibitive computational costs.

Methods

The authors propose three distinct methods for integrating heuristic state evaluations into MCTS:

  • MCTS with Informed Rollouts (MCTS-IR): Uses heuristic evaluations to guide the random moves chosen during the simulation (rollout) phase of MCTS, aiming for more accurate outcome predictions.
  • MCTS with Informed Cutoffs (MCTS-IC): Employs heuristic evaluations to terminate rollouts early if a state's value can be reliably estimated, avoiding potentially noisy further simulation steps.
  • MCTS with Informed Priors (MCTS-IP): Leverages heuristic evaluations to assign "prior" values to nodes in the MCTS tree. These priors bias the search towards more promising branches from the outset.

For each of these approaches, they consider two variants: one using simple heuristic function calls (denoted by "-E") and another using shallow depth minimax searches to compute the state evaluations (denoted by "-M"). The "-M" variants are the core of their novel contributions, aiming to provide more robust evaluations than simple heuristics. They also explore enhancements to the minimax search within these hybrids, specifically move ordering and k-best pruning, to mitigate the computational cost associated with deeper searches.

Datasets

The paper evaluates their proposed algorithms on three deterministic, perfect-information, turn-taking zero-sum games:

  • Othello
  • Breakthrough (6x6 board)
  • Catch the Lion

These domains were chosen to represent a range of branching factors and tactical complexities. No new datasets were introduced; the evaluation was performed on established game environments.

Key Insights and Ideas

  • Minimax for Priors is Promising: The most significant finding is that using enhanced minimax search to compute priors for MCTS nodes (MCTS-IP-M) is a highly effective strategy. This approach seems to strike a good balance between leveraging minimax's tactical strength and MCTS's strategic exploration.
  • Computational Cost is a Major Hurdle: Simply embedding minimax searches into rollouts (MCTS-IR-M) or using them for cutoffs (MCTS-IC-M) proved too computationally expensive, especially in domains with higher branching factors. The frequent calls to minimax significantly slowed down the overall search.
  • Move Ordering and K-Best Pruning are Crucial: To make the minimax-enhanced hybrids practical, enhancements to the minimax search itself were necessary. Move ordering and k-best pruning dramatically improved performance by reducing the effective branching factor and focusing the search on more promising moves.
  • MCTS-IP-M-k Outperforms: The enhanced MCTS-IP-M variant (MCTS-IP-M-k), which uses minimax for priors and incorporates move ordering and k-best pruning, emerged as the strongest hybrid across all tested domains and time settings.
  • Synergy of MCTS and Minimax: In Breakthrough, the best hybrid (MCTS-IP-M-k) not only outperformed its individual MCTS and minimax components but also surpassed a standalone alpha-beta search, demonstrating that combining these approaches can indeed create an algorithm stronger than its parts.

Key Results

  • MCTS-IP-M-k is the Champion: This hybrid consistently outperformed other MCTS-minimax variants and even standalone alpha-beta search in Breakthrough.
  • Breakthrough Advantage: The hybrid approach showed a clear advantage in Breakthrough, where it could combine MCTS's strategic depth with minimax's tactical precision.
  • Domain Sensitivity: The performance of the hybrids was sensitive to the branching factor of the domain. Higher branching factors made the unenhanced minimax integrations too slow.
  • Time Settings: MCTS-IP-M-k performed well across various time settings, though it could overfit to specific tuning times.
  • Minimax Depth Matters: For MCTS-IP-M-k, optimal minimax search depths were found to be greater than 1, indicating that deeper tactical analysis was beneficial. In contrast, for MCTS-IR-M-k and MCTS-IC-M-k, the optimal minimax depth was often just 1, suggesting their strength came more from the search enhancements than the embedded minimax itself.

Limitations and Future Work

  • Branching Factor Sensitivity: The paper acknowledges that the hybrids' sensitivity to the branching factor remains a challenge, even with enhancements.
  • Potential for Further Optimization: The authors suggest exploring more advanced alpha-beta enhancements like dynamic move ordering (killer moves, history heuristic) and investigating how to more optimally exploit domain knowledge.
  • Domain Understanding: Further research is needed to understand how different domain properties (e.g., trap density, progression) influence hybrid performance.
  • Deep Learning Integration: The paper highlights the success of deep reinforcement learning in AlphaZero and suggests it would be interesting to see how powerful function approximators could be integrated into these hybrid search algorithms.

Summary updated

BibTeX
@inproceedings{baier2018mcts,
  author = {Hendrik Baier and Mark H. M. Winands},
  title = {{MCTS-Minimax Hybrids with State Evaluations (Extended Abstract)}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.24963/ijcai.2018/782},
}
Figure