Monte-Carlo-Graphsuche ausgehend von den Grundprinzipien

(github.com/lightvector)

3 Punkte von GN⁺ 2024-03-11 | 1 Kommentare | Auf WhatsApp teilen

Grundprinzipien der Monte-Carlo-Graphsuche

Die Monte-Carlo-Baumsuche (MCTS) lässt sich statt auf Bäume auch auf gerichtete Graphen anwenden, als „Monte-Carlo-Graphsuche“ („MCGS“), was mitunter als schwierig zu implementieren gilt.
Die bestehende wissenschaftliche Literatur folgt meist der „Standard“-Erklärung von MCTS für Bäume, weshalb die Verallgemeinerung auf Graphen konzeptionell schwer zu verstehen ist.
Dieses Dokument präsentiert eine als intuitiver angesehene Erklärung, die im Wesentlichen äquivalent ist, aber sauberer formuliert ist, und leitet aus den Grundprinzipien her, warum Graphsuche auf diese Weise funktionieren muss.

Bei der Spielbaumsuche oder anderen Anwendungen der Baumsuche kann es mehrere mögliche Sequenzen von Zügen oder Aktionen geben, die zum selben Zustand führen.
Zum Beispiel führt im Schach 1. d4 d5 2. Nf3 zur gleichen Stellung wie 1. Nf3 d5 2. d4.
Wenn solche Situationen in Spielen möglich sind, wächst die Zahl der Möglichkeiten zusammen mit der Suchtiefe exponentiell, wodurch tiefe Suche teurer wird als nötig.
Idealerweise möchte man, dass solche Verzweigungen der Suche Berechnungen gemeinsam nutzen.
Standardimplementierungen von MCTS behandeln das Spiel jedoch als Verzweigungsbaum und durchsuchen doppelte Positionen im Baum ineffizient erneut.

MCTS wird oft als ein Algorithmus beschrieben, der Laufzeitstatistiken von Playouts verfolgt, die durch Knoten eines Baums verlaufen.
Jeder Knoten repräsentiert einen einzelnen Spielzustand und verfolgt die Besuchszahl (N) sowie den laufenden Mittelwert (Q) der durch Playouts gesampelten Utility-Werte.
Eine einzelne Iteration oder ein einzelnes Playout von MCTS besteht darin, den Baum hinabzugehen und die nächste zu untersuchende Aktion zu sampeln, den Baum zu erweitern, wenn ein neuer Zustand erreicht wird, die Utility U des neuen Zustands zu schätzen und dann den Baum wieder hinaufzugehen, wobei in jedem Knoten N erhöht und der Mittelwert Q mit der neu gesampelten Utility U aktualisiert wird.

Wendet man den obigen Algorithmus unverändert auf einen gerichteten azyklischen Graphen statt auf einen Baum an, kann der Algorithmus ungenau werden.
Das liegt daran, dass MCTS als Erweiterung von Methoden auf Basis des Multi-Armed-Bandit-Problems üblicherweise im Sinne von Laufzeitstatistiken einzelner Playouts erklärt wird.
Czech, Korus und Kersting haben dieses Problem gelöst und einen korrekten Algorithmus entwickelt, es gibt jedoch auch einen alternativen Ansatz, MCTS aus der Perspektive des Online-Policy-Lernens zu betrachten.
In dieser alternativen Erklärung ergibt sich die Verallgemeinerung auf Graphen relativ natürlich.

Wenn MCTS Statistiken in verschiedenen Knoten aktualisiert, führt es in Wirklichkeit eine Form von Online-Policy-Lernen aus.
Die Besuchsverteilung von MCTS stellt näherungsweise eine „posteriori“ Policy dar, die die Prior-Policy P aus dem neuronalen Netz schrittweise verbessert, um die erwartete Utility zu maximieren.

