Analyse & Programmation

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);
}

<< Préc - Suivant >>