Recherche de graphes Monte-Carlo à partir des principes fondamentaux

• Monte-Carlo Graph Search (MCGS) est une approche qui applique MCTS à un graphe orienté plutôt qu’à un arbre, afin de partager les explorations redondantes dans les jeux où plusieurs suites de coups mènent au même état
• Si l’on transpose tels quels le nombre de visites N et la valeur moyenne Q du MCTS classique dans un DAG, le nombre de visites d’un enfant partagé peut se désaligner avec les estimations de politique et de valeur du parent, ce qui peut rendre l’algorithme non sain
• En voyant MCTS comme une optimisation de politique régularisée, la distribution des visites par action produite par PUCT s’interprète comme une politique a posteriori, et Q comme l’utilité espérée de cette politique
• Un MCGS correct suit séparément le nombre de visites d’arête N(n,a), indépendamment du nombre de visites des nœuds enfants, et recalcule Q comme une somme pondérée de U(n) et des Q des enfants afin de préserver le sens de la politique et de la valeur dans le graphe
• En pratique, plusieurs choix restent ouverts : Q obsolète, mises à jour incrémentales, poursuite ou non du playout depuis un enfant transposé, collisions de hachage et gestion des cycles dans le jeu ; KataGo utilise actuellement des mises à jour idempotentes

---

Les états transposés que la recherche arborescente manque

• Dans la recherche dans un arbre de jeu, il arrive que différentes suites de coups se transposent vers un même état
  • Aux échecs, 1. d4 d5 2. Nf3 et 1. Nf3 d5 2. d4 atteignent la même position
• Dans les jeux où les transpositions sont possibles, le nombre d’états redondants peut croître exponentiellement à mesure que la profondeur de recherche augmente ; il est donc préférable de partager les calculs pour un même état
• Une implémentation courante de MCTS traite le jeu comme un arbre de branchement et réexplore plusieurs instances d’une même position
  • Des optimisations de bas niveau comme la mise en cache des évaluations du réseau neuronal pour les positions répétées peuvent réduire le coût
  • Mais il reste un problème : si une tactique importante est découverte dans une instance et que son évaluation est corrigée, cela ne se propage pas aux autres instances
• En modélisant l’espace d’états comme un graphe orienté acyclique (DAG), lorsque plusieurs chemins atteignent le même état, cet état peut être représenté par un seul nœud
• On laisse largement de côté le traitement des jeux comportant de vrais cycles, pour se concentrer sur la manière dont MCTS devrait fonctionner dans un DAG

MCTS standard : un arbre qui accumule des statistiques d’exécution

• Le MCTS standard stocke la partie explorée du jeu sous forme d’arbre de nœuds en mémoire
• Chaque nœud suit généralement les valeurs suivantes
  • N : nombre de playouts ayant jusqu’ici traversé ce nœud ou s’y étant terminés
  • Q : moyenne courante des valeurs d’utilité échantillonnées par ces playouts
• Un playout se déroule dans l’ordre suivant
  • Il part de la racine et descend en choisissant l’action suivante selon une formule d’exploration
  • Lorsqu’il atteint un état encore inexploré, il ajoute un nouveau nœud
  • Il obtient l’utilité U du nouvel état. Dans l’exemple, il s’agit d’une requête au value head du réseau neuronal
  • En remontant l’arbre, il incrémente N pour chaque nœud et met à jour la moyenne Q
• Dans un MCTS de style AlphaZero, la sélection d’action utilise la formule PUCT
  • N(a) : nombre de fois où l’action a a été essayée ; dans un arbre, il est égal au N du nœud enfant pointé par cette action
  • Q(a) : utilité moyenne de l’action a, égale au Q du nœud enfant
  • PlayerToMove : indique si le joueur courant maximise ou minimise
  • P(a) : probabilité a priori, par exemple la prédiction de politique du réseau neuronal
  • c_PUCT : constante ajustable
