Grammatical inference for the construction of opening books

摘要

It is known that Monte-Carlo Tree Search (MCTS) is usually weak in the very early stages of game development. To improve the performance of MCTS we have analyzed a grammatical inference problem. The research led us to devise an efficient algorithm, that for given small finite sets of a game's winning and losing positions, inductively synthesizes a regular expression for predicting similar positions to the ones in the winning part. On that foundation we have built an opening book and showed-in the conducted experiments on the Toads-and-Frogs game-that it helped to increase the playing strength significantly.