Minimax
Quel est le meilleur coup si mon adversaire joue aussi au mieux ?
Regarde toutes les réponses jusqu’à une profondeur fixe, en supposant que chaque camp joue au mieux, et remonte les scores dans l’arbre pour choisir un coup.
MAX choisit. À la racine, MAX garde le plus grand de 3, 2 et 1. La valeur est 3 : le coup à jouer est celui qui mène au premier ▽.
Un jeu est un arbre. La position est la racine, chaque coup légal est une branche, et chaque branche mène à une position où l’autre camp a ses propres coups. Le minimax parcourt cet arbre jusqu’à une profondeur choisie et note les positions du bas avec une fonction d’évaluation, ou par victoire, nul et défaite quand la partie est finie.
Puis il remonte. À son tour, un camp prend l’enfant qui a le meilleur score pour lui (l’étape max). Au tour de l’adversaire, il suppose le pire score pour lui, car c’est ce que l’adversaire choisira (l’étape min). La valeur qui arrive à la racine est ce que vaut le meilleur jeu, et le coup qui y mène est celui à jouer.
Exemple détaillé, sur l’arbre ci-dessus. MAX (△) doit jouer et a trois options ; chacune mène à une position où MIN (▽) a trois réponses. Les neuf feuilles valent 3, 12, 8 | 2, 4, 6 | 5, 1, 9. MIN répond à chaque option par sa pire réponse pour MAX : 3 dans la première, 2 dans la deuxième, 1 dans la troisième. MAX compare alors 3, 2 et 1 et prend la première option. Sa valeur est 3 : pas le 12 visible dans l’arbre, car un MIN sensé ne le permettrait jamais.
C’est toute l’idée : supposer que l’adversaire fait toujours la réponse la pire pour vous, et choisir le coup qui est le meilleur sous cette hypothèse. On ne prédit pas ce que l’adversaire fera ; on garantit le minimum qu’on obtiendra.
Il est exact quand il peut atteindre la fin de la partie, comme au morpion. Ailleurs, la réponse vaut ce que valent l’évaluation et la profondeur.
Chargement de la démo…
Puissance 4 avec le minimax sélectionné. Augmentez la profondeur de recherche et regardez le nombre de positions examinées grandir.
- 01Lister les coups légaux de la position actuelle.
- 02Pour chaque coup, le jouer et poser la même question à l’adversaire, un niveau moins profond.
- 03À la profondeur 0, ou quand la partie est finie, renvoyer le score de la position du point de vue du camp qui choisit.
- 04À votre tour, garder le plus grand score renvoyé ; au tour de l’adversaire, le plus petit.
- 05À la racine, jouer le coup dont le score était le meilleur.
function minimax(position, depth, me):
if game_over(position): return result_score(position, me)
if depth == 0: return evaluate(position, me)
scores = [minimax(play(position, m), depth - 1, me) for m in moves(position)]
if turn(position) == me: return max(scores)
else: return min(scores)
function best_move(position, depth):
me = turn(position)
return argmax over m in moves(position) of minimax(play(position, m), depth - 1, me)b est le nombre de coups légaux par tour et d la profondeur. Puissance 4 a environ 7 coups par tour, donc la profondeur 6 fait environ 117 000 positions. Un jeu à environ 10 coups par tour atteint un million à la même profondeur.
- Trouve le meilleur coup dans son horizon, à chaque fois.
- Un même code joue à tout jeu à deux capable de lister les coups, donner un résultat et noter une position.
- Déterministe : la même position donne le même coup.
- Le coût croît exponentiellement avec la profondeur.
- Quand la partie ne peut pas être explorée jusqu’au bout, la qualité repose sur la fonction d’évaluation.
- Il examine beaucoup de branches qui ne peuvent pas changer la réponse, ce que l’élagage alpha-bêta supprime.
- 01MorpionExplore toute la partie, donc il joue parfaitement. L’option minimax simple montre combien de positions cela demande.
- 02OthelloUne recherche à profondeur fixe notée par les coins, les bords et la mobilité.
- 03Puissance 4Jusqu’à sept coups de profondeur, noté en comptant les alignements de quatre que chaque camp peut encore compléter.