🤖 machine learning

Monte Carlo Permutation Search

Dit artikel introduceert Monte Carlo Permutation Search (MCPS), een algemene MCTS-algoritme dat de GRAVE-algoritme overtreft in spellen zoals Hex en Go door padbrede playout-statistieken op te nemen in de exploratieterm en een nieuwe wegingsformule af te leiden die de noodzaak van GRAVE's bias-hyperparameter elimineert.

Oorspronkelijke auteurs: Tristan Cazenave

Gepubliceerd 2026-05-27

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Tristan Cazenave

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je probeert een complex puzzel op te lossen, zoals een spel van Go of Hex, maar je hebt geen supercomputer of een getrainde AI die je de beste zet vertelt. In plaats daarvan moet je vertrouwen op "gokken en controleren" door duizenden willekeurige toekomstige scenario's in je hoofd uit te spelen. Zo werkt een computerprogramma genaamd Monte Carlo Tree Search (MCTS).

Lange tijd was de beste manier om dit gokken te doen een algoritme genaamd GRAVE. Het was goed in het kijken naar het verleden om de toekomst te voorspellen, maar de auteur van dit artikel, Tristan Cazenave, dacht: "We kunnen het beter doen."

Hij bedacht een nieuw algoritme genaamd MCPS (Monte Carlo Permutation Search). Hier is hoe het werkt, eenvoudig uitgelegd:

De Drie Manieren om naar het Verleden te Kijken

Om te beslissen welke zet als volgende moet worden gedaan, bekijkt MCPS zijn geschiedenis van willekeurige spellen (zogenaamde "playouts") op drie verschillende manieren. Denk hierbij aan drie verschillende lenzen op een camera:

De "Exacte Pad" Lens (Standaard Weergave):
Dit kijkt naar spellen waarbij de speler precies dezelfde reeks zetten heeft gedaan om op de huidige plek te komen, en vervolgens de specifieke zet heeft gedaan die we testen.
- Vergelijking: "Ik ben de Main Street afgelopen, linksaf gekeerd en toen koffie gekocht. Hoe is dat gegaan?"
De "Volgorde Maakt Niet Uit" Lens (De GRAVE Upgrade):
Dit kijkt naar spellen waarbij de speler dezelfde zetten heeft gedaan om op de plek te komen, maar de volgorde was iets anders, en de specifieke zet die we testen later in het spel verscheen.
- Vergelijking: "Ik heb koffie gekocht, toen de Main Street afgelopen, en toen linksaf gekeerd. Het zijn dezelfde ingrediënten, gewoon een andere volgorde van het recept. Smakten ze nog steeds goed?"
- Waarom het helpt: In veel spellen verandert de volgorde waarin je je stukken plaatst de eindstand van het bord niet. Deze lens laat de computer dus leren van meer spellen, niet alleen van diegene die exact overeenkwamen met de volgorde.
De "Permutatie" Lens (Het Nieuwe MCPS Geheime Ingrediënt):
Dit is de nieuwe toevoeging. Het kijkt naar elk spel waarbij de speler exact dezelfde set zetten gebruikte (het pad naar de huidige plek + de nieuwe zet), ongeacht de volgorde waarin ze plaatsvonden.
- Vergelijking: "Ik heb een hamer, een schroevendraaier en een spijker gebruikt om een plank te bouwen. Het maakt niet uit of ik eerst heb gehamerd of eerst heeft geschroefd; als ik die drie gereedschappen gebruikte, is de plank gebouwd. Hoe is die combinatie uitgekomen?"
- De Haken en Ogen: In sommige spellen (zoals AtariGo) maakt de volgorde wel uit omdat het spel vroeg kan eindigen (zoals het vangen van een steen). MCPS lost dit op door slim om te gaan met het groeperen van deze zetten.

De "Magische Formule"