• « PUCT » vient de la famille Predictor UCT/UCB, qui utilise une distribution a priori prédite ; la variante AlphaZero diffère de la forme d’origine par sa forme fonctionnelle
• Les MCTS modernes peuvent être déterministes lorsqu’ils utilisent une évaluation par réseau neuronal, mais le terme « Monte-Carlo » vient de l’ancienne méthode consistant à exécuter des rollouts aléatoires jusqu’au bout pour estimer l’utilité
• Après avoir répété les playouts jusqu’à épuisement du budget de calcul du tour, l’action finale choisie à la racine n’est pas l’enfant au meilleur Q, mais celui dont le nombre de visites N est le plus élevé
  • Un enfant avec un Q élevé mais un N faible peut être une erreur produite par du bruit dans une recherche peu profonde
• La distribution des visites à la racine, N(a) / ΣN(b), peut servir de cible d’apprentissage de politique dans la boucle d’entraînement d’AlphaZero

Les problèmes d’une application naïve à un DAG

• On peut conserver presque tel quel le code de MCTS arborescent et, si un nouvel état de jeu existe déjà dans nodes_by_hash, faire pointer vers le nœud existant
• Cette approche ne préserve pas l’hypothèse de l’arbre selon laquelle le nombre de visites d’un nœud enfant est égal au nombre de visites de l’action choisie depuis le parent
• Exemple de situation
  • Le nœud A préfère une action menant au nœud C, et le Q de A est principalement déterminé par environ 30 playouts ayant exploré C
  • C est aussi visité environ 40 fois par d’autres chemins de transposition
  • Ensuite, C est davantage visité via d’autres chemins de transposition, une tactique plus profonde est découverte, et l’estimation d’utilité de C passe de 0.39 → 0.51
• Comme le playout qui a mis à jour C n’est pas passé par A, le Q de A ne reflète pas la nouvelle évaluation de C
• Par la suite, même si A reçoit de nouveaux playouts, PUCT peut explorer d’autres actions moins visitées plutôt que C, dont le nombre de visites est élevé
  • C semble en effet « déjà suffisamment exploré »
  • Le Q de A peut alors au contraire baisser
• Une extension naïve aux graphes fait que, plus les chemins de transposition visitent souvent un coup préféré en amont, plus le parent explore d’autres coups, ce qui introduit un biais artificiel dans la moyenne des playouts
• Cela devient un algorithme non sain, au point qu’il n’est même pas clair qu’il converge vers le coup optimal avec une exploration infinie

Mettre à jour tous les parents ne résout pas le problème

• Lorsqu’un nœud est mis à jour par un playout, on pourrait aussi imaginer répercuter ce playout non seulement sur les parents effectivement traversés, mais sur tous les parents et ancêtres
• Dans le cas A-C précédent, cette méthode permettrait de mettre à jour l’utilité de A en même temps
• Mais dans un autre exemple, un parent D est pollué par les nombreuses visites d’un enfant transposé F qu’il ne préfère pas lui-même
  • Le meilleur enfant de D, E, a Q = 0.56, et le Q = 0.55 de D est cohérent avec cela
  • D n’a exploré F qu’une seule fois, mais F a déjà été visité 9 fois par d’autres chemins, pour un total de 10 visites
  • Si F est ensuite visité 100 fois de plus par d’autres chemins tout en conservant une faible utilité, la mise à jour de tous les parents peut faire chuter le Q de D jusqu’à 0.35
• Du point de vue de D, il ne souhaitait pas allouer autant de playouts à F ; mettre à jour tous les parents brise donc aussi le sens de la politique

Voir MCTS comme une optimisation de politique

• Monte-Carlo Tree Search as Regularized Policy Optimization interprète MCTS du point de vue du machine learning
• À chaque nœud, la distribution cumulée des visites sélectionnées itérativement par PUCT approxime et converge vers la solution du problème d’optimisation suivant

Valeur maximisée par π :
Σ π(a) Q(a) - λ_N D_KL(P || π)

• Signification des composants
  • Σ π(a) Q(a) : utilité espérée estimée lorsque l’on suit la politique π
  • D_KL(P || π) : divergence KL inverse mesurant l’écart entre la politique a priori P et la politique a posteriori π
  • λ_N : coefficient fixant la force du terme KL, qui diminue à mesure que le nombre de visites augmente
