Analyse & Programmation

Négamax

L'algorithme connu sous le nom de Négamax est une légère variante de l'algorithme Minimax. La modification consiste simplement à inverser le résultat retourné de la recherche à la profondeur suivante. Il réduit beaucoup la quantité de code nécessaire pour l'écriture d'un moteur d'échecs.

L'algorithme en pseudo langage est le suivant:

function negamax(profondeur, échiquier, couleur)
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 = -negamax(profondeur-1, échiquier, inverse(couleur))
            déjouer coup
       retourner la meilleur valeur
fin

Le principe est simple, puisque les joueurs à tour de rôle essaient d'améliorer leur propre score, nous utilisons une échelle permettant les valeurs négatives et nous gardons un seul score pour les deux joueurs. Par exemple, une valeur positive signifie que les blancs ont l'avantage et une valeur négative signifie que les noirs ont l'avantage.

Voici un exemple d'exécution à une profondeur de 2 et pour évaluer le meilleur coup des blancs.

Nous appelons la fonction négamax comme suit:

meilleur = negamax(2, position, blanc)

1. L'algorithme génère les coups possibles des blancs.

2. L'algorithme prend le premier coup de la liste et le joue sur l'échiquier.

3. Puisque que nous ne sommes pas encore à la profondeur 0, nous appelons à nouveau la fonction negamax avec une profondeur de moins et en inversant la couleur.

4. Negamax génère les coups possibles pour les noirs.

5. Pour chacun des coups, il va appeler encore une fois négamax, mais cette fois-ci avec comme valeur de profondeur à 0 ce qui aura pour effet de retourner tout simplement la valeur de la position.

6. Ensuite, negamax va retourner le meilleur score trouvé. J'espère que vous me suivez bien ici. Rendu ici, négamax va garder le score de la meilleur réplique contre le premier coup des blancs. Supposons que c'est 10.

7. La valeur retourné de negamax est 10 et nous l'inversons ce qui nous donne une valeur de -10. Donc pour le premier coup des blancs, la meilleur réplique des noirs donne un score de 10.

8. Negamax passe au deuxième coup et rappelle negamax à nouveau.

9. Si le score retourné est meilleur que le score trouvé jusqu'à présent, nous le gardons et nous recommençons pour chacun des coups possibles des blancs. Supposons qu'un des coups des blancs, la meilleur réplique des noirs ne donne qu'un score de 5, alors nous allons avoir un meilleur score de 5. En faisant cela pour chaque coup possible des blancs, nous sommes assuré de trouvé le coup ayant le meilleur score à une profondeur de 2.

Voici un graphique pour visualiser l'exemple ci-haut:

<< Préc - Suivant >>