Startseite▸KI & Maschinelles Lernen▸Monte-Carlo-Baumsuche — Spiel-KI

🌳 Monte-Carlo-Baumsuche — Spiel-KI

Beobachten Sie, wie MCTS einen Suchbaum über ein einfaches Spiel wachsen lässt, indem vier Phasen wiederholt werden — Auswahl mit UCB1, Erweiterung, zufälliges Rollout und Rückpropagation — und dabei starke Züge findet, ohne eine vollständige Spielbaumsuche.

KI & Maschinelles Lernen2DFortgeschritten60 FPS

Über Monte-Carlo-Baumsuche

Die Monte-Carlo-Baumsuche (MCTS) ist ein Algorithmus zum Finden starker Züge in sequentiellen Entscheidungsproblemen, wie Brettspielen, indem schrittweise ein Suchbaum durch wiederholtes zufälliges Abtasten aufgebaut wird. Jede Iteration durchläuft vier Phasen: Auswahl, die den Baum von der Wurzel aus mithilfe der UCB1-Formel — Gewinnrate + C·√(ln(Elternbesuche)/Kindbesuche) — durchläuft, um das Ausnutzen bekannt guter Züge gegen das Erkunden wenig besuchter Züge abzuwägen; Erweiterung, die einen neuen Knoten für einen unversuchten Zug hinzufügt; Rollout, das gleichverteilt zufällige Züge bis zu einem Endzustand spielt; und Rückpropagation, die Besuchs- und Gewinnstatistiken entlang des Pfads zurück zur Wurzel aktualisiert. Da MCTS Stellungswerte aus Simulationsergebnissen statt aus einer handgefertigten Heuristik schätzt, skaliert es gut für Spiele mit enormen Verzweigungsfaktoren, wie Go, wo eine erschöpfende Minimax-Suche rechnerisch unmöglich ist. Diese Eigenschaft machte MCTS zum Rückgrat von DeepMinds AlphaGo und, kombiniert mit tiefen neuronalen Netzen anstelle zufälliger Rollouts, von AlphaZero — Systemen, die menschliche Expertise in Go, Schach und Shogi übertrafen.

Häufig gestellte Fragen

Was sind die vier Phasen der Monte-Carlo-Baumsuche?

MCTS wiederholt bei jeder Iteration vier Phasen: Auswahl, die den Baum mithilfe von UCB1 durchläuft, um vielversprechende Kindknoten zu wählen; Erweiterung, die einen neuen Kindknoten für einen unversuchten Zug hinzufügt; Rollout (Simulation), das zufällige Züge bis zu einem Endzustand spielt; und Rückpropagation, die Besuchs- und Gewinnzähler für jeden Knoten auf dem Pfad zurück zur Wurzel aktualisiert. Tausendfache Wiederholung lässt einen asymmetrischen Baum wachsen, der sich auf starke Zugfolgen konzentriert.

Was ist UCB1 und wie balanciert es Exploration und Exploitation?

UCB1 (Upper Confidence Bound 1) bewertet jeden Kindknoten als Gewinnrate + C·√(ln(Elternbesuche)/Kindbesuche). Der Gewinnraten-Term bevorzugt Züge, die sich gut bewährt haben (Exploitation), während der Wurzel-Term für Kinder mit wenigen Besuchen größer wird (Exploration) und die Suche zu unterabgetasteten Zweigen zurückzieht. Die Konstante C = √2 balanciert die beiden Terme für auf 0 bis 1 skalierte Belohnungen.

Warum reicht ein zufälliges Rollout ohne handgefertigte Bewertungsfunktion aus?

Ein einzelnes zufälliges Rollout ist verrauscht, aber gemittelt über viele Simulationen liefern Rollout-Ergebnisse eine erwartungstreue statistische Schätzung der wahren Gewinnwahrscheinlichkeit einer Stellung. Dies erlaubt MCTS, Stellungen in Spielen zu bewerten, in denen der Entwurf einer genauen heuristischen Bewertungsfunktion — wie sie Minimax benötigt — schwierig oder unmöglich wäre, etwa bei Gos riesigen und mustergebundenen Brettzuständen.

Wo wird MCTS in realer Spiel-KI eingesetzt?

MCTS ist der zentrale Suchalgorithmus hinter DeepMinds AlphaGo, das 2016 die besten menschlichen Go-Spieler besiegte, und seinem Nachfolger AlphaZero, das Go, Schach und Shogi durch Selbstspiel meisterte. In diesen Systemen wurden die zufälligen Rollouts von MCTS durch die Wert- und Policy-Schätzungen eines trainierten neuronalen Netzes ersetzt, aber die Auswahl-Erweiterung-Rückpropagation-Struktur der Baumsuche blieb erhalten.

⚙ Unter der Haube

Monte Carlo Tree SearchGame AIUCB1Reinforcement learningCanvas 2D

2D · HTML5 Canvas 2D · 60 FPS target · runs fully client-side, no install