Re: Diplomacy Software

From: utility@quiche.cs.mcgill.ca (Ronald BODKIN)

Date: Wed, 07 Feb 1990 22:20:25 +0000

In article <485@nvuxh.UUCP> hall@nvuxh.UUCP (Michael R Hall) writes:
>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.
	I should think that each piece averages no more than 8 orders
per move.  To start with, if it IS supporting your own piece, that
restricts the other piece substantially, and often times there are few
supports available.

> Of course, you could try many
>things to reduce the search space. Humans can play Diplomacy, after
>all, and they don't even think that the tactics are the hardest
>part. What I usually do is segment a small portion of the board to
>deal with at a given time. Sometimes a situation on one side of the
>board will affect moves on the other side of the board, but not all
>that often. Similar techniques could be exploited to let the
>computer compute suggested orders in less than one week CPU time.
	There exists an extension of the alpha-beta algorithm for
look-ahead in the search space (I intend to publish this in future)
for games like diplomacy.  Of course, the analysis of the bargaining
game needs heavy work.  As for divide and conquer, I do believe that
this is the only way to go in computer diplomacy play.  Might as well
abstract out to resource allocation in regions since diplomacy tactics
are essentially regular enough that people can meaningfully speak of
allocation of units to strategic tasks.

>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!
	Smy-Syr is easily enough prevented by rules about threats and
defense.  It doesn't defend any endangered SC's nor does it threaten
any SC's nor does it increase tactical support.

>I think Mr. Botts had grander visions than a mere tactical advisor,
>but I think a tactical advisor is on the outter edge of what would
>be practical to implement.
	I don't really agree.  A tactical advisor is not too tough to
implement badly, and with a week of processing and some abstraction,
3 ply lookahead seems reasonable (of course, horizon effects would
still be DEADLY).  After this, the computer can probably engage in
some kind of negotiation -- using game theoretic principles of arguing
on the basis of its best understanding of the strength of a given
player's cooperation (i.e. it presents arguments from rational
alternatives for the player's cooperation).  To the extent to which
the computer believes the other player is rational and is strongly
motivated to act according to its vision of rational play, it will
trust that player.  Others should be duped into doing what is worst
without giving away its hand and making it clear that the computer
is trying to dupe or WHAT tactics it has (e.g. don't write your
obvious enemy Germany in a tense "which piece to support" situation
with an offer for him to take e.g. Belgium, when this suggests too
obviously that you will be defending that square and leaving
Burgundy open).
			Ron

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