Comprendre MCTS 4 - Monte Carlo Tree Search (2024)

Bonjour. Aujourd'hui, je clos enfin ma série concernant l'IntelligenceArtificielle pour les jeux et MCTS. Dans le dernier épisode, on avait parlé des heuristiques qui ont permis à Deep Blue de vaincre Gary Kasparov.

On va donc voir l'algorithme qui a été utilisé par Deep Mind pour vaincre Lee Sedol. Autant vous avertir tout de suite, je ne vais pas parler d'apprentissage automatique. Si le Deep Learning vous intéresse, David Louapre a sorti une vidéo.

Je vous mets le lien ici : https://frama.link/XuXZf_DJ. Nous, on va s'intéresser à autre chose. On va se pencher sur la partie algorithme pour les jeux, et donc les méthodes dites de Monte Carlo.

Depuis le début de cette série, on a vu que les jeux extensifs, comme le go ou les échecs, peuvent se représenter sous la forme d'arbre, et que l'essentiel du travail pour gagner était de prédire un score pour chaque nœud.

On a aussi vu qu'on pouvait faire ça en analysant toutes les possibilités du jeu, ou en utilisant des fonctions d'évaluation qui permettaient d'approximer l'état d'un jeu. On a aussi vu que ces méthodes avaient des limites.

Parmi ces limites, on a vu que certains jeux n'avaient pas de fonctions d'évaluation évidentes et que quand il y avait trop de coups possibles, on n'arrivait plus à s'en sortir.

Aujourd'hui, on va donc essayer de voir une autre méthode qui permette de traiter ces cas. On va chercher à atteindre le même but que d’habitude : pour chaque coup possible, on va essayer de lui attribuer un score.

Mais on est dans une situation pour le moins complexe : quelle que soit la profondeur à laquelle on ira chercher, on n'a pas de fonction d'évaluation donc il sera impossible d'évaluer un plateau à l'aide d'une telle fonction.

Il va falloir trouver autre chose. Il existe déjà un algorithme intéressant pour faire des estimations de fonctions complexe, qui s'appelle Monte-Carlo. Ceux qui font de la physique le connaissent sans doute.

Il consiste à évaluer l'intégrale d'une fonction en l'approximant par l'aire située au-dessous de la courbe. Pour y arriver, on va faire des tirages et calculer si ces tirages sont au-dessus ou au-dessous de la courbe. Je vous mets une image.

Comprendre MCTS 4 - Monte Carlo Tree Search (1)

La première application aux jeux n'est pas vraiment plus complexe. On l'appelle "flat" Monte-Carlo, ou Monte-Carlo à plat, vous comprendrez pourquoi sous peu.

Elle consiste simplement, pour chaque mouvement possible, de générer un certain nombre de parties aléatoires et de vérifier combien de parties sont gagnées. Cela donne un score qui approxime (mal) les probabilités de gagner.

On voit bien que cette méthode pose problème. Les parties générées sont totalement aléatoires. Or, ni l'adversaire ni nous ne jouons de manière aléatoire. De plus, on va tester pareillement toutes les possibilités, y compris les plus mauvaises

Si 990 simulations nous donnent perdants si nous jouons un coup, est-il vraiment nécessaire de continuer à tester ? C'est à partir de ces constatations que Levente Kocsis et Csaba Szepesvári vont publier le premier article sur MCTS.

L'idée de base est simple: on va mélanger l'idée derrière le flat Monte-Carlo, tout en essayant de construire intelligemment l'arbre de jeu. On va notamment s'intéresser aux coups les plus prometteurs et aux coups sur lesquels on a le moins d'information

L'algorithme MCTS fonctionne en 4 phases: sélection, expansion, simulation et rétropropagation, ce dernier terme n'ayant rien à voir avec les réseaux de neurones sinon l'idée de base.

Gardez à l'esprit qu'on construit l'arbre peu à peu. Pour chaque noeud qu'on a modélisé, on va garder en mémoire le nombre de fois où on l'a inclus dans une simulation et son score estimé pour le moment.

