Progressive strategies for Monte-Carlo Tree Search
Abstract
Monte-Carlo Tree Search (MCTS) is a new best-¯rst search guided by the results of Monte-Carlo simulations. In this article we introduce two progressive strategies for MCTS, called progressive bias and progressive unpruning. They enable the use of rel- atively time-expensive heuristic knowledge without speed reduction. Progressive bias directs the search according to heuristic knowledge. Progressive unpruning ¯rst reduces the branching factor, and then increases it gradually again. Experiments assess that the two progressive strategies signi¯cantly improve the level of our Go program Mango. Moreover, we see that the combination of both strategies perform even better on larger board sizes.