Possible positions

The problem to be solved is as follows: to find the number of different positions at Diplomacy after Spring 1901.

It is guessed easily that the number in question is vertiginous. Indeed, there are on the table exactly 22 units (6 countries have 3 of them and 1 has 4 of them). If they can go to 5 places (approximately) each one, one will be able to reach the order of magnitude of 522 = (round-off by defect) 2.38 X 10¹⁵ ^¹^[1]. There is thus no question of using this direct approach consisting in producing this list; the place occupied would overflow the hard disk of any commercial microcomputer.

There is no enumerating the possible orders either, applying an electronic referee, to thus obtain a position which one inserts in a list from which one eliminates the doubled blooms carefully. A completely honest electronic referee carrying out 1000 arbitrations per second would spend a time such as it would be necessary to pass the instruction to the future generations to collect the result.

Like any combinative problem, it should be broken up, one thus will start by listing the starting positions per country. One can already note that any set of order can be written in a “canonical” way. What does that mean? That one can classify the orders into two categories:

If one changes all the latter (the orders which were not adjudicated as a successful move) by an order to hold on the spot, and if the others are left, one then obtains exactly the same result.

Which are the possibilities for a given unit? To remain on the spot, to go on an accessible zone. One will speak about zone to distinguish the three following zones: stpcs, stpcn, stp. These three zones remain attached to only one area, stp. In the large majority of the cases, the attached area keeps the same name as the zone.

One recovers a list of vicinities by fleet and a list of vicinities by army (any Diplomacy adjudication software has necessarily one)

Here an extract of the file declaring the vicinities ("ARMEEVOISIN" means "ARMYNEIGHBOUR" and "FLOTTEVOISIN" means "FLEETNEIGHBOUR"):

One uses these vicinities to obtain, for each unit, all his new possible positions (in the form of zone), and thus, for a triplet (quadrupled) of units, by combining all the positions of the units of the country in “rough” form. Of course, a fleet uses the “FLOTTEVOISIN” and an army the “ARMEEVOISIN”.

It is however necessary to purge this list by preserving only the cases where the three (four) units occupy of the distinct areas, which is rather easy. Our distinction between zone and area is convenient there, because it makes it possible to refuse the result of {F stpcs H, a mos - stp} which leads to two units on the area stp.

Another case of figure is less immediate, but must also be purged from the list. One defines that movements are in opposition if they are carried out by two units (close) with both seeking to take the place of the other, or more precisely to come in the area than occupies the other. A simple example is {a Rom - ven, a ven - Rom}. It is thus necessary still to draw aside from our list the combinations comprising of the movements in opposition.

Is the result then the good one? No, because we can thus produce doubled blooms. Here two sequences of canonical natures producing of the situations let us double, i.e. identical: {a ven - Rom, a Rom - tos} and {a Rom H, a ven - tos}. It is indeed not written on the units the name of their site of origin.

This last purging will enable us to obtain a correct result, confirmed by other sources of VOPALIEC zine^²^[2].

One notices by the way that these data confirm a vague allowed opinion that Turkey is a simple country, and Germany a complicated country. Russia, strong of its 4 units, can thus spread itself of more than manners, but its case is not comparable.

Now that we have our list of deployments by country, remains to continue while seeking to gather several countries. In the absolute, if these 7 countries did not interact, the solution would be simply the product of the these 7 values, namely approximately 425 X 160 X 98 X 97 X 93 X 88 X 40 = (round-off by defect) 2.11 X 10¹⁴. Of course certain incompatibilities are obvious, between two sufficiently close countries, like England and France, the deployment {ENG, EDI, yor} of this first cannot cohabit with the deployment {ENG, PAR, MAR} of the latter.

One could (and one did it) calculate the number of incompatibilities for each one of (7 X 6)/2 = 21 pairs of country, to multiply each result by the product of the possible deployments for the 5 other countries. By then cutting off the sum from all these incompatibilities of the product of all the possible deployments, one would obtain a result rather close to the solution, but all the same erroneous, because one would have cut off at least twice (thus one time too much) a 7-uplet of deployments presenting from the incompatibilities from two pairs of nonempty countries of intersections. One will call thereafter this method the “bad method”.

