Bon, une première version (la version 5). Rien de bien sophistiqué.

Je garde la même direction jusqu'à ce quelque chose le bloque dans ce cas il choisi une nouvelle direction.
Aucune recherche pour l'instant, par contre, une fourmi tournera vers une nourriture ou un nid adverse lorsqu'il a arrive à la même hauteur que celui-ci.

À l'écriture de ce texte, il a joué une partie et on voit déjà une grande différence.

Certaines mappes ont l'air de vrai labyrinthe. Il va falloir une forme de recherche sinon les fourmis demeurent toutes dans le même coin et ils finissent par se rentrer les unes dans les autres et meurent.

La guerre des fourmis

J'aime beaucoup le langage Lisp. Pour me pratiquer un peu, j'ai décidé de participer à un concours d'intelligence artificielle: http://aichallenge.org/profile.php?user=11421


Pour le moment, je n'ai soumis que le robot de base qui vient avec le starter kit.

L'évaluateur

L'évaluateur est un peu comme la personnalité de votre moteur. C'est cette partie qui déterminera comment va réellement jouer votre moteur. Je parle du style pas nécessairement de sa force. Biensûr, si vous n'avez presque pas de connaissance du jeu d'échecs, il vous sera difficile de faire un moteur potable. Pour l'écrire, il faut un minimum de connaissance du jeu.

---

L'évaluateur à la base se divise en deux parties.

1. L'évaluation matérielle;
2. L'évaluation positionnelle.

---

L'évaluation matérielle

L'évaluation du matériel peut sembler facile à première vue. Ne suffit-il pas de donner une valeur pour chaque type de pièce des deux cotés et en faire le total? Et bien, cela ne prendrait pas en compte la variabilité de la valeur des pièces. La tour, le cavalier ou même le pion que vous avez de plus devient beaucoup plus important lorsque la majorité des autres pièces ont disparues. L'évaluateur doit donc prendre en compte ce fait et doit donc amener le moteur à échanger des pièces s'il a du matériel en plus.

Pour comprendre, supposons que l'évaluateur doit donner une valeur aux deux situations décrites plus bas en prenant les valeurs des pièces suivantes

int pion = 100, fou = 300, tour = 500;

et la formule qui suit:

scoremat = (nbpionblanc * 100 + nbfoublanc * 300 + nbtourblanche * 500)
- (nbpionnoir * 100 + nbfounoir * 300 + nbtournoire* 500);

Voici les deux situations:

2 pions, 1 fou et 1 tour contre 2 pions, 1 tour

2 pions, 1 fou contre 2 pions.

L'évaluateur retournera un score matériel identique pour les deux positions et pourtant la deuxième position est légèrement plus désirable que l'autre.

Il faut donc une formule qui prend en compte cet avantage.

Un façon facile serait de calculer un pourcentage des valeurs des pièces selon le nombre de pièces total sur le jeu. Ce n'est un exemple, mais je vous laisse trouver par vous même car le but c'est d'avoir un jeu à soi.

---

L'évaluation positionnelle

Comme vous le savez, une partie d'échec possède trois phases importantes. L'ouverture, le milieu de partie et la finale.

Lors de l'ouverture, le joueur doit déployer ses forces le plus rapidement possible afin de pouvoir attaquer en milieu de partie. Il doit aussi mettre son roi à l'abri au moment opportun pour éviter les attaques.

Dans le milieu de partie, le joueur doit trouver un moyen de prendre un avantage, si possible matériel comme un pion ou deux, sinon positionnelle, un pion passé protégé, détruire la défense du roi adverse. Le but est bien entendu d'amener le jeu dans une finale gagnante.

En finale, tout dépend de l'avantage ou le désavantage que le joueur possède. Si le joueur possède un avantage décisif, ça lui sera facile de forcer la victoire. La plupart des joueurs d'expériences abandonne avant même d'entrer en finale lorsqu'ils ont un trop grand désavantage surtout contre un moteur ou contre un grand maître.

Par contre, si l'avantage n'est que théorique, il faut une connaissance approfondie des finales pour forcer la victoire. Les erreurs sont souvent fatales dans cette phase. Selon moi, pour un moteur, cette phase est une des plus importantes. J'ai vu mon moteur Monik gagner des parties qui étaient théoriquement perdues tout ça parce que le moteur adverse ne possédait pas de connaissance des finales ou très peu. Tant que l'adversaire possède des pions, il lui est toujours possible de promouvoir l'un d'eux en une dame.

Valeur positionnelles des pièces

Pour donner une valeur à la position des pièces, le plus simple est d'utiliser un tableau de valeur pour chaque case de l'échiquier. Vous pouvez utiliser un tableau pour chacune des phases.

