Analyse & Programmation

Introduction

Le générateur de coups est normalement constitué de deux fonctions.  La première, pour générer les coups de captures et, la deuxième, pour générer les autres coups.

Ça va peut-être être difficile à comprendre ici pourquoi. La raison nous vient d'un besoin du moteur de recherche: La quiescence. Nous allons discuter de la quiescence lorsque nous construirons l'algorithme de recherche alpha-bêta.

Représentation d'un coup

Lorsque nous générons les coups, nous devons avoir une façon efficace de les représenter i.e. d'utiliser le minimum d'espace possible pour réduire au maximum le déplacement d'informations entre la mémoire et le processeur. Nous allons donc calculer le nombre de bits exacts pour chacune des informations que nous avons besoin afin de pouvoir stocker ça dans un mot de 32 bits.

Voici les informations nécessaires à garder pour chaque coup généré: la case de départ, la case d'arrivée, la pièce jouée, la pièce capturée ou la pièce promue, si c'est le cas, la valeur du coup.

Si nous devons garder les pièces jouées, capturées ou promues, c'est parce que cette information servira aussi à défaire les coups sur l'échiquier. La fonction de recherche, plutôt que de copier complète d'une position et de la restaurer, effectue les coups et les défaits car c'est plus rapide que de faire un copie mémoire.

Maintenant, calculons les bits nécessaires.

La case de départ et la case d'arrivée doivent pouvoir stocker des valeurs de 0 à 63. Ce qui nous donne 6 bits maximum.

Les pièces jouées, capturées ou promues doivent pouvoir stocker des valeurs de 1 à 6. Ça nous donne 3 bits.

La valeur du coup dépend de la façon dont nous allons évaluer les coups, comme la capture d'une pièce, le mat ou le positionnement.

Il faut donc y réfléchir à présent.

Valeur de la position

L'évaluation donnée à une position d'échec est très difficile. En fait, c'est là que les jeux sont différents les uns des autres selon moi. Mon professeur d'intelligence artificielle disait que c'était comme les ingrédients d'une recette. Ce sont eux qu'on cache. Pour les recettes, je ne sais pas, mais je suppose que c'est vrai pour les moteurs d'échecs.

Un ordinateur aura beau être hyper rapide, il faudra qu'à un moment donné il arrête de bouger les pièces et qu'il évalue la position et cette position est rarement aussi facile à évaluer qu'un mat ou une nulle. Il faut prendre la position résultante de tous ces coups joués et tenter de donner une valeur à celle-ci. Est-elle meilleure ou pire que les autres évaluées jusqu'à maintenant? Ça s'appelle l'heuristique. Pour un moteur d'échec, on se contente de l'appeler la fonction d'évaluation.

La plupart des moteurs d'échec que j'ai étudié donnait les valeurs suivantes pour leur pièces, nous allons les utiliser:

Pion = 1, Cavalier = 3, Fou = 3, Tour = 5, Dame = 9, Roi ou Mat = INFINI.

Bien entendu, jamais nous allons capturer un roi car les joueurs doivent tout faire pour l'éviter sinon il est mat. Le mat veut dire qu'il n'est plus capable de l'éviter et il n'a donc plus de coups valides à jouer.

Donc nous avons nos valeurs, mais nous devons aussi pouvoir évaluer un coup positionnel et un coup positionnel nous donne normalement une valeur en dessous d'un pion. On aurait donc besoin d'utiliser des décimales. Par contre, nous allons les éviter car ça ralentirait beaucoup les calculs. Nous allons donc multiplier nos valeurs par 100. Ce qui nous donne:

Pion = 100, Cavalier = 300, Fou = 300, Tour = 500, Dame = 900, Roi ou Mat = INFINI.

L'infini en numérique est normalement représenté par la valeur maximale pouvant être représenté par le nombre de bit utilisés. Pour faire plus simple, nous allons utiliser une valeur assez grande mais puissant être stockée dans le reste des bits disponibles de notre structure. Il nous reste 14 bits, ce qui nous donne 4095, mais nous allons nous contenter de 3000.

Voici donc la structure en C:

struct  {
 uint source : 6;
 uint dest   : 6;
 int piece   : 3;
 int capture : 3;
 uint score  : 14;
} coup;

Les bitboards

Il y a d'autres méthodes pour générer les coups, mais celle que je connais le mieux utilise les bitboards. Monik, le moteur d'échec que j'ai conçu utilise les bitboards pour générer ses coups. Aujourd'hui, avec les processeurs 64 bits de plus en plus présents, les bitboards ont, d'après moi, un net avantage par rapport aux autres méthodes.

Les bitboards, vous l'aurez sûrement deviné, utilisent les bits pour représenter des positions sur l'échiquier. Puisque le bit ne peut représenter que deux valeurs possibles le 0 et le 1, il est nécessaire d'utiliser plusieurs bitboards pour représenter un échiquier au complet.

Nous avons un bitboard pour représenter les pions blancs, les pions noirs, les cavaliers blancs, les cavaliers noirs ainsi de suite jusqu'au roi présents sur l'échiquier.

Prenons par exemple les pions blancs.

La bitboard pour les pions blancs sur un échiquier de départ est le suivant:

00000000
00000000
00000000
00000000
00000000
11111111
00000000

En hexadécimale, la valeur est la suivante:

Bitboard pionb = 0x0000000000FF00;

