Olympus Blog

Introduction

Le problème à résoudre est le suivant : trouver le nombre de positions différentes à Diplomatie après le Printemps 1901.

Impossibilité d’une approche naïve

On devine aisément que le nombre en question est vertigineux. En effet, il y a sur la table exactement 22 unités (6 pays en possèdent 3 et 1 en possède 4). Si elles peuvent se rendre à 5 endroits (environ) chacune, on pourra atteindre l’ordre de grandeur de 522 = (arrondi par défaut) 2.38 x 10151 [1]. Il n’est donc pas question d’utiliser cette approche directe consistant à produire cette liste, la place occupée sur disque déborderait de celle de tout micro-ordinateur du commerce.

Pas question non plus d’énumérer les ordres possibles, appliquer un arbitre électronique, obtenir ainsi une position que l’on insère dans une liste dont on élimine soigneusement les doublons. Un arbitre électronique tout à fait honnête réalisant 1000 arbitrages à la seconde consommerait un temps tel qu’il faudrait passer la consigne aux générations futures de recueillir le résultat.

Etape 1 : par pays

Comme tout problème combinatoire, il faut le décomposer, on va donc commencer par lister les positions de départ par pays. On peut déjà constater que tout jeu d’ordre peut être écrit de manière « canonique ». Que signifie cela ? Que l’on peut classer les ordres en deux catégories :

• Les ordres de mouvements couronnés de succès à l’issue de la résolution,
• Les autres.

Si on change tous ces derniers (les ordres qui n’ont pas été arbitrés par un mouvement) par un ordre de tenir sur place, et si on laisse les autres, on obtient alors exactement le même résultat.

Quelles sont les possibilités pour une unité donnée ? Rester sur place, se rendre sur une zone accessible. On parlera de zone pour distinguer les trois zones suivantes : stpcs, stpcn, stp. Ces trois zones restent rattachées à une seule région, stp. Dans la grande majorité des cas, la région attachée garde le même nom que la zone.

On récupère une liste de voisinages par flotte et une liste de voisinages par armée (tout programme d’arbitrage de Diplomatie en possède nécessairement une)

Voici un extrait du fichier déclarant les voisinages :

(ARMEEVOISIN MON GRE)

(ARMEEVOISIN MON SER)

(ARMEEVOISIN MON TRI)

(ARMEEVOISIN ANK CAU)

(ARMEEVOISIN ANK CON)

(ARMEEVOISIN ANK SMY)

(ARMEEVOISIN APU NAP)

On utilise ces voisinages pour obtenir, pour chaque unité, toutes ses nouvelles positions possibles (sous forme de zone), et donc, pour un triplet (quadruplé) d’unités, en combinant toutes les positions des unités du pays sous forme « brute ». Bien entendu, une flotte utilise les « FLOTTEVOISIN » et une armée les « ARMEEVOISIN ».

Il faut cependant purger cette liste en ne conservant que les cas où les trois (quatre) unités occupent des régions distinctes, ce qui est assez facile. Notre distinction entre zone et région est là opportune, car elle permet de refuser le résultat de {f stpcs t, a mos – stp} qui conduit à deux unités sur la région stp.

Un autre cas de figure est moins immédiat, mais doit aussi être purgé de la liste. On définit que des mouvements sont en opposition s’ils sont effectués par deux unités (voisines) dont chacune cherche à prendre la place de l’autre, ou plus précisément à venir dans la région qu’occupe l’autre. Un exemple simple est {a rom – ven, a ven – rom}. Il faut donc encore écarter de notre liste les combinaisons comportant des mouvements en opposition.

Le résultat est-il alors le bon ? Non, car nous pouvons ainsi produire des doublons. Voici deux séquences d’ordres canoniques produisant des situations doublons, c’est à dire identiques : {a ven – rom, a rom – tos} et {a rom t, a ven – tos}. Il n’est en effet pas inscrit sur les unités le nom de leur emplacement d’origine.

Cette dernière purge nous permettra d’obtenir un résultat correct, confirmé par d’autres sources du zine VOPALIEC2 [2].

Voici le nombre de déploiements possibles par pays :

Russie	425
Allemagne	160
Italie	98
Autriche	97
France	93
Angleterre	88
Turquie	40

On remarque au passage que ces données confirment une vague opinion admise que la Turquie est un pays simple, et l’Allemagne un pays compliqué. La Russie, forte de ses 4 unités, peut donc se déployer de plus de manières, mais son cas n’est pas comparable.

Etape 2: par groupe de pays

Fort de notre liste de déploiements par pays, reste à poursuivre en cherchant à regrouper plusieurs pays. Dans l’absolu, si ces 7 pays n’interagissaient pas, la solution serait simplement le produit de ces 7 valeurs, à savoir environ 425 x 160 x 98 x 97 x 93 x 88 x 40 = (arrondi par défaut) 2.11 x 10¹⁴. Bien entendu certaines incompatibilités sont évidentes, entre deux pays suffisamment voisins, comme l’Angleterre et la France, le déploiement {man, edi, yor} de cette première ne peut cohabiter avec le déploiement {man, par, tou} de cette dernière.

