Having a formal description of a game is
one thing. Being able to use that
description to play the game effectively
is something else entirely. In this
segment we discuss strategies for building
general gameplayers. And we discuss some
of the difficulties that need to be
handled along the way. Since the end
descriptions are written in Logic, it's
obviously necessary for a gameplayer to do
some amount of automated reasoning. There
are two extremes here. One possibility is
for the gameplayer to process the game
description interpretively throughout a
game. Second extreme is for the player to
use the description to devise a
specialized program. And then use that
program to play the game. So effectively
automatic programming. But this is just an
introduction to general game playing.
We'll discuss just the first possibility
and leave it to you to think about the
second possibility and various hybrid
approaches. As we mentioned earlier, in
GDL we can conceptualize a state as a set
of facts that are true in that state. Such
as the facts here about the state of
Tic-Tac-Toe shown on the left. Computing
the legal moves in any such state is
straight forward. We simply use the rules
defining legality together with the facts
about the state, to deduce statements of
that legality. For example, in the state
shown on the right here, we can compute
the conclusions shown at the bottom. The O
player has six legal moves and the X
player has only one, namely the no op
action. Given a state, and actions for
each of the players, we can compute the
facts true in the next state using the
update rules. In the case shown here, we
use the update rule at the bottom to
compute the facts show in red on the
right. The other facts on the right are
computed using the other update rules.
These sentences mention next, they're,
they can then be rewritten with true in
place of next to form a description for
the resulting state. One way for a player
to decide on a course of action is to use
these two computations to expand the game
tree. Starting in a known state, it
computes the legal actions for itself and
its opponents, as we previously discussed.
For each combination of actions of the
players, it simulates, the combination to
compute the next state, and thereby
expands the tree. Here we see the
Tic-Tac-Toe tree expanded from this
initial state down one level. Repeating
this, we can expand the tree to two
levels, three levels, and so forth. Until,
finally, we encounter terminal states on
every branch. Such as the one shown here
in the middle of the bottom row. By
examining various branches, we can choose
the one that produces the best payoff.
now, of course, this choice depends on the
moves over the other players. And we must
consider all possible opponent moves, or
make some assumptions about things that
the other players will or will not do. In
principle, this procedure allows us to
identify the best possible strategy to
play the game. Unfortunately, even in
cases where there is a clear cut solution,
a tree may be so large as to make it
practically impossible for any player to
expand the game tree. Tic-Tac-Toe there's
just 5,000 states. It's a manageable
number, but there are more than ten to the
thirtieth states in chess. Using this
approach the player would run out of time
and memory long before finishing. The
alternative is to do incremental search,
when each move expanding the tree as much
as possible, and then making a choice
based on the apparent value of
non-terminal states. In traditional
game-playing where the rules are known in
advance the programmer can invent
game-specific evaluation functions to help
in this regard. For example in chess, we
know that states with higher piece count
and greater board control are better than
ones with less material or less control.
Unfortunately, this is not possible for
Jake, for GG and GGP program cannot invent
such game specific rules in advance as the
games rules aren't even known until the
game begins. The program must evaluate
states for itself. One possibility is to
use general heuristics. A number of such
heuristics have been proposed over the
years. gold proximity is one. Proponents
of this heuristic argued that, all other
things being equal, it's a good idea to
prefer states that are closer to goal
states than states that are farther away.
The distance here is usually judged by
similarity between the states. You know,
the number of facts in common in the
descriptions of the two states. Mobility
is another general heuristic. Proponents
argue that, all other things being equal,
it's better to move to a state that
affords the player greater mobility. And
that is more possible actions. It's better
than being boxed into a corner. And
symmetrically, proponents of mobility
argue that it's good to minimize the
mobility of one's opponents. Monte Carlo,
originally known as Depths Charge, is a
particularly powerful heuristic for
evaluations, evaluating states. Suppose a
player is comparing two states, with too
little time to search the entire game tree
descending from those states. The idea of
Depths Charge is to play through a few
complete games from each of the states
being compared, making random choices
until a terminal state is attained. After
doing this a few times we compare the
numbers of wins and losses and select the
state that leads to the largest number of
wins. All of these heuristics have been
shown to be effective in some games. Of
these, Monte Carlo is by far the most
successful. Unfortunately they're just
heuristics. They frequently fail,
sometimes with comical consequences. Final
match of GDP 06 is an example. The game
was cylinder checkers, that is checkers
played on a cylinder. The board here is,
well you can't see it, wraps around
vertically. Recall that in checkers a
player is permitted to move one of his
ordinary pieces, those pieces that are not
kings, one square forward on each turn.
Here red is moving from top to bottom and
black is moving from bottom to top. If a
piece is blocked by an opponent's player,
he can jump that player, that piece, if
there is an empty square on the other
side. Mor eover the player must make a
jump is one is available. Objective of the
game is to take all or as many of the
opponent's pieces as possible while
preserving one's own pieces. Here we see
this snapshot of the game. It's red's turn
to play. What should he do? And what do
you think he did? Here's the hint. Player
in this case was clone player. And, it
decided for some reason or the other that
limiting the opponent's mobility was a
good heuristic. If we were to move the
most rear most piece, the rear most piece,
black would have multiple possible moves.
However, if it were to move the piece in
front, black would be forced to capture
it's piece. In other words, it would have
at most one move. Clearly moving the
forward piece minimizes the opponents
mobility. So, that's what clone player
did. Actually the whole match played out
this way, with red giving black captures
at every single opportunity. It was sad to
watch, but also I have to say a little
comical. The moral is, that non-guaranteed
heuristics are sometimes useful, but they
are not always useful. That said, there
are some evaluation techniques that always
work. For example, there's no harm
preferring new states to states that have
previously been seen, provided there's a
way to get back to the original states.
Also, if a player is able to determine
some observable condition that corresponds
to actual distance from the goal, then
it's good to minimize that quantity.
Suppose the player, for example, were in a
cave, trying to get out. If it saw a
brighter light in one tunnel than in
another, it might go for the brighter
light. And finally, there are some states
that can be determined to be bad and
avoided. Even if other states are not
known to be good. For example, stepping
off the roof of a tall building is
probably not the best way to get to the
store. You know, at least not in the real
world. this discussion of game tree search
in heuristics reveals just how difficult
the general game playing problem is. Monte
Carlo works fairly well, but it breaks
down badly in certain cases just like the
others. Fortunately, there's another
complementary approach to general game
playing that has a lot of power. And that
is Metagaming. Metagaming is the process,
of analyzing and/or modifying the game, in
general. That is, out of the context of a
specific match. Metagaming is usually done
during the start collect period of a
match. Or sometimes during, in a separate
thread, while the game is being played.
typical Metagaming techniques include
presearching the game tree, optimizing the
game description and various ways of
compiling the game description to achieve
higher performance. Some cases it's
possible we formulate the game into one or
more simple, simpler games and were to
discover that there are some game specific
evaluation functions. As an example of,
reformulation potential, consider this
game called Hodgepodge. Hodgepodge is
actually two games glued together. Here we
show Chess and Othello. But it could be
any two games. One move in a joint game of
Hodgepodge corresponds to one move in each
of the two constituent's games. Winning
requires winning at least one of the two
games while not loosing the other. What
makes Hodgepodge interesting is that it's
factorial. That is, that it can be divided
into independents. Realizing that this can
have a dramatic benefit, see this consider
the size of the game tree for Hodgepodge.
Suppose that one game tree has, for one of
the subgames has a branch tree factor A
and the game tree factor for the other has
a branch tree factor B. And then the
branching factor of the joint game is A
times B. And the size of the fringe of the
game tree at level N is A times B to the
N. However the two games are independent.
Moving in one game does not affect the
state of the other game. So the player
really should be searching two smaller
game trees, one with a branching factor A
and the other with a branching factor B.
In this way, adepts ten there would only
be A to the N plus B to the N states. It's
a huge decrease in the size of the search
space. Factor ing's just one example of
game reformulation. There are many others.
For example, it may be possible to find
symmetries in games that cut down on
search, the search base. Some games are
bottlenecks that allow for type of
factoring. Consider for example, a game
made up of one or more sub games strung
together. Which is necessary to win one
game before moving on to the second game,
and the second before moving to the third
and so forth. In such cases, there's no
need to search to a terminal state in the
overall game. It's suffiicient to limit
search to the termination in the current
sub game These are examples of extreme
cases. But there are many simpler everyday
examples of finding structure of this sort
that can be, help out in curtailing a
search. The trick in metagaming is to
analyze or reformulate games without
expanding entire game trees. The
interesting thing about general game
playing is this, that sometimes the cost
of analysis is proportional to the size of
the description rather than the size of
the game tree, as the examples we were
just examining. Such players, cases,
players can expend a little time and gain
a lot in search savings. That's pretty
much it for our quick tour of general game
playing strategies. I, I want to close
this segment with an anecdote about my own
early experience in general game playing.
after building my first general game
player, I decided to see how well it
performed on a game of Tic-Tac-Toe. I let
it play blue while I played red. And
here's the state of the match after six
moves. I was intentionally playing badly
to see what my player would do. The
question is, what did my player do at this
point? Now, if you or I were playing blue,
we would probably play in the lower left,
maybe in the lower right, winning the
game. But, that's not what the player did,
instead it played in the upper right, the
next legal move in lexicographic order.
So, I scratched my head and wondered
exactly why I did this? I wondered if I
was too stupid to see the obvious win. in
the end, that's not wha t it, not at all
the case. It was playing perfectly. It had
already realized that it had a guaranteed
win, no matter what I did at this point,
so why not play in the upper right. It's
aggravating for me as a human to have my
defeat dragged out in this way. but this
sort of delay gratification is not unusual
in general game playing. It's just
frustrating for us humans to watch.