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.