Échecs aléatoires Fischer et dénombrement

Le début d’une partie d’échecs s’appelle une ouverture: ce sont les premiers coups qui sont joués (en général une dizaine, jusqu’à une vingtaine de coups parfois) à partir de la position standard du jeu d’échecs. Il y a différent types d’ouvertures (menant chacune à un type de jeu bien particulier); elles sont étudiées depuis très longtemps, et il existe de très nombreux livres à leur sujet. Tous les meilleurs joueurs d’échecs connaissent par cœur de nombreuses ouvertures et passent des heures à étudier les moindres variations dans celles-ci.

Position de départ classique au jeu d'échecs.

Afin d’éviter le côté « par cœur » et dans le but de juger les joueurs sur leur créativité plutôt que sur leurs connaissances, le célèbre joueur Bobby Fischer (un des plus grands joueurs de tous les temps) a eu l’idée d’inventer une variante du jeu d’échecs, appelée échecs aléatoires Fischer. Le principe est simple: on modifie l’ordre des pièces au départ (voire échiquier ci-dessous). Cet ordre est déterminé au hasard par tirage au sort.

Un exemple de position de départ possible aux échecs aléatoires Fischer.

La question à laquelle nous allons tenter de répondre ici est: combien y a-t-il de positions de départ légales possibles aux échecs aléatoires Fischer ? Bien entendu, nous clarifierons au préalable ce qu’on entend par position de départ légale.

Des chiffres et des lettres

Avant de poursuivre avec les échecs aléatoires, intéressons-nous un moment à compter le nombre de mots possibles à partir d’un certain tirage de lettres. Comme dans l’émission « Des chiffres et des lettres » (que vous regardez tous très assidument je suppose), on se donne un tirage d’un certain nombre de lettres et on essaye de trouver le nombre de mots qu’on peut former à l’aide de toutes ces lettres (chaque lettre devant être utilisée, et une fois seulement). Ici, le terme « mot » est à prendre au sens large, on n’impose pas que tous les mots formés aient un sens.

Commençons par un exemple simple. Combien de mots différents peut-on former à partir des lettres A, B et C ?

D’un point de vue mathématique, un mot consiste à associer une place (1, 2 ou 3) à une lettre (A, B ou C). Par exemple, pour le mot BAC, on effectue l’association

En d’autres termes, un mot peut-être vu comme une bijection de l’ensemble {1,2,3} dans l’ensemble {A,B,C}. On peut montrer que le nombre total de telles bijections est 3! c’est-à-dire 1 x 2 x 3 = 6. On peut aussi vérifier que tous les mots possibles sont ABC, ACB, BAC, BCA, CAB et CBA.
Plus généralement, pour un tirage de n lettres différentes, le nombre total de mots qu’on peut former est n! = 1 x 2 x … x n.

Mais, il peut arriver qu’on souhaite déterminer le nombre de mots qu’on peut composer à partir d’un tirage comprenant plusieurs fois la (ou les) même(s) lettre(s). Considérons le tirage A, B, A, A, C où la lettre A apparaît trois fois. Le problème est qu’on ne peut plus considérer qu’un mot est une bijection de l’ensemble {1, 2, 3, 4, 5} à valeurs dans {A, B, A, A, C} puisque ce dernier ensemble n’est rien autre que {A,B,C} (pour qu’on ait une bijection, les ensembles de départ et d’arrivée doivent avoir le même nombre d’éléments). Pour résoudre ce problème, différencions momentanément ces trois A, en les notant A₁, A₂ et A₃. D’après ce qu’on a dit précédemment, le nombre de mots qu’on peut faire à partir de A₁, B, A₂, A₃ et C est de 5!=1 x 2 x 3 x 4 x 5 = 120. Mais nous souhaitons malgré tout obtenir le même mot à chaque fois qu’on échange A₁, A₂ et A₃. Par exemple, nous considérons que les mots BA₂A₁CA₃ et BA₁A₃CA₂ sont le même mot BAACA.

Pour obtenir le nombre de mots sans distinction des A, il faut donc diviser 120 par le nombre de permutations possibles des lettres A1, A2 et A3, c’est-à-dire par 3! = 6 (autrement dit, on avait compté chaque mot 6 fois de trop). Au final, le nombre de mots qu’on peut former à partir de A, B, A, A, C est de .

De même, si on a le tirage A, A, B, A, B, le nombre de mots total est de car il faut diviser à la fois par le nombre de permutations possibles des lettres A (3!) et par le nombre de permutations possibles des lettres B (2!).

Un premier dénombrement

Il y a deux types de figures aux échecs:

• les pions;
• les pièces, à savoir les deux fous (F), les deux tours (T), les deux cavaliers (C), la dame (D) et la pièce la plus importante, le roi (R).

