Ancestor-Based α-β Bounds for Monte-Carlo Tree Search

Upper Confidence bounds applied to Trees (UCT) is the default selection policy in Monte-Carlo Tree Search (MCTS), yet it overlooks the strategic use of ancestral node information. Consequently, UCT approaches each decision level as an independent Multi-Armed Bandit problem, disregarding the results achieved along the path that led to the current state. Consequently, it treats decisions as separate in the tree, without integrating the historical context of previous choices. This paper introduces an enhancement to UCT for two-player, deterministic zero-sum games by integrating insights from $\alpha-\beta$ pruning-a method that increases minimax search efficiency through selective pruning. We propose a revised selection policy that leverages ancestor node data, mirroring $\alpha-\beta$ pruning’s principle, to refine sample-based search. Our experiments with this enhanced method reveal performance gains in Breakthrough, Mini Shogi, and GoMoku, highlighting the effectiveness of incorporating ancestor search results into the MCTS selection processes.