Re: Diplomacy Software

From: hall@nvuxh.UUCP (Michael R Hall)

Date: Tue, 30 Jan 1990 03:15:11 +0000

(Now cross-posted to rec.games.board, which is more appropriate than .pbm)

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.
[Munch.]
> We humans generally deal with such situations by ruthlessly pruning the
> tree of possibilities down to something we can manage, which is pretty
> close to a single trunk.  In other words, we pick one, or a small set,
> of the possible states of the game, label it "reality", and then proceed
> essentially as though it were known to be true.  We humans are not good
> at managing multiple alternate realities.

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.
(I have written an extremely fast Blackjack analyzer, but again, in
Blackjack moves are sequential, not simultaneous.)

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

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 think a good approach would be to let the user specify a subset of
all pieces and a subset of all moves for those pieces. The computer
can then start trying to come up with good sets of orders for any
given country.

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.
--
Michael R. Hall           |"We have seen pictures [of Mars] where there are
hall@nvuxh.cc.bellcore.COM|canals, we believe, and water. If there is water,
bellcore!nvuxh!hall       |there is oxygen. If oxygen...we can breathe."-Quayle

References

Diplomacy Software
kdb@chinet.chi.il.us (Karl Botts)
Mon, 22 Jan 1990 06:24:56 +0000

Referenced By

Diplomacy Software
kdb@chinet.chi.il.us (Karl Botts)
Mon, 22 Jan 1990 06:24:56 +0000