Tout d’abord, comme au début d’une partie normale, on souhaite, pour des raisons d’équité, qu’aux échecs aléatoires Fischer les pièces des Blancs et des Noirs soient symétriques (par rapport à une ligne séparant les Blancs des Noirs au milieu de l’échiquier; il s’agit donc d’une symétrie axiale). De plus, on laisse tels quels les pions qui sont situés sur la deuxième rangée pour les Blancs, et la septième rangée pour les Noirs.

Cette position de départ est assimilée au mot CTFFCRTD.

On peut assimiler une position de départ à un mot formé avec les lettres de chaque pièce qu’on rencontre en parcourant l’échiquier de gauche à droite: par exemple, la position de départ des échecs usuelles est TCFDRFCT (car de gauche à droite, on a: Tour, Cavalier, Fou, Dame, Roi, Fou, Cavalier, Tour).

Donc, si cette variante des échecs consistait uniquement à modifier l’ordre de départ des pièces, trouver le nombre de positions initiales reviendrait ainsi à compter le nombre de mots qu’on peut écrire à partir du tirage de lettres F, F, T, T, C, C, D, R. Nous avons vu que le nombre de mots possibles est de , c’est-à-dire qu’il y aurait 5040 échiquiers de départ possibles !

Règles pour le placement des pièces aux échecs aléatoires Fischer

Malheureusement, la situation n’est pas si simple. Les échecs aléatoires Fischer imposent des contraintes sur le placement des pièces. Voici la liste des règles:

1. Les pièces des Blancs et des Noirs doivent être symétriques;
2. Les pions occupent toute la deuxième rangée pour les Blancs, et toute la septième rangée pour les Noirs;
3. Les deux fous doivent être situés sur des cases de couleurs opposées;
4. Le roi doit être situé entre les deux tours (afin de permettre un roque, comme dans les échecs habituelles).

Nous pouvons à présent commencer à dénombrer le nombre de positions de départ légales des échecs aléatoires Fischer.

Nous allons placer chacune des pièces des Blancs sur la première ligne en dénombrant le nombre de possibilités pour chacune.

Le premier fou: Puisque nous devons placer les fous sur des cases de couleur opposées, nous allons d’abord placer le premier fou sur une des cases noires de la première ligne. Il y a donc 4 possibilités.

Le second fou: Pour chaque placement du premier fou, le second fou peut être disposé sur une des 4 cases blanches de la première ligne. Ce qui donne 4  x 4 possibilités de placement des deux fous sur des cases de couleurs différentes.

Exemple de placement des fous.

Le roi et les deux tours: C’est le moment où ça se corse. On suppose qu’on a placé les deux fous. Il reste alors 6 cases de libres. Mais puisque le roi doit être situé entre les deux tours, il ne peut être placé ni dans la case libre située le plus à gauche, ni dans la case libre située le plus à droite.

Les cases libres extrêmes sont interdites au roi (cercles rouges). Ici, il y a m=2 cases de libre à gauche du roi pour la première tour, donc (5-m) = 3 cases libres à droite pour la deuxième tour.

Notons m le nombre de cases libres à gauche du roi une fois celui-ci placé (le nombre m est donc compris entre 1 et 4 inclus). Le nombre de cases libres à la droite du roi est donc de (5-m) car une fois celui-là placé, il n’y plus que 5 cases de libres.

• Si m=1, il y a une seule case possible pour la tour située à gauche du roi, et (5-1)=4 possibilités pour la deuxième tour, ce qui donne 1 x 4 = 4 possibilités;
• Si m=2, il y a deux cases possibles pour la tour de gauche, et pour chacune de ces possibilités, il y a (5-2)=3 possibilités pour la tour de droite. Au final, cela donne 2 x 3 possibilités;
• Si m=3, de même, il y a 3 x (5-3) = 6 possibilités pour placer les tours;
• Si m=4, il y a 4 x (5-4) = 4 possibilités pour placer les tours.

Cela donne 4 + 6 + 6 + 4 possibilités de placement du roi et des tours. Ainsi, pour chaque placement des deux fous, il y a 20 possibilités de placement du roi et des tours. Au total, il y a donc 4 x 4 x 20 possibilités de placement des fous, du roi et des tours.

Les cavaliers et la dame: Supposons les fous, le roi et les tours placés. Il reste donc trois cases libres. Il y a autant de façons de placer les cavaliers et la dame sur ces trois cases qu’il y a de mots composables à partir du tirage C, C, D, c’est-à-dire possibilités (CCD, CDC, DCC).

Il n'y a que trois façons de placer la dame et les cavaliers une fois qu'on a placé les fous, le roi et les tours.

Au total, il y a donc 4 x 4 x 20 x 3 = 960 échiquiers de départ possibles aux échecs aléatoires Fischer. C’est pour cette raison que cette variante est parfois appelée « Échecs 960 ».