On pourrait (et on l’a fait) calculer le nombre d’incompatibilités pour chacun des (7 x 6) / 2 = 21 paires de pays, multiplier chaque résultat par le produit des déploiements possibles pour les 5 autres pays. En retranchant ensuite la somme de toutes ces incompatibilités du produit de tous les déploiements possibles, on obtiendrait un résultat assez voisin de la solution, mais tout de même erroné, parce que l’on aurait retranché au moins deux fois (donc une de trop) un 7-uplet de déploiements présentant des incompatibilités sur deux paires de pays d’intersections non vides. On appellera par la suite cette méthode la « mauvaise méthode ».

Après avoir bien observé la carte de Diplomatie, on va regrouper nos pays de la manière suivante :

Pour calculer le nombre de déploiements possibles pour deux pays, on produit tous les couples possibles, puis on réalise les mêmes purges que si toutes les unités étaient du même pays, dont on fera l’économie d’une répétition. La purge écartant le cas où des unités de même type ont interverti leurs positions n’est cependant pas à réaliser, en effet, d’une part elles ne sont pas de même nationalité donc distinctes, d’autre part cet état de fait est impossible (seules les armées de ven et tri pourraient être échangées, ce qui est impossible car cela nécessiterait des mouvements en opposition).

On trouve ainsi

• 7700 déploiements pour Angleterre et France ;
• 7138 déploiements pour Italie et Autriche ;
• 13 271 déploiements pour Russie et Turquie.

Reste à composer {Italie, Autriche} avec Allemagne, opération délicate puisque le produit des possibles est de 7 138 x 160 = 1 142 080. Purger ce million d’éléments est possible, mais il faut quelque peu optimiser le traitement, on économise donc déjà la vérification des conflits d’oppositions qui ne peuvent pas se produire entre des unités allemandes d’une part, italienne ou autrichiennes d’autre part.

Pour aller encore plus vite (car la lourdeur du calcul l’exige), on se limite à vérifier entre les éléments suivants :

• (Italie, 3^ème unité) et (Allemagne, 3^ème unité)
• (Autriche, 2^ème unité) et (Allemagne, 3^ème unité)

En effet, on a repéré les possibilités de conflits dans le tableau suivant :

De ces 1 142 080 éléments, seuls 1 023 641 restent après la purge.

On conserve donc soigneusement dans trois fichiers les déploiements possibles pour ces trois sous-ensembles de pays, et on va maintenant chercher le nombre de solutions de notre problème.

Etape 3 : partitionnement des sous-ensembles

Cette dernière étape sera un peu plus laborieuse. Rappelons d’abord la définition du partitionnement d’un ensemble : c’est lui trouver des sous-ensembles vérifiant les trois propriétés suivantes :

• Aucun n’est vide,
• Leur réunion est l’ensemble de départ,
• Ils sont disjoints deux à deux.

Etudions d’abord les déploiements de {Angleterre, France}. C’est en bou et pie qu’ils interfèrent avec le reste de l’Europe et de manière indépendante.

Notre partition aura donc 4 éléments :

Etudions ensuite les déploiements de {Russie, Turquie}. C’est en gal, pru et sil qu’ils interfèrent avec le reste de l’Europe, et de manière dépendante cette fois. C’est l’unité en var au départ qui cause ce conflit, les occupations sont donc incompatibles deux à deux.

Notre partition aura donc 4 éléments :

Etudions enfin les déploiements de {Allemagne, Autriche, Italie}. C’est en pie, bou, gal, pru et sil qu’ils interfèrent avec le reste de l’Europe, et de manière presque indépendante. Nous expliquerons ce « presque » ultérieurement

Notre partition aura donc 32 éléments :

Des cas impossibles (nombre = 0) sont restés dans notre partitionnement. Le premier rencontré, par exemple, correspond à une unité en pie, bou, sil et pru, et pas d’unité en gal. C’est ber et mun qui peuvent occuper pru, sil et bou, et occuper les trois à la fois pour ces deux unités est impossible. La présence de ces cas impossibles résulte du petit manque d’indépendance des combinaisons. Nous pouvons les laisser car ils ne gênent pas la suite des calculs, bien qu’un « bon » partitionnement ne tolère pas d’ensembles vides.

On en profite pour vérifier au passage que la somme des nombres d’éléments pour chaque partitionnement fournit bien le nombre d’éléments total de l’ensemble partitionné.

Etape 4 : décompte exhaustif

Il faut maintenant combiner toutes ces possibilités. On peut se trouver dans 4 x 4 x 32 = 512 cas différents, certains sont plausibles (s’il n’y a aucun conflit), les autres ne le sont pas. Pour chaque triplet différent, le produit des trois nombres donne une valeur, et ce sont ces valeurs qu’il faut ajouter pour obtenir notre résultat.