Het artikel legt uit dat MCPS niet zomaar één van deze weergaven kiest; het mixt ze samen. De auteur heeft wat wiskunde gedaan om de perfecte manier te vinden om deze drie bronnen van informatie te mengen.

Denk hierbij aan het maken van een smoothie. Je hebt drie soorten fruit (de drie statistieken). GRAVE gebruikte een vast recept dat soms niet lekker smaakte. MCPS gebruikt een wiskundig perfect recept dat automatisch de hoeveelheden aanpast op basis van hoeveel data het heeft voor elk fruit. Het beste deel? Het heeft geen "proeftest" (een mens die een bias-parameter instelt) nodig om het goed te krijgen; de wiskunde doet dit automatisch.

Hoe Het Werelddeed in de Praktijk

De auteur testte MCPS tegen de oude kampioen (GRAVE) op vijf verschillende soorten spellen:

Hex (De Perfecte Match): In dit spel verandert de volgorde van zetten nooit de eindstand van het bord. MCPS was hier een grote winnaar, vooral op grotere borden. Het was alsof je een kaart had die elke mogelijke route liet zien, niet alleen de ene die je nam.
Go (De Diepdenker): Op kleine borden waren ze ongeveer gelijk. Maar op grote borden, naarmate de computer meer tijd kreeg om na te denken, trok MCPS aan de leiding. Het was beter in het gebruiken van die extra tijd om dieper te graven in de meest veelbelovende speelroutes, terwijl de oude methode vastbleef in het verkennen van ondiepe opties.
AtariGo (De Snelle Afbouwer): Dit is een spel waarbij de eerste vangst wint. Hier maakt de volgorde wel uit. Verrassend genoeg won MCPS nog steeds, maar zijn voordeel was het grootst op kleine borden waar het spel snel eindigt. Op grote borden wordt het spel te lang voor de "volgorde maakt niet uit"-truc om evenveel te helpen.
NoGo (De Consistente Winnaar): Dit is een spel waarbij je verliest als je vangt. MCPS won bijna overal, en sloeg de oude methode consequent met een stevige marge.
Wargame (De Snelheidsduivel): In dit aangepaste strategiespel speelde MCPS niet alleen beter; het speelde ook sneller. Het simuleerde spellen die eerder eindigden en vond de winnende strategie sneller, waardoor het meer simulaties kon uitvoeren in dezelfde hoeveelheid tijd.

De Conclusie

Het artikel beweert dat MCPS een slimmere, efficiëntere manier is voor computers om spellen te spelen zonder diep leren of enorme training nodig te hebben.

Het werkt door te beseffen dat in veel spellen de set zetten die je maakt belangrijker is dan de volgorde waarin je ze doet. Door alle keren te tellen dat een specifieke set zetten voorkwam in willekeurige spellen, bouwt MCPS een betere "intuïtie" op over welke zetten goed zijn. Het is als een detective die beseft dat zelfs als de verdachten in een andere volgorde arriveerden, het feit dat ze allemaal op de plaats delict waren, de echte aanwijzing is.

Het resultaat is een universeel hulpmiddel dat de vorige beste methode in bijna elk getest scenario verslaat, waardoor het een krachtige nieuwe standaard wordt voor spelende AI wanneer je geen supercomputer tot je beschikking hebt.

Technische Samenvatting: Monte Carlo Permutatie Search (MCPS)

Probleemstelling

Monte Carlo Tree Search (MCTS) is een dominant algoritme voor het spelen van spellen en het nemen van beslissingen, met name in domeinen waar diepe versterkende leer (deep reinforcement learning) onuitvoerbaar is vanwege gebrek aan trainingsdata of rekenkundige beperkingen (bijvoorbeeld General Game Playing). Hoewel MCTS-varianten zoals GRAVE (Generalized RAVE) de standaard UCT hebben verbeterd door statistieken van voorouderknooppunten en All-Moves-As-First (AMAF)-heuristieken te benutten, vertrouwen ze op twee primaire bronnen van informatie: statistieken van playouts die beginnen met een specifieke zet en statistieken van playouts waarin de zet later voorkomt.

