Playing the Artificial Intelligence Card
Ian Frank
Appears in `Scientist' Magazine. Published by University of Edinburgh,
1997.
Full text of article:
Rincewind looked blankly at Ysabell as words
like `rebiddable suit', `double finesse' and
`grand slam' floated through the velvet.
`Do you understand any of that?' she asked.
`Not a word,' he said.
`It sounds awfully complicated.'
On the other side of the door the heavy voice
said: DID YOU SAY HUMANS PLAY THIS FOR FUN?
`Some of them get to be very good at it, yes.
I'm only an amateur, I'm afraid.'
BUT THEY ONLY LIVE EIGHTY OR NINETY YEARS!
--- Terry Pratchett
`The Light Fantastic'
Yes, humans play Bridge for fun. Like most things that are fun,
though, it's difficult to enjoy alone. And, since it can sometimes be
hard to find others who share your taste in pastimes, ingenious
designers have come up with computer programs to substitute for live
participants. Recently, researchers at Edinburgh's Department of
Artificial Intelligence have also been turning their attention to
computer Bridge. They have produced their own Bridge system
(FINESSE), and made new discoveries about how to play complex games.
The First Moves
Gaming research has long been popular in Artificial Intelligence. In
the 1950s, the acceptance of the `Turing Test' focused attention on
the mimicking of human behavior as a test of machine intelligence. To
pass this test, a computer must answer questions from a human
interrogator in a way that makes it indistinguishable from a human
responder. Since this was beyond the capabilities of any practical
fifties technology, attention was turned instead to easier problems
such as simple, two-person games of strategy like chess and checkers.
Computer Challengers
Research on these games, and on chess in particular, has generated
significant advances in the theory of search algorithms and search
control, as well as motivating cognitive studies into the ways that
humans play games. In checkers, a program called Chinook is now the
strongest in the world (http://web.cs.ualberta.ca:80/~chinook/). In
chess, the world champion Gary Kasparov said that he `sensed a new
kind of intelligence across the table' during his 1996 match with
IBM's Deep Thought (http://www.chess.ibm.park.org/). Kasparov won this
match 3-1, after coming back from the shock of losing the first game.
This May, the computer designers get a second chance, with a re-match
pitting Kasparov against their upgraded contender, Deeper Blue
(http://www.chess.ibm.com/).
Bridge to the Unknown
Whatever the outcome of the Kasparov rematch, computers seem to be hot
on the heels of human game players. In Othello, the top 5 ranked
programs are all machines! The road to computer ascendancy may still
have a few corners left, though. Earlier this year, for example, there
was a burst of media articles about the game of Bridge. Whereas chess,
checkers and othello are two-person games with `complete information'
(you can see all the pieces), Bridge involves four players and has
`incomplete information' (the opponent's cards are hidden). Not
knowing the actual state of the game leaves computers guessing between
the large number of possible configurations. A Times leader article
on computer Bridge was titled `Deep thought, but very little nous'.
The conclusion of a New Scientist article was that `Computers may be
able to trounce grandmasters at chess, but you wouldn't want one as a
Bridge partner'.
Neither Here nor There
One of the reasons that computers find Bridge difficult was formalised
by the researchers at Edinburgh. They showed exactly what goes wrong
when the search algorithms that have been so successful for perfect
information games are tried on imperfect information games like
Bridge. Put simply, the typical search procedure makes a `tree' of
possible moves and then, starting at the leaves of the tree and
working to the base, selects the best move at each branching point.
This works for complete information games, but with games like Bridge
it runs into a problem: the best choice at one point in the tree can
depend on the choice you make at any other point, too. The
researchers at Edinburgh named this problem `non-locality'; no one
part of a game tree can be examined independently from the rest.
A Little Finesse
The Bridge system developed at Edinburgh, FINESSE, restricts the
available options at any stage of the search to a pre-determined set
of possibilities, or tactics. These tactics basically distill the
large diversity of card-play examples found in Bridge books into a
small number of concrete and distinct manoeuvres. With these tactics,
FINESSE becomes capable of constructing plans that look ahead right to
the end of the tree of possible actions. The tactics also help with
the problem of non-locality by allowing some portions of the game tree
to be easily identified as `bad responses' to some manoeuvres.
Another benefit of this approach is that the formalisation of a set of
tactics has the side-effect of increasing our knowledge about the game
itself. This is demonstrated by FINESSE's ability to give
English-language explanations for its actions. A typical explanation
might be `Finesse the Queen --- this leads to three tricks if West
holds the King'. The quality of these explanations is the subject of
ongoing research, as is the construction of an extra module for
allowing FINESSE to be used as a tutoring system for Bridge beginners.
The Future
On simple Bridge problems, FINESSE shows that non-locality occurs just
over a third of the time. This measurement has recently been confirmed
by Matt Ginsberg in America, who looked at larger examples. Ginsberg
thinks that he may have a theoretical solution to non-locality but
describes it as an `algorithmic nightmare'. Despite the protestations
by the heavy voice at the beginning of this article (actually, Death)
that `THEY ONLY LIVE EIGHTY OR NINETY YEARS!', then, it seems that
humans can still teach computers a thing or two about Bridge. For the
time being at least they should be able to trump the Artificial
Intelligence card.
[Ian Frank received his PhD from Edinburgh University in July 1996 and
is now a member of the Complex Games Lab at the
Electrotechnical Laboratory, Japan.]
|
