by David Norman

When writing a computer adjudicator for Diplomacy, it is inevitable that it won't work perfectly first time. But generally, once a few games have been played, the problems have all been found and fixed, and it works correctly and reliably. However, with the DAIDE adjudicator, we've recently found a bug that's so obscure that I thought it worth writing about it.

The DAIDE (Diplomacy AI Development Environment) Adjudicator is used to run Diplomacy games between AIs. But it is also used within various AIs, to generate orders. Albert, by Jason van Hal is one such AI. Albert generates several sets of orders for each of the powers, and then plays them against each other to evaluate how good each set is, in order to select the best set to submit. Jason estimates that for each turn played, Albert does about 150,000 internal adjudications!

A short while ago, Jason reported to me that he was occasionally seeing Albert crash inside the adjudicator module. As I'd written this module, he wanted me to look at it. The problem was, it was very occasional — Jason estimated it only happened about once in every 150 games played between 7 Alberts.

The problem is, when the bug happens this rarely, it's very difficult to tie it down. The bug is causing a crash, so you can't log anything after the event. And writing the current adjudication to disk before doing each one, adds a huge amount of overhead to Albert. However, through a combination of methods, Jason firstly managed to tie it down to a position in which it happens, and then by running Albert repeatedly on that position, to a specific adjudication.

So, the bug was as follows:

Firstly, you need two convoys. This isn't a surprise — mutiple convoys are a pain to adjudicate, as each convoy can affect the other.

Secondly, you need a fleet in the destination of each convoy. Each fleet is either supporting the convoying fleet for the other convoy, or supporting an attack on it. This ensures that it's difficult to work out which one to adjudicate first. But this still isn't that unusual.

Then you need one of those convoys to actually be a multi-step convoy.

And to complete the complication, you then need one of the fleets, other than the ones involved in the circle, to be dislodged.

And at that point, it was correctly working out that the Turkish convoy was broken, and therefore it could resolve this one first and then the Italian. But then it was removing the Italian convoy from the list of convoys to resolve, not the Turkish one — which meant a few steps later, it was trying to resolve a convoy it had resolved already, and having a convoy that was never being resolved. And that is what caused it to crash.

Given the combination of orders required to make this bug occur, it is pretty rare that it happens. Given that Albert is doing 150,000 adjudications per turn, a game is typically about 40 turns, and it was only crashing every 150 games, that suggests that this bug happens about once in every billion adjudications!

Which means if it was in any other Diplomacy Adjudicator, it would probably never have happened!

David Norman

If you wish to e-mail feedback on this article to the author, and clicking on the envelope above does not work for you, feel free to use the "Dear DP..." mail interface.