The Math of Adjudication

Introduction

Anyone who is introduced to the game of Diplomacy and has an interest in algorithms and discrete mathematics will not only be intrigued by this magnificent game, but also be attracted by the peculiarities of the rules in their own right.

Adjudicating a face to face game manually is not very difficult. Certainly, some experience is required: but it is a job that can be done fairly easily. Yet if we look at the history of automatic adjudication, we see that many adjudicators have been plagued with bugs and mistakes. Even in the forums of the more mature and respected adjudicator programs, one can find the occasional bug report.

Since I always had interest in algorithms and discrete mathematics, I was keenly interested in adjudication. Of course, when my initial attempts didn't work out, I started to look at what had already been written. I searched on the Internet and found the DPTG (Diplomacy Player's Technical Guide). The DPTG is a very complicated document, and I wondered whether it made things easier or more difficult.

Anyway, I was not happy with the DPTG. If the algorithm in the DPTG is the simplest flawless algorithm, then so be it. However, many of the sentences in the DPTG are clearly “derived knowledge”. They are constructed or deduced from more fundamental principles that the authors already know, but that may not be obvious to the casual reader. We should try to get the complete reasoning on paper, instead of only the conclusions.

If we look at mathematics, we see that the ancient Greeks had only 5 axioms for geometry (the five postulates from Euclid). Even the fifth postulate was heavily debated until the early 19^th century. So if the DPTG describes the most fundamental axioms of adjudication, then this implies that adjudication in Diplomacy is far more complex than the entire field of geometry! Surely adjudication is a bit simpler than that...

So, I worked on my own ideas about adjudication, and finally I constructed my own algorithm. I wanted to build this in an existing program, but concluded that it needed systematic testing. I thought I could write the necessary test cases in a few evenings, but it turned out to be slightly more work than I expected. The result was the DATC (Diplomacy Adjudicator Test Cases, which was (and still is) used by several new Diplomacy programs. For a new adjudication program, the DATC significantly increases the quality of the first release.

Still, my real interests were in adjudication and in making the simplest flawless algorithm. In this article I will discuss all the issues about adjudication that I have explored over the last 10 years. It contains the following chapters:

• Equations, the fundamentals of the rules
  In this chapter I will show how some approaches to adjudication won't work, and that the fundamental rules of Diplomacy are best represented with equations rather than a procedure.
• A simple recursive algorithm that works for most cases
  With the rules described as equations, one can construct a simple recursive algorithm that works in most cases other than cyclic dependencies.
• Decisions on partial information
  One way to deal with cyclic dependencies is to make decisions based on partial information. However, this makes programming the equations more complicated.
• Two proofs about the Diplomacy rules
  In this chapter we prove two theorems. First, that an order can only be part of one dependency cycle at a time; and second, that decisions based on partial information are enough to do the job.
• A simple recursive guess algorithm that works in all cases
  Finally, I give an algorithm that is correct and simpler than an algorithm based on partial information. This chapter includes a listing of a part of the algorithm.

NEXT

Lucas Kruijswijk (L.B.Kruijswijk@inter.nl.net)