Voici un exemple de combinaison possible et un exemple de combinaison impossible :

• {A4, B6, C32} est possible, aucun conflit.
• {A2, B3, C8} est impossible, car il y a un conflit sur bou.

On liste donc les 512 cas de figure différents, et on ne sélectionne que ceux pour lesquels il n’y a pas conflit.

Concrètement, l’absence de conflit signifie que :

• bou n’est pas occupé à la fois dans {France, Angleterre} et {Allemagne, Italie, Autriche}.
• pie n’est pas occupé à la fois dans {France, Angleterre} et {Allemagne, Italie, Autriche}.
• Si var est allée en gal dans{Russie, Turquie}, gal n’est pas occupé dans {Allemagne, Italie, Autriche}
• Si var est allée en sil dans{Russie, Turquie}, sil n’est pas occupé dans {Allemagne, Italie, Autriche}
• Si var est allée en pru dans{Russie, Turquie}, pru n’est pas occupé dans {Allemagne, Italie, Autriche}

On obtient donc une liste de 180 triplets, il faut donc réaliser les 180 produits, puis la somme des 180 résultats.

(Ou, en français, environ soixante-quinze mille milliards, en notation scientifique (arrondi par défaut) 7.49 x 10¹³)

Récapitulation et comparaison des estimations successives (arrondis par défaut) :

Détails techniques

Les énumérations ont été réalisées grâce à plusieurs petits systèmes experts dont le moteur était une réalisation personnelle^{4 [4]} de l’auteur (développée sous LINUX en Langage C). Ce moteur de système expert rustique avec variable utilise un sous-ensemble de la syntaxe OPS5. Il permet d’écrire typiquement des règles de la forme^{5 [5]} :

Exemple d’inférence :

L’algorithme RETE^{6 [6]} y est implémenté de manière standard, il permet d’optimiser fortement les calculs aux prix d’une très forte occupation de la mémoire. L’utilisation du prédicat « DIFF » a servi par exemple à détecter les triplets de zones d’arrivé des unités d’un pays pour lesquels les 3 régions correspondantes sont bel et bien distinctes.

A chaque problème correspond une base de règle et une base de faits spécifique, l’inférence produisant les résultats escomptés. Programmer la résolution d’un problème avec un système expert est pratique, convivial et rapide.

Lorsque qu’il a fallu juste compter le nombre de chaque élément des partitions, ce sont les appels systèmes UNIX « grep » (recherche de chaîne de caractère dans un fichier, avec l’option « -v » pour une recherche inversée) et « wc » (compte du nombre de lignes, mots et caractères) qui ont été mis à contribution.

Voici un exemple de recherche dans l’ensemble des déploiements {Allemagne, Italie, Autriche} correspondant au cas C20^{7 [7]} :

cat italautall.txt | grep –v PIE | grep BOU | grep GAL | grep –v SIL | grep –v PRU | wc

Lorsqu’il a fallu réaliser 180 produits puis une somme de 180 termes, c’est EXCEL qui s’est chargé de l’opération, et encore de manière très conviviale. Un copier/coller dans un fichier texte sur PC du résultat de l’inférence, puis une importation de ce fichier texte dans un classeur EXCEL, une cellule (au sens EXCEL) de calcul de produit (dupliquée ensuite 179 fois), et une cellule réalisant la somme des 180 produits, et le tour est joué.

Conclusion

Le problème de trouver le nombre total de positions possibles en est un autre, plus mathématique, qui pourra faire l’objet d’une étude ultérieure. La méthodologie mise en place pourrait résoudre les casse-têtes liés aux positions de Diplomatie publiés de ci delà (reconstitution d’une partie à partir d’informations incomplètes.) Enfin les listes de positions possibles par pays produites pourraient aussi servir à revisiter la théorie des ouvertures.

Je serai ravi de toute confirmation de ce résultat par une autre personne pour le valider de manière définitive…

1^[1] Un calcul manuel plus précis par une tierce personne donne (arrondi par défaut) 6.09 x 10¹⁵

2^[2] Vopaliec, zine papier français consacré à Diplomatie et d’autres jeux, disponible auprès de la personne suivante : jeanpierremaulion-at-wanadoo.fr

3^[3] Noter d’ailleurs au passage que les seuls conflits d’opposition possibles sur toute la carte sont entre ven et tri, et notre purge des oppositions avait donc soigneusement écarté ((Italie : ven – tri, rom t, nap t), (Autriche : tri – ven, vie t, bud t)).

4^[4] Réalisation antérieure à la résolution de ce problème.

5^[5] Noter le « ? » précédant les variables.

6^[6] Conçu par C. Forgy en 1982.

7^[7] Pour la compréhension des lecteurs non familiers d’UNIX, le signe « | » permet de rediriger la sortie d’un processus dans l’entrée d’un autre, et la commande « cat » liste le contenu d’un fichier.