2014 GeneralGamePlaying

• (Genesereth & Thielscher, 2014) ⇒ Michael Genesereth, and Michael Thielscher. (2014). “General Game Playing.” In: Synthesis Lectures on Artificial Intelligence and Machine Learning Journal, March 2014.In: Synthesis Lectures on Artificial Intelligence and Machine Learning Journal, March 2014. doi:10.2200/S00564ED1V01Y201311AIM024

Subject Headings: General Game Playing; Single Player Game; Multiplayer Game; Small Game.

Cited By

• http://scholar.google.com/scholar?q=%222014%22+General+Game+Playing

Quotes

Author Keywords

• General game playing; artificial intelligence; logic programming; computational logic; intelligent agents; knowledge representation

Abstract

General game players are computer systems able to play strategy games based solely on formal game descriptions supplied at “runtime” (in 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.

Preface

General game players are computer system s able to play strategy games based solely on formal game descriptions supplied at “runtime”. (In 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.

General Game Playing (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 for defining rationality in a way that takes into account problem representation and complexities like incompleteness of information and resource bounds. It has practical application s 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. (1) It presents the theory of GGP 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.

Although the book is elementary, it does assume some basic background. First of all, readers should be familiar with Symbolic Logic. Game descriptions are written in the language of Symbolic Logic, and it helps to be able to read and write such descriptions. Second, readers should be familiar with the concepts of computer programming. At the very least, they should be able to read and understand program fragments written in modern programming languages. We use Javascript in all of our examples. Javascript is fairly simple. If readers are familiar with languages like Java and C, they should be able to read Javascript without any further training. Before getting started, we want to acknowledge the contributions of various people. First of all, there are the various students who over the years helped to craft the course, notably Nathaniel Love, David Haley, Eric Schkufza, Evan Cox, Alex Landau, Peter Pham, Mirela Spasova, and Bertrand Decoster. Special mention goes to Sam Schreiber for maintaining the GGP configurable player and the Java code base used by many students. He is also the creator and maintainer or ggp.org, a website for all things GGP.

And thanks as well to the students who over the years have had to endure early versions of this material, in many cases helping to get it right by suffering through experiments that were not always successful. It is a testament to the intelligence of these students that they seem to have learned the material despite multiple bumbling mistakes on our part. Their patience and constructive comments were invaluable in helping us to understand what works and what does not.

Table of Contents

Preface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xv
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Games . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 Game Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.4 Game Management . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.5 Game Playing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.6 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2 Game Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.2 Logic Programs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.3 Game Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.4 Game Description Language . . . . . . . . . . . . . . . . . . . . . . . 20
2.5 Game Description Example . . . . . . . . . . . . . . . . . . . . . . . . 21
2.6 Game Simulation Example . . . . . . . . . . . . . . . . . . . . . . . . 24
2.7 Game Requirements . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.8 Prefix GDL. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3 Game Management . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.2 Game Management . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.3 Game Communication Language . . . . . . . . . . . . . . . . . . . . . 32
3.4 Game Play . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
4 Game Playing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
4.2 Infrastructure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
4.3 Creating a Legal Player . . . . . . . . . . . . . . . . . . . . . . . . . 38
4.4 Creating a Random Player . . . . . . . . . . . . . . . . . . . . . . . . 41
5 Small Single-Player Games . . . . . . . . . . . . . . . . . . . . . . . . 43
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
5.2 8-Puzzle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
5.3 Compulsive Deliberation . . . . . . . . . . . . . . . . . . . . . . . . . 45
5.4 Sequential Planning . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
6 Small Multiple-Player Games . . . . . . . . . . . . . . . . . . . . . . . 51
6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
6.2 Minimax . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
6.3 Bounded Minimax Search . . . . . . . . . . . . . . . . . . . . . . . . 56
6.4 Alpha-Beta Search . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
7 Heuristic Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
7.2 Depth-Limited Search . . . . . . . . . . . . . . . . . . . . . . . . . . 67
7.3 Fixed-Depth Heuristic Search . . . . . . . . . . . . . . . . . . . . . . . 68
7.4 Variable Depth Heuristic Search . . . . . . . . . . . . . . . . . . . . . . 70
8 Probabilistic Search . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
8.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
8.2 Monte Carlo Search . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
8.3 Monte Carlo Tree Search . . . . . . . . . . . . . . . . . . . . . . . . . 78
9 Propositional Nets . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
9.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
9.2 Propositional Nets . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
9.3 Games as Propositional Nets . . . . . . . . . . . . . . . . . . . . . . . 85
10 General Game Playing With Propnets . . . . . . . . . . . . . . . . . . 89
10.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
10.2 Propositional Nets as Data Structures . . . . . . . . . . . . . . . . . . 89
10.3 Marking and Reading Propositional Nets . . . . . . . . . . . . . . . . . . 92
10.4 Computing Game Playing Basics . . . . . . . . . . . . . . . . . . . . . 94
11 Factoring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
11.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
11.2 Compound Games with Independent Subgames . . . . . . . . . . . . . . . . . . 98
11.3 Compound Games with Interdependent Termination . . . . . . . . . . . . . . . . . . 101
11.4 Compound Games with Interdependent Actions . . . . . . . . . . . . . . . . . . 102
11.5 Conditional Independence . . . . . . . . . . . . . . . . . . . . . . . . 104
12 Discovery of Heuristics . . . . . . . . . . . . . . . . . . . . . . . . . 107
12.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
12.2 Latches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
12.3 Inhibitors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
12.4 Dead State Removal . . . . . . . . . . . . . . . . . . . . . . . . . . 108
13 Logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
13.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
13.2 Unification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
13.3 Derivation Steps (without Negation) . . . . . . . . . . . . . . . . . . 114
13.4 Derivations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
13.5 Derivation Tree Search . . . . . . . . . . . . . . . . . . . . . . . . . 117
13.6 Handling Negation . . . . . . . . . . . . . . . . . . . . . . . . . . 119
14 Analyzing Games with Logic . . . . . . . . . . . . . . . . . . . . . . . 129
14.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
14.2 Computing Domains . . . . . . . . . . . . . . . . . . . . . . . . . . 129
14.3 Reducing the Domains Further . . . . . . . . . . . . . . . . . . . . . . 133
14.4 Instantiating Rules . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
14.5 Analyzing the Structure of GDL Rules . . . . . . . . . . . . . . . . . . 139
14.6 Rule Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
14.7 Using Rule Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . 142
14.7.1 Determining the Equivalence of Game Descriptions . . . . . . . . . . . . . . 142
14.7.2 Computing Symmetries . . . . . . . . . . . . . . . . . . . . . . 142
14.8 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
15 Solving Single-Player Games with Logic . . . . . . . . . . . . . . . . . . 151
15.1 Answer Set Programming . . . . . . . . . . . . . . . . . . . . . . . . 151
15.2 Adding Time to GDL Rules . . . . . . . . . . . . . . . . . . . . . . . 152
15.3 Solving Single-Player Games with Answer Set Programming . . . . . . . . . . . . . 156
15.4 Systems for Answer Set Programming . . . . . . . . . . . . . . . . . . 158
15.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158
16 Discovering Heuristics with Logic . . . . . . . . . . . . . . . . . . . . 161
16.1 Discovering Heuristics with Answer Set Programming . . . . . . . . . . . . . . . . . . 161
16.2 Goal Heuristics. . . . . . . . . . . . . . . . . . . . . . . . . . . . 162
16.3 Fuzzy Logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
16.4 Using the Goal Heuristics . . . . . . . . . . . . . . . . . . . . . . . . 166
16.5 Optimizations and Limitations . . . . . . . . . . . . . . . . . . . . . . 167
16.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168
17 Games with Incomplete Information . . . . . . . . . . . . . . . . . . 171
17.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
17.2 GDL-II . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
17.3 Blind Tic-Tac-Toe . . . . . . . . . . . . . . . . . . . . . . . . . . . 172
17.4 Card Games and Others . . . . . . . . . . . . . . . . . . . . . . . . 177
17.5 GDL-II Game Management . . . . . . . . . . . . . . . . . . . . . . . 178
17.6 Playing GDL-II Games: Hypothetical States . . . . . . . . . . . . . . . . . . 180
17.7 Sampling Complete States . . . . . . . . . . . . . . . . . . . . . . . . 181
17.8 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186
18 Games with Historical Constraints . . . . . . . . . . . . . . . . . . . . 189
18.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189
18.2 System Definition Language . . . . . . . . . . . . . . . . . . . . . . . 189
18.3 Example–Tic-Tac-Toe . . . . . . . . . . . . . . . . . . . . . . . . . 190
18.4 Example–Chess . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194
19 Incomplete Game Descriptions . . . . . . . . . . . . . . . . . . . . . . 199
19.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199
19.2 Relational Logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199
19.3 Incomplete Game Description Language . . . . . . . . . . . . . . . . . . 203
19.4 Buttons and Lights Revisited . . . . . . . . . . . . . . . . . . . . . . . 203
19.5 Complete Description of Buttons and Lights . . . . . . . . . . . . . . . . . . 205
19.6 Incomplete Description of Buttons and Lights . . . . . . . . . . . . . . . . . . 208
19.7 Playing Buttons and Lights with an Incomplete Description . . . . . . . . . . . . . . 208
20 Advanced General Game Playing . . . . . . . . . . . . . . . . . . . . . 211
20.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211
20.2 Temporal General Game Playing . . . . . . . . . . . . . . . . . . . . 211
20.3 Inductive General Game Playing . . . . . . . . . . . . . . . . . . . . . 211
20.4 Really General Game Playing . . . . . . . . . . . . . . . . . . . . . . 212
20.5 Enhanced General Game Playing . . . . . . . . . . . . . . . . . . . . 212

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2014 GeneralGamePlaying	Michael Genesereth Michael Thielscher			General Game Playing				10.2200/S00564ED1V01Y201311AIM02		2014