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 fre¬≠quency and then write a routine to approximate the chances in real life.  One idea I am quite keen on is an aggress¬≠iveness 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)