After having carefully observed the Diplomacy map, one will gather our countries in the following way:

To calculate the number of possible deployments for two countries, all the possible couples are produced, then the same purging operations are carried out as if all the units were same country, that will save us from repeating it. The purging drawing aside the case where units in the same way standard inverted their positions is not however to realize, indeed, on the one hand they are not of the same nationality thus distinct, on the other hand this fact is impossible (only the armies of ven and TRI could be exchanged, which is impossible because that would require movements in opposition) ^³^[3].

Remain to compose {Italy, Austria} with Germany, delicate operation since the product of possible is of 7.138 X 160 = 1.142.080. To purge this million elements is possible, but it is necessary somewhat to optimize the treatment; one thus saves already the checking of the conflicts of oppositions which cannot occur between German units on the one hand, Italian or Austrian on the other hand.

To go even more quickly (because the heaviness of calculation requires it), one limits oneself to check between the following elements:

One thus preserves carefully in three files the possible deployments for these three subsets of country, and one now will seek the number of solutions of our problem.

This last stage will be a little harder. Let us point out initially the definition of the partitioning of a unit: it is to find subsets checking the three following properties:

Let us study initially the deployments of {England, France}. It is in bOu and pie that they interfere with rest of Europe in an independent way.

Let us study then the deployments of {Russia, Turkey}. It is in gal, pru and sil that they interfere with the rest of Europe, and in a dependent way this time. It is the unit in VAr at the beginning which causes this conflict; the occupations are thus incompatible two by two.

Let us study finally the deployments of {Germany, Austria, Italy}. It is in pie, buR, gal, pru and sil that they interfere with the rest of Europe, and in an almost independent way. We will explain this “almost” later on

Impossible cases (number = 0) remained in our partitioning. The first met, for example, corresponds to a unit in pie, buR, sil and pru, and no unit in gal. It is ber and mun which can occupy pru, sil and bou, and to occupy the three at the same time for these two units is impossible. The presence of these impossible cases results from the small lack of independence of the combinations. We can leave them because they do not obstruct the continuation of calculations; although “a good” partitioning does not tolerate empty sets.

One may at the same time check that the sum of the numbers of elements for each partitioning does yield the total number of elements of the partitioned unit.

All these possibilities should now be combined. One can be in 4 X 4 X 32 = 512 different cases, some are plausible (if there is no conflict), others are not it. For each different triplet, the product of the three numbers gives a value, and these are these values that it is necessary to add to obtain our result.

Here a possible example of combination and an impossible example of combination:

The 512 different cases of figure are thus listed, and one selects only those for which there is not conflict.

One thus obtains a list of 180 triplets, it is thus necessary to carry out the 180 products, then the sum of the 180 results.

(or, in English, approximately seventy-five thousand billion, in scientific notation (round-off by defect) 7.49 X 10¹³)

The enumerations were carried out thanks to several small expert systems whose engine was a personal realization ^⁴^[4] of the author (developed under LINUX in Language C). This engine of rustic expert system with variable uses a subset of syntax OPS5. It makes it possible to write typically rules of the form ^⁵^[5]:

Algorithm RETE ^⁶^[6] is implemented in a standard way, it allows strong optimized calculations at the prices of a very strong occupation of the memory. The use of predicate “DIFF” was used for example to detect the triplets of zones of arrived of the units of a country for which the 3 corresponding areas are indeed distinct.

To each problem corresponds a base of rule and a specific base of facts, the inference producing the anticipated results. To program the resolution of a problem with an expert system is practical, convivial and fast.

When that it was just necessary to count the number of each element of the partitions, the calls to UNIX “grep” (research of character string in a file, with the option “- v” for a reversed research) and “WC” (account of the number of lines, words and characters) were used.

Here an example of research in the whole of the deployments {Germany, Italy, Austria} corresponding to the case C20 ^⁷^[7]:

