Specialization of a UCT-Based General Game Playing Program to Single-Player Games

摘要

General game playing (GGP) aims at designing autonomous agents capable of playing any game within a certain genre, without human intervention. GGP agents accept the rules, which are written in the logic-based game definition language (GDL) and unknown to them beforehand, at runtime. The state-of-the-art players use Monte Carlo tree search (MCTS) together with the upper confidence bounds applied to trees (UCT) method. In this paper, we discuss several enhancements to GGP players geared towards more effective playing of single-player games within the MCTS/UCT framework. The main proposed improvements include introduction of a collection of lightweight policies which can be used for guiding the MCTS and a GGP-friendly way of using transposition tables. We have tested our base player and a specialized version of it for single-player games in a series of experiments using ten single-player games of various complexity. It is clear from the results that the optimized version of the player achieves significantly better performance. Furthermore, in the same set of tests against publicly available version of CadiaPlayer, one of the strongest GGP agents, the results are also favorable to the enhanced version of our player.