README

Position initiale des pièces au jeu des échecs aléatoires de Fischer

Introduction

Cet article est une présentation sommaire du jeu des échecs aléatoires de Fischer, considéré comme un problème mathématique et algorithmique. L'article 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.

Règles des échecs aléatoires

Les échecs aléatoires de Fischer (en anglais Fischer Random Chess ou Chess960) 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.

• Les deux fous doivent se trouver sur des cases de couleur différente.
• Le roi doit être placé quelque part entre les deux tours : autrement dit les deux tours ne doivent pas se trouver du même côté du roi, cela pour que le roque soit toujours possible des deux côtés.
• Les pièces blanches et les pièces noires doivent être placées dans le même ordre, de sorte que le roi blanc soit sur la même colonne que le roi noir, la dame blanche sur la même colonne que la dame noire, etc.

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.

Méthode pour produire une nouvelle position au moyen d'un dé

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.

1. Lancer le dé et placer un fou blanc sur la case noire[^1] indiquée par le dé. On compte à partir de la gauche. Ainsi 1 correspond à la case a1, 2 à la case c1, etc. Si on obtient un 5 ou un 6, on relance le dé jusqu'à ce qu'on obtienne un nombre compris entre 1 et 4 (puisqu'il n'y a que quatre cases noires par ligne).
2. Lancer le dé et placer un fou blanc sur la case blanche indiquée par le dé. 1 correspond à la case b1, 2 à la case d1, etc. Là encore, on relance le dé si on obtient un nombre supérieur à 4.
3. Il reste six cases vides. Lancer le dé et placer la dame sur la case vide indiquée par le dé.
4. Il reste cinq cases vides. Lancer le dé et placer un cavalier sur la case vide indiquée par le dé. Si on obtient un 6, on relance le dé.
5. Il reste quatre cases vides. Lancer le dé et placer un cavalier sur la case vide indiquée par le dé. Si on obtient un 5 ou un 6, on relance le dé.

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.

Dénombrement des positions

À 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 souvent donné à ce jeu.

Problème du roque et notation Forsyth-Edwards modifiée

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 commercial Shredder (de Stefan Meyer-Kahlen) qui en fait usage.

Pour la position de départ classique en notation Shredder-FEN, l'autorisation de roquer sera notée AHah.

Programme en Pascal

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.

Conclusion

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'autres[^5].

Il est à noter que l'une[^4] de ces 960 positions est la position de départ des échecs traditionnels. Les vieux échecs, pour parler comme Bobby Fischer[^3], 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.

[^1]: La case la plus à gauche sur la ligne 1 de l'échiquier est une case noire. [^2]: 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. [^4]: 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. [^3]: Extraits d'un entretien accordé à une radio islandaise. [^5]: Le programme northam.pas met en œuvre la méthode proposée par Edward Northam.