Monte-Carlo-Baumsuche verständlich erklärt

Eine Kurierin soll in einer fremden Stadt ohne Stadtplan ein Paket ausliefern. Sie probiert zufällige Fahrten aus und merkt sich, welche Abzweigungen sich bewährt haben. Diese Seite zeigt, wie weit das reicht und wo es versagt.

Zuletzt aktualisiert: 11. November 2026

Ein Wort unbekannt? Das Begriffsverzeichnis erklärt es in wenigen Sätzen.

Einen Weg finden ohne Stadtplan

Eine Kurierin soll in einer fremden Stadt ein Paket ausliefern. Einen Stadtplan hat sie nicht, und die Richtung zum Ziel kennt sie auch nicht. Einige Straßen sind gesperrt.

Ob eine Fahrt gut war, erfährt sie erst am Ende: Sie kommt an oder landet in einer Sackgasse. Unterwegs sagt ihr nichts, ob sie richtig fährt. Die Faustregel „immer Richtung Ziel“ kann sie nicht nutzen.

Also probiert sie aus, schreibt auf und fährt öfter dorthin, wo es geklappt hat. So arbeitet die Monte-Carlo-Baumsuche, englisch Monte Carlo Tree Search, kurz MCTS. „Monte Carlo“ steht für den Zufall. Der „Baum“ ist ihr Merkzettel, der sich an Abzweigungen verzweigt wie ein Stammbaum.

Ein Durchgang in vier Schritten

Die Kurierin arbeitet in Durchgängen mit je vier Schritten. Viele Durchgänge hintereinander heißen ein Lauf. Auf dem Merkzettel steht je Abzweigung, wie oft sie dort war. Dazu steht dort, wie viele Punkte die Fahrten im Schnitt brachten.

• Dem Merkzettel folgen. Vom Start aus nimmt sie an jeder Abzweigung die aussichtsreichste nach der Regel des nächsten Abschnitts. So kommt sie an eine Stelle, von der noch nie probierte Wege abgehen.
• Neu probieren. Dort wählt sie per Zufall einen unprobierten Weg und schreibt ihn auf.
• Zufallsfahrt. Ab dort wählt sie an jeder Kreuzung eine zufällige Richtung, nie zweimal dieselbe Kreuzung. Die Fahrt endet am Ziel, in einer Sackgasse oder nach einer festen Zahl von Kreuzungen, dem Fahrtlimit. Fachleute sagen Rollout.
• Punkte eintragen. Sackgasse und Fahrtlimit bringen null Punkte. Wer ankommt, bekommt höchstens einen Punkt. Verglichen wird die Fahrt mit der Luftlinie, der geraden Entfernung von Start und Ziel: Je länger die Fahrt im Vergleich dazu, desto weniger Punkte. Die Punkte trägt sie bei den Abzweigungen ein, die schon auf dem Merkzettel stehen, vom Start bis zur neuen Abzweigung. Die Kreuzungen der Zufallsfahrt selbst merkt sie sich nicht.

Der Merkzettel wächst ungleichmäßig: dicht, wo Fahrten Punkte brachten, dünn, wo sie ins Leere liefen. Als Ergebnis gilt die kürzeste Strecke, die irgendeine Fahrt je bis zum Ziel fand.

Bewährtes wiederholen oder Neues probieren

Das kennen Sie aus dem Urlaub: Sie haben ein gutes Restaurant gefunden. Gehen Sie wieder hin oder probieren Sie ein neues? Immer dasselbe verpasst vielleicht ein besseres. Nur Neues heißt oft schlecht essen.

Die Kurierin entscheidet das an jeder Abzweigung mit einer Regel (Fachname UCB1). Jede Abzweigung bekommt einen Wert: ihre Durchschnittspunkte plus einen Bonus. Der Bonus ist groß, wenn die Abzweigung selten probiert wurde, und schrumpft mit jedem Besuch. Lässt man sie lange links liegen, wächst er langsam wieder. So kommt auch eine dran, die beim ersten Mal Pech hatte.

