Analyse & Programmation

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.