• La distribution des visites peut être vue comme une politique a posteriori qui part de la politique a priori P du réseau neuronal et s’améliore à mesure que davantage de visites accumulent des preuves sur l’utilité des actions
• MCTS s’interprète donc comme un algorithme qui effectue simultanément un petit apprentissage de politique en ligne à chaque nœud de l’arbre
• Cette perspective explique pourquoi la distribution des visites ressemble à la politique d’un agent fort et pourquoi elle est utilisée comme cible d’apprentissage de politique dans AlphaZero
• Il est aussi possible de calculer la solution exacte du problème d’optimisation et de l’utiliser comme politique, mais en pratique cela peut attribuer un poids élevé à des coups peu visités dont le Q semble élevé par hasard
  • En utilisant la distribution des visites comme politique a posteriori, un coup doit être effectivement beaucoup exploré pour obtenir un poids élevé, ce qui est plus robuste

Réinterprétation de Q : de la moyenne des playouts à l’espérance sous la politique

• Dans la définition standard, Q(n) pour le nœud n est la moyenne des utilités des playouts ayant visité n

Q(n) = (1 / N(n)) Σ U(p)

• On peut la réécrire en fonction des enfants comme suit

Q(n) = (1 / N(n)) ( U(n) + Σ N(c) Q(c) )

• Ici, U(n) est l’estimation brute d’utilité du réseau neuronal pour le nœud n, et N(c) Q(c) est la valeur de l’enfant pondérée par le nombre de visites de chaque enfant
• Q peut donc s’interpréter comme une moyenne pondérée par la distribution des visites des Q des enfants
• Si la distribution des visites est la politique a posteriori optimisée par MCTS, alors Q(n) est l’utilité espérée régularisée lorsque l’on suit cette politique a posteriori
• Dans cette interprétation, chaque nœud continue d’optimiser sa politique pour maximiser les Q rapportés par ses enfants, et met à jour son propre Q comme l’estimation courante de l’utilité espérée atteignable avec cette politique
• Si le Q des nœuds enfants converge vers la valeur optimale au sens de la théorie des jeux, alors la politique et le Q du parent convergent récursivement vers la valeur optimale

MCGS correct : séparer visites d’arêtes et visites d’enfants

• Le problème qui apparaît dans un graphe vient de l’hypothèse selon laquelle les visites des enfants d’un parent se produisent uniquement via ce parent
• Avec des chemins de transposition, le nombre de visites d’un nœud enfant peut diverger arbitrairement du nombre de visites que PUCT voulait allouer depuis ce parent
• La solution consiste à suivre séparément le nombre cumulé de fois où PUCT a choisi une action à un nœud donné
• Chaque nœud n suit les valeurs suivantes
  • N(n) : nombre total de visites de ce nœud
  • N(n,a) : nombre de fois où PUCT a choisi l’action a au nœud n, c’est-à-dire le nombre de visites de l’arête
  • Q(n) = (1 / N(n)) ( U(n) + Σ N(n,a) Q(n,a) )
• Ici, Q(n,a) est égal au Q(c) du nœud enfant c atteint en jouant l’action a
• Le calcul PUCT utilise lui aussi le nombre de visites de l’arête, et non celui de l’enfant

argmax_a PlayerToMove(n) * Q(n,a)
       + c_PUCT P(n,a) sqrt(Σ N(n,b)) / (1 + N(n,a))

• L’algorithme de base choisit les actions sur le chemin du playout, relie l’état transposé au nœud existant s’il existe déjà, puis, en remontant, incrémente le nombre de visites des arêtes et recalcule N et Q comme une fonction des valeurs des enfants
• Cette approche est similaire à haut niveau à Monte-Carlo Graph Search for AlphaZero de Czech, Korus et Kersting, mais elle est dérivée du point de vue de l’optimisation de politique plutôt que des statistiques d’exécution

Choix d’implémentation : Q obsolète et modes de mise à jour

