🤖 machine learning

Monte Carlo Permutation Search

Cet article présente la recherche par permutation de Monte Carlo (MCPS), un algorithme MCTS polyvalent qui surpasse l'algorithme GRAVE dans des jeux comme le Hex et le Go en intégrant des statistiques de déroulement à l'échelle du chemin dans le terme d'exploration et en dérivant une nouvelle formule de pondération qui élimine le besoin du paramètre de biais de GRAVE.

Auteurs originaux : Tristan Cazenave

Publié 2026-05-27

📖 6 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Tristan Cazenave

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous essayez de résoudre un puzzle complexe, comme un jeu de Go ou de Hex, mais que vous ne disposez ni d'un supercalculateur ni d'une intelligence artificielle entraînée pour vous indiquer le meilleur coup. À la place, vous devez vous fier à une méthode de « devinettes et vérifications » en simulant mentalement des milliers de scénarios futurs aléatoires. C'est ainsi que fonctionne un programme informatique appelé Recherche Arborescente Monte Carlo (MCTS).

Pendant longtemps, la meilleure façon d'effectuer ces devinettes était un algorithme appelé GRAVE. Il était bon pour regarder le passé afin de prédire l'avenir, mais l'auteur de cet article, Tristan Cazenave, s'est dit : « Nous pouvons faire mieux. »

Il a créé un nouvel algorithme appelé MCPS (Recherche de Permutation Monte Carlo). Voici comment il fonctionne, expliqué simplement :

Les Trois Façons de Regarder le Passé

Pour décider quel coup jouer ensuite, MCPS examine son historique de parties aléatoires (appelées « simulations ») de trois manières différentes. Imaginez ces trois façons comme trois objectifs différents sur un appareil photo :

L'Objectif « Chemin Exact » (Vue Standard) :
Il examine les parties où le joueur a effectué la même séquence exacte de coups pour arriver à la position actuelle, puis a joué le coup spécifique que nous testons.
- Analogie : « Je suis descendu dans la rue Principale, j'ai tourné à gauche, puis j'ai acheté un café. Comment cela s'est-il passé ? »
L'Objectif « L'Ordre n'Importe Pas » (La Mise à Niveau de GRAVE) :
Il examine les parties où le joueur a effectué les mêmes coups pour arriver à la position, mais où l'ordre était légèrement différent, et où le coup spécifique que nous testons est apparu plus tard dans la partie.
- Analogie : « J'ai acheté un café, puis je suis descendu dans la rue Principale, puis j'ai tourné à gauche. Ce sont les mêmes ingrédients, juste un ordre de recette différent. Est-ce que cela a toujours bon goût ? »
- Pourquoi cela aide : Dans de nombreux jeux, l'ordre dans lequel vous placez vos pièces ne change pas l'état final du plateau. Ainsi, cet objectif permet à l'ordinateur d'apprendre à partir de plus de parties, pas seulement de celles qui correspondaient à l'ordre exact.
L'Objectif « Permutation » (Le Secret du MCPS) :
C'est la nouvelle addition. Il examine n'importe quelle partie où le joueur a utilisé le même ensemble exact de coups (le chemin vers la position actuelle + le nouveau coup), indépendamment de l'ordre dans lequel ils se sont produits.
- Analogie : « J'ai utilisé un marteau, un tournevis et un clou pour construire une étagère. Peu importe si j'ai martelé en premier ou vissé en premier ; si j'ai utilisé ces trois outils, l'étagère a été construite. Comment cette combinaison s'est-elle déroulée ? »
- Le Problème : Dans certains jeux (comme AtariGo), l'ordre importe car la partie peut se terminer prématurément (comme lors de la capture d'une pierre). MCPS gère cela en étant intelligent sur la façon dont il regroupe ces coups.

La « Formule Magique »

L'article explique que MCPS ne se contente pas de choisir l'une de ces vues ; il les mélange. L'auteur a fait des calculs mathématiques pour déterminer la manière parfaite de combiner ces trois sources d'informations.

