Fast Optimization of the Pattern Shapes in Board Games with Simulated Annealing

摘要

Monte-Carlo Tree Search is a popular method to implement computer programs for board games, and its performance can be significantly improved by including static knowledge about the game, for example in the formof patterns learned from game records. Finding the right pattern shapes is still an open problem, and we propose in this paper an evolutionary-like method to optimize the pattern shapes. We avoid direct optimization through the heavy Monte-Carlo framework by using instead the performance of a machine-learning algorithm as an early indicator of the quality of the pattern shapes. We have implemented this general method on the specific case of the game of Othello. The final pattern shapes obtained after optimization would be hard to find manually, and they greatly improve the strength of our Othello program.