Wie stark der Bonus zählt, stellt ein Regler ein. Ein winziges Netz hat 4 mal 4 Kreuzungen. Mit kleinem Bonus fand die Suche dort die beste Strecke nur in 10 % der Läufe, mit großem Bonus in allen. Im Beispielnetz unten wirkte der Regler nur schwach.

Was dabei herauskommt

Die Zahlen in diesem Teil stammen von einem Rechenbild, einem vereinfachten Beispiel am Rechner: ein Netz aus 12 mal 12 Kreuzungen, davon etwa 15 % gesperrt, je 4000 Durchgänge. Genannt wird der Median, der Wert in der Mitte, wenn man die Läufe nach Ergebnis ordnet. Der Umweg sagt, um wie viel länger die gefundene Strecke ist als die kürzeste.

• Sie kommt an. Mit dem Fahrtlimit des Beispiels fand die Kurierin in jedem Lauf eine Strecke. Setzt man das Limit auf nur 10 Kreuzungen, gelang das nur einer Minderheit der Läufe: Das Limit ist kürzer als jeder Weg zum Ziel, also kommt keine Zufallsfahrt nahe dem Start dort an.
• Sie ist nicht die kürzeste. In keinem Lauf war es die kürzeste Strecke, der typische Umweg betrug 17 %. Eine Deutung dieser Seite: Eine etwas längere Strecke bekommt nur etwas weniger Punkte, und der Zufall trifft die allerbeste selten.
• Mehr Durchgänge helfen langsam. Bei vierfach so vielen Durchgängen wie im Beispiel war der typische Umweg etwa halb so groß.
• Wer die Karte kennt, ist viel schneller. Ein Verfahren mit Karte arbeitet die Kreuzungen nach Entfernung vom Start ab. Es fand die kürzeste Strecke nach 121 Prüfschritten. Die Kurierin brauchte rund 81 000 Kreuzungsbesuche. Die Zähleinheiten sind verschieden: Das Kartenverfahren zählt jede Kreuzung, die es abarbeitet, die Kurierin jede Kreuzung, die sie berührt, auch wiederholt. Der Abstand bleibt groß, weil sie ähnliche Wege wieder und wieder fährt.

Große Netze

Je größer das Netz, desto seltener kommt eine Zufallsfahrt am Ziel an. Der Zufall muss mehr Kreuzungen nacheinander richtig treffen. Bei 22 mal 22 Kreuzungen erreichten weniger als 1 % der Durchgänge das Ziel. Dann bekommen fast alle Fahrten null Punkte, der Merkzettel gibt keinen Hinweis, und die Suche fährt praktisch blind. Der typische Umweg stieg auf rund 68 %.

Wie viel leistet der Zufall wirklich?

Nun bekommt die Kurierin zusätzlich einen Kompass, der die Richtung zum Ziel zeigt. Sie würfelt weiter, bevorzugt aber an jeder Kreuzung die Richtung, in der die Luftlinie zum Ziel kürzer wird. Sie fährt also mit Schlagseite zum Ziel.

Der typische Umweg fiel von 17 % auf rund 2 %. Mit Schlagseite kommen die Fahrten öfter an, und das Problem der Nullpunkte schrumpft. Der Kompass leistet hier den größten Teil der Arbeit.

Zum Vergleich: Ein Fahrer, der stur die Abzweigung mit der kürzesten Luftlinie zum Ziel nimmt, heißt gierig (englisch Greedy). Er kam auf denselben Netzen auf einen typischen Umweg von rund 15 %.

Dafür lässt sich der Zufall nicht täuschen. In einem handgebauten kleinen Netz lockt ein Köder nahe am Ziel. Von dort führt ein langer Korridor erst spät ans Ziel. Der gierige Fahrer folgt dem Köder und fährt eine längere Strecke als nötig. Die Kurierin ohne Kompass fand in diesem kleinen Netz in allen 10 getesteten Läufen die beste Strecke. Der Korridor bringt ihr zwar Punkte, aber weniger als der kürzere Weg.

Häufige Missverständnisse

