Fonctionnement d'un jeu d'échecs

Introduction

Depuis 20 ans, une centaine de programmes d'échecs ont été commercialisés, et ce chiffre doit approcher les 500 si l'on compte les programmes amateurs. Pourtant, en première analyse, tous reposent sur des principes identiques qui ont fait leurs preuves dans la théorie du jeu (algorithme minimax et alpha-bêta...).

En deuxième analyse il s'avère que puisqu'il y a des programmes plus forts que d'autres, il doit y avoir quand même quelques différences et celles ci, nous le verrons, se feront surtout au niveau de la fonction d'évaluation -qui est en quelque sorte le moteur du jeu- et qui sera propre à chaque programmeur.

A noter que la programmation d'un jeu d'échec n'est pas une science exacte et que donc ma façon de voir les choses est peut-être erronée.

Tout d'abord, posons quelques règles de base.

L'échiquier, ses limites et le mouvement des pièces

Je vais citer plusieurs méthodes, mais sachez que mon jeu d'échecs emploiera la troisième (bitboard).

Commençons par faire simple, puisqu'aux échecs une case peut-être occupée par une des six pièces blanches, une des six pièces noires ou tout simplement être vide, on va coder chaque type de pièce par une valeur numérique. Il nous vient tout de suite à l'idée qu'une valeur s'échelonnant de -6 à 6 serait largement suffisant (On pourrait également différentier chaque pièce, ex: cavalier blanc dame et cavalier blanc roi).

Ainsi on aura:

0	Case vide
1	Case occupée par un pion blanc
2	Case occupée par un cavalier blanc
3	Case occupée par un fou blanc
4	Case occupée par une tour blanche
5	Case occupée par une dame blanche
6	Case occupée par le roi blanc

Leurs homologues noirs seront négatives. Passons à l'étape suivante.

Pour les deux premières méthodes, la différence va se faire au niveau de la représentation de l'échiquier.
Voici la première: Chaque case est située en fonction de sa colonne et de sa ligne et est donc un élément de la matrice carrée 8x8 suivante (gréco-latin):

Cette notation, très proche de la notation échiquéenne, à le mérite d'être clair; ainsi le mouvement e2-e4 sera codé par (5, 2)-(5, 4).
En plus, en calculant au préalable tous les vecteurs directeurs de la dite pièce, cette disposition permettra de trouver très facilement si une pièce est hors des limites de l'échiquier.
Par exemple si la pièce est une tour, ses vecteurs directeurs seront : (-1, 0), (1, 0), (0,-1), (0, 1) signifiant respectivement : "déplacer la tour vers la gauche", "déplacer la tour vers la droite ", "déplacer la tour vers le bas" et "déplacer la tour vers le haut". Maintenant si elle est positionnée en (3, 4) (donc c4 ) on ajoutera les vecteurs directeurs à ce couple jusqu'à ce que la somme donne un couple dont les valeurs n'appartiennent plus à la matrice . Aussi ici pour la première direction on aura (2, 4) et (1, 4) valides puis (0, 4) qu'on éliminera d'office, on répètera cette opération pour les trois autres directions.
Voici les vecteurs directeurs de chaque pièce:

Pion blanc	(0, 1), (0, 2) si le pion n'a pas encore bougé, (1, 1) et (-1, 1) pour les prises
Pion noir	(0,-1), (0,-2) si le pion n'a pas encore bougé, (-1,-1) et (1,-1) pour les prises
Cavalier	(-2, 1), (-1, 2), (1, 2), (2, 1), (2,-1), (1, 2), (-1,-2), (-2,-1)
Fou	(-1, 1), (1, 1), (1,-1), (-1,-1)
Tour	(-1, 0), (0, 1), (1, 0), (0,-1), plus les roques
Dame	(-1, 0), (0, 1), (1, 0), (0,-1), (-1, 1), (1, 1), (1,-1), (-1,-1)
Roi	(-1, 0), (0, 1), (1, 0), (0,-1), (-1, 1), (1, 1), (1,-1), (-1,-1), plus les roques

