8. Minimax
8.1 Construction de l’arbre
À partir d’un état où MAX doit jouer :
- générer les coups de MAX;
- pour chacun, générer les réponses possibles de MIN;
- alterner MAX et MIN jusqu’à la fin du jeu ou une profondeur fixée;
- évaluer chaque feuille selon le gain de MAX.
La vidéo fait une autocorrection importante : l’arbre commence ici par MAX, mais les feuilles peuvent appartenir à un niveau MAX ou MIN. Ce qui demeure invariant est que leur valeur mesure le résultat de MAX.
8.2 Propagation
- Si le parent est MAX : lui attribuer le maximum des valeurs de ses enfants.
- Si le parent est MIN : lui attribuer le minimum des valeurs de ses enfants.
Une valeur élevée dans une feuille éloignée ne suffit pas à justifier un coup : si MIN peut éviter cette feuille et forcer une valeur plus basse, c’est cette réponse rationnelle qui détermine la valeur de la branche.
8.3 Interprétation
La valeur de la racine indique le meilleur gain que MAX peut garantir contre un MIN rationnel. MAX choisit l’enfant dont la valeur propagée est maximale. Après le coup réellement joué par MIN, l’état atteint devient une nouvelle racine et le calcul est refait pour les tours suivants.
8.4 Jeu de Nim
Dans l’exemple, un joueur doit séparer un ensemble de bâtonnets en deux sous-ensembles de tailles différentes; il perd lorsqu’aucune séparation valide n’est possible. Avec sept bâtonnets et l’évaluation 1/0, la valeur remontée à la racine est 0. Ainsi, si MIN joue correctement, MAX ne peut garantir une victoire, quel que soit son premier découpage.
Racine MAX; trois enfants MIN B,C,D; valeurs des feuilles du point de vue de MAX. Parcours gauche à droite. Après B=3, la première feuille 2 de C puis D permet la coupure β≤α. Le résultat reste 3.
Source : Schéma original créé pour le portail le 16 octobre 2026; aucun graphe source incomplet reconstitué. · S04 §8–9 et mini-test