[This topic has already been assigned to a student.]

Description

Computer Game Playing has been a testbed since the early days of AI. During the last decades, much progress was achieved, where perhaps two of the most outstanding successes were IBM's Deep Blue beating Kasparov in 1997 and Checkers being solved by Jonathan Schaeffer's group in 2007. However, these game playing systems are of limited value for at least two reasons. For one, they are special-purpose programs that are only able to play the one particular game which they were created for. For another, such specialized systems usually contain a great deal of domain knowledge (e.g. in the form of heuristics), meaning that a large fraction of the game analysis is already done beforehand by human experts and designers.

The idea behind General Game Playing, for which there is an annual competition since 2005, is to develop game playing systems that are able to play all different kinds of games, even ones that are currently unknown to the system. At runtime, before the actual game starts, a General Game Player is provided with a declarative description of the game rules in form of a set of formulas. The system is then given a certain amount of time in which it can analyze the structure of the game, and is then supposed to play a match of that game without any human intervention; any heuristics, evaluation function, state representation etc. has therefore to be designed in a domain-independent fashion. The design of such a player involves many different areas of AI such as rational decision making in games, learning, and knowledge representation and reasoning.

The goal of this thesis is to implement and evaluate a General Game Playing system using standard AI techniques and methods such as those presented in the AI lecture. The resulting system, which may be based upon online available reference players, should at least be able to learn an evaluation function during the analysis phase (e.g. using Decision Trees, Neural Nets etc.) and apply it using an intelligent search strategy in the actual game. Based on the available literature, a more sophisticated technique is to be included later on. In the evalutation phase, different variants of the player are then to be compared with each other as well as a baseline player (e.g. which does nothing but search) in a selection of available games.

Requirements

• lecture "Introduction to Artificial Intelligence"
• lecture "Introduction to Knowledge Representation" (recommended)
• skills in Prolog programming (recommended)

Links

• http://games.stanford.edu/
• http://www.general-game-playing.de/

Literature

• [1] M. Genesereth, N. Love, B. Pell: General Game Playing: Overview of the AAAI Competition, AI Magazine 26(2), 62-72, 2005. [PDF]
• [2] S. Schiffel, M. Thielscher: Fluxplayer: A Successful General Game Player, Proc. of AAAI 2007. [PDF]
• [3] J. Clune: Heuristic Evaluation Functions for General Game Playing, Prof. of AAAI 2007. [PDF]
• [4] H. Finnson, Y. Björnsson: Simulation-based Approach to General Game Playing, Proc. of AAAI 2008. [PDF]

Contact

Jens Claßen