Efficiency of Static Knowledge Bias in Monte-Carlo Tree Search

This analysis examines the integration of static knowledge into Monte-Carlo Tree Search (MCTS) algorithms for the game of Go. The primary thesis posits that incorporating static move evaluation—derived from the Bradley-Terry model—into both the simulation policy and the tree search process significantly enhances the performance of Go engines. By utilizing this model to inform progressive widening and to provide a bias within the Upper Confidence Bound (UCB) formula, programs can achieve competitive strength against established open-source engines.

The research focuses on the 13x13 and 19x19 board sizes, utilizing the Go program Nomitan to conduct extensive testing against Fuego and Pachi. The methodology involved over 31,200 games in the 13x13 setting, with a 95% confidence interval of ±5% on winning rates. The study demonstrates that progressive widening, which restricts the search to a subset of promising moves, is highly effective when tuned with a specific parameter, μ. Furthermore, the introduction of a Bradley-Terry-based bonus term into the UCB formula allows for a more nuanced selection of moves, balancing static expert knowledge with dynamic search results.

Key findings indicate that the optimal implementation requires a delicate balance between the static bias and the exploration-exploitation terms of the UCB formula. Excessive bias can lead to local reading errors, while insufficient bias fails to leverage learned patterns effectively. The research concludes that combining progressive widening with a decreasing static bias provides the most robust performance. These findings suggest that leveraging richer, more complex features within the Bradley-Terry model is a viable pathway for further improving the competitive capabilities of MCTS-based game engines.