IA de jeux, Implémenter une IA arborescente, en C++

Voir aussi : video youtube - video peertube - code source

Cet article, de la série “IA de jeux”, présente l’algorithme de Monte-Carlo Tree Search, pour le jeu de Puissance 4. Il explique tout d’abord la notion d’arbre de jeux puis l’algorithme de MCTS. Enfin, il propose une implémentation en C++ et la compare aux IA présentées dans l’article précédent (Random, Monte-Carlo).

Articles de la séries IA de jeux :

Arbre de jeux

Les IA de jeu sont souvent basées sur un arbre de jeux, c’est-à-dire une exploration des jeux obtenus en jouant différents coups successifs. Par exemple, imaginons qu’on joue au Puissance 4 et qu’on arrive au jeu suivant.

0123456
Y.Y.Y.Y
RRR.R.R
YYY.Y.Y
RRR.R.R
YYY.Y.Y
RRR.R.R
moves: 1 3 5
status: PlayY

Ici, c’est au joueur Jaune de jouer. Pour choisir son coup, il peut calculer comment va évoluer le jeu s’il joue (virtuellement) chacun des coups possibles. Récursivement, il peut ensuite calculer l’évolution de chacuns de ces “jeux virtuels”. On construit ainsi l’arbre des jeux obtenus en jouant les coups possibles.

Dans la figure ci-dessus, la racine de l’arbre correspond au jeu actuel et ses sous arbres aux jeux obtenus en jouant les coups possibles (1, 3 ou 5). Par exemple, le sous-arbre le plus à gauche correspond à jouer le coup 1. On obtient alors le jeu où la colonne 1 est remplie, où Rouge doit jouer et où les coups possibles sont 3 et 5. Récursivement, si Rouge joue 5 puis Jaune joue 3, on arrive au jeu tout en bas de la figure.

L’intérêt d’un arbre de jeu est de nous aider à choisir la branche de la racine qui placera le jeu réel dans une position où l’on a le plus de chance de gagner. Généralement, il est impossible de développer l’arbre de jeux complet car les possibilités sont trop nombreuses. L’objectif des IA est donc de consacrer le temps de calcul disponible à développer au maximum les branches intéressantes de l’arbre.

Monte-Carlo Tree Search

Généralités

MCTS est un algorithme assez classique pour les jeux de plateau (Go, Othello, Gomoku, Hex…). Il consiste à construire progressivement un arbre de jeux, non-équilibré, en utilisant une politique de descente d’arbre et une politique d’évaluation.

Plus précisément, l’algorithme comporte quatre étapes (sélection, expansion, simulation et rétropropagation) qui sont répétées un grand nombre de fois. A la fin de ce calcul, on choisit le coup correspondant à la branche la plus intéressante de la racine.

Exemple

Pour illustrer l’algorithme, considérons qu’on a déjà calculé l’arbre de jeu de la figure précédente et regardons le déroulement d’une itération MTCS (figure suivante).

La sélection consiste à parcourir l’arbre, de la racine \(s_0\) jusqu’à une feuille \(s_1\). Ici, on appelle “feuille” un noeud de l’arbre pour lequel on a pas construit tous les noeuds enfants possibles (c’est-à-dire qu’on n’a pas testé tous les coups possibles du jeu correspondant au noeud). Le choix des noeuds enfants (Tree policy) sera détaillé dans la section suivante.

A partir du noeud \(s_1\), l’expansion consiste à créer un nouveau noeud enfant, \(s_2\), pour tester un coup non encore considéré. Le choix du coup n’est pas très important; on peut prendre le premier disponible.

L’étape de simulation consiste à effectuer une partie aléatoire à partir du jeu correspondant au noued \(s_2\). On ne retient pas le déroulement exact de cette partie aléatoire mais juste le résultat.

Enfin, l’étape de rétropropagation consiste à mettre à jour les informations des noeuds (nombre de simulations, score total des résultats), du nouveau noeud \(s_2\) jusqu’à la racine \(s_0\). Ceci permet de mettre à jour l’arbre pour les itérations suivantes.

Tree policy

Lors de l’étape de sélection, pour descendre dans l’arbre, on doit choisir un noeud enfant. Il s’agit d’un problème de bandit manchot : on veut privilégier les choix qui semblent déjà intéressants (exploitation), tout en regardant également les choix qui ont été peu considérés jusqu’ici (exploration). Une solution classique à ce problème est d’utiliser la formule UCB :

