Cet article est une présentation du jeu des échecs aléatoires de Fischer, considéré 1° comme un problème mathématique et 2° comme un exercice de programmation.
On présente une méthode pour produire toutes les positions de départ possibles du jeu. Cette méthode est mise en œuvre dans un programme informatique en langage Pascal.
Les échecs aléatoires de Fischer (en anglais Fischer random chess ou chess 960) sont une variante du jeu des échecs inventée par Robert James Fischer. Les règles du jeu sont les mêmes que celles des échecs traditionnels, à une ou deux choses près. La première, celle qui donne au jeu son nom, c'est que la position de départ change à chaque partie. La seconde, qui est la conséquence de la première, concerne la façon d'effectuer le roque.
Au début de la partie les pièces majeures (autres que les pions) sont placées de façon aléatoire, sur les mêmes lignes que dans le jeu traditionnel : pièces blanches sur la ligne 1, pièces noires sur la ligne 8. Les pions sont à leur place habituelle.
Une image valant mieux qu'un long discours, voici comment les pièces blanches sont placées dans le jeu d'échecs traditionnel.
Et voici un exemple de la façon dont les mêmes pièces peuvent être placées au début d'une partie d'échecs aléatoires.
Cette répartition aléatoire obéit néanmoins à certaines règles.
Combien de façons différentes y a-t-il de placer les pièces ?
Comment produire toutes les positions possibles ?
C'est ce que nous allons apprendre.
Voici la méthode proposée par Hans Bodlaender pour obtenir une position de départ au moyen d'un dé qu'on lance cinq fois.
Il reste trois cases vides. On place une tour sur la première, le roi sur la deuxième et l'autre tour sur la troisième.
Les pions sont à leur place habituelle. Les pièces noires sont disposées comme les pièces blanches. Le roi fait face au roi, etc.
À présent il est aisé de calculer le nombre de positions possibles.
Les cinq lancers du dé (abstraction faite des cas où le dé a dû être relancé) peuvent produire 4 x 4 x 6 x 5 x 4 = 1920 séquences ou combinaisons différentes.
Cependant par cette méthode on a produit toutes les positions en double. En effet pour chaque séquence, il y a une séquence différente qui produit le même résultat (la même position), parce qu'il y a deux façon de placer les cavaliers qui reviennent au même. Par exemple, quelle que soit la valeur de a, b et c, la séquence a, b, c, 1, 1 produit le même résultat que la séquence a, b, c, 2, 1.
Il n'y a donc en réalité que 1920 / 2 = 960 positions différentes, d'où le nom d'échecs 960 qui est donné à ce jeu.
Nous voici donc en possession d'une méthode permettant de produire toutes les positions de départ possibles au jeu des échecs aléatoires. Il nous reste cependant un problème à régler, relatif à la notation que nous allons utiliser pour représenter ces positions.
Il s'agit, plus précisément, d'un problème relatif au droit de roquer. La règle du roque au jeu des échecs aléatoires est la suivante : quelles que soient les positions respectives du roi et de la tour qui participe au roque, les deux pièces se retrouvent après le roque dans la même position qu'après un roque au jeu des échecs traditionnels. Par exemple si le roi blanc, se trouvant en c1, roque côté a (on ne peut plus dire côté dame), il reste en c1. Seule la tour se déplace.
La notation Forsyth-Edwards, communément utilisée pour représenter une position au jeu des échecs, doit être modifiée pour le jeu des échecs aléatoires.
En effet, dans le jeu des échecs traditionnel, le roque ne peut avoir lieu que si le roi se trouve sur la colonne e, et la tour sur la colonne a (côté dame) ou h (côté roi). Dans le jeu des échecs aléatoires, on ne peut pas savoir a priori quelle est la position du roi ni quelle est celle de la tour.
Or il peut arriver qu'une tour se soit déplacée et soit passée de l'autre côté du roi, du même côté donc que la tour avec laquelle le roi a éventuellement le droit de roquer. La position est alors ambiguë, et la notation Forsyth-Edwards ne suffit pas à indiquer quel est le coup éventuellement autorisé (je dis éventuellement autorisé car les conditions habituelles pour une possibilité effective de roquer s'appliquent aux échecs aléatoires).
On a donc imaginé de substituer aux symboles habituels (K, Q, k, q), — soit seulement en cas d'ambiguïté2, soit de façon systématique, — les lettres correspondant à la colonne de la tour autorisée à roquer.
La première approche (connue sous le nom de notation X-FEN) a l'avantage de préserver la compatibilité avec la notation Forsyth-Edwards originale : on n'utilise la lettre de la colonne que lorsque cela est nécessaire.
La deuxième approche (c'est la notation Shredder-FEN) a l'avantage d'être plus simple à produire. Cette notation est ainsi surnommée à cause du logiciel Shredder qui en fait usage.
Pour la position de départ classique en notation Shredder-FEN, l'autorisation de roquer sera notée AHah.
La méthode présentée plus haut a été mise en œuvre dans un programme en langage Pascal.
L'unité fischerandom.pas contient la
fonction StartPosition(), qui pour cinq valeurs entières
données (correspondant à cinq lancers réussis du dé) renvoie une chaîne
de caractères qui est la position au format FEN. Un cinquième paramètre
de type booléen permet de choisir de générer ou une chaîne FEN entière,
ou seulement les pièces majeures. Le sixième paramètre permet de choisir
la notation utilisée pour le roque (X-FEN ou S-FEN).
{ Positions de départ aux échecs de Fischer, par la méthode de Hans Bodlaender. }
function StartPosition(a, b, c, d, e: integer; const AFullFEN: boolean = FALSE; const ASchredderFEN: boolean = FALSE): string; overload;Deux versions surchargées de la fonction sont également disponibles : l'une à laquelle on ne passe qu'un seul nombre entier au lieu de 5 (un nombre compris entre 1 et 1960), l'autre à laquelle on ne passe aucun nombre et qui produit elle-même un nombre au hasard.
function StartPosition(i: integer): string; overload;
function StartPosition(): string; overload;La deuxième version de la fonction convertit l'unique nombre entier en cinq nombres. Par exemple, si le nombre passé en paramètre est 1, la version originale de la fonction sera appelée avec les paramètres 1, 1, 1, 1, 1.
Autres exemples.
| Paramètre unique | Paramètres multiples |
|---|---|
| 2 | 1, 1, 1, 1, 2 |
| 3 | 1, 1, 1, 1, 3 |
| 4 | 1, 1, 1, 1, 4 |
| 5 | 1, 1, 1, 2, 1 |
On peut déduire de ce qui précède qu'il existe 960 positions de départ différentes au jeu des échecs aléatoires. Nous n'avons présenté qu'une seule méthode pour produire ces différentes positions. Il y en a d'autres3.
Il est à noter que l'une4 de ces 960 positions est la position de départ des échecs traditionnels. Les vieux échecs, pour parler comme Bobby Fischer5, peuvent donc être considérés comme un cas particulier des nouveaux échecs. Une personne ou un programme informatique capable de jouer aux échecs aléatoires est aussi capable de jouer aux échecs ordinaires.
Cet article s'appuie sur un document écrit en anglais par David A. Wheeler et intitulé Fischer Random Chess. La méthode pour générer la position de départ est due à Hans Bodlaender.
Si vous le souhaitez, vous pouvez télécharger les sources de cet article.
La case la plus à gauche sur la ligne 1 de l'échiquier est une case noire.↩︎
L'auteur de cette proposition, Reinhard Scharnagl, suggère de n'utiliser la lettre de la colonne que lorsque la tour autorisée à roquer n'est pas celle qui est le plus à l'extérieur de l'échiquier.↩︎
Le programme northam.pas met en œuvre la méthode proposée par Edward Northam.↩︎
Selon la numérotation proposée par Reinhard Scharnagl (et désormais communément adoptée) il s'agit de la position 518, en comptant à partir de zéro.↩︎