IEEE Spectrum December, 2008 - 44

chacunÀsongoÛt: Adapting games to suit the tastes of
individual players is possible with passAge (player-specific
stories via Automatically generated events), a system the authors
have created for research purposes, based on the game engine of
Bioware's neverwinter nights, a fantasy adventure set in medieval
times. if the person playing passAge likes fighting, the game will
cue in combat opportunities, including perhaps a battle with a giant
spider [top]. if, however, the player prefers to amass wealth, the
game can offer such possibilities, too [bottom].

52

from such logs will play reasonably well-doing things
a person might do. It'll be a
long time before these bots
will be able to beat expert
human players, though. But
that's not the objective, after
all-they just need to make
for entertaining adversaries.
Jeff Orkin and Deb Roy of
MIT are undertaking a similar

NA * iEEE SpEctrum * DEcEmbEr 2008

program a computer to do
that is extraordinarily hard.
Why so? Studying an opponent should be easy, after all-
and it is, but only if you have
thousands of poker hands
to analyze. What do you do
if you have only a few? To
make matters worse, human
poker players make a point of
changing their style so as to
be hard to predict.
Right now, the best pokerplaying programs to come
out of our research group will
make money off your average
human player, and they are
beginning to beat even some of
the best in the world in organized competitions. This suggests that poker is just now
joining the ranks of chess and
checkers-games at which
computers have trounced even
world champions.

O

n e l e s s o n t h at
computer scientists
learned from working on chess and checkers is
that programs must strike a
balance in how they decide
what move to make next. At
one extreme, the computer can
look all the way to the end of
a game, examine every possible final position, and evaluate
whether each one constitutes
a win, a draw, or a loss. Then
it can work backward from
those possibilities, assuming best play by both sides at
every stage, to select the optimal move. But searching that
far ahead would take a great
deal of time-for chess, enough
for the sun to burn out.
The alternative is to use
an evaluation function that
incorporates knowledge of
the game, enough to go beyond
just rec- Continued on page 54
www.spectrum.ieee.org

the UniVerSity of alBerta gaMeS groUp/atari

tions and actions are not
nearly as constrained as
they are in a game like chess.
Researchers in our group
have used this formalism to
analyze computer logs of more
than 50 hours of tournamentlevel play between seasoned
Counter‑Strike teams. Soon,
we expect, computer bots
programmed to learn tactics

effort with something they call
The Restaurant Game, for which
they are applying machine
learning to the task of making
bots speak and act believably
in social settings. In this case,
the bots' behaviors are based
on observations gleaned from
more than 10 000 sessions of
human play.
Machine lear ning can
also pay off for poker, which
has become an especially hot
game in recent years with the
explosion of opportunities for
playing it online. The strongest programs for two-player
fixed-bet-size poker attempt
to calculate the mathematically optimal solution for winning each hand. It turns out
that finding such solutions
is computationally infeasible,
at least right now-there are
just too many possible combinations of cards and betting sequences. But members
of our research group have
devised ways to calculate
near-optimal strategies using
certain simplifying assumptions. For example, instead
of allowing four rounds of
betting-which is permitted in competition poker-
the program sets the limit at
three. By further reducing
the complexity of the game
in clever ways, the computational burden can be reduced
to a reasonable level. BioTools,
a commercial spin-off of our
research group in Edmonton,
has incorporated some of our
group's work in this area in
its Poker Academy software.
Although this program
plays poker pretty well, it
can't yet do what is most
required-spot and exploit
t he ot her player 's wea knesses. Figuring out how to
http://www.spectrum.ieee.org
Table of Contents for the Digital Edition of IEEE Spectrum December, 2008
