Combining Tree Search With Value Prediction Models Capable of Estimating Their Uncertainty

The aim of this paper is twofold. Firstly, we propose a method that combines tree search – specifically, Monte Carlo Tree Search – with value prediction models conditionally based on the model's uncertainty in a given state. If, during the search, this uncertainty is within the allowed margin, the current path is terminated, thereby saving simulation budget. This method, overlooked in literature, results in a non-uniform frequency of model usage, in contrast to typical methods applied to game-playing agents, which we summarize in the paper. Secondly, we investigate the effects of using models with various frequencies and prediction accuracies. Rich empirical results demonstrate the impact of 110 combinations of these parameters across various search budget scenarios. Generally, weaker players, for example, those performing fewer search iterations per move, benefit more from a broad selection of prediction models. For stronger baseline MCTS players, the model should only be used when its predictions achieve an accuracy greater than 0.9, especially when the objective is to develop an agent with high efficacy. Practical applicability of the proposed approach has been demonstrated in additional experiments involving chess and Othello, employing different approaches to prediction models. In both of them, it outperformed the baseline approaches.