Analyse & Programmation

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.

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.

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.

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.