The Diplomacy
Programming Project

The Combinatorics
Of Adjustments

Danny Loeb


After the Fall moves have been played, and the retreats (if any) made, each player's number of units must be adjusted to equal the number of supply centers his Great Power controls.
Last issue we discussed the complexity of the search problems posed to the computer diplomat by the retreat phase in the game of diplomacy. In comparison, how difficult a problem is posed by winter adjustments (builds/removals)? To measure this problem, we analyze the worst-case scenario that a potential computer diplomat might face.

An initial version of the adjustment portion of the strategy finder of the Bordeaux diplomat was written by Brian Chojnowski (University of Illinois, Champaign-Urbana). Some alternate algorithms were proposed by Jean-Michel Faure (Bordeaux) and Per Westling (Linkoping, Sweden). The current version programmed by Gilles Schaeffer (Bordeaux, ENS/Paris) is presented below. We conclude with possible future developments.

Search size

The difficulty of a search problem is proportional to the number of the choices.

As we have seen there are 4,430,690,040,914,420 significantly different Spring 1901 openings in Diplomacy. Searching completely such a large space is an impossible task that grows worse in successive movement phases as a typical game of Diplomacy progresses.

On the other hand, a typical retreat phase involves only a small number of units with limited interactions, and tightly constrained movements. We can thus make a complete search of all possible retreats combinations. (Actually, we don't really consider all combinations, since "independent" retreats are optimized separately in order to gain time for a 2 or 3-ply look-ahead in our search.)

How many removals are possible?

If he has fewer centers than units, he must disband the excess units only, by removing them from the board. The units removed may be any of his units he chooses.
A player can have any number n of units up to 17. He may then be required to remove k of them where k is some number between 0 and n. He can remove any k he wants. He can remove no more and no less.

Thus, the number of choices is exactly the binomial coefficient n!/k!(n-k)! as given in the table below.

n\k 1   2   3    4    5	    6     7     8     9    10    11   12   13  14  15 16 17 
 1  1
 2  2   1
 3  3   3   1
 4  4   6   4    1
 5  5  10  10    5    1
 6  6  15  20   15    6     1
 7  7  21  35   35   21     7     1
 8  8  28  56   70   56    28     8     1
 9  9  36  84  126  126    84    36     9     1
10 10  45 120  210  252   210   120    45    10     1
11 11  55 165  330  462   462   330   165    55    11     1
12 12  66 220  495  792   924   792   495   220    66    12    1
13 13  78 286  715 1287  1716  1716  1287   715   286    78   13    1
14 14  91 364 1001 2002  3003  3432  3003  2002  1001   364   91   14   1
15 15 105 455 1365 3003  5005  6435  6435  5005  3003  1365  455  105  15   1
16 16 120 560 1820 4368  8008 11440 12870 11440  8008  4368 1820  560 120  16  1
17 17 136 680 2380 6188 12376 19448 24310 24310 19448 12376 6188 2380 680 136 17 1

By inspection we see that the largest number of choices, namely 24,310, arises when a 17-unit superpower is forced to remove roughly half of his forces.

How many builds are possible?

If he has more centers than units, he may build units by placing them, one in each unoccupied supply center, in his home country only (provided that such supply centers are still under his control). He must specify a fleet or an army in a coastal supply center (if Russia builds a fleet in St. Petersburg, he must specify the coast on which it is to appear, or the build is invalid).
The number of builds possible will vary depending upon: Since we are computing maximal numbers of build possibility, we can ignore the possibility that a center is occupied or owned by another power, and thus unavailable for a build.

Turkey, England, Italy

These powers have three coastal centers.
  1. 2 + 2 + 2 = 6 choices for one build.
  2. 2x2 + 2x2 + 2x2 = 12 choices for two builds. (18 counting waives)
  3. 2x2x2 = 8 choices for three builds. (26 counting waives)

Two coastal centers: France, Germany

These powers have two coastal centers and one inland.
  1. 2 + 2 + 1 = 5 choices for one build.
  2. 2x2 + 2x1 + 2x1 = 8 choices for two builds. (13 counting waives)
  3. 2x2x1 = 4 choices for three builds. (17 counting waives)

One coastal centers: Austria

These powers have one coastal centers, and two inland.
  1. 2 + 1 + 1 = 4 choices for one build.
  2. 1x1 + 2x1 + 2x1 = 5 choices for two builds. (9 counting waives)
  3. 2x1x1 = 2 choices for three builds. (11 counting waives)

Russia

Russia has 2 inland centers, a coastal center, and a bicoastal center.
  1. 1 + 1 + 2 + 3 = 5 choices for one build.
  2. 3x2 + 3x1 + 3x1 + 2x1 + 2x1 + 1x1 = 17 choices for two builds. (22 counting waives)
  3. 3x2x1 + 3x2x1 + 3x1x1 + 2x1x1 = 17 choices for three builds. (39 counting waives)
  4. 3x2x1x1 = 6 choices for four builds. (45 counting waives)
Russia has the most choices to consider for its builds. Up to 45 counting waives when it has 4 builds.

Occasionally, it may be in a countries interest to waive a build that it might otherwise be able to use to create a new unit. For example, Austria might save a build in order to build one fleet now and one fleet next year. Since our program can only look-ahead one or two phases at a time, it is unable to anticipate any advantages that waiving a build might bring next year. Thus, we do not even consider doing so unless so required by diplomatic constraints (eg. demilitarized zones) imposed by the negotiation module. Not counting waives then, Russia still has the most choices (17) when it has 2 or 3 builds.

Open problem

The total size of the search space is given by the product of the number of the choices available to each player. How can we maximize that?

Other than the share combinatorial challenge of tackling such a problem, there are practical implications of answer. It may be acceptable to write a diplomat that occasionally submits poor moves. However, it is unacceptable to write a diplomat that hangs for decades in certain rare situations trying to compare all the possible build combinations.

If the total search space can bounded by a reasonable number, then we can apply symplex methods to the resulting game matrix and find all of the Nash equilibria. However, if the total search space is too large, then (at least in some circumstances) only approximative methods may be practical.

So just how bad can things get?

The "obvious" solution of having two 17-unit powers each lose 8 supply centers does not work, since we must also assign 16 units to capture their centers. Also, note that a power must have 3 (or 4) units to control all of its supply center (as we assume above).

One possible solution with over 11 billion combinations is the following

FromToPossibilities
Austria17824310
Germany122
France358
Turkey3512
England3512
Italy3512
Russia4617
Total11,426,088,960

Algorithms

Even in the example given above, it might be possible to program a computer to consider all of the possibilities. However, the time available for an adjustment phase is severely limited and we also want to anticipate possible Spring moves while planning our builds.

Our current strategy finder calculates winter orders in two steps.

  1. First, a good move is found sequentially for each country using an algorithm by Brian Chojnowski.
  2. Second, moves are optimized with respect to each other using a simulated annealing algorithm by Gilles Schaeffer similar to that used in the movement phase.

Preliminary Search

First, optimal adjustments are found for each country under the simplifying assumption that the builds or removals of each country do not drastically effect those of another country.

This assumption allows us to calculate the builds and removals for each country independently. For each country, we consider all the possible combinations or builds and removals, and chose the option that maximize the value of the resulting position. This value may be calculated directly by the position evaluation subprogram. Or if sufficient time is available, the values may be calculated via a recursive call to the strategy finder itself so that the diplomat can anticipate the Spring moves while planning its Winter adjustments.

However, the adjustments of one country can affect those of another.

Nevertheless, the results of the above search produce reasonable winter orders based on the consideration independently of all of the options for each country.

That is, each country finds the best adjustment for its alliance under the (false) assumption that all other countries will skip their adjustment phase.

Possible Improvement

Calculate the adjustment of country i under the assumption that only countries i+1 through 7 will skip their adjustment phase. This may produce slightly better orders for country 7. This would be especially helpful if we arrange for country 7 to be our country. (We should note however that the strategy finder as currently implemented has no knowledge about what country we play. The strategy finder simply finds the best moves for all countries based on diplomatic constraints.)

Secondary search

If time is limited, for example if this search is part of a recursive search, then the results of the preliminary search are taken as final.

Given additional time, our strategy finder will attempt further improvements using simulated annealing. Each country is considered successively an random modifications of its adjustments are proposed until time runs out. The modifications are adopted if the resulting position is better for the country in question given the adjustments currently being considered by the six other powers. As the search progresses, we assume that the moves being considered are practically optimal, and we therefore modify smaller and smaller subsets of adjustments orders at a time.

Possible Improvements

1. Combined Search

These two phases of search could be combined as follows.

  1. For each country, let new list be its list of legal adjustment orders (subject to diplomatic constraints), and let old list be an empty list. Let n be 7 times the length of the longest new list.
  2. Let P be the position on the board given the first set of orders on each countries new list.
  3. Remove the first set of orders from each countries new list, and place it in old list.
  4. Let C be Austria.
  5. If C's new list is empty, then go to step 15.
  6. Let b be the first set of orders on C's new list.
  7. Consider the position P' obtained by replacing C's adjustment in P with b.
  8. Evaluate the value of P' for all countries using the position evaluator (if the flag has not been set) or using a recursive search (if it has).
  9. If P' is better for C's alliance than P, then
  10. Insert b into C's old list according to the value of P' for C's alliance.
  11. Remove b from C's new list.
  12. If all new lists are empty and flag is set, then go to line 16.
  13. If all new list are empty and flag is not set, then set flag, replace new lists with old lists, and empty old lists.
  14. After n iterations, set the flag if recursive search has been specified.
  15. If time remains, let C be the next country, and go to step 4.
  16. Return first element of each old list with their values, and halt.
This algorithm combines the two searchs above into a single search. Each country is guaranteed to consider all of its options. Moreover, no one country is especially privileged in its ability to anticipate the moves of the other countries.

Once a country exhausts its list of possible moves, then it stops searching until another country changes its mind about its best move. There is no point considering exactly the same combination of moves two times. When it resumes searching it will consider moves in the order of their value as determined in the previous search under the theory that moves that were good under the prior circumstances are likely to still be good.

If all countries exhaust their lists, then each countries adjustment is optimal with respect to the adjustments being considered by the six other countries. We have thus found the "Nash equilibrium" we are looking for.

2. Mixed Equilibria

Occasionally, Nash equilibria involving pure strategies might fail to exist. It might be possible to detect an "infinite loop" in the above search using a hash table, and then use linear programming to find a mixed Nash equilibrium.

3. Disband and Build

The builds should be redesigned to interface with the retreats in a multipli search so that disbanding a unit and rebuilding it elsewhere is considered. This should be done whenever there are units to retreat, and no removals to consider, and at least one home supply center open. In that case, the best retreats will be recalculated in each "component" for various subsets of our units. The best builds will then be factored in, and the results compared.

In anticipating the number of builds, we will assume that any unit which can do so will capture an enemy or neutral supply center with its retreat.

For more...

In conclusion, the problem of analyzing build combinations is slightly more difficult than the problem of analyzing retreat combinations, but child's play in comparison to the problem of analyzing moves. We thus have programmed the Bordeaux diplomat to conduct a very thorough search. Nevertheless, in order to leave time to look-ahead at future phases, this search is not perfect.

More work could be done on integrating the search for retreats and builds, and especially on testing the work done so far.

For more information, feel free to contact the author at the address below, read previous articles in this series, or consult the DPP Home Page.

Note that plenty of work is left to be done, especially in testing the strategy finder, writing the negotiation module, and on the small games projects.

Danny Loeb
([email protected])

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