Negamax en Python : comprendre l’algorithme avec un exemple de jeu

Negamax est une écriture compacte de minimax pour les jeux à deux joueurs, à somme nulle et à information parfaite. On évalue toujours la position du point de vue du joueur qui doit jouer. Après avoir simulé un coup, on change de point de vue : le score de l’adversaire est inversé.

Ce guide utilise un jeu d’allumettes complet, avec une version simple, une version mémorisée et une recherche alpha-beta. Le script est exécutable tel quel avec Python 3.12, sans bibliothèque externe. Les tests comparent les résultats à minimax et à une solution mathématique indépendante.

Pourquoi un seul maximum suffit

Si un état vaut +1 pour le joueur A, il vaut −1 pour B. Choisir le meilleur coup revient donc à maximiser l’opposé de la valeur obtenue par l’adversaire : valeur(position) = max(−valeur(position suivante)). Cette égalité remplace l’alternance explicite des branches de maximisation et minimisation.

Le cours de Berkeley sur minimax présente la recherche contre un adversaire optimal et l’élagage alpha-beta. Negamax reprend ce raisonnement avec une convention de signe unique. Pour une première introduction, consultez aussi minimax avec un exemple de jeu.

Le jeu : retirer 1, 2 ou 3 allumettes

À chaque tour, on retire entre une et trois allumettes, sans dépasser ce qui reste. Celui qui prend la dernière gagne. Les tours alternent et il n’y a ni hasard ni information cachée. Le nombre restant suffit donc à représenter l’état du jeu.

Quand il reste zéro allumette, le joueur qui devrait jouer a perdu : son adversaire vient de prendre la dernière. La valeur terminale est −1. Ce choix est spécifique à cette règle ; si prendre la dernière faisait perdre, il faudrait changer le modèle du jeu.

Un script complet, sans fonctions à assembler

Enregistrez ce bloc dans negamax_allumettes.py, puis exécutez python negamax_allumettes.py. Les entrées négatives, booléennes ou non entières sont refusées. Sur une position terminale, meilleur_coup(0) renvoie explicitement (None, -1).

"""Jeu exact : retirer 1, 2 ou 3 allumettes ; la dernière fait gagner."""
from functools import lru_cache

def verifier(n):
    if type(n) is not int or n < 0:
        raise ValueError("Le nombre d'allumettes doit être un entier positif ou nul")

def negamax(n):
    verifier(n)
    def chercher(restantes):
        if restantes == 0:
            return -1
        return max(-chercher(restantes-c) for c in range(1, min(3, restantes)+1))
    return chercher(n)

@lru_cache(maxsize=None)
def _memo(n):
    if n == 0:
        return -1
    return max(-_memo(n-c) for c in range(1, min(3, n)+1))

def negamax_memo(n):
    verifier(n)
    return _memo(n)

def meilleur_coup(n):
    verifier(n)
    if n == 0:
        return None, -1
    # En cas d'égalité, conserver le premier coup, donc le plus petit.
    coups = range(1, min(3, n)+1)
    coup = max(coups, key=lambda c: -_memo(n-c))
    return coup, -_memo(n-coup)

def negamax_alpha_beta(n, profondeur=None):
    verifier(n)
    if profondeur is None:
        profondeur = n
    if type(profondeur) is not int or profondeur < 0:
        raise ValueError("La profondeur doit être un entier positif ou nul")
    def chercher(restantes, d, alpha, beta):
        if restantes == 0:
            return -1
        if d == 0:
            return 0  # Évaluation neutre, pas une preuve de partie nulle.
        meilleur = float('-inf')
        for c in range(1, min(3, restantes)+1):
            score = -chercher(restantes-c, d-1, -beta, -alpha)
            meilleur = max(meilleur, score)
            alpha = max(alpha, score)
            if alpha >= beta:
                break
        return meilleur
    return chercher(n, profondeur, float('-inf'), float('inf'))

if __name__ == '__main__':
    for n in range(11):
        coup, score = meilleur_coup(n)
        print(f"n={n:2d} score={score:+d} coup={coup}")
    print("Recherche limitée à zéro pli :", negamax_alpha_beta(10, 0))

Lire les résultats et vérifier le meilleur coup

n= 0 score=-1 coup=None
n= 1 score=+1 coup=1
n= 2 score=+1 coup=2
n= 3 score=+1 coup=3
n= 4 score=-1 coup=1
n= 5 score=+1 coup=1
n= 6 score=+1 coup=2
n= 7 score=+1 coup=3
n= 8 score=-1 coup=1
n= 9 score=+1 coup=1
n=10 score=+1 coup=2
Recherche limitée à zéro pli : 0

Avec dix allumettes, le meilleur coup retire deux allumettes et laisse huit à l’adversaire. Les multiples de quatre sont perdants contre un adversaire optimal. Depuis un autre nombre, on peut laisser un multiple de quatre ; après chaque retrait adverse de c, on peut retirer 4 − c.

Cette propriété se démontre par récurrence et sert d’oracle indépendant pour nos tests. Depuis une position perdante comme huit, tous les coups perdent contre un adversaire parfait ; le script choisit alors le plus petit coup parmi les ex æquo. Il ne prédit pas les erreurs d’un joueur humain.

Trois versions et leurs limites

