Game-playing agents for abstract board games almost universally employ state-space search for thinking ahead. Ideally, when new search enhancements are introduced, their effectiveness is investigated in different game-playing domains to better highlight their relative strengths and weaknesses. We present a highly configurable open-source framework for generating synthetic state-spaces for combinatorial games to better facilitate an in-depth exploration of new search enhancements.

A general game player is a system that can play previously unknown games just by being given their rules. For this purpose, the Game Description Language (GDL) has been developed as a high-level knowledge representation formalism to communicate game rules to players. In this paper, we address a fundamental limitation of state-of-the-art methods and systems for General Game Playing, namely, their being confined to deterministic games with complete information about the game state. We develop a simple yet expressive extension of standard GDL that allows for formalising the rules of arbitrary finite, n-player games with randomness and incomplete state knowledge. In the second part of the paper, we address the intricate reasoning challenge for general game-playing systems that comes with the new description language. We develop a full embedding of extended GDL into the Situation Calculus augmented by Scherl and Levesque's knowledge fluent. We formally prove that this provides a sound and complete reasoning method for players' knowledge about game states as well as about the knowledge of the other players.

The variety of open-source game description language (GDL) reasoners available to newcomers to general game playing (GGP) lowers the technical barrier of entering the field. This variety, however, also makes it more complicated to decide on a fitting reasoner for a given GGP project, considering the project's objectives, ambitions, and technical constraints. This paper gives an overview of available GDL reasoners, discusses their main pros and cons, and, most importantly, quantifies their relative reasoning performance on a number of games (in terms of nodes searched per second), showing two orders of magnitude difference in some cases. We similarly quantify the performance difference between game playing systems specifically designed for playing a single game on the one hand, and GGP systems on the other hand, witnessing up to several orders of magnitude difference.

Recently the general Game Description Language (GDL) has been extended so as to cover arbitrary games with incomplete/imperfect information. Learning — without human intervention — to play such games poses a reasoning challenge for general game-playing systems that is much more intricate than in case of complete information games. Action formalisms like the Situation Calculus have been developed for precisely this purpose. In this paper we present a full embedding of the Game Description Language into the Situation Calculus (with Scherl and Levesque's knowledge fluent). We formally prove that this provides a sound and complete reasoning method for players' knowledge about game states as well as about the knowledge of the other players.

We develop a method for detecting symmetries in arbitrary games and exploiting these symmetries when using tree search to play the game. Games in the General Game Playing domain are given as a set of logic based rules defining legal moves, their effects and goals of the players. The presented method transforms the rules of a game into a vertex-labeled graph such that automorphisms of the graph correspond with symmetries of the game. The algorithm detects many kinds of symmetries that often occur in games, e.g., rotation and reflection symmetries of boards, interchangeable objects, and symmetric roles. A transposition table is used to efficiently exploit the symmetries in many games.