- Monte-Carlo Graph Search (MCGS) ist ein Ansatz, bei dem MCTS in Spielen, in denen mehrere Zugfolgen in denselben Zustand übergehen, auf einen gerichteten Graphen statt auf einen Baum angewendet wird, um redundante Suche gemeinsam zu nutzen.
- Überträgt man die Besuchszahl N und den durchschnittlichen Wert Q des klassischen MCTS unverändert auf einen DAG, kann die Besuchszahl eines gemeinsam genutzten Kindes von der Policy- und Wertschätzung des Elternknotens abweichen und den Algorithmus unsolide machen.
- Betrachtet man MCTS als regularisierte Policy-Optimierung, ist die von PUCT erzeugte Besuchsverteilung pro Aktion als Posterior-Policy zu verstehen, während Q der erwartete Nutzen dieser Policy ist.
- Ein korrektes MCGS verfolgt getrennt von den Besuchszahlen der Kindknoten die Kantenbesuche N(n,a) und berechnet Q aus
U(n) und der gewichteten Summe der Kind-Qs neu, sodass die Bedeutung von Policy und Wert auch im Graphen erhalten bleibt.
- In der praktischen Implementierung bleiben Entscheidungen wie stale Q, inkrementelle Updates, ob ein Playout bei einem transponierten Kind fortgesetzt wird, sowie der Umgang mit Hash-Kollisionen und Zyklen im Spiel; KataGo verwendet derzeit idempotente Updates.
Transponierte Zustände, die die Baumsuche übersieht
- In der Spielbaumsuche kommt es vor, dass unterschiedliche Zugfolgen in denselben Zustand transponieren (transposition).
- Im Schach erreichen
1. d4 d5 2. Nf3 und 1. Nf3 d5 2. d4 dieselbe Stellung.
- In Spielen mit möglichen Transpositionen kann die Zahl redundanter Zustände mit zunehmender Suchtiefe exponentiell wachsen; daher ist es wünschenswert, Berechnungen für denselben Zustand gemeinsam zu nutzen.
- Eine typische MCTS-Implementierung behandelt das Spiel als Verzweigungsbaum und durchsucht mehrere Instanzen derselben Stellung erneut.
- Low-Level-Optimierungen wie das Caching von neuronalen Netzbewertungen für wiederholte Stellungen können die Kosten senken.
- Es bleibt jedoch das Problem, dass eine in einer Instanz entdeckte wichtige Taktik und die dadurch korrigierte Bewertung nicht auf andere Instanzen übertragen werden.
- Modelliert man den Zustandsraum als gerichteten azyklischen Graphen (DAG), kann ein Zustand, den mehrere Pfade erreichen, als ein einzelner Knoten dargestellt werden.
- Die Behandlung tatsächlicher Zyklen in Spielen wird weitgehend ausgeklammert; der Fokus liegt darauf, wie MCTS in einem DAG funktionieren sollte.
Standard-MCTS: ein Baum aus Ausführungsstatistiken
- Standard-MCTS speichert den durchsuchten Teil eines Spiels als Knotenbaum im Speicher.
- Jeder Knoten verfolgt üblicherweise die folgenden Werte:
N: die Zahl der Playouts, die diesen Knoten bisher passiert haben oder an diesem Knoten endetenQ: der laufende Durchschnitt der Nutzenwerte, die diese Playouts gesampelt haben
- Ein einzelnes Playout läuft in folgender Reihenfolge ab:
- Es startet an der Wurzel und steigt ab, indem es gemäß einer Explorationsformel die nächste Aktion auswählt.
- Wenn es einen noch nicht untersuchten Zustand erreicht, wird ein neuer Knoten hinzugefügt.
- Für den neuen Zustand wird ein Nutzen
U ermittelt; im Beispiel ist das eine Anfrage an den Value Head eines neuronalen Netzes.
- Beim Zurücklaufen durch den Baum wird das
N jedes Knotens erhöht und der Durchschnitt Q aktualisiert.
- In MCTS im AlphaZero-Stil wird für die Aktionsauswahl die PUCT-Formel verwendet.
N(a): wie oft Aktion a ausprobiert wurde; im Baum entspricht das dem N des Kindknotens, auf den diese Aktion zeigtQ(a): der durchschnittliche Nutzen der Aktion a; er entspricht dem Q des KindknotensPlayerToMove: berücksichtigt, ob der aktuelle Spieler maximiert oder minimiertP(a): eine Prior-Wahrscheinlichkeit, etwa aus der Policy-Vorhersage des neuronalen Netzesc_PUCT: eine einstellbare Konstante
- „PUCT“ stammt aus der Familie von Predictor UCT/UCB mit vorhergesagten Prior-Verteilungen; die AlphaZero-Variante unterscheidet sich in ihrer Funktionsform vom Original.
- Moderne MCTS kann bei Nutzung neuronaler Netzbewertungen deterministisch sein, doch das „Monte-Carlo“ im Namen stammt von der früheren Methode, zufällige Rollouts bis zum Ende durchzuführen, um den Nutzen zu schätzen.
- Nachdem bis zum Ende des Rechenbudgets für einen Zug wiederholt Playouts durchgeführt wurden, wird an der Wurzel nicht das Kind mit dem höchsten
Q, sondern das Kind mit der größten Besuchszahl N als endgültige Aktion gewählt.
- Ein Kind mit hohem
Q und niedrigem N kann ein Fehler sein, der bei flacher Suche durch Rauschen zu gut aussieht.
- Die Besuchsverteilung an der Wurzel,
N(a) / ΣN(b), kann in der AlphaZero-Trainingsschleife als Ziel für das Policy-Lernen verwendet werden.
Probleme bei naiver Anwendung auf einen DAG
- Man kann den MCTS-Code für Bäume fast unverändert lassen und, wenn ein neuer Spielzustand bereits in
nodes_by_hash vorhanden ist, auf den existierenden Knoten verweisen.
- Dieser Ansatz erhält die Baumannahme nicht aufrecht, dass die Besuchszahl eines Kindknotens der Zahl der im Elternknoten gewählten Aktionen entspricht.
- Beispielsituation:
- Knoten A bevorzugt eine Aktion zu Knoten C, und das
Q von A wird überwiegend durch etwa 30 Playouts bestimmt, die C untersucht haben.
- C wurde über andere Transpositionspfade ebenfalls etwa 40-mal besucht.
- Später wird C über andere Transpositionspfade noch häufiger besucht; eine tiefere Taktik wird entdeckt, und C's Nutzenschätzung steigt von
0.39 → 0.51.
- Da die Playouts, die C aktualisiert haben, nicht über A liefen, spiegelt A's
Q die neue Bewertung von C nicht wider.
- Selbst wenn A später wieder Playouts erhält, kann PUCT statt des oft besuchten C andere Aktionen mit niedrigerer Besuchszahl explorieren.
- Denn C wirkt, als sei es „bereits ausreichend untersucht“.
- Dadurch kann A's
Q sogar sinken.
- Eine naive Grapherweiterung führt dazu, dass Elternknoten umso stärker andere Züge untersuchen, je häufiger Transpositionspfade ihre bevorzugten oberen Züge besuchen; das erzeugt eine künstliche Verzerrung im Playout-Durchschnitt.
- Der Algorithmus wird dadurch so unsolide, dass nicht klar ist, ob er selbst bei unendlicher Suche zum optimalen Zug konvergiert.
Auch das Aktualisieren aller Eltern löst das Problem nicht
- Man könnte auch erwägen, wenn ein Knoten durch ein Playout aktualisiert wird, diese Aktualisierung nicht nur auf die tatsächlich durchlaufenen Eltern, sondern auf alle Eltern und Vorfahren anzuwenden.
- Im vorherigen A-C-Beispiel könnte diese Methode A's Nutzen mit aktualisieren.
- In einem anderen Beispiel wird jedoch Elternknoten D durch viele Besuche eines transponierten Kindes F verunreinigt, das D selbst gar nicht bevorzugt.
- D's bestes Kind E hat
Q = 0.56, und D's Q = 0.55 passt dazu.
- D hat F nur einmal untersucht, aber F wurde über andere Pfade bereits 9-mal besucht und steht damit bei insgesamt 10 Besuchen.
- Wenn F danach über andere Pfade weitere 100-mal besucht wird und bei niedrigem Nutzen bleibt, kann die Methode, alle Eltern zu aktualisieren, D's
Q bis auf 0.35 herunterziehen.
- Aus Sicht von D wollte es F nicht so viele Playouts zuweisen; daher zerstört auch die Aktualisierung aller Eltern die Policy-Bedeutung.
MCTS als Policy-Optimierung betrachten
- Monte-Carlo Tree Search as Regularized Policy Optimization interpretiert MCTS aus Sicht des maschinellen Lernens.
- Die kumulative Besuchsverteilung, die PUCT an jedem Knoten durch wiederholte Auswahl erzeugt, approximiert die Lösung des folgenden Optimierungsproblems und konvergiert gegen sie:
Wert, den π maximiert:
Σ π(a) Q(a) - λ_N D_KL(P || π)
- Bedeutung der Komponenten:
Σ π(a) Q(a): der geschätzte erwartete Nutzen beim Folgen der Policy πD_KL(P || π): die reverse KL-Divergenz, die den Unterschied zwischen der Prior-Policy P und der Posterior-Policy π misstλ_N: ein Koeffizient, der die Stärke des KL-Terms festlegt und mit wachsender Besuchszahl abnimmt
- Die Besuchsverteilung kann als Posterior-Policy verstanden werden, die von der Prior-Policy
P des neuronalen Netzes ausgeht und sich mit mehr Besuchen verbessert, sobald sich Evidenz für die Aktionsnutzen ansammelt.
- MCTS lässt sich daher als Algorithmus interpretieren, der an jedem Knoten des Baums gleichzeitig ein kleines Online-Policy-Learning durchführt.
- Diese Sicht erklärt, warum die Besuchsverteilung wie die Policy eines starken Agenten aussieht und in AlphaZero als Ziel für das Policy-Lernen dient.
- Es wäre auch möglich, die exakte Lösung des Optimierungsproblems zu berechnen und als Policy zu verwenden; in der Praxis kann das jedoch Zügen mit wenigen Besuchen und zufällig hoch wirkendem
Q ein großes Gewicht geben.
- Nutzt man die Besuchsverteilung als Posterior-Policy, muss ein Zug tatsächlich viel untersucht worden sein, um ein hohes Gewicht zu erhalten, was robuster ist.
Neuinterpretation von Q: vom Playout-Durchschnitt zum Policy-Erwartungswert
- In der Standarddefinition ist
Q(n) eines Knotens n der Nutzendurchschnitt der Playouts, die n besucht haben.
Q(n) = (1 / N(n)) Σ U(p)
- Schreibt man dies aus Sicht der Kinder um, ergibt sich:
Q(n) = (1 / N(n)) ( U(n) + Σ N(c) Q(c) )
- Dabei ist
U(n) die rohe Nutzenschätzung des neuronalen Netzes für Knoten n, und N(c) Q(c) ist der mit den Besuchszahlen der einzelnen Kinder gewichtete Kindwert.
- Somit lässt sich
Q als besuchsverteilungsgewichteter Durchschnitt der Kind-Qs interpretieren.
- Wenn die Besuchsverteilung die von MCTS optimierte Posterior-Policy ist, dann ist
Q(n) der regularisierte erwartete Nutzen beim Folgen dieser Posterior-Policy.
- In dieser Interpretation optimiert jeder Knoten seine Policy fortlaufend, um die von den Kindern gemeldeten
Q-Werte zu maximieren, und aktualisiert sein eigenes Q als aktuelle Schätzung des unter dieser Policy erreichbaren erwarteten Nutzens.
- Wenn die
Q-Werte der Kindknoten gegen die spieltheoretisch optimalen Werte konvergieren, konvergieren auch die Policy und Q des Elternknotens rekursiv gegen den optimalen Wert.
Korrektes MCGS: Kantenbesuche und Kindbesuche trennen
- Das Problem im Graphen entsteht, weil angenommen wird, dass Kindbesuche eines Elternknotens ausschließlich über diesen Elternknoten erfolgen.
- Bei Transpositionspfaden kann die Besuchszahl eines Kindknotens beliebig von der Zahl der Besuche abweichen, die PUCT diesem Kind in diesem Elternknoten zuweisen wollte.
- Die Lösung besteht darin, die kumulative Zahl der Aktionen, die PUCT an einem bestimmten Knoten ausgewählt hat, separat zu verfolgen.
- Jeder Knoten
n verfolgt die folgenden Werte:
N(n): die Gesamtzahl, wie oft dieser Knoten besucht wurdeN(n,a): wie oft PUCT an Knoten n die Aktion a gewählt hat, also die KantenbesuchszahlQ(n) = (1 / N(n)) ( U(n) + Σ N(n,a) Q(n,a) )
- Dabei ist
Q(n,a) gleich Q(c) des Kindknotens c, der durch das Spielen von Aktion a erreicht wird.
- Auch in der PUCT-Berechnung werden nicht Kindbesuche, sondern Kantenbesuche verwendet.
argmax_a PlayerToMove(n) * Q(n,a)
+ c_PUCT P(n,a) sqrt(Σ N(n,b)) / (1 + N(n,a))
- Der Basisalgorithmus wählt die Aktionen eines Playout-Pfads aus, verbindet bei einem bereits existierenden transponierten Zustand mit dem vorhandenen Knoten, erhöht beim Zurücklaufen die Kantenbesuche und berechnet
N und Q als Funktion der Kindwerte neu.
- Diese Methode ähnelt auf hoher Ebene Monte-Carlo Graph Search for AlphaZero von Czech, Korus und Kersting, wird hier aber nicht aus Sicht von Ausführungsstatistiken, sondern aus Sicht der Policy-Optimierung hergeleitet.
Implementierungsoptionen: stale Q und Aktualisierungsmethoden
- Der gezeigte Pseudocode aktualisiert nur die Knoten des Pfads, den das Playout tatsächlich durchlaufen hat.
- Dadurch können
Q-Werte von Knoten auf nicht durchlaufenen Pfaden zu stale Q werden.
- Theoretisch ist das dennoch solide.
- Standard-Explorationsformeln wie PUCT probieren im Grenzfall alle Aktionen unendlich oft aus.
- Wenn ein Knoten erneut besucht wird, berechnet er mit den aktuellen Kind-
Q-Werten und Kantenbesuchen direkt das korrekte Q.
- In einem DAG kann er im Grenzfall zum spieltheoretisch optimalen Wert konvergieren.
- Stale Q kann die Sucheffizienz senken.
- Man kann unmittelbare Elternzeiger pflegen und auch Eltern-Q aktualisieren.
- Man kann alle Vorfahren in topologischer Reihenfolge aktualisieren und stale Zustände eliminieren.
- Man kann nur den Playout-Pfad aktualisieren und einen separaten parallelen Thread stale Knoten finden und aktualisieren lassen.
- Der Pseudocode verwendet idempotente Updates.
- Unabhängig davon, welche Zwischenaktualisierungen zuvor stattgefunden haben: Sobald ein Knoten einmal besucht wird, stimmen sein
N und Q für die aktuellen Werte seiner Kinder.
- Inkrementelle Updates sind ebenfalls möglich, im Graphen aber schwieriger gleichwertig oder im Grenzfall gleichwertig zu machen.
- Czech et al. gingen von Ausführungsstatistiken aus und verwenden daher stärker inkrementelle Formeln.
- Sie speichern neben den Kantenbesuchszahlen auch das Q der Kante.
- Sie haben einen Mechanismus, durch den stale Q schrittweise zum aktuellen Wert aufholt, sowie einen Fehlertoleranz-Hyperparameter.
- Der gezeigte Pseudocode zeigt, dass MCGS auch ohne neuen Fehlertoleranzparameter oder Speicherung von Kanten-Q funktionieren kann.
- KataGo verwendet derzeit die idempotente Formel.
Ob Playouts bei einem transponierten Kind fortgesetzt werden sollen
- In MCTS auf Bäumen sind das Erhöhen der Kantenbesuche und das Erhöhen der Kindbesuche dasselbe Ereignis.
- Im Graphen kann ein Kindknoten wegen Transpositionen bereits viel häufiger besucht worden sein als die betreffende Kante.
- In diesem Fall kann man den Kindknoten als bereits ausreichend besucht betrachten, das Playout abbrechen, nur die Kantenbesuche erhöhen und anschließend Eltern und Vorfahren aktualisieren.
- Gründe, die für einen Abbruch sprechen:
- Wenn die Kantenbesuche niedrig und die Kindbesuche hoch sind, kann der Grenzinformationsgewinn durch einen zusätzlichen Besuch dieses Kindes gering sein.
- Gründe, die für eine Fortsetzung sprechen:
- Ein Knoten, dessen Kindbesuche höher sind als seine Kantenbesuche, ist wahrscheinlich ein Knoten, in den mehrere Eltern transponieren; er beeinflusst daher mehr Eltern, sodass eine genaue Bewertung wichtig sein kann.
- Diese Entscheidung bleibt ein Experimentierfeld.
- Möglich ist auch ein Schwellenwertverfahren, das nur abbricht, wenn die Kindbesuche ausreichend stark über den Kantenbesuchen liegen.
- KataGo bricht Playouts standardmäßig ab, bietet aber Konfigurationsoptionen, sie fortzusetzen oder nur stochastisch einen Teil abzubrechen.
- Der Pseudocode bricht Playouts nicht ab; bei Bedarf kann mit der Bedingung
child.N <= edge_visits eine einzeilige Prüfung hinzugefügt werden.
Hashes, Endknoten und tatsächliche Spielzyklen
- Endknoten eines Spiels werden im Pseudocode unabhängig von der Besuchszahl mit
N = 1, U = Q = Nutzen des Spielergebnisses neu berechnet.
- Die Besuchszahl der entsprechenden Kante im Elternknoten steigt normal, daher ist diese Methode möglich.
- Wenn das Spielergebnis stochastisch ist und der erwartete Nutzen nicht direkt berechnet werden kann, kann es wichtig sein,
N bei jedem Besuch eines Endknotens zu erhöhen und die gesampelten Ergebnisse zu mitteln.
- Es ist auch möglich, Endnutzen umfassender zu behandeln und beweisbare Werte schneller im Graphen nach oben zu propagieren.
- Allgemeines MCTS/MCGS besitzt keinen Mechanismus, um sichere Nutzenwerte zu erkennen; wenn Endzustände wichtig sind, konvergiert es daher nicht so günstig zum Optimalwert wie klassische Suche à la alpha-beta.
- Um Transpositionen zu finden, wird ein eindeutiger Hash des Spielzustands angenommen.
- Einen wirklich kollisionsfreien Hash für komplexe Spielzustände zu erzeugen, kann schwierig und teuer sein.
- Ein ausreichend großer Zobrist-Hash mit 128 oder 192 Bit reicht in der Praxis üblicherweise aus, um Kollisionen faktisch zu verhindern, solange Zustände nicht adversarial konstruiert wurden.
- Um bei einem durch Hash-Kollisionen entstandenen Zyklus unendliche Rekursion zu vermeiden, kann eine Zyklenerkennung hinzugefügt werden.
- Die Behandlung von Zyklen, die aus echten Spielregeln entstehen, wie Superko im Go oder dreifache Stellungswiederholung im Schach, wird nicht im Detail behandelt.
- Der Anhang vom 10.03.2024 verweist auf ein Google Doc mit gröberen Überlegungen zu Wiederholungen und Zyklusbehandlung; Experimente mit spielspezifischen Heuristiken können nötig sein.
- KataGos Go-Behandlung nutzt ein Go-spezifisches Theorem, nach dem es mindestens
S + E - 1 Züge braucht, um nach einem bestimmten Zug zur ursprünglichen Stellung zurückzukehren, und begrenzt damit das Teilen von Knoten in zyklusrelevanten Situationen stabil.
1 Kommentare
Hacker-News-Kommentare
Ich denke, dass eine solche Graphsuche nötig ist, um KI-Schlussfolgern voranzubringen. Mit einem reinen LLM allein ist die Wahrscheinlichkeit groß, dass es scheitert
Im Link gibt es viele gute Referenzen, darunter Zobrist-Hashing für Spieltabellen https://en.wikipedia.org/wiki/Zobrist_hashing
Man muss ein gutes Hashing finden, das zu sprachbasierten Zustandsbeschreibungen passt, damit der Rechenaufwand der Graphsuche nicht explodiert
Zur Baumsuche lohnt sich auch ein Blick auf Thinking Fast and Slow: https://arxiv.org/abs/1705.08439 sowie auf Teaching Large Language Models to Reason with Reinforcement Learning, das den MCTS-Ansatz mit anderen aktuellen Reinforcement-Learning-Strategien vergleicht: https://arxiv.org/abs/2403.04642
Ein Schritt weiter wäre womöglich, Zustandsrepräsentation und Suchalgorithmus gemeinsam zu lernen. Dabei würde der Suchalgorithmus über einer Zustandsrepräsentation des neuronalen Netzes suchen, aus der er Kosten ableiten kann
https://sites.google.com/view/genie-2024/
Genie von DeepMind ist ein gutes Beispiel für die Modellierung diskreter Zustände. Das neuronale Netz lernt eine sehr komplexe Repräsentation einschließlich Kollisionserkennung und Aktionen. Anstatt diesen Zustand in Pixel zu dekodieren, könnte man vermutlich direkt darüber suchen
Natürlich kann diese Struktur in der Praxis ziemlich anders aussehen
Man nimmt eine Sammlung logischer Argumente, findet eine Methode, jedem Argument einen Hash zuzuweisen, und stellt diese Argument-Hashes als Merkle-Baum dar, der gemäß ersten Prinzipien geschichtet ist
Wenn ein Argument erfolgreich widerlegt wird, ändert sich der Hash dieses Arguments, und die Hashes der untergeordneten Argumente werden ebenfalls ungültig
Anhand des HN-URLs und des Autors habe ich sofort erkannt, dass es das Genie ist, das KataGo gebaut hat: https://github.com/lightvector/KataGo
Auch die Beiträge auf https://www.reddit.com/r/cbaduk/ sind konstant hervorragend
Ich habe nicht extrem viel Erfahrung mit Schach, bin aber skeptisch gegenüber der Behauptung, dass sich dieselbe Position im Suchbaum oft genug wiederholt, um wichtig zu sein. Ich würde gern echte Messwerte mit Leela Zero sehen
Wenn man dreifache Stellungswiederholung und die 50-Züge-Regel in den Zustand aufnimmt, dürfte die Wiederholungswahrscheinlichkeit deutlich geringer sein, und selbst ohne diesen Punkt einzubeziehen denke ich das
Ich finde die Stelle seltsam, dass im obigen Algorithmus trotz des Namens „Monte-Carlo Tree Search“ überhaupt kein Monte Carlo vorkommt und alles vollständig deterministisch ist. Ich dachte, die üblicherweise implementierte MCTS sei deterministisch, obwohl es beim Sampling Zufälligkeit gibt
In heutigen ähnlichen Projekten wird das durch hochwertigere Bewertungen mit neuronalen Netzen ersetzt. Zufällige Züge zu spielen, um zu sehen, wer gewinnt, ist nicht besonders gut, war damals aber die beste bekannte Strategie
Letztlich war der Monte-Carlo-Teil auch damals kein wesentlicher Bestandteil dessen, was heute noch MCTS genannt wird, sondern eher die zweitbeste Lösung. Deshalb ist der Name etwas unglücklich
Interessant ist, dass die meisten Monte-Carlo-Methoden keine echten Zufallszahlengeneratoren verwenden, sondern Pseudozufallszahlengeneratoren, sodass bei gleichem Seed und gleichem Input immer dasselbe Ergebnis herauskommt, also deterministisch
Dieser Algorithmus fragt statt eines allgemeinen Pseudozufallszahlengenerators mit separater Heuristik ein neuronales Netz ab. Das neuronale Netz ist eine Heuristik über einem riesigen Suchraum und wirkt je nach Training wie ein extrem schlechter Pseudozufallszahlengenerator, der stark zu bestimmten Ergebnissen verzerrt ist; dadurch sieht es letztlich wie ein heuristisch gesteuerter Pseudozufallszahlengenerator aus
Wichtig ist, dass dies eine Spezialisierung von MCTS ist und daher technisch nicht für alle Anwendungsfälle passt
Als ich MCTS untersucht habe, war die im Beitrag erwähnte Arbeit komplett unter meinem Radar. Bei Gelegenheit wäre es ziemlich interessant, diese Modifikation selbst laufen zu lassen
Eine kurze Einführung wäre hilfreich
In Spielen, in denen man denselben Zustand über mehrere Wege erreichen kann, kann viel Speicher verschwendet werden, weil derselbe Zustandsknoten in verschiedenen Ästen mehrfach abgelegt wird
Dieser Beitrag betrachtet den Ansatz der Graphsuche sehr gut. Im Kern investiert man zusätzliche Rechenarbeit in das Hashing des Spielzustands, um zu prüfen, ob ein Knoten schon besucht wurde, und spart dafür Speicher
Weil bereits gesehene Knoten nicht erneut gespeichert werden müssen, wird der kreisfreie Baum zu einem gerichteten azyklischen Graphen
Deshalb muss man die Baumsuche etwas anpassen, um korrekte Ergebnisse zu erhalten. Insbesondere sollte sich die Optimierungseinheit eher an Kanten, also Aktionen oder Zügen, orientieren als an Knoten, also Zuständen
Ein gut geschriebener technischer Essay im Stil des literarischen Programmierens, verfasst von jemandem, der das Thema wirklich verstanden hat