## 2.1 IntroductionThe most significant characteristic of General Game Playing is that players do not know the rules of games before those games begin. Game rules are communicated at runtime, and the players must be able to read and understand the descriptions they are given in order to play legally and effectively. In General Game Playing, games are defined in a formal language known as GDL. GDL is a logic programming language. It is similar to other logic programming languages, such as Datalog and Prolog and Epilog, except that (1) it has restrictions that assure that all questions of logical entailment for any description in the language are decidable and (2) it includes some reserved words that specialize it for the description of games. This chapter is an introduction to GDL and the issues that arise in using it to describe games. We start with an introduction to the modeling games as dataset graphs, and we illustrate with the game of Tic Tac Toe. We then introduce GDL, and we show how to encode the rules of Tic Tac Toe as rules in GDL. Finally, we talk about additional features of games that ensure that they are interesting. ## 2.2 Games As Dataset GraphsThe GDL model of games starts with entities and relations. In our examples here, we refer to entities and relations using strings of letters, digits, and a few non-alphanumeric characters (e.g. "_"). For reasons described below, we prohibit strings beginning with upper case letters; all other combinations are acceptable. Examples include The set of all entities that can be used in a game is called the The A game Given a game schema, we define a The In GDL, propositions are usually partitioned into disjoint classes, viz. base propositions and effectory propositions (more commonly called ## 2.4 Tic Tac Toe As a Dataset GraphAs an example, let us look at a conceptualization of the states for the game of Tic-Tac-Toe as datasets. We can think of states in terms of two relations. The
In Tic Tac Toe, there is only one type of action a player can perform - it can mark a cell. The binary operation
The dataset shown below represents the initial state of Tic Tac Toe. All of the cells are blank and the x player is in control.
Given the rules of Tic Tac Toe, all nine possible moves are legal in this state.
The graphs consists of all feasible states with arcs defining transitions. Too large too draw (here some 5040) states. ## 2.5 Game Description LanguageIn GDL, we fix the meanings of some words in the language for all games (the There are 101 game-independent object constants in GDL, viz. the base ten representations of the integers from 0 through 100, inclusive, i.e. 0, 1, 2, ... , 100. These are included for use as utility values for game states, with 0 being low and 100 being high. GDL has no game-independent function constants. However, there are seven game-independent relation constants, viz. the ones shown below. `role(`*a*`)`means that*a*is a role in the game.`base(`*p*`)`means that*p*is a base proposition in the game.`action(`*a*`)`means that*a*is a feasible action in the game.`init(`*p*`)`means that the proposition*p*is true in the initial state.`legal(`*a*`)`means it is legal for the player in control to play action*a*in the current state.`goal(`*r*`,`*n*`)`means that player the current state has utility*n*for player*r*.`terminal`means that the current state is a terminal state.
A GDL description is an open logic program with the following input and output relations. (1) A GDL game description must give complete definitions for We can describe these concepts abstractly. However, experience has shown that most people learn their meaning more easily through examples. In the next section, we look at a definition of one particular game, viz. Tic Tac Toe. ## 2.6 Tic Tac Toe Game RulesWe begin with an enumeration of roles. In this case, there are just two roles, here called role(white) role(black) We can characterize the propositions of the game as shown below. base(cell(M,N,x)) :- index(M) & index(N) base(cell(M,N,o)) :- index(M) & index(N) base(cell(M,N,b)) :- index(M) & index(N) base(control(white)) base(control(black)) We can characterize the feasible actions for each role in similar fashion. action(mark(M,N)) :- index(M) & index(N) index(1) index(2) index(3) Next, we characterize the initial state by writing all relevant propositions that are true in the initial state. In this case, all cells are blank; and the init(cell(M,N,b)) :- index(M) & index(N) init(control(x)) With our declarations out of the way, we can get down to the dynamics of the game. First, we define legality. It is legal to mark a cell if that cell is blank.
In GDL, symbols that begin with capital letters are variables, while symbols that begin with lower case letters are constants. The Next, we look at the update rules for the game. The first rules says that, if
Goals. The x player gets a score of 100 if there is a line of x's and no line of o's. It gets 0 points if there is a line of o's and no line of x's. Otherwise, it gets 50 points. The rewards for the o player are analogous. The line relation is defined below.
Supporting concepts. A line is a row of marks of the same type or a column or a diagonal. A row of marks mean thats there three marks all with the same first coordinate. The column and diagonal relations are defined analogously.
Termination. A game terminates whenever there is a line of marks of the same type or if the game is no longer open, i.e. there are no blank cells.
Note that, any of these relations can be assumed to be false if it is not provably true. Thus, we have complete definitions for the relations Although GDL is designed for use in defining complete information games, it can be extended to partial information games. That said, the resulting descriptions are more verbose and more expensive to process. ## 2.7 Game RequirementsThe definitions in Section 2.2 constrain GDL to game descriptions from which it is possible to compute the legal actions of all players for each state and from which it is possible to compute the next state for each state from the actions of all players. However, there are additional constraints that limit the scope of GDL to avoid problematic games.
In general game playing, all well-formed single player games should be strongly winnable. Clearly, it is possible to generate game descriptions in GDL which are not well-formed. Checking game descriptions to see if they are well-formed can certainly be done in general by using brute-force methods (exploring the entire game tree); and, for some games, faster algorithms may exist. Game descriptions used in GGP competitions are always well-formed. However, in this book, we occasionally look at games that are not well-formed for reasons of simplicity or pedagogy. |