In general game playing, every game can be
thought of as a state graph, like the one
shown here. The nodes represent states and
the arcs represent actions. For example,
if the player performs action A in state
S1, the world goes into state S2. Action B
leads to state S3, action C leads to state
S4, and action D has no effect on, in
other words the world stays in the same
state. Start state is denoted by an
incoming arrow. Here, s1 is the start
state. Goal states for the player are
denoted by color. Here, s8 and s11 are
goal states for the player. more
generally, in general game playing, we
allow states with varying degrees of
goalhood. Ranging from zero meaning bad to
100 meaning very good. Terminal states are
denoted here by slightly heavier circles.
barely visible. In this case, that's
three, S9 and S11 are terminal states.
Beginning in the start state, the player's
objective is to arrive at a terminal state
that's also a goal state. Or in the case
of multiple levels of goals, to arrive at
a terminal state that has as high a reward
as possible. In the case of multiple
players with simultaneous moves, the arcs
become multi-arcs, with one arc for each
combination of the player's actions. Here,
here's an example of a simultaneous move
game with two players. If in status one
both players perform action a, we follow
the arc labeled aa. If the first player
does a, and the second player does b, we
follow the arc ab. And similarly for ba
and bb. We also had different goals for
the different players notated with
different colors here in brown and purple.
Multi-player games are a little more
difficult than single player games as each
player cannot control the other player's
actions, so it's more search involved.
Okay, that's pretty much it. Most purists
strategy games can be conceptualized, can
be thought of in this framework. Since all
the state graphs that we're considering
are finite. It is possible, at least in
principle, to describe such games in the
form of lists, states, actions and tables.
That express legality, goals, update and
so forth. Unfortunately direct
representations are not practical in most
cases. Even though the numbers of states
and actions are finite, they can be
extremely large. And the tables relating
them can be even larger. for example, in
chess there are thousands of possible
moves, and more than ten to the thirtieth
states. In order to be practical we need
somewhat more compact en, encoding. Okay.
This is the job of the Game Description
Language, or GDL. GDL's a formal language
for encoding finite discrete games. It
supports compact representation of games
by one relying on a conceptualization of
games states as databases. And two, using
logic to define the notions of legality,
update, goals, terminations, so forth. In
the vast majority of games, states and
actions have composite structure that
allows us to define a large number of
states and actions in terms of a smaller
number of more fundamental entities. In
games like tic-tact-toe, states are not
monolithic. They can be conceptualized in
terms of cells and marks. Here for example
are two representations of a state in a
game of tic-tact-toe. On the left we have
the traditional two dimensional
representation. On the right we have a
representation of the state as a database
of facts. the first fact says that the
cell in the first row in the first column
contains an X. Second cell in the first
row in the, the, second column contains a
blank, denoted here by the constant B and
so forth. And finally this last assertion
says that it's O's turn to make a mark. In
other words it has control. Okay. Using
this conceptualization of states, we can
define the game of tic tac toe with a
small database of logical sentences, as
shown here. these are all sentences in her
brown logic syntax written with the pure
ASCII character set. First, we define the
roles of the game. There are two players
named X and O. Next we characterize the
initial state. In this case, all of the
cells are blank and X has control. Next we
characterize the player's legal actions.
GDL makes extensive use of reductions
which are written using the left arrow
operator. A reductoin's simply an
implication in reverse, with the
conclusion first and the conditions
afterward. It's more convenient to write
things this way than to use forward
implications. Also in GDL, symbols that
begin with capital letters are variables,
and those that begin with lower case
letters or digits are constants. For
example, capital P, capital X and capital
Y here, are variables. While lower case b,
lower case x, lower case y and noop are
object constants. Okay, with that
introduction, lets look at this definition
for legality. First sentence says that
it's legal for an arbitrary player P to
mark the cell in row X and column Y
provided that it contains a blank and
provided that P has control. Second
sentence tells us that it's legal for x to
do the no-op action if o has control. The
no-op action means the x does nothing, it
passes. Analogously, it's legal to o to do
the no-op action if x has control. These
three axioms assure us that both players
have legal moves at every non-terminal
state. Okay. Next we look at the update
rules for the game. The cell is marked
with an X or an O if the corresponding
player marks that cell in the previous
step. sentence two says that it
self-contains a mark that is not blank,
then it retains that mark on the
subsequent state. The cell is blank and is
not marked in that step, then it remains
blank. And finally, the last two sentences
tell us that control alternates on each
play. The game terminates if either player
has a line of marks or if there are no
empty cells. The goal is to find the
players' rewards. The X player gets 100
points if there's a line of X's and no
line of O's. Gets 50 points if neither
player has a line. And he gets zero points
if there's a line of O's and no line of X,
no line of O's and no line of Xs. The
rewards for the O player are analogous.
And finally, we define some helper
relations. A line is a roll of marks of
the same type or a column or a diagonal. A
roll of marks means that there are three
marks with the same first coordinate.
Column of marks means that there are three
marks with the same second coordinate and
a diagonal is a line from the upper left
to the lower right or from the upper right
to the lower left. And that's it. That's
the entire description of the Tic-Tac-Toe
rules, okay? One more final twist on game
description, and that's obfuscation. In,
in order to prevent programmers from
building in specialized capabilities that
recognize based on specific words in game
descriptions, it's common for game
managers to obfuscate descriptions before
game begins. All words are consistently
replaced by nonsense words, as in the
example shown here. The only exceptions
are variables and a selection of constants
common to all games such as next, does,
true, and so forth.