negamax explore récursivement tous les coups. Son coût croît très vite avec la profondeur : pour un facteur de branchement borné par b et une profondeur d, la borne usuelle est O(b^d). Un arbre complet contient plusieurs niveaux ; b^d ne doit pas être pris pour le nombre exact total de positions visitées.

negamax_memo mémorise les valeurs exactes. Pour ce jeu, il n’existe que n + 1 états et au plus trois coups par état : le calcul et le cache sont en O(n). La pile récursive reste limitée par Python ; pour de très grands tas, une programmation dynamique itérative convient mieux. Dans un autre jeu, la clé du cache doit décrire tout l’état pertinent, y compris le joueur lorsque nécessaire.

negamax_alpha_beta interrompt une branche lorsqu’elle ne peut plus améliorer le résultat recherché. Les bornes deviennent −beta, −alpha dans l’appel adverse. L’ordre des coups influence le travail évité. Avec la profondeur par défaut égale à n, toutes les parties possibles de ce petit jeu peuvent atteindre leur fin.

Avec une profondeur limitée, une position non terminale reçoit ici une évaluation neutre de zéro. Ce zéro signifie « estimation neutre à cette profondeur », pas « partie nulle démontrée ». Le cas terminal est vérifié avant la coupure de profondeur. Une heuristique plus élaborée améliorerait l’estimation, sans garantir le résultat d’une recherche complète.

Ne combinez pas naïvement le cache exact et alpha-beta : après une coupure, une valeur retournée peut être une borne. Une table de transposition correcte doit distinguer valeurs exactes, bornes inférieures et bornes supérieures, ainsi que la profondeur de recherche.

Sept tests à exécuter

Enregistrez ce second bloc dans test_negamax.py, à côté du script, et lancez python test_negamax.py. Il compare les trois recherches sur les petites positions, vérifie les positions jusqu’à 60 contre la règle des multiples de quatre, contrôle les coups gagnants et compare à un minimax écrit depuis le point de vue fixe de A.

import unittest
from negamax_allumettes import negamax,negamax_memo,meilleur_coup,negamax_alpha_beta

class NegamaxTests(unittest.TestCase):
    def test_terminal(self):
        self.assertEqual(meilleur_coup(0),(None,-1))
        self.assertEqual(negamax_alpha_beta(0,0),-1)
    def test_entrees(self):
        for n in [-1,2.5,True,'3']:
            for f in [negamax,negamax_memo,meilleur_coup,negamax_alpha_beta]:
                with self.assertRaises(ValueError):f(n)
        for d in [-1,True,1.5]:
            with self.assertRaises(ValueError):negamax_alpha_beta(2,d)
    def test_solution_mathematique(self):
        for n in range(61):self.assertEqual(negamax_memo(n),-1 if n%4==0 else 1)
    def test_coup_gagnant(self):
        for n in range(1,61):
            c,score=meilleur_coup(n);self.assertIn(c,range(1,min(3,n)+1))
            if n%4:self.assertEqual(n-c,(n//4)*4)
    def test_trois_recherches(self):
        for n in range(15):
            self.assertEqual(negamax(n),negamax_memo(n))
            self.assertEqual(negamax_alpha_beta(n),negamax_memo(n))
    def test_minimax_point_de_vue_fixe(self):
        def minimax(n,tour_a):
            if n==0:return -1 if tour_a else 1
            scores=[minimax(n-c,not tour_a) for c in range(1,min(3,n)+1)]
            return max(scores) if tour_a else min(scores)
        for n in range(13):self.assertEqual(negamax(n),minimax(n,True))
    def test_profondeur_limitee(self):
        self.assertEqual(negamax_alpha_beta(10,0),0)
        self.assertEqual(negamax_alpha_beta(1,1),1)

if __name__=='__main__':unittest.main(verbosity=2)

Les sept tests passent dans l’environnement indiqué. Ils vérifient ce jeu précis ; ils ne valident pas automatiquement une adaptation aux échecs ou au morpion.

Adapter Negamax à un plateau

Remplacez le nombre d’allumettes par un état contenant le plateau et le joueur courant. Il faut ensuite énumérer les coups légaux, produire l’état suivant et reconnaître les résultats terminaux. Conservez une convention d’évaluation : soit le joueur courant, soit un joueur fixe avec un facteur de couleur. Mélanger ces conventions produit des inversions de score incorrectes.

Le changement de signe à chaque coup suppose ici une alternance des joueurs. Si une règle permet de rejouer immédiatement, l’inversion doit suivre le changement effectif de joueur. Pour les jeux cycliques, il faut aussi représenter les règles de répétition ou limiter explicitement la recherche.

Exercices pour prolonger

1. Remplacez les retraits autorisés par 1 ou 3. Recalculez les positions perdantes : la règle des multiples de quatre ne s’applique plus automatiquement.
2. Comptez les appels des versions simple et alpha-beta pour une même position et une même profondeur. Comparez aussi deux ordres de coups ; ne mesurez pas seulement le temps d’une exécution.
3. Ajoutez un affichage des coups d’une partie jouée par deux recherches exactes, en vérifiant chaque retrait.

Pour continuer, reliez cet exemple à la complexité algorithmique. Si le jeu exige une recherche par simulation, le guide Monte Carlo introduit une autre famille de méthodes.