Ce n'est pas très difficile jusqu'à maintenant.

Mais comment fait-on pour générer des coups avec ça?

Et bien, il faut encore plus de bitboards. Il faut un bitboard pour chaque position possible d'une pièce tout en représentant ses coups. Dan le cas des pions, il faut un bitboard pour un coup normal et un autre, pour les prises, car les pions bougent différemment selon qu'ils avancent ou qu'ils prennent une pièce.

Pour le pion blanc à la case A2, par exemple, nous avons le bitboard suivant:

00000000
00000000
00000000
00000000
00000000
01000000
00000000
00000000

Je vous laisse calculer la valeur par vous-même.

Vous mettez ce bitboard dans un tableau de 64 et lorsque vous voulez connaître les cases attaquées par le pion en a2, vous faites:

bitboard att = attpionb[A2];

Bien sûr, pour que la prise soit valide, il faut une pièce noire en B3. Pour générer un coup valide, vous prenez le bitboard des pièces noires -vous devez en avoir un- et vous faites un ET logique avec le bitboard d'attaque du pion en A2. S'il se trouve une pièce en B3, le bit B3 restera à un. Ensuite, vous convertissez ce bit en position de 0 à 63 et vous avez un coup valide. Voici le code que ça pourrait donner:

bitboard att = attpion[A2] & piecen;
if (att) {
  coup uncoup;
  uncoup.From = A2;
  uncoup.To = BitboardToPosition(att);
  uncoup.Piece = PION;  ajouteCoup(uncoup);
}

Les pièces glissantes

Nous allons sauter les cavaliers et le roi car ils sont trivial à implanter car ce sont des pièces qui ne glissent pas. Nous allons passer directement aux pièces qui glissent. Les pièces qui glissent sont plus difficile à implanter car le nombre de coups possibles dépend des pièces dans le chemin.

Nous pourrions toujours utiliser une petite boucle mais alors l'utilisation des bitboards deviendrait moins utile.

Pour commencer, nous avons besoin d'une autre liste de bitboards pour indiquer les cases attaquées par la tour pour toutes les positions possibles sur l'échiquier de cette tour. Ces bitboards pourrons aussi servir pour la dame car elle peut aussi glisser dans les mêmes directions de la tour.

Nous avons besoins d'une liste de bitboards pour toutes les directions que la tour peu prendre. Les directions de notre tour avec la notation que nous avons étudiez dans la représention de l'échiquier sont 1, 8, -1 et -8.

Appellons les alors plus1[64], plus8[64], moins1[64], moins8[64].

Un exemple, supponsons que nous avons une tour en A1. Nous voulons connaître toutes les cases attaquées vers la droite. Nous prenons alors le bitboard plus1[A1].

Ça nous donne le bitboard suivant:

- - - - - - - -
- - - - - - - -
- - - - - - - -
- - - - - - - -
- - - - - - - -
- - - - - - - -
- - - - - - - -
- x x x x x x x

La plupart du temps, y a des pièces rencontrées. Supposons alors qu'il y a une pièce en A4.

Nous devons exclure les cases A5, A6, A7, A8 et nous voulons le faire sans boucle biensûr.

C'est en réalité assez simple.

Vous prenez le même bitboard plus1 mais pour la case A4 qui nous donne le bitboard suivant:

- - - - - - - -
- - - - - - - -
- - - - - - - -
- - - - - - - -
- - - - - - - -
- - - - - - - -
- - - - - - - -
- - - - x x x x

- - - - - - - -

Vous faites alors un ou exclusif et le résultat sera le suivant:

- - - - - - - -
- - - - - - - -
- - - - - - - -
- - - - - - - -
- - - - - - - -
- - - - - - - -
- - - - - - - -
- x x x - - - -

Ce qui donne les cases A2, A3, A4.

Il suffit alors de déterminer si la case A4 est valide ou non selon si vous êtes entrain de générer des attaques et si c'est une pièces adverse.

Ensuite, vous faites la même chose pour les 3 autres directions en prenant les listes de bitboards plus8, moins1 et moins8. Le principe est le même pour les diagonales des fous. Vous générez les bitboards plus7, moins7, plus9, moins9.

Premier et dernier bit

Il y a deux fonctions dont vous allez avoir besoin. Ce sont les fonctions pour trouver le premier bit et le dernier bit à partir d'une position donnée.

Pour trouver la pièce rencontrer en A4 dans l'exemple plus haut, nous nous faisons un ET logique avec le bitboard des pièces sur l'échiquier et cela nous donne un bitboard avec le bit A4 à 1. Mais il nous faut le convertir en position de 0 à 63. Pour ça, nous utilisons une fonctionne qui retourne le premier bit ou le dernier bit. Cela dépend de l'architecture de votre ordinateur, Big indian ou little indian. La technique que j'emploie dans mon propre moteur consiste à générer un index pour chaque valeur sur 16 bits et le premier bit correspondant. Ça évite d'utiliser une boucle pour le calcul. Il suffit de diviser le mot en 4 parties de 16 bits et ensuite ramener la valeur indexée sur 16 bits.

J'espère que ce tutoriel vous aidera si l'envie vous prend de programmer un jeu d'échecs en utilisant les bitboards.

Si vous pensez qu'il y a des parties qui ne sont pas claires dans mon tutoriel et qui méritent d'être revues, laisser moi un commentaire et j'essaierai de corriger ça.