🤖 machine learning

Monte Carlo Permutation Search

Dieser Artikel stellt Monte Carlo Permutation Search (MCPS) vor, einen universell einsetzbaren MCTS-Algorithmus, der in Spielen wie Hex und Go den GRAVE-Algorithmus übertrifft, indem er playout-spezifische Statistiken über den gesamten Pfad in den Explorationsterm integriert und eine neue Gewichtungsformel ableitet, die das Bias-Hyperparameter von GRAVE überflüssig macht.

Ursprüngliche Autoren: Tristan Cazenave

Veröffentlicht 2026-05-27

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Tristan Cazenave

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich vor, Sie versuchen, ein komplexes Puzzle zu lösen, wie ein Spiel Go oder Hex, aber Sie haben keinen Supercomputer oder eine trainierte KI, die Ihnen den besten Zug sagt. Stattdessen müssen Sie sich auf „Raten und Prüfen" verlassen, indem Sie Tausende von zufälligen Zukunftsszenarien in Gedanken durchspielen. So funktioniert ein Computerprogramm namens Monte-Carlo-Baumsuche (MCTS).

Lange Zeit war der beste Weg, dieses Raten durchzuführen, ein Algorithmus namens GRAVE. Er war gut darin, aus der Vergangenheit die Zukunft vorherzusagen, aber der Autor dieses Papers, Tristan Cazenave, dachte: „Wir können es besser machen."

Er entwickelte einen neuen Algorithmus namens MCPS (Monte Carlo Permutation Search). Hier ist, wie er funktioniert, einfach erklärt:

Die drei Arten, in die Vergangenheit zu blicken

