Possible positions
Jérémie Lefrançois
Introduction
The problem to be solved is as follows: to find the number of different positions at Diplomacy after Spring 1901.
Impossibility of a naive approach
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^{15} ^{1}^{[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.
Stage 1: by country
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:
orders of successful moves of at the end of the resolution,
others.
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"):
(ARMEEVOISIN ALB GRE)
(ARMEEVOISIN ALB SER)
(ARMEEVOISIN ALB TRI)
(ARMEEVOISIN ANK ARM)
(ARMEEVOISIN ANK CON)
(ARMEEVOISIN ANK SMY)
(ARMEEVOISIN APU NAP)
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}^{[2]}.
Here the number of possible deployments per country:
Russia |
425 |
Germany |
160 |
Italy |
98 |
Austria |
97 |
France |
93 |
England |
88 |
Turkey |
40 |
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.
Stage 2: by group of country
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^{14}. 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}^{[3]}.
One finds thus
7700 deployments for England and France;
7138 deployments for Italy and Austria;
13.271 deployments for Russia and Turkey.
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:
(Italy, 3rd unit) and (Germany, 3rd unit)
(Austria, 2nd unit) and (Germany, 3rd unit)
Indeed, one has located the possibilities of conflicts in the following table:
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} |
Of these 1.142.080 elements, only 1.023.641 remains after the purging.
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.
Stage 3: partitioning of the subsets
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:
None is empty,
their union is the starting whole,
they are disjoined two by two.
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.
Our partition will thus have 4 elements:
Locate |
buR |
pie |
Numbers |
A1 |
Yes |
Yes |
418 |
A2 |
Yes |
Not |
2244 |
A3 |
No |
Yes |
1408 |
A4 |
No |
No |
3630 |
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.
Our partition will thus have 4 elements:
Locate |
VAr? |
Numbers |
B1 |
Gal |
2634 |
B2 |
Pru |
2634 |
B3 |
Sil |
2634 |
B4 |
Æ |
5369 |
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
Our partition will thus have 32 elements:
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 |
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.
Stage 4: exhaustive calculation
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:
{A4, B6, C32} is possible, no conflict.
{A2, B3, C8} is impossible, because there is a conflict on buR.
The 512 different cases of figure are thus listed, and one selects only those for which there is not conflict.
Concretely, the absence of conflict means that:
bur is not occupied at the same time in {France, England} and {Germany, Italy, Austria}.
pie is not occupied at the same time in {France, England} and {Germany, Italy, Austria}.
If var went in gal in {Russia, Turkey}, gal is not occupied in {Germany, Italy, Austria}
If var went in sil in {Russia, Turkey}, sil is not occupied in {Germany, Italy, Austria}
If var went in pru in {Russia, Turkey}, pru is not occupied in {Germany, Italy, Austria}
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.
The result obtained is thus: 74.980.036 938.664.
(or, in English, approximately seventy-five thousand billion, in scientific notation (round-off by defect) 7.49 X 10^{13})
Recapitulation and comparison of the successive estimates (rounded by defect):
Result by “bad method” |
Result |
Estimate from deployments by country |
Coarse estimate starting from the orders |
7.47 X 10^{13} |
7.49 X 10^{13} |
2.11 X 10^{14} |
2.38 X 10^{15} |
Technical details
The enumerations were carried out thanks to several small expert systems whose engine was a personal realization ^{4}^{[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}^{[5]}:
Example of inference:
Base rules |
Base facts initial |
Fact resulting from the inference |
If (father? X? y) (father? y? Z) then (grand_pere? X? Z) |
(father Jeremie Michel) (father Michel Paul)} |
(grand_pere Jeremie Paul) |
Algorithm RETE ^{6}^{[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}^{[7]}:
cat italautall.txt | grep - v PIE | grep BUR | grep GAL | grep - v SIL | grep - v PRU | wc
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.
Conclusion
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…
jeremie.lefrancois-at-laposte.net
1^{[1]} A more precise manual calculation by a third person gives (round-off by defect) 6.09 X 10^{15}
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.