Algorithme minimax

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_n)) si p est un nœud Joueur avec fils O₁, …, O_n ;
• minimax(p) = min(minimax(O₁), …, minimax(O_n)) si p est un nœud Opposant avec fils O₁, …, O_n.

Dans le schéma ci-dessus, les nœuds gris représentent les nœuds joueurs et les bleus les nœuds opposants. Pour déterminer la valeur du nœud A, on choisit la valeur maximum de l’ensemble des nœuds B (A est un nœud joueur). Il faut donc déterminer les valeurs des nœuds B qui reçoivent chacun la valeur minimum stockée dans leurs fils (les nœuds B sont opposants). Les nœuds C sont des feuilles, leur valeur peut donc être calculée par la fonction d’évaluation.

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.

En pratique, la valeur théorique de la position P ne pourra généralement pas être calculée. En conséquence, la fonction d’évaluation sera appliquée sur des positions non terminales. On considérera que plus la fonction d’évaluation est appliquée loin de la racine, meilleur est le résultat du calcul. C'est-à-dire qu’en examinant plus de coups successifs, nous supposons obtenir une meilleure approximation de la valeur théorique donc un meilleur choix de mouvement.

Si l’ensemble des valeurs prises par f(p) est symétrique par rapport à 0[1] une fonction g(p) peut être définie telle que :

• g(p) = f(p) si nous sommes sur un nœud joueur
• g(p) = –f(p) si nous sommes sur un nœud opposant

Ainsi on définit negamax à partir de cette nouvelle fonction :

• negamax(p) = g(p) si P est terminale
• negamax(p) = max(–NegaMax(p_i)) sinon

À partir du même exemple que pour l’algorithme Minmax, voici l'arbre résultant :

Le pseudocode de l'algorithme minimax de profondeur limitée est présenté ci-dessous :

function minimax(node, depth, maximizingPlayer) is
    if depth = 0 or node is a terminal node then
        return the heuristic value of node
    if maximizingPlayer then
        value := −∞
        for each child of node do
            value := max(value, minimax(child, depth − 1, FALSE))
    else (* minimizing player *)
        value := +∞
        for each child of node do
            value := min(value, minimax(child, depth − 1, TRUE))
    return value

(* Initial call *)
minimax(origin, depth, TRUE)

Cet algorithme peut être optimisé grâce à l'implémentation de la technique dite de l'élagage alpha-bêta[1]. L'algorithme alpha bêta accélère la routine de recherche minimax en éliminant les cas qui ne seront pas utilisés. Cette méthode utilise le fait que tous les autres niveaux de l’arbre seront maximisés et que tous les autres niveaux seront minimisés.