Alle Probleme, die bei der Erweiterung von MCTS auf Graphen auftreten, entstehen aus der Annahme, dass nur Besuche eines Kindknotens vom Elternknoten aus zählen.
Die Theorie garantiert, dass die von PUCT gewählten kumulierten Aktionszahlen eine posteriori Policy liefern, die die optimierte Policy π approximiert; genau das sollte daher verfolgt werden.
Nutzt man die Interpretation, dass die von einem Knoten gemeldeten Q-Werte erwartete Werte der posteriori Policy sind, kann man die rekursive Q-Formel anwenden, ohne behandeln zu müssen, wie einzelne Playouts berechnet werden.

Der in diesem Dokument vorgestellte Algorithmus ist dem Algorithmus von Czech, Korus und Kersting sehr ähnlich, weist aber einige Implementierungsentscheidungen und ein paar kleinere Unterschiede auf.
Es gibt mehrere Möglichkeiten, sich der Einfachheit der Implementierung halber zu entscheiden, etwa Strategien zur Verringerung der „Veraltetheit“ von Q-Werten oder die Verwendung gleicher Updates anstelle schrittweiser Updates.

Dieser Artikel dürfte für Menschen interessant sein, die sich für Künstliche Intelligenz und Spieltheorie interessieren, da er die Komplexität der Monte-Carlo-Graphsuche (MCGS) und einen neuen Ansatz zu ihrem Verständnis darstellt.
Algorithmen wie MCTS spielen eine wichtige Rolle in komplexen Strategiespielen wie Schach oder Go und tragen zur Entwicklung von KI für solche Spiele bei.
Der in diesem Artikel behandelte Inhalt könnte für Software Engineers auf Einstiegsniveau jedoch recht anspruchsvoll sein und theoretisches Hintergrundwissen erfordern.
Bei der Implementierung von MCGS ist zu berücksichtigen, wie sich Effizienz und Genauigkeit des Algorithmus ausbalancieren lassen, was großen Einfluss auf die Leistung in realen Spielumgebungen haben kann.
Ein anderes Projekt oder Produkt mit ähnlicher Funktionalität ist DeepMinds AlphaZero, das in Schach, Go und Shogi ein Niveau erreicht hat, das die besten menschlichen Spieler übertrifft.

GN⁺ 2024-03-11

Graph Search ist für Fortschritte beim Reasoning von KI notwendig; einfache LLMS werden scheitern. Im Link gibt es viele gute Referenzen, darunter Zobrist-Hashing für Spieltabellen. Man muss gutes Hashing für sprachbasierte Zustandsbeschreibungen finden, damit Graph Search rechnerisch nicht explodiert. Gute Lektüre zur Tree Search sind "Thinking Fast and Slow" und "Teaching Large Language Models to Reason with Reinforcement Learning", die den MCTS-Ansatz mit anderen aktuellen RL-Strategien vergleichen.
Ich habe den genialen Entwickler von KataGo direkt an der HN-URL erkannt. Seine cbaduk-Beiträge auf Reddit sind durchweg hervorragend.
Beim Namen "Monte-Carlo Tree Search" sollten Leser bemerken, dass der erwähnte Algorithmus kein "Monte-Carlo" enthält und vollständig deterministisch ist. Es ist merkwürdig, dass MCTS typischerweise deterministisch implementiert wird. Ich hatte angenommen, dass beim Sampling Zufälligkeit im Spiel ist.
Die erwähnte Arbeit war bei meiner Beschäftigung mit MCTS komplett unter meinem Radar. Es wäre sehr spannend, diese Modifikation bei der nächsten Gelegenheit auszuprobieren.

Hintergrundwissen:

LLMS: In diesem Kontext bezieht sich LLMS nicht auf eine bestimmte Technik, sondern kann allgemeine Machine-Learning-Systeme meinen.
Zobrist-Hashing: Eine Technik zum effizienten Hashing von Spielzuständen, die besonders häufig bei Brettspielen verwendet wird.
MCTS (Monte-Carlo Tree Search): Ein Algorithmus, der durch zufälliges Sampling optimale Entscheidungen trifft und meist in Entscheidungsprozessen wie Spielen eingesetzt wird.
Reinforcement Learning (RL): Ein Teilgebiet des Machine Learning, das durch Versuch und Irrtum lernt und über ein Belohnungssystem optimale Handlungsstrategien erarbeitet.