Imaginez que vous préparez un smoothie. Vous avez trois fruits (les trois statistiques). GRAVE utilisait une recette fixe qui avait parfois un goût étrange. MCPS utilise une recette mathématiquement parfaite qui ajuste automatiquement les quantités en fonction de la quantité de données dont il dispose pour chaque fruit. La meilleure partie ? Il n'a pas besoin d'un « test de dégustation » (un humain réglant un paramètre de biais) pour que cela fonctionne ; les mathématiques le font automatiquement.

Comment il a Performé dans le Monde Réel

L'auteur a testé MCPS contre l'ancien champion (GRAVE) sur cinq types de jeux différents :

Hex (Le Match Parfait) : Dans ce jeu, l'ordre des coups ne change jamais le plateau final. MCPS a été un grand gagnant ici, en particulier sur les grands plateaux. C'était comme avoir une carte montrant tous les chemins possibles, pas seulement celui que vous avez emprunté.
Go (Le Penseur Profond) : Sur les petits plateaux, ils étaient à peu près égaux. Mais sur les grands plateaux, à mesure que l'ordinateur avait plus de temps pour réfléchir, MCPS prenait l'avantage. Il était meilleur pour utiliser ce temps supplémentaire pour creuser plus profondément dans les lignes de jeu les plus prometteuses, tandis que l'ancienne méthode restait bloquée à explorer des options superficielles.
AtariGo (Le Finisseur Rapide) : C'est un jeu où la première capture gagne. Ici, l'ordre importe. Étonnamment, MCPS a quand même gagné, mais son avantage était le plus grand sur les petits plateaux où la partie se termine rapidement. Sur les grands plateaux, la partie devient trop longue pour que l'astuce « l'ordre n'importe pas » aide autant.
NoGo (Le Gagnant Constant) : C'est un jeu où vous perdez si vous capturez. MCPS a gagné presque partout, battant constamment l'ancienne méthode avec une marge solide.
Wargame (Le Démon de la Vitesse) : Dans ce jeu de stratégie personnalisé, MCPS n'a pas seulement joué mieux ; il a joué plus vite. Il a simulé des parties qui se terminaient plus tôt et a trouvé la stratégie gagnante plus rapidement, lui permettant d'exécuter plus de simulations dans le même laps de temps.

La Conclusion

L'article affirme que MCPS est une façon plus intelligente et plus efficace pour les ordinateurs de jouer aux jeux sans avoir besoin d'apprentissage profond ni d'entraînement massif.

Il fonctionne en réalisant que dans de nombreux jeux, l'ensemble des coups que vous faites est plus important que l'ordre dans lequel vous les faites. En comptant toutes les fois où un ensemble spécifique de coups est apparu dans des parties aléatoires, MCPS construit une meilleure « intuition » sur quels coups sont bons. C'est comme un détective qui réalise que même si les suspects sont arrivés dans un ordre différent, le fait qu'ils étaient tous sur les lieux est la véritable indice.

Le résultat est un outil polyvalent qui bat la meilleure méthode précédente dans presque tous les scénarios testés, en faisant une nouvelle norme puissante pour les IA de jeux lorsque vous ne disposez pas d'un supercalculateur à votre disposition.

Résumé Technique : Recherche par Permutation Monte Carlo (MCPS)

Énoncé du Problème

La Recherche Arbre Monte Carlo (MCTS) est un algorithme dominant pour la prise de décision et le jeu, en particulier dans les domaines où l'apprentissage par renforcement profond est irréalisable en raison d'un manque de données d'entraînement ou de contraintes computationnelles (par exemple, le Jeu Généralisé). Bien que des variantes de MCTS comme GRAVE (Generalized RAVE) aient amélioré l'UCT standard en exploitant les statistiques des nœuds ancêtres et les heuristiques All-Moves-As-First (AMAF), elles reposent sur deux sources principales d'information : les statistiques des parties simulées (playouts) commençant par un coup spécifique et les statistiques des parties simulées où le coup apparaît plus tard.

