September 2004

AI Expert Newsletter

September 2004

Dennis Merritt

AI - The art and science of making computers do interesting things that are not in their nature.

Diplomacy - AIs for a multiplayer game involving negotiation
Standard Meta-Language - A good language for developing AI
Links

Diplomacy

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 Game

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.

Map 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.

Real World

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 era?

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).

Computerized Diplomacy

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.

Map 2 - Board position from a game in progress at the Diplomatic Pouch's web site.

AI

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

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 is:

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 appropriately bound.

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 in ML:

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.

Links

www.starblood.org/daide/ - Diplomacy AI Center resource Web site.

ca.geocities.com/bmr335/dipai.html - 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.

http://devel.diplom.org/DipPouch/Zine/S1995M/Loeb/Project.html - 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.

www.dcs.napier.ac.uk/course-notes/sml/manual.html - A good tutorial on ML by Andrew Cumming.

http://www.faqs.org/faqs/meta-lang-faq/ - FAQ for ML.

As always, feedback ideas and interesting links and other contributions are welcome. Past issues are available at either www.ddj.com or www.ainewsletter.com.

Until next month,

Dennis Merritt