Par exemple, pour le roi, nous voulons qu'en début et milieu de partie qu'il reste dans son coin cacher derrière ses pions. Il suffit alors de donner une valeur supérieur aux cases B1 et B7 pour le roi blanc et des valeurs très négative pour le reste et surtout au centre. Voici le tableau pour l'évaluation du roi de mon moteur comme exemple.

// Ouverture et milieu de partie.
const SCORE PosRoi[] =
{
-40, -40, -40, -40, -40, -40, -40, -40,
-40, -40, -40, -40, -40, -40, -40, -40,
-40, -40, -40, -40, -40, -40, -40, -40,
-40, -40, -40, -40, -40, -40, -40, -40,
-40, -40, -40, -40, -40, -40, -40, -40,
-40, -40, -40, -40, -40, -40, -40, -40,
-20, -20, -20, -20, -20, -20, -20, -20,
0,  30,  20, -20,   0, -20,  30,  30
};

Pour les pions, c'est un peu plus complexe. La structure des pions est souvent beaucoup plus importante que la position d'un seul pion,

à suivre

L'Alpha-béta

Introduction

Nous allons commencer par un peu de théorie. La recherche alpha-bêta est une variante de la recherche en profondeur d'abord. La recherche en profondeur d'abord est un algorithme pour parcourir un graphe ou un arbre de nœuds. En théorie, l'arbre des coups possibles à une profondeur données est un graphe et non un arbre car les positions peuvent revenir par différents ordres des coups. Et puisqu'un arbre ne doit pas posséder deux chemins différents pour rejoindre un même nœud, c'est donc un graphe. Par contre, dans le domaine, nous l'appelons toujours un arbre tout de même.

---

Recherche en profondeur

La recherche en profondeur d'abord est le cousin de la recherche en largeur d'abord. La différence vient de l'ordre dans lequel les noeuds sont visités. Dans la recherche en profondeur d'abord, nous générons les noeuds possibles d'un niveau et visitons le premier noeud pour passer au prochain niveau. Nous répétons ce processus jusqu'à la profondeur voulue.

Voici l'algorithme en langage pseudo:

fonction rechercher-profondeur(profondeur, échiquier)
début
 génère coups
 pour chaque coups de la liste
 jouer coup
 si on est rendu à la profondeur 0
 alors
 retourner la valeur de la position
 sinon
 valeur = rechercher(profondeur-1, echiquier)
 déjouer coup
 retourn la meilleur valeur
fin

Pour faciliter la compréhension, voici un graphique indiquant l'ordre dans lequel les noeuds sont visités pour une recherche en profondeur:

Recherche minimax

L'algorithme au dessus est un algorithme utilisé pour trouver la meilleure valeur à une profondeur quelconque. Il est souvent utilisé pour essayer de trouver la meilleur solution à un problème. Par contre, dans le cas du jeu d'échecs, il y a deux adversaires ayant des buts opposés. Chacun essaie de faire augmenter son score personnel. Chacun regarde la position avec un but inverse. On doit donc modifier l'algorithme pour prendre en compte cette nouvelle réalité. L'algorithme minimax répond à notre problème.

Voici la nouvelle version légèrement modifiée, l'algorithme minimax de Von Neumann.

fonction minimax(profondeur, échiquier)
début
	génère coups
 	pour chaque coups de la liste
 	    jouer coup
 	    si on est rendu à la profondeur 0
 	    alors
 		retourner la valeur de la position
 	    sinon
 		valeur = rechercher(profondeur-1, echiquier)
 	    déjouer coup
 	si c'est le tour du moteur
 		retourner la meilleur valeur
 	sinon
 		retourner la pire valeur
fin

---

Négamax

L'algorithme connu sous le nom de Négamax est une légère variante de l'algorithme Minimax. La modification consiste simplement à inverser le résultat retourné de la recherche à la profondeur suivante. Il réduit beaucoup la quantité de code nécessaire pour l'écriture d'un moteur d'échecs.

L'algorithme en pseudo langage est le suivant:

function negamax(profondeur, échiquier, couleur)
début
génère coups pour couleur
pour chaque coups de la liste
jouer coup
si on est rendu à la profondeur 0 // Si c'est un feuille
alors
retourner la valeur de la position
sinon
valeur = -negamax(profondeur-1, échiquier, inverse(couleur))
déjouer coup
retourner la meilleur valeur
fin

Le principe est simple, puisque les joueurs à tour de rôle essaient d'améliorer leur propre score, nous utilisons une échelle permettant les valeurs négatives et nous gardons un seul score pour les deux joueurs. Par exemple, une valeur positive signifie que les blancs ont l'avantage et une valeur négative signifie que les noirs ont l'avantage.

Voici un exemple d'exécution à une profondeur de 2 et pour évaluer le meilleur coup des blancs.

Nous appelons la fonction négamax comme suit:

meilleur = negamax(2, position, blanc)

1. L'algorithme génère les coups possibles des blancs.

2. L'algorithme prend le premier coup de la liste et le joue sur l'échiquier.

3. Puisque que nous ne sommes pas encore à la profondeur 0, nous appelons à nouveau la fonction negamax avec une profondeur de moins et en inversant la couleur.

4. Negamax génère les coups possibles pour les noirs.

5. Pour chacun des coups, il va appeler encore une fois négamax, mais cette fois-ci avec comme valeur de profondeur à 0 ce qui aura pour effet de retourner tout simplement la valeur de la position.

6. Ensuite, negamax va retourner le meilleur score trouvé. J'espère que vous me suivez bien ici. Rendu ici, négamax va garder le score de la meilleur réplique contre le premier coup des blancs. Supposons que c'est 10.

7. La valeur retourné de negamax est 10 et nous l'inversons ce qui nous donne une valeur de -10. Donc pour le premier coup des blancs, la meilleur réplique des noirs donne un score de 10.

8. Negamax passe au deuxième coup et rappelle negamax à nouveau.

9. Si le score retourné est meilleur que le score trouvé jusqu'à présent, nous le gardons et nous recommençons pour chacun des coups possibles des blancs. Supposons qu'un des coups des blancs, la meilleur réplique des noirs ne donne qu'un score de 5, alors nous allons avoir un meilleur score de 5. En faisant cela pour chaque coup possible des blancs, nous sommes assuré de trouvé le coup ayant le meilleur score à une profondeur de 2.

Voici un graphique pour visualiser l'exemple ci-haut:

---

Alpha-bêta

L'algorithme de recherche alpha-bêta est en réalité l'algorithme minimax ou negamax avec des coupes. Les coupes sont des branches de l'arbre qu'il serait inutile d'explorer. L'algorithme retourne le même résultat que Negamax mais plus rapidement car le nombre de nœud exploré est réduit.

Pour comprendre comment il fonctionne prenons un exemple simple. Supposons que c'est aux blancs à jouer et que nous effectuons une recherche à une profondeur 2. L'algorithme simule le premier coup et c'est une capture de pion.

L'algorithme poursuit et simule le premier coup des noirs. Le pion n'est pas regagné. L'algorithme poursuit et c'est le temps de l'évaluation. Le score est de 100 pour les blancs. L'algorithme revient et simule le deuxième coups des noirs et le pion n'est toujours pas regagné et c'est la même chose pour toutes les répliques des noirs.

L'algorithme passe donc au deuxième coups des blancs mais maintenant, l'algorithme passe en paramètre le score d'un pion pour les blancs comme borne supérieure pour les noirs qui un coup inversé devient la perte d'un pion, donc -100. Si un coup des noirs dépasse cette borne, ils améliorent leur sort et c'est donc que le coup des blancs est moins bon.

Poursuivons pour voir.

Nous évaluons le deuxième coups des blancs. L'algorithme simule le coup et c'est un simple mouvement de pièce, aucun gain de pion. Il simule le premier coup des noirs et ensuite l'évaluation de la position. Le score est de 0. L'évaluateur donne nulle pour ce coup. L'algorithme revient et reçoit la valeur de 0. Le score des noirs est supérieur à la borne de -100 qui est la perte d'un pion. Ce qui rend inutile l'exploration du reste des coups des noirs car nous savons que le coup des blancs est moins bon que le coup précédent. La seule chose qui peut arriver, c'est que nous trouvions un coup encore pire pour les blancs.

Voici l'algorithme.

function alpha-beta(profondeur, échiquier, couleur, alpha, beta)
début
génère coups pour couleur
pour chaque coups de la liste
jouer coup
si on est rendu à la profondeur 0 // Si c'est un feuille
alors
retourner la valeur de la position
sinon
		valeur = -alpha-beta(profondeur-1, échiquier, inverse(couleur), -beta, -alpha)
déjouer coup
	si la valeur est supérieur à alpha
	alors
		alpha = valeur // Le meilleur coup jusqu'à maintenant
		si alpha est supérieur à bêta alors on retourne alpha // Inutile de poursuivre
	retourner alpha
fin

Remarquez qu'à chaque appelle d'alpha-bêta, les bornes sont inversés. Bêta devient toujours le meilleur score de l'opposant à ne pas dépasser, sinon c'est qu'il est inutile de poursuivre parce que le joueur à ce niveau a un meilleur coup.

Étudiez bien l'algorithme et faites même un trace pour bien comprendre ce qui se passe. C'est ce qui vous permettra d'améliorer votre moteur au moment venu.

---

Ordonnancement des coups

Si vous avez bien étudiez l'algorithme de recherche alpha-bêta, vous aurez sûrement compris qu'il est avantageux d'avoir les meilleurs coups au début de la recherche car ils vont générer plus de coupes plus rapidement. Si vous naviguez un peu dans le monde des programmeurs de moteur d'échecs vous entendrez souvent parler d'ordonnancement des coups.

Avec un bon ordonnancement des coups, les coupes peuvent augmenter exponentiellement. C'est une des raisons pourquoi nous avons parlé de deux fonctions séparés pour générer les coups. En jouant les coups de capture avant les coups normaux, vous augmentez les chances d'avoir un coup qui a un meilleur score au début de la recherche générant plus de coupes et réduisant le nombre de noeud à explorer.

Alpha-bêta par itération

La technique de recherche alpha-bêta par itération permet deux choses.

1. Un meilleur ordonnancement des coups;
2. Mieux contrôler la durée de recherche du moteur.

Nous savons qu'il faut un bon ordonnancement des coups pour que l'alpha-bêta soit efficace. De faire des recherches de plus en plus profonde est ce qui permet de bien ordonnancer les coups. Chaque itération utilise l'évaluation de la précédente pour réordonner ces coups ce qui permet à la recherche de toujours être optimal à chaque itération.

Si vous commencez la recherche du moteur avec un profondeur de 8 par exemple, vous n'avez aucun contrôle sur la durée de recherche. Et si vous interrompez la recherche à n'importe quel moment, le résultat sera hasardeux car vous ne saurez pas s'il y avait un coup meilleur plus loin dans la liste.

En y allant par itération, vous pouvez toujours utilisez le résultat de l'itération précédente qui est complète.

Au départ, pour tester votre algorithme vous allez probablement y avec une profondeur fixe et vous aurez déjà un moteur capable de bien évaluer le jeu, mais ça vous semblera long même pour une profondeur très courte.

---

Quiescence

Le générateur de coup

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.

L'échiquier

Puisqu'un échiquier possède 64 cases, 8 colonnes et 8 rangées, on pourrait penser que d'utiliser un tableau à deux dimensions de 8 x 8 serait l'idéal. Le problème est, lorsque nous voulons stocker les coups possibles d'une pièce, nous devons stocker deux valeurs pour chaque direction possible. C'est faisable mais légèrement moins rapide. Et, croyez-moi, le "légèrement moins rapide" devient beaucoup moins rapide lorsque le moteur évalue des milliers, et même, des millions de coups. La raison est que vous devez traiter deux valeurs à chaque fois. De plus, ça se gère un peu moins facilement.

---

Il est préférable d'utiliser un tableau d'une seule dimension. Essayons par exemple un tableau de 64 cases à une seule dimension. Si nous voulons stocker les coups possibles d'une tour, il suffit alors d'une seule valeur.

int dirTour[] = {-1, 1, -8, 8, 0};

Pour un fou, ça serait simplement:

int dirFou[] = {-7, 7, -9, 9, 0};

Bien sûr, ces coups sont en réalité des directions que nous allons répéter pour générer chaque coup valide pour chaque direction. Nous verrons cela dans le générateur de coups.

Bon, nous avons un échiquier.

Les pièces

#define    pion         1
#define    cavalier     2
#define    fou          3
#define    tour         4
#define    dame         5
#define    roi          6

Nous n'avons pas besoin de définir des constantes pour les pièces noires car nous n'avons qu'à faire -pion par exemple pour représenter un pion noir.
Une chose que j'aime bien faire aussi, c'est de définir une constante pour chaque position de l'échiquier. Cela permet de bien documenter le code lorsque nous référons une case de l'échiquier.

enum {
A8, B8, C8, D8, E8, F8, G8, H8,
A7, B7, C7, D7, E7, F7, G7, H7,
A6, B6, C6, D6, E6, F6, G6, H6,
A5, B5, C5, D5, E5, F5, G5, H5,
A4, B4, C4, D4, E4, F4, G4, H4,
A3, B3, C3, D3, E3, F3, G3, H3,
A2, B2, C2, D2, E2, F2, G2, H2,
A1, B1, C1, D1, E1, F1, G1, H1 };

Plaçons maintenant les pièces dessus. Voici le code étant explicatif en lui même grâce à nos constantes.