Un inconvénient est qu'elle utilise des tableaux à deux dimensions. Or les opérations sont plus compliquées que sur un tableau unidimensionnel et donc un peu plus longues à effectuer pour le processeur... et répétés un million de fois par seconde pendant trois minutes, cela devient vraiment un handicape.

Donc voyons la deuxième méthode qui tente de résoudre cette perte de temps.

Nous allons ici utiliser un échiquier à une dimension... Examinons ce que cela donnerait avec un tableau 8x8:

Soit la même tour qu'au cas précédent positionnée en 26 (c4), analysons ses mouvements vers la gauche; on voudrait décrémenter de 1 jusqu'à atteindre les limites de l'échiquier. Or, on voit que si cela marche en effet pour les cases 25 et 24, ce n'est plus le cas ensuite puisqu'il n'y a aucune condition d'arrêt.

Aussi nous allons utiliser une matrice carrée de 144 éléments (cet échiquier étendue est appelé Mailbox) qui donnera la possibilité de déterminer rapidement si une pièce sort de l'échiquier :

Chacun de ces éléments comprend comme dans la première méthode des valeurs de -6 à 6 mais pour délimiter l'échiquier une valeur en plus est nécessaire. Nous prendrons 7. On complétera notre tableau ainsi:

7	Case hors des limites de l'échiquier

Nous aurons par exemple dans la position de départ l'échiquier suivant:

Bien sûr les cases 7 garderont toujours les mêmes valeurs tandis que la valeur des autres évoluera au cours de la partie.

Maintenant si la tour est en 64 (c4) et que la condition d'arrêt est "valeur de la case d'arrivée=7" on pourra décrémenter de 1 jusqu'à atteindre une case de valeur 7. On trouvera 63, 62 et se sera tout puisque la valeur de la case 61 a pour valeur 7.

Nous écrirons donc la fonction Init(), qui initialise l'échiquier, ainsi (en C/C++):

Les directions de chaque pièce seront les suivantes:

Pion blanc	+12, +24 si le pion n'a pas encore bougé, +11 et +13 pour les prises
Pion noir	-12, -24 si le pion n'a pas encore bougé, -13 et -11 pour les prises
Cavalier	+10, +23, +25, +14, -10, -23, -25, -14
Fou	+11, +13, -11, -13
Tour	-1, +12, +1, -12, plus les roques
Dame	-1, +11, +12, +13, +1, -11, -12, -13
Roi	-1, +11, +12, +13, +1, -11, -12, -13, plus les roques

Venons-en à la troisième technique: les Bitboard.

Les bitboard

Depuis la venue des processeurs 64 bits (genre Pentium) il est apparue une nouvelle méthode de codage de l'échiquier. Celle ci s'est vite imposée autant par son côté esthétique que par sa vitesse de traitement. En effet un processeur est dit 64 bits lorsqu'il peut traiter, en un cycle d'horloge, un nombre -ou un mot- de 64 bits. Or un échiquier est pourvu de 64 cases...de là il n'y qu'un pas à franchir pour optimiser le temps de traitement d'une position. De plus en opérant directement à l'aide d'une notation binaire, on peut utiliser les opérateurs booléens ainsi que les opérateurs de décalages (voir ces termes dans le glossaire) qui permettent de multiplier (par un multiple de 2) très rapidement un nombre.

Vu qu'un seul de ces nombres de 64 bits ne suffira pas du tout à coder l'échiquier on va en utiliser plusieurs qui représenteront la position des pions blancs, la position des pions noirs, etc.
Par exemple, on aura une variable nommée "WhitePieces" qui donnera le statut des pièces blanches, une variable nommée "WhiteKnights" qui donnera la position des cavaliers blancs...
Elles auront respectivement pour valeurs initiales 0000000000000000000000000000000000000000000000001111111111111111 et 0000000000000000000000000000000000000000000000000000000001000010 qu'on préférera représenter ainsi:

et: