Literature - General Game Playing

Literature

I need your help to keep this list up to date. If you find or publish a paper related to general game playing please drop me a line.

Author	Title	Year	Journal/Proceedings	Reftype	DOI/URL
Aldinger, J.	Lösen allgemeiner Spiele durch heuristische Suche [Abstract] [BibTeX]	2009		misc	URL
Abstract: A General Game Playing System is a system that can accept a formal definition of a game and play the game effectively without human intervention. Unlike specialized game players, general game players do not rely on algorithms designed in advance for specific games, and they are able to play different kinds of games. In this work, a player based on the General Game Playing System Jocular was developed that uses an automatically generated evaluation function derived from the FF heuristic known from research in action planning. The evaluation function generalizes the FF heuristic in that it is designed for two-player games with numeric preferences over terminal states.
BibTeX: @misc{Aldinger2009, author = {Johannes Aldinger}, title = {Lösen allgemeiner Spiele durch heuristische Suche}, year = {2009}, url = {http://www.informatik.uni-freiburg.de/~ki/papers/bachelorarbeiten/aldinger-bachelorarbeit-09.pdf} }
Asgharbeygi, N., Stracuzzi, D. & Langley, P.	Relational Temporal Difference Learning [Abstract] [BibTeX]	2006	International Conference on Machine Learning	inproceedings	URL
Abstract: We introduce relational temporal difference learning as an effective approach to solving multi-agent Markov decision problems with large state spaces. Our algorithm uses temporal difference reinforcement to learn a distributed value function represented over a conceptual hierarchy of relational predicates. We present experiments using two domains from the General Game Playing repository, in which we observe that our system achieves higher learning rates than non-relational methods. We also discuss related work and directions for future research.
BibTeX: @inproceedings{Asgharbeygi2006, author = {Nima Asgharbeygi and David Stracuzzi and Pat Langley}, title = {Relational Temporal Difference Learning}, booktitle = {International Conference on Machine Learning}, year = {2006}, url = {http://www.stanford.edu/~nimaa/papers/rtd-icml06.pdf} }
Banerjee, B., Kuhlmann, G. & Stone, P.	Value Function Transfer for General Game Playing [Abstract] [BibTeX]	2006	ICML workshop on Structural Knowledge Transfer for Machine Learning	inproceedings	URL
Abstract: We present value function transfer techniques for General Game Playing (GGP) by Reinforcement Learning. We focus on 2 player, alternate-move, complete information board games and use the GGP simulator and framework. Our approach is two-pronged: first we extract knowledge about crucial regions in the value-function space of any game in the genre. Then for each target game, we generate a smaller version of this game and extract symmetry information from the board setup. The combined knowledge of value function and symmetry allows us to achieve significant transfer via Reinforcement Learning, to larger board games using only a limited size of state-space by virtue of exploiting symmetry.
BibTeX: @inproceedings{Banerjee2006, author = {Bikramjit Banerjee and Gregory Kuhlmann and Peter Stone}, title = {Value Function Transfer for General Game Playing}, booktitle = {ICML workshop on Structural Knowledge Transfer for Machine Learning}, year = {2006}, url = {http://www.cs.utexas.edu/~pstone/Papers/bib2html-links/ICML06-bikram.pdf} }
Banerjee, B. & Stone, P.	General Game Learning using Knowledge Transfer [Abstract] [BibTeX]	2007	The 20th International Joint Conference on Artificial Intelligence, pp. 672-677	inproceedings	URL
Abstract: We present a reinforcement learning game player that can interact with a General Game Playing system and transfer knowledge learned in one game to expedite learning in many other games. We use the technique of value-function transfer where general features are extracted from the state space of a previous game and matched with the completely different state space of a new game. To capture the underlying similarity of vastly disparate state spaces arising from different games, we use a game-tree lookahead structure for features. We show that such feature-based value function transfer learns superior policies faster than a reinforcement learning agent that does not use knowledge transfer. Furthermore, knowledge transfer using lookahead features can capture opponent-specific value-functions, i.e. can exploit an opponent's weaknesses to learn faster than a reinforcement learner that uses lookahead with minimax (pessimistic) search against the same opponent.
BibTeX: @inproceedings{Banerjee2007, author = {Bikramjit Banerjee and Peter Stone}, title = {General Game Learning using Knowledge Transfer}, booktitle = {The 20th International Joint Conference on Artificial Intelligence}, year = {2007}, pages = {672-677}, url = {http://www.cs.utexas.edu/~pstone/Papers/bib2html-links/IJCAI07-bikram.pdf} }
Björnsson, Y. & Schiffel, S.	Comparison of GDL Reasoners [Abstract] [BibTeX]	2013	Proceedings of the IJCAI-13 Workshop on General Game Playing (GIGA'13), pp. 55-62	inproceedings	URL
Abstract: The variety of open-source GDL reasoners available to newcomers to General Game Playing (GGP) lowers the technical barrier of entering the ﬁeld. This variety, however, also makes it more complicated to decide on a ﬁtting 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 quantiﬁes their relative reasoning performance on a number of games (in terms of nodes searched per second), showing an order of magnitude difference in some cases. We similarly quantify the performance difference between gameplaying systems speciﬁcally designed for playing a single game on the one hand and general gameplaying systems on the other, witnessing up to several orders of magnitude difference.
BibTeX: @inproceedings{Bjornsson2013, author = {Yngvi Björnsson and Stephan Schiffel}, title = {Comparison of GDL Reasoners}, booktitle = {Proceedings of the IJCAI-13 Workshop on General Game Playing (GIGA'13)}, year = {2013}, pages = {55-62}, url = {http://giga13.ru.is/GIGA-13-Proceedings.pdf} }
Björnsson, Y.	Learning Rules of Simplified Boardgames by Observing [Abstract] [BibTeX]	2012	Frontiers in Artificial Intelligence and Applications, Volume 242: ECAI 2012	incollection	URL
Abstract: General Game Playing (GGP) agents learn strategies to skillfully play a wide variety of games when given only the rules of the game. The rules are provided in a language called Game Description Language (GDL) and specify the initial game setup, what constitutes legal moves and how they update the game state when played, how the game terminates, and what the outcome is. In here we extend this line of research further, that is, we assume that the game-playing agent must learn the rules of a game by observing others play instead of them being provided. Our focus here will mainly be on modeling piece movements with less attention placed on the remaining game-rule properties. We define a subset of games, we name simplified boardgames, that despite constituting only a small subset of games expressible in GDL nonetheless encapsulate a large variety of interesting piece movement patterns found in popular boardgames. We provide a well-defined formalism and a practicable algorithm for learning game rules of simplified boardgames. We empirically evaluate the learning algorithm on different boardgames and under different assumptions of availability of observations. Furthermore, we show that our formalism offers at least an order of magnitude speedup over state-of-the-art logic-based GDL reasoners for fitting boardgames. The method is thus directly relevant for GGP systems.
BibTeX: @incollection{Bjoernsson2012, author = {Yngvi Björnsson}, title = {Learning Rules of Simplified Boardgames by Observing}, booktitle = {Frontiers in Artificial Intelligence and Applications, Volume 242: ECAI 2012}, publisher = {IOS Press}, year = {2012}, url = {http://ebooks.iospress.nl/publication/6968} }
Brand, D.	General Game Playing with PROST [Abstract] [BibTeX]	2012	School: University of Freiburg	mastersthesis	URL
Abstract: This work gives the probabilistic planning system PROST the functionality to solve single player games in general game playing. Therefore, a communication with the game master, i.e., the server managing the game flow, must be established. Initially, the game master sends the rules to every player encoded in the game description language (GDL). As PROST was developed as a probablistic planning system, it supports only RDDL. For this reason, the rules must be converted from GDL to RDDL, which is the main focus of this work. The aim of this conversion is to create valid RDDL files which can be used with existing PROST-functionality. As PROST only supports a fragment of RDDL, it is necessary to also enhance the PROST planner in order to be able to make reasonable plans for single player games. Finally, the results of this work are analysed empirically and problems and limitations of PROST and RDDL are presented.
BibTeX: @mastersthesis{Brand2012, author = {Daniel Brand}, title = {General Game Playing with PROST}, school = {University of Freiburg}, year = {2012}, url = {http://www.informatik.uni-freiburg.de/~ki/papers/bachelorarbeiten/brand-bachelorarbeit-12.pdf} }
Cazenave, T., Saffidine, A., Schofield, M. & Thielscher, M.	Nested Monte Carlo Search for Two-player Games [BibTeX]	2016	Proceedings of the AAAI Conference on Artificial Intelligence	inproceedings	URL
BibTeX: @inproceedings{Cazenave2016, author = {Tristan Cazenave and Abdallah Saffidine and Michael Schofield and Michael Thielscher}, title = {Nested Monte Carlo Search for Two-player Games}, booktitle = {Proceedings of the AAAI Conference on Artificial Intelligence}, publisher = {AAAI Press}, year = {2016}, url = {https://www.aaai.org/ocs/index.php/AAAI/AAAI16/paper/view/12134/11652} }
Cerexhe, T., Rajaratnam, D., Saffidine, A. & Thielscher, M.	A Systematic Solution to the (De-)Composition Problem in General Game Playing [Abstract] [BibTeX]	2014	Proceedings of the European Conference on Artificial Intelligence (ECAI)	inproceedings	URL
Abstract: General game players can drastically reduce the cost of search if they are able to solve smaller subproblems individually and synthesise the resulting solutions. To provide a systematic solution to this (de-)composition problem, we start off with generalising the standard decomposition problem in planning by allowing the composition of individual solutions to be further constrained by domain-dependent requirements of the global planning problem. We solve this generalised problem based on a systematic analysis of composition operators for transition systems, and we demonstrate how this solution can be further generalised to general game playing.
BibTeX: @inproceedings{Cerexhe2014, author = {Timothy Cerexhe and David Rajaratnam and Abdallah Saffidine and Michael Thielscher}, title = {A Systematic Solution to the (De-)Composition Problem in General Game Playing}, booktitle = {Proceedings of the European Conference on Artificial Intelligence (ECAI)}, year = {2014}, url = {http://cse.unsw.edu.au/~mit/Papers/ECAI14.pdf} }
Cerexhe, T., Sabuncu, O. & Thielscher, M.	Evaluating Answer Set Clause Learning for General Game Playing [Abstract] [BibTeX]	2013	Proceedings of 12th International Conference on Logic Programming and Nonmonotonic Reasoning	inproceedings	URL
Abstract: In games with imperfect information, the ‘information set’ is a collection of all possible game histories that are consistent with, or explain, a player’s observations. Current game playing systems rely on these best guesses of the true, partially-observable game as the foundation of their decision making, yet finding these information sets is expensive. We apply reactive Answer Set Programming (ASP) to the problem of sampling information sets in the ﬁeld of General Game Playing. Furthermore, we use this domain as a test bed for evaluating the effectiveness of oClingo, a reactive answer set solver, in avoiding redundant search by keeping learnt clauses during incremental solving.
BibTeX: @inproceedings{Cerexhe2013, author = {Timothy Cerexhe and Orkunt Sabuncu and Michael Thielscher}, title = {Evaluating Answer Set Clause Learning for General Game Playing}, booktitle = {Proceedings of 12th International Conference on Logic Programming and Nonmonotonic Reasoning}, year = {2013}, url = {http://cgi.cse.unsw.edu.au/~mit/Papers/LPNMR13b.pdf} }
Chaslot, G., Hoock, J.-B., Perez, J., Rimmel, A., Teytaud, O. & Winands, M.	Meta Monte-Carlo Tree Search for Automatic Opening Book Generation [Abstract] [BibTeX]	2009	Proceedings of the IJCAI-09 Workshop on General Game Playing (GIGA'09), pp. 7-12	inproceedings	URL
Abstract: Modern game playing programs use opening books in order to perform better. Generating opening books automatically in combination with an $alpha program has been well studied. A challenge is to generate automatically an opening book for the newMonte-Carlo Tree Search (MCTS) algorithms. In this article, we tackle this issue by combining two level of MCTS. The resulting algorithm is called Meta-MCTS. Instead of applying a simulation strategy, it uses an MCTS program to play a simulated game. We describe two Meta-MCTS algorithms: the first one, Quasi Best-First, favors exploitation. The second one, Beta Distribution Sampling, favors exploration. Our approach is generic and can be used for general game playing. It will be particularly useful when there is off-line time available. In order to evaluate the performances of these algorithms, we generated and tested 9$9 Go opening books.
BibTeX: @inproceedings{Chaslot2009, author = {Guillaume Chaslot and Jean-Baptiste Hoock and Julien Perez and Arpad Rimmel and Olivier Teytaud and Mark Winands}, title = {Meta Monte-Carlo Tree Search for Automatic Opening Book Generation}, booktitle = {Proceedings of the IJCAI-09 Workshop on General Game Playing (GIGA'09)}, year = {2009}, pages = {7-12}, url = {https://dke.maastrichtuniversity.nl/m.winands/documents/ouvertures9x9.pdf} }
Clune, J.	Heuristic evaluation functions for general game playing [Abstract] [BibTeX]	2008	School: University of California, Los Angeles	phdthesis	URL
Abstract: A general game-playing program plays games that it has not previously encountered. A game manager program sends the game-playing programs a description of a game's rules and objectives in a game description language. The game-playing programs compete by sending messages over a network indicating their moves until the game is completed. The class of games covered is intentionally broad, including games of one or more players with alternating or simultaneous moves, with arbitrary numeric payoffs. This research explores the problem of constructing an effective general game- playing program, with an emphasis on techniques for automatically constructing effective heuristic evaluation functions from game descriptions. A technique based on abstract models of games is presented. The abstract model treats mobility, payoff and termination as the most salient elements of a game. Each of these aspects are quantified in terms of stable features. Evidence is presented that the technique produces heuristic evaluation functions that are both comprehensible and effective. Empirical work includes a series of general game-playing programs that placed first or second for the three consecutive years of the AAAI General Game-Playing Competition.
BibTeX: @phdthesis{Clune2008, author = {James Clune}, title = {Heuristic evaluation functions for general game playing}, school = {University of California, Los Angeles}, year = {2008}, url = {http://proquest.umi.com/pqdlink?did=1679290781&Fmt=7&clientId=79356&RQT=309&VName=PQD} }
Clune, J.	Heuristic Evaluation Functions for General Game Playing [Abstract] [BibTeX]	2007	AAAI, pp. 1134-1139	inproceedings	URL
Abstract: A general game playing program plays games that it has not previously encountered. A game manager program sends the game playing programs a description of a game's rules and objectives in a well-defined game description language. A central challenge in creating effective general game playing programs is that of constructing heuristic evaluation functions from game descriptions. This paper describes a method for constructing evaluation functions that represent exact values of simplified games. The simplified games are abstract models that incorporate the most essential aspects of the original game, namely payoff, control, and termination. Results of applying this method to a sampling of games suggest that heuristic evaluation functions based on our method are both comprehensible and effective.
BibTeX: @inproceedings{Clune2007, author = {James Clune}, title = {Heuristic Evaluation Functions for General Game Playing}, booktitle = {AAAI}, publisher = {AAAI Press}, year = {2007}, pages = {1134-1139}, url = {http://www.aaai.org/Papers/AAAI/2007/AAAI07-180.pdf} }
Cox, E., Schkufza, E., Madsen, R. & Genesereth, M.	Factoring General Games using Propositional Automata [Abstract] [BibTeX]	2009	Proceedings of the IJCAI-09 Workshop on General Game Playing (GIGA'09), pp. 13-20	inproceedings	URL
Abstract: In this paper we propose the design of a more robust General Game Player, able to successfully play the class of synchronous independent games using Propositional Automata, a framework for reasoning about discrete, dynamic, multiagent systems, developed by the Stanford Logic Group. We prove conditions under which a Propositional Automata represents multiple, synchronous independent subgames, and in doing so, prove when a Propositional Automata can be separated, or factored into multiple automata. A General Game Player able to recognize such independences can computationally save, by searching the smaller game trees represented by the independent factored automata for solutions. Additionally we explore the concept of independent substructures appearing within Propositional Automata given certain states, and prove conditions under which a Propositional Automata is contingently factorable into multiple Propositional Automata.
BibTeX: @inproceedings{Cox2009, author = {Evan Cox and Eric Schkufza and Ryan Madsen and Michael Genesereth}, title = {Factoring General Games using Propositional Automata}, booktitle = {Proceedings of the IJCAI-09 Workshop on General Game Playing (GIGA'09)}, year = {2009}, pages = {13-20}, url = {http://logic.stanford.edu/classes/cs227/2010/readings/factoring.pdf} }
Cropper, A., Evans, R. & Law, M.	Inductive general game playing [BibTeX]	2020	Machine Learning Vol. 109, pp. 1393-1434	article	URL
BibTeX: @article{Cropper2020, author = {Andrew Cropper and Richard Evans and Mark Law}, title = {Inductive general game playing}, journal = {Machine Learning}, year = {2020}, volume = {109}, pages = {1393--1434}, url = {https://link.springer.com/content/pdf/10.1007/s10994-019-05843-w.pdf} }
Edelkamp, S. & Kissmann, P.	On the Complexity of BDDs for State Space Search: A Case Study in Connect Four [Abstract] [BibTeX]	2011	Proceedings of the IJCAI-11 Workshop on General Game Playing (GIGA'11), pp. 15-21	inproceedings	URL
Abstract: Symbolic search using BDDs usually saves huge amounts of memory, while in some domains its savings are moderate at best. It is an open problem to determine if BDDs work well for a certain domain. Motivated by finding evidences for BDD growths for state space search, in this paper we are concerned with symbolic search in the domain of CONNECT FOUR. We prove that there is a variable ordering for which the set of all possible states - when continuing after a terminal state has been reached - can be represented by polynomial sized BDDs, whereas the termination criterion leads to an exponential number of nodes in the BDD given any variable ordering.
BibTeX: @inproceedings{Edelkamp2011a, author = {Stefan Edelkamp and Peter Kissmann}, title = {On the Complexity of BDDs for State Space Search: A Case Study in Connect Four}, booktitle = {Proceedings of the IJCAI-11 Workshop on General Game Playing (GIGA'11)}, year = {2011}, pages = {15-21}, url = {http://ijcai-11.iiia.csic.es/files/proceedings/GIGA-11-Proceedings.pdf} }
Edelkamp, S. & Kissmann, P.	On the Complexity of BDDs for State Space Search: A Case Study in Connect Four. [Abstract] [BibTeX]	2011	AAAI	inproceedings	URL
Abstract: Symbolic search using BDDs usually saves huge amounts of memory, while in some domains its savings are moderate at best. It is an open problem to determine if BDDs work well for a certain domain. Motivated by finding evidences for BDD growths for state space search, in this paper we are concerned with symbolic search in the domain of Connect Four. We prove that there is a variable ordering for which the set of all possible states – when continuing after a terminal state has been reached - can be represented by polynomial sized BDDs, whereas the termination criterion leads to an exponential number of nodes in the BDD given any variable ordering.
BibTeX: @inproceedings{Edelkamp2011, author = {Edelkamp, Stefan and Kissmann, Peter}, title = {On the Complexity of BDDs for State Space Search: A Case Study in Connect Four.}, booktitle = {AAAI}, publisher = {AAAI Press}, year = {2011}, url = {http://www.aaai.org/ocs/index.php/AAAI/AAAI11/paper/view/3690} }
Edelkamp, S. & Kissmann, P.	Symbolic Classification of General Multi-Player Games [Abstract] [BibTeX]	2008	European Conference on Artificial Intelligence (ECAI), pp. 905-906	inproceedings	DOI URL
Abstract: For general two-player turn-taking games, first solvers have been contributed. Algorithms for multi-player games like Maxn, however, cannot classify general games robustly, and its extension Soft-Maxn, which can play optimally against unknown and weak opponents, demands large amounts of memory. As RAM is a scarce resource, this paper proposes a memory-efficient implementation of the Soft-Maxn algorithm, by exploiting the functional representation of state and evaluation sets with BDDs.
BibTeX: @inproceedings{Edelkamp2008, author = {Stefan Edelkamp and Peter Kissmann}, title = {Symbolic Classification of General Multi-Player Games}, booktitle = {European Conference on Artificial Intelligence (ECAI)}, year = {2008}, pages = {905-906}, url = {http://dx.doi.org/10.3233/978-1-58603-891-5-905}, doi = {http://dx.doi.org/10.3233/978-1-58603-891-5-905} }
Edelkamp, S. & Kissmann, P.	Symbolic Classification of General Two-Player Games [Abstract] [BibTeX]	2008	German Conference on Artificial Intelligence (KI), pp. 185-192	inproceedings	URL
Abstract: In this paper we present a new symbolic algorithm for the classification, i. e. the calculation of the rewards for both players in case of optimal play, of two-player games with general rewards according to the Game Description Language. We will show that it classifies all states using a linear number of images concerning the depth of the game graph. We also present an extension that uses this algorithm to create symbolic endgame databases and then performs UCT to find an estimate for the classification of the game.
BibTeX: @inproceedings{Edelkamp2008a, author = {Stefan Edelkamp and Peter Kissmann}, title = {Symbolic Classification of General Two-Player Games}, booktitle = {German Conference on Artificial Intelligence (KI)}, year = {2008}, pages = {185-192}, url = {http://www.tzi.de/~edelkamp/publications/conf/ki/EdelkampK08-1.pdf} }
Edelkamp, S. & Kissmann, P.	Symbolic Exploration for General Game Playing in PDDL [Abstract] [BibTeX]	2007	Workshop on Planning and Games (PG), International Conference on Automated Planning and Scheduling	inproceedings	URL
Abstract: In artificial intelligence (AI), two- and multiplayer games have been of some interest, but the best AI algorithms always had considerable knowledge of the game they were designed for (Schaeffer 2000). In general game playing (Love, Hinrichs, & Genesereth 2006) strategies are computed domain independently without knowing which game is played. Best policies result in perfect play. The opponents attempt to maximize their gain. Game trees are often depth bounded and values at the leaf nodes of the trees are computed by a static evaluation function. On the other hand, retrograde analysis (Schaeffer et al. 2005) calculates databases of classified positions in backward direction, starting from won and lost ones. These endgame databases can be used in conjunction with game playing programs to eventually solve the game by computing the game theoretical status of the initial position. The purpose of this paper is to close the gap between general game playing and domain independent action planning. Moreover, we illustrate how symbolic planning technology can be applied.
BibTeX: @inproceedings{Edelkamp2007, author = {Stefan Edelkamp and Peter Kissmann}, title = {Symbolic Exploration for General Game Playing in PDDL}, booktitle = {Workshop on Planning and Games (PG), International Conference on Automated Planning and Scheduling}, year = {2007}, url = {http://www.plg.inf.uc3m.es/icaps-pg2007/papers/Symbolic%20Exploration%20for%20Generalized%20Game%20Playing%20in%20PDDL.pdf} }
Edin, E.	Classification and Solutions of General Combinatorial Games [Abstract] [BibTeX]	2007	School: Royal Institute of Technology, Stockholm, Sweden	mastersthesis	URL
Abstract: This master's project is an attempt to enable automatic classification and solving of combinatorial games, in the context of general game playing. The Game Description Language is used as the framework for general game playing. The classification of the combinatorial games is focused on the basic properties normal or misère form, all small games, partial or impartial games, and number of players. The methods used in making these classifications are template matching and logical deduction. This master's thesis focuses on solving only subtraction games, since they are easily analysed, while remaining interesting. Presented here is a solution, that can analyse the most common constructs, to solving a slightly generalised form of subtraction games. The classification and solving is tested on a suite of games constructed for this master's project.
BibTeX: @mastersthesis{Edin2007, author = {Erik Edin}, title = {Classification and Solutions of General Combinatorial Games}, school = {Royal Institute of Technology, Stockholm, Sweden}, year = {2007}, url = {http://www.nada.kth.se/utbildning/grukth/exjobb/rapportlistor/2007/rapporter07/edin_erik_07048.pdf} }
Engesser, T., Mattmüller, R., Thielscher, M. & Nebel, B.	Epistemic Game Description Language and Dynamic Epistemic Logic Compared [BibTeX]	2018	Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), pp. 1795-1802	inproceedings	URL
BibTeX: @inproceedings{Engesser2018, author = {Thorsten Engesser and Robert Mattmüller and Michael Thielscher and Bernhard Nebel}, title = {Epistemic Game Description Language and Dynamic Epistemic Logic Compared}, booktitle = {Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI)}, year = {2018}, pages = {1795--1802}, url = {http://gki.informatik.uni-freiburg.de/papers/engesser-mattmueller-nebel-thielscher-ijcai2018.pdf} }
Fawcett, T.E.	Knowledge-Based Feature Discovery for Evaluation Functions [Abstract] [BibTeX]	1996	Computational Intelligence Vol. 12(1), pp. 42-64	article	URL
Abstract: Since Samuel's work on checkers over thirty years ago, much effort has been devoted to learning evaluation functions. However, all such methods are sensitive to the feature set chosen to represent the examples. If the features do not capture aspects of the examples significant for problem solving, the learned evaluation function may be inaccurate or inconsistent. Typically, good feature sets are carefully handcrafted and a great deal of time and effort goes into refining and tuning them. This paper presents an automatic knowledge-based method for generating features for evaluation functions. The feature set is developed iteratively: features are generated, then evaluated, and this information is used to develop new features in turn. Both the contribution of a feature and its computational expense are considered in determining whether and how to develop it further. This method has been applied to two problem solving domains: the Othello board game and the domain of telecommunications network management. Empirical results show that the method is able to generate many known features and several novel features, and to improve concept accuracy in both domains.
BibTeX: @article{Fawcett1996, author = {Fawcett, Tom E.}, title = {Knowledge-Based Feature Discovery for Evaluation Functions}, journal = {Computational Intelligence}, year = {1996}, volume = {12}, number = {1}, pages = {42-64}, url = {http://home.comcast.net/~tom.fawcett/public_html/papers/kbfd.pdf} }
Fawcett, T.E.	Feature Discovery for Problem Solving Systems [Abstract] [BibTeX]	1993	School: University of Massachusetts, Amherst	phdthesis	URL
Abstract: Since Samuel's work on checkers over thirty years ago, much effort has been devoted to learning evaluation functions automatically from examples. Many methods have been developed that, given examples of problem states paired with their desired evaluations, can induce an evaluation function from them. However, all such methods are sensitive to the set of features chosen to represent the examples. If the features do not capture those aspects of the examples that are significant for problem solving, the learned evaluation function may be inaccurate or inconsistent. Typically, good feature sets are handcrafted carefully, and a great deal of time and effort goes into refining and tuning them. Very little work has been done on automatically generating sets of features for problem solving domains, or on explaining why known features are useful. This dissertation presents a method for generating features for problem solving domains. It employs both a declarative problem specification and examples of state evaluations, and so combines aspects of both analytical and empirical learning. The feature set is developed iteratively: features are generated, then evaluated, and this information is used to develop new features in turn. Both the contribution of a feature and its computational expense are considered in determining whether and how to develop it further. This method has been applied to two problem solving domains: the Othello board game and the real-world domain of telecommunications network management. Empirical results show that the method is able to generate many known features, several novel features, and to improve concept accuracy in both domains.
BibTeX: @phdthesis{Fawcett1993, author = {Fawcett, Tom E.}, title = {Feature Discovery for Problem Solving Systems}, school = {University of Massachusetts, Amherst}, year = {1993}, url = {http://dl.acm.org/citation.cfm?id=164002} }
Fawcett, T.E. & Utgoff, P.E.	Automatic Feature Generation for Problem Solving Systems [BibTeX]	1992	Proc. of ICML, pp. 144-153	inproceedings	URL
BibTeX: @inproceedings{Fawcett1992, author = {T. E. Fawcett and P. E. Utgoff}, title = {Automatic Feature Generation for Problem Solving Systems}, booktitle = {Proc. of ICML}, publisher = {Morgan Kaufmann}, year = {1992}, pages = {144-153}, url = {ftp://ftp.cs.umass.edu/pub/techrept/techreport/1992/UM-CS-1992-009.ps} }
Finnsson, H.	Simulation-Based General Game Playing [Abstract] [BibTeX]	2012	School: Reykjavík University	phdthesis	URL
Abstract: The aim of General Game Playing (GGP) is to create intelligent agents that automatically learn how to play many different games at an expert level without any human intervention. One of the main challenges such agents face is to automatically learn knowledge-based heuristics in real-time, whether for evaluating game positions or for search guidance. In this thesis we approach this challenge with Monte-Carlo Tree Search (MCTS), which in recent years has become a popular and effective search method in games. For competitive play such an approach requires an effective search-control mechanism for guiding the simulation playouts. In here we describe our GGP agent, CADIA PLAYER, and introduce several schemes for automatically learning search guidance based on both statistical and reinforcement learning techniques. Providing GGP agents with the knowledge relevant to the game at hand in real time is, however, a challenging task. This thesis furthermore proposes two extensions for MCTS in the context of GGP, aimed at improving the effectiveness of the simulations in real time based on in-game statistical feedback. Also we present a way to extend MCTS solvers to handle simultaneous move games. Finally, we study how various gametree properties affect MCTS performance.
BibTeX: @phdthesis{Finnsson2012, author = {Hilmar Finnsson}, title = {Simulation-Based General Game Playing}, school = {Reykjavík University}, year = {2012}, url = {http://www.ru.is/media/skjol-td/Hilmar_Finnsson_PhD_CS_HR.pdf} }
Finnsson, H.	Generalized Monte-Carlo Tree Search Extensions for General Game Playing [Abstract] [BibTeX]	2012	Twenty-Sixth AAAI Conference on Artificial Intelligence	inproceedings	URL
Abstract: General Game Playing (GGP) agents must be capable of playing a wide variety of games skillfully. Monte-Carlo Tree Search (MCTS) has proven an effective reasoning mechanism for this challenge, as is reﬂected by its popularity among designers of GGP agents. Providing GGP agents with the knowledge relevant to the game at hand in real time is, however, a challenging task. In this paper we propose two enhancements for MCTS in the context of GGP, aimed at improving the effectiveness of the simulations in real time based on in-game statistical feedback. The ﬁrst extension allows early termination of lengthy and uninformative simulations while the second improves the action-selection strategy when both explored and unexplored actions are available. The methods are empirically evaluated in a state-of-the-art GGP agent and shown to yield an overall signiﬁcant improvement in playing strength.
BibTeX: @inproceedings{Finnsson2012a, author = {Hilmar Finnsson}, title = {Generalized Monte-Carlo Tree Search Extensions for General Game Playing}, booktitle = {Twenty-Sixth AAAI Conference on Artificial Intelligence}, year = {2012}, url = {http://www.aaai.org/ocs/index.php/AAAI/AAAI12/paper/viewFile/4935/5300} }
Finnsson, H.	CADIA-Player: A General Game Playing Agent [Abstract] [BibTeX]	2007	School: Reykjavík University - School of Computer Science	mastersthesis	URL
Abstract: The aim of General Game Playing (GGP) is to create intelligent agents that can automatically learn how to play many different games well without any human intervention, given only a description of the game rules. This forces the agents to be able to learn a strategy without having any domain-specific knowledge provided by their developers. The most successful GGP agents have so far been based on the traditional approach of using game-tree search augmented with an automatically learned evaluation function for encapsulating the domain-specific knowledge. In this thesis we describe CADIAPlayer, a GGP agent that instead uses a simulation-based approach to reason about its actions. More specifically, it uses Monte Carlo rollouts with upper confidence bounds for trees (UCT) as its main search procedure. CADIAPlayer has already proven the effectiveness of this simulation-based approach in the context of GGP by winning the Third Annual GGP Competition. We describe its implementation as well as several algorithmic improvements for making the simulations more effective. Empirical data is presented showing that CADIA-Player outperforms naïve Monte Carlo by close to 90% winning ratio on average on a wide range of games, including Checkers and Othello. We further investigate the relative importance of UCT?s actionselection rule, its memory model, and the various enhancements in achieving this result.
BibTeX: @mastersthesis{Finnsson2007, author = {Hilmar Finnsson}, title = {CADIA-Player: A General Game Playing Agent}, school = {Reykjavík University - School of Computer Science}, year = {2007}, url = {http://ru.is/lisalib/getfile.aspx?itemid=9558} }
Finnsson, H. & Björnsson, Y.	Game-Tree Properties and MCTS Performance [Abstract] [BibTeX]	2011	Proceedings of the IJCAI-11 Workshop on General Game Playing (GIGA'11), pp. 23-30	inproceedings	URL
Abstract: In recent years Monte-Carlo Tree Search (MCTS) has become a popular and effective search method in games, surpassing traditional alpha-beta methods in many domains. The question of why MCTS does better in some domains than in others remains, however, relatively open. In here we identify some general properties that are encountered in game trees and measure how these properties affect the success of MCTS. We do this by running it on custom-made games that allow us to parameterize various game properties in order for trends to be discovered. Our experiments show how MCTS can favor either deep, wide or balanced game trees. They also show how the level of game progression relates to playing strength and how disruptive Optimistic Move can be.
BibTeX: @inproceedings{Finnsson2011, author = {Hilmar Finnsson and Yngvi Björnsson}, title = {Game-Tree Properties and MCTS Performance}, booktitle = {Proceedings of the IJCAI-11 Workshop on General Game Playing (GIGA'11)}, year = {2011}, pages = {23-30}, url = {http://cadia.ru.is/wiki/_media/public:cadiaplayer:hif_giga11.pdf} }
Finnsson, H. & Björnsson, Y.	CadiaPlayer: Search-Control Techniques [Abstract] [BibTeX]	2011	KI Vol. 25(1), pp. 9-16	article	URL
Abstract: Effective search control is one of the key components of any successful simulation-based game-playing program. In General Game Playing (GGP), learning of useful search-control knowledge is a particularly challenging task because it must be done in real-time during online play. In here we describe the search-control techniques used in the 2010 version of the GGP agent CadiaPlayer, and show how they have evolved over the years to become increasingly effective and robust across a wide range of games. In particular, we present a new combined search-control scheme (RAVE/MAST/FAST) for biasing action selection. The scheme proves quite effective on a wide range of games including chess-like games, which have up until now proved quite challenging for simulation-based GGP agents.
BibTeX: @article{Finnsson2011a, author = {Hilmar Finnsson and Yngvi Björnsson}, title = {CadiaPlayer: Search-Control Techniques}, journal = {KI}, year = {2011}, volume = {25}, number = {1}, pages = {9-16}, url = {http://www.springerlink.com/content/1411104x6q2h0182/} }
Finnsson, H. & Björnsson, Y.	Learning Simulation Control in General Game Playing Agents [BibTeX]	2010	#AAAI#, pp. 954-959	inproceedings	URL
BibTeX: @inproceedings{Finnsson2010, author = {Hilmar Finnsson and Yngvi Björnsson}, title = {Learning Simulation Control in General Game Playing Agents}, booktitle = {#AAAI#}, publisher = {AAAI Press}, year = {2010}, pages = {954-959}, url = {http://www.ru.is/faculty/yngvi/pdf/FinnssonB10a.pdf} }
Finnsson, H. & Björnsson, Y.	Simulation Control in General Game Playing Agents [BibTeX]	2009	Proceedings of the IJCAI-09 Workshop on General Game Playing (GIGA'09), pp. 21-26	inproceedings	URL
BibTeX: @inproceedings{Finnsson2009, author = {Hilmar Finnsson and Yngvi Björnsson}, title = {Simulation Control in General Game Playing Agents}, booktitle = {Proceedings of the IJCAI-09 Workshop on General Game Playing (GIGA'09)}, year = {2009}, pages = {21-26}, url = {http://www.ru.is/faculty/yngvi/pdf/finnssonb09a.pdf} }
Finnsson, H. & Björnsson, Y.	Simulation-based Approach to General Game Playing [Abstract] [BibTeX]	2008	AAAI	inproceedings	URL
Abstract: The aim of General Game Playing (GGP) is to create intelligent agents that automatically learn how to play many different games at an expert level without any human intervention. The most successful GGP agents in the past have used traditional game-tree search combined with an automatically learned heuristic function for evaluating game states. In this paper we describe a GGP agent that instead uses a Monte Carlo/UCT simulation technique for action selection, an approach recently popularized in computer Go. Our GGP agent has proven its effectiveness by winning last year?s AAAI GGP Competition. Furthermore, we introduce and empirically evaluate a new scheme for automatically learning search-control knowledge for guiding the simulation playouts, showing that it offers significant benefits for a variety of games.
BibTeX: @inproceedings{Finnsson2008, author = {Hilmar Finnsson and Yngvi Björnsson}, title = {Simulation-based Approach to General Game Playing}, booktitle = {AAAI}, publisher = {AAAI Press}, year = {2008}, url = {http://ru.is/faculty/hif/papers/cadiaplayer_aaai08.pdf} }
Geißer, F., Keller, T. & Mattmüller, R.	Past, Present, and Future: An Optimal Online Algorithm for Single-Player GDL-II Games [Abstract] [BibTeX]	2014	Proceedings of the 21st European Conference on Artificial Intelligence (ECAI), pp. 357-362	inproceedings
Abstract: In General Game Playing, a player receives the rules of an unknown game and attempts to maximize his expected reward. Since 2011, the GDL-II rule language extension allows the formulation of nondeterministic and partially observable games. In this paper, we present an algorithm for such games, with a focus on the single-player case. Conceptually, at each stage, the proposed NORNS algorithm distinguishes between the past, present and future steps of the game. More specifically, a belief state tree is used to simulate a potential past that leads to a present that is consistent with received observations. Unlike other related methods, our method is asymptotically optimal. Moreover, augmenting the belief state tree with iteratively improved probabilities speeds up the process over time significantly. As this allows a true picture of the present, we additionally present an optimal version of the well-known UCT algorithm for partially observable single-player games. Instead of performing hindsight optimization on a simplified, fully observable tree, the true future is simulated on an action-observation tree that takes partial observability into account. The expected reward estimates of applicable actions converge towards the true expected rewards even for moves that are only used to gather information. We prove that our algorithm is asymptotically optimal for single-player games and POMDPs and support our claim with an empirical evaluation.
BibTeX: @inproceedings{Geisser2014, author = {Florian Geißer and Thomas Keller and Robert Mattmüller}, title = {Past, Present, and Future: An Optimal Online Algorithm for Single-Player GDL-II Games}, booktitle = {Proceedings of the 21st European Conference on Artificial Intelligence (ECAI)}, publisher = {IOS Press}, year = {2014}, pages = {357-362} }
Genesereth, M. & Björnsson, Y.	The International General Game Playing Competition [Abstract] [BibTeX]	2013	AI Magazine Vol. 34(2), pp. 107-111	article	URL
Abstract: Games have played a prominent role as a test-bed for advancements in the field of Artificial Intelligence ever since its foundation over half a century ago, resulting in highly specialized world-class game-playing systems being developed for various games. The establishment of the International General Game Playing Competition in 2005, however, resulted in a renewed interest in more general problem solving approaches to game playing. In general game playing (GGP) the goal is to create game-playing systems that autonomously learn how to skillfully play a wide variety of games, given only the descriptions of the game rules. In this paper we review the history of the competition, discuss progress made so far, and list outstanding research challenges.
BibTeX: @article{Genesereth2013, author = {Michael Genesereth and Yngvi Björnsson}, title = {The International General Game Playing Competition}, journal = {AI Magazine}, year = {2013}, volume = {34}, number = {2}, pages = {107-111}, url = {http://www.aaai.org/ojs/index.php/aimagazine/article/view/2475} }
Genesereth, M. & Thielscher, M.	General Game Playing [Abstract] [BibTeX]	2014		book	DOI
Abstract: General game players are computer systems able to play strategy games based solely on formal game descriptions supplied at "runtime" (n other words, they don't know the rules until the game starts). Unlike specialized game players, such as Deep Blue, general game players cannot rely on algorithms designed in advance for specific games; they must discover such algorithms themselves. General game playing expertise depends on intelligence on the part of the game player and not just intelligence of the programmer of the game player. GGP is an interesting application in its own right. It is intellectually engaging and more than a little fun. But it is much more than that. It provides a theoretical framework for modeling discrete dynamic systems and defining rationality in a way that takes into account problem representation and complexities like incompleteness of information and resource bounds. It has practical applications in areas where these features are important, e.g., in business and law. More fundamentally, it raises questions about the nature of intelligence and serves as a laboratory in which to evaluate competing approaches to artificial intelligence. This book is an elementary introduction to General Game Playing (GGP). (1) It presents the theory of General Game Playing and leading GGP technologies. (2) It shows how to create GGP programs capable of competing against other programs and humans. (3) It offers a glimpse of some of the real-world applications of General Game Playing.
BibTeX: @book{Genesereth2014, author = {Michael Genesereth and Michael Thielscher}, title = {General Game Playing}, publisher = {Morgan & Claypool}, year = {2014}, doi = {http://dx.doi.org/10.2200/S00564ED1V01Y201311AIM024} }
Genesereth, M.R., Love, N. & Pell, B.	General Game Playing: Overview of the AAAI Competition [Abstract] [BibTeX]	2005	AI Magazine Vol. 26(2), pp. 62-72	article	URL
Abstract: A General Game Playing System is one that can accept a formal description of a game and play the game effectively without human intervention. Unlike specialized game players, such as Deep Blue, general game players do not rely on algorithms designed in advance for specific games; and, unlike Deep Blue, they are able to play different kinds of games. In order to promote work in this area, the AAAI is sponsoring an open competition at this summer's National Conference. This article is an overview of the technical issues and logistics associated with this summer?s competition, as well as the relevance of General Game Playing to the long range goals of artificial intelligence.
BibTeX: @article{Genesereth2005, author = {Michael R. Genesereth and Nathaniel Love and Barney Pell}, title = {General Game Playing: Overview of the AAAI Competition}, journal = {AI Magazine}, year = {2005}, volume = {26}, number = {2}, pages = {62-72}, url = {http://games.stanford.edu/competition/misc/aaai.pdf} }
Goldwaser, A. & Thielscher, M.	Deep Reinforcement Learning for General Game Playing [BibTeX]	2020	Proceedings of the AAAI Conference on Artificial Intelligence, pp. 1701-1708	inproceedings	URL
BibTeX: @inproceedings{Goldwaser2020, author = {Adrian Goldwaser and Michael Thielscher}, title = {Deep Reinforcement Learning for General Game Playing}, booktitle = {Proceedings of the AAAI Conference on Artificial Intelligence}, publisher = {AAAI Press}, year = {2020}, pages = {1701--1708}, url = {http://cgi.cse.unsw.edu.au/~mit/Papers/AAAI20.pdf} }
Gudmundsson, S.F. & Björnsson, Y.	MCTS: Improved Action Selection Techniques for Deterministic Games [Abstract] [BibTeX]	2011	Proceedings of the IJCAI-11 Workshop on General Game Playing (GIGA'11), pp. 45-52	inproceedings	URL
Abstract: The simulation-based principles behind Monte-Carlo Tree Search (MCTS) have their roots in non-deterministic domains. In game domains, MCTS has nonetheless proved successful in both non-deterministic and deterministic games. This has been achieved by using more or less identical selection mechanisms for choosing actions, thus potentially not fully exploiting the inherent differences of deterministic and non-deterministic games. In this paper we take steps towards better understanding how determinism and discrete game outcomes may inﬂuence how action selection is best done in the selection step in MCTS. We use a simple n-arm-bandit test domain to show that action selection can be improved by taking into account whether a game is deterministic and has only few discrete game outcomes possible. We introduce two methods in this context to do so: moving average return function and sufﬁciency threshold and evaluate them empirically in the n-arm-bandit test domain, as well as providing preliminary results in a GGP inspired game. Both methods offer signiﬁcant improvement over the standard UCT action-selection mechanism.
BibTeX: @inproceedings{Gudmundsson2011, author = {Stefan Freyr Gudmundsson and Yngvi Björnsson}, title = {MCTS: Improved Action Selection Techniques for Deterministic Games}, booktitle = {Proceedings of the IJCAI-11 Workshop on General Game Playing (GIGA'11)}, year = {2011}, pages = {45-52}, url = {ijcai-11.iiia.csic.es/files/proceedings/GIGA-11-Proceedings.pdf} }
Gudmundsson, S.F. & Björnsson, Y.	Sufﬁciency-Based Selection Strategy for MCTS [Abstract] [BibTeX]	2013	Proceedings of the IJCAI-13 Workshop on General Game Playing (GIGA'13), pp. 15-21	inproceedings	URL
Abstract: Monte-Carlo Tree Search (MCTS) has proved a remarkably effective decision mechanism in many different game domains, including computer Go and general game playing (GGP). However, in GGP, where many disparate games are played, certain type of games have proved to be particularly problematic for MCTS. One of the problems are game trees with so-called optimistic moves, that is, bad moves that superﬁcially look good but potentially require much simulation effort to prove otherwise. Such scenarios can be difﬁcult to identify in real time and can lead to suboptimal or even harmful decisions. In this paper we investigate a selection strategy for MCTS to alleviate this problem. The strategy, called sufﬁciency threshold, concentrates simulation effort better for resolving potential optimistic move scenarios. The improved strategy is evaluated empirically in an n-arm-bandit test domain for highlighting its properties as well as in a state-of-the-art GGP agent to demonstrate its effectiveness in practice. The new strategy shows significant improvements in both domains.
BibTeX: @inproceedings{Gudmundsson2013, author = {Stefan Freyr Gudmundsson and Yngvi Björnsson}, title = {Sufﬁciency-Based Selection Strategy for MCTS}, booktitle = {Proceedings of the IJCAI-13 Workshop on General Game Playing (GIGA'13)}, year = {2013}, pages = {15-21}, url = {http://giga13.ru.is/GIGA-13-Proceedings.pdf} }
Guðmundsson, G.Þ.	Solving general game playing puzzles using heuristics search [Abstract] [BibTeX]	2009	School: Reykjavik University	mastersthesis	URL
Abstract: One of the challenges of General Game Playing (GGP) is to effectively solve puzzles. Solving puzzles is more similar to planning algorithms than the search methods used for two- or multi-player games. General problem solving has been a topic addressed by the planning community for years. In this thesis we adapt heuristic search methods for automated planning to use in solving single-agent GGP puzzles. One of the main differences between planning and GGP is the real-time nature of GGP competitions. The backbone of our puzzle solver is a realtime variant of the classical A* search algorithm we call Time-Bounded and Injection-based A* (TBIA). The TBIA is a complete algorithm which always maintains a best known path to follow and updates this path with new and better paths as they are discovered. The heuristic TBIA* uses is constructed automatically for each puzzle being solved, and is based on techniques used in the Heuristic Search Planner system. It is composed of two parts: the first is a distance estimate derived from solving a relaxed problem and the second is a penalty for every unachieved sub-goal. The heuristic is inadmissible when the penalty is added but typically more informative. We also present a caching mechanism to enhance the heuristic performance and a self regulating method we call adaptive k that balances cache useage. We show that our method both adds to the flora of GGP puzzles solvable under real-time settings and outperforms existing simulation-based solution methods on a number of puzzles.
BibTeX: @mastersthesis{Guomundsson2009, author = {Gylfi Þór Guðmundsson}, title = {Solving general game playing puzzles using heuristics search}, school = {Reykjavik University}, year = {2009}, url = {http://hdl.handle.net/1946/7422} }
Günther, M.	Automatic Feature Construction for General Game Playing [Abstract] [BibTeX]	2008	School: TU-Dresden	mastersthesis	URL
Abstract: 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(lambda) 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.
BibTeX: @mastersthesis{Guenther2008, author = {Martin Günther}, title = {Automatic Feature Construction for General Game Playing}, school = {TU-Dresden}, year = {2008}, url = {http://www.inf.tu-dresden.de/content/institutes/ki/cl/study/assignments/download/diplom_guenther_feature_construction.pdf} }
Günther, M.	Decomposition of Single Player Games [Abstract] [BibTeX]	2007	School: TU-Dresden	misc	URL
Abstract: The goal of General Game Playing is to construct an autonomous agent that can effectively play games it has never encountered before. Only the game rules are given explicitly; most 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. This work presents a method to decompose a given single-player game into its subgames by analyzing the preconditions and effects of actions. Moreover, two different search algorithms that exploit this information are proposed. Both are assessed and compared with regard to their optimality and computational complexity.
BibTeX: @misc{Guenther2007, author = {Martin Günther}, title = {Decomposition of Single Player Games}, school = {TU-Dresden}, year = {2007}, url = {http://www.inf.tu-dresden.de/content/institutes/ki/cl/study/assignments/download/beleg_guenther_subgame_detection.pdf} }
Günther, M., Schiffel, S. & Thielscher, M.	Factoring General Games [Abstract] [BibTeX]	2009	Proceedings of the IJCAI-09 Workshop on General Game Playing (GIGA'09), pp. 27-33	inproceedings	URL
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.
BibTeX: @inproceedings{Guenther2009, author = {Martin Günther and Stephan Schiffel and Michael Thielscher}, title = {Factoring General Games}, booktitle = {Proceedings of the IJCAI-09 Workshop on General Game Playing (GIGA'09)}, year = {2009}, pages = {27-33}, url = {http://www.general-game-playing.de/downloads/GIGA09_factoring_general_games.pdf} }
Haufe, S.	Automated Theorem Proving for General Game Playing [Abstract] [BibTeX]	2012	School: Technische Universität Dresden	phdthesis	URL
Abstract: General Game Playing is concerned with the development of techniques that enable computer programs to play arbitrary n-player games given nothing but the game rules in a tailor-made description language. A key to success in this endeavour is the ability to reliably extract hidden game-specific features from a given game description to choose the currently most appropriate algorithm, to construct a suited heuristic, or to apply techniques that reduce the search space. In addition, an automated method for property extraction can provide valuable assistance for the discovery of specification bugs during game design. In this thesis, we develop a provably correct theory for the automated verification of game-specific invariance properties which may involve arbitrary finite sequences of successive game states as well as player-specific knowledge. Our proof theory applies an induction principle on the game rules based on the generation of answer set programs, which allows to practically verify invariance properties even in complex games whose state space cannot totally be explored.
BibTeX: @phdthesis{Haufe2012, author = {Sebastian Haufe}, title = {Automated Theorem Proving for General Game Playing}, school = {Technische Universität Dresden}, year = {2012}, url = {http://nbn-resolving.de/urn:nbn:de:bsz:14-qucosa-89998} }
Haufe, S., Michulke, D., Schiffel, S. & Thielscher, M.	Knowledge-Based General Game Playing [Abstract] [BibTeX]	2011	KI Vol. 25(1), pp. 25-33	article	URL
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.
BibTeX: @article{Haufe2011, author = {Sebastian Haufe and Daniel Michulke and Stephan Schiffel and Michael Thielscher}, title = {Knowledge-Based General Game Playing}, journal = {KI}, year = {2011}, volume = {25}, number = {1}, pages = {25-33}, url = {http://www.springerlink.com/content/j8n427724vh5u625/} }
Haufe, S., Schiffel, S. & Thielscher, M.	Automated Verification of State Sequence Invariants in General Game Playing [Abstract] [BibTeX]	2012	Artificial Intelligence Vol. 187-188, pp. 1-30	article	DOI URL
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.
BibTeX: @article{Haufe2012a, author = {Sebastian Haufe and Stephan Schiffel and Michael Thielscher}, title = {Automated Verification of State Sequence Invariants in General Game Playing}, journal = {Artificial Intelligence}, year = {2012}, volume = {187-188}, pages = {1-30}, url = {http://dx.doi.org/10.1016/j.artint.2012.04.003}, doi = {http://dx.doi.org/10.1016/j.artint.2012.04.003} }
Haufe, S. & Thielscher, M.	Pushing the Envelope: General Game Players Prove Theorems [Abstract] [BibTeX]	2010	Vol. 6464Proceedings of the Australasian Joint Conference on Artificial Intelligence, pp. 1-10	inproceedings	URL
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.
BibTeX: @inproceedings{Haufe2010, author = {Sebastian Haufe and Michael Thielscher}, title = {Pushing the Envelope: General Game Players Prove Theorems}, booktitle = {Proceedings of the Australasian Joint Conference on Artificial Intelligence}, publisher = {Springer}, year = {2010}, volume = {6464}, pages = {1-10}, url = {http://cgi.cse.unsw.edu.au/~mit/Papers/AI10.pdf} }
Haufe, S. & Thielscher, M.	Automated Verification of Epistemic Properties for General Game Playing [Abstract] [BibTeX]	2012	Proceedings of the International Conference onPrinciples of Knowledge Representation and Reasoning (KR)	inproceedings	URL
Abstract: Automatically deriving properties of new games is one of the fundamental challenges for general game-playing systems, whose task is to learn to play any previously unknown game solely by being given the rules of that game. A recently developed method uses Answer Set Programming for verifying ﬁnitely-bounded temporal invariance properties against a given game description by structural induction. Addressing the new challenge posed by the recent extension of the general Game Description Language to include games with imperfect information and randomness, we extend this method to epistemic properties about games. We formally prove this extension to be correct, and we report on experiments that show its practical applicability.
BibTeX: @inproceedings{Haufe2012b, author = {Sebastian Haufe and Michael Thielscher}, title = {Automated Verification of Epistemic Properties for General Game Playing}, booktitle = {Proceedings of the International Conference onPrinciples of Knowledge Representation and Reasoning (KR)}, year = {2012}, url = {http://cgi.cse.unsw.edu.au/~mit/Papers/KR12.pdf} }
Hinrichs, T.	Automatically Proving Playability through Abstraction [BibTeX]	2006		techreport	URL
BibTeX: @techreport{Hinrichs2006, author = {Timothy Hinrichs}, title = {Automatically Proving Playability through Abstraction}, year = {2006}, url = {http://www.cs.uic.edu/~hinrichs/papers/hinrichs2005automatically.pdf} }
Hinrichs, T. & Forbus, K.D.	Transfer Learning through Analogy in Games [Abstract] [BibTeX]	2011	AI Magazine Vol. 32(1), pp. 70-83	article	URL
Abstract: We report on a series of transfer learning experiments in game domains, in which we use structural analogy from one learned game to speed learning of another related game. We find that a major benefit of analogy is that it reduces the extent to which the source domain must be generalized before transfer. We describe two techniques in particular, minimal ascension and metamapping, that enable analogies to be drawn even when comparing descriptions using different relational vocabularies. Evidence for the effectiveness of these techniques is provided by a large-scale external evaluation, involving a substantial number of novel distant analogs.
BibTeX: @article{Hinrichs2011, author = {Thomas Hinrichs and Kenneth D. Forbus}, title = {Transfer Learning through Analogy in Games}, journal = {AI Magazine}, year = {2011}, volume = {32}, number = {1}, pages = {70-83}, url = {http://www.aaai.org/ojs/index.php/aimagazine/article/view/2332} }
van der Hoek, W., Ruan, J. & Wooldridge, M.	Strategy Logics and the Game Description Language [Abstract] [BibTeX]	2007	Proceedings of the Workshop on Logic, Rationality and Interaction	inproceedings	URL
Abstract: The Game Description Language (GDL) is a special purpose declarative language for defining games. GDL is used in the AAAI General Game Playing Competition, which tests the ability of computer programs to play games in general, rather than just to play a specific game. Participants in the competition are provided with a game specified in GDL, and then required to play this game. Recently, there has been much interest in the use of strategic cooperation logics for reasoning about game-like scenarios - Alternatingtime Temporal Logic (ATL) is perhaps the best known example. The aim of this paper is to make a link between ATL and GDL. We show that a GDL specification can be viewed as a specification of an ATL model, and that ATL can thus be interpreted over GDL specifications. Our main result is that it is possible to translate a propositional GDL specification into an "equivalent" ATL specification, which is only polynomially larger than the original GDL specification. As a corollary, we are able to characterise the complexity of reasoning about GDL-specified games using ATL: it is EXPTIME-complete.
BibTeX: @inproceedings{Hoek2007, author = {W. van der Hoek and J. Ruan and M. Wooldridge}, title = {Strategy Logics and the Game Description Language}, booktitle = {Proceedings of the Workshop on Logic, Rationality and Interaction}, year = {2007}, url = {http://www.csc.liv.ac.uk/~mjw/pubs/lori2007a.pdf} }
Holt, A.	General Game Playing Systems [Abstract] [BibTeX]	2008	School: Technical University of Denmark	mastersthesis	URL
Abstract: General Game Playing (GGP) is a field in artificial intelligence (AI) that deals with systems that, provided with only the rules of an arbitrary game, can play the game in an intelligent way. This problem is much harder than making a computer play a specificc game since you cannot rely on predefined evaluation functions or any other domain specific knowledge. It is also more interesting from an AI point of view since the computer needs to show some intelligent behaviour in order to come up with a good move instead of just following a predefined formula. In this report we will investigate different methods of making such a system. We will look at what others have done, and an actual implementation of our own general game player is presented. This implementation can either use the minimax algorithm with a simulation based evaluation mechanism or the UCT algorithm based on Monte Carlo simulations. In the end of this report these two techniques are compared by playing against each other in different games. These comparisons shows that the minimax algorithm with an evaluation function is a good choice in GGP but the UCT algorithm can be very strong when given enough time or computational resources to make a suitable amount of simulations.
BibTeX: @mastersthesis{Holt2008, author = {Andreas Holt}, title = {General Game Playing Systems}, school = {Technical University of Denmark}, year = {2008}, url = {http://orbit.dtu.dk/getResource?recordId=228660&objectId=1&versionId=1} }
Huang, X., Ruan, J. & Thielscher, M.	Model Checking for Reasoning About Incomplete Information Games [Abstract] [BibTeX]	2013	Proceedings of the IJCAI-13 Workshop on General Game Playing (GIGA'13), pp. 47-54	inproceedings	URL
Abstract: GDL-II is a logic-based knowledge representation formalism used in general game playing to describe the rules of arbitrary games, in particular those with incomplete information. In this paper, we show how model checking can be used to automatically verify that games speciﬁed in GDL-II satisfy desirable temporal and knowledge conditions. We present a systematic translation of GDL-II to a model checking language, prove the translation to be correct, and demonstrate the feasibility of applying model checking tools for GDL-II games by four case studies.
BibTeX: @inproceedings{Huang2013, author = {Xiaowei Huang and Ji Ruan and Michael Thielscher}, title = {Model Checking for Reasoning About Incomplete Information Games}, booktitle = {Proceedings of the IJCAI-13 Workshop on General Game Playing (GIGA'13)}, year = {2013}, pages = {47-54}, url = {http://giga13.ru.is/GIGA-13-Proceedings.pdf} }
Hufschmitt, A.	Recherche automatique d'heuristiques pou le General Game Playing [Abstract] [BibTeX]	2013	School: Université Paris 8 de Vincennes à Saint-Denis	mastersthesis	URL
Abstract: Dans ce mémoire, nous présentons une démarche pour générer automatique- ment des heuristiques dans le domaine du General Game Playing (GGP). Dans le cadre des compétitions de GGP organisées par Standford, les joueurs programmés reçoivent les règles de jeux originaux sous la forme de description en Game Deﬁnition Langage (GDL). Ces joueurs utilisent des algorithmes de parcours d’arbre comme le Upper Conﬁdence Bounds applied to Trees (UCT) pour déterminer les coups les plus prometteurs pouvant mener à une victoire. Ces algorithmes nécessitent l’usage d’heuristiques pour évaluer les positions et guider la recherche vers les branches les plus prometteuses. Ces heuristiques peuvent être des connaissances propres au domaine (présence d’un plateau de jeu, de marques, de pièces, etc.) établies manuellement et calculées à partir de caractéristiques extraites des règles GDL. Dans notre étude, nous rejetons cette démarche qui fait usage d’un savoir propre au domaine et nous proposons une méthode susceptible de fournir des heuristiques automatiquement à partir de la seule description GDL des positions d’un jeu. L’utilisation de réseaux de neurones pour la génération automatique d’heuristiques pose des problèmes notamment au niveau du choix de la topologie à utiliser. Nous proposons l’utilisation de l’algorithme de Neuro-Evolution of Augmenting Topologies (NEAT) susceptible de découvrir la topologie nécessaire pour la résolution de notre problème. Nous présentons donc le principe des algorithmes génétiques et le fonctionnement de NEAT. Notre but est de générer automatiquement des heuristiques permettant de guider une exploration UCT à chaque position d’un jeu. Cependant, pour évaluer notre méthode de génération d’heuristiques, nous limitons notre étude à des positions terminales de jeux dont le score est connu. Dans un premier temps, nous associons les faits GDL de ces positions à des pondérations. La somme des pondérations des faits vrais dans un état ﬁnal donné permet d’en estimer le score. Nous utilisons un algorithme génétique pour faire évoluer ces pondérations et évaluons la capacité de notre population à prédire le score d’un échantillon de 93 jeux. Nous concluons sur la non-linéarité du problème à traiter et sur l’incapacité d’un simple algorithme génétique à créer des combinaisons de faits nécessaires à l’évaluation de positions de jeux comme le Tictactoe. Dans un second temps, nous utilisons l’algorithme de Neuro-Evolution of Augmenting Topologies aﬁn de faire évoluer non plus des vecteurs de pondérations, mais des réseaux de neurones. Nous fournissons en entrée de ces réseaux les valeurs booléennes des faits dans chaque position ﬁnale. Nous avons obtenu des réseaux de topologies efﬁcaces pour la résolution de problèmes non-linéaires simples s’apparentant au problème du XOR, mais notre programme, fondé sur un exemple d’implémentation en C++ de Buckland [Buckland and Collins, 2002], n’a pas été en mesure de fournir des solutions élégantes et efﬁcaces pour la résolution de problèmes complexes. Nous concluons que NEAT s’avère une approche valable pour la génération automatique d’heuristiques, mais nous devons apporter des modiﬁcations à notre implémentation pour nous rapprocher du modèle original de Stanley [Stanley, 2004] et améliorer les résultats obtenus. Notre programme mis au point nous permettra d’évaluer des positions non-terminales et pourra générer automatiquement des heuristiques pour guider l’exploration UCT d’un joueur GGP.
BibTeX: @mastersthesis{Hufschmitt2013, author = {Aline Hufschmitt}, title = {Recherche automatique d'heuristiques pou le General Game Playing}, school = {Université Paris 8 de Vincennes à Saint-Denis}, year = {2013}, url = {http://www.alinehuf.fr/master1-info/heuristiques_GGP_alinehuf.pdf} }
Hufschmitt, A., Vittaut, J.-N. & Méhat, J.	A General Approach of Game Description Decomposition for General Game Playing [BibTeX]	2017	Vol. 705Computer Games. CGW 2016, GIGA 2016, pp. 165-177	inproceedings	URL
BibTeX: @inproceedings{Hufschmitt2017, author = {Aline Hufschmitt and Jean-Noël Vittaut and Jean Méhat}, title = {A General Approach of Game Description Decomposition for General Game Playing}, booktitle = {Computer Games. CGW 2016, GIGA 2016}, publisher = {Springer}, year = {2017}, volume = {705}, pages = {165-177}, url = {http://giga16.ru.is/giga16-paper3.pdf} }
Jiang, G., Zhang, D., Perrussel, L. & Zhang, H.	Epistemic GDL: A Logic for Representing and Reasoning about Imperfect Information Games [BibTeX]	2016	Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, pp. 1138-1144	inproceedings	URL
BibTeX: @inproceedings{Jiang2016, author = {Guifei Jiang and Dongmo Zhang and Laurent Perrussel and Heng Zhang}, title = {Epistemic GDL: A Logic for Representing and Reasoning about Imperfect Information Games}, booktitle = {Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence}, year = {2016}, pages = {1138-1144}, url = {https://staff.cdms.westernsydney.edu.au/~dongmo/personalWeb/papers/IJCAI-16_165.pdf} }
Jonathan Rubin, I.W.	Memory and Analogy in Game-Playing Agents [Abstract] [BibTeX]	2009	Workshop on Case-Based Reasoning for Computer Games at the International Conference on Case-Based Reasoning (ICCBR)	inproceedings	URL
Abstract: Abstract. We present our views and ideas about a possible approach to general game playing by utilising memory and analogy. We initially discuss the importance of memory in game playing agents. The forms that memory can take are examined and examples of successful agents who utilise memory are presented. Following this we focus on experience-based, lazy learners and justify why we believe they may be beneficial in a general game playing domain. Analogical reasoning is then introduced and its benefits considered. We conclude by formulating some example analogies and speculating how an experience-based, lazy learner could apply these to a general game playing environment.
BibTeX: @inproceedings{JonathanRubin2009, author = {Jonathan Rubin, Ian Watson}, title = {Memory and Analogy in Game-Playing Agents}, booktitle = {Workshop on Case-Based Reasoning for Computer Games at the International Conference on Case-Based Reasoning (ICCBR)}, year = {2009}, url = {http://www.cs.auckland.ac.nz/~jrub001/files/MemoryAndAnalogy_ICCBR9.pdf} }
Kaiser, Ł. & Stafiniak, Ł.	First-Order Logic with Counting for General Game Playing [Abstract] [BibTeX]	2011	Proceedings of the IJCAI-11 Workshop on General Game Playing (GIGA'11), pp. 85-90	inproceedings	URL
Abstract: General Game Players (GGPs) are programs which can play an arbitrary game given only its rules and the Game Descrip- tion Language (GDL) is a variant of Datalog used in GGP competitions to specify the rules. GDL inherits from Data- log the use of Horn clauses as rules and recursion, but it too requires stratiﬁcation and does not allow to use quantiﬁers. We present an alternative formalism for game descriptions which is based on ﬁrst-order logic (FO). States of the game are represented by relational structures, legal moves by struc- ture rewriting rules guarded by FO formulas, and the goals of the players by formulas which extend FO with counting. The advantage of our formalism comes from more explicit state representation and from the use of quantiﬁers in for- mulas. We show how to exploit existential quantiﬁcation in players’ goals to generate heuristics for evaluating positions in the game. The derived heuristics are good enough for a basic alpha-beta agent to win against state of the art GGP.
BibTeX: @inproceedings{Kaiser2011, author = {Łukasz Kaiser and Łukasz Stafiniak}, title = {First-Order Logic with Counting for General Game Playing}, booktitle = {Proceedings of the IJCAI-11 Workshop on General Game Playing (GIGA'11)}, year = {2011}, pages = {85-90}, url = {ijcai-11.iiia.csic.es/files/proceedings/GIGA-11-Proceedings.pdf} }
Kaiser, Ł. & Stafiniak, Ł.	Translating the Game Description Language to Toss [Abstract] [BibTeX]	2011	Proceedings of the IJCAI-11 Workshop on General Game Playing (GIGA'11), pp. 91-98	inproceedings	URL
Abstract: We show how to translate games deﬁned in the Game De- scription Language (GDL) into the Toss format. GDL is a variant of Datalog used to specify games in the General Game Playing Competition. Speciﬁcations in Toss are more declar- ative than in GDL and make it easier to capture certain use- ful game characteristics. The presented translation must thus detect structural properties of games which are not directly visible in the GDL speciﬁcation.
BibTeX: @inproceedings{Kaiser2011a, author = {Łukasz Kaiser and Łukasz Stafiniak}, title = {Translating the Game Description Language to Toss}, booktitle = {Proceedings of the IJCAI-11 Workshop on General Game Playing (GIGA'11)}, year = {2011}, pages = {91-98}, url = {ijcai-11.iiia.csic.es/files/proceedings/GIGA-11-Proceedings.pdf} }
Kaiser, D.M.	The Design and Implementation of a Successful General Game Playing Agent [Abstract] [BibTeX]	2007	FLAIRS Conference, pp. 110-115	inproceedings	URL
Abstract: General Game Playing is the problem of designing an agent capable of playing any previously unknown game when given only the rules. This paper describes the implementation architecture and design issues behind Ogre, a General Game Playing agent designed at Florida International University. Our main contribution is an innovative algorithm for automatically generating efficient evaluation functions for previously unfamiliar games. The system competed successfully at the second AAAI General Game Playing competition held at AAAI-06.
BibTeX: @inproceedings{Kaiser2007, author = {David M. Kaiser}, title = {The Design and Implementation of a Successful General Game Playing Agent}, booktitle = {FLAIRS Conference}, publisher = {AAAI Press}, year = {2007}, pages = {110-115}, url = {http://faculty.mdc.edu/dkaiser/papers/The%20Design%20and%20Impl3v4.pdf} }
Kaiser, D.M.	Automatic Feature Extraction for Autonomous General Game Playing Agents [Abstract] [BibTeX]	2007	Proceedings of the Sixth Intl. Joint Conf. on Autonomous Agents and Multiagent Systems	inproceedings	URL
Abstract: The General Game Playing (GGP) problem is concerned with developing systems capable of playing many different games, even games the system has never encountered before. Successful GGP agents must be able to extract relevant features from the formal game description and construct effective search heuristics. In this article, we present a procedure by which autonomous General Game Playing agents can generate effective and efficient search heuristics from the formal game description. The major aspect of our approach is an innovative technique to automatically extract critical features from the game structure. Our method has been incorporated into a fully implemented system that came in fourth place at the second General Game Playing Competition held at AAAI-06.
BibTeX: @inproceedings{Kaiser2007a, author = {David M. Kaiser}, title = {Automatic Feature Extraction for Autonomous General Game Playing Agents}, booktitle = {Proceedings of the Sixth Intl. Joint Conf. on Autonomous Agents and Multiagent Systems}, year = {2007}, url = {http://faculty.mdc.edu/dkaiser/papers/Automatic%20Feature%20Extraction%20v2.pdf} }
Kaiser, D.M.	The structure of games [Abstract] [BibTeX]	2007	School: Florida International University	phdthesis	URL
Abstract: Computer Game Playing has been an active area of research since Samuel's first Checkers player (Samuel 1959). Recently interest beyond the classic games of Chess and Checkers has led to competitions such as the General Game Playing competition, in which players have no beforehand knowledge of the games they are to play, and the Computer Poker Competition which force players to reason about imperfect information under conditions of uncertainty. The purpose of this dissertation is to explore the area of General Game Playing both specifically and generally. On the specific side, we describe the design and implementation of our General Game Playing system OGRE. This system includes an innovative method for feature extraction that helped it to achieve second and fourth place in two international General Game Playing competitions. On the more general side, we also introduce the Regular Game Language, which goes beyond current works to provide support for both stochastic and imperfect information games as well as the more traditional games.
BibTeX: @phdthesis{Kaiser2007b, author = {David M. Kaiser}, title = {The structure of games}, school = {Florida International University}, year = {2007}, url = {http://digitalcommons.fiu.edu/cgi/viewcontent.cgi?article=1002&context=etd} }
Khadem, M.S.	Simultaneous Move Games in General Game Playing [Abstract] [BibTeX]	2010	School: University of Alberta	mastersthesis	URL
Abstract: General Game Playing (GGP) deals with the design of players that are able to play any discrete, deterministic, complete information games. For many games like chess, designers develop a player using a specially designed algorithm and tune all the features of the algorithm to play the game as good as possible. However, a general game player knows nothing about the game that is about to be played. When the game begins, game description is given to the players and they should analyze it and decide on the best way to play the game. In this thesis, we focus on two-player constant-sum simultaneous move games in GGP and how this class of games can be handled. Rock-paper-scissors can be considered as a typical example of a simultaneous move game. We introduce the CFR algorithm to the GGP community for the first time and show its effectiveness in playing simultaneous move games. This is the first implementation of CFR outside the poker world. We also improve the UCT algorithm, which is the state of the art in GGP, to be more robust in simultaneous move games. In addition, we analyze how UCT performs in simultaneous move games and argue that it does not converge to a Nash equilibrium. We also compare the usage of UCT and CFR in this class of games. Finally, we discuss about the importance of opponent modeling and how a model of the opponent can be exploited by using CFR.
BibTeX: @mastersthesis{Khadem2010, author = {Mohammad Shafiei Khadem}, title = {Simultaneous Move Games in General Game Playing}, school = {University of Alberta}, year = {2010}, url = {http://hdl.handle.net/10048/880} }
Kirci, M., Schaeffer, J. & Sturtevant, N.	Feature Learning Using State Differences [Abstract] [BibTeX]	2009	Proceedings of the IJCAI-09 Workshop on General Game Playing (GIGA'09), pp. 35-42	inproceedings	URL
Abstract: The goal of General Game playing (GGP) can be described as designing computer programs that can play a variety of games when given a game description. Learning algorithms have not been an essential part of all successful GGP programs. This paper presents a feature learning approach, GIFL, for 2-player, alternating move games in GGP using state differences. The algorithm is simple, robust and improves the quality of play.
BibTeX: @inproceedings{Kirci2009, author = {Mesut Kirci and Jonathan Schaeffer and Nathan Sturtevant}, title = {Feature Learning Using State Differences}, booktitle = {Proceedings of the IJCAI-09 Workshop on General Game Playing (GIGA'09)}, year = {2009}, pages = {35-42}, url = {http://www.cs.ualberta.ca/~nathanst/papers/GGPfeatures.pdf} }
Kirci, M., Sturtevant, N.R. & Schaeffer, J.	A GGP Feature Learning Algorithm [Abstract] [BibTeX]	2011	KI Vol. 25(1), pp. 35-42	article	URL
Abstract: This paper presents a learning algorithm for two-player, alternating move GGP games. The Game Independent Feature Learning algorithm, GIFL, uses the differences in temporally-related states to learn patterns that are correlated with winning or losing a GGP game. These patterns are then used to inform the search. GIFL is simple, robust and improves the quality of play in the majority of games tested. GIFL has been successfully used in the GGP program Maligne.
BibTeX: @article{Kirci2011, author = {Mesut Kirci and Nathan R. Sturtevant and Jonathan Schaeffer}, title = {A GGP Feature Learning Algorithm}, journal = {KI}, year = {2011}, volume = {25}, number = {1}, pages = {35-42}, url = {http://web.cs.du.edu/~sturtevant/papers/FeatureLearning.pdf} }
Kissmann, P. & Edelkamp, S.	Instantiating General Games [Abstract] [BibTeX]	2009	Proceedings of the IJCAI-09 Workshop on General Game Playing (GIGA'09), pp. 43-50	inproceedings
Abstract: Driven by the success of current state-of-the-art planners and as a side product of improving the efficiency of playing general games, this paper provides a way to instantiate games specified in the game description language GDL. The static analyzer returns an instantiated game description in a format close to planner input. This bridge between general game playing and action planning technology is based on a multistage algorithm that translates the schematic knowledge representation language KIF into a grounded action-oriented planning domain definition language. To support multi-valued variable planning, a superset of all reachable grounded predicates is associated to a mutex group predicate encoding that minimizes the state vector during play.
BibTeX: @inproceedings{Kissmann2009, author = {Peter Kissmann and Stefan Edelkamp}, title = {Instantiating General Games}, booktitle = {Proceedings of the IJCAI-09 Workshop on General Game Playing (GIGA'09)}, year = {2009}, pages = {43-50} }
Kissmann, P. & Edelkamp, S.	Gamer, a General Game Playing Agent [Abstract] [BibTeX]	2011	KI Vol. 25(1), pp. 49-52	article	URL
Abstract: This work is concerned with our general game playing agent Gamer. In contrast to many other players, we do not only use a Prolog-like mechanism to infer knowledge about the current state and the available moves but instantiate the games to reduce the inference time in parallel UCT game tree search. Furthermore, we use the generated output to try to solve the games using symbolic search methods and thus play optimally.
BibTeX: @article{Kissmann2011, author = {Peter Kissmann and Stefan Edelkamp}, title = {Gamer, a General Game Playing Agent}, journal = {KI}, year = {2011}, volume = {25}, number = {1}, pages = {49-52}, url = {http://www.springerlink.com/content/y646p6603131k581/} }
Kissmann, P. & Edelkamp, S.	Instantiating General Games Using Prolog or Dependency Graphs [BibTeX]	2010	German Conference on Artificial Intelligence, pp. 255-262	inproceedings	DOI URL
BibTeX: @inproceedings{Kissmann2010, author = {Peter Kissmann and Stefan Edelkamp}, title = {Instantiating General Games Using Prolog or Dependency Graphs}, booktitle = {German Conference on Artificial Intelligence}, year = {2010}, pages = {255-262}, url = {http://fai.cs.uni-saarland.de/kissmann/publications/ki10-instantiator.pdf}, doi = {http://dx.doi.org/10.1007/978-3-642-16111-7_29} }
Koriche, F., Lagrue, S., Piette, É. & Tabary, Sé.	General game playing with stochastic CSP [BibTeX]	2016	Constraints Vol. 21, pp. 95-114	article	URL
BibTeX: @article{Koriche2016, author = {Frédéric Koriche and Sylvain Lagrue and Éric Piette and Séebastien Tabary}, title = {General game playing with stochastic CSP}, journal = {Constraints}, year = {2016}, volume = {21}, pages = {95--114}, url = {https://link.springer.com/content/pdf/10.1007/s10601-015-9199-5.pdf} }
Koriche, F., Lagrue, S., Piette, É. & Tabary, S.	Constraint-Based Symmetry Detection in General Game Playing [BibTeX]	2017	Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI-17, pp. 280-287	inproceedings	DOI URL
BibTeX: @inproceedings{Koriche2017, author = {Frédéric Koriche and Sylvain Lagrue and Éric Piette and Sébastien Tabary}, title = {Constraint-Based Symmetry Detection in General Game Playing}, booktitle = {Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI-17}, year = {2017}, pages = {280--287}, url = {https://doi.org/10.24963/ijcai.2017/40}, doi = {http://dx.doi.org/10.24963/ijcai.2017/40} }
Kostenko, A.	Calculating End Game Databases for General Game Playing [Abstract] [BibTeX]	2007	School: TU-Dresden	mastersthesis	URL
Abstract: The issue of end game database construction is known and well-studied in various specific gaming domains like Chess and Checkers. However with the arrival of the General Game Playing (GGP) challenge the automatic construction of end game databases attracted focus again. The current work presents a sound and complete algorithm for automated construction of end game databases within the GGP setting. The theoretical base for the algorithm rests on regression introduced in the Situation Calculus. Along with the theoretical base a sample implementation constructed on top of FLUX (a Fluent Calculus implementation) is presented.
BibTeX: @mastersthesis{Kostenko2007, author = {Arsen Kostenko}, title = {Calculating End Game Databases for General Game Playing}, school = {TU-Dresden}, year = {2007}, url = {http://www.inf.tu-dresden.de/content/institutes/ki/cl/study/assignments/download/Arsen_Kostenko_MSc.pdf} }
Kowalski, J. & Szykuła, M.	Game Description Language Compiler Construction [Abstract] [BibTeX]	2013	Proceedings of the Australasian Joint Conference on Artificial Intelligence	inproceedings	URL
Abstract: We describe a multilevel algorithm compiling a general game description in GDL into an optimized reasoner in a low level language. The aim of the reasoner is to eﬃciently compute game states and per- form simulations of the game. This is essential for many General Game Playing systems, especially if they use simulation-based approaches. Our compiler produces a faster reasoner than similar approaches used so far. The compiler is implemented as a part of the player Dumalion. Although we concentrate on compiling GDL, the developed methods can be applied to similar Prolog-like languages in order to speed up computations.
BibTeX: @inproceedings{Kowalski2013, author = {Kowalski, J. and Szykuła, M.}, title = {Game Description Language Compiler Construction}, booktitle = {Proceedings of the Australasian Joint Conference on Artificial Intelligence}, publisher = {Springer}, year = {2013}, url = {http://kot.rogacz.com/Science/Research/publications/AJCAI2013.pdf} }
Kuhlmann, G., Dresner, K. & Stone, P.	Automatic Heuristic Construction in a Complete General Game Player [Abstract] [BibTeX]	2006	Proceedings of the Twenty-First National Conference on Artificial Intelligence, pp. 1457-62	inproceedings	URL
Abstract: Computer game players are typically designed to play a single game: today's best chess-playing programs cannot play checkers, or even tic-tac-toe. General Game Playing is the problem of designing an agent capable of playing many different previously unseen games. The first AAAI General Game Playing Competition was held at AAAI 2005 in order to promote research in this area. In this article, we survey some of the issues involved in creating a general game playing system and introduce our entry to that event. The main feature of our approach is a novel method for automatically constructing effective search heuristics based on the formal game description. Our agent is fully implemented and tested in a range of different games.
BibTeX: @inproceedings{Kuhlmann2006, author = {Gregory Kuhlmann and Kurt Dresner and Peter Stone}, title = {Automatic Heuristic Construction in a Complete General Game Player}, booktitle = {Proceedings of the Twenty-First National Conference on Artificial Intelligence}, year = {2006}, pages = {1457-62}, url = {http://www.cs.utexas.edu/~pstone/Papers/bib2html-links/AAAI06-ggp.pdf} }
Kuhlmann, G. & Stone, P.	Graph-Based Domain Mapping for Transfer Learning in General Games [Abstract] [BibTeX]	2007	Proceedings of The Eighteenth European Conference on Machine Learning	inproceedings	URL
Abstract: A general game player is an agent capable of taking as input a description of a game's rules in a formal language and proceeding to play without any subsequent human input. To do well, an agent should learn from experience with past games and transfer the learned knowledge to new problems. We introduce a graph-based method for identifying previously encountered games and prove its robustness formally. We then describe how the same basic approach can be used to identify similar but non-identical games. We apply this technique to automate domain mapping for value function transfer and speed up reinforcement learning on variants of previously played games. Our approach is fully implemented with empirical results in the general game playing system.
BibTeX: @inproceedings{Kuhlmann2007, author = {Gregory Kuhlmann and Peter Stone}, title = {Graph-Based Domain Mapping for Transfer Learning in General Games}, booktitle = {Proceedings of The Eighteenth European Conference on Machine Learning}, year = {2007}, url = {http://www.cs.utexas.edu/~pstone/Papers/bib2html-links/ECML07-rulegraphs.pdf} }
Kuhlmann, G.J.	Automated Domain Analysis and Transfer Learning in General Game Playing [Abstract] [BibTeX]	2010	School: University of Texas at Austin	phdthesis	URL
Abstract: Creating programs that can play games such as chess, checkers, and backgammon, at a high level has long been a challenge and benchmark for AI. Computer game playing is arguably one of AI's biggest success stories. Several game playing systems developed in the past, such as Deep Blue, Chinook and TD-Gammon have demonstrated competitive play against the top human players. However, such systems are limited in that they play only one particular game and they typically must be supplied with game-specific knowledge. While their performance is impressive, it is difficult to determine if their success is due to generally applicable techniques or due to the human game analysis. A general game player is an agent capable of taking as input a description of a game's rules and proceeding to play without any subsequent human input. In doing so, the agent, rather than the human designer, is responsible for the domain analysis. Developing such a system requires the integration of several AI components, including theorem proving, feature discovery, heuristic search, and machine learning. In the general game playing scenario, the player agent is supplied with a game's rules in a formal language, prior to match play. This thesis contributes a collection of general methods for analyzing these game descriptions to improve performance. Prior work on automated domain analysis has focused on generating heuristic evaluation functions for use in search. The thesis builds upon this work by introducing a novel feature generation method. Also, I introduce a method for generating and comparing simple evaluation functions based on these features. I describe how more sophisticated evaluation functions can be generated through learning. Finally, this thesis demonstrates the utility of domain analysis in facilitating knowledge transfer between games for improved learning speed. The contributions are fully implemented with empirical results in the general game playing system.
BibTeX: @phdthesis{Kuhlmann2010, author = {Gregory John Kuhlmann}, title = {Automated Domain Analysis and Transfer Learning in General Game Playing}, school = {University of Texas at Austin}, year = {2010}, url = {http://repositories.lib.utexas.edu/handle/2152/ETD-UT-2010-08-1975} }
Kulick, J., Block, M. & Rojas, R.	General Game Playing mit stochastischen Spielen [Abstract] [BibTeX]	2009		techreport	URL
Abstract: In der Game Description Language lassen sich rundenbasierte Spiele mit vollständiger Information ohne stochastische Ereignisse beschreiben. Obwohl die Sprache erst 2005 entwickelt wurde, hat sie eine hohe Akzeptanz innerhalb der Wissenschaftgemeinde. Es werden Programme entwickelt, die aus den Spielbeschreibungen Strategien ableiten und die Spiele erfolgreich spielen. In dieser Arbeit wird eine Erweiterung der Sprache GDL vorgestellt, mit der nun auch Spiele mit stochastischen Elementen beschrieben und gespielt werden können.
BibTeX: @techreport{Kulick2009, author = {Johannes Kulick and Marco Block and Raul Rojas}, title = {General Game Playing mit stochastischen Spielen}, year = {2009}, url = {http://www.inf.fu-berlin.de/publications/techreports/tr2009/B-09-08/B-09-08.pdf} }
Levinson, R.A.	General Game-Playing and Reinforcement Learning [Abstract] [BibTeX]	1996	Computational Intelligence Vol. 12(1), pp. 155-176	article	URL
Abstract: This paper provides a blueprint for the development of a fully domain-independent single-agent and multiagent heuristic search system. It gives a graph-theoretic representation of search problems based on conceptual graphs and outlines two different learning systems. One, an “informed learner”, makes use of the graph-theoretic definition of a search problem or game in playing and adapting to a game in the given environment. The other, a “blind learner”, is not given access to the rules of a domain but must discover and then exploit the underlying mathematical structure of a given domain. Relevant work of others is referenced within the context of the blueprint. To illustrate further how one might go about creating general game-playing agents, we show how we can generalize the understanding obtained with the Morph chess system to all games involving the interactions of abstract mathematical relations. A monitor for such domains has been developed, along with an implementation of a blind and informed learning system known as Morphll. Performance results with MorphK are preliminary but encouraging and provide a few more data points with which to understand and evaluate the blueprint.
BibTeX: @article{Levinson1996, author = {Robert A. Levinson}, title = {General Game-Playing and Reinforcement Learning}, journal = {Computational Intelligence}, year = {1996}, volume = {12}, number = {1}, pages = {155-176}, note = {Special Issue on Games: Structure and Learning}, url = {http://onlinelibrary.wiley.com/doi/10.1111/j.1467-8640.1996.tb00257.x/abstract} }
Love, N., Hinrichs, T., Haley, D., Schkufza, E. & Genesereth, M.	General Game Playing: Game Description Language Specification [BibTeX]	2008		techreport	URL
BibTeX: @techreport{Love2008, author = {Nathaniel Love and Timothy Hinrichs and David Haley and Eric Schkufza and Michael Genesereth}, title = {General Game Playing: Game Description Language Specification}, year = {2008}, note = {most recent version should be available at http://games.stanford.edu/}, url = {http://games.stanford.edu/language/spec/gdl_spec_2008_03.pdf} }
Méhat, J. & Cazenave, T.	A Parallel General Game Player [Abstract] [BibTeX]	2011	KI Vol. 25(1), pp. 43-47	article	URL
Abstract: We have parallelized our general game player Ary on a cluster of computers. We propose multiple parallelization algorithms. For the sake of simplicity all our algorithms have processes that run independently and that join their results at the end of the thinking time in order to choose a move. Parallelization works very well for checkers, quite well for other two player sequential move games and not at all for a few other games.
BibTeX: @article{Mehat2011, author = {Jean Méhat and Tristan Cazenave}, title = {A Parallel General Game Player}, journal = {KI}, year = {2011}, volume = {25}, number = {1}, pages = {43-47}, url = {http://www.springerlink.com/content/a83gt77455j377k8/} }
Méhat, J. & Cazenave, T.	Combining UCT and Nested Monte Carlo Search for Single-Player General Game Playing [Abstract] [BibTeX]	2010	IEEE Transactions on Computational Intelligence and AI in Games Vol. 2(4), pp. 271-277	article	URL
Abstract: Monte-Carlo tree search has recently been very successful for game playing particularly for games where the evaluation of a state is difficult to compute, such as Go or General Games. We compare Nested Monte-Carlo Search (NMC), Upper Confidence bounds for Trees (UCT-T), UCT with transposition tables (UCT+T) and a simple combination of NMC and UCT+T (MAX) on single-player games of the past GGP competitions. We show that transposition tables improve UCT and that MAX is the best of these four algorithms. Using UCT+T, the program Ary won the 2009 GGP competition. MAX and NMC are slight improvements over this 2009 version.
BibTeX: @article{Mehat2010, author = {Jean Méhat and Tristan Cazenave}, title = {Combining UCT and Nested Monte Carlo Search for Single-Player General Game Playing}, journal = {IEEE Transactions on Computational Intelligence and AI in Games}, year = {2010}, volume = {2}, number = {4}, pages = {271-277}, url = {http://www.lamsade.dauphine.fr/~cazenave/papers/ggp2009.pdf} }
Möller, M., Schneider, M., Wegner, M. & Schaub, T.	Centurio, a General Game Player: Parallel, Java- and ASP-based [Abstract] [BibTeX]	2011	KI Vol. 25(1), pp. 17-24	article	URL
Abstract: We present the General Game Playing system Centurio. Centurio is a Java-based player featuring different strategies based on Monte Carlo Tree Search extended by techniques borrowed from Upper Confidence bounds applied to Trees as well as Answer Set Programming (for single-player games). Centurio’s Monte Carlo Tree Search is accomplished in a massively parallel way by means of multi-threading as well as cluster-computing. Another major feature of Centurio is its compilation of game descriptions, states, and state manipulations into Java, yielding an edge over existing Prolog-based approaches. Centurio is open source software freely available via the web.
BibTeX: @article{Moller2011, author = {Maximilian Möller and Marius Schneider and Martin Wegner and Torsten Schaub}, title = {Centurio, a General Game Player: Parallel, Java- and ASP-based}, journal = {KI}, year = {2011}, volume = {25}, number = {1}, pages = {17-24}, url = {http://www.springerlink.com/content/e83797479364n584/} }
Mandziuk, J., Ong, Y.S. & Waledzik, K.	Multi-Game Playing - a Challenge for Computational Intelligence [Abstract] [BibTeX]	2013	IEEE Symposium Series on Computational Intelligence (SSCI)	inproceedings	URL
Abstract: In this paper, we deal with the topic of multi-game playing, i.e. creating agents able to autonomously learn to play any game within some arbitrarily deﬁned genre. We describe the motivation for research in this particular area and brieﬂy summarize the most important undertakings. Subsequently, we present a relatively young multi-game playing platform, called the General Game Playing (GGP) and our approach to development of GGP agent followed by some experimental results.
BibTeX: @inproceedings{Mandziuk2013, author = {Jacek Mandziuk and Yew Soon Ong and Karol Waledzik}, title = {Multi-Game Playing - a Challenge for Computational Intelligence}, booktitle = {IEEE Symposium Series on Computational Intelligence (SSCI)}, year = {2013}, url = {http://www.mini.pw.edu.pl/~kwaledzik/wp/wp-content/uploads/research/177-GGP-challenge.pdf} }
Manuel, S., Rajaratnam, D. & Thielscher, M.	Encoding Epistemic Strategies for General Game Playing [BibTeX]	2019	Vol. 11670Proceedings of the Pacific Rim International Conference onArtificial Intelligence, pp. 555-567	inproceedings	URL
BibTeX: @inproceedings{Manuel2019, author = {Shawn Manuel and David Rajaratnam and Michael Thielscher}, title = {Encoding Epistemic Strategies for General Game Playing}, booktitle = {Proceedings of the Pacific Rim International Conference onArtificial Intelligence}, publisher = {Springer}, year = {2019}, volume = {11670}, pages = {555--567}, url = {http://cgi.cse.unsw.edu.au/~mit/Papers/PRICAI19.pdf} }
Méhat, J. & Cazenave, T.	Tree Parallelization of Ary on a Cluster [Abstract] [BibTeX]	2011	Proceedings of the IJCAI-11 Workshop on General Game Playing (GIGA'11), pp. 39-43	inproceedings	URL
Abstract: We investigate the beneﬁts of Tree Parallelization on a cluster for our General Game Playing program Ary. As the Tree parallelization of Monte-Carlo Tree Search works well when playouts are slow, it is of interest for General Game Playing programs, as the interpretation of game description takes a large proportion of the computing time, when compared with program designed to play speciﬁc games. We show that the tree parallelization does provide an advantage, but that it decreases for common games as the number of subplayers grows beyond 10.
BibTeX: @inproceedings{Mehat2011a, author = {Jean Méhat and Tristan Cazenave}, title = {Tree Parallelization of Ary on a Cluster}, booktitle = {Proceedings of the IJCAI-11 Workshop on General Game Playing (GIGA'11)}, year = {2011}, pages = {39-43}, url = {ijcai-11.iiia.csic.es/files/proceedings/GIGA-11-Proceedings.pdf} }
Mehat, J. & Vittaut, J.-N.	Online Adjustment of Tree Search for GGP [Abstract] [BibTeX]	2013	Proceedings of the IJCAI-13 Workshop on General Game Playing (GIGA'13), pp. 63-69	inproceedings	URL
Abstract: We present an adaptive method that enables a General Game Player using Monte-Carlo Tree Search to adapt its use of RAVE to the game it plays. This adaptation is done with a comparison of the UCT and RAVE prediction for moves, that are based on previous playout results. We show that it leads to results that are equivalent to those obtained with a hand tuned choice of RAVE usage and better than a ﬁtfor-all ﬁxed choice on simple ad hoc synthetic games. This is well adapted to the domain of General Game Playing where the player cannot be tuned for the characteristics of the game it will play before the beginning of a match.
BibTeX: @inproceedings{Mehat2013, author = {Jean Mehat and Jean-Noel Vittaut}, title = {Online Adjustment of Tree Search for GGP}, booktitle = {Proceedings of the IJCAI-13 Workshop on General Game Playing (GIGA'13)}, year = {2013}, pages = {63-69}, url = {http://giga13.ru.is/GIGA-13-Proceedings.pdf} }
Michulke, D.	Neural Networks for High-Resolution State Evaluation in General Game Playing [Abstract] [BibTeX]	2011	Proceedings of the IJCAI-11 Workshop on General Game Playing (GIGA'11), pp. 31-37	inproceedings	URL
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.
BibTeX: @inproceedings{Michulke2011, author = {Daniel Michulke}, title = {Neural Networks for High-Resolution State Evaluation in General Game Playing}, booktitle = {Proceedings of the IJCAI-11 Workshop on General Game Playing (GIGA'11)}, year = {2011}, pages = {31-37}, url = {http://www.general-game-playing.de/downloads/GIGA11_Neural_Networks.pdf} }
Michulke, D.	Evaluation Functions in General Game Playing [Abstract] [BibTeX]	2012	School: Technische Universität Dresden	phdthesis
Abstract: While in traditional computer game playing agents were designed solely for the purpose of playing one single game, General Game Playing is concerned with agents capable of playing classes of games. Given the game's rules and a few minutes time, the agent is supposed to play any game of the class and eventually win it. Since the game is unknown beforehand, previously optimized data structures or human-provided features are not applicable. Instead, the agent must derive a strategy on its own. One approach to obtain such a strategy is to analyze the game rules and create a state evaluation function that can be subsequently used to direct the agent to promising states in the match. In this thesis we will discuss existing methods and present a general approach on how to construct such an evaluation function. Each topic is discussed in a modular fashion and evaluated along the lines of quality and efficiency, resulting in a strong agent.
BibTeX: @phdthesis{Michulke2012, author = {Daniel Michulke}, title = {Evaluation Functions in General Game Playing}, school = {Technische Universität Dresden}, year = {2012} }
Michulke, D.	Heuristic Interpretation of Predicate Logic Expressions in General Game Playing [Abstract] [BibTeX]	2011	Proceedings of the IJCAI-11 Workshop on General Game Playing (GIGA'11), pp. 61-68	inproceedings	URL
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.
BibTeX: @inproceedings{Michulke2011a, author = {Daniel Michulke}, title = {Heuristic Interpretation of Predicate Logic Expressions in General Game Playing}, booktitle = {Proceedings of the IJCAI-11 Workshop on General Game Playing (GIGA'11)}, year = {2011}, pages = {61-68}, url = {http://www.general-game-playing.de/downloads/GIGA11_Heuristic_Interpretation.pdf} }
Michulke, D. & Schiffel, S.	Distance Features for General Game Playing [Abstract] [BibTeX]	2011	Proceedings of the IJCAI-11 Workshop on General Game Playing (GIGA'11), pp. 7-14	inproceedings	URL
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.
BibTeX: @inproceedings{Michulke2011b, author = {Daniel Michulke and Stephan Schiffel}, title = {Distance Features for General Game Playing}, booktitle = {Proceedings of the IJCAI-11 Workshop on General Game Playing (GIGA'11)}, year = {2011}, pages = {7-14}, url = {http://www.general-game-playing.de/downloads/GIGA11_Distance_Features.pdf} }
Michulke, D. & Schiffel, S.	Admissible Distance Heuristics for General Games [Abstract] [BibTeX]	2013	Vol. 358Agents and Artificial Intelligence, pp. 188-203	incollection	DOI URL
Abstract: A general game player is a program that is able to play arbitrary games well given only their rules. One of the main problems of general game playing is the automatic construction of a good evaluation function for these games. Distance features are an important aspect of such an evaluation function, measuring, e.g., the distance of a pawn towards the promotion rank in chess or the distance between Pac-Man and the ghosts. However, current distance features for General Game Playing are often based on too specific detection patterns to be generally applicable, and they often apply a uniform Manhattan distance regardless of the move patterns of the objects involved. In addition, the existing distance features do not provide proven bounds on the actual distances. In this paper, we present a method to automatically construct distance heuristics directly from the rules of an arbitrary game. The presented method is not limited to specific game structures, such as Cartesian boards, but applicable to all structures in a game. Constructing the distance heuristics from the game rules ensures that the construction does not depend on the size of the state space, but only on the size of the game description which is exponentially smaller in general. Furthermore, we prove that the constructed distance heuristics are admissible, i.e., provide proven lower bounds on the actual distances. We demonstrate the effectiveness of our approach by integrating the distance heuristics in an evaluation function of a general game player and comparing the performance with a state-of-the-art player.
BibTeX: @incollection{Michulke2013, author = {Michulke, Daniel and Schiffel, Stephan}, title = {Admissible Distance Heuristics for General Games}, booktitle = {Agents and Artificial Intelligence}, publisher = {Springer Berlin Heidelberg}, year = {2013}, volume = {358}, pages = {188-203}, url = {http://dx.doi.org/10.1007/978-3-642-36907-0_13}, doi = {http://dx.doi.org/10.1007/978-3-642-36907-0_13} }
Michulke, D. & Schiffel, S.	Distance Features for General Game Playing Agents [Abstract] [BibTeX]	2012	Proceedings of the 4th International Conference on Agents and Artificial Intelligence (ICAART)	inproceedings	URL
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.
BibTeX: @inproceedings{Michulke2012a, author = {Daniel Michulke and Stephan Schiffel}, title = {Distance Features for General Game Playing Agents}, booktitle = {Proceedings of the 4th International Conference on Agents and Artificial Intelligence (ICAART)}, year = {2012}, url = {http://www.general-game-playing.de/downloads/ICAART12_Distance_Features.pdf} }
Michulke, D. & Schiffel, S.	Matt bei "Vier gewinnt" [Abstract] [BibTeX]	2009	c't Vol. 1, pp. 174-181	article	URL
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.
BibTeX: @article{Michulke2009, author = {Daniel Michulke and Stephan Schiffel}, title = {Matt bei "Vier gewinnt"}, journal = {c't}, year = {2009}, volume = {1}, pages = {174-181}, url = {https://www.heise.de/artikel-archiv/ct/2009/1/174_General-Game-Playing-Universelle-Spielprogramme} }
Michulke, D. & Thielscher, M.	Neural Networks for State Evaluation in General Game Playing [Abstract] [BibTeX]	2009	Proceedings of the European Conference on Machine Learning (EMCL), pp. 95-110	inproceedings	URL
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.
BibTeX: @inproceedings{Michulke2009a, author = {Daniel Michulke and Michael Thielscher}, title = {Neural Networks for State Evaluation in General Game Playing}, booktitle = {Proceedings of the European Conference on Machine Learning (EMCL)}, year = {2009}, pages = {95-110}, url = {http://www1.inf.tu-dresden.de/~mit/publications/conferences/ECML09.pdf} }
Muggleton, S., Paes, A., Carlos, VS. & Zaverucha, G.	Chess Revision: Acquiring the Rules of Chess Variants through Theory Revision from Examples [Abstract] [BibTeX]	2009	Proceedings of the IJCAI-09 Workshop on General Game Playing (GIGA'09), pp. 51-58	inproceedings
Abstract: Games are a very popular testbed for machine learning systems, mainly because they require a focus on intelligent reasoning. The rules of a game can be meaningfully represented using the expressiveness of first-order logic. Thus, Inductive Logic Programming systems can be used to induce a classifier of such a game. On the other hand, quite often slightly different games are derived from a base game. One of the best such examples is the game of Chess, which has inspired the creation of different variants, ranging from faster to more challenging or to regional versions of chess. As the knowledge acquisition is a difficult, time consuming and error prone task, if a classifier of the standard chess had been obtained, one should be able to take advantage of that as starting point to obtain a classifier of different variants. This can be done using theory revision systems, which start from an initial theory and modify it from a set of examples, so that the final modified theory correctly represent them. In this paper we present a framework for obtaining a classifier of chess variants using Theory Revision from Examples. Preliminary experimental results show the effectiveness of our approach.
BibTeX: @inproceedings{Muggleton2009, author = {Stephen Muggleton and Aline Paes and Vıtor Santos Carlos and Gerson Zaverucha}, title = {Chess Revision: Acquiring the Rules of Chess Variants through Theory Revision from Examples}, booktitle = {Proceedings of the IJCAI-09 Workshop on General Game Playing (GIGA'09)}, year = {2009}, pages = {51-58} }
Okimoto, T.	General Game Playing using Automatically Generated Evaluation Functions [Abstract] [BibTeX]	2008	School: University of Freiburg	mastersthesis	URL
Abstract: A General Game Playing System is one that can accept a formal definition of a game and play the game effectively without human intervention. Unlike specialized game players, general game players do not rely on algorithms designed in advance for specific games, and they are able to play different kinds of games. The purpose of this work is to develop a General Game Playing System based on the Java reference player Jocular that uses automatically generated evaluation functions to guide the exploration of the game tree. The inference of the evaluation function given the game description should be based on the fuzzy logic approach used in the Fluxplayer system. Experimenting with other distance heuristics would be interesting as well. The resulting system should be evaluated against other General Game Playing Systems and possibly against human players on a number of benchmark games available online.
BibTeX: @mastersthesis{Okimoto2008, author = {Tenda Okimoto}, title = {General Game Playing using Automatically Generated Evaluation Functions}, school = {University of Freiburg}, year = {2008}, url = {http://www.informatik.uni-freiburg.de/~ki/theses/diploma.html} }
Pell, B.	A Strategic Metagame Player for General Chess-Like Games [Abstract] [BibTeX]	1996	Computational Intelligence Vol. 12, pp. 177-198	article	URL
Abstract: This paper introduces METAGAMER, the first program designed within the paradigm of Meta-Game Playing. This programs plays Metagame in the class of symmetric chess-like games, which includes chess, Chinese-chess, checkers, draughts, and Shogi. METAGAMER takes as input the rules of a specific game and analyses those rules to construct for that game an efficient representation and an evaluation function, for use by a generic search engine. The strategic analysis performed by METAGAMER relates a set of general knowledge sources to the details of the particular game. Amonge other properties, this analysis determines the relative value of the different pieces in a given game. Although METAGAMER does not learn from experience, the values resulting from its analysis are qualitatively similar to values used by experts on known games, and are sufficiont to produce competitive perfomance the first time METAGAMER actually plays each new game. Besides being the first Metagame-playing program, this is the first program to have derived useful piece values directly from analysis of the rules of different games. This paper describes the knowledge implemented in METAGAMER, illustrates the piece values METAGAMER derives for chess and checkers, and discusses experiments with METAGAMER on both existing and newly generated games.
BibTeX: @article{Pell1996, author = {Barney Pell}, title = {A Strategic Metagame Player for General Chess-Like Games}, journal = {Computational Intelligence}, year = {1996}, volume = {12}, pages = {177-198}, url = {http://www.barneypell.com/papers/metagamer-cij.pdf} }
Pell, B.	Strategy generation and evaluation for meta-game playing [Abstract] [BibTeX]	1993	School: University of Cambridge	phdthesis	URL
Abstract: Meta-Game Playing (Metagame) is a new paradigm for research in game-playing in which we design programs to take in the rules of unknown games and play those games without human assistance. Strong performance in this new paradigm is evidence that the program, instead of its human designer has performed the analysis of each specific game. SCL- Metagame is a concrete Metagame research problem based around the class of symmetric chess-like games. The class includes the games of chess, draughts, noughts and crosses, Chinese-chess, and Shogi. An implemented game generator produces new games in this class, some of which are objects of interest in their own right.; METAGAMER is a program that plays SCL-Metagame. The program takes as input the rules of a specific game and analyses those rules to construct for that game an efficient representation and an evaluation function, both for use with a generic search engine. The strategic analysis performed by the program relates a set of general knowledge sources to the details of the particular game. Among other properties, this analysis determines the relative value of the different pieces in a given game. Although METAGAMER does not learn from experience, the values resulting from its analysis are qualitatively similar to values used by experts on known games, and are sufficient to produce competitive performance the first time the program actually plays each game it is given.; This appears to be the first program to have derived useful piece values directly from analysis of the rules of different games. Experiments show that the knowledge implemented in METAGAMER is useful on games unknown to its programmer in advance of the competition and make it seem likely that future programs which incorporate learning and more sophisticated active-analysis techniques will have a demonstrable competitive advantage on this new problem. When playing the known games of chess and checkers against humans and specialised programs, METAGAMER has derived from more general principles some strategies which are familiar to players of those games and which are hard-wired in many game-specific programs.
BibTeX: @phdthesis{Pell1993, author = {Barney Pell}, title = {Strategy generation and evaluation for meta-game playing}, publisher = {Cambridge [Cambridgeshire] :University of Cambridge, Computer Laboratory,}, school = {University of Cambridge}, year = {1993}, url = {http://www.barneypell.com/papers/pell-thesis.pdf} }
Pell, B.	Logic programming for general game-playing [Abstract] [BibTeX]	1993	(UCAM-CL-TR-302)	techreport	URL
Abstract: Meta-Game Playing is a new approach to games in Artificial Intelligence, where we construct programs to play new games in a well-defined class, which are output by an automatic game generator. As the specific games to be played are not known in advance, a degree of human bias is eliminated, and playing programs are required to perform any game-specific optimisations without human assistance. The attempt to construct a general game-playing program is made difficult by the opposing goals of generality and efficiency. This paper shows how application of standard techniques in logic-programming (abstract interpretation and partial evaluation) makes it possible to achieve both of these goals. Using these techniques, we can represent the semantics of a large class of games in a general and declarative way, but then have the program transform this representation into a more efficient version once it is presented with the rules of a new game. This process can be viewed as moving some of the responsibility for game analysis (that concerned with efficiency) from the researcher to the program itself.
BibTeX: @techreport{Pell1993a, author = {Barney Pell}, title = {Logic programming for general game-playing}, year = {1993}, number = {UCAM-CL-TR-302}, url = {http://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-302.ps.gz} }
Pell, B.	METAGAME in Symmetric Chess-Like Games [BibTeX]	1992	Heuristic Programming in Artificial Intelligence 3 -- The Third Computer Olympiad	article	URL
BibTeX: @article{Pell1992, author = {Barney Pell}, title = {METAGAME in Symmetric Chess-Like Games}, journal = {Heuristic Programming in Artificial Intelligence 3 -- The Third Computer Olympiad}, year = {1992}, url = {http://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-277.ps.gz} }
Pitrat, J.	Realization of a general game-playing program [BibTeX]	1968	IFIP Congress, pp. 1570-1574	inproceedings
BibTeX: @inproceedings{Pitrat1968, author = {Jacques Pitrat}, title = {Realization of a general game-playing program}, booktitle = {IFIP Congress}, year = {1968}, pages = {1570-1574} }
Quenault, M. & Cazenave, T.	Extended General Gaming Model [Abstract] [BibTeX]	2007	Computer Games Workshop, pp. 195-204	inproceedings	URL
Abstract: General Gaming is a field of research on systems that can manage various game descriptions and play them effectively. These systems, unlike specialized ones, must deal with various kinds of games and cannot rely on any kind of game algorithms designed upstream, such as DEEPER BLUE ones. This field is currently mainly restricted to complete-information board games. Given the lack of more various games in the field of General Gaming, we propose in this article a very open functional model and its tested implementation. This model is able to bring together on the same engine both card games and board games, both complete- and incomplete-information games, both deterministic and chance games.
BibTeX: @inproceedings{Quenault2007, author = {M. Quenault and T. Cazenave}, title = {Extended General Gaming Model}, booktitle = {Computer Games Workshop}, year = {2007}, pages = {195-204}, url = {http://www.lamsade.dauphine.fr/~cazenave/papers/extendedggmodel.pdf} }
Rajaratnam, D. & Thielscher, M.	Execution Monitoring as Meta-Games for General Game-Playing Robots [BibTeX]	2015	Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), pp. 3178-3185	inproceedings	URL
BibTeX: @inproceedings{Rajaratnam2015, author = {David Rajaratnam and Michael Thielscher}, title = {Execution Monitoring as Meta-Games for General Game-Playing Robots}, booktitle = {Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI)}, publisher = {AAAI Press}, year = {2015}, pages = {3178--3185}, url = {http://cgi.cse.unsw.edu.au/~mit/Papers/IJCAI15.pdf} }
Rauber, T., Kissmann, P. & Hoffmann, Jö.	Translating Single-Player GDL into PDDL [Abstract] [BibTeX]	2013	KI 2013: Advances in Artificial Intelligence, pp. 188-199	incollection	URL
Abstract: In the single-agent case general game playing and action planning are two related topics, so that one might hope to use the established planners to improve the handling of general single-player games. However, both come with their own description language, GDL and PDDL, respectively. In this paper we propose a way to translate single-player games described in GDL to PDDL planning tasks and provide an evaluation on a wide range of single-player games, comparing the efficiency of grounding and solving the games in the translated and in the original format.
BibTeX: @incollection{Rauber2013, author = {Thorsten Rauber and Peter Kissmann and Jörg Hoffmann}, title = {Translating Single-Player GDL into PDDL}, booktitle = {KI 2013: Advances in Artificial Intelligence}, publisher = {Springer}, year = {2013}, pages = {188-199}, url = {http://link.springer.com/chapter/10.1007%2F978-3-642-40942-4_17} }
Reisinger, J., Bahceci, E., Karpov, I. & Miikkulainen, R.	Coevolving Strategies for General Game Playing [Abstract] [BibTeX]	2007	IEEE Symposium on Computational Intelligence and Games, pp. 320-327	inproceedings	URL
Abstract: The General Game Playing Competition poses a unique challenge for Artificial Intelligence. To be successful, a player must learn to play well in a limited number of example games encoded in first-order logic and then generalize its game play to previously unseen games with entirely different rules. Because good opponents are usually not available, learning algorithms must come up with plausible opponent strategies in order to benchmark performance. One approach to simultaneously learning all player strategies is coevolution. This paper presents a coevolutionary approach using NeuroEvolution of Augmenting Topologies to evolve populations of game state evaluators. This approach is tested on a sample of games from the General Game Playing Competition and shown to be effective: It allows the algorithm designer to minimize the amount of domain knowledge built into the system, which leads to more general game play and allows modeling opponent strategies efficiently. Furthermore, the General Game Playing domain proves to be a powerful tool for developing and testing coevolutionary methods.
BibTeX: @inproceedings{Reisinger2007, author = {Joseph Reisinger and Erkin Bahceci and Igor Karpov and Risto Miikkulainen}, title = {Coevolving Strategies for General Game Playing}, booktitle = {IEEE Symposium on Computational Intelligence and Games}, year = {2007}, pages = {320-327}, url = {http://ieeexplore.ieee.org/iel5/4219012/4219013/04219060.pdf?isnumber=4219013&prod=CNF&arnumber=4219060&arSt=320&ared=327&arAuthor=Reisinger%2C+J.%3B+Bahceci%2C+E.%3B+Karpov%2C+I.%3B+Miikkulainen%2C+R.} }
Richards, M. & Amir, E.	Information Set Sampling for General Imperfect Information Positional Games [BibTeX]	2009	Proceedings of the IJCAI-09 Workshop on General Game Playing (GIGA'09), pp. 59-66	inproceedings
BibTeX: @inproceedings{Richards2009, author = {Mark Richards and Eyal Amir}, title = {Information Set Sampling for General Imperfect Information Positional Games}, booktitle = {Proceedings of the IJCAI-09 Workshop on General Game Playing (GIGA'09)}, year = {2009}, pages = {59-66} }
Romero, J., Saffidine, A. & Thielscher, M.	Solving the Inferential Frame Problem in the General Game Description Language [Abstract] [BibTeX]	2014	Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence	inproceedings	URL
Abstract: The Game Description Language GDL is the standard input language for general game-playing systems. While players can gain a lot of traction by an efficient inference algorithm for GDL, state-of-the-art reasoners suffer from a variant of a classical KR problem, the inferential frame problem. We present a method by which general game players can transform any given game description into a representation that solves this problem. Our experimental results demonstrate that with the help of automatically generated domain knowledge, a significant speedup can thus be obtained for the majority of the game descriptions from the AAAI competition.
BibTeX: @inproceedings{Romero2014, author = {Javier Romero and Abdallah Saffidine and Michael Thielscher}, title = {Solving the Inferential Frame Problem in the General Game Description Language}, booktitle = {Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence}, publisher = {AAAI Press}, year = {2014}, url = {http://cse.unsw.edu.au/~mit/Papers/AAAI14.pdf} }
Ruan, J., van der Hoek, W. & Wooldridge, M.	Verification of Games in the Game Description Language [Abstract] [BibTeX]	2009	Journal of Logic and Computation Vol. 19(4), pp. 1127-1156	article	DOI URL
Abstract: The Game Description Language (GDL) is a special purpose declarative language for defining games. GDL is used in the AAAI General Game Playing Competition, which tests the ability of computer programs to play games in general, rather than just the ability to play a specific game. Participants in the competition are provided with a previously unknown game specified in GDL, and are required to dynamically and autonomously determine how best to play this game. Recently, there has been much interest in the use of strategic cooperation logics for reasoning about game-like scenarios—the Alternating-time Temporal Logic (ATL) of Alur, Henzinger, and Kupferman is perhaps the best known example. Such logics are speciﬁcally intended to support reasoning about game-theoretic properties of multi-agent systems. In short, the aim of this article is to make a concrete link between ATL and GDL, with the ultimate goal of using ATL to reason about GDL-speciﬁed games. We make the following contributions. First, we demonstrate that GDL can be understood as a speciﬁcation language for ATL models, and prove that the problem of interpreting ATL formulae over propositional GDL descriptions is EXPTIME-complete. Second, we use ATL to characterize a class of ‘fair playability’ conditions, which might or might not hold of various games.
BibTeX: @article{Ruan2009, author = {Ji Ruan and Wiebe van der Hoek and Michael Wooldridge}, title = {Verification of Games in the Game Description Language}, journal = {Journal of Logic and Computation}, year = {2009}, volume = {19}, number = {4}, pages = {1127-1156}, url = {http://www.csc.liv.ac.uk/~mjw/pubs/jlc2009a.pdf}, doi = {http://dx.doi.org/10.1093/logcom/exp039} }
Ruan, J. & Thielscher, M.	On the Comparative Expressiveness of Epistemic Models and GDL-II [Abstract] [BibTeX]	2011	Proceedings of the IJCAI-11 Workshop on General Game Playing (GIGA'11), pp. 53-60	inproceedings	URL
Abstract: A general game player automatically learns to play arbitrary new games solely by being told their rules. For this purpose games are speciﬁed in the game description language GDL, a variant of Datalog with function symbols that uses a few known keywords. A recent extension to GDL allows to describe nondeterministic games with any number of players who may have imperfect, asymmetric information. We analyze the epistemic structure and expressiveness of this language in terms of modal epistemic logic and present two main results: (1) The operational semantics of GDL entails that the situation at any stage of a game can be characterized by a multi-agent epistemic (i.e., S5-) model; (2) GDL is sufﬁciently expressive to model any situation that can be described by a (ﬁnite) multi-agent epistemic model.
BibTeX: @inproceedings{Ruan2011, author = {Ji Ruan and Michael Thielscher}, title = {On the Comparative Expressiveness of Epistemic Models and GDL-II}, booktitle = {Proceedings of the IJCAI-11 Workshop on General Game Playing (GIGA'11)}, year = {2011}, pages = {53-60}, url = {ijcai-11.iiia.csic.es/files/proceedings/GIGA-11-Proceedings.pdf} }
Ruan, J. & Thielscher, M.	Strategic and Epistemic Reasoning for the Game Description Language GDL-II [Abstract] [BibTeX]	2012	Proceedings of the European Conference on Artificial Intelligence (ECAI)	inproceedings	URL
Abstract: The game description language GDL has been developed as a logic-based formalism for representing the rules of arbitrary games in general game playing. A recent language extension called GDL-II allows to describe nondeterministic games with any number of players who may have incomplete, asymmetric information. In this paper, we show how the well-known Alternating-time Temporal Epistemic Logic (ATEL) can be adapted for strategic and epistemic reasoning about general games described in GDL-II. We provide a semantic characterisation of GDL-II descriptions in terms of ATEL models. We also provide a syntactic translation of GDL-II descriptions into ATEL formulas, and we prove that these two characterisations are equivalent. We show that model checking in this setting is decidable by giving an algorithm, and we demonstrate how our results can be used to verify strategic and epistemic properties of games described in GDL-II.
BibTeX: @inproceedings{Ruan2012, author = {Ji Ruan and Michael Thielscher}, title = {Strategic and Epistemic Reasoning for the Game Description Language GDL-II}, booktitle = {Proceedings of the European Conference on Artificial Intelligence (ECAI)}, publisher = {IOS Press}, year = {2012}, url = {http://cgi.cse.unsw.edu.au/~mit/Papers/ECAI12.pdf} }
Ruan, J. & Thielscher, M.	Logical-Epistemic Foundations of General Game Descriptions [Abstract] [BibTeX]	2014	Studia Logica Vol. 102(2), pp. 321-338	article	URL
Abstract: A general game player automatically learns to play arbitrary new games solely by being told their rules. For this purpose games are specified in the general Game Description Language (GDL), a variant of Datalog with function symbols that uses a few game-specific keywords. A recent extension of basic GDL allows the description of nondeterministic games with any number of players who may have incomplete, asymmetric information. In this paper, we analyse the epistemic structure and expressiveness of this language in terms of modal epistemic logic and prove two main results: (1) The operational semantics of GDL entails that the situation at any stage of a game can be characterised by a multi-agent epistemic (i.e., S5-) model; (2) GDL is sufficiently expressive to model any situation that can be described by a (finite) multi-agent epistemic model.
BibTeX: @article{Ruan2014, author = {Ji Ruan and Michael Thielscher}, title = {Logical-Epistemic Foundations of General Game Descriptions}, journal = {Studia Logica}, year = {2014}, volume = {102}, number = {2}, pages = {321-338}, url = {http://cgi.cse.unsw.edu.au/~mit/Papers/SL14.pdf} }
Ruan, J. & Thielscher, M.	The Epistemic Logic Behind the Game Description Language [BibTeX]	2011	Proceedings of the AAAI Conference on Artificial Intelligence, pp. 840-845	inproceedings	URL
BibTeX: @inproceedings{Ruan2011a, author = {Ji Ruan and Michael Thielscher}, title = {The Epistemic Logic Behind the Game Description Language}, booktitle = {Proceedings of the AAAI Conference on Artificial Intelligence}, publisher = {AAAI Press}, year = {2011}, pages = {840-845}, url = {http://www.cse.unsw.edu.au/~mit/Papers/AAAI11a.pdf} }
Saffidine, A. & Cazenave, T.	A Forward Chaining Based Game Description Language Compiler [Abstract] [BibTeX]	2011	Proceedings of the IJCAI-11 Workshop on General Game Playing (GIGA'11), pp. 69-75	inproceedings	URL
Abstract: We present a first attempt at the compilation of the Game Description Language (GDL) using a bottom-up strategy. GDL is transformed into a normal form in which rules contain at most two predicates. The rules are then inverted to allow forward chaining and each predicate will turn into a function in the target language. Adding a fact to the knowledge base corresponds to triggering a function call. Permanent and persistent facts are detected and enable to speed up the deductions. The resulting program performs playouts at a competitive level. Experimental results show that a speed-up of more than 40% can be obtained without sacrificing scalability.
BibTeX: @inproceedings{Saffidine2011, author = {Abdallah Saffidine and Tristan Cazenave}, title = {A Forward Chaining Based Game Description Language Compiler}, booktitle = {Proceedings of the IJCAI-11 Workshop on General Game Playing (GIGA'11)}, year = {2011}, pages = {69-75}, url = {http://www.lamsade.dauphine.fr/%7Ecazenave/papers/gadelac.pdf} }
Saffidine, A., Finnsson, H. & Buro, M.	Alpha-Beta Pruning for Games with Simultaneous Moves [Abstract] [BibTeX]	2012	The Twenty-Sixth AAAI Conference on Artificial Intelligence	inproceedings	URL
Abstract: Alpha-Beta pruning is one of the most powerful and fundamental MiniMax search improvements. It was designed for sequential two-player zero-sum perfect information games. In this paper we introduce an Alpha-Beta-like sound pruning method for the more general class of “stacked matrix games” that allow for simultaneous moves by both players. This is accomplished by maintaining upper and lower bounds for achievable payoﬀs in states with simultaneous actions and dominated action pruning based on the feasibility of certain linear programs. Empirical data shows considerable savings in terms of expanded nodes compared to naive depth-ﬁrst move computation without pruning.
BibTeX: @inproceedings{Saffidine2012, author = {Abdallah Saffidine and Hilmar Finnsson and Michael Buro}, title = {Alpha-Beta Pruning for Games with Simultaneous Moves}, booktitle = {The Twenty-Sixth AAAI Conference on Artificial Intelligence}, year = {2012}, url = {http://cadia.ru.is/wiki/_media/public:cadiaplayer:hif_aaai12b.pdf} }
Schiffel, S.	Symmetry Detection in General Game Playing [Abstract] [BibTeX]	2009	Proceedings of the IJCAI-09 Workshop on General Game Playing (GIGA'09), pp. 67-74	inproceedings	URL
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.
BibTeX: @inproceedings{Schiffel2009, author = {Stephan Schiffel}, title = {Symmetry Detection in General Game Playing}, booktitle = {Proceedings of the IJCAI-09 Workshop on General Game Playing (GIGA'09)}, year = {2009}, pages = {67-74}, url = {http://www.general-game-playing.de/downloads/GIGA09_symmetry_detection.pdf} }
Schiffel, S.	Knowledge-Based General Game Playing [Abstract] [BibTeX]	2011	School: Technische Universität Dresden	phdthesis	URL
Abstract: The goal of General Game Playing (GGP) is to develop a system, that is able to automatically play previously unseen games well, solely by being given the rules of the game. In contrast to traditional game playing programs, a general game player cannot be given game specific knowledge. Instead, the program has to discover this knowledge and use it for effectively playing the game well without human intervention. In this thesis, we present a such a program and general methods that solve a variety of knowledge discovery problems in GGP. Our main contributions are methods for the automatic construction of heuristic evaluation functions, the automated discovery of game structures, a system for proving properties of games, and symmetry detection and exploitation for general games.
BibTeX: @phdthesis{Schiffel2011, author = {Stephan Schiffel}, title = {Knowledge-Based General Game Playing}, school = {Technische Universität Dresden}, year = {2011}, url = {http://nbn-resolving.de/urn:nbn:de:bsz:14-qucosa-88742} }
Schiffel, S.	Symmetry Detection in General Game Playing [Abstract] [BibTeX]	2010	Proceedings of the AAAI Conference on Artificial Intelligence, pp. 980-985	inproceedings	URL
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.
BibTeX: @inproceedings{Schiffel2010, author = {Stephan Schiffel}, title = {Symmetry Detection in General Game Playing}, booktitle = {Proceedings of the AAAI Conference on Artificial Intelligence}, publisher = {AAAI Press}, year = {2010}, pages = {980-985}, url = {http://www.general-game-playing.de/downloads/AAAI10_symmetry_detection.pdf} }
Schiffel, S. & Thielscher, M.	A Multiagent Semantics for the Game Description Language [Abstract] [BibTeX]	2009	Agents and Artificial Intelligence	inproceedings	URL
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.
BibTeX: @inproceedings{Schiffel2009a, author = {Stephan Schiffel and Michael Thielscher}, title = {A Multiagent Semantics for the Game Description Language}, booktitle = {Agents and Artificial Intelligence}, publisher = {Springer}, year = {2009}, url = {http://www.cse.unsw.edu.au/~mit/Papers/ICAART09.pdf} }
Schiffel, S. & Thielscher, M.	Specifying Multiagent Environments in the Game Description Language [Abstract] [BibTeX]	2009	Proceedings of ICAART 2009 - First International Conference on Agents and Artificial Intelligence	inproceedings	URL
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 that GDL can be readily used as a specification language for a large class of multiagent environments. 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 environments that can be described in GDL.
BibTeX: @inproceedings{Schiffel2009b, author = {Stephan Schiffel and Michael Thielscher}, title = {Specifying Multiagent Environments in the Game Description Language}, booktitle = {Proceedings of ICAART 2009 - First International Conference on Agents and Artificial Intelligence}, publisher = {INSTICC Press}, year = {2009}, note = {Don't put on website!}, url = {http://www.general-game-playing.de/downloads/ICAART09_Schiffel_Thielscher.pdf} }
Schiffel, S. & Thielscher, M.	Representing and Reasoning About the Rules of General Games With Imperfect Information [Abstract] [BibTeX]	2014	Journal of Artificial Intelligence Research Vol. 49, pp. 171-206	article	DOI URL
Abstract: 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.
BibTeX: @article{Schiffel2014, author = {Stephan Schiffel and Michael Thielscher}, title = {Representing and Reasoning About the Rules of General Games With Imperfect Information}, journal = {Journal of Artificial Intelligence Research}, year = {2014}, volume = {49}, pages = {171-206}, url = {http://www.jair.org/papers/paper4115.html}, doi = {http://dx.doi.org/10.1613/jair.4115} }
Schiffel, S. & Thielscher, M.	Reasoning About General Games Described in GDL-II [Abstract] [BibTeX]	2011	Proceedings of the AAAI Conference on Artificial Intelligence, pp. 846-851	inproceedings	URL
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.
BibTeX: @inproceedings{Schiffel2011a, author = {Stephan Schiffel and Michael Thielscher}, title = {Reasoning About General Games Described in GDL-II}, booktitle = {Proceedings of the AAAI Conference on Artificial Intelligence}, publisher = {AAAI Press}, year = {2011}, pages = {846-851}, url = {http://cgi.cse.unsw.edu.au/~mit/Papers/AAAI11b.pdf} }
Schiffel, S. & Thielscher, M.	Automated Theorem Proving for General Game Playing [Abstract] [BibTeX]	2009	Proceedings of IJCAI'09, pp. 911-916	inproceedings	URL
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.
BibTeX: @inproceedings{Schiffel2009c, author = {Stephan Schiffel and Michael Thielscher}, title = {Automated Theorem Proving for General Game Playing}, booktitle = {Proceedings of IJCAI'09}, year = {2009}, pages = {911-916}, url = {http://www.cse.unsw.edu.au/~mit/Papers/IJCAI09.pdf} }
Schiffel, S. & Thielscher, M.	Automatic construction of a heuristic search function for General Game Playing [Abstract] [BibTeX]	2007	Proceedings of the Seventh IJCAI International Workshop on Nonmontonic Reasoning, Action and Change	inproceedings	URL
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 search heuristics 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.
BibTeX: @inproceedings{Schiffel2007, author = {Stephan Schiffel and Michael Thielscher}, title = {Automatic construction of a heuristic search function for General Game Playing}, booktitle = {Proceedings of the Seventh IJCAI International Workshop on Nonmontonic Reasoning, Action and Change}, year = {2007}, url = {http://www.fluxagent.org/download.php?file=07-SchiffelThielscher-IJCAI.pdf} }
Schiffel, S. & Thielscher, M.	Fluxplayer: A Successful General Game Player [Abstract] [BibTeX]	2007	Proceedings of the 22nd AAAI Conference on Artificial Intelligence (AAAI-07), pp. 1191-1196	inproceedings	URL
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.
BibTeX: @inproceedings{Schiffel2007a, author = {Stephan Schiffel and Michael Thielscher}, title = {Fluxplayer: A Successful General Game Player}, booktitle = {Proceedings of the 22nd AAAI Conference on Artificial Intelligence (AAAI-07)}, publisher = {AAAI Press}, year = {2007}, pages = {1191-1196}, url = {http://www.fluxagent.org/download.php?file=07-SchiffelThielscher-AAAI.pdf} }
Schkufza, E.	Decomposition of Games for Efficient Reasoning [Abstract] [BibTeX]	2007	Abstraction, Reformulation, and Approximation, pp. 409-410	inproceedings	DOI URL
Abstract: General Game Playing (GGP) is an area of research in artificial intelligence that focuses on the representation of games in terms of an abstract language known as Game Description Language (GDL). The abstract nature of that language allows for the development of intelligent agents that without modification can perform competently on games that they have never seen before based on known properties of GDL's uniform and compact syntax. Although GDL is an effective tool for communication, it is less useful as a representational framework for reasoning about games. In its place, the Stanford Logic Group has developed a new class of behavioral models, called Propositional Nets (PNs), with which an algorithm has been designed for determining whether games can be decomposed into independent sub-systems that can be reasoned about independently of one another.
BibTeX: @inproceedings{Schkufza2007, author = {Eric Schkufza}, title = {Decomposition of Games for Efficient Reasoning}, booktitle = {Abstraction, Reformulation, and Approximation}, publisher = {Springer Berlin / Heidelberg}, year = {2007}, pages = {409-410}, url = {http://www.springerlink.com/content/750hn867578890k3/}, doi = {http://dx.doi.org/10.1007/978-3-540-73580-9} }
Schkufza, E., Love, N. & Genesereth, M.R.	Propositional Automata and Cell Automata: Representational Frameworks for Discrete Dynamic Systems [Abstract] [BibTeX]	2008	Vol. 5360Australasian Conference on Artificial Intelligence, pp. 56-66	inproceedings	URL
Abstract: This paper describes and compares two simple, powerful models for formalizing the behavior of discrete dynamic systems: Propositional and Cell Automata. Propositional Automata encode state in terms of boolean propositions, and behavior in terms of boolean gates and latches. Cell Automata generalize the propositional model by encoding state in terms of multi-valued cells, and behavior in terms of comparators and selectors that respond to cell values. While the models are equally expressive, Cell Automata are computationally more efficient than Propositional Automata. Additionally, arbitrary Propositional Automata can be converted to optimal Cell Automata with identical behavioral properties, and Cell Automata can be encoded as a Propositional Automata with only logarithmic increase in size.
BibTeX: @inproceedings{Schkufza2008, author = {Eric Schkufza and Nathaniel Love and Michael R. Genesereth}, title = {Propositional Automata and Cell Automata: Representational Frameworks for Discrete Dynamic Systems}, booktitle = {Australasian Conference on Artificial Intelligence}, publisher = {Springer}, year = {2008}, volume = {5360}, pages = {56-66}, url = {http://dx.doi.org/10.1007/978-3-540-89378-3_6} }
Schofield, M., Cerexhe, T. & Thielscher, M.	Lifting HyperPlay for General Game Playing to Incomplete-Information Models [Abstract] [BibTeX]	2013	Proceedings of the IJCAI-13 Workshop on General Game Playing (GIGA'13), pp. 39-45	inproceedings	URL
Abstract: General Game Playing is the design of AI systems able to understand the rules of new games and to use such descriptions to play those games effectively. Games with imperfect information have recently been added as a new challenge for existing general game-playing systems. The only published solution to this challenge, HyperPlay, maintains a collection of complete information models. In doing so it grounds all of the unknown information thereby valuing all information gathering moves at zero—a well-known criticism of such samplingbased or particle ﬁlter systems. We have extended HyperPlay to better reason about its knowledge. This escalates reasoning from complete-information models to incompleteinformation models, and correctly values information gathering moves. In this paper we describe the new HyperPlay-II technique, show how it was adapted for use with a Monte Carlo decision making process, and give experimental results demonstrating its superiority over its predecessor.
BibTeX: @inproceedings{Schofield2013, author = {Michael Schofield and Timothy Cerexhe and Michael Thielscher}, title = {Lifting HyperPlay for General Game Playing to Incomplete-Information Models}, booktitle = {Proceedings of the IJCAI-13 Workshop on General Game Playing (GIGA'13)}, year = {2013}, pages = {39-45}, url = {http://giga13.ru.is/GIGA-13-Proceedings.pdf} }
Schofield, M., Cerexhe, T. & Thielscher, M.	HyperPlay: A Solution to General Game Playing with Imperfect Information [Abstract] [BibTeX]	2012	Proceedings of the AAAI Conference on Artificial Intelligence	inproceedings	URL
Abstract: General Game Playing is the design of AI systems able to understand the rules of new games and to use such descriptions to play those games effectively. Games with imperfect information have recently been added as a new challenge for existing general game-playing systems. The HyperPlay technique presents a solution to this challenge by maintaining a collection of models of the true game as a foundation for reasoning, and move selection. The technique provides existing game players with a bolt-on solution to convert from perfect-information games to imperfect-information games. In this paper we describe the HyperPlay technique, show how it was adapted for use with a Monte Carlo decision making process and give experimental results for its performance.
BibTeX: @inproceedings{Schofield2012, author = {Michael Schofield and Timothy Cerexhe and Michael Thielscher}, title = {HyperPlay: A Solution to General Game Playing with Imperfect Information}, booktitle = {Proceedings of the AAAI Conference on Artificial Intelligence}, publisher = {AAAI Press}, year = {2012}, url = {http://cgi.cse.unsw.edu.au/~mit/Papers/AAAI12.pdf} }
Schofield, M. & Saffidine, A.	High Speed Forward Chaining for General Game Playing [Abstract] [BibTeX]	2013	Proceedings of the IJCAI-13 Workshop on General Game Playing (GIGA'13), pp. 31-38	inproceedings	URL
Abstract: General Game Playing demands that an AI system be capable of interpreting a set of rules for a previ ously unseen game and reason about the game state as efﬁciently as possible. In simulation based rea soners, the number of states that can be visited in a ﬁxed time limit is paramount. One technique for calculating each game state is Forward Chaining; where the system calculates all of the relations that can be calculated from the current state and uses that as a basis for the next state. In this work we progress some earlier work on For ward Chaining and propose two additional features. Firstly the augmentation of rule processing using reference tables to facilitate high speed instantia tion of ground relations into a rule, and secondly an empirical hypothesis ordering strategy utilising data collected from the operation of the system to optimise its performance. This paper proposes and deﬁnes these additional features and presents ex perimental data to support their use.
BibTeX: @inproceedings{Schofield2013a, author = {Michael Schofield and Abdallah Saffidine}, title = {High Speed Forward Chaining for General Game Playing}, booktitle = {Proceedings of the IJCAI-13 Workshop on General Game Playing (GIGA'13)}, year = {2013}, pages = {31-38}, url = {http://giga13.ru.is/GIGA-13-Proceedings.pdf} }
Schofield, M. & Thielscher, M.	General Game Playing with Imperfect Information [BibTeX]	2019	Journal of Artificial Intelligence Research Vol. 66, pp. 901-935	article	DOI URL
BibTeX: @article{Schofield2019, author = {Michael Schofield and Michael Thielscher}, title = {General Game Playing with Imperfect Information}, journal = {Journal of Artificial Intelligence Research}, year = {2019}, volume = {66}, pages = {901--935}, url = {https://jair.org/index.php/jair/article/view/11844/26543}, doi = {http://dx.doi.org/10.1613/jair.1.11844} }
Schofield, M. & Thielscher, M.	The Efficiency of the HyperPlay Technique Over Random Sampling [BibTeX]	2017	Proceedings of the AAAI Conference on Artificial Intelligence, pp. 282-290	inproceedings	URL
BibTeX: @inproceedings{Schofield2017, author = {Michael Schofield and Michael Thielscher}, title = {The Efficiency of the HyperPlay Technique Over Random Sampling}, booktitle = {Proceedings of the AAAI Conference on Artificial Intelligence}, publisher = {AAAI Press}, year = {2017}, pages = {282--290}, url = {https://www.aaai.org/ocs/index.php/AAAI/AAAI17/paper/viewFile/14560/13774} }
Schofield, M. & Thielscher, M.	Lifting Model Sampling for General Game Playing to Incomplete-Information Models [BibTeX]	2015	Proceedings of the AAAI Conference on Artificial Intelligence, pp. 3585-3591	inproceedings	URL
BibTeX: @inproceedings{Schofield2015, author = {Michael Schofield and Michael Thielscher}, title = {Lifting Model Sampling for General Game Playing to Incomplete-Information Models}, booktitle = {Proceedings of the AAAI Conference on Artificial Intelligence}, publisher = {AAAI Press}, year = {2015}, pages = {3585--3591}, url = {https://aaai.org/ocs/index.php/AAAI/AAAI15/paper/view/10014/9797} }
Shafiei, M., Sturtevant, N. & Schaeffer, J.	Comparing UCT versus CFR in Simultaneous Games [Abstract] [BibTeX]	2009	Proceedings of the IJCAI-09 Workshop on General Game Playing (GIGA'09), pp. 75-82	inproceedings	URL
Abstract: Simultaneous move games where all the player have to take their actions simultaneously are a class of games in general game playing. In this paper we analyze how UCT performs in this class of games. We argue that UCT does not converge to a Nash equilibrium in general and the situation that it converges to can be exploited. We also analyze CFR (CounterFactual Regret) and show how it can be used to exploit UCT.
BibTeX: @inproceedings{Shafiei2009, author = {Mohammad Shafiei and Nathan Sturtevant and Jonathan Schaeffer}, title = {Comparing UCT versus CFR in Simultaneous Games}, booktitle = {Proceedings of the IJCAI-09 Workshop on General Game Playing (GIGA'09)}, year = {2009}, pages = {75-82}, url = {http://www.cs.ualberta.ca/~nathanst/papers/uctcfr.pdf} }
Sharma, S. & Kobti, Z.	A Multi-Agent Architecture for General Game Playing [Abstract] [BibTeX]	2007	Proceedings of the IEEE Symposium on Computational Intelligence and Games	inproceedings	URL
Abstract: General Game playing, a relatively new field in game research, presents new frontiers in building intelligent game players. The traditional premise for building a good artificially intelligent player is that the game is known to the player and pre-programmed to play accordingly. General game players challenge game programmers by not identifying the game until the beginning of game play. In this paper we explore a new approach to intelligent general game playing employing a self-organizing, multiple-agent evolutionary learning strategy. In order to decide on an intelligent move, specialized agents interact with each other and evolve competitive solutions to decide on the best move, sharing the learnt experience and using it to train themselves in a social environment. In an experimental setup using a simple board game, the evolutionary agents employing a learning strategy by training themselves from their own experiences, and without prior knowledge of the game, demonstrate to be as effective as other strong dedicated heuristics. This approach provides a potential for new intelligent game playing program design in the absence of prior knowledge of the game at hand.
BibTeX: @inproceedings{Sharma2007, author = {Shiven Sharma and Ziad Kobti}, title = {A Multi-Agent Architecture for General Game Playing}, booktitle = {Proceedings of the IEEE Symposium on Computational Intelligence and Games}, year = {2007}, url = {http://www.site.uottawa.ca/~sshar009/cig07.pdf} }
Sharma, S., Kobti, Z. & Goodwin, S.	Coevolving Intelligent Game Players in a Cultural Framework [Abstract] [BibTeX]	2009	Proceedings of the IEEE Congress on Evolutionary Computing, Special Session on Computational Intelligence in Games	inproceedings	URL
Abstract: Game playing has always provided an exciting avenue of research in Artificial Intelligence. Various methodologies and techniques have been developed to build intelligent game players. Coevolution has proven to be successful in learning how to play games with no prior game knowledge. In this paper we develop a coevolutionary system for the General Game Playing framework, where absolutely nothing is known about the game beforehand, and enhance it using Cultural Algorithms. In order to test the effectiveness of complementing coevolution with cultural algorithms, we play matches in several games between our player, a random player and one trained using standard coevolution.
BibTeX: @inproceedings{Sharma2009, author = {Shiven Sharma and Ziad Kobti and Scott Goodwin}, title = {Coevolving Intelligent Game Players in a Cultural Framework}, booktitle = {Proceedings of the IEEE Congress on Evolutionary Computing, Special Session on Computational Intelligence in Games}, year = {2009}, url = {http://www.site.uottawa.ca/~sshar009/SKG_CEC.pdf} }
Sharma, S., Kobti, Z. & Goodwin, S.	Learning and Knowledge Generation in General Games [Abstract] [BibTeX]	2008	Proceedings of the IEEE Symposium on Computational Intelligence and Games	inproceedings	URL
Abstract: General Game Playing (GGP) aims at developing game playing agents that are able to play a variety of games and in the absence of game specific knowledge, become proficient players. Most GGP players have used standard tree-search techniques enhanced by automatic heuristic learning. In this paper we explore knowledge representation and learning in GGP using Reinforcement Learning and Ant Colony Algorithms. Knowledge is created by simulating random games. We test the quality of the knowledge by comparing the performance of players using the knowledge in a variety of games. The ideas presented in this paper provide the potential for a framework for learning and knowledge representation, given the total absence of any prior knowledge.
BibTeX: @inproceedings{Sharma2008b, author = {Shiven Sharma and Ziad Kobti and Scott Goodwin}, title = {Learning and Knowledge Generation in General Games}, booktitle = {Proceedings of the IEEE Symposium on Computational Intelligence and Games}, year = {2008}, url = {http://www.site.uottawa.ca/~sshar009/cig08.pdf} }
Sharma, S., Kobti, Z. & Goodwin, S.D.	General Game Playing with Ants [Abstract] [BibTeX]	2008	Vol. 5361Proceedings of the Seventh International Conference on Simulated Evolution And Learning (SEAL'08), pp. 381-390	inproceedings	DOI URL
Abstract: General Game Playing (GGP) aims at developing game playing agents that are able to play a variety of games and, in the absence of pre-programmed game specific knowledge, become proficient players. The challenge of making such a player has led to various techniques being used to tackle the problem of game specific knowledge absence. Most GGP players have used standard tree-search techniques enhanced by automatic heuristic learning, neuroevolution and UCT (Upper Confidence bounds applied to Trees) search, which is a simulation-based tree search. In this paper, we explore a new approach to GGP. We use an Ant Colony System (ACS) to explore the game space and evolve strategies for game playing. Each ant in the ACS is a player with an assigned role, and forages through the game's state space, searching for promising paths to victory. Preliminary results show this approach to be promising. In order to test the architecture, we create matches between players using the knowledge learnt by the ACS and random players.
BibTeX: @inproceedings{Sharma2008, author = {Shiven Sharma and Ziad Kobti and Scott D. Goodwin}, title = {General Game Playing with Ants}, booktitle = {Proceedings of the Seventh International Conference on Simulated Evolution And Learning (SEAL'08)}, publisher = {Springer}, year = {2008}, volume = {5361}, pages = {381-390}, url = {http://www.site.uottawa.ca/~sshar009/seal08.pdf}, doi = {http://dx.doi.org/10.1007/978-3-540-89694-4_39} }
Sharma, S., Kobti, Z. & Goodwin, S.D.	Knowledge Generation for Improving Simulations in UCT for General Game Playing [Abstract] [BibTeX]	2008	Vol. 5360Australasian Conference on Artificial Intelligence	inproceedings	DOI URL
Abstract: General Game Playing (GGP) aims at developing game playing agents that are able to play a variety of games and, in the absence of pre-programmed game specific knowledge, become proficient players. Most GGP players have used standard tree-search techniques enhanced by automatic heuristic learning. The UCT algorithm, a simulation-based tree search, is a new approach and has been used successfully in GGP. However, it relies heavily on random simulations to assign values to unvisited nodes and selecting nodes for descending down a tree. This can lead to slower convergence times in UCT. In this paper, we discuss the generation and evolution of domain-independent knowledge using both state and move patterns. This is then used to guide the simulations in UCT. In order to test the improvements, we create matches between a player using standard the UCT algorithm and one using UCT enhanced with knowledge.
BibTeX: @inproceedings{Sharma2008a, author = {Shiven Sharma and Ziad Kobti and Scott D. Goodwin}, title = {Knowledge Generation for Improving Simulations in UCT for General Game Playing}, booktitle = {Australasian Conference on Artificial Intelligence}, publisher = {Springer}, year = {2008}, volume = {5360}, url = {http://www.site.uottawa.ca/~sshar009/ai08.pdf}, doi = {http://dx.doi.org/10.1007/978-3-540-89378-3_5} }
Sharma, S., Kobti, Z. & Goodwin, S.D.	General Game Playing: An Overview and Open Problems [BibTeX]	2009	Computing, Engineering and Information, International Conference on Vol. 0, pp. 257-260	article	DOI
BibTeX: @article{Sharma2009a, author = {Shiven Sharma and Ziad Kobti and Scott D. Goodwin}, title = {General Game Playing: An Overview and Open Problems}, journal = {Computing, Engineering and Information, International Conference on}, publisher = {IEEE Computer Society}, year = {2009}, volume = {0}, pages = {257-260}, doi = {http://doi.ieeecomputersociety.org/10.1109/ICC.2009.50} }
Sheng, X.	Goal-Based Agent Design: Decision Making in General Game Playing [Abstract] [BibTeX]	2011	School: North Carolina State University	phdthesis	URL
Abstract: General Game Playing's primary research thrust is building automated intelligent computer agents that accept declarative descriptions of arbitrary games at run-time and are capable of using such descriptions to play effectively without human intervention. The research in general game playing approximates human cognitive processes, sophisticated planning, and problem solving with an instant reward system represented in games. General game playing has well-recognized research areas with diverse topics including knowledge representation, search, strategic planning, and machine learning. It attacks the general intelligence problem that Artificial Intelligence researchers have made little progress on for the last several decades. We have designed and implemented an automated goal-based general game playing agent that is capable of playing most games written in the Game Description Language and has shown excellent results for general-purpose learning in the general game playing environment. Our contributions include: the general game playing agent designed to play a wide variety of games, the knowledge reasoning performance improvement algorithm, the run-time feature identification algorithm, the contextual decision-making algorithm, and the GDL extension to enrich the game domain.
BibTeX: @phdthesis{Sheng2011, author = {Xinxin Sheng}, title = {Goal-Based Agent Design: Decision Making in General Game Playing}, school = {North Carolina State University}, year = {2011}, url = {http://www.lib.ncsu.edu/resolver/1840.16/7353} }
Sheng, X. & Thuente, D.	Extending the General Game Playing Framework to Other Languages [Abstract] [BibTeX]	2011	Proceedings of the IJCAI-11 Workshop on General Game Playing (GIGA'11), pp. 77-84	inproceedings	URL
Abstract: General Game Playing (GGP) research aims at building automated intelligent computer agents that accept declarative descriptions of arbitrary games at run time and are able to use such descriptions to play effectively without human intervention. This paper extends the Game Description Language (GDL) to more easily describe complicated games, including social and financial games with diverse goals. The GDL extension allows adding functions, defined in other programming languages such as Java, C++, Lisp, to the general game playing architecture. We used the three-player, simultaneous financial game Farmer, a standard GGP game, as an example to illustrate the need for and the benefits of the GDL extension. We also show the extension of the GDL is critical for adding coalition games to the general game playing area.
BibTeX: @inproceedings{Sheng2011a, author = {Xinxin Sheng and David Thuente}, title = {Extending the General Game Playing Framework to Other Languages}, booktitle = {Proceedings of the IJCAI-11 Workshop on General Game Playing (GIGA'11)}, year = {2011}, pages = {77-84}, url = {ijcai-11.iiia.csic.es/files/proceedings/GIGA-11-Proceedings.pdf} }
Sheng, X. & Thuente, D.	Using Decision Trees for State Evaluation in General Game Playing [Abstract] [BibTeX]	2011	KI Vol. 25(1), pp. 53-56	article	URL
Abstract: A general game playing agent understands the formal descriptions of an arbitrary game in the multi-agent environment and learns to play the given games without human intervention. In this paper, we present an agent that automatically extracts common features shared by the game winners and uses such learned features to build decision trees to guide the heuristic search. We present data to show the significant performance improvements contributed by the decision tree evaluation. We also show by using hash tables in knowledge reasoning, our agent uses 80% less time when compared to a widely available GGP agent written in the same language.
BibTeX: @article{Sheng2011b, author = {Xinxin Sheng and David Thuente}, title = {Using Decision Trees for State Evaluation in General Game Playing}, journal = {KI}, year = {2011}, volume = {25}, number = {1}, pages = {53-56}, url = {http://www.springerlink.com/content/94730p6w84586711/} }
Sheng, X. & Thuente, D.	Decision Tree Learning in General Game Playing [Abstract] [BibTeX]	2011	International Conference on Artificial Intelligence and Applications	inproceedings	DOI URL
Abstract: This paper introduces a General Game Playing agent that automatically adapts to play different kinds of games without human intervention in a multi-agent system. By using machine learning techniques in heuristic search, especially decision tree learning, the agent is able to identify common winning features in a given game and evaluate a game state with many features as an entirety. We provide four distinctly different game examples to show how the agent’s performance has been improved by introducing decision tree learning. These four games are the strategy game Mini-Chess, the territory taking game Connect Four, the crossing Chinese Checker, and the three player simultaneous game Farmer.
BibTeX: @inproceedings{Sheng2011c, author = {Xinxin Sheng and David Thuente}, title = {Decision Tree Learning in General Game Playing}, booktitle = {International Conference on Artificial Intelligence and Applications}, year = {2011}, url = {http://www.actapress.com/Abstract.aspx?paperId=451465}, doi = {http://dx.doi.org/10.2316/P.2011.717-109} }
Sheng, X. & Thuente, D.	Using Hash Tables to Expedite Knowledge Reasoning in the General Game Playing Agent [Abstract] [BibTeX]	2010	Advanced Topics in Artificial Intelligence (ATAI 2010)	inproceedings	URL
Abstract: General game playing research focuses on designing automated agents that accept declarative logic description of arbitrary games at run time and are able to play efficiently without human intervention. The game information including the game states, the rules of the game, and the player's role in thegame are all represented in logic relations. The general game playing agent uses knowledge representation and reasoning algorithms to analyze and play the game. We use hash table to significantly improve the reasoning performance. We provide experimental data on seven different games: small games like the single player game Maze, the strategy game Mini-Chess, the two player game Tic-Tac-Toe, the middle size board games ConnectFour and Chess Endgame, the large size game like Othello, and finally the three-player eCommerce game Farmer. In all of these scenarios, our agent has proven to significantly outperform thes tandard published Java player.
BibTeX: @inproceedings{Sheng2010, author = {Xinxin Sheng and David Thuente}, title = {Using Hash Tables to Expedite Knowledge Reasoning in the General Game Playing Agent}, booktitle = {Advanced Topics in Artificial Intelligence (ATAI 2010)}, year = {2010}, url = {http://dl.globalstf.org/index.php?page=shop.product_details&flypage=flypage_images.tpl&product_id=399&category_id=33&option=com_virtuemart&Itemid=4} }
Sheng, X. & Thuente, D.J.	Predictive Sub-goal Analysis in a General Game Playing Agent [Abstract] [BibTeX]	2010	Proceedings of the 2010 IEEE/WIC/ACM International Conference on Web Intelligence and International Conference on Intelligent Agent Technology - Workshops, Toronto, Canada, August 31 - September 3, 2010, pp. 423-427	inproceedings	URL
Abstract: General Game Playing (GGP) research aims at designing intelligent game playing agents that, given the rules of any game, automatically learn strategies to play and win without human intervention. Our GGP agent can play the wide variety of heterogeneous games provided by the IJCAI GGP competition framework, and without human intervention, learn from its own history to develop strategies toward achieving the game goals. It uses statistical analysis to identify important game features shared by the winners. To illustrate how the correct features are identified, we use game examples from different game categories, including Tic-Tac-Toe (territory taking game), Mini-Chess (strategy game), and Connect Four (board game on larger scale).
BibTeX: @inproceedings{Sheng2010a, author = {Xinxin Sheng and David J. Thuente}, title = {Predictive Sub-goal Analysis in a General Game Playing Agent}, booktitle = {Proceedings of the 2010 IEEE/WIC/ACM International Conference on Web Intelligence and International Conference on Intelligent Agent Technology - Workshops, Toronto, Canada, August 31 - September 3, 2010}, publisher = {IEEE}, year = {2010}, pages = {423-427}, url = {http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=5614591} }
Sierra, C., Botti, V. & Ossowski, S.	Agreement Computing [Abstract] [BibTeX]	2011	KI Vol. 25(1), pp. 57-61	article	URL
Abstract: In this paper we introduce the concept of Agreement Computing, motivate the central role that the concept of agreement plays in open software systems and discuss a number of research challenges that need to be addressed to make the agreement computing vision a reality.
BibTeX: @article{Sierra2011, author = {Carles Sierra and Vicent Botti and Sascha Ossowski}, title = {Agreement Computing}, journal = {KI}, year = {2011}, volume = {25}, number = {1}, pages = {57-61}, url = {http://www.springerlink.com/content/m3k36875j5687x24/} }
Sievers, S.	Extension of a Planning System for the Solution of Single Person Games [Abstract] [BibTeX]	2009	School: University of Freiburg	mastersthesis	URL
Abstract: A General Game Playing System is one that can accept a formal definition of a game and play the game effectively without human intervention. Unlike specialized game players, general game players do not rely on algorithms designed in advance for specific games, and they are able to play different kinds of games. Besides two-player and multi-player games, the games that have to played successfully at the AAAI General Game Playing Competition also include single-player games. Due to algorithmic reasons, it is preferable to develop different modules handling the different kinds of games. Since single-player games described in the Game Description Language (GDL), in which the competition games are encoded, are essentially classical planning problems, it is possible to solve them using according algorithms. The goal of this thesis was to integrate state-of-the-art algorithms and heuristics used in classical planning into a General Game Playing system currently under development. The resulting system should be evaluated using some of the benchmark games available online.
BibTeX: @mastersthesis{Sievers2009, author = {Silvan Sievers}, title = {Extension of a Planning System for the Solution of Single Person Games}, school = {University of Freiburg}, year = {2009}, url = {http://www.informatik.uni-freiburg.de/~ki/papers/bachelorarbeiten/sievers-bachelorarbeit-09.pdf} }
Sironi, C.F., Liu, J. & Winands, M.H.M.	Self-Adaptive Monte Carlo Tree Search in General Game Playing [BibTeX]	2020	IEEE Transactions on Games Vol. 12(2), pp. 132-144	article	URL
BibTeX: @article{Sironi2020, author = {Chiara F. Sironi and Jialin Liu and Mark H. M. Winands}, title = {Self-Adaptive Monte Carlo Tree Search in General Game Playing}, journal = {IEEE Transactions on Games}, year = {2020}, volume = {12}, number = {2}, pages = {132--144}, url = {https://ieeexplore.ieee.org/iel7/7782673/8116623/08556454.pdf} }
Spies, D.	Stratiﬁed Logic Program Updates for General Game Playing [Abstract] [BibTeX]	2013	Proceedings of the IJCAI-13 Workshop on General Game Playing (GIGA'13), pp. 71-77	inproceedings	URL
Abstract: General Game Playing Agents often play far more poorly than their game-speciﬁc counterparts due to the overhead of repeatedly querying an evolving logic program. A natural alternative approach is to instead maintain a grounded logic program and update it as the game state changes. This paper presents a simple algorithm for updating a stratiﬁed logic program to reﬂect changes to the game state and shows for Connect-4 that using logic program updates as opposed to recomputing from scratch at each visited game-state constitutes a big-O improvement in the running time of checking for 4-in-a-row.
BibTeX: @inproceedings{Spies2013, author = {David Spies}, title = {Stratiﬁed Logic Program Updates for General Game Playing}, booktitle = {Proceedings of the IJCAI-13 Workshop on General Game Playing (GIGA'13)}, year = {2013}, pages = {71-77}, url = {http://giga13.ru.is/GIGA-13-Proceedings.pdf} }
Swiechowski, M. & Mandziuk, J.	Specialized vs. Multi-game Approaches to AI in Games [Abstract] [BibTeX]	2014	Proceedings of the 7th IEEE International Conference on Intelligent Systems, pp. 243-254	inproceedings	URL
Abstract: In this work, we identify the main problems in which methodology of creating multi-game playing programs differs from single-game playing programs. The multi-game framework chosen in this comparison is General Game Playing, which was proposed at Stanford University in 2005, since it defines current state-of-the-art trends in the area. Based on the results from the International General Game Playing Competitions and additional results of our agent named MINI-Player we conclude on what defines a successful player. The most successful players have been using a minimal knowledge and a mechanism called Monte Carlo Tree-Search, which is simulation-based and self-improving over time.
BibTeX: @inproceedings{Swiechowski2014a, author = {Maciej Swiechowski and Jacek Mandziuk}, title = {Specialized vs. Multi-game Approaches to AI in Games}, booktitle = {Proceedings of the 7th IEEE International Conference on Intelligent Systems}, year = {2014}, pages = {243-254}, url = {http://www.mini.pw.edu.pl/~swiechowskim/is2014_paper.pdf} }
Swiechowski, M. & Mandziuk, J.	Prolog versus specialized logic inference engine in General Game Playing [Abstract] [BibTeX]	2014	Proceedings of IEEE Conference on Computational Intelligence in Games (CIG)	inproceedings
Abstract: In this paper, we study the problem of applying an inference engine, i.e. a mechanism able to derive answers from a knowledge base, to General Game Playing (GGP). Our focus is on the General Game Playing Competition framework proposed by the Stanford Logic Group. This particular embodiment of a multi-game playing uses the Game Description Language (GDL) for representing the knowledge base by means of game rules. The GDL is a variant of Datalog and a subset of Prolog, so there is a strong bond with formal logic languages. We present basic principles of our system which is dedicated to GDL. The motivation is to exceed the performance of Prolog engines applied to GDL, which is currently a common approach. Empirical results show that our solution is indeed faster in 6 out of 7 tested games.
BibTeX: @inproceedings{Swiechowski2014b, author = {Maciej Swiechowski and Jacek Mandziuk}, title = {Prolog versus specialized logic inference engine in General Game Playing}, booktitle = {Proceedings of IEEE Conference on Computational Intelligence in Games (CIG)}, year = {2014} }
Swiechowski, M. & Mandziuk, J.	Fast Interpreter for Logical Reasoning in General Game Playing [Abstract] [BibTeX]	2014	Journal of Logic and Computation Vol. 24(5), pp. 1071-1110	article	URL
Abstract: In this article, we present an efficient construction of the Game Description Language (GDL) interpreter. GDL is a first-order logic language used in the General Game Playing (GGP) framework. Syntactically, the language is a subset of Datalog and Prolog, and like those two, is based on facts and rules. Our aim was to achieve higher execution speed than anyone’s of the currently available tools, including other Prolog interpreters applied to GDL. Speed is a crucial factor of the state space search methods used by most GGP agents, since the faster the GDL reasoner, the more game states can be evaluated in the allotted time. The cornerstone of our interpreter is the resolution tree which reflects the dependencies between rules. Our paradigm was to expedite any heavy workload to the preprocessing step to optimize the real-time usage. The proposed enhancements effectively maintain a balance between the time needed to build the internal data representation and the time required for data analysis during actual play. Therefore we refrain from using tree-based dictionary approaches such as TRIE to store the results of logical queries in favour of a memory-friendly linear representation and dynamic filters to reduce space complexity. Experimental results show that our interpreter outperforms the two most popular Prolog interpreters used by GGP programs: Yet Another Prolog (YAP) and ECLiPSe, respectively, in 22 and 26 games, out of the 28 tested. We give some insights into possible reasons for the edge of our approach over Prolog.
BibTeX: @article{Swiechowski2014c, author = {Maciej Swiechowski and Jacek Mandziuk}, title = {Fast Interpreter for Logical Reasoning in General Game Playing}, journal = {Journal of Logic and Computation}, year = {2014}, volume = {24}, number = {5}, pages = {1071-1110}, url = {http://dx.doi.org/10.1093/logcom/exu058} }
Swiechowski, M. & Mandziuk, J.	Self-Adaptation of Playing Strategies in General Game Playing [Abstract] [BibTeX]	2013	Computational Intelligence and AI in Games, IEEE Transactions on Vol. PP(99)	article	DOI URL
Abstract: The term General Game Playing (GGP) refers to a subfield of Artificial Intelligence which aims at developing agents able to effectively play many games from a particular class (finite, deterministic). It is also the name of the annual competition proposed by Stanford Logic Group at Stanford University, which provides a framework for testing and evaluating GGP agents. In this paper we present our GGP player which managed to win 4 out of 7 games in the 2012 preliminary round and advanced to the final phase. Our system (named MINI-Player) relies on a pool of playing strategies and autonomously picks the ones which seem to be best suited to a given game. The chosen strategies are combined with one another and incorporated into the Upper Confidence Bounds applied to Trees (UCT) algorithm. The effectiveness of our player is evaluated on a set of games from the 2012 GGP Competition as well as a few other, single-player games. The paper discusses the efficacy of proposed playing strategies and evaluates the mechanism of their switching. The proposed idea of dynamically assigning search strategies during play is both novel and promising.
BibTeX: @article{Swiechowski2013, author = {Swiechowski, M. and Mandziuk, J.}, title = {Self-Adaptation of Playing Strategies in General Game Playing}, journal = {Computational Intelligence and AI in Games, IEEE Transactions on}, year = {2013}, volume = {PP}, number = {99}, url = {http://dx.doi.org/10.1109/TCIAIG.2013.2275163}, doi = {http://dx.doi.org/10.1109/TCIAIG.2013.2275163} }
Tak, M.J., Winands, M.H. & Björnsson, Y.	Decaying Simulation Strategies [Abstract] [BibTeX]	2013	Proceedings of the IJCAI-13 Workshop on General Game Playing (GIGA'13), pp. 23-30	inproceedings	URL
Abstract: The aim of General Game Playing (GGP) is to create programs capable of playing a wide range of different games at an expert level, given only the rules of the game. The most successful GGP programs currently employ simulation-based Monte Carlo Tree Search (MCTS). The performance of MCTS depends heavily on the simulation strategy used. In this paper we investigate the application of a decay factor for two domain independent simulation stategies: N-Gram Selection Technique (NST) and Move-Average Sampling Technique (MAST). The adjustment is tested in CADIA PLAYER on 20 different games. Three types of games are used, namely: turn-taking, simultaneous-move and multi-player. Experiments reveal that a decay factor signiﬁcantly improves the NST and MAST simulation strategy.
BibTeX: @inproceedings{Tak2013, author = {Mandy J.W. Tak and Mark H.M. Winands and Yngvi Björnsson}, title = {Decaying Simulation Strategies}, booktitle = {Proceedings of the IJCAI-13 Workshop on General Game Playing (GIGA'13)}, year = {2013}, pages = {23-30}, url = {http://giga13.ru.is/GIGA-13-Proceedings.pdf} }
Tak, M.J.W., Winands, M.H.M. & Bjornsson, Y.	N-Grams and the Last-Good-Reply Policy Applied in General Game Playing [Abstract] [BibTeX]	2012	IEEE Transactions on Computational Intelligence and AI in Games Vol. 4(2), pp. 73-83	article	URL
Abstract: The aim of general game playing (GGP) is to create programs capable of playing a wide range of different games at an expert level, given only the rules of the game. The most successful GGP programs currently employ simulation-based Monte Carlo tree search (MCTS). The performance of MCTS depends heavily on the simulation strategy used. In this paper, we introduce improved simulation strategies for GGP that we implement and test in the GGP agent CadiaPlayer, which won the International GGP competition in both 2007 and 2008. There are two aspects to the improvements: first, we show that a simple epsilon-greedy exploration strategy works better in the simulation play-outs than the softmax-based Gibbs measure currently used in CadiaPlayer and, second, we introduce a general framework based on N-grams for learning promising move sequences. Collectively, these enhancements result in a much improved performance of CadiaPlayer. For example, in our test suite consisting of five different two-player turn-based games, they led to an impressive average win rate of approximately 70%. The enhancements are also shown to be effective in multiplayer and simultaneous-move games. We additionally perform experiments with the last-good-reply policy (LGRP). The LGRP combined with N-grams is also tested. The LGRP has already been shown to be successful in Go programs and we demonstrate that it also has promise in GGP.
BibTeX: @article{Tak2012, author = {Tak, M. J. W. and Winands, M. H. M. and Bjornsson, Y.}, title = {N-Grams and the Last-Good-Reply Policy Applied in General Game Playing}, journal = {IEEE Transactions on Computational Intelligence and AI in Games}, year = {2012}, volume = {4}, number = {2}, pages = {73-83}, url = {http://dx.doi.org/10.1109/TCIAIG.2012.2200252} }
Taylor, M.E., Kuhlmann, G. & Stone, P.	Accelerating Search with Transferred Heuristics [Abstract] [BibTeX]	2007	ICAPS-07 workshop on AI Planning and Learning	inproceedings	URL
Abstract: A common goal for transfer learning research is to show that a learner can solve a source task and then leverage the learned knowledge to solve a target task faster than if it had learned the target task directly. A more difficult goal is to reduce the total training time so that learning the source task and target task is faster than learning only the target task. This paper addresses the second goal by proposing a transfer hierarchy for 2-player games. Such a hierarchy orders games in terms of relative solution difficulty and can be used to select source tasks that are faster to learn than a given target task. We empirically test transfer between two types of tasks in the General Game Playing domain, the testbed for an international competition developed at Stanford. Our results show that transferring learned search heuristics from tasks in different parts of the hierarchy can significantly speed up search even when the source and target tasks differ along a number of important dimensions.
BibTeX: @inproceedings{Taylor2007, author = {Matthew E. Taylor and Gregory Kuhlmann and Peter Stone}, title = {Accelerating Search with Transferred Heuristics}, booktitle = {ICAPS-07 workshop on AI Planning and Learning}, year = {2007}, url = {http://www.cs.utexas.edu/~pstone/Papers/bib2html-links/ICAPS07WS-taylor.pdf} }
Thielscher, M.	General Game Playing in AI Research and Education [Abstract] [BibTeX]	2011	Vol. 7006Proceedings of the German Annual Conference on Artificial Intelligence (KI), pp. 26-37	inproceedings	URL
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.
BibTeX: @inproceedings{Thielscher2011, author = {Michael Thielscher}, title = {General Game Playing in AI Research and Education}, booktitle = {Proceedings of the German Annual Conference on Artificial Intelligence (KI)}, publisher = {Springer}, year = {2011}, volume = {7006}, pages = {26-37}, url = {http://www.cse.unsw.edu.au/~mit/Papers/KI11.pdf} }
Thielscher, M.	Translating General Game Descriptions into an Action Language [BibTeX]	2011	Vol. 6565Logic Programming, Knowledge Representation, and Nonmonotonic Reasoning: Essays in Honor of Michael Gelfond, pp. 300-314	inproceedings	URL
BibTeX: @inproceedings{Thielscher2011a, author = {Michael Thielscher}, title = {Translating General Game Descriptions into an Action Language}, booktitle = {Logic Programming, Knowledge Representation, and Nonmonotonic Reasoning: Essays in Honor of Michael Gelfond}, publisher = {Springer}, year = {2011}, volume = {6565}, pages = {300-314}, url = {http://www.cse.unsw.edu.au/~mit/Papers/LPKRNR11.pdf} }
Thielscher, M.	A Legal Player for GDL-II Based on Filtering With Logic Programs [Abstract] [BibTeX]	2013	Proceedings of the IJCAI-13 Workshop on General Game Playing (GIGA'13), pp. 7-14	inproceedings	URL
Abstract: Motivated by the problem of building a basic reasoner for general game playing with imperfect information, we address the problem of ﬁltering with logic programs, whereby an agent updates its incomplete knowledge of a program by observations. We develop a ﬁltering method by adapting an existing backward-chaining and abduction method for so-called open logic programs. Experimental results show that this provides a basic effective and efﬁcient “legal” player for general imperfect-information games.
BibTeX: @inproceedings{Thielscher2013, author = {Michael Thielscher}, title = {A Legal Player for GDL-II Based on Filtering With Logic Programs}, booktitle = {Proceedings of the IJCAI-13 Workshop on General Game Playing (GIGA'13)}, year = {2013}, pages = {7-14}, url = {http://giga13.ru.is/GIGA-13-Proceedings.pdf} }
Thielscher, M.	Simulation of Action Theories and an Application to General Game-Playing Robots [BibTeX]	2015	Vol. 9060Advances in Knowledge Representation, Logic Programming, and Abstract Argumentation, pp. 33-46	incollection	URL
BibTeX: @incollection{Thielscher2015, author = {Michael Thielscher}, title = {Simulation of Action Theories and an Application to General Game-Playing Robots}, booktitle = {Advances in Knowledge Representation, Logic Programming, and Abstract Argumentation}, publisher = {Springer}, year = {2015}, volume = {9060}, pages = {33--46}, url = {http://cgi.cse.unsw.edu.au/~mit/Papers/KRLPAA15.pdf} }
Thielscher, M.	Answer Set Programming for Single-Player Games in General Game Playing [Abstract] [BibTeX]	2009	Proceedings of the International Conference on Logic Programming (ICLP)	inproceedings	URL
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.
BibTeX: @inproceedings{Thielscher2009, author = {Michael Thielscher}, title = {Answer Set Programming for Single-Player Games in General Game Playing}, booktitle = {Proceedings of the International Conference on Logic Programming (ICLP)}, publisher = {Springer}, year = {2009}, url = {http://www.cse.unsw.edu.au/~mit/Papers/ICLP09.pdf} }
Thielscher, M.	GDL-III: A Description Language for Epistemic General Game Playing [BibTeX]	2017	Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), pp. 1276-1282	inproceedings
BibTeX: @inproceedings{Thielscher2017, author = {Michael Thielscher}, title = {GDL-III: A Description Language for Epistemic General Game Playing}, booktitle = {Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI)}, year = {2017}, pages = {1276--1282} }
Thielscher, M.	Filtering With Logic Programs and Its Application to General Game Playing [Abstract] [BibTeX]	2013	Proceedings of the AAAI Conference on Artificial Intelligence	inproceedings	URL
Abstract: Motivated by the problem of building a basic reasoner for general game playing with imperfect information, we address the problem of ﬁltering with logic programs, whereby an agent updates its incomplete knowledge of a program by observations. We develop a ﬁltering method by adapting an existing backward-chaining and abduction method for so-called open logic programs. Experimental results show that this provides a basic effective and efﬁcient “legal” player for general imperfect-information games.
BibTeX: @inproceedings{Thielscher2013a, author = {Michael Thielscher}, title = {Filtering With Logic Programs and Its Application to General Game Playing}, booktitle = {Proceedings of the AAAI Conference on Artificial Intelligence}, publisher = {AAAI Press}, year = {2013}, url = {http://cgi.cse.unsw.edu.au/~mit/Papers/AAAI13.pdf} }
Thielscher, M.	GDL-II [Abstract] [BibTeX]	2011	Künstliche Intelligenz Vol. 25, pp. 63-66	article	DOI URL
Abstract: Abstract The Game Description Language (GDL) used in the past AAAI competitions allows to tell a system the rules of arbitrary ﬁnite 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.
BibTeX: @article{Thielscher2011b, author = {Michael Thielscher}, title = {GDL-II}, journal = {Künstliche Intelligenz}, publisher = {Springer}, year = {2011}, volume = {25}, pages = {63-66}, url = {http://www.springerlink.com/content/61522435262878j5/}, doi = {http://dx.doi.org/10.1007/s13218-010-0076-5} }
Thielscher, M.	The General Game Playing Description Language is Universal [Abstract] [BibTeX]	2011	Proceedings of the International Joint Conference on Artificial Intelligence, pp. 1107-1112	inproceedings	URL
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.
BibTeX: @inproceedings{Thielscher2011c, author = {Michael Thielscher}, title = {The General Game Playing Description Language is Universal}, booktitle = {Proceedings of the International Joint Conference on Artificial Intelligence}, publisher = {AAAI Press}, year = {2011}, pages = {1107-1112}, url = {http://www.cse.unsw.edu.au/~mit/Papers/IJCAI11.pdf} }
Thielscher, M.	A General Game Description Language for Incomplete Information Games [Abstract] [BibTeX]	2010	Proceedings of the AAAI Conference on Artificial Intelligence, pp. 994-999	inproceedings	URL
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 information they need to reason about their own knowledge as well as that of the other players up front and during game play.
BibTeX: @inproceedings{Thielscher2010, author = {Michael Thielscher}, title = {A General Game Description Language for Incomplete Information Games}, booktitle = {Proceedings of the AAAI Conference on Artificial Intelligence}, publisher = {AAAI Press}, year = {2010}, pages = {994-999}, url = {http://www.cse.unsw.edu.au/~mit/Papers/AAAI10a.pdf} }
Thielscher, M. & Voigt, S.	A Temporal Proof System for General Game Playing [Abstract] [BibTeX]	2010	Proceedings of the AAAI Conference on Artificial Intelligence, pp. 1000-1005	inproceedings	URL
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.
BibTeX: @inproceedings{Thielscher2010a, author = {Michael Thielscher and Sebastian Voigt}, title = {A Temporal Proof System for General Game Playing}, booktitle = {Proceedings of the AAAI Conference on Artificial Intelligence}, publisher = {AAAI Press}, year = {2010}, pages = {1000-1005}, url = {http://www.cse.unsw.edu.au/~mit/Papers/AAAI10b.pdf} }
Thielscher, M. & Zhang, D.	From General Game Descriptions to a Market Specification Language for General Trading Agents [Abstract] [BibTeX]	2010	Vol. 59Agent-Mediated Electronic Commerce: Designing Trading Strategies and Mechanisms for Electronic Markets, pp. 259-274	inproceedings	URL
Abstract: The idea behind General Game Playing is to build systems that, instead of being programmed for one specific task, are intelligent and ﬂexible 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.
BibTeX: @inproceedings{Thielscher2010b, author = {Michael Thielscher and Dongmo Zhang}, title = {From General Game Descriptions to a Market Specification Language for General Trading Agents}, booktitle = {Agent-Mediated Electronic Commerce: Designing Trading Strategies and Mechanisms for Electronic Markets}, publisher = {Springer}, year = {2010}, volume = {59}, pages = {259-274}, url = {http://www.cse.unsw.edu.au/~mit/Papers/TADA10.pdf} }
Thielscher, M. & Zhang, D.	From GDL to a Market Specification Language for General Trading Agents [Abstract] [BibTeX]	2009	Proceedings of the IJCAI-09 Workshop on General Game Playing (GIGA'09), pp. 83-90	inproceedings
Abstract: The idea behind General Game Playing is to build systems that, instead of being programmed for one specific task, are intelligent and ﬂexible 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.
BibTeX: @inproceedings{Thielscher2009a, author = {Michael Thielscher and Dongmo Zhang}, title = {From GDL to a Market Specification Language for General Trading Agents}, booktitle = {Proceedings of the IJCAI-09 Workshop on General Game Playing (GIGA'09)}, year = {2009}, pages = {83-90} }
Tong, S.	Roulette Wheel Selection Game Player [Abstract] [BibTeX]	2013	Honors Projects	misc	URL
Abstract: General Game Playing is a field of artificial intelligence that seeks to create programs capable of playing any game at an expert-level without the need for human aid. There are two major approaches to general game playing: simulation and heuristic. I focused on the move selection component of a common simulation strategy called Monte Carlo Tree Search. Traditionally, the selection step of Monte Carlo Tree Search uses an algorithm called Upper Confidence Bound Applied to Trees or UCT. In place of this algorithm, I investigated the applicability of a random roulette wheel style of selection. I studied the effectiveness of this roulette wheel style selection using tic-tac-toe and nim. The game player built from Roulette Wheel selection performed well against its opponents. It demonstrated the strengths of a flexible planning strategy throughout these games.
BibTeX: @misc{Tong2013, author = {Scott Tong}, title = {Roulette Wheel Selection Game Player}, year = {2013}, url = {http://digitalcommons.macalester.edu/mathcs_honors/30/} }
Torres, J.M., Martínez, D.C. & Simari, G.R.	Argumentación rebatible en agentes adaptativos de escenarios dinámicos [Abstract] [BibTeX]	2013	XV Workshop de Investigadores en Ciencias de la Computación (WICC)	inproceedings	URL
Abstract: Un agente inteligente es una entidad computacional que se desenvuelve en un entorno mediante sensores y efectores, capaz de actuar sin intervención de otros agentes o humanos. Un agente adaptativo es aquel que tiene especial preparación para reaccionar a variaciones inesperadas en su entorno. En este contexto, el área de Juegos Generales se enfoca en la creación de agentes capaces de aceptar las reglas formales de un juego estratégico y utilizarlas para aprender a jugar. Esto potencia el avance en conceptos como aprendizaje automatizado, representación de conocimiento, razonamiento y reconocimiento de patrones. La argumentación rebatible es un mecanismo de razonamiento no monótono que permite capturar aspectos del razonamiento del sentido común y la representación de información incompleta y potencialmente inconsistente. Los procesos argumentativos son inherentemente dialécticos y permiten modelar adecuadamente interacciones sociales entre agentes inteligentes. El objetivo general de esta investigación es la integración de formalismos de argumentación rebatible en agentes adaptativos en entornos dinámicos. Particularmente, el diseño y desarrollo de técnicas y tecnologías argumentativas para asistir a agentes capaces de enfrentar juegos generales como modelo de problema de razonamiento.
BibTeX: @inproceedings{Torres2013, author = {Torres, Juan Manuel and Martínez, Diego C. and Simari, Guillermo Ricardo}, title = {Argumentación rebatible en agentes adaptativos de escenarios dinámicos}, booktitle = {XV Workshop de Investigadores en Ciencias de la Computación (WICC)}, year = {2013}, url = {http://sedici.unlp.edu.ar/handle/10915/27345} }
Utgoff, P.E.	Feature Construction for Game Playing [Abstract] [BibTeX]	2001	Machines that learn to play games, pp. 131-152	inproceedings	URL
Abstract: To build an evaluation function for game-playing, one needs to construct informative features that enable accurate relative assessment of a game state. This chapter describes the feature construction problem, and suggests directions for dealing with shortcomings in the present state of the art.
BibTeX: @inproceedings{Utgoff2001, author = {Paul E. Utgoff}, title = {Feature Construction for Game Playing}, booktitle = {Machines that learn to play games}, publisher = {Nova Science Publishers}, year = {2001}, pages = {131-152}, url = {http://ml-www.cs.umass.edu/~utgoff/papers/nova-kubat.pdf} }
Waledzik, K. & Mandziuk, J.	Multigame playing by means of UCT enhanced with automatically generated evaluation functions [Abstract] [BibTeX]	2011	Vol. 6830Artificial General Intelligence, pp. 327-332	incollection	URL
Abstract: General Game Playing (GGP) contest provides a research framework suitable for developing and testing AGI approaches in game domain. In this paper, we propose a new modification of UCT game-tree analysis algorithm working in cooperation with a knowledge-free method of building approximate evaluation functions for GGP games. The process of function development consists of two stages: generalization and specification. Both stages are performed autonomously by the system and do not require human intervention of any kind. Eﬀectiveness of the proposed method is proved in three exemplar games selected from the GGP games repository.
BibTeX: @incollection{Waledzik2011, author = {Karol Waledzik and Jacek Mandziuk}, title = {Multigame playing by means of UCT enhanced with automatically generated evaluation functions}, booktitle = {Artificial General Intelligence}, publisher = {Springer Berlin / Heidelberg}, year = {2011}, volume = {6830}, pages = {327-332}, url = {http://www.mini.pw.edu.pl/~mandziuk/PRACE/AGI11_long.pdf} }
Walȩdzik, K. & Mańdziuk, J.	CI in General Game Playing - To Date Achievements and Perspectives [Abstract] [BibTeX]	2010	Vol. 6114Artifical Intelligence and Soft Computing, pp. 667-674	incollection	URL
Abstract: Multigame playing agents are programs capable of autonomously autonomously learning to play new, previously unknown games. In this paper, we concentrate on the General Game Playing Competition which defines a universal game description language and acts as a framework for comparison of various approaches to the problem. Although so far the most successful GGP agents have relied on classic Artificial Intelligence approaches, we argue that it would be also worthwhile to direct more effort to construction of General Game Players based on Computational Intelligence methods. We point out the most promising, in our opinion, directions of research and propose minor changes to GGP in order to make it a common framework suited for testing various aspects of multigame playing.
BibTeX: @incollection{Walȩdzik2010, author = {Walȩdzik, Karol and Mańdziuk, Jacek}, title = {CI in General Game Playing - To Date Achievements and Perspectives}, booktitle = {Artifical Intelligence and Soft Computing}, publisher = {Springer Berlin / Heidelberg}, year = {2010}, volume = {6114}, pages = {667-674}, note = {10.1007/978-3-642-13232-2_82}, url = {http://dx.doi.org/10.1007/978-3-642-13232-2_82} }
Wang, H., Emmerich, M. & Plaat, A.	Assessing the Potential of Classical Q-learning in General Game Playing [BibTeX]	2018	Vol. 1021Benelux Conference on Artificial Intelligence (BNAIC), pp. 138-150	inproceedings	URL
BibTeX: @inproceedings{Wang2018, author = {Hui Wang and Michael Emmerich and Aske Plaat}, title = {Assessing the Potential of Classical Q-learning in General Game Playing}, booktitle = {Benelux Conference on Artificial Intelligence (BNAIC)}, publisher = {Springer}, year = {2018}, volume = {1021}, pages = {138--150}, url = {https://arxiv.org/pdf/1810.06078} }
Waugh, K.	Faster State Manipulation in General Games using Generated Code [Abstract] [BibTeX]	2009	Proceedings of the IJCAI-09 Workshop on General Game Playing (GIGA'09), pp. 91-97	inproceedings
Abstract: Many programs for playing games rely on some type of state space search to choose their actions. It is well known that there is a correlation between the depth to which these programs search and the strength of their play. Unfortunately when playing games in the general game-playing competition, manipulating states requires expensive logical inference and as a result, programs that play these games cannot examine many states before they are required to act. Typically, these programs make use of a Prolog package to perform the required logical inference. These packages are not designed specifically for general game playing. As a result, there is great potential for improving the strength of play by designing a specialized package to perform the state manipulation tasks. In this paper we introduce gdlcc, a program that takes a general game description and creates a game specific C++ library for performing state manipulating tasks. Experimental results show that a program using this library, as opposed to a Prolog package, can examine between 60% and 1760% more states per action.
BibTeX: @inproceedings{Waugh2009, author = {Kevin Waugh}, title = {Faster State Manipulation in General Games using Generated Code}, booktitle = {Proceedings of the IJCAI-09 Workshop on General Game Playing (GIGA'09)}, year = {2009}, pages = {91-97} }
Zhang, D. & Thielscher, M.	Representing and Reasoning about Game Strategies [BibTeX]	2015	Journal of Philosophical Logic Vol. 44(2), pp. 203-236	article	DOI URL
BibTeX: @article{Zhang2015, author = {Dongmo Zhang and Michael Thielscher}, title = {Representing and Reasoning about Game Strategies}, journal = {Journal of Philosophical Logic}, year = {2015}, volume = {44}, number = {2}, pages = {203--236}, url = {https://link.springer.com/content/pdf/10.1007/s10992-014-9334-6.pdf}, doi = {http://dx.doi.org/10.1007/s10992-014-9334-6} }
Zhao, D.	Decomposition of Multi-Player Games [Abstract] [BibTeX]	2009	School: TU-Dresden	mastersthesis	URL
Abstract: Research in General Game Playing aims at building a system which can play arbitrary games. Moreover, the system should not only be able to play any game, but also to play the game fast. Time constraints for choosing moves are a main challenge to the system, especially with very large games. However, some large games can be split into many independent small games (called subgames), and the game can be solved by solving its subgames. This is called decomposition search. We will show in our work that the time complexity of decomposition search for decomposable games is exponentially smaller than that of normal game search.
BibTeX: @mastersthesis{Zhao2009, author = {Dengji Zhao}, title = {Decomposition of Multi-Player Games}, school = {TU-Dresden}, year = {2009}, url = {http://www.inf.tu-dresden.de/content/institutes/ki/cl/study/assignments/download/dengji_zhao_master_thesis.pdf} }
Zhao, D., Schiffel, S. & Thielscher, M.	Decomposition of Multi-Player Games [Abstract] [BibTeX]	2009	Vol. 5866Proceedings of the Australasian Joint Conference onArtificial Intelligence, pp. 475-484	inproceedings	URL
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.
BibTeX: @inproceedings{Schiffel2009d, author = {Dengji Zhao and Stephan Schiffel and Michael Thielscher}, title = {Decomposition of Multi-Player Games}, booktitle = {Proceedings of the Australasian Joint Conference onArtificial Intelligence}, publisher = {Springer}, year = {2009}, volume = {5866}, pages = {475-484}, url = {http://cgi.cse.unsw.edu.au/~mit/Papers/AI09b.pdf} }