L'article identifie une limite dans les approches existantes : elles n'exploitent pas pleinement l'information statistique contenue dans les parties simulées où la séquence de coups menant à un nœud apparaît dans un ordre différent. Dans les jeux à propriétés commutatives (comme Hex), toute permutation de coups conduit au même état. Dans les jeux non commutatifs (comme AtariGo), les permutations peuvent conduire à des états différents, pourtant l'article émet l'hypothèse que la valeur statistique des coups reste informative. L'objectif est de développer un algorithme MCTS à usage général qui améliore GRAVE sans nécessiter de réglage spécifique au problème, d'entraînement de modèle ou de paramètres d'hyperbiais.

Méthodologie

Concept de base : Recherche par Permutation Monte Carlo (MCPS)

MCPS introduit une troisième source de statistiques dans le processus d'évaluation des nœuds. Pour évaluer une action $a$ à un nœud $s$ atteint par un chemin $(a_0, a_1, \dots, a_d)$ , MCPS agrège les données de trois ensembles distincts de parties simulées :

Statistiques Directes ( $Q$ ) : Parties simulées commençant par le chemin vers $s$ suivi immédiatement de l'action $a$ .
Statistiques AMAF ( $\tilde{Q}$ ) : Parties simulées commençant par le chemin vers $s$ , où l'action $a$ apparaît plus tard dans la séquence (approche GRAVE standard).
Statistiques de Permutation ( $\hat{Q}$ ) : Parties simulées contenant l'ensemble des coups $\{a_0, a_1, \dots, a_d, a\}$ dans n'importe quel ordre et à n'importe quelle position.

Déduction Mathématique des Poids

L'article fournit une déduction mathématique pour combiner ces trois estimateurs. En supposant que les statistiques sont indépendantes, les auteurs dérivent les poids qui minimisent la variance de l'estimateur combiné.
Soient $n$ , $\tilde{n}$ et $\hat{n}$ les comptes d'échantillons pour les trois statistiques. Les poids optimaux ( $\beta, \tilde{\beta}, \hat{\beta}$ ) sont proportionnels à leurs comptes d'échantillons :
$\beta = \frac{n}{n + \tilde{n} + \hat{n}}, \quad \tilde{\beta} = \frac{\tilde{n}}{n + \tilde{n} + \hat{n}}, \quad \hat{\beta} = \frac{\hat{n}}{n + \tilde{n} + \hat{n}}$
Cette combinaison convexe élimine le besoin du paramètre d'hyperbiais utilisé dans l'algorithme GRAVE, fournissant un schéma de pondération sans paramètre.

Implémentation Algorithmique

Sélection : La valeur d'un coup est calculée comme la moyenne pondérée des trois estimateurs.
Calcul des Statistiques de Permutation : Pour calculer efficacement $\hat{Q}$ , l'algorithme utilise une fenêtre glissante de parties simulées récentes (par défaut $W=10\,000$ ) représentées sous forme de bitsets. Pour un nœud $s$ , l'algorithme intersecte les bitsets de tous les coups sur le chemin vers $s$ pour identifier les parties simulées contenant la séquence complète du chemin. Il intersecte ensuite ce résultat avec le bitset du coup candidat $a$ pour isoler les parties simulées pertinentes. Cela est effectué en utilisant des opérations sur mots de 64 bits (POPCOUNT et balayage de bits) pour l'efficacité.
Gel : Une fois qu'un nœud accumule un nombre seuil de visites ( $\rho=30$ ), ses statistiques de permutation sont calculées et « gelées ». Ce nœud agit alors comme référence pour tout son sous-arbre, permettant aux descendants d'hériter de ces statistiques sans les recalculer.
Codage des Coups : Pour permettre le transfert de connaissances entre différentes positions de plateau, les coups sont mappés à des codes entiers basés sur des caractéristiques pertinentes pour le jeu (par exemple, joueur, cellule de destination, déclencheur de combat) plutôt que sur des coordonnées exactes.