/* Initialisation de l'échiquier. */
memset(echiquier, 0, sizeof(echiquier)); // met toutes les cases à 0.

/* Les pions. */
for(i=A7; i<=H7; i++)
echiquier[i] = -pion; // pions noirs
for(i=A2; i<=H2; i++)
echiquier[i] = pion;  // pions blancs;

/* Les cavaliers */
echiquier[B8] = echiquier[G8] = -cavalier; // cavaliers noirs
echiquier[B1] = echiquier[G1] = cavalier;  // cavaliers blancs

/* Les fous */
echiquier[C8] = echiquier[F8] = -fou; // fous noirs
echiquier[C1] = echiquier[F1] = fou;  // fous blancs

/* Les tours */
echiquier[A8] = echiquier[H8] = -tour; // tours noires
echiquier[A1] = echiquier[H1] = tour;  // tours blanches

/* Les dames */
echiquier[D8] = -dame; // dame noire
echiquier[D1] = dame;  // dame blanche

/* Les rois */
echiquier[E8] = -roi;  // roi noir
echiquier[E1] = roi;   // roi blanc

Voici ce que ça donne lorsqu'on l'imprime:

-4 -2 -3 -5 -6 -3 -2 -4 
-1 -1 -1 -1 -1 -1 -1 -1 
0  0  0  0  0  0  0  0 
0  0  0  0  0  0  0  0 
0  0  0  0  0  0  0  0 
0  0  0  0  0  0  0  0 
1  1  1  1  1  1  1  1 
4  2  3  5  6  3  2  4

Autres informations

Il faut garder aussi quelques autres informations de plus.

Par exemple, il faut connaitre la possibilité des roques, la possibilité d'un coup en passant, le joueur à jouer et le numéro du coup.

Pour le joueur à jouer, nous utilisons seulement un entier. En C, un entier représente vrai pour toutes valeurs différentes de zéro.

unsigned int baj ;

C'est une abbréviation de Blanc à jouer. La variable est à 1 si c'est au blanc à jouer, sinon elle est à zéro.

Pour le numéro du coup, un entier aussi.

unsigned int noCoup;

Pour le coup en passant, il faut garder la case où le pion aurait dû se faire capturer en passant. Cette case sera initialisée si le joueur adverse avance son pion de 2 cases sur le départ.

int enPassant; // Valeur possible de 0 à 63.

Pour terminer, les roques.

Nous avons besoin de garder la possibilité du roque blanc côté dame, roque blanc côté roi, roque noir côté dame et roque noir côté roi.

Nous n'avons besoin que d'un bit pour chacun. Prenons donc les quatres premiers bits d'un mot.

#define    ROQUEBLANCDAME 0x01
#define    ROQUEBLANCROI  0x02
#define    ROQUENOIRDAME  0x04
#define    ROQUENOIRROI   0x08

int roque;

Pour l'initialisation, voici le code:

baj = 1; /* blanc à jouer. */
enPassant = -1; /* Pas de case en passant. */
noCoup = 0; /* Aucun coup de joué. */
/* Tous les roques sont possibles. */
roque = ROQUEBLANCDAME | ROQUEBLANCROI | ROQUENOIRDAME | ROQUENOIRROI;

Je crois que c'est tout pour l'échiquier. Nous allons maintenant passer au générateur de coups.

/* Initialisation de l'échiquier. */
memset(echiquier, 0, sizeof(echiquier)); // met toutes les cases à 0.

/* Les pions. */
for(i=A7; i<=H7; i++)
echiquier[i] = -pion; // pions noirs
for(i=A2; i<=H2; i++)
echiquier[i] = pion; // pions blancs;

/* Les cavaliers */
echiquier[B8] = echiquier[G8] = -cavalier; // cavaliers noirs
echiquier[B1] = echiquier[G1] = cavalier; // cavaliers blancs

/* Les fous */
echiquier[C8] = echiquier[F8] = -fou; // fous noirs
echiquier[C1] = echiquier[F1] = fou; // fous blancs

/* Les tours */
echiquier[A8] = echiquier[H8] = -tour; // tours noires
echiquier[A1] = echiquier[H1] = tour; // tours blanches

/* Les dames */
echiquier[D8] = -dame; // dame noire
echiquier[D1] = dame; // dame blanche

/* Les rois */
echiquier[E8] = -roi; // roi noir
echiquier[E1] = roi; // roi blanc

Comment programmer un moteur d'échecs

Les parties dont vous avez besoin au minimum pour faire un moteur d'échec sont les suivantes:

• Un échiquier;
• Un générateur de coups valides;
• Un algorithme de recherche alpha-bêta;
• Un évaluateur.