Cette formule indique simplement qu’on va choisir le nouveau \(s_1\) en prennant le noeud enfant \(j\) de l’ancien \(s_1\) qui maximise le score donné entre les crochets. Ce score comprend un terme d’exploitation et un terme d’exploration : \(w_j\) est le score total de \(j\), \(n_j\) est le nombre de simulations de \(j\) et \(n_s_1\) est le nombre de simulations de \(s_1\). \(K\) est un paramètre de l’algorithme qui permet de régler son comportement (favoriser/défavoriser l’exploration).

Implémentation

Intégration à l’interface Bot

Pour ajouter un bot dans notre implémentation, il suffit de dériver une classe de Bot et de redéfinir la méthode genmove. On a également besoin d’un générateur aléatoire et du nombre d’itérations MCTS à réaliser.

// Bot.hpp

class BotMcts : public Bot {
    private:
        random_t _rng;
        const int _nIters;

    public:
        BotMcts(int nIters);
        int genmove(const Game & game) override;
};

L’implémentation du constructeur de BotMcts est triviale. Pour la méthode genmove, il suffit d’initialiser un arbre de recherche, de réaliser les itérations MCTS puis de retourner le meilleur coup trouvé.

// Bot.cpp

BotMcts::BotMcts(int nIters) : 
    _rng(std::random_device{}()), 
    _nIters(nIters) 
{}

int BotMcts::genmove(const Game & game) {
    Node root(game);
    for (int i=0; i<_nIters; i++) {
        Node * node = selectAndExpand(&root);
        Status status = simulate(node, _rng);
        backpropagate(node, status);
    }
    return bestNode(root);
}

Structure d’arbre

Pour implémenter l’algorithme de MTCS, on a besoin d’un arbre n-aire. Pour cela, il suffit d’une structure Node avec un tableau de Node pour les noeuds enfants. On met également quelques attributs nécessaires à l’algorithme (score total du noeud, nombre de simulations…) ainsi qu’un pointeur vers le noeud parent, pour la rétropropagation.

// Bot.hpp

struct Node {
    double _reward;
    int _nSims;
    Game _game;
    int _nMoves;
    Player _player;  // before playing the move
    Node * _parent;
    std::vector<std::unique_ptr<Node>> _children;

    Node(const Node &) = delete;
    Node(const Game & game);
    Node(const Game & game, Node * parent, int k0);
};

// Bot.cpp

Node::Node(const Game & game) :
    _reward(0), _nSims(0), _game(game), 
    _nMoves(_game.getMoves().size()), 
    _player(game.getCurrentPlayer()), _parent(nullptr) 
{
    _children.reserve(_nMoves);
}

Node::Node(const Game & game, Node * parent, int k0) :
    _reward(0), _nSims(0), _game(game), _parent(parent) 
{
    _player = _game.getCurrentPlayer();
    _game.playK(k0);
    _nMoves = int(_game.getMoves().size());
    _children.reserve(_nMoves);
}

Attention : ici il est nécessaire de pré-allouer le tableau stockant les noeuds enfants car sinon il y aurait des réallocations et les pointeurs vers les noeuds parents ne seraient plus valides.

Implémentation de MCTS

La fonction selectAndExpand réalise les étapes de sélection et d’expansion : elle traverse l’arbre depuis la racine et retourne le noeud à simuler. Si on arrive à une fin de partie, on ne peut pas faire d’expansion mais on peut simplement retourner le noeud atteint.

// Bot.cpp

Node * selectAndExpand(Node * root) {
    Node * n = root;
    while (true) {
        // return node if game terminated
        if (not n->_game.isRunning())
            return n;
        // expand if new child found
        const int k = n->_children.size();
        if (k < n->_nMoves) {
            n->_children.push_back(std::make_unique<Node>(n->_game, n, k));
            return n->_children.back().get();
        }
        // select child node using UCB
        n = selectUcb(n);
    }
}

On implémente également une fonction ucb1 pour calculer le score UCB d’un noeud et une fonction selectUcb pour calculer la formule UCB complète sur les enfants d’un noeud donné.

// Bot.cpp

double ucb1(double cReward, double cNsims, int pNsims) {
    assert (cNsims > 0);
    const double exploitation = cReward / cNsims;
    const double exploration = std::sqrt(std::log(1 + pNsims) / cNsims);
    return exploitation + KUCT*exploration;
}

Node * selectUcb(const Node * n) {
    int bestI = -1;
    double bestScore = -1.0;
    for (int i=0; i<n->_nMoves; i++) {
        const auto & c = n->_children[i];
        const double s = ucb1(c->_reward, c->_nSims, n->_nSims);
        if (s > bestScore) {
            bestScore = s;
            bestI = i;
        }
    }
    assert(bestI > -1);
    return n->_children[bestI].get();
}