• „Zufall heißt: Das Verfahren probiert nur blind.“ Nein. Der Zufall steckt nur in den Zufallsfahrten. Der Merkzettel lenkt die Durchgänge dorthin, wo Fahrten Punkte brachten.
• „Das Verfahren wird bei Brettspielen wie Go eingesetzt, also findet es auch den kürzesten Weg in meinem Netz.“ Nicht zuverlässig. Wo man das Netz vollständig kennt, schafft ein Verfahren mit Karte die kürzeste Strecke mit viel weniger Aufwand.

Woran Sie das im Alltag erkennen

Das Vorgehen passt am ehesten, wenn Sie Folgendes sehen:

• Ob eine Entscheidung gut war, zeigt sich erst am Ende, etwa am Schluss einer Partie.
• Sie können die Entscheidung viele Male probeweise durchspielen, ohne dass es etwas kostet.
• Eine verlässliche Faustregel, was unterwegs gut ist, fehlt.

Wie ernst ist das Modell zu nehmen?

Das Rechenbild ist ein künstliches Netz mit zufällig gesperrten Kreuzungen, keine echte Stadt. Wie sich das Verfahren in Spielen oder bei unsicheren Fahrzeiten verhält, zeigt die Messung nicht.

Was Sie mitnehmen

• Fragen Sie bei einem Verfahren, das „ohne Vorwissen“ arbeitet: Steckt irgendwo doch ein Kompass drin, der den Zufall lenkt?
• Fragen Sie bei Zufallsverfahren, wie viele Versuche nötig sind und wie das mit der Größe der Aufgabe wächst.
• Trauen Sie dem ersten Treffer nicht: Eine gefundene Lösung ist noch nicht die beste.

Zu dieser Seite gehört ein Programm zum Ausprobieren im Browser, die Demo. Dort stellen Sie Netzgröße, Durchgänge, Bonus und Kompass ein. Zum Verstehen brauchen Sie sie nicht. „Demo ausprobieren“ öffnet sie, „Weiter zum Fachteil“ führt zum zweiten Teil für Fachleute.

Hinweis: Alle Demos rechnen mit synthetischen oder frei verfügbaren Beispieldaten und laufen auf einem externen Anbieter (Datenschutz). Bitte geben Sie darin keine vertraulichen oder personenbezogenen Daten ein. Die Ergebnisse gelten für die jeweilige Demo-Instanz und lassen sich nicht ungeprüft auf reale Fälle übertragen; für darauf gestützte Entscheidungen übernehme ich keine Gewähr.

Modell und Annahmen

Dieser Teil ist eigenständig lesbar. Er fasst Modell und Messungen der Demo zusammen.