• Le pseudocode présenté ne met à jour que les nœuds du chemin effectivement traversé par le playout
• Par conséquent, le Q des nœuds situés sur des chemins non traversés peut devenir un Q obsolète
• Cela reste néanmoins sain en théorie
  • Les formules d’exploration standard comme PUCT essaient toutes les actions une infinité de fois à la limite
  • Lorsqu’un nœud est revisité, il calcule directement le bon Q à partir des Q des enfants et du nombre de visites des arêtes à cet instant
  • Dans un DAG, cela peut converger à la limite vers la valeur optimale au sens de la théorie des jeux
• Un Q obsolète peut réduire l’efficacité de la recherche
  • On peut conserver des pointeurs vers les parents immédiats pour mettre aussi à jour leur Q
  • On peut mettre à jour tous les ancêtres dans l’ordre topologique afin d’éliminer les états obsolètes
  • On peut ne mettre à jour que le chemin du playout tout en laissant un thread parallèle distinct trouver et mettre à jour les nœuds obsolètes
• Le pseudocode utilise des mises à jour idempotentes
  • Quelles que soient les mises à jour intermédiaires précédentes, dès qu’un nœud est visité une fois, son N et son Q redeviennent corrects par rapport aux valeurs courantes de ses enfants
• Des mises à jour incrémentales sont aussi possibles, mais dans un graphe il est plus difficile de les rendre équivalentes, ou équivalentes à la limite
• Czech et al. adoptent une approche fondée sur les statistiques d’exécution et utilisent donc des formules plus incrémentales
  • Ils stockent non seulement le nombre de visites des arêtes, mais aussi le Q des arêtes
  • Ils prévoient un mécanisme par lequel les Q obsolètes rattrapent progressivement les valeurs à jour, ainsi qu’un hyperparamètre de tolérance d’erreur
• Le pseudocode présenté montre qu’il est possible de faire fonctionner MCGS sans nouveau paramètre de tolérance d’erreur ni stockage de Q d’arête
• KataGo utilise actuellement la formule idempotente

Continuer ou non le playout depuis un enfant transposé

• Dans le MCTS arborescent, l’augmentation des visites d’arête et celle des visites de l’enfant sont le même événement
• Dans un graphe, à cause des transpositions, le nœud enfant peut déjà avoir été visité beaucoup plus souvent que cette arête
• Dans ce cas, on peut considérer que le nœud enfant a déjà été suffisamment visité, arrêter le playout, n’incrémenter que la visite de l’arête, puis mettre à jour le parent et les ancêtres
• Raisons de préférer l’arrêt
  • Si les visites de l’arête sont faibles et celles de l’enfant élevées, la quantité d’information marginale apportée par une visite supplémentaire de cet enfant peut être faible
• Raisons de préférer la poursuite
  • Un nœud dont le nombre de visites enfant est supérieur au nombre de visites de l’arête est probablement un nœud vers lequel plusieurs parents se transposent ; comme il influence davantage de parents, il peut être important que son évaluation soit précise
• Ce choix reste du domaine expérimental
  • Une approche à seuil est aussi possible : arrêter seulement lorsque le nombre de visites de l’enfant dépasse suffisamment celui de l’arête
• Par défaut, KataGo interrompt le playout, mais propose des options de configuration pour continuer ou n’interrompre qu’une partie des cas de manière probabiliste
• Le pseudocode n’interrompt pas le playout ; si nécessaire, on peut ajouter une vérification d’une ligne avec la condition child.N <= edge_visits

Hachage, nœuds terminaux et cycles réels dans les jeux

• Dans le pseudocode, les nœuds terminaux du jeu sont recalculés avec N = 1, U = Q = utilité du résultat de la partie, indépendamment du nombre de visites
  • Comme le nombre de visites de l’arête correspondante chez le parent augmente normalement, cette approche est également possible
  • Si le résultat de la partie est probabiliste et que l’utilité espérée ne peut pas être calculée directement, il peut être important d’incrémenter N à chaque visite d’un nœud terminal et de moyenner les résultats échantillonnés
• Il est aussi possible de traiter plus largement l’utilité des fins de partie afin de propager plus rapidement des valeurs prouvables vers le haut du graphe
  • Comme MCTS/MCGS classique ne dispose pas d’un mécanisme reconnaissant les valeurs d’utilité certaines, lorsque les états terminaux sont importants, il ne converge pas vers la valeur optimale aussi économiquement qu’une recherche classique de type alpha-beta
