Avertissement au lecteur : Ce chapitre est un peu technique mais il est très intéressant. Je cherche un bon mathématicien pour le compléter et le valider. Par ailleurs - concernant la notation - n^m signifie n à la puissance m (notation adaptée à une page HTML).

Etude de la combinatoire

A priori deux méthodes permettent d'évoquer la combinatoire de jeux de tactique :
1) la méthode dynamique par l'arbre des coups (méthode temporelle),
2) la méthode statique par le nombre d'états possibles (méthode atemporelle).

La méthode de l'arbre des coups

Evaluer l'arbre des coups consiste à multiplier le nombre de possibilités du joueur 1 par celle du joueur 2 au premier coup puis dans les coups suivants.

Exemple :
• Aux Echecs : 20 x 20 = 400 choix pour le 1er coup. (20 = 16 coups de pions + 4 coups de cavalier possible)
• A Dérive : 30 x 30 = 900 choix pour le 1er coup. (30 = 5 cases x 6 valeurs possibles), ou 5 x 5 = 2^5 choix pour le 1er coup (si la valeur initiale est imposée à 1).

Inconvénient de cette méthode : dénombre des coups qui retombent sur des positions déjà rencontrées.

Cette méthode est pourtant souvent évoquée pour évoquer l'explosion combinatoire d'un jeu tactique qui repose sur quelques actions simples.

La méthode du nombre d'états possibles

La méthode du nombre d'états possibles consiste à dénombrer tous les états possibles en tenant compte de l'espace, des pièces et des règles du jeu.

Cette méthode possède l'avantage de ne pas comptabiliser deux fois un même état. Elle est donc nettement plus représentative.

Inconvénient d'une étude combinatoire

Quelle que soit la méthode choisie, une étude combinatoire dénombre aussi bien les coups sensés que les coups absurdes vis à vis de l'objectif à réaliser.

La combinatoire de Dérive

Attachons nous à découvrir le potentiel de Dérive par le biais du nombre d'états possibles du plateau de jeu.

Le plateau de jeu de Dérive est composé de cinquante cases utiles dans tous les niveaux de jeu.

Pour commencer le raisonnement, plaçons nous dans l’hypothèse du niveau 1, à 2 joueurs.

Considérons un dé sur le plateau. Quelle valeur possède-t-il ? Elle est comprise entre 1 et 6. Quelle couleur a-t-il ? La couleur d'un des deux joueurs. Le case occupée possède donc 6*2=12 états possibles.

Ce raisonnement peut être tenu jusqu’au placement potentiel des 5 dés d'un joueur. La combinatoire est donc 12^5 pour le placement des 5 premières pièces sur 5 cases données. Ensuite, les dés appartiendront nécessairement à l'un des joeurs, d'où 6 états possibles seulement pour chaque case. La combinatoire est alors de 6^5 pour le placement de 5 dernieres pièces. D'où une combinatoire de 12^5*6^5.

Ce premier dénombrement est à multiplier par le nombre de manières qu’il y a de choisir 10 cases parmi les cases autorisées. Autrement dit pour répondre à la question : où sont les pièces des joueurs sur le plateau ? A priori, les joueurs disposent des 32 cases du centre plus les 4 cases de chacune de leur rive non commune avec tout autre rive, plus une case par rive : soit 39 cases. Ce nombre de cases est minoré : il considère chacune des rives adverses comme une case unique.

Pour le placement de 10 dés, cette combinatoire est donc donnée par C(39,10).

Il est rappelé que C(n,p) = A(n,p) / p ! = n ! / (n-p) ! p !
Donc, C(n,p) = n * (n-1) * ... (n-p+1) / p * (p-1) * ... 2

Par ailleurs, le nombre de dés sur le plateau peut varier entre 10 et 0. Ce que nous exprimons ainsi :
Somme(i=1,5;12^(5-i+1)*6^5 * C(39,10-i+1))+Somme(i=1,5;6^(5-i+1) * C(39,5-i+1))

De manière plus générale, soit n le nombre de pièces par joueur au niveau considéré. Le nombre de combinaisons minoré est donné par :
- A 2 joueurs :
Somme(i=1,n;12^(n-i+1)*6n * C(39,2n-i+1))
+Somme(i=1,n;6^(n-i +1)* C(39,n-i+1))
- A 3 joueurs :
Somme(i=1,n;18^(n-i+1)*12n*6n*C(39,3n-i+1))
+Somme(i=1,n;12^(n-i+1)*6n * C(39,2n-i+1))
+Somme(i=1,n;6^(n-i+1)* C(39,n-i+1))
- A 4 joueurs :
Somme(i=1,n;24^(n-i+1)*18n*12n*6n * C(39,4n-i+1))
+Somme(i=1,n;18^(n-i+1)*12n*6n * C(39,3n-i+1))
+Somme(i=1,n;12^(n-i+1)*6n * C(39,2n-i+1))
+Somme(i=1,n;6^(n-i+1) * C(39,n-i+1))