• Aufgabe: Gesucht ist eine möglichst kurze Route von einem Start zu einem Ziel in einem ungerichteten Netz mit Kantenlängen; die Kosten einer Route sind die Summe ihrer Kantenlängen. Das Netz ist vollständig bekannt und deterministisch, bewertet wird eine Route erst am Ziel (Reward nur am Ziel). Die Kosten \(L^*\) der kürzesten Route liefert die Uniform-Cost-Suche.
• Netz: Ein Raster aus \(n \times n\) Zellen (Seitenlänge \(n\) von 4 bis 25, Voreinstellung 12); jede Zelle wird unabhängig mit einer Wahrscheinlichkeit von 0 bis 40 % gesperrt (Voreinstellung 15 %). Start (unten links) und Ziel (oben rechts) sind stets offen, und bei Bedarf werden Zellen wieder geöffnet, bis beide verbunden sind; der tatsächliche Anteil gesperrter Zellen weicht daher zufällig ab. Die Zellmitten sind um einen Bruchteil des Zellenabstands verschoben, die Nachbarschaft ist die Vierernachbarschaft, die Kantenlänge ist der euklidische Abstand in Kilometern. Das Netz entsteht aus einer Zahl als Startwert (Netz Nr. 35 ist eines davon); dieselbe Nr. ergibt bei anderer Größe oder Hindernisdichte ein anderes Netz. Dazu kommt ein handgebautes Netz mit 8 Knoten: Die Luftlinie lockt zu einem Köder nahe am Ziel, von dem ein langer Korridor erst spät zum Ziel führt, während ein kürzerer Umweg woanders verläuft.
• Luftlinie: \(h(v)\) ist der Abstand des Knotens \(v\) zum Ziel in der Ebene. Wegen der euklidischen Kantenlängen ist \(h\) nie größer als der wahre Restweg (zulässig). Reines MCTS benutzt von ihr nur den Abstand \(d_0 = h(\text{Start})\) als Maßstab des Rewards, nicht zur Wegwahl.
• Baum: Ein Knoten \(v\) steht für einen Zustand \(s(v)\) (eine Kreuzung) auf einem bestimmten Weg von der Wurzel; er trägt die Besuchszahl \(N(v)\) und die Reward-Summe \(W(v)\). Derselbe Zustand kann in verschiedenen Ästen stehen (Transpositionen werden nicht zusammengeführt), wiederholt sich aber nie auf einem Weg.
• Eine Iteration: (1) Selektion: von der Wurzel zum Kind mit größtem UCB1-Wert absteigen, solange der Knoten keine unprobierten Kinder hat. (2) Expansion: ein zufällig gewähltes, noch nicht probiertes Kind anhängen. (3) Simulation: ab dem neuen Knoten ein selbstvermeidender Zufallslauf (Rollout), der endet, wenn er das Ziel erreicht, in einer Sackgasse steht oder \(H\) Schritte gemacht hat. (4) Rückpropagation: der Reward \(r\) der Simulation geht in alle Vorfahren. Erreicht der Abstieg selbst das Ziel, folgt \(r\) aus den Pfadkosten; eine Sackgasse im Baum gibt 0.
• Ergebnis: die beste je beobachtete Route, denn jede Simulation, die das Ziel erreicht, liefert eine gültige Route. Daneben gibt es den robusten Pfad, der von der Wurzel jeweils dem meistbesuchten Kind folgt; er endet nicht immer im Ziel.
• Regler: Iterationen \(I\) (100 bis 64 000, Voreinstellung 4000), UCB-Konstante \(c\) (0,25 bis 16, Voreinstellung 1), Rollout-Horizont \(H\) (10 bis 200, Voreinstellung 100), Rollout-Politik (gleichverteilt oder geführt durch \(h\)) und Reward (nur am Ziel oder mit Fortschritt). Die beiden letzten bringen Wissen aus \(h\) ins Verfahren; mit gleichverteiltem Rollout und Reward nur am Ziel heißt das Verfahren hier reines MCTS.
• Vergleich und Kennzahlen: Die Uniform-Cost-Suche findet das Optimum ohne Heuristik und dient als Basis; A* und Greedy Best-First (beide mit \(h\)) laufen auf denselben Netzen. Die Lücke ist \(100\,(L_{\text{best}} - L^*)/L^*\) mit den Kosten \(L_{\text{best}}\) der besten gefundenen Route, gezählt nur über Läufe mit Route. Dazu kommen der Anteil aller Läufe mit Route, mit Lücke höchstens 5 % und mit Lücke 0, der Anteil der Iterationen, die das Ziel erreichen (Ziel-Rollouts), und der Aufwand in Knotenbesuchen: Jede berührte Baumstufe und jeder Rollout-Schritt zählt 1. Eine Expansion der Uniform-Cost-Suche ist eine andere Einheit; beide sind nur der Größenordnung nach vergleichbar.
• Messdesign: Wenn nichts anderes steht, gelten Seitenlänge 12, 15 % Hindernisse, 4000 Iterationen, \(c = 1\) und \(H = 100\). Eine Konfiguration läuft auf 5 festen Netzen mit je 6 Zufallsstarts des MCTS-Zufallsgenerators, also 30 Läufen; angegeben wird der Median, die Lücke nur über Läufe mit Route.

Die Formeln

