Articles

Publié par

Il y a 7 années -

Temps de lecture 6 minutes

L’algorithme Minimax

Cette article traite de l’algorithme Minimax abordé lors d’un hands-on durant une journée XKE. L’objectif était de développer une intelligence artificielle basique pour un tournoi de Puissance 4. On rencontre souvent le minimax dans la théorie mathématique des jeux, domaine rattaché à l’intelligence artificielle. Son étude permet d’aborder les notions de récursion, de parcours de graphes, de complexité en temps et complexité en espace…

Agent rationnel

Dans le monde de l’intelligence artificiel, un programme qui « réfléchit » est souvent appelé un agent rationnel.

Un agent simple interagit de deux façons différentes avec l’environnement qui l’entoure.

  • Il perçoit l’environnement à l’aide de capteurs, comme par exemple une caméra ou une sonde.
  • Il agit sur l’environnement à l’aide d’effecteurs, comme par exemple un bras ou une jambe mécanique.

L’agent rationnel possède une capacité supplémentaire : il peut mesurer la performance d’une action sur l’environnement. Ainsi, en fonction de la séquence des événements perçus et donc de l’état connu de son environnement, il va sélectionner l’action qui maximisera la mesure de performance.

Le jeu : un environnement multi-agents

Un jeu est un environnement où évoluent plusieurs agents, représentés par des joueurs. L’environnement est concurrentiel, dans lequel les buts des agents sont en conflit.

L’application du minimax se borne aux jeux qui possèdent les caractéristiques suivantes :

  • Un jeu alterné : chaque agent joue à tour de rôle. Nous nous limiterons à 2 joueurs.
  • Un environnement déterministe : l’agent possède tous les éléments nécessaires pour prédire exactement le nouvel état de l’environnement après l’exécution d’une action. Exemple, si un joueur du Puissance 4 choisit de jouer la première colonne avec un jeton rouge, il est possible de déterminer la totalité du plateau de jeu après cette action.
  • Un environnement à information parfaite : la totalité de l’environnement est observable par tous les agents. Exemple, le plateau du jeu du morpion est visible par tous, alors que dans le poker, le jeu des adversaires ne l’est pas.
  • Un jeu à somme nulle : la somme des gains de tous les joueurs s’annule. Exemple, si on définit le gain d’une partie de puissance 4 comme 1 si on gagne, 0 si ex æquo et -1 si on perd, alors dans tous les cas , à la fin de la partie, la somme des gains est nulle. Autrement dit, une situation favorable pour un joueur est obligatoirement défavorable pour ses adversaires. Dans le cadre des jeux à somme non-nulle, certaines issues sont soit favorable, soit défavorable, pour tous les joueurs à la fois (voir le dilemme du prisonnier).

Posons le problème…

Le problème d’un agent rationnel dans le cadre d’un jeu peut se résumer en une phrase : « Trouver le meilleur coup pour gagner la partie ! ». Posons le problème :

  • L’état initial : le plateau du jeu à un instant T
  • Les joueurs : quel joueur est en train de jouer ?
  • Les actions : les coups légaux (qui respectent les règles) possibles pour un état du plateau de jeu donné.
  • Le modèle de transition : permet de déterminer les nouveaux états du plateau de jeu en fonction des actions choisies précédemment.

Voici un schéma afin de vous représenter le problème :

…comme un problème d’exploration de graphes

Effectivement, nous reconnaissons un graphe dans le schéma précédent, les états représentent les nœuds, les actions représentent les liens, qui permettent de déduire des états enfants et ainsi de suite. Dans le cadre des jeux, le graphe est souvent acyclique et orienté, c’est-à-dire qu’aucun lien ne permet de revenir à un nœud déjà exploré. Il y a différentes façon d’explorer un graphe mais elles appartiennent souvent à deux grandes familles : l’exploration en largeur d’abord et l’exploration en profondeur d’abord.

L’objectif de l’agent rationnel est donc d’explorer l’arbre et donc d’évaluer un maximum de coups d’avance afin de déterminer quel sera le meilleur coup suivant :

