Negamax est une version compacte de minimax. On l’utilise dans les jeux à deux joueurs, à information parfaite et à somme nulle : ce qu’un joueur gagne, l’autre le perd. Échecs, dames, puissance 4 ou tic-tac-toe entrent dans cette famille, au moins dans leur forme classique.
L’idée clé est simple : au lieu d’écrire séparément un joueur qui maximise et un joueur qui minimise, on considère toujours le point de vue du joueur courant. Quand on passe au joueur adverse, le score change de signe.
score_position = -negamax(position_suivante, profondeur - 1)
Cette petite inversion résume l’algorithme. Elle rend le code plus court que minimax, sans changer le principe de recherche.
La réponse courte
Negamax repose sur cette équivalence :
score(position, joueur) = -score(position, adversaire)
Pseudo-code :
negamax(position, profondeur):
si position terminale ou profondeur == 0:
retourner evaluation(position)
meilleur = -infini
pour chaque coup possible:
jouer le coup
score = -negamax(position suivante, profondeur - 1)
meilleur = max(meilleur, score)
retourner meilleur
La différence avec minimax est surtout dans l’écriture. Minimax alterne deux fonctions ou deux branches : maximiser puis minimiser. Negamax utilise une seule fonction récursive et inverse le score à chaque changement de joueur.
Pourquoi Negamax fonctionne
Dans un jeu à somme nulle, les intérêts des deux joueurs sont opposés. Si une position vaut +10 pour moi, elle vaut -10 pour l’adversaire.
Cette symétrie permet de remplacer :
max(mon score)
min(score adverse)
par :
max(-score adverse)
Autrement dit, je cherche toujours le meilleur score pour le joueur qui doit jouer. Quand je simule le tour adverse, je récupère son score et je change le signe pour revenir à mon point de vue.
Minimax, minmax et Negamax
Les trois termes sont souvent mélangés.
| Terme | Idée |
|---|---|
minimax |
Algorithme général : un joueur maximise, l’autre minimise |
minmax |
Variante de nom souvent utilisée pour parler de minimax |
negamax |
Réécriture compacte de minimax pour les jeux à somme nulle |
Si vous débutez, commencez par comprendre minimax en Python. Negamax devient ensuite naturel : c’est le même raisonnement, mais avec une convention de score plus élégante.
Un petit jeu pour tester Negamax
Pour éviter un code trop long, utilisons un jeu simple : il y a un tas d’allumettes. À chaque tour, un joueur peut retirer 1, 2 ou 3 allumettes. Le joueur qui prend la dernière gagne.
Une position se résume au nombre d’allumettes restantes.
def coups_possibles(allumettes):
return [coup for coup in (1, 2, 3) if coup <= allumettes]
def position_terminale(allumettes):
return allumettes == 0
Si allumettes == 0, le joueur qui doit jouer a perdu, car l’adversaire vient de prendre la dernière allumette. Du point de vue du joueur courant, le score est donc négatif.
def evaluer(allumettes):
if allumettes == 0:
return -1
return 0
Implémentation simple de Negamax
Voici une première version, volontairement directe.
def negamax(allumettes):
if position_terminale(allumettes):
return -1
meilleur_score = float("-inf")
for coup in coups_possibles(allumettes):
score = -negamax(allumettes - coup)
meilleur_score = max(meilleur_score, score)
return meilleur_score
Test :
for n in range(1, 11):
print(n, negamax(n))
Résultat :
1 1
2 1
3 1
4 -1
5 1
6 1
7 1
8 -1
9 1
10 1
Les positions 4 et 8 sont perdantes si l’adversaire joue parfaitement. À chaque fois, tous les coups disponibles laissent une position gagnante à l’autre joueur.
Trouver le meilleur coup
Un score ne suffit pas toujours. On veut aussi connaître le coup à jouer.
def meilleur_coup(allumettes):
meilleur_score = float("-inf")
meilleur = None
for coup in coups_possibles(allumettes):
score = -negamax(allumettes - coup)
if score > meilleur_score:
meilleur_score = score
meilleur = coup
return meilleur, meilleur_score
Exemple :
print(meilleur_coup(10)) # (2, 1)
Avec 10 allumettes, retirer 2 force l’adversaire à recevoir une position perdante avec 8 allumettes.
Ajouter une profondeur de recherche
Sur un vrai jeu, on ne peut pas toujours explorer jusqu’à la fin. On limite donc la profondeur.
def negamax(position, profondeur):
if position_terminale(position) or profondeur == 0:
return evaluer(position)
meilleur_score = float("-inf")
for coup in coups_possibles(position):
position_suivante = position - coup
score = -negamax(position_suivante, profondeur - 1)
meilleur_score = max(meilleur_score, score)
return meilleur_score
Dans notre jeu d’allumettes, l’évaluation est très simple. Dans un jeu comme les échecs, l’évaluation estime la qualité d’une position non terminale : matériel, sécurité du roi, mobilité, structure, menaces, etc.
Le point important : plus la profondeur augmente, plus l’arbre de recherche grossit vite.
Complexité de Negamax
Si chaque position propose en moyenne b coups possibles et que l’on cherche à profondeur d, la complexité brute est :
O(b^d)
C’est la même explosion combinatoire que minimax.
Exemple :
b = 3,d = 10donne environ3^10 = 59 049positions ;b = 30,d = 6donne déjà729 000 000branches théoriques.
Dans les vrais jeux, on ajoute donc des optimisations : élagage alpha-beta, ordre des coups, tables de transposition, mémorisation, profondeur itérative, heuristiques d’évaluation.
Pour relier ce comportement à la notation Big O, voir la complexité algorithmique en Python.
Negamax avec élagage alpha-beta
L’élagage alpha-beta évite d’explorer certaines branches qui ne peuvent plus améliorer le résultat final.
Version Negamax :
def negamax_alpha_beta(position, profondeur, alpha, beta):
if position_terminale(position) or profondeur == 0:
return evaluer(position)
meilleur_score = float("-inf")
for coup in coups_possibles(position):
position_suivante = position - coup
score = -negamax_alpha_beta(
position_suivante,
profondeur - 1,
-beta,
-alpha,
)
meilleur_score = max(meilleur_score, score)
alpha = max(alpha, score)
if alpha >= beta:
break
return meilleur_score
L’inversion -beta, -alpha est le détail à ne pas manquer. Comme on change de point de vue à chaque appel récursif, les bornes changent aussi de signe et d’ordre.
Appel :
score = negamax_alpha_beta(
position=10,
profondeur=10,
alpha=float("-inf"),
beta=float("inf"),
)
print(score)
Sur de grands arbres, alpha-beta peut réduire fortement le nombre de positions explorées, surtout si les bons coups sont testés tôt.
Mémoriser les positions déjà vues
Dans certains jeux, la même position peut être atteinte par plusieurs chemins. On peut alors mémoriser les scores calculés.
Avec notre jeu d’allumettes, c’est très simple :
from functools import lru_cache
@lru_cache(maxsize=None)
def negamax_memo(allumettes):
if position_terminale(allumettes):
return -1
return max(
-negamax_memo(allumettes - coup)
for coup in coups_possibles(allumettes)
)
La mémorisation transforme souvent un exercice récursif coûteux en calcul beaucoup plus rapide. Dans les jeux complexes, on parle plutôt de tables de transposition.
Adapter Negamax au tic-tac-toe
Sur un jeu de plateau, la position doit contenir :
- l’état du plateau ;
- le joueur courant ;
- la liste des coups possibles ;
- une fonction d’évaluation.
L’idée reste la même.
def negamax(position, profondeur, couleur):
if terminal(position) or profondeur == 0:
return couleur * evaluer(position)
meilleur = float("-inf")
for coup in coups_possibles(position):
suivant = jouer(position, coup)
score = -negamax(suivant, profondeur - 1, -couleur)
meilleur = max(meilleur, score)
return meilleur
Ici, couleur vaut souvent 1 pour le joueur maximisant et -1 pour l’autre. L’évaluation peut être écrite du point de vue d’un joueur de référence, puis corrigée par couleur.
Erreurs fréquentes
Oublier le signe moins
L’erreur la plus courante est d’écrire :
score = negamax(position_suivante, profondeur - 1)
au lieu de :
score = -negamax(position_suivante, profondeur - 1)
Sans le signe moins, vous ne revenez pas au point de vue du joueur courant.
Évaluer depuis le mauvais point de vue
La fonction d’évaluation doit être cohérente. Soit elle renvoie un score du point de vue du joueur courant, soit elle renvoie un score du point de vue d’un joueur fixe et vous utilisez un facteur couleur.
Mélanger les deux conventions donne des décisions incohérentes.
Ne pas gérer les positions terminales
Chaque appel récursif doit pouvoir s’arrêter.
if position_terminale(position) or profondeur == 0:
return evaluer(position)
Sans condition terminale correcte, la récursion peut continuer trop longtemps ou produire des scores faux.
Confondre Negamax avec une IA probabiliste
Negamax suppose que l’adversaire joue parfaitement. Ce n’est pas un algorithme d’apprentissage, ni une simulation aléatoire. Pour des jeux très grands ou incertains, on utilise parfois Monte Carlo, MCTS ou du reinforcement learning.
Quand utiliser Negamax
Negamax est adapté si :
- le jeu oppose deux joueurs ;
- les gains de l’un correspondent aux pertes de l’autre ;
- l’état du jeu est connu ;
- les coups possibles sont énumérables ;
- vous pouvez évaluer une position.
Il est moins adapté si :
- le jeu a du hasard important ;
- il y a plus de deux joueurs ;
- les informations sont cachées ;
- l’espace de recherche est trop grand sans heuristique solide.
Exercices rapides
Exercice 1
Pourquoi 4 allumettes est une position perdante dans le jeu où l’on peut retirer 1, 2 ou 3 ?
Correction : quel que soit le coup joué, l’adversaire reçoit 1, 2 ou 3 allumettes, et peut prendre la dernière.
Exercice 2
Modifiez meilleur_coup pour afficher tous les coups gagnants, pas seulement le premier.
Correction possible :
def coups_gagnants(allumettes):
gagnants = []
for coup in coups_possibles(allumettes):
if -negamax(allumettes - coup) == 1:
gagnants.append(coup)
return gagnants
Exercice 3
Ajoutez un compteur pour mesurer le nombre d’appels récursifs avec et sans mémorisation.
L’objectif est de voir concrètement pourquoi la recherche exhaustive devient vite coûteuse.
Pour aller plus loin
Negamax n’est pas un nouvel algorithme magique par rapport à minimax. C’est une manière plus compacte d’écrire la même recherche quand le jeu est à somme nulle. Son intérêt vient de la clarté du code récursif : une seule fonction, un score inversé, et une logique facile à enrichir avec alpha-beta.
Pour continuer :
- Minimax en Python : comprendre l’algorithme avec un exemple de jeu
- Complexité algorithmique en Python : comprendre O(n), O(log n) et O(n²)
- La méthode de Monte Carlo en Python
La règle à retenir : Negamax maximise toujours du point de vue du joueur courant. À chaque changement de joueur, on inverse le score.
Références
- Wikipedia : Negamax
- Chessprogramming Wiki : Negamax
- Chessprogramming Wiki : Alpha-Beta