Selektion (UCB1). Unter den Kindern \(v\) des Knotens \(u\) wird dasjenige mit dem größten Wert gewählt; \(N(u)\) ist die Besuchszahl des Elternknotens, \(W(v)/N(v)\) der mittlere Reward des Kindes:

\[\arg\max_{v \in \text{children}(u)} \; \frac{W(v)}{N(v)} + c \sqrt{\frac{\ln N(u)}{N(v)}}\]

Reward einer Simulation. Erreicht sie das Ziel mit Gesamtkosten \(L\), ist der Reward höchstens 1, weil die Luftlinie \(d_0\) von Start zu Ziel nie größer als \(L\) ist; erreicht sie es nicht, ist er 0:

\[r = \min(1, d_0 / L)\]

Fortschritts-Reward (nutzt \(h\)): Auch eine Simulation, die das Ziel verfehlt, bekommt bis zu 0,5, je nach Luftlinie \(h(s_{\text{Ende}})\) am Ende:

\[r = \tfrac12 \max(0, 1 - h(s_{\text{Ende}}) / d_0)\]

Geführter Rollout (nutzt \(h\)): Der nächste Schritt wird unter den noch nicht besuchten Nachbarn \(v\) mit einer Wahrscheinlichkeit gezogen, die proportional ist zu

\[\propto \exp\!\big(-(h(v) - h_{\min}) / (\tau \bar w)\big)\]

mit \(h_{\min}\) als kleinstem \(h\) unter den Kandidaten, der Temperatur \(\tau = 0,5\) und der mittleren Kantenlänge \(\bar w\). Rückpropagation: Für jeden Vorfahren gilt \(N \mathrel{+}= 1\) und \(W \mathrel{+}= r\).

Herleitung Schritt für Schritt

Die Schritte sind Überlegungen und Rechnung dieser Seite, keine Messungen der Demo.

• Schritt 1, Bau von UCB1: Der Mittelwert \(W(v)/N(v)\) schätzt den Reward des Teilbaums unter \(v\) und belohnt Ausbeutung. Der Bonus \(c\sqrt{\ln N(u)/N(v)}\) fällt mit jedem Besuch des Kindes etwa wie \(1/\sqrt{N(v)}\) und wächst mit \(\ln N(u)\), solange das Kind nicht gewählt wird. Er wächst dann ohne Grenze; jedes Kind kommt also irgendwann wieder an die Reihe.
• Schritt 2, Wirkung von \(c\): Für \(c = 0\) zählt nur der Mittelwert, und der erste Treffer kann die Suche festhalten. Für sehr großes \(c\) dominiert der Bonus, und die Besuche verteilen sich nahezu gleich. Dazwischen liegt der Bereich, in dem die Suche zwischen Vertiefen und Erkunden wechselt.
• Schritt 3, enge Rewards: Hat eine Route die Kosten \((1+\gamma) L^*\), ist ihr Reward das \(1/(1+\gamma)\)-Fache des Rewards einer kürzesten Route. Bei einer Lücke von 17 % ist das gut ein Siebtel weniger. Zwischen guten und mittelmäßigen Routen trennen die Rewards also nur wenig, während „Ziel erreicht“ gegen „nicht erreicht“ ein Sprung von 0 auf einen positiven Wert ist. Das passt zur Vermutung, dass UCB1 auf kleinen Netzen ein großes \(c\) braucht. Auf Seitenlänge 12 ist \(c\) dagegen fast wirkungslos, was die Vermutung nicht erklärt; isoliert ist sie nicht.
• Schritt 4, spärlicher Reward: Ein Rollout hat nur dann einen Reward über 0, wenn er das Ziel innerhalb von \(H\) Schritten erreicht. Bei der Vierernachbarschaft braucht jede Route von der Ecke zur gegenüberliegenden Ecke mindestens \(2(n-1)\) Kanten, bei \(n = 12\) also mehr als 10. Ein Rollout nahe der Wurzel kann das Ziel bei \(H = 10\) daher nicht erreichen. Läufe mit Route entstehen dann, wenn der Baum selbst bis zum Ziel wächst oder Rollouts tief im Baum starten (Deutung, nicht getrennt gemessen).
• Schritt 5, Wirkung des geführten Rollouts: Ein Kandidat, dessen Luftlinie um \(\tau \bar w\) größer ist als die des besten, bekommt das Gewicht \(e^{-1}\) relativ zu ihm. Für \(\tau \to 0\) wird der Rollout greedy, für \(\tau \to \infty\) gleichverteilt. Er lenkt die Zufallsläufe zum Ziel und mildert damit das Problem der Nullrewards aus Schritt 4, ohne den Baum zu ändern.
• Schritt 6, Aufwand: Gut zwanzig Knotenbesuche je Iteration folgen aus dem Quotienten der unten genannten rund 81 000 Besuche und 4000 Iterationen. Gegenüber 121 Expansionen der Uniform-Cost-Suche sind das mehrere hundertmal so viele Zähleinheiten. Die Einheiten sind verschieden; die Aussage ist nur eine Größenordnung.
• Schritt 7, Monotonie: Bei gleichem Zufallsstart sind die ersten \(I\) Iterationen eines längeren Laufs dieselben wie bei einem kürzeren. Da das Ergebnis die beste je beobachtete Route ist, kann mehr Iterationen den besten Wert nicht verschlechtern.

