Algorithme minimax

L'algorithme minimax (aussi appelé algorithme MinMax) est un algorithme qui s'applique à la théorie des jeux pour les jeux à deux joueurs à somme nulle (et à information complète) consistant à minimiser la perte maximum (c'est-à-dire dans le pire des cas). Pour une vaste famille de jeux, le théorème du minimax de von Neumann assure l'existence d'un tel algorithme, même si dans la pratique il n'est souvent guère aisé de le trouver. Le jeu de hex est un exemple où l'existence d'un tel algorithme est établie et montre que le premier joueur peut toujours gagner, sans pour autant que cette stratégie soit connue. Il amène l'ordinateur à passer en revue toutes les possibilités pour un nombre limité de coups et à leur assigner une valeur qui prend en compte les bénéfices pour le joueur et pour son adversaire. Le meilleur choix est alors celui qui minimise les pertes du joueur tout en supposant que l'adversaire cherche au contraire à les maximiser (le jeu est à somme nulle). Il existe différents algorithmes basés sur MinMax permettant d'optimiser la recherche du meilleur coup en limitant le nombre de nœuds visités dans l'arbre de jeu, le plus connu est l'élagage alpha-bêta. En pratique, l'arbre est souvent trop vaste pour pouvoir être intégralement exploré (comme pour le jeu d'échecs ou de go). Seule une fraction de l'arbre est alors explorée. Dans le cas d'arbres très vastes, une IA (système expert, évaluation par apprentissage à partir d'exemple, etc.) peut servir à élaguer certaines branches sur la base d'une estimation de leur utilité. C'est ce qui est employé, par exemple, dans le cadre du go. L'algorithme minimax visite l'arbre de jeu pour faire remonter à la racine une valeur (appelée « valeur du jeu ») qui est calculée récursivement de la façon suivante : minimax(p) = f(p) si p est une feuille de l’arbre où f est une fonction d’évaluation de la position du jeu ; minimax(p) = max(minimax(O), ..., minimax(O)) si p est un nœud Joueur avec fils O, ..., O ; minimax(p) = min(minimax(O), ..., minimax(O)) si p est un nœud Opposant avec fils O, .