Generation and Evaluation of Exploration Terms for Monte Carlo Tree Search

Abstract

Monte Carlo Tree Search (MCTS) has shown good results for many difficult problems. We propose to automatically generate mathematical expressions that are used as exploration terms for MCTS algorithms, and we evaluate the resulting expressions in the game of Go. We use a systematic generation of small exploration terms. This is in contrast to our initial conference paper, which used Monte Carlo Search to generate exploration terms for Sequential Halving Using Scores (SHUSS). In this journal paper, we extend the work to automatically design three exploration terms: the exploration term near the leaves of Prior Upper Confidence for Trees (PUCT), the exploration term at the root of PUCT and the SHUSS exploration term. All three resulting exploration terms improve upon standard PUCT in the game of Go.