Time for another field trip. Not a
physical trip, but a virtual one. Rather
than discussing new ideas and logic, we'll
be instead looking at an application of
the ideas we've already seen. The
destination for our trip this time is the
sub-field of artificial intelligence
called general game playing. As we shall,
shall see, GGP is an interesting
application in its own right. It's
intellectually engaging, and I think more
than a little fun. But it's more than
that, It serves as an analogue for
applications of logic in other areas such
as business and law and science and
engineering. And more fundamentally, it
raises questions about the nature of
intelligence. And serves as a laboratory
in which to evaluate competing approaches
to artifical intelligence. We'll return to
these points a little later in the lesson.
For now let's just begin at the beginning.
Playing strategy games like chess and
checkers, couples intellectual activity
with competition. By playing games we can
exercise and improve our intellectual
skills. The competition, that's
excitement, allows us to compare our
skills to those of others. The same
motivation accounts for interest in
computer game playing as a test bit for
artificial intelligence. Programs that
think better should be able to win more
games. And so we can use competition as an
evaluation technique for intelligent
systems. Unfortunately, building programs
to play specific games has limited value
in AI. To begin with, specialized game
players are very narrow. They can be good
at one thing but not another. Deep Blue,
for example, may have beaten the world
chess champion, but has no clue at all how
to play checkers and it cannot even check,
balance a checkbook. The second problem
with specialized game playing systems is
that they do only part of the work. Most
of the interesting analysis and design is
done in advance by their programmers. The
systems themselves might just as well be
tele-operated. Well, all is not lost. Many
believe that the idea of game playing can
be used to good effect, to inspire and
evaluate good work in artificial
intelligence, but it requires moving more
of the men-, mental work to the computer
itself. And, this can be done by focusing
our attention on general game playing.
Gen-, general game players are systems
able to play arbitrary strategy games
based solely on formal descriptions
supplied at run time. In a typical general
game playing session, the players know
nothing about the game in advance. Once
the game begins, they receive a game
description and based solely on that
description they must figure out how to
play the game legally and effectively.
Furthermore, they must deal with
uncertainty about the actions of the other
players and resource bounds in the form of
a game clock that limits their computation
time. Unlike specialized game players such
as Deep Blue, general game players cannot
rely on algorithms designed in advance for
specific games. General game playing
expertise must depend on intelligence on
the part of the game player, and not just
intelligence of the programmer of the game
player. In order to perform well, general
game players must incorporate multiple
artificial intelligence technologies such
as knowledge representation, reasoning,
learning and rational decision making.
Also, unlike generalized, specialized game
players. General game players must be able
to play different kinds of games. They
should be able to play simple games, like
Tic Tac Toe, and complex games like Chess.
Games with simultaneous moves like
Diplomacy, and games of alternating play,
like Risk. Games with complete information
or games with incomplete information for
example Battleship. Games with different
numbers of players, Black swirl, Rubik's
cube, Chess, Chinese Checkers. Games with
or without communication among the
players, for example Bughouse chess. Zero
sum games and cooperative games. The
various aspects to general game playing
and we need to address them all in order
to understand the field. In this lesson,
we'll start by, discussing game
description. Here as we shal l see logic
plays a key role as a language for writing
game rules. Next, we'll discuss, game
management with the focus on use of
technology to coordinate the play among
automated game players and possibly
humans. We then sketch the main techniques
used in today's general game playing
programs and we'll, we'll look at some of
the problems that have yet to be solved.
Finally, we will close with some
philosophical remarks about general game
playing and an overview of international
general game playing competition. before
closing however, there are a couple of
introductory words worth mentioning.
General game playing resembles a couple of
other disciplines. There are significant
overlaps but there are also some important
differences. And it's worthwhile to keep
these relationships in mind as we look at
the details of general game playing. Like
general game theory traditional game
theory is concerned with games in general.
However, game theory is primarily
concerned with the analysis of game trees.
There's no concern for how these trees are
communicated to the players, or for how
the descriptions are used. There's also
little concern for tradeoffs between
deliberation and action. In general game
playing, the game tree is communicated at
run time. Hence, there is an emphasis on
description, and use of this description.
And by bringing game description into the
picture, there's a possibility of more
refined notions of rationality. General
game playing also resembles the field of
action planning. In fact, they're very
closely related. The inputs are the same,
the state machine with initial states and
goal states. However, the purpose is
slightly different. In the case of
planning, the objective is to create a
plan that transforms the initial state
into a goal state. There's no execution
environment and hence no concern for
deliberation, inaction, and interleaving
of those activities. In general game
playing, the objective is to actually get
the world into the goal state, to actually
execute the actions. The main differe nce
is the presence in GGP of an execution
environment that allows the general game
player to execute its plan. As a result,
players can interleave planning and
execution. By so doing they can sometimes
solve problems that would be unsolvable by
pre-planning alone, as we shall see.