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;