Research

FluxPlayer

FLUXPLAYER is a system for General Game Playing (GGP). GGP is the art of designing programs that are capable of playing previously unknown games of a wide variety by being told nothing but the rules of the game. This is in contrast to traditional computer game players like Deep Blue, which are designed for a particular game and can't adapt automatically to modifications of the rules, let alone play completely different games. General Game Playing is intended to foster the development of integrated cognitive information processing technology.

FLUXPLAYER is based on FLUX, a high-level programming system for cognitive agents.

award ceremony
FLUXPLAYER has won the 2nd International General Game Playing Competition at AAAI-06 in Boston.

Media Coverage

Publications

Günther, M., Schiffel, S. & Thielscher, M. "Factoring General Games".
In Proceedings of the IJCAI-09 Workshop on General Game Playing (GIGA'09). Pasadena, California, USA. July 2009., pp. 27-34.
Abstract: The goal of General Game Playing is to construct an autonomous agent that can play games it has never encountered before. Only the game rules are given explicitly; interesting and useful properties of a game are implicit and need to be deduced. One particular such property is decomposability into separate subgames that have little interaction with each other. We present a method to decompose a given game into its subgames by analyzing the preconditions and effects of actions. Moreover, a search algorithm that exploits this information in single-player games is proposed.
[URL]
Haufe, S., Michulke, D., Schiffel, S. & Thielscher, M. "Knowledge-Based General Game Playing".
KI. Vol. 25(1), pp. 25-33.
Abstract: Although we humans cannot compete with computers at simple brute-force search, this is often more than compensated for by our ability to discover structures in new games and to quickly learn how to perform highly selective, informed search. To attain the same level of intelligence, general game playing systems must be able to figure out, without human assistance, what a new game is really about. This makes General Game Playing in ideal testbed for human-level AI, because ultimate success can only be achieved if computers match our ability to master new games by acquiring and exploiting new knowledge.
This article introduces five knowledge-based methods for General Game Playing. Each of these techniques contributes to the ongoing success of our FLUXPLAYER, which was among the top four players at each of the past AAAI competitions and in particular was crowned World Champion in 2006.
[URL]
Haufe, S., Schiffel, S. & Thielscher, M. "Automated Verification of State Sequence Invariants in General Game Playing".
Artificial Intelligence.
Abstract: A general game player is a system that can play previously unknown games given nothing but their rules. Many of the existing successful approaches to general game playing require to generate some form of game-specific knowledge, but when current systems establish knowledge they rely on the approximate method of playing random sample matches rather than formally proving knowledge. In this paper, we present a theoretically founded and practically viable method for automatically verifying properties of games whose rules are given in the general Game Description Language (GDL). We introduce a simple formal language to describe game-specific knowledge as state sequence invariants, and we provide a proof theory for verifying these invariants with the help of Answer Set Programming. We prove the correctness of this method against the formal semantics for GDL, and we report on extensive experiments with a practical implementation of this proof system, which show that our method of formally proving knowledge is viable for the practice of general game playing.
[DOI] [URL]
Haufe, S. & Thielscher, M. "Pushing the Envelope: General Game Players Prove Theorems".
In Proceedings of the Australasian Joint Conference on Artificial Intelligence. Adelaide. December 2010. Volume 6464, pp. 1-10. Springer.
Abstract: A general game player is a system that can play previously unknown games given nothing but their rules. A key to success in this endeavour is the ability to automatically gain knowledge about new games that follows from the rules without being explicitly given. In this paper, we show how a recently developed, theoretical method for
automated theorem proving in general game playing can be put into practice. To this end, we extend the method so as to allow a general game player to systematically search and verify multiple temporal game properties at once. We formally prove this extension to be correct, and we report on extensive experiments that show how this improvement helps to significantly enhance the ability of a successful general game player to infer new properties about a previously unknown game.
[URL]
Michulke, D. "Neural Networks for High-Resolution State Evaluation in General Game Playing".
In Proceedings of the IJCAI-11 Workshop on General Game Playing (GIGA'11).
Abstract: C-IL²P is an algorithm that transforms a propositional domain theory to a neural network that correctly represents the domain theory and is ready-to-use without prior training. Its original intention was to transform explicit symbolic knowledge into a neural network to allow for learning.

The game playing agent system presented in "Neural Networks for State Evaluation in General Game Playing" (Michulke, 2009) uses the algorithm differently: By transforming the symbolic description of the goal of a game to a neural network it obtains an evaluation function for states of that game. Much like fuzzy logic, the network can be used for graded inference while retaining correctness. But in contrast to fuzzy logic, the network is able to learn and may consequently improve with experience, which is unique among competing agents and arguably an important advantage in a game playing setting. However, since not intended for this use, the transformation algorithm produces networks that cannot correctly represent complex domain theories without losing their ability to distinguish some input vectors that ought to have a different evaluation.

In this paper we introduce a generalization of C-IL²P that addresses the above issue. It structures the formerly monolithic approach of logic-to-network transformation to allow for lower weights in the network. This increases the output resolution by several orders of magnitude, as experiments demonstrate, while maintaining correctness.

[URL]
Michulke, D. "Heuristic Interpretation of Predicate Logic Expressions in General Game Playing".
In Proceedings of the IJCAI-11 Workshop on General Game Playing (GIGA'11).
Abstract: Unlike traditional game playing, General Game Playing (GGP) is concerned with agents capable of playing classes of games. Given the rules of an unknown game, the agent is supposed to play well without human intervention. For this purpose, agent systems using game tree search need to automatically construct a state value function to guide search.

This state value function is often either probabilistic as in Monte-Carlo Systems and thus most likely unable to compete with deterministic functions in games like chess; or it is expensive in construction due to feature generation and learning-based selection and weighting mechanisms.

In this work we present an alternative method that derives features from the goal conditions stated in the game rules, avoiding thereby the disadvantages of other approaches. The paper structures and generalizes some known approaches, shows new ways of deriving features and demonstrates how to use these features as part of an evaluation function. Experiments demonstrate both a high effectiveness and generality.

[URL]
Michulke, D. & Schiffel, S. "Distance Features for General Game Playing".
In Proceedings of the IJCAI-11 Workshop on General Game Playing (GIGA'11). Barcelona, Spain. July 2011.
Abstract: General Game Playing (GGP) is concerned with the development of programs that are able to play previously unknown games well. The main problem such a player is faced with is to come up with a good heuristic evaluation function automatically. Part of these heuristics are distance measures used to estimate, e.g., the distance of a pawn towards the promotion rank. However, current distance heuristics in GGP are based on too specific detection patterns as well as expensive internal simulations, they are limited to the scope of totally ordered domains and/or they apply a uniform Manhattan distance heuristics regardless of the move pattern of the object involved.In this paper we describe a method to automatically construct distance measures by analyzing the game rules. The presented method is an improvement to all previously presented distance estimation methods, because it is not limited to specific structures, such as, game boards. Furthermore, the constructed distance measures are admissible.
We demonstrate how to use the distance measures in an evaluation function of a general game player and show the effectiveness of our approach by comparing with a state-of-the-art player.
[URL]
Michulke, D. & Schiffel, S. "Distance Features for General Game Playing".
In Proceedings of the 4th International Conference on Agents and Artificial Intelligence (ICAART). Vilamoura, Portugal. February 2012.
Abstract: General Game Playing (GGP) is concerned with the development of programs that are able to play previously unknown games well. The main problem such a player is faced with is to come up with a good heuristic evaluation function automatically. Part of these heuristics are distance measures used to estimate, e.g., the distance of a pawn towards the promotion rank. However, current distance heuristics in GGP are based on too specific detection patterns as well as expensive internal simulations, they are limited to the scope of totally ordered domains and/or they apply a uniform Manhattan distance heuristics regardless of the move pattern of the object involved.
In this paper we describe a method to automatically construct distance measures by analyzing the game rules. The presented method is an improvement to all previously presented distance estimation methods, because it is not limited to specific structures, such as, Cartesian game boards. Furthermore, the constructed distance measures are admissible.
We demonstrate how to use the distance measures in an evaluation function of a general game player and show the effectiveness of our approach by comparing with a state-of-the-art player.
[URL]
Michulke, D. & Schiffel, S. "Matt bei "Vier gewinnt"".
c't., January, 2009. Vol. 1, pp. 174-181.
Abstract: Deep Fritz besiegt menschliche Schachweltmeister, ist aber nicht in der Lage, eine simple Partie Tic Tac Toe zu spielen – geschweige denn, sie zu gewinnen. Doch Forscher arbeiten an sogenannten General Game Playern, die sich in jedem erdenklichen Spiel wacker schlagen sollen.
[URL]
Michulke, D. & Thielscher, M. "Neural Networks for State Evaluation in General Game Playing".
In Proceedings of the European Conference on Machine Learning (EMCL). Bled, Slovenia. September 2009., pp. 95-110.
Abstract: Unlike traditional game playing, General Game Playing is concerned with agents capable of playing classes of games. Given the rules of an unknown game, the agent is supposed to play well without human intervention. For this purpose, agent systems that use deterministic game tree search need to automatically construct a state value function to guide search. Successful systems of this type use evaluation functions derived solely from the game rules, thus neglecting further improvements by experience. In addition, these functions are fixed in their form and do not necessarily capture the game's real state value function. In this work we present an approach for obtaining evaluation functions on the basis of neural networks that overcomes the aforementioned problems. A network initialization extracted from the game rules ensures reasonable behavior without the need for prior training. Later training, however, can lead to significant improvements in evaluation quality, as our results indicate.
[URL]
Schiffel, S. "Symmetry Detection in General Game Playing".
In Proceedings of the AAAI Conference on Artificial Intelligence. Atlanta. July 2010., pp. 980-985. AAAI Press.
Abstract: 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.
[URL]
Schiffel, S. & Thielscher, M. "A Multiagent Semantics for the Game Description Language".
In Agents and Artificial Intelligence. Porto. Springer.
Abstract: The Game Description Language (GDL) has been developed for the purpose of formalizing game rules. It serves as the input language for general game players, which are systems that learn to play previously unknown games without human intervention. In this paper, we show how GDL descriptions can be intepreted as multiagent domains and, conversely, how a large class of multiagent environments can be specified in GDL. The resulting specifications are declarative, compact, and easy to understand and maintain. At the same time they can be fully automatically understood and used by autonomous agents who intend to participate in these environments. Our main result is a formal characterization of the class of multiagent domains that serve as formal semantics for—and can be described in—the Game Description Language.
[URL]
Schiffel, S. & Thielscher, M. "Reasoning About General Games Described in GDL-II".
In Proceedings of the AAAI Conference on Artificial Intelligence. San Francisco. August 2011., pp. 846-851. AAAI Press.
Abstract: 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.
[URL]
Schiffel, S. & Thielscher, M. "Automated Theorem Proving for General Game Playing".
In Proceedings of IJCAI'09., pp. 911-916.
Abstract: A general game player is a system that understands the rules of an unknown game and learns to play this game well without human intervention. To succeed in this endeavor, systems need to be able to extract and prove game-specific knowledge from the mere game rules. We present a practical approach to this challenge with the help of Answer Set Programming. The key idea is to reduce the automated theorem proving task to a simple proof of an induction step and its base case. We prove correctness of this method and report on experiments with an off-the-shelf Answer Set Programming system in combination with a successful general game player.
[URL]
Schiffel, S. & Thielscher, M. "Fluxplayer: A Successful General Game Player".
In Proceedings of the 22nd AAAI Conference on Artificial Intelligence (AAAI-07). Vancouver., pp. 1191-1196. AAAI Press.
Abstract: General Game Playing (GGP) is the art of designing programs that are capable of playing previously unknown games of a wide variety by being told nothing but the rules of the game. This is in contrast to traditional computer game players like Deep Blue, which are designed for a particular game and can't adapt automatically to modifications of the rules, let alone play completely different games. General Game Playing is intended to foster the development of integrated cognitive information processing technology. In this article we present an approach to General Game Playing using a novel way of automatically constructing a position evaluation function from a formal game description. Our system is being tested with a wide range of different games. Most notably, it is the winner of the AAAI GGP Competition 2006.
[URL]
Thielscher, M. "General Game Playing in AI Research and Education".
In Proceedings of the German Annual Conference on Artificial Intelligence (KI). Berlin, Germany. October 2011. Volume 7006, pp. 26-37. Springer.
Abstract: Introduced in 2005 as a new AI Challenge and Competition, general game playing has quickly evolved into an established research area. More recently it is also gaining popularity as a useful addition to AI curricula at universities around the world. The first part of this paper will survey the research landscape of general game playing, which covers a broad range of classic AI topics, including knowledge representation, search, planning and learning. The second part will argue that general game playing provides a unique approach to teaching a number of different topics such as problem solving by search, logic, logic programming and planning. The inherent competitive aspect also can be used as a great motivator for students to design and implement their own AI systems.
[URL]
Thielscher, M. "Translating General Game Descriptions into an Action Language".
In Logic Programming, Knowledge Representation, and Nonmonotonic Reasoning: Essays in Honor of Michael Gelfond. Volume 6565, pp. 300-314. Springer.
[URL]
Thielscher, M. "Answer Set Programming for Single-Player Games in General Game Playing".
In Proceedings of the International Conference on Logic Programming (ICLP). Pasadena. July 2009. Springer.
Abstract: As a novel, grand AI challenges, General Game Playing is concerned with the development of systems that understand the rules of unknown games and play these games well without human intervention. In this paper, we show how Answer Set Programming can assist a general game player with the special class of single-player games. To this end, we present a translation from the general Game Description Language (GDL) into answer set programs (ASP). Correctness of this mapping is established by proving that the stable models of the resulting ASP coincide with the possible developments of the original GDL game. We report on experiments with single-player games from past AAAI General Game Playing Competitions which substantiate the claim that Answer Set Programming can provide valuable support to general game playing systems for this type of games.
[URL]
Thielscher, M. "GDL-II".
Künstliche Intelligenz. Vol. 25, pp. 63-66. Springer.
Abstract: Abstract The Game Description Language (GDL) used in the past AAAI competitions allows to tell a system the rules of arbitrary finite games that are characterised by perfect information, but does not extend to games in which players have asymmetric information, e.g. about their own hand of cards, or which involve elements of chance like the roll of dice. Accordingly, contemporary general game-playing systems are not designed to play games such as Backgammon, Poker or Diplomacy. GDL-II (for: GDL with Incomplete/Imperfect Information) is a recent extension of the original description language that makes general game playing truly general, because it allows to describe just any finite game with arbitrary forms of randomness as well as imperfect/incomplete information. This brings along the challenge to build the next generation of truly general game-playing systems that are able to understand any game description given in GDL-II and to learn to master these types of games, too.
[DOI] [URL]
Thielscher, M. "The General Game Playing Description Language is Universal".
In Proceedings of the International Joint Conference on Artificial Intelligence. Barcelona. July 2011., pp. 1107-1112. AAAI Press.
Abstract: The Game Description Language is a high-level, rule-based formalisms for communicating the rules of arbitrary games to general game-playing systems, whose challenging task is to learn to play previously unknown games without human intervention. Originally designed for deterministic games with complete information about the game state, the language was recently extended to include randomness and imperfect information. However, determining the extent to which this enhancement allows to describe truly arbitrary games was left as an open problem. We provide a positive answer to this question by relating the extended Game Description Language to the universal, mathematical concept of extensive-form games, proving that indeed just any such game can be described faithfully.
[URL]
Thielscher, M. "A General Game Description Language for Incomplete Information Games".
In Proceedings of the AAAI Conference on Artificial Intelligence. Atlanta. July 2010., pp. 994-999. AAAI Press.
Abstract: A General Game Player is a system that can play previously unknown games given nothing but their rules. The Game Description Language (GDL) has been developed as a high-level knowledge representation formalism for axiomatising the rules of any game, and a basic requirement of a General Game Player is the ability to reason logically about a given game description. In this paper, we address the fundamental limitation of existing GDL to be confined to deterministic games with complete information about the game state. To this end, we develop an extension of GDL that is both simple and elegant yet expressive enough to allow to formalise the rules of arbitrary (discrete and finite) n-player games with randomness and incomplete state knowledge. We also show that this extension suffices to provide players with all infor
mation they need to reason about their own knowledge as well as that of the other players up front and during game play.
[URL]
Thielscher, M. & Voigt, S. "A Temporal Proof System for General Game Playing".
In Proceedings of the AAAI Conference on Artificial Intelligence. Atlanta. July 2010., pp. 1000-1005. AAAI Press.
Abstract: A general game player is a system that understands the rules of unknown games and learns to play these games well without human intervention. A major challenge for research in General Game Playing is to endow a player with the ability to extract and prove game-specific knowledge from the mere game rules. We define a formal language to express temporally extended—yet local—properties of games. We also develop a provably correct proof theory for this language using the paradigm of Answer Set Programming, and we report on experiments with a practical implementation of this proof system in combination with a successful general game player.
[URL]
Thielscher, M. & Zhang, D. "From General Game Descriptions to a Market Specification Language for General Trading Agents".
In Agent-Mediated Electronic Commerce: Designing Trading Strategies and Mechanisms for Electronic Markets. Volume 59, pp. 259-274. Springer.
Abstract: The idea behind General Game Playing is to build systems that, instead of being programmed for one specific task, are intelligent and flexible enough to negotiate an unknown environment solely on the basis of the rules which govern it. In this paper, we argue that this principle has the great potential to bring to a new level artificially intelligent systems in other application areas as well. Our specific interest lies in General Trading Agents, which are able to understand the rules of unknown markets and then to actively participate in them without human intervention. To this end, we extend the general Game Description Language into a language that allows to formally describe arbitrary markets in such a way that these specifications can be automatically processed by a computer. We present both syntax and a transition-based semantics for this Market Specification Language and illustrate its expressive power by presenting axiomatizations of several well-known auction types.
[URL]
Zhao, D., Schiffel, S. & Thielscher, M. "Decomposition of Multi-Player Games".
In Proceedings of the Australasian Joint Conference onArtificial Intelligence. Melbourne. December 2009. Volume 5866, pp. 475-484. Springer.
Abstract: Research in General Game Playing aims at building systems that learn to play unknown games without human intervention. We contribute to this endeavour by generalising the established technique of decomposition from AI Planning to multi-player games. To this end, we present a method for the automatic decomposition of previously unknown games into independent subgames, and we show how a general game player can exploit a successful decomposition for game tree search.
[URL]