Meta Monte-Carlo Tree Search for Automatic Opening Book Generation
Guillaume M. J. -B. Chaslot, Jean‐Baptiste Hoock, Julien Pérez, Arpad Rimmel, Olivier Teytaud, Mark H. M. Winands · 2009
Modern game playing programs use opening books in order to perform better. Generating opening books automatically in combination with an αβ program has been well studied. A challenge is to generate automatically an opening book for the new Monte-Carlo Tree Search (MCTS) algorithms. In this article, we tackle this issue by combining two level of MCTS. The resulting algorithm is called Meta-MCTS. Instead of applying a simulation strategy, it uses an MCTS program to play a simulated game. We describe two Meta-MCTS algorithms: the first one, Quasi Best-First, favors exploitation. The second one, Beta Distribution Sampling, favors exploration. Our approach is generic and can be used for general game playing. Itwill be particularly usefulwhen there is off-line time avail- able. In order to evaluate the performances of these algorithms, we generated and tested 99 Go opening books.