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 1015 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:

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 zine2[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 1014. 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

 

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:

 

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:

 

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:

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:

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 1013)

 

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 1013

7.49 X 1013

2.11 X 1014

2.38 X 1015

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 1015

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.