Het artikel identificeert een beperking in bestaande benaderingen: ze maken geen volledig gebruik van de statistische informatie die zit in playouts waarbij de volgorde van zetten die leiden tot een knooppunt in een andere volgorde voorkomt. In spellen met commutatieve eigenschappen (zoals Hex) leidt elke permutatie van zetten naar dezelfde staat. In niet-commutatieve spellen (zoals AtariGo) kunnen permutaties leiden tot verschillende staten, maar het artikel hypothesiseert dat de statistische waarde van de zetten toch informatief blijft. Het doel is een algemeen toepasbaar MCTS-algoritme te ontwikkelen dat GRAVE verbetert zonder probleemspecifieke afstemming, modeltraining of bias-hyperparameters te vereisen.

Methodologie

Kernconcept: Monte Carlo Permutatie Search (MCPS)

MCPS introduceert een derde bron van statistieken in het proces voor het evalueren van knooppunten. Om een actie $a$ te evalueren in een knooppunt $s$ dat wordt bereikt via een pad $(a_0, a_1, \dots, a_d)$ , aggregeert MCPS data uit drie onderscheiden sets van playouts:

Directe Statistieken ( $Q$ ): Playouts die beginnen met het pad naar $s$ gevolgd door actie $a$ .
AMAF Statistieken ( $\tilde{Q}$ ): Playouts die beginnen met het pad naar $s$ , waarbij actie $a$ later in de reeks voorkomt (standaard GRAVE-benadering).
Permutatiestatistieken ( $\hat{Q}$ ): Playouts die de set zetten $\{a_0, a_1, \dots, a_d, a\}$ bevatten in elke volgorde en op elke positie.

Wiskundige Afleiding van Gewichten

Het artikel biedt een wiskundige afleiding voor het combineren van deze drie schatters. Onder de aanname dat de statistieken onafhankelijk zijn, leiden de auteurs de gewichten af die de variantie van de gecombineerde schatter minimaliseren.
Laat $n$ , $\tilde{n}$ en $\hat{n}$ de steekproefaantallen zijn voor de drie statistieken. De optimale gewichten ( $\beta, \tilde{\beta}, \hat{\beta}$ ) zijn evenredig met hun steekproefaantallen:
$\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}}$
Deze convexe combinatie elimineert de noodzaak van de bias-hyperparameter die in het GRAVE-algoritme wordt gebruikt, en biedt een gewichtsschema zonder parameters.

Algorithmische Implementatie

Selectie: De waarde van een zet wordt berekend als het gewogen gemiddelde van de drie schatters.
Berekening van Permutatiestatistieken: Om $\hat{Q}$ efficiënt te berekenen, gebruikt het algoritme een glijdend venster van recente playouts (standaard $W=10.000$ ), weergegeven als bitsets. Voor een knooppunt $s$ intersecteert het algoritme de bitsets van alle zetten op het pad naar $s$ om playouts te identificeren die de volledige padvolgorde bevatten. Vervolgens intersecteert het dit resultaat met de bitset van de kandidaatzet $a$ om de relevante playouts te isoleren. Dit gebeurt met behulp van 64-bit woordoperaties (POPCOUNT en bit-scan) voor efficiëntie.
Invriezen: Zodra een knooppunt een drempelaantal bezoeken heeft bereikt ( $\rho=30$ ), worden de permutatiestatistieken ervan berekend en "bevroren". Dit knooppunt fungeert vervolgens als referentie voor de volledige subboom, waardoor nakomelingen deze statistieken kunnen erven zonder ze opnieuw te hoeven berekenen.
Zetcodering: Om kennisoverdracht tussen verschillende bordposities mogelijk te maken, worden zetten gemapt naar gehele getalcodes op basis van spelrelevante kenmerken (bijvoorbeeld speler, bestemmingscel, gevechtstrigger) in plaats van exacte coördinaten.