Um zu entscheiden, welchen Zug als Nächstes zu machen ist, betrachtet MCPS seine Historie an zufälligen Spielen (sogenannte „Playouts") auf drei verschiedene Arten. Denken Sie an diese als drei verschiedene Objektive einer Kamera:

Das Objektiv „Exakter Pfad" (Standardansicht):
Dies betrachtet Spiele, in denen der Spieler die exakt gleiche Zugfolge machte, um an die aktuelle Stelle zu gelangen, und dann den spezifischen Zug ausführte, den wir testen.
- Analogie: „Ich bin die Main Street hinuntergegangen, habe links abgebogen und dann einen Kaffee gekauft. Wie lief das?"
Das Objektiv „Reihenfolge ist egal" (Das GRAVE-Upgrade):
Dies betrachtet Spiele, in denen der Spieler die gleichen Züge machte, um an die Stelle zu gelangen, aber die Reihenfolge war leicht unterschiedlich, und der spezifische Zug, den wir testen, erschien später im Spiel.
- Analogie: „Ich habe einen Kaffee gekauft, dann bin ich die Main Street hinuntergegangen, dann habe ich links abgebogen. Es sind die gleichen Zutaten, nur eine andere Reihenfolge im Rezept. Hat es trotzdem gut geschmeckt?"
- Warum es hilft: In vielen Spielen ändert die Reihenfolge, in der Sie Ihre Steine setzen, nicht den endgültigen Spielzustand. Dieses Objektiv ermöglicht es dem Computer also, aus mehr Spielen zu lernen, nicht nur aus denen, die exakt der gleichen Reihenfolge entsprachen.
Das Objektiv „Permutation" (Das neue MCPS-Geheimrezept):
Dies ist die neue Ergänzung. Es betrachtet jedes Spiel, in dem der Spieler exakt denselben Satz an Zügen verwendete (der Pfad zur aktuellen Stelle + der neue Zug), unabhängig davon, in welcher Reihenfolge diese stattfanden.
- Analogie: „Ich habe einen Hammer, einen Schraubenzieher und einen Nagel verwendet, um ein Regal zu bauen. Es ist egal, ob ich zuerst gehämmert oder geschraubt habe; wenn ich diese drei Werkzeuge verwendet habe, wurde das Regal gebaut. Wie hat sich diese Kombination ausgewirkt?"
- Der Haken: In einigen Spielen (wie AtariGo) ist die Reihenfolge wichtig, weil das Spiel früh enden kann (wie beim Fangen eines Steins). MCPS bewältigt dies, indem es intelligent damit umgeht, wie es diese Züge gruppiert.

Die „Magische Formel"

Das Paper erklärt, dass MCPS nicht einfach eine dieser Ansichten auswählt; es mischt sie zusammen. Der Autor hat einige Mathematik betrieben, um den perfekten Weg zu finden, diese drei Informationsquellen zu mischen.

Stellen Sie es sich wie das Zubereiten eines Smoothies vor. Sie haben drei Früchte (die drei Statistiken). GRAVE verwendete ein festes Rezept, das manchmal nicht gut schmeckte. MCPS verwendet ein mathematisch perfektes Rezept, das die Mengen automatisch anpasst, basierend darauf, wie viele Daten es für jede Frucht hat. Das Beste daran? Es braucht keinen „Geschmackstest" (ein Mensch, der einen Bias-Parameter festlegt), um es richtig zu machen; die Mathematik erledigt dies automatisch.

Wie es in der realen Welt abgeschnitten hat

Der Autor testete MCPS gegen den alten Champion (GRAVE) bei fünf verschiedenen Arten von Spielen:

Hex (Der perfekte Match): In diesem Spiel ändert die Reihenfolge der Züge niemals den endgültigen Spielbrettzustand. MCPS war hier ein großer Gewinner, besonders auf größeren Brettern. Es war, als hätte man eine Karte, die jeden möglichen Pfad zeigt, nicht nur den, den man genommen hat.
Go (Der tiefe Denker): Auf kleinen Brettern waren sie etwa gleich. Aber auf großen Brettern, als dem Computer mehr Zeit zum Nachdenken gegeben wurde, zog MCPS davon. Es war besser darin, diese zusätzliche Zeit zu nutzen, um tiefer in die vielversprechendsten Spielzüge einzudringen, wohingegen die alte Methode stecken blieb und oberflächliche Optionen erkundete.
AtariGo (Der schnelle Finisher): Dies ist ein Spiel, bei dem der erste Fang gewinnt. Hier ist die Reihenfolge wichtig. Überraschenderweise gewann MCPS immer noch, aber sein Vorteil war am größten auf kleinen Brettern, wo das Spiel schnell endet. Auf großen Brettern wird das Spiel zu lang, als dass der Trick „Reihenfolge ist egal" so sehr helfen könnte.
NoGo (Der konsistente Gewinner): Dies ist ein Spiel, bei dem man verliert, wenn man fängt. MCPS gewann fast überall und schlug die alte Methode konsequent mit einem soliden Vorsprung.
Wargame (Der Geschwindigkeitsdämon): In diesem benutzerdefinierten Strategiespiel spielte MCPS nicht nur besser; es spielte schneller. Es simulierte Spiele, die früher endeten, und fand die Gewinnstrategie schneller, was es ihm ermöglichte, mehr Simulationen in der gleichen Zeitspanne durchzuführen.

Das Fazit

Das Paper behauptet, dass MCPS eine intelligentere, effizientere Methode für Computer ist, um Spiele zu spielen, ohne tiefes Lernen oder massives Training zu benötigen.

Es funktioniert, indem es erkennt, dass in vielen Spielen die Menge der Züge, die Sie machen, wichtiger ist als die Reihenfolge, in der Sie sie machen. Indem es alle Fälle zählt, in denen ein bestimmter Satz von Zügen in zufälligen Spielen erschien, baut MCPS eine bessere „Intuition" darüber auf, welche Züge gut sind. Es ist wie ein Detektiv, der erkennt, dass selbst wenn die Verdächtigen in einer anderen Reihenfolge ankamen, die Tatsache, dass sie alle am Tatort waren, der eigentliche Hinweis ist.

Das Ergebnis ist ein universelles Werkzeug, das in fast jedem getesteten Szenario die bisher beste Methode schlägt und damit einen neuen, mächtigen Standard für spielende KI darstellt, wenn Ihnen kein Supercomputer zur Verfügung steht.

Technische Zusammenfassung: Monte Carlo Permutation Search (MCPS)

Problemstellung

Monte Carlo Tree Search (MCTS) ist ein dominanter Algorithmus für das Spielen von Spielen und Entscheidungsfindung, insbesondere in Bereichen, in denen Deep Reinforcement Learning aufgrund fehlender Trainingsdaten oder rechnerischer Einschränkungen nicht durchführbar ist (z. B. General Game Playing). Während MCTS-Varianten wie GRAVE (Generalized RAVE) den Standard-UCT durch die Nutzung von Statistiken aus Vorfahrenknoten und Heuristiken für All-Moves-As-First (AMAF) verbessert haben, verlassen sie sich auf zwei primäre Informationsquellen: Statistiken aus Playouts, die mit einem spezifischen Zug beginnen, und Statistiken aus Playouts, in denen der Zug später erscheint.

Die Arbeit identifiziert eine Einschränkung bestehender Ansätze: Sie nutzen die statistischen Informationen in Playouts, bei denen die Folge von Zügen, die zu einem Knoten führen, in einer anderen Reihenfolge auftritt, nicht vollständig aus. In Spielen mit kommutativen Eigenschaften (wie Hex) führt jede Permutation von Zügen zum selben Zustand. In nicht-kommutativen Spielen (wie AtariGo) können Permutationen zu unterschiedlichen Zuständen führen, dennoch geht die Arbeit davon aus, dass der statistische Wert der Züge informativ bleibt. Das Ziel ist die Entwicklung eines universellen MCTS-Algorithmus, der GRAVE verbessert, ohne problemspezifische Feinabstimmung, Modelltraining oder Bias-Hyperparameter zu erfordern.

Methodik

Kernkonzept: Monte Carlo Permutation Search (MCPS)

MCPS führt eine dritte Quelle von Statistiken in den Bewertungsprozess von Knoten ein. Um eine Aktion $a$ an einem Knoten $s$ zu bewerten, der durch einen Pfad $(a_0, a_1, \dots, a_d)$ erreicht wurde, aggregiert MCPS Daten aus drei distincten Sätzen von Playouts:

Direkte Statistiken ( $Q$ ): Playouts, die mit dem Pfad zu $s$ beginnen, gefolgt unmittelbar von der Aktion $a$ .
AMAF-Statistiken ( $\tilde{Q}$ ): Playouts, die mit dem Pfad zu $s$ beginnen, wobei die Aktion $a$ später in der Sequenz erscheint (Standard-GRAVE-Ansatz).
Permutationsstatistiken ( $\hat{Q}$ ): Playouts, die die Menge der Züge $\{a_0, a_1, \dots, a_d, a\}$ in beliebiger Reihenfolge und an beliebigen Positionen enthalten.

Mathematische Herleitung der Gewichte

Die Arbeit liefert eine mathematische Herleitung zur Kombination dieser drei Schätzer. Unter der Annahme, dass die Statistiken unabhängig sind, leiten die Autoren die Gewichte ab, die die Varianz des kombinierten Schätzers minimieren.
Seien $n$ , $\tilde{n}$ und $\hat{n}$ die Stichprobenanzahlen für die drei Statistiken. Die optimalen Gewichte ( $\beta, \tilde{\beta}, \hat{\beta}$ ) sind proportional zu ihren Stichprobenanzahlen:
$\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}}$
Diese konvexe Kombination eliminiert die Notwendigkeit des Bias-Hyperparameters, der im GRAVE-Algorithmus verwendet wird, und bietet ein gewichtungsloses Schema ohne Parameter.

