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.

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