AI Expert Newsletter
AI - The art and science of making computers do interesting
things that are not in their nature.
Have you ever played Hasbro's (was Avalon Hill's) game Diplomacy?
I've only played it a few times but found it to be one of the best
games I'd ever played. It requires seven players, each running a
European country around World War I. In many ways its a classic
war game, where each player has armies that can be deployed and
set to attack neighboring countries and/or defend held ground.
The players make their moves simultaneously, at least logically
so. Each player writes down the movements for his/her armies and
then all the moves are revealed at once. Each of the conflicts around
the board is resolved. For example, France may have aligned some
forces to attack Germany and Germany placed some defenders at the
border. Depending on the number of units of each, the attack succeeds
or fails and the pieces adjusted on the board to reflect the result
of the conflict. Once all the conflicts are resolved, the cycle
continues, until one player/country has conquered Europe.
What makes the game so fascinating is that no country has sufficient
forces to dominate the game. So Germany, for example, can invade
Russia, or invade France, or defend one or the other border, but
can't do it all. So how does the German player decide? This is where
the game gets it name. Before each move there is a "diplomacy"
period where the players talk to each other in quiet corners of
the room. Germany and France might decide to become allies, and
both move to attack Russia, freeing each from having to worry about
their common border.
1 - The game board for face-to-face play.
This is where the game gets nasty. Germany might also make a similar
deal with Russia. And turn and attack France, whose borders were
left open because France thought they were allied with Germany.
The skill of the game all resolves around the ability of a player
to make strategic alliances, retain the trust of some allies while
simultaneously betraying others, and thus manipulate his/her country
into a position of European dominance. And its all very real, because
if the French player saw the German player talking to the Russian
player, then he/she would want to know why, and if Germany was planning
to betray France, he/she would have to have a good reason to tell
to France to maintain France's trust.
Fascinating. The problem was, at least when I played it, is in
the process of winning the game, you lose friends and playing partners.
So it might cost two or three friends a game. They sell t-shirts
for Diplomacy with a logo of one country stabbing another in the
back. The game is also relatively tedious to play, as it takes a
while to go through each cycle of negotiation, move planning, and
then resolution of conflicts.
How good is Diplomacy? Rumors were that it was very popular in
the Kennedy White House, with the Kennedy's and Kissenger et.al.
playing heated games into the night. During those days of the Cold
War, I always wondered if there weren't Soviet bugs in the White
House picking up quiet conversations between Kennedy and Kissenger
about plans to invade Russia.
And how much did the artificial environment of the game Diplomacy
influence decision making of international policy makers of the
Digressing: It seems clear that experience with the games of chess
and/or go influence military leader's strategic approach to war.
I was recently reading about WW II in the Pacific where I learned
that the Japanese intent was not to invade America, but rather to
threaten that in order to obtain and expand their sphere of influence
in Asia. A very go-like idea. They were surprised that the Americans
did not accept that; instead the American intent was to go straight
to Tokyo. A very chess-like idea. Neither side understood the other's
thinking the Americans afraid the Japanese were intent on
reaching Washington (chess-like); the Japanese thinking the Americans
would accept a resolution where both wound up with territory in
the Pacific (go-like).
Computers solve the two major problems with the game. You can now
play online, so a computer handles the mechanics of conflict resolution;
and you can play with people all over the World, so you alienate
strangers instead of friends on your march to dominance.
2 - Board position from a game in progress at the Diplomatic Pouch's
And now the fun bit, trying to get a computer to play Diplomacy.
(Most of this material is derived from Danny Loeb's article on the
Diplomacy programming project, see links.)
The first problem is to devise a language that can be used to communicate.
While it might be tempting to try to solve the natural language
problems in understanding negotiating discourse, that is really
a different sort of problem; so the developers created a formal
language, called the DPP Protocol, that is expressive enough to
communicate about possibilities in the realm of Diplomacy. Here's
a sample that threatens another player with war if he/she takes
one of your cities:
France: "SND ENG (IFF DMZ(PAR BRE MAR) THN PCE ELS NOT(PCE))"
The diplomat discussed in Danny Loeb's article is the Bordeauz
Diplomat. It has two main components, the strategic core and the
negotiator. The strategic core provides all the capabilities of
analyzing the values of positions and moves. It doesn't think, but
rather just provides the analysis necessary for the negotiator.
The strategic core needs to determine the best moves for either
an individual country or an alliance. At first glance, search trees
similar to those imployed in two-player games might appear like
a good approach for finding "best" moves. But the mathematical
combinations are staggering. Unlike chess, which has 20 posible
opening moves, seven player Diplomacy, with its "simultaneous"
movement, has over four quadrillion possible opening moves.
Not only does this prohibit looking more than one move in advance,
it makes it very difficult to simply find a "best" next
move. The solution they game up with was to use a genetic search
algorithm to find the next "best" move. Seed moves are
used to start the search, and then those moves are randomly mutated
in the hopes of finding better moves.
The strategic core is also used to evaluate potential new alliances,
comparing their value to existing ones. Moves that are communicated
as rumor or threats can be evaluated using the strategic core to
see if the they are valid. The genetic search engine is used for
that purpose as well, with the proposed move used as a seed. If
after a number of cycles of evolution the move is still being considered,
then it is a plausable move.
The moves of the last turn are processed by the strategic core
to detect new alliances and backstabbing betrayals. This information
all becomes useful to the negotiator in determine the trustworthiness
of a potential ally.
Trustworthiness evaluation is also based on mutual gain. An ally
who no longer gains by the alliance is deemed untrustworthy. In
other words, it's critical to ask "what's in it for you?"
Development kits for creating diplomats are available in a number
of languages, including C++ and Java. Check them out and let me
know what you think.
Standard Meta-Lamguage (SML/NJ)
LCS, a parallel processing version of SML, is a functional language
used to build the Diplomacy AI. A functional language differs from
conventional programming languages in that variable values cannot
be changed. In fact, they are not called variables, but rather bindings
to symbolic names. Once a symbolic name is bound, the value sticks.
On the one hand, this makes it difficult to do some standard sorts
of programming things. On the other hand, it allows for a very clean
declarative specification of a program because there is no state.
In other words, what you see is what you get. In this way it is
similar to logic programming.
ML also supports strict typing, making it harder than normal to
create buggy programs and also making it possible to prove program
correctness much more readily than with a conventional program.
It supports polymorphism, which makes it possible to create generic
functions that work on various types.
(Most of the following material is taken from Andrew Cumming's
tutorial, see links.)
Programs in a functional language are, as the name implies, a collection
of functions. For example, a function that doubles a value in ML
fun double x = 2 * x;
Functions refer to other functions, so to quadruple a value:
fun quadruple x = double(double x);
ML is strongly typed. It has the basic types like string and integer,
and complex types of lists and tuples. A list is a list of items
of the same type. A tuple is fixed length collection of a variety
of types, including complex types. Between tuples and lists, ML
provides for very powerful data representation.
Here's an example of tuple with its associated type declaration:
(true,3.5,"x", (4,5) ) : bool * real * string * (int * int)
And a list:
[(2,3),(2,2),(9,1)] : (int * int) list
ML has a pattern-matching algorithm that examines complex types
and generates bindings for embedded names in those types. For example,
at the ML interpreter prompt, which is hyphen (minus sign) -, one
can ask to bind one complex type to another.
- val (d,e) = (2,"two");
val d = 2 : int
val e = "two" : string
In this case the two symbolic names within the tuple (d,e) are
Given that you can't change a binding, iterative loops of conventional
languages don't work. As you might expect, recursion is used instead
for looping. Here's the classic factorial definition as expressed
fun factorial 0 = 1
| factorial n = n * factorial(n-1);
And this leads to the possibility of writing powerful functions
for processing lists. Here's how to sum a list of integers:
fun sum nil = 0
| sum(h::t) = h + sum t;
The result is a language that, like Lisp and Prolog, is an expressive
language for implementing AI applications that generally require
symbolic manipulation, pattern-matching and search. It is a good
tool for building a Diplomacy AI.
- Diplomacy AI Center resource Web site.
- Brian Robert's collection of links to articles about Diplomacy
AI. He is also the author of a Diplomacy bot.
www.diplom.org/ - The home
page of The Diplomatic Pouch, a resource for all things Diplomacy,
include a zine with many articles on Diplomacy AI.
- Danny Loeb's article on the Diplomacy programming project.
www.smlnj.org/ - The home page
for Standard ML, a functional language with many good features for
AI and logic applications. It is the language used for implementing
the Diplomacy AI modules.
- A good tutorial on ML by Andrew Cumming.
- FAQ for ML.
As always, feedback ideas and interesting links and other contributions
are welcome. Past issues are available at either www.ddj.com
Until next month,