Algorithmische Implementierung

Selektion: Der Wert eines Zuges wird als gewichteter Durchschnitt der drei Schätzer berechnet.
Berechnung der Permutationsstatistiken: Um $\hat{Q}$ effizient zu berechnen, verwendet der Algorithmus ein gleitendes Fenster aktueller Playouts (Standard $W=10.000$ ), dargestellt als Bitsets. Für einen Knoten $s$ schneidet der Algorithmus die Bitsets aller Züge auf dem Pfad zu $s$ miteinander, um Playouts zu identifizieren, die die vollständige Pfadsequenz enthalten. Anschließend schneidet er dieses Ergebnis mit dem Bitset des Kandidatenzugs $a$ , um die relevanten Playouts zu isolieren. Dies erfolgt unter Verwendung von 64-Bit-Wortoperationen (POPCOUNT und Bit-Scan) zur Effizienzsteigerung.
Einfrieren: Sobald ein Knoten eine Schwellenanzahl von Besuchen ( $\rho=30$ ) angesammelt hat, werden seine Permutationsstatistiken berechnet und „eingefroren". Dieser Knoten fungiert dann als Referenz für seinen gesamten Unterbaum, sodass Nachkommen diese Statistiken erben können, ohne sie neu berechnen zu müssen.
Zugkodierung: Um Wissensübertragung zwischen verschiedenen Brettpositionen zu ermöglichen, werden Züge basierend auf spielrelevanten Merkmalen (z. B. Spieler, Zielzelle, Kampfauslöser) auf Ganzzahl-Codes abgebildet, anstatt auf exakten Koordinaten.

