Principes fondamentaux de l’exploration de graphes Monte-Carlo
- La recherche arborescente Monte-Carlo (MCTS) peut être appliquée à un graphe orienté plutôt qu’à un arbre sous la forme de l’« exploration de graphes Monte-Carlo » (« MCGS »), parfois considérée comme délicate à implémenter.
- Comme les références académiques existantes suivent l’explication « standard » de MCTS pour les arbres, il est difficile de comprendre conceptuellement sa généralisation aux graphes.
- Ce document propose une explication jugée plus intuitive, essentiellement équivalente mais plus propre, et dérive à partir des principes fondamentaux pourquoi l’exploration sur graphe doit fonctionner de cette manière.
Introduction / contexte
- Dans la recherche dans les arbres de jeu ou dans d’autres applications de recherche sur arbre, il est possible de trouver plusieurs séquences de coups ou d’actions menant au même état.
- Par exemple, aux échecs,
1. d4 d5 2. Nf3 mène à la même position que 1. Nf3 d5 2. d4.
- Quand ce type de situation est possible dans un jeu, le nombre de cas possibles augmente exponentiellement avec la profondeur de recherche, ce qui rend la recherche profonde plus coûteuse que nécessaire.
- Idéalement, on voudrait que ces branches de recherche partagent leurs calculs.
- Cependant, les implémentations standard de MCTS traitent le jeu comme un arbre de branchement et réexplorent inefficacement les positions dupliquées dans l’arbre.
Explication courante de MCTS — un arbre de statistiques d’exécution
- MCTS est souvent décrit comme un algorithme qui suit les statistiques d’exécution des play-outs traversant les nœuds d’un arbre.
- Chaque nœud représente un état unique du jeu et suit le nombre de visites (N) ainsi que la moyenne cumulée (Q) des valeurs d’utilité échantillonnées par les play-outs.
- Une itération unique, ou play-out, de MCTS consiste à descendre dans l’arbre en échantillonnant l’action suivante à explorer, à étendre l’arbre lorsqu’un nouvel état est atteint, à estimer l’utilité U du nouvel état, puis à remonter dans l’arbre en incrémentant N à chaque nœud et en mettant à jour la moyenne Q avec la nouvelle utilité U échantillonnée.
Qu’est-ce qui ne va pas sur un graphe ?
- Si l’algorithme ci-dessus est appliqué tel quel à un graphe orienté acyclique plutôt qu’à un arbre, il peut devenir incorrect.
- Cela vient du fait que MCTS est généralement expliqué en termes de statistiques d’exécution des play-outs comme une extension de méthodes basées sur les bandits manchots multi-bras.
- Czech, Korus et Kersting ont résolu ce problème et sont parvenus à un algorithme valide, mais il existe une autre manière d’aborder MCTS, du point de vue de l’apprentissage de politique en ligne.
- Dans cette explication alternative, la généralisation aux graphes apparaît de façon relativement naturelle.
Revoir MCTS comme une optimisation de politique régularisée
- Lorsque MCTS met à jour les statistiques à différents nœuds, il exécute en réalité une forme d’apprentissage de politique en ligne.
- La distribution des visites de MCTS représente approximativement une politique « a posteriori » qui améliore progressivement la politique a priori P issue du réseau neuronal afin de maximiser l’utilité espérée.
Réaliser correctement une exploration de graphes Monte-Carlo
- Tous les problèmes qui apparaissent lorsqu’on étend MCTS aux graphes proviennent de l’hypothèse selon laquelle les visites d’un nœud enfant ne viennent que des nœuds parents.
- La théorie garantit que les comptes d’actions cumulés sélectionnés par PUCT fournissent une politique a posteriori qui approxime la politique optimisée π, il faut donc suivre cela.
- En utilisant l’interprétation selon laquelle la valeur Q rapportée par un nœud est la valeur attendue de la politique a posteriori, on peut appliquer la formule récursive de Q sans avoir à traiter la manière de calculer les play-outs individuels.
Discussion des choix d’implémentation
- L’algorithme présenté dans ce document est très proche de celui de Czech, Korus et Kersting, mais comporte quelques choix d’implémentation et quelques différences mineures.
- Il existe plusieurs façons de privilégier la simplicité d’implémentation, par exemple des stratégies pour réduire l’« ancienneté » des valeurs Q, ou l’utilisation de mises à jour identiques plutôt qu’incrémentales.
Avis de GN⁺
- Cet article peut intéresser les personnes qui s’intéressent à l’intelligence artificielle et à la théorie des jeux en présentant la complexité de l’exploration de graphes Monte-Carlo (MCGS) et une nouvelle approche pour la comprendre.
- Des algorithmes comme MCTS jouent un rôle important dans des jeux de stratégie complexes comme les échecs ou le go, et contribuent au développement de l’IA pour ces jeux.
- Cependant, le contenu abordé dans cet article peut être assez difficile pour un ingénieur logiciel débutant et nécessite des connaissances théoriques préalables.
- Parmi les points à considérer lors de l’implémentation de MCGS figure la manière d’équilibrer l’efficacité et la précision de l’algorithme, ce qui peut avoir un impact majeur sur les performances dans un environnement de jeu réel.
- Parmi d’autres projets ou produits offrant des fonctions similaires figure AlphaZero de DeepMind, qui a atteint un niveau surpassant les meilleurs humains aux échecs, au go et au shogi.
1 commentaires
Commentaires sur Hacker News
L’exploration de graphes est nécessaire aux progrès du raisonnement en IA, et de simples LLM échoueront. Le lien contient de nombreuses bonnes références, notamment sur le hachage de Zobrist pour les tables de jeu. Il faut trouver un bon hachage pour les descriptions d’état basées sur le langage afin que l’exploration de graphes n’explose pas en coût de calcul. Parmi les bonnes lectures sur la recherche dans les arbres, on trouve Thinking Fast and Slow et Teaching Large Language Models to Reason with Reinforcement Learning, qui comparent l’approche MCTS à d’autres stratégies de RL actuelles.
J’ai immédiatement reconnu le développeur génial de KataGo à l’URL HN. Ses publications Reddit sous cbaduk sont constamment excellentes.
À propos du nom « Monte-Carlo Tree Search », les lecteurs doivent remarquer qu’il n’y a rien de « Monte-Carlo » dans l’algorithme mentionné, et qu’il est entièrement déterministe. Il est étrange que MCTS soit généralement implémenté de manière déterministe. Je supposais qu’il y avait de l’aléatoire dans l’échantillonnage.
L’article mentionné était complètement passé sous mon radar lorsque j’étudiais MCTS. Ce sera très amusant d’essayer cette modification à la prochaine occasion.
Connaissances de base :