La dernière formule est à corriger si n < p dans une expression C(n,p). Dans ce cas, le facteur en question s'annule : ceci signifie qu'on ne peut placer plus de dés qu'il n'y a de cases.

Le lecteur pourra librement évaluer ces expressions.

Il est instructif de comparer cette combinatoire avec celle des Dames et des Echecs.

La combinatoire des Dames

Le nombre de cases utiles est de 50. Une case est occupée par un pion ou une dame pour un joueur donné, elle possède donc 4 états possibles. Le nombre de pions ou dames par joueurs est de 20.

La combinatoire de l’état du plateau de dames est donc donnée par :
Somme(i=1,20;4^(20-i+1)*220 * C(50,40-i+1))
+Somme(i=1,20;2^(20-i +1)* C(50,20-i+1))
ou, si l'on ne tient plus compte de la présence des dames (expression minorée, donc) :
Somme(i=1,20;2^(20-i+1)*C(50,40-i+1))
+Somme(i=1,20; C(50,20-i+1)).

La combinatoire des Echecs

Le nombre de cases utiles aux échecs est de 64.

Considérons une pièce sur le plateau. Quelle valeur possède-t-elle ? Elle peut prendre six valeurs : P, T, F, C, D, R. Quelle couleur a-t-elle ? La couleur d'un des deux joueurs. Le case occupée possède donc 6*2=12 états possibles.

Combien y-a-t-il de pièces : 16 par joueurs.

La combinatoire majorée est donc donnée par :
Somme(i=1,16;12^(16-i+1)*616* C(64,32-i+1))
+Somme(i=1,16;6^(16-i+1)* C(64,16-i+1))

Cette combinatoire est largement majorée puisqu’elle considère la possibilité d’avoir 15 pièces identiques pour un joueur sur le plateau (par exemple, 15 cavaliers ou même 15 Rois !) ce qui ­ bien sûr ­ est impossible.

Il convient donc d’être plus précis : seuls les 8 pions ont potentiellement 5 valeurs possibles puis il convient de placer les 2 Tours, puis les 2 Fous, puis les 2 Cavaliers, puis la Dame puis le Roi (qui est obligatoirement présent).

La combinatoire de l’état du plateau d’Echecs est donc donnée par :
Somme(i=1,8;12^(8-i+1)*11^2* 10^2* 9^2* 8 * 7* 6^8* 5^2* 4^2*3^2*2*C(64,32-i+1))
+Somme(i=1,2;11^(2-i+1)* 10^2* 9^2* 8 * 7* 6^8* 5^2* 4^2*3^2*2*C(64,24-i+1))
+Somme(i=1,2;10^(2-i+1)* 9^2* 8 * 7* 6^8* 5^2* 4^2*3^2*2*C(64,22-i+1))
+Somme(i=1,2;9^(2-i+1)* 8 * 7* 6^8* 5^2* 4^2*3^2*2*C(64,20-i+1))
+(8 * 7* 6^8* 5^2* 4^2*3^2*2*C(64,18))
+(7* 6^8* 5^2* 4^2*3^2*2*C(64,17))
+Somme(i=1,8;6^(8-i+1)* 5^2* 4^2*3^2*2*C(64,16-i+1))
+Somme(i=1,2;5^(2-i+1)* 4^2*3^2*2*C(64,8-i+1))
+Somme(i=1,2;4^(2-i+1)*3^2*2*C(64,6-i+1))
+Somme(i=1,2;3^(2-i+1)*2*C(64,4-i+1))
+2*C(64,2)

Pour comparer la combinatoire de Dérive, des Dames et des Echecs, il convient d’évaluer chacune des expressions. Nous laissons pour l'instant le soin au lecteur de le faire (...)

Combinatoire de Dérive au niveau 1, à 2 joueurs	1,2651E+18
Combinatoire de Dérive au niveau 6, à 2 joueurs
Combinatoire de Dérive au niveau 6, à 4 joueurs
Combinatoire minorée aux Dames
Combinatoire aux Dames
Combinatoire majorée aux Echecs
Combinatoire aux Echecs

Dans tous les cas, la combinatoire est supérieure au milliard de milliard d’états possibles (1E+18).

La combinatoire de Dérive à 2 joueurs est du même ordre que celle des dames.

La combinatoire de Dérive à 4 joueurs est du même ordre que celle des Echecs.