Hauptbeiträge

Algorithmische Erweiterung: Der Vorschlag von MCPS, der Permutationsstatistiken in die MCTS-Selektionsregel integriert und den GRAVE-Algorithmus erweitert.
Theoretische Verbesserung: Eine Herleitung von Gewichtsformeln, die die Varianz des Schätzers unter Unabhängigkeitsannahmen minimieren und die Notwendigkeit des GRAVE-Bias-Hyperparameters beseitigen.
Effiziente Implementierung: Eine Methode zur Berechnung von Permutationsstatistiken unter Verwendung von Bitsets und gleitenden Fenstern, die es dem Algorithmus ermöglicht, die kombinatorische Explosion von Zugreihenfolgen effizient zu bewältigen.
Allgemeine Anwendbarkeit: Der Nachweis, dass der Algorithmus über verschiedene Spieltypen (kommutativ und nicht-kommutativ) hinweg funktioniert, ohne spezifische Parameteranpassungen.

Experimentelle Ergebnisse

Die Autoren testeten MCPS gegen GRAVE über fünf Spiele hinweg: Hex, Go, AtariGo, NoGo und ein benutzerdefiniertes asymmetrisches Kriegsspiel. In allen Fällen wurden 800 Spiele pro Konfiguration gespielt (400 mit jedem Algorithmus, der zuerst spielt) unter identischen Zeitbudgets.

Hex: MCPS übertrifft GRAVE auf Brettern $7\times7$ und größer, mit Gewinnquoten von 70–76 % auf größeren Brettern. Auf $5\times5$ benachteiligt der Overhead der Bitsets MCPS leicht. Der Vorteil wächst mit der Brettgröße, da MCPS tiefere Bäume aufbaut.
Go: MCPS übertrifft GRAVE auf Brettern $7\times7$ und größer. Bemerkenswert ist, dass sich auf größeren Brettern ( $13\times13$ , $15\times15$ ) die Gewinnquotenlücke mit steigendem Zeitbudget signifikant vergrößert (bis zu 63,75 % bei 2 s). MCPS baut mit mehr Zeit konsistent tiefere Bäume auf, während die Baumschichttiefe von GRAVE oft stagniert oder abnimmt.
AtariGo: MCPS übertrifft GRAVE in allen Konfigurationen, mit den größten Gewinnen auf kleinen Brettern ( $5\times5$ , $7\times7$ ). Der Vorteil nimmt auf größeren Brettern ab, da das Spiel oft endet, bevor die Suche den Endzustand erreicht, was den Nutzen tieferer Bäume begrenzt.
NoGo: MCPS zeigt die gleichmäßigste Verbesserung und übertrifft GRAVE in jeder Zelle mit Gewinnquoten zwischen 57 % und 69 %. Die Verbesserung ist über Brettgrößen und Zeitbudgets hinweg konsistent.
Kriegsspiel: MCPS übertrifft GRAVE auf Brettern $9\times9$ und größer. Der Algorithmus läuft 15–33 % schneller (mehr Playouts pro Sekunde) aufgrund kürzerer Simulationslängen und konvergiert schneller in entscheidenden Spielzuständen.

Bedeutung und Behauptungen

Die Arbeit behauptet, dass MCPS eine signifikante Verbesserung gegenüber GRAVE für universelle MCTS-Anwendungen darstellt, insbesondere in Szenarien, in denen Deep Learning keine Option ist. Der primäre Mechanismus für den Erfolg ist die „besser informierte Selektionsregel", die es dem Algorithmus ermöglicht:

Tiefere Suchbäume aufzubauen.
Simulationsaufwand pro Iteration zu reduzieren (in einigen Spielen).
Endzuständen näher zu kommen (in Spielen wie AtariGo).
Zusätzliche Rechenzeit in eine tiefere Exploration vielversprechender Linien umzuwandeln (beobachtet bei Go).

Die Autoren betonen, dass der Algorithmus universell einsetzbar ist und keine problemspezifischen Modifikationen oder Trainings erfordert. Die Ergebnisse deuten darauf hin, dass der Vorteil von MCPS am ausgeprägtesten ist, wenn der daraus resultierende Tiefenvorteil innerhalb des relevanten Entscheidungshorizonts des Spiels liegt. Die Arbeit schließt, dass das Konzept der Kombination dreier Quellen von Statistiken für andere Arten von Statistiken jenseits von Permutationen wiederverwendbar ist.