• Pour trouver les transpositions, on suppose un hachage unique de l’état du jeu
  • Construire un vrai hachage sans collision pour des états de jeu complexes peut être délicat et coûteux
  • Un hachage de Zobrist suffisamment grand, sur 128 ou 192 bits, suffit généralement en pratique à rendre les collisions pratiquement impossibles, sauf pour des états construits de manière adversariale
  • On peut ajouter une détection de cycles pour éviter une récursion infinie si une collision de hachage crée un cycle
• Le traitement des cycles issus des règles réelles des jeux, comme le superko au go ou la triple répétition aux échecs, n’est pas abordé en détail
• L’annexe du 10/03/2024 fournit un lien Google Docs contenant des réflexions plus approximatives sur la gestion des répétitions et des cycles ; des expérimentations avec des heuristiques propres à chaque jeu peuvent être nécessaires
• Dans sa gestion du go, KataGo exploite un théorème propre au go selon lequel, pour revenir à la position d’origine après certains coups, il faut au moins S + E - 1 coups, ce qui permet de limiter de manière stable le partage de nœuds dans les situations liées aux cycles

[GN⁺]

Avis sur Hacker News

• Je pense que ce type de recherche dans les graphes est nécessaire pour faire progresser le raisonnement en IA. Avec de simples LLM, l’échec est très probable.
  Le lien contient beaucoup de bonnes références, dont le hachage de Zobrist pour les tables de jeu https://en.wikipedia.org/wiki/Zobrist_hashing
  Pour éviter que le coût de calcul de la recherche dans les graphes n’explose, il faut trouver un bon hachage adapté aux descriptions d’état fondées sur le langage.
  À propos de la recherche dans les arbres, Thinking Fast and Slow : https://arxiv.org/abs/1705.08439 et Teaching Large Language Models to Reason with Reinforcement Learning, qui compare une approche MCTS aux autres stratégies actuelles d’apprentissage par renforcement : https://arxiv.org/abs/2403.04642, valent aussi la lecture.

  • Ça me paraît de trop bas niveau.
    Une étape suivante pourrait consister à apprendre conjointement la représentation d’état et l’algorithme de recherche. L’algorithme de recherche parcourrait une représentation d’état produite par un réseau de neurones, à partir de laquelle il peut obtenir un coût.
    https://sites.google.com/view/genie-2024/
    Genie de DeepMind est un bon exemple de modélisation d’états discrets. Le réseau de neurones apprend une représentation très complexe, incluant la détection de collisions et les actions. Au lieu de décoder cet état en pixels, on pourrait probablement effectuer la recherche directement dessus.
    Bien sûr, cette architecture pourrait être assez différente en pratique.
  • C’est très simplifié, mais une approche qui me semble mériter d’être explorée serait la suivante :
    prendre un ensemble d’arguments logiques, trouver une manière d’attribuer un hash à chaque argument, puis représenter ces hashes d’arguments sous forme d’arbre de Merkle empilé selon les premiers principes.
    Si un argument est réfuté avec succès, son hash change, et les hashes des sous-arguments sont eux aussi invalidés.
  • Je me demande s’il ne serait pas possible de combiner les deux d’une manière ou d’une autre. Il est difficile de croire que le cerveau n’utilise qu’une seule technique pour tout ; il semble plus probable qu’il dispose de plusieurs outils, avec au-dessus un sélecteur qui décide quel outil utiliser et quand.

• En voyant l’auteur dans l’URL HN, j’ai immédiatement reconnu le génie qui a créé KataGo : https://github.com/lightvector/KataGo
  Ses publications sur https://www.reddit.com/r/cbaduk/ sont elles aussi constamment excellentes.

  • L’URL se trouve littéralement dans le dépôt KataGo.

