Accelerated UCT and Its Application to Two-Player Games

The Accelerated UCT algorithm is introduced as a solution to the over-optimistic behavior and deceptive structures inherent in standard Monte-Carlo Tree Search (MCTS) when applied to two-player games. While traditional Upper Confidence bound applied to Trees (UCT) can converge to optimal strategies given infinite time, it often selects suboptimal moves in practice due to inaccurate winning ratios derived from limited playouts. Accelerated UCT addresses this by employing a new backup operator that assigns higher weights to recently visited actions, effectively prioritizing recent, more reliable playout results while maintaining the integrity of past data.

The methodology involves a velocity-based weighting system that non-uniformly decreases the reliability of subtrees containing older playout results. Unlike Discounted UCB, which can suffer from excessive "forgetting" of valuable historical information, Accelerated UCT remains robust by balancing recent performance with historical context. The algorithm also incorporates a virtual child mechanism to ensure that playout results from expanded nodes are appropriately integrated into the search tree.

Experimental results across Othello, Havannah, and Go demonstrate that Accelerated UCT consistently outperforms both plain UCT and Discounted UCT. Notably, when integrated into Fuego—a high-performance computer Go program—Accelerated UCT provided a statistically significant improvement in playing strength, even when combined with existing enhancements like Rapid Action Value Estimate (RAVE). These findings suggest that the algorithm effectively mitigates deceptive structures that remain uncorrected by standard domain-dependent playout policies. Future development aims to automate the selection of the decay parameter, which currently requires empirical tuning based on the specific game domain and time constraints.