Les étapes de simulation et de rétropropagation sont assez triviale. Il faut juste faire attention, lors de la rétropropagation, à bien calculer le score par rapport au joueur correspondant au noeud. En effet, d’un coup à l’autre, le joueur change et il faut bien prendre en compte que chaque joueur essaie de maximiser son propre score.

// Bot.cpp

Status simulate(const Node * node, random_t & rng) {
    Game g(node->_game);
    return playoutRandom(g, rng);
}

void backpropagate(Node * node, Status status) {
    Node * n = node;
    while (n) {
        n->_reward += computeScore(status, n->_player);
        n->_nSims += 1;
        n = n->_parent;
    }
}

Enfin, la fonction bestNode permet de choisir le coup à jouer, une fois les itérations MCTS réalisées. Pour cela, il suffit de trouver le noeud enfant de la racine qui a été le plus souvent simulé.

// Bot.cpp

int bestNode(const Node & root) {
    const auto & cs = root._children;
    auto cmp = [](const std::unique_ptr<Node> & n1, const std::unique_ptr<Node> & n2)
        { return n1->_nSims < n2->_nSims; };
    auto iter = std::max_element(cs.begin(), cs.end(), cmp);
    return std::distance(cs.begin(), iter);
}

Résultats

Pour rappel, les graphiques ci-dessous indiquent la répartition des parties de jeu : Rouge gagne en rouge, Jaune Gagne en jaune et égalité en bleu.

Comparaison avec Random

On peut tout d’abord comparer MCTS à Random, en fonction du nombre d’itérations MCTS. Comme attendu, on constate que MCTS est bien meilleur que Random.

Comparaison avec MCTS-512

Pour MCTS contre MCTS à 512 itérations, on constate qu’on a des résultats équivalents à 512 itérations et que MCTS prend l’avantage à 1024 itérations.

Comparaison avec Monte-Carlo

Si on compare MCTS contre MC-128 et MC contre MCTS-512, on constate que MCTS est effectivement plus efficace que MC, à paramétrages comparables (voir également la section suivante).

Comparaison à temps équivalent

Il faut noter que dans nos implémentations, le paramètre de MC est le nombre de simulations par coups possibles alors que le paramètre de MCTS est le nombre total de simulations. Comme il y a généralement 7 coups possibles, si on veut comparer MCTS et MC pour le même nombre de simulations, il faudrait utiliser une valeur de paramètre 7 fois plus grande pour MCTS.

Cependant, MCTS réalise d’autres calculs que les simulations, par rapport à MC. Si on veut comparer à temps constant, il faut réellement chronométrer les calculs et comparer des paramétrages comparables. Par exemple, si on prend un réglage de paramètre 6 fois plus grand pour MCTS, on constate des temps de calculs assez proches.

$ cat out-test1-McX-Random.csv
winR winY tie ry ryt dt nGames value
0.96 0.04 0 1 1 0.162487 300 8
0.98 0.02 0 1 1 0.287232 300 16
0.996667 0.00333333 0 1 1 0.564018 300 32
0.996667 0.00333333 0 1 1 1.01998 300 64
1 0 0 1 1 1.9695 300 128

$ cat out-test1-MctsX-Random.csv
winR winY tie ry ryt dt nGames value
0.973333 0.0266667 0 1 1 0.146129 300 48
0.993333 0.00666667 0 1 1 0.27603 300 96
1 0 0 1 1 0.510616 300 192
1 0 0 1 1 0.954336 300 384
1 0 0 1 1 1.90944 300 768

Si on trace ces données, on obtient le graphique suivant. On constate qu’à temps équivalent, MCTS est plus performant que MC. Ce phénomène semble même s’accentuer avec le temps de calcul.

On notera cependant que les comparaisons à temps équivalent ont l’inconvénient de dépendre beaucoup de l’implémentation des algorithmes.

Conclusion

Dans cet article, on a vu le principe des arbres de jeux ainsi qu’un algorithme, Monte-Carlo Tree Search, basé sur ce principe. Plus précisément, MCTS construit progressivement un arbre de jeux en sélectionnant les branches selon un compromis exploitation/exploration et estimant les nouveaux noeuds par des simulations aléatoires. Ainsi, MCTS développe plus profondément les branches qui semblent intéressantes, ce qui lui permet d’être plus efficace que des algorithmes comme Monte-Carlo.