Re: Diplomacy Software

From: kevin@math.lsa.umich.edu (Kevin Coombes)

Date: Thu, 01 Feb 1990 18:18:55 +0000

In article <485@nvuxh.UUCP> hall@nvuxh.UUCP (Michael R Hall) writes:
>   In article <1990Jan22.062456.1421@chinet.chi.il.us>,
>kdb@chinet.chi.il.us (Karl Botts) writes:
>   > I was thinking more along the lines of something that would assist a
>   > human playing Diplomacy; help him to organize his information, manage
>   > his communications, analyze scenarios, and so forth.
>
>   I was considering writing a Diplomacy tactical advisor that would
>   exhaustively (or heuristically) search through the space of possible
>   moves and advise you on sets of moves considered most profitable
>   for every country. The computer would not need to take into account
>   alliances, because by ignoring alliances it will note potential
>   stabs. You could play what-if scenarios to get a better grasp of the
>   current situation.
>
>   Unfortunately, the space of possible moves is so vast that I have
>   (at least for now) given up on this idea. It is much worse than
>   chess. In chess just one piece of one player moves at a time,
>   whereas in Diplomacy all pieces of all players move simultaneously.
>   ...
>   34 pieces to the power of (~5 possible moves + ~5 possible defense supports
>   + ~5 possible attack supports) is the kind of combinatorics we're
>   talking about for just one turn. Of course, you could try many
>   ...
>   Also, you either need a very good static state evaluation function
>   to evaluate how favorable board positions are to each country or
>   else you need to look very many turns ahead and then use a simple
>   state evaluation like "number of supply centers". Otherwise, not
>   much will prevent Turkey from trying to open with A Smy-Syr!
>   ...

I've also thought about this some. I haven't had the time to implement
anything, but I'm not as pessimistic as Mr. Hall. I think you have to
define the problem in the correct terms. A ``tactical advisor'' should
only try to find the best moves for one country. This reduces the
number of pieces you're looking at considerably. You should also
concentrate your efforts on writing a good state evaluation function,
since a search through several game turns is prohibitively expensive.
It might be possible to write such a function which only looks at the
possible moves in the current game turn. An advantage of this approach
is that it also limits the effective size of the board to the set of
spaces which are at most two moves distant from any of your currently
occupied spaces or currently controlled supply centers.

Here are some random thoughts that might go into an attempt to write
such an evaluation function.
1. Each space on the board should have some intrinsic value which
depends on its status as a supply center, its mobility (separated into
land connections, sea connections and coastal connections), and its
access to other supply centers.
2. This intrinsic value should be modified by a number of factors,
such as: who controls it, who occupies it, who is adjacent to it, and
what season it is (mobility being more important in the spring, and
control of supply centers in the fall).
3. The numbers generated by the considerations of 1 and 2 should be
used to get a ranked list of the spaces which it is most important to
occupy or to prevent others from occupying. You can then search
through the set of possible moves and evaluate the resulting positions
with respect to how many of the high priority goals are achieved.

This approach will prevent Turkey from opening A Smy-Syr; it will,
however, strongly encourage England to open F Lon-ECh, F Edi-Nth. I
haven't been able to decide in general whether it is more likely to
lead to aggressive or defensive play. If you don't make provisions to
modify the values based on estimates of the strengths of alliances,
then I suspect it will lead to aggressive openings followed by passive
stalemates.

Kevin Coombes <kevin@math.lsa.umich.edu>

References

Diplomacy Software
kdb@chinet.chi.il.us (Karl Botts)
Mon, 22 Jan 1990 06:24:56 +0000
Re: Diplomacy Software
hall@nvuxh.UUCP (Michael R Hall)
Tue, 30 Jan 1990 03:15:11 +0000