La sélection va consister à décider sur quelle partie de l'arbre on va se concentrer. On va partir de la racine, et on va descendre selon un certain critère qui prenne en compte les deux métriques que l'on vient de citer.

Basiquement, on veut voir quels coups sont les meilleurs parmi ceux qu'on aurait le plus envie de jouer (ceux qui ont le plus haut score), mais on ne voudrait pas non plus manquer une opportunité. On va donc jouer aussi les coups qu'on a peu joués.

A chaque fois qu'on descend d'un niveau, on regarde si tous les enfants du nœud qu'on regarde ont été explorés. Si ce n'est pas le cas, on explore un nœud fils qui ne l'a pas encore été.

Si on décide d'explorer un nouveau nœud fils, on arrête la sélection. On ajoute le nœud fils en question à l'arbre (c'est la phase d'expansion) et on passe sur un nouveau mode.

Dans ce nouveau mode, on joue de manière aléatoire comme dans le cas du Monte-Carlo à plat, jusqu'à atteindre un état final du jeu. Rappelez-vous qu'on fait ce choix parce qu'on ne connaît pas de "bonne" stratégie a priori, on n'a donc pas de meilleur choix.

Durant cette étape de simulation, on n'ajoute aucun nœud à l'arbre. On essaie juste de simuler une partie aléatoire aussi vite que possible pour obtenir un résultat rapidement.

De plus, ajouter tous les nœuds à l'arbre le rendrait trop grand en mémoire et ajouterait des nœuds qu'on a choisi aléatoirement, alors que c'est précisément ce qu'on tente d'éviter.

Enfin, une fois un état final du jeu atteint, on calcule le score des joueurs, et on le reporte sur les nœuds sélectionnés dans l'arbre, avec un pourcentage équivalent au nombre de fois où ils ont été sélectionnés. C'est ce qu'on appelle la rétropropagation.

Comprendre MCTS 4 - Monte Carlo Tree Search (2)

Voilà l'algorithme de MCTS ou Monte Carlo Tree Search. Il est appelé ainsi parce qu'il revient à construire un arbre et à utiliser Monte Carlo. Contrairement au "flat" Monte Carlo, il va essayer de construire un arbre.

Un point important est la manière de choisir entre exploration et exploitation. Dans leur article, Kocsis et Szepesvári proposent un critère nommé Upper Confidence Bound, qui a donné son nom à leur implémentation de MCTS.

On l'appelle Upper Confidence Tree, et il est, et de loin, le plus utilisé. Il existe aussi de nombreuses extensions. En particulier, dans la plupart des jeux, seul compte l'état courant du plateau. Savoir par quels coups on y est arrivé n'importe pas.

Dans ce cas, il est possible de tirer avantage de cette particularité et 'appliquer un unique score aux branches identiques. MCTS a vraiment été un algorithme important du point de vue de l'IA pour les jeux.

A une époque où les machines étaient incapables de jouer au go, il a permis de trouver un moyen autre que celui des fonctions d'évaluation et ainsi de progresser. Il a aussi donné un cadre dans lequel sont venus s'inscrire les algos d'apprentissage.

Voilà, je vais m'arrêter ici pour aujourd'hui. Si j'en ai l'occasion, je ferai une petite conclusion à cette série. Je vous tiendrai au courant !

Comprendre MCTS 4 - Monte Carlo Tree Search (2024)
Top Articles
Latest Posts
Article information

Author: Lakeisha Bayer VM

Last Updated:

Views: 6403

Rating: 4.9 / 5 (69 voted)

Reviews: 92% of readers found this page helpful

Author information

Name: Lakeisha Bayer VM

Birthday: 1997-10-17

Address: Suite 835 34136 Adrian Mountains, Floydton, UT 81036

Phone: +3571527672278

Job: Manufacturing Agent

Hobby: Skimboarding, Photography, Roller skating, Knife making, Paintball, Embroidery, Gunsmithing

Introduction: My name is Lakeisha Bayer VM, I am a brainy, kind, enchanting, healthy, lovely, clean, witty person who loves writing and wants to share my knowledge and understanding with you.