Automatic Feature Construction for General Game Playing
Guillaume Martin · 2008
The goal of General Game Playing is to construct an autonomous agent that can effectively play games it has never encountered before. The agent is only provided with the game rules, without any information about how to win the game. Since no human intervention is allowed, the agent needs to deduce important concepts automatically from the game rules. A central challenge is the automatic construction of an evaluation function that can estimate the winning chances for any position encountered during game-tree search. An evaluation function is a weighted combination of features : numerical functions that identify important aspects of a position. This thesis presents a method to generate a set of features for General Game Playing, based on previous work on knowledge-based feature generation. Moreover, a method is developed that quickly selects features for inclusion in the evaluation function. The feature construction method is combined with TD(λ) reinforcement learning to produce a complete evaluation function. It is shown that the method could successfully generate an evaluation function for many general games, and an empirical evaluation of its quality is presented.