Minimax
Publié le 2025-12-22 19:32
Dans un jeu comme les échecs, on n’a pas d’aléatoire et tout le monde voit tout. C’est ce qu’on appelle un jeu à information parfaite. L’idée de minimax naît naturellement : je choisis un coup qui me donne la meilleure issue possible, en supposant que l’adversaire répond toujours de la meilleure manière contre moi.
Autrement dit, chaque coup n’est pas jugé “bon” parce qu’il piège quelqu’un. Il est jugé “bon” s’il reste bon même face aux meilleures défenses. C’est une philosophie assez stricte, mais c’est exactement ce qui rend minimax pertinent : c’est un choix rationnel dans un monde où l’adversaire ne fait pas de cadeaux.
On peut visualiser minimax comme un arbre. À la racine, c’est mon tour : j’ai une liste de coups possibles. Pour chacun, l’adversaire aura ensuite une liste de réponses possibles. Puis ce sera à nouveau mon tour, etc. À la fin, on obtient des feuilles (des positions terminales de la recherche) auxquelles on attribue un score. Ensuite, on remonte ces scores : quand c’est mon tour, je garde la branche qui maximise mon score ; quand c’est le tour adverse, je garde la branche qui minimise mon score.
Il existe une forme très pratique appelée negamax, qui simplifie l’implémentation. Au lieu de coder “max” d’un côté et “min” de l’autre, on adopte toujours le point de vue du joueur au trait : ce qui est bon pour moi est mauvais pour l’autre, donc le score change simplement de signe quand on change de camp. C’est une simplification élégante, mais elle ne change pas la logique : on explore, on évalue, on remonte, on choisit.
Exemple venant de l'article de wikipedia https://fr.wikipedia.org/wiki/Algorithme_minimax
Le nœud A prend donc la valeur 5. Le joueur doit donc jouer le coup l’amenant en B2. En observant l’arbre, on comprend bien que l’algorithme considère que l’opposant va jouer de manière optimale : il prend le minimum. Sans ce prédicat, on choisirait le nœud C1 qui propose le plus grand gain et le prochain coup sélectionné amènerait en B1. Mais alors on prend le risque que l’opposant joue C3 qui propose seulement un gain de 3.
Negamax est une simplification qui défini la valeur d'un nœud comme la symétrique par rapport à 0 de l'évaluation adverse.
Mais le point faible est évident : la taille de l’arbre explose. Dès qu’on dépasse quelques coups d’avance, le nombre de positions devient gigantesque. C’est pour ça que minimax, seul, est rarement suffisant : il faut apprendre à explorer “plus intelligemment”, en coupant des branches inutiles. C’est l’objet de l’alpha-beta pruning.