Contributions Clés

Extension Algorithmique : La proposition de MCPS, qui intègre les statistiques de permutation dans la règle de sélection MCTS, étendant l'algorithme GRAVE.
Amélioration Théorique : Une dérivation de formules de pondération qui minimisent la variance de l'estimateur sous des hypothèses d'indépendance, éliminant le besoin du paramètre d'hyperbiais GRAVE.
Implémentation Efficace : Une méthode pour calculer les statistiques de permutation en utilisant des bitsets et des fenêtres glissantes, permettant à l'algorithme de gérer l'explosion combinatoire des ordres de coups efficacement.
Applicabilité Générale : Démonstration que l'algorithme fonctionne sur divers types de jeux (commutatifs et non commutatifs) sans réglage spécifique des paramètres.

Résultats Expérimentaux

Les auteurs ont testé MCPS contre GRAVE sur cinq jeux : Hex, Go, AtariGo, NoGo et un jeu de guerre asymétrique personnalisé. Dans tous les cas, 800 parties ont été jouées par configuration (400 avec chaque algorithme jouant en premier) sous des budgets de temps identiques.

Hex : MCPS surpasse GRAVE sur les plateaux $7\times7$ et plus grands, avec des taux de victoire atteignant 70–76 % sur les grands plateaux. Sur $5\times5$ , la surcharge des bitsets désavantage légèrement MCPS. L'avantage croît avec la taille du plateau car MCPS construit des arbres plus profonds.
Go : MCPS surpasse GRAVE sur les plateaux $7\times7$ et plus grands. Notamment, sur les grands plateaux ( $13\times13$ , $15\times15$ ), l'écart de taux de victoire s'élargit considérablement à mesure que le budget de temps augmente (jusqu'à 63,75 % à 2 s). MCPS construit systématiquement des arbres plus profonds avec plus de temps, tandis que la profondeur de l'arbre de GRAVE stagne souvent ou diminue.
AtariGo : MCPS surpasse GRAVE dans toutes les configurations, avec les gains les plus importants sur les petits plateaux ( $5\times5$ , $7\times7$ ). L'avantage diminue sur les grands plateaux car le jeu se termine souvent avant que la recherche n'atteigne l'état terminal, limitant le bénéfice des arbres plus profonds.
NoGo : MCPS montre l'amélioration la plus uniforme, surpassant GRAVE dans chaque cellule avec des taux de victoire entre 57 % et 69 %. L'amélioration est constante quelle que soit la taille du plateau et le budget de temps.
Jeu de Guerre : MCPS surpasse GRAVE sur les plateaux $9\times9$ et plus grands. L'algorithme s'exécute 15–33 % plus vite (plus de parties simulées par seconde) en raison de longueurs de simulation plus courtes et converge vers des états de jeu décisifs plus rapidement.

Importance et Revendications

L'article affirme que MCPS représente une amélioration significative par rapport à GRAVE pour les applications MCTS à usage général, en particulier dans les scénarios où l'apprentissage profond n'est pas une option. Le mécanisme principal de succès est la « règle de sélection mieux informée », qui permet à l'algorithme de :

Construire des arbres de recherche plus profonds.
Réduire le travail de simulation par itération (dans certains jeux).
Atteindre plus près des états terminaux (dans des jeux comme AtariGo).
Convertir le temps de calcul supplémentaire en une exploration plus profonde des lignes prometteuses (observé dans le Go).

Les auteurs soulignent que l'algorithme est à usage général, ne nécessitant aucune modification ou entraînement spécifique au problème. Les résultats suggèrent que le bénéfice de MCPS est plus prononcé lorsque l'avantage de profondeur résultant tombe dans l'horizon de décision pertinent du jeu. L'article conclut que le concept de combinaison de trois sources de statistiques est réutilisable pour d'autres types de statistiques au-delà des permutations.