Belangrijkste Bijdragen

Algorithmische Uitbreiding: Het voorstellen van MCPS, dat permutatiestatistieken integreert in de MCTS-selectieregel, waarmee het GRAVE-algoritme wordt uitgebreid.
Theoretische Verbetering: Een afleiding van wegingsformules die de variantie van de schatter minimaliseren onder onafhankelijkheidsaannames, waardoor de behoefte aan de GRAVE-bias-hyperparameter wordt weggenomen.
Efficiënte Implementatie: Een methode voor het berekenen van permutatiestatistieken met behulp van bitsets en glijdende vensters, waardoor het algoritme de combinatorische explosie van zetordes efficiënt kan hanteren.
Algemene Toepasbaarheid: Aantonen dat het algoritme werkt over diverse speltypen (commutatief en niet-commutatief) zonder specifieke parameterafstemming.

Experimentele Resultaten

De auteurs hebben MCPS getest tegen GRAVE in vijf spellen: Hex, Go, AtariGo, NoGo en een aangepast asymmetrisch Wargame. In alle gevallen werden 800 spellen gespeeld per configuratie (400 met elk algoritme als eerste speler) onder identieke tijdsbudgetten.

Hex: MCPS presteert beter dan GRAVE op borden van $7\times7$ en groter, met winstpercentages van 70–76% op grotere borden. Op $5\times5$ is de overhead van bitsets een lichte nadeel voor MCPS. Het voordeel groeit met de bordgrootte omdat MCPS diepere bomen bouwt.
Go: MCPS presteert beter dan GRAVE op borden van $7\times7$ en groter. Opvallend is dat op grotere borden ( $13\times13$ , $15\times15$ ) het verschil in winstpercentage significant toeneemt naarmate het tijdsbudget groter wordt (tot 63,75% bij 2 seconden). MCPS bouwt consistent diepere bomen naarmate er meer tijd is, terwijl de boomdiepte van GRAVE vaak stagneert of afneemt.
AtariGo: MCPS presteert beter dan GRAVE in alle configuraties, met de grootste winst op kleine borden ( $5\times5$ , $7\times7$ ). Het voordeel neemt af op grotere borden omdat het spel vaak eindigt voordat de zoektocht de eindtoestand bereikt, waardoor het voordeel van diepere bomen beperkt blijft.
NoGo: MCPS toont de meest uniforme verbetering en presteert beter dan GRAVE in elke cel met winstpercentages tussen 57% en 69%. De verbetering is consistent over bordgroottes en tijdsbudgetten.
Wargame: MCPS presteert beter dan GRAVE op borden van $9\times9$ en groter. Het algoritme is 15–33% sneller (meer playouts per seconde) vanwege kortere simulatielengtes en convergeert sneller naar beslissende spelstaten.

Betekenis en Beweringen

Het artikel beweert dat MCPS een aanzienlijke verbetering is ten opzichte van GRAVE voor algemeen toepasbare MCTS-toepassingen, met name in scenario's waar deep learning geen optie is. Het primaire mechanisme voor succes is de "beter geïnformeerde selectieregel", die het algoritme in staat stelt:

Diepere zoekbomen te bouwen.
Simulatiewerk per iteratie te verminderen (in sommige spellen).
Dichter bij eindstaten te komen (in spellen zoals AtariGo).
Extra rekentijd om te zetten in diepere verkenning van veelbelovende lijnen (waargenomen in Go).

De auteurs benadrukken dat het algoritme algemeen toepasbaar is en geen probleemspecifieke aanpassingen of training vereist. De resultaten suggereren dat het voordeel van MCPS het meest uitgesproken is wanneer het resulterende dieptevoordeel binnen het relevante beslissingshorizon van het spel valt. Het artikel concludeert dat het concept van het combineren van drie bronnen van statistieken herbruikbaar is voor andere soorten statistieken buiten permutaties.