Artificial Intelligence and Diplomacy
by
Stephen Agar
I
have been thinking vague thoughts about how you would code an AI program to play
Diplomacy - it would be fun if you could play against six computer opponents (or
have a game of Intimate Diplomacy against the computer).
Admittedly, the old Leisure Genius program does have AI of some sort, but
the computer plays atrociously (as Russia the computer usually opens with
F(StP)sc Stands!). I was spurred to
write the following article by news that Sean Lorber is writing a program in the
US to do just that.
Openings would be quite easy - you could just program in
the 50 or so commonest openings for each country, use Richard Sharp's fairly
comprehensive statistics on frequency and then write a routine to approximate
the chances in real life. One idea
I am quite keen on is an aggressiveness factor, which could be random or could
be set by the human player. All
openings could be given a weighting for aggressiveness so that a more aggressive
computer player would be more likely to pick an aggressive opening.
If the computer deduces "logical"
opening moves then it may be predictable - the computer would just order F(Sev)-Rum
every time, allowing Turkey into the Black Sea.
Chess programs work on a library of openings, and I think it would work
equally well with a Diplomacy program. Once
the opening is out of the way, we need to construct an algorithm which will pick
the optimum move, and this is where it gets very difficult.
Now I don't claim to be any kind of expert, but it occurs to me that
there are two distinct ways of doing this, you could either consider factors to
optimise in turn the best move for each unit, or you could consider the nest
moves for units to occupy specific positions on the board.
I favour the latter approach as it is the best way to formulate coherent
strategies that use units together as opposed to all the moves being a
collection of one-offs. Thus I
think before every move, retreat or adjustment, the program would need to
calculate the Tactical Factor of each space to each Power and use that
information as the core factor for determining which move to make.
Tactical
Factors could perhaps be based on the characteristics of the space (owned or
hostile centre), number of adjacent centres (home, neutral, enemy) and the number
of adjacent enemy units (say within two spaces, weighted so closer units count
more). The Tactical Factor of each province would need to be re-calculated each
move (Eg. the initial Tactical Factor of Warsaw and Livonia
to Russia would increase if Germany moved to Prussia). If I was playing a
gunboat game, I think my thought processes might go something like this:
1.
Count the number of hostile units next to each of my home centres. If
there is one hostile unit, then I would order the unit in
2.
As (1) save I would be protecting my non-home centres.
3.
As (1) save I would be attacking enemy home centres.
4.
As (1) save I would be attacking enemy non-home centres.
5.
As (1) save that I would be doing the exercise in order to get my units
to make attacks on hostile centres.
6.
As (1) save that I would be defending my own units from dislodgment.
7.
As (1) save that I would be attempting to dislodge enemy units (which
could not retreat to one of my undefended centres).
8.
As (1) save I would be playing for position.
All provinces need to be rated as to the desirability of occupying them
(a Tactical Factor).
Further
refinements could include a formula for assessing whether the moves of another
player are threatening or non-threatening, the existence of the former making it
more likely that the computer will play more aggressively when considering
decisions which affect that players units or centres.
Choices between different moves also need to consider the chances of
success and the desirability of maximising the number of units involved in
taking spaces with the highest Tactical Factors.
An aggressive computer player would put a greater emphasis on moves which
seek to gain a tactical advantage, whereas a defensive player puts the emphasis
on defending what he has (thus an aggressive player would always perceive spaces
which he does not own or occupy as having a higher Tactical Factor then a
defensive player would).
Resolving
conflicts between the different possible moves (as England should the computer
defend Brest, try to take Spain or move to WMS for position) is a difficult
question. Essentially I think you
need to weight moves using a formula which takes into account the likely gains
and losses overall and then throw in a random element, weighted according to the
aggressiveness rating of the computer player.
Particular weighting could be given to encourage moves against a player
which has already taken a centre of the computer.
Retreats
could be made depending of the Tactical Factors of all the spaces open to
retreat to, but in a build season if the Tactical Factor of occupying a home
centre exceeds that of a possible retreat space, then the computer may disband
and build (after all it would be silly for Turkey to retreat A(StP)-Fin, if
there was an Austrian army in Bulgaria threatening Constantinople. Builds are
more difficult. The computer could
calculate (say) the nearest three enemy controlled or neutral centres, calculate
how vulnerable they are (number of enemy units within two spaces - number of
friendly units, units two spaces away having a weighting half that of adjacent
units) and then choose a unit which can reach the most vulnerable quickest.
Now
this is all a lot easier to say than to program (and such a routine would be
bound to produce bizarre moves every now and then), but there should be a basic
competence behind it. Of course,
the $64,000 question is should the program have 1:25 chance in any given move
that a computer player would NMR or even drop out?
How realistic should any computer program be?
Reprinted from Spring Offensive 21 (March 1994)
| 