Befunde

Alle Werte sind Mediane über 30 Läufe (5 Netze, 6 Zufallsstarts) bei Seitenlänge 12, 15 % Hindernissen, 4000 Iterationen, \(c = 1\) und \(H = 100\), wenn nichts anderes steht. Die Erfolgs-, Nah- und Optimal-Anteile laufen über alle Läufe, die Lücken nur über Läufe mit Route.

Qualität und Aufwand des reinen MCTS.

Frage	Befund
Findet reines MCTS Routen?	In 100 % der Läufe; bei Seitenlänge 22 in 93 %.
Wie gute?	Optimal in 0 % der Läufe, Lücke 17,1 %, Lücke höchstens 5 % in 0 % der Läufe. Greedy Best-First (mit \(h\)) auf denselben Netzen: 14,7 %.
Aufwand gegen Uniform-Cost	Uniform-Cost: 121 Expansionen (A*: 93) für das Optimum. MCTS: rund 81 000 Knotenbesuche für die Lücke von 17 % (verschiedene Einheiten).
Sperrwahrscheinlichkeit 0 / 10 / 20 / 30 / 40 %	Lücke 20,2 / 17,2 / 18,1 / 15,8 / 7,4 %. Bei 40 % sind 10 % der Läufe optimal und 40 % unter 5 %.
Rollout-Horizont \(H\) = 10	Nur 40 % der Läufe finden eine Route. Lücke bei \(H\) = 20 / 50 / 100 / 200: 17,6 / 19,2 / 17,1 / 17,1 %.

Wie schnell wird die Route besser? Die Lücke fällt mit den Iterationen, aber langsam.

Iterationen	250	1000	4000	16000
Lücke	40,0 %	28,2 %	17,1 %	8,5 %
Anteil der Läufe mit Lücke höchstens 5 %	0 %	0 %	0 %	20 %

Spärlicher Reward. Je größer das Raster, desto seltener erreicht eine Iteration das Ziel. Die Lücke steigt dabei nicht streng mit der Seitenlänge: Bei Seitenlänge 6 liegt sie über der bei 10. Für die Voreinstellung 12 liegt kein Einzelwert dieser Reihe vor.

Seitenlänge	6	10	14	18	22
Ziel-Rollouts	95,3 %	5,1 %	2,6 %	0,3 %	0,2 %
Lücke	5,6 %	2,0 %	21,5 %	41,7 %	67,8 %

Wie viel ist eingeschmuggeltes \(h\)? Dieselbe Konfiguration in vier Varianten. Der geführte Rollout ist der Hebel; ein Fortschritts-Reward allein bringt wenig. Was mit \(h\) übrig bleibt, ist Greedy Best-First mit Zufall und Baum.

