Monte Carlo Tree Search (MCTS)

In Spielen ohne klare Bewertungsfunktion. In Schach kann man sagen "Dame > Bauer". In Go ist das schwer. MCTS braucht keine Bewertungsfunktion. Es braucht nur die Regeln und "Wer hat am Ende gewonnen?". Auch in der Logistik oder Chemie (Retrosynthese), um Pfade in riesigen Suchräumen zu finden.

1. Die 4 Phasen

1. Selection: Wähle einen vielversprechenden Knoten aus (mit UCB1-Formel: Balance zwischen "Gut" und "Unbekannt").
2. Expansion: Füge einen neuen Zug zum Baum hinzu.
3. Simulation (Rollout): Spiele von dort zufällig bis zum Ende.
4. Backpropagation: Update die Gewinnstatistik aller Knoten auf dem Weg nach oben.

2. UCT (Upper Confidence bound applied to Trees)

Die Formel für Selection: $Value + C \cdot \sqrt{\frac{\ln N}{n}}$. $Value$: Wie oft habe ich hier gewonnen? (Exploitation). $N$: Wie oft war ich beim Elternknoten? $n$: Wie oft war ich hier? Wenn $n$ klein ist (selten besucht), wird der Term groß -> Wir probieren es aus (Exploration). Das garantiert, dass wir nicht im lokalen Optimum stecken bleiben.

1. AlphaGo Zero und Residual Neural Networks (PUCT)

Das epische AlphaGo der Google-Schmiede revolutionierte MCTS durch Vernichtung des menschlichen Master-Wissens (Heuristiken aus Büchern). AlphaGo Zero lernte Schach komplett aus sich selbst herus auf Null, ohne Pattern. Der Kern ist der modifizierte Selektor PUCT (Predictor UCT). Anders als das brutale Random-Rollout (Playouts bis zum Gameover als purer Zufalls-Walk), schmetterte Zero MCTS ein riesiges Deep ResNet in den Branching Faktor Knoten ein. Erreicht der Algorithmus ein Leaf, bewertet ein neuronales O(1)-Prädiktornetzwerk in Millisekunden sofort eine exakte Gewinnchance v im Spektrum $[-1, 1]$ (Value Head) und spuckt Policy Promiliarys ($P$) für die kindlichen Knoten Züge aus, anstatt blind und teuer in Random Walks 400 Schritte in die Zukunft in Rechenstau abzutauchen. Das eliminiert völlig die massive Schwäche von Zufallssimulationen in Brett-Winkeln, wo schon ein einzelner taktischer Missklick "plötzlich" den König verliert (was der Zufall zu selten im purem MCTS trifft, das ResNet es aber instinktiv blockt!).

2. Multi-Threading, Virtual Loss & Lock-Free Trees

MCTS lebt vom reinen Skalierungs-Brute-Force im RAM (Mehr Rollouts/Sekunde = Höhere ELO Stats bei gleicher Intelligenz). Parallelisierung der 1 Millionen RAM-Nodes generiert ein CPU-Gemetzel. Wenn 64 CPU Cores exzessiv in denselben Graph pushen und im Backpropagation Schritt die parent_visits ($N$) updaten, entsteht durch Locking-Mutexe massiver Stau (Thread Starvation). Trick 1 ist Leaf Parallelization (1 Node durchsucht The Tree, verteilt Rollout auf 64 Arbeiter). Das flacht Latenz. Trick 2 im Root-Tree ist Virtual Loss. Ein Worker pickt sich über UCB den heißesten Baumknoten aus, aber packt diesem Knoten einen bösen temporären Counter "Loss=-1" hinzu. Dadurch stürzt der Attraktivität-Score für die anderen 63 Workers brutal und asynchron ins Leere ab. Die restlichen Threads tauchen automatisch sofort in alle völlig anderen Breitengrade des Labyrinths tief hinein (Exploration Boost). Kehrt Tree-Walker 1 mit echtem Rollout Data-Paylod zurück, storniert die Lock-Free Update-Funktion das Virtual-Delay radikal, überschreibt atomar echt Werte und rebalanciert die Such-Struktur ohne Latenzbrüche nahtlos asynchron ins Nirvana der Baumtiefe.

3. Continuous und Partially Observable Action Spaces (POMDPs)

Klassisches MCTS versagt schmerzhaft bei Non-Board Games (wie Poker oder Starcraft), da die "Information" des Gegner-Tisches verdeckt operiert oder der Zug ("Bewege den Cursor um 1.3 cm") absolut kontinuierlich auf Realzahlen gleitet (unendlicher Branching Faktor statt endlicher $8\times8$ Kacheln). Methoden wie POMCP (Partially Observable Monte Carlo Planning) ergänzen MCTS, indem in der Root nicht "Hier steht der Bauer H2", sondern exakt "Particle Filter Probability States" verbaut werden. Die Simulation iteriert in Fantasie-Welten asynchron "Lass uns annehmen, der Feind hat Asse". Bei kontinuierlichen Steuerknüppeln konvertieren Forscher (z. B. durch Progressive Widening Trees UCB-Tunnel) die unendlichen Gleitkomma-Vektoren in limitierende diskrete Action-Budgets herunter, welche der Selektor adaptiv pro Sekunde neu granular fein-aufsplittet (K-Means Action Bins), um reale Robotik Bewegung zu simulieren.