When 180 products had to be carried out and then a sum of 180 terms, it is EXCEL which was responsible for the operation, and still in a very convivial way. A copy/paste in a text file on PC of the result of the inference, then an importation of this text file in a EXCEL folder, a cell (EXCEL meaning) of calculation of product (duplicated then 179 times), and a cell carrying out the sum of the 180 products, and the job is done.

The problem of finding the total number of possible positions is another, more mathematical, which could be the subject of a later study. The methodology used could solve the quizzes related to the positions of Diplomacy published here and there (reconstitution of a game starting from incomplete information.) Lastly the possible lists of positions by country produced could be also used to revisit the theory of the openings.

I will be charmed of any confirmation of this result by another person to validate it in a final way…

1^[1] A more precise manual calculation by a third person gives (round-off by defect) 6.09 X 10¹⁵

2^[2] Vopaliec, a French paper zine devoted to Diplomacy and other games, available towards the following person: jeanpierremaulion-At-wanadoo.fr

3^[3] By the way note that the only possible conflicts of opposition on all the map are between ven and TRI, and our purging of the oppositions had thus carefully drawn aside ((Italy: ven - tri, Rom H, nap H), (Austria: TRI - ven, VIE H, bud H)).

4^[4] Realization former to the resolution of this problem.

5^[5] To note it “?” preceding the variables.

6^[6] Conceived by C. Forgy in 1982.

7^[7] For the comprehension of the readers nonfamiliar of UNIX, the sign “|” makes it possible to redirect the exit of a process in the entry of another, and orders it “cat” list the contents of a file.

Country	1st unit	2nd unit	3rd unit
Italy	nap	ROM	ven => {TYR}
Austria	TRI	VIE => {TYR, boh}	bud
Germany	kie	Ber	Mun => {TYR, boh, sil}

Locate	buR	pie	Numbers
A1	Yes	Yes	418
A2	Yes	Not	2244
A3	No	Yes	1408
A4	No	No	3630

Locate	VAr?	Numbers
B1	Gal	2634
B2	Pru	2634
B3	Sil	2634
B4	Æ	5369

Locate	magpie	buR	gal	sil	pru	Numbers
C1	Yes	Yes	Yes	Yes	Yes	80
C2	Yes	Yes	Yes	Yes	No	3192
C3	Yes	Yes	Yes	No	Yes	3192
C4	Yes	Yes	Yes	No	No	7980
C5	Yes	Yes	No	Yes	Yes	0
C6	Yes	Yes	No	Yes	No	8250
C7	Yes	Yes	No	No	Yes	8250
C8	Yes	Yes	No	No	No	20625
C9	Yes	No	Yes	Yes	Yes	3192
C10	Yes	No	Yes	Yes	No	17140
C11	Yes	No	Yes	No	Yes	17140
C12	Yes	No	Yes	No	No	29550
C13	Yes	No	Not	Yes	Yes	8250
C14	Yes	No	No	Yes	No	42262
C15	Yes	No	No	No	Yes	42262
C16	Yes	No	No	No	Not	71280
C17	Not	Yes	Yes	Yes	Yes	0
C18	Not	Yes	Yes	Yes	No	9228
C19	Not	Yes	Yes	No	Yes	9228
C20	Not	Yes	Yes	No	No	23070
C21	Not	Yes	No	Yes	Yes	0
C22	Not	Yes	No	Yes	No	22158
C23	Not	Yes	No	No	Yes	22158
C24	Not	Yes	No	No	No	55395
C25	Not	No	Yes	Yes	Yes	9228
C26	Not	No	Yes	Yes	No	47108
C27	Not	No	Yes	No	Yes	47108
C28	Not	No	Yes	No	No	79320
C29	Not	No	No	Yes	Yes	22158
C30	Not	No	No	Yes	No	108276
C31	Not	No	No	No	Yes	108276
C32	Not	No	No	No	Not	178365

Russia	425
Germany	160
Italy	98
Austria	97
France	93
England	88
Turkey	40

Result