Variante	Lücke, 4000 Iterationen	Anteil höchstens 5 %	Lücke, 16000 Iterationen	Anteil höchstens 5 %
rein (ohne \(h\))	17,1 %	0 %	8,5 %	20 %
mit Fortschritts-Reward	12,4 %	10 %	9,1 %	23 %
mit geführtem Rollout	2,4 %	83 %	1,3 %	93 %
mit beidem	3,2 %	80 %	0,5 %	100 %

Auf dem kleinen Raster (Seitenlänge 6) ist reines MCTS bei einer Lücke von 5,6 % in 23 % der Läufe optimal, geführt bei 0,0 % in 100 %. Auf dem großen (Seitenlänge 22) sinkt die Lücke mit geführtem Rollout von 67,8 % auf 7,0 %.

UCB-Konstante. Auf Seitenlänge 12 ist \(c\) fast wirkungslos. Auf einem 4 mal 4 großen Raster ohne Hindernisse (1000 Iterationen, 10 Netze mit je 3 Zufallsstarts) entscheidet es dagegen, ob die Suche das Optimum findet. Schon bei Seitenlänge 5 und 6 reicht \(c = 4\) nicht mehr: Der Optimal-Anteil sinkt auf 67 % und 7 % (gleiche Bedingungen). Die Wirkung von \(c\) hängt also von der Netzgröße ab.

\(c\)	0,25	1	4	16
Seitenlänge 4 ohne Hindernisse: Anteil optimal	10 %	67 %	100 %	100 %
Seitenlänge 12: Lücke	13,3 %	17,1 %	14,6 %	16,7 %

Auf Seitenlänge 12 liegen die Lücken für die übrigen Werte von \(c\) (0,5; 2; 8) bei 16,5 %, 17,6 % und 16,8 %.

Handgebaute Falle. Greedy Best-First folgt dem Köder in den Korridor (Lücke 7,5 %). MCTS ohne Heuristik fand den kürzeren Umweg in allen 10 getesteten Zufallsstarts, bei 200 wie bei 250 Iterationen. Bei Zufallsstart 1 kam die erste optimale Route nach 4 Knotenbesuchen; Uniform-Cost braucht 8, A* 7 Expansionen. Ein Rollout durch den Korridor erreicht das Ziel und bekommt Reward, nur weniger als der kürzere Weg (Rechnung dieser Seite aus der Netzgeometrie). Das ist ein einzelnes Netz mit 8 Knoten.

Ein Einzelfall durchgerechnet. Eine einzelne Instanz (Netz Nr. 35, Zufallsstart 1; nicht eines der 5 festen Netze der Mediane) weicht vom Median ab: reines MCTS hat dort eine Lücke von 22,8 % gegen 17,1 % im Median, bei rund 106 000 Knotenbesuchen; Uniform-Cost braucht 126, A* 82 Expansionen, das Optimum ist 175,9 km lang.

Einstellung (Netz Nr. 35, Zufallsstart 1)	Lücke dieses Laufs
reines MCTS	22,8 %
geführter Rollout	4,5 %
Fortschritts-Reward	19,5 %
Seitenlänge 22	84,5 %
250 Iterationen	36,8 %
40 % Hindernisse	14,3 %

Grenzen: was die Messung zeigt und was nicht

