Adjudicating Diplomacy Games
by Computer

by Stewart Cross

Well, here was a challenge - design a computer program to adjudicate Diplomacy games.  Stephen assured me it would be useful, and he was not aware of any commercially available program designed specifically for long-suffering zine editors.  Now I wouldn't exactly claim to be a computer genius, but I'm reasonably literate, and here was an opportunity like no other to familiarise myself with the rules of a game which, it must be admitted, I haven't exactly distinguished myself at yet. 

At first sight, Diplomacy appears to be quite a simple game, and my target was a simple one - I wasn't trying to play the game, after all - only provide a framework for managing it. But once I started thinking of how to actually analyze moves and decide whether they succeed or not, I realised it's actually deceptively difficult, for a variety of reasons. 

One reason is the sheer volume of possible moves. Take for example four armies in (say) Venice, Tyrolia, Trieste and Vienna, and for the moment ignore their countries. How many different orders could be submitted? Let's start with Venice: 

A(Ven) Stands

A(Ven) - Tri

A(Ven) S A(Tri) - Tyr

A(Ven) S A(Vie) - Tyr

A(Ven) S A(Tri)

A(Ven) - Tyr

A(Ven) S A(Tyr) - Tri

A(Ven) S A(Vie) - Tri 

Venice can make 9 different orders in total. Vienna can also make 9, while Tyrolia and Trieste can make 11 each because A(Ven) S A(Tyr)they are adjacent to three of the other provinces instead of two. So the grand total of possible moves here is 11 x 11 x 9 x 9 = 9,801.  And this is just for 4 units in 4 provinces. The possibilities for 34 units in 75 provinces are enormous. 

Actually, the situation isn't quite as mathematically complex as that. The scenario I've described has several different symmetries which reduce the number of genuinely different combinations to around 250.  But although most of the possible combinations are illogical and would very rarely, if ever, actually be ordered, the computer has to be able to adjudicate them nevertheless. 

Now the human mind is very good at scanning complex situations and recognising patterns, and this is the way in which Diplomacy players, by and large, adjudicate. We can quickly recognise which moves are interdependent and ignore all the others while we analyze "groups" of moves. The computer, on the other hand, is good at calculations but cannot recognise patterns easily, especially where the number of possibilities is so great. Instead, it has to work analytically on each move and determine its success or failure. 

Another reason why Diplomacy is difficult to analyze is that it is potentially very "interconnected".  For example, the outcome of A(Mos) - Ukr could, potentially, determine the result of F(Lon) - ENG on the other side of the board.  Convoys, in particular, allow arbitrarily long-range movement, and allow units to influence events very far away.  In practice, we all know that most Diplomacy rounds can be broken up into small independent scenarios, and the human mind can quickly work out which moves affect the outcome. The computer, though, cannot  normally break up an adjudication into small parts, for its lack of pattern recognition means it can never rule out the possibility that a unit in a different part of the board will affect its result.  It has to deal with all the moves at the same time. 

So the solution had to be analytic and deal with all the units together. My next consideration was how to do the analysis, and this is where more problems arose. 

Diplomacy works on a rule of simultaneous movement, but the actuality is more subtle than that.  There is a hierarchy of moves, ranging from the simple uncontested moves which must succeed, through to moves dependent on a complex chain of events.  It is very important to get this hierarchy right.  When we apply the rule ourselves, we quickly identify it - "move A must succeed, therefore move B, which is dependent on its outcome, fails". The computer must firstly identify which moves must succeed or fail, and then use this knowledge in an iterative process to adjudicate the dependent moves. 

So consider what factors determine the outcome of a single move (let's call it "your" attack). The first is clearly its strength. It is fairly simple to add 1 (for the move) plus 1 for each valid, un-cut support, to give a total "weight" for the attack. 

The second factor is the defence. If there is a unit in the province being attacked, what does it do?  It might stand, it might counterattack (these two cases are actually the same as far as the calculation is concerned), or it might move somewhere else.  This move "somewhere else" might be significant if it dislodges your attack's support, or another attacker, or one of its supports.  The third factor is other, third-party attacks.  These have the potential to "stand off" your attack, so they must also be considered. 

Taken together, I drew up (after several attempts) a list of 20 distinct categories of result with different outcomes. These ranged from the trivial: 

- No unit in province attacked, all third party attacks have less weight than yours - move succeeds. 

to the uncomfortably complex: 

- Unit in province attacked succeeds in dislodging the support of the only third party attack with a weight equal to yours - move succeeds. 

These 20 categories fell into 2 broad classes. 7 of them were determinate, in the sense that their result was independent of any other moves.  The remaining 15 were indeterminate until the moves around them had been decided.  This now gave me a basis for the program. The components of the analysis were as follows: 

Check the syntax of each order

Check the validity of individual orders

Check orders' dependencies

Check the validity of convoys

Make support cuts

Adjudicate moves:

- Calculate weights of attack, defence & counterattack

- Determine category of result

- On the first pass, adjudicate the determinate moves

- On subsequent passes, adjudicate other moves

- Loop until all moves are adjudicated

Check for dislodged convoys & adjudicate again if necessary

Make retreats, disbands and adjust units. 

There was one final complication. This "algorithm" depends on there being at least one move which is determinate at the start of the adjudication. There are some cases where this is not so. These are the three- or four-way rotations, for example: 

A(Bud) - Ser; A(Ser) - Rum; A(Rum) - Bud 

An explicit test for these needed to be included in the adjudication routine. 

There were some other areas where careful thought and rule-reading were required.  Self-dislodgement was prohibited by putting a test in the adjudication cycle to prevent it; but I had to be careful not to do it too early, as self-attacks are valid for other purposes, for example to stand off another player.  Support cuts were relatively straightforward, but I had to be careful to include the bit about a convoy not being able to cut support for an attack on its last fleet. The convoyed swap: 

F(TYS) C A(Tus)-Rom; A(Rom)-Tus 

was also quite simple once I remembered it. 

Convoys themselves required quite a bit of thought.  In the end, I settled for a compromise.  My program supports convoys of any length, but they must be linear and unbroken.  The "unbroken" bit is common sense, but the "linear" actually goes contrary to the rules, which do allow multiple paths for convoys.  Not only that, I (against Stephen's advice) insisted on including "unwanted" convoys. So, given : 

Germany: A(Hol) - Bel

England: F(ENG) C A(Hol) - Bel ; F(NTH) C A(Hol)-Bel

France: F(Pic) S F(Bre) - ENG 

The French move would succeed, F(ENG) would be dislodged and the German move would fail, even if the German was unaware of the other moves. Well, it keeps me entertained! 

Once the basic adjudication routine had been designed, I spent some time shaping the program as a genuine game manager.  I set up map, unit and country files to store the basic data, a system for changing seasons, an editor for changing orders and examining results, a game file to store basic game information like the players' and GM's names, and a menu system to control everything.  The result is reasonably pleasing, although it probably needs fine tuning.  I am fairly happy with the integrity of the adjudicator, having spent many hours testing it on the most difficult situations I could think of, and initial tests have do seem to be showing that it can save a good deal of time.  I must admit, I don't feel the urge to run a Diplomacy zine myself, but it's nice to do something useful.  Now, if anyone's interested in Croquet..... 

Reprinted from Spring Offensive 10