• Je n’ai pas une énorme expérience des échecs, mais je suis sceptique face à l’idée que les mêmes positions se répètent assez souvent dans l’arbre de recherche pour que ce soit important. J’aimerais voir des mesures réelles avec Leela Zero.
  Si l’on inclut dans l’état la triple répétition et la règle des 50 coups, les possibilités de répétition devraient être bien plus faibles ; et même sans prendre cela en compte, j’ai des doutes.

  • Au go, les ko sont très fréquents. Répéter exactement la position sur le plateau est interdit, mais si la recherche dans l’arbre n’évalue pas correctement les positions de ko, on peut facilement créer des situations où l’IA joue de mauvais coups.

• Je trouve étrange le passage disant que, malgré le nom « Monte-Carlo Tree Search », il n’y a absolument rien de Monte-Carlo dans l’algorithme ci-dessus et qu’il est entièrement déterministe. Je pensais que les implémentations habituelles de MCTS étaient déterministes, mais qu’il y avait de l’aléatoire dans l’échantillonnage.

  • À l’origine, MCTS comportait bien de l’aléatoire. L’article semble aussi le mentionner : il s’agissait de réaliser des playouts pour évaluer une position à la fin.
    Dans les projets similaires actuels, cela a été remplacé par une évaluation de meilleure qualité via réseau de neurones. Jouer des coups aléatoires pour voir qui gagne n’est pas très bon, mais c’était la meilleure stratégie connue à l’époque.
    Au final, la partie Monte-Carlo n’était déjà pas un élément essentiel de ce qu’on appelle encore MCTS aujourd’hui ; c’était plutôt un pis-aller. Le nom est donc un peu malheureux.
  • À strictement parler, c’est un autre algorithme sous la même appellation « monte carlo ».
    Ce qui est intéressant, c’est que la plupart des méthodes de Monte-Carlo s’appuient sur des générateurs pseudo-aléatoires plutôt que sur de vrais générateurs de nombres aléatoires ; avec la même graine et la même entrée, elles donnent donc toujours le même résultat, de manière déterministe.
    Cet algorithme interroge un réseau de neurones au lieu d’utiliser un générateur pseudo-aléatoire classique et des heuristiques distinctes. Le réseau de neurones est une heuristique sur un immense espace de recherche ; selon son apprentissage, il fonctionne comme un très mauvais générateur pseudo-aléatoire fortement biaisé vers certains résultats, si bien qu’il finit par ressembler à un générateur pseudo-aléatoire avec heuristique.
    Le point important est qu’il s’agit d’une spécialisation de MCTS, et que techniquement elle ne convient donc pas à tous les cas d’usage.
  • S’il y a de l’aléatoire, je me demande s’il y a convergence, et quelle quantité de ressources-temps est nécessaire. Cela peut aussi varier selon qu’on parle de CPU, RAM, GPU, TPU ou QPU.

• Quand j’ai étudié MCTS, l’article mentionné dans le billet était complètement passé sous mon radar. Ce serait assez amusant d’essayer moi-même cette modification à la prochaine occasion.

• Une brève introduction serait appréciable.

  • Quand on crée une IA pour jouer à des jeux — et, par analogie large, c’est vrai pour toutes les IA — l’une des techniques les plus prometteuses est la recherche dans les arbres. Elle consiste à classer le coup actuel à partir des coups suivants.
    Dans les jeux où l’on peut atteindre le même état par plusieurs chemins, on peut gaspiller beaucoup de mémoire en enregistrant à répétition le même nœud d’état dans différentes branches.
    Cet article examine bien l’approche de la recherche dans les graphes. En substance, elle consiste à effectuer un calcul supplémentaire pour hacher l’état du jeu afin de vérifier si le nœud a déjà été visité, et à économiser de la mémoire en contrepartie.
    Comme il n’est plus nécessaire d’enregistrer à nouveau un nœud déjà vu, l’arbre sans cycles devient un graphe orienté acyclique.
    Pour cette raison, il faut ajuster un peu la recherche dans l’arbre afin d’obtenir des résultats corrects. En particulier, l’unité d’optimisation doit être davantage l’arête — c’est-à-dire l’action ou le coup — que le sommet, c’est-à-dire l’état.
    C’est un essai technique bien écrit, dans un style de programmation lettrée, par quelqu’un qui comprend bien le sujet.