Minimax

Dans un jeu à somme nulle, le gain d’un joueur est exactement la perte de l’autre : il n’y a donc aucune place pour un bénéfice mutuel ni aucune raison d’attendre de la coopération. Le minimax y répond par le pessimisme sur l’adversaire : évaluer chaque coup disponible par le pire résultat auquel il pourrait mener si l’adversaire joue du mieux possible, et choisir le coup dont le pire cas est le meilleur.

Appliquée à un arbre de jeu, la règle devient une évaluation récursive. Les positions terminales sont notées du point de vue du premier joueur. Aux nœuds où ce joueur joue, la valeur est le maximum sur les enfants ; aux nœuds où l’adversaire joue, c’est le minimum. Les valeurs remontent jusqu’à la racine, et le coup menant à l’enfant de meilleure valeur est retenu.

L’évaluation complète est impossible pour tout jeu intéressant, la taille de l’arbre croissant exponentiellement avec la profondeur. Deux ajustements la rendent praticable. L’élagage alpha-bêta suit les bornes de ce que chaque joueur peut déjà garantir et abandonne les branches qui, de façon démontrable, ne peuvent changer le résultat, renvoyant exactement le même coup en examinant bien moins de nœuds. Et la recherche est coupée à une profondeur fixée, une fonction d’évaluation heuristique estimant les positions non terminales.

Le fondement théorique est le théorème du minimax de von Neumann, qui établit que tout jeu fini à somme nulle à deux joueurs possède une valeur bien définie, atteinte par les deux joueurs lorsque les stratégies mixtes sont permises. C’est ce qui fait du minimax plus qu’une heuristique : il identifie un jeu véritablement optimal et non simplement prudent, au sein de cette classe de jeux.

Considérez un arbre peu profond où le joueur maximisant choisit entre deux coups. Le coup A mène à des réponses adverses valant 3 et 5 ; le coup B mène à des réponses valant 2 et 9. L’adversaire minimise, donc A vaut 3 et B vaut 2.

Le joueur maximisant retient donc A, qui vaut 3, alors même que B contient le gain isolé le plus élevé, 9. Ce 9 ne serait atteint que si l’adversaire commettait une bévue, et le minimax suppose qu’il n’en commettra pas : il optimise le résultat garanti, non le résultat espéré.

L’élagage alpha-bêta parvient plus vite à la même conclusion. Ayant établi que A garantit 3, la recherche examine B, trouve une réponse valant 2, et peut cesser immédiatement d’explorer B : l’adversaire dispose déjà d’une réponse qui rend B pas meilleur que 2, ce qui est pire que 3, donc les branches restantes de B ne peuvent changer la décision.