• Synthetische Netze: Alle Zahlen stammen von einem Raster mit verschobenen Zellmitten, Vierernachbarschaft und ungerichteten Kanten, dazu einer handgebauten Falle. Mediane über 30 Läufe auf 5 festen Netzen belegen die Aussagen; einzelne Läufe streuen stärker (Einzelfall oben).
• Reichweite der Befunde: „In keinem Lauf optimal“ gilt nur für Seitenlänge 12 bei 4000 Iterationen; für kleinere Raster und größeres \(c\) siehe die Tabellen. „Immer eine Route“ gilt bis Seitenlänge 18, bei 22 nicht. Die Lücke wird nur über Läufe mit Route gebildet; bei Seitenlänge 22 fehlen so Läufe ohne Route in der Statistik, und die Lücke fällt dadurch eher zu günstig aus.
• Ursachen nicht isoliert: Dass enge Rewards ein großes \(c\) verlangen, ist eine Vermutung. Ebenso bleibt offen, warum viele Hindernisse helfen (naheliegend: weniger Irrwege). Die Reward-Normalisierung und Einzelspieler-Varianten (SP-MCTS), die das \(c\)-Problem angehen könnten, sind nicht gebaut.
• Vergleich mit Greedy: Greedy Best-First benutzt \(h\), reines MCTS nicht; die Gegenüberstellung der Mediane (14,7 % gegen 17,1 %) vergleicht also Verfahren mit verschiedenem Wissen. Greedy ist deterministisch und hat kein Iterationsbudget, sein Median läuft über die 5 Netze. Nicht gemessen ist ein Vergleich mit reinen Zufallsläufen ohne Baum bei gleichem Budget; er würde zeigen, was UCB1 und der Baum zur Qualität beitragen.
• Fortschritts-Reward: Er ist nicht monoton im Erfolg: Eine Route mit Kosten über dem Doppelten von \(d_0\) bekommt weniger Reward als ein Rollout, der knapp vor dem Ziel endet (bis 0,5). Ob das erklärt, warum er allein wenig bringt, ist nicht untersucht (Rechnung dieser Seite).
• Streuung und Umsetzung: Angegeben sind Mediane; die Streubreite (10. bis 90. Perzentil) zeigt die Demo, diese Seite gibt sie nicht wieder. Im Baum wird jedes neue Kind sofort besucht, UCB1 vergleicht also nur besuchte Kinder; bei Gleichstand gewinnt das zuerst angelegte.
• Einheiten: Knotenbesuche und Expansionen sind verschiedene Zähleinheiten; der Vergleich gilt nur der Größenordnung nach.
• Problemklasse: Ein vollständig bekanntes, deterministisches Netz ist nicht das Terrain von MCTS; dort sind Uniform-Cost und A* exakt und mit weit weniger Aufwand zu haben. Das Verfahren ist für Spiele, Simulatoren und zufällige Übergänge gedacht; dort wurde es nicht gemessen.
• Nicht gebaut: RAVE, Transpositionstabellen, gelernte Bewertungen wie bei AlphaZero, Weighted A* und Stochastic Beam Search.
• Theorie: Für UCB1 bei unabhängigen Banditen mit Rewards in \([0,1]\) gibt es Schranken für das Bedauern, und UCT konvergiert unter bestimmten Bedingungen im Grenzwert; die Konvergenz kann aber sehr langsam sein (alles in diesem Punkt aus dem Gedächtnis, nicht geprüft). Der Beweis der UCB1-Schranke nutzt nach meiner Erinnerung den Faktor \(\sqrt{2}\) im Bonus, die Demo \(c = 1\). Außerdem misst die Demo endliche Läufe auf einem Baum mit Pfaden; die Garantien sind hier nicht nachgewiesen.

Verweise

Die Vergleichsverfahren Greedy Best-First und Uniform-Cost erklärt auch die Seite zu A*, das ebenfalls mit der Luftlinie arbeitet.

Quellen

• Kocsis, L., & Szepesvári, C. (2006): Bandit Based Monte-Carlo Planning. ECML 2006, LNCS 4212, 282–293.
• Auer, P., Cesa-Bianchi, N., & Fischer, P. (2002): Finite-time Analysis of the Multiarmed Bandit Problem. Machine Learning 47, 235–256.
• Browne, C. B. et al. (2012): A Survey of Monte Carlo Tree Search Methods. IEEE Transactions on Computational Intelligence and AI in Games 4(1), 1–43.
• Quelltext, Messreihen und Tests der Demo: github.com/sebastian-hanisch/mcts-demo.

Autoren, Jahr, Zeitschrift und Seiten stammen aus der Projektbeschreibung der Demo und wurden nicht nachgeschlagen; die Arbeiten selbst wurden für diese Seite nicht im Volltext gelesen. Die Formeln stützen sich auf die Messungen der Demo.