Voici une animation qui résume le processus minimax (avec une profondeur d’exploration maximum de 2) :

Algorithme Minimax


Implémentation de l’algorithme

public class Minimax {

    // Cette méthode est proche du comportement de getMaxSCore()
    // sauf qu'elle retourne l'action associée au meilleur score
    public Action getBestActionWithMinimax(State state) {
        Action bestAction = null;
        int maxScore = -State.BEST_SCORE;

        for (Action action : state.getActions()) {
            State childState = getChildState(state, action);
            int score = getMinScore(nextState);

            if (score > maxScore) {
                maxScore = score;
                bestAction = action;
            }
        }
        return bestState;
    }

    // Cette méthode symbolise le tour de notre agent, elle
    // sélectionne le score le plus élevé parmi les états
    // enfants
    int getMaxScore(State state) {
        // testFinalState() va borner notre exploration en vérifiant la
        // fin du jeu ou une profondeur d'exploration maximum
        if (testFinalState(state)) {
            // La fonction d'évaluation
            return getScore(state);
        }

        int maxScore = -State.BEST_SCORE;

        // La méthode getActions() retourne tous les coups
        // possilbes
        for (Action action : state.getActions()) {
            // La méthode getChildState() détermine l'état
            // du jeu en simulant l'action sélectionée
            State childState = getChildState(state, action);
            // La récursion caractérise l'exploration en profondeur d'abord            
            int childScore = getMinScore(childState);

            maxScore = max(maxScore, childScore);
        }
        return maxScore;
    }

    // Cette méthode symbolise le tour de l'adversaire,
    // elle sélectionne le score le moins élevé parmi
    // les états enfants
    int getMinScore(State state, int depth) {
        if (testFinalState(state)) {
            return getScore(state);
        }

        int minScore = State.BEST_SCORE;

        for (Action action : state.getActions()) {
            State childState = getChildState(state, action);
            // La récursion caractérise l'exploration en profondeur d'abord
            int childScore = getMaxScore(childState);

            minScore = min(minScore, childScore);
        }
        return minScore;
    }
}

Complexité en temps et en espace

Comme évoqué précédemment, cette algorithme réalise une exploration en profondeur d’abord complète de l’arbre de jeu (ou jusqu’à la profondeur maximale). Ainsi si la profondeur maximale de l’arbre est de m et qu’il y a b coups légaux à chaque point, alors la complexité en temps est O(bm). Effectivement, dans sa forme la plus simple, l’algorithme explorera tous les nœuds pour déterminer le meilleur des coups.

Concernant la complexité en espace, dans le cas où toutes les actions sont générées en une fois, elle est de O(bm). En effet tous les états précédents doivent être conservés tant qu’ils n’ont pas été explorés. Dans le cas où les actions sont générées les une après les autres, la complexité est de O(m), seuls les états explorés sont conservés.

Pour aller plus loin

Pour des jeux réels, l’algorithme minimax est trop consommateur en temps d’exécution dans sa version simplifiée. Mais il est à la base de l’analyse mathématique des jeux ainsi que d’autres algorithmes plus praticables. Nous pourrons voir dans un autre article l’élagage alpha-béta qui permet d’optimiser l’exploration minimax. Et si vous souhaitez aller encore plus loin, vous pouvez jeter un coup d’œil à un hands-on sur le puissance 4 réalisé en XKE, disponible sur github https://github.com/mrenou/connect4-minimax.

Publié par

Commentaire

1 réponses pour " L’algorithme Minimax "

  1. Publié par , Il y a 2 années

    Le code donné en exemple est incohérent la méthode getMinScore prends 2 paramètres et dans votre exemple lorsque vous l’appelez elle n’en prend qu’un. De plus, vous n’avez pas expliquer ce que faisait la méthode getChildState.

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *

Nous recrutons

Être un Xebian, c'est faire partie d'un groupe de passionnés ; C'est l'opportunité de travailler et de partager avec des pairs parmi les plus talentueux.