Not logged inCSS-Forum
Forum CSS-Online Help Search Login
CSS-Shop Impressum Datenschutz
Up Topic Hauptforen / Schachprogrammierung / Monte Carlo Tree Search (MCTS)
- - By Lothar Jung Date 2021-07-13 10:09 Edited 2021-07-13 10:19 Upvotes 1
Wichtige Quellen:

https://www.ke.tu-darmstadt.de/lehre/arbeiten/bachelor/2012/Arenz_Oleg.pdf

https://de.wikipedia.org/wiki/Monte-Carlo-Algorithmus?wprov=sfti1

https://www.chessprogramming.org/Monte-Carlo_Tree_Search
Parent - - By Jörg Oster Date 2021-08-14 17:38 Upvotes 1
Lothar Jung schrieb:

Wichtige Quellen:

<a class='ura' href='https://www.ke.tu-darmstadt.de/lehre/arbeiten/bachelor/2012/Arenz_Oleg.pdf'>https://www.ke.tu-darmstadt.de/lehre/arbeiten/bachelor/2012/Arenz_Oleg.pdf</a>

<a class='ura' href='https://de.wikipedia.org/wiki/Monte-Carlo-Algorithmus?wprov=sfti1'>https://de.wikipedia.org/wiki/Monte-Carlo-Algorithmus?wprov=sfti1</a>

<a class='ura' href='https://www.chessprogramming.org/Monte-Carlo_Tree_Search'>https://www.chessprogramming.org/Monte-Carlo_Tree_Search</a>


Der erste Link ist durchaus lesenswert.
Gut verständlich, finde ich, und die Vor- und Nachteile werden gut dargestellt.

Einen gravierenden Nachteil können wir auch gerade bei TCEC VVLT-Bonus live in Aktion sehen.
Parent - - By Peter Martan Date 2021-08-14 21:32 Edited 2021-08-14 21:48 Upvotes 1
Jörg Oster schrieb:

Einen gravierenden Nachteil können wir auch gerade bei TCEC VVLT-Bonus live in Aktion sehen.

Du meinst, dass sich die lange TC weniger bezahlt macht als für die A-B-Suche?
Sag ich schon lange, lässt sich aber außer an einzelnen Stellungen sehr schwer statistisch relevant beweisen, jetzt haben wir bei dem VVLTC gerade mal 3 Partien nach 2 Tagen.
Lustig aber, dass jede gegen jede andere Engine je einmal verloren und einmal gewonnen hat. Nur so zum anderen Thema Transitivität im Computerschach der Neuzeit, wenngleich hier jetzt wohl einfach jedesmal die weiße Seite zu stark im Vorteil aus der Eröffnung gekommen ist.
Und 3 Partien sind sowieso nix, aber 2xA-B auf CPU gegen 1xPUCT auf GPU ist halt auch der typische Ungleichheitsfall, was die Teilnehmer angeht.

   Program                            Score     %    Av.Op.  Elo    +   -    Draws

  1 KomodoDragon 2774.00           :   1.0/  2  50.0   3500   3500  600 600    0.0 %
  2 Stockfish 14_202108051641      :   1.0/  2  50.0   3500   3500  600 600    0.0 %
  3 LCZero 0.28-dev+_69722-vf2     :   1.0/  2  50.0   3500   3500  600 600    0.0 %


Individual statistics:

1 KomodoDragon 2774.00      : 3500    2 (+  1,=  0,-  1), 50.0 %

Stockfish 14_202108051641     :   1 (+  1,=  0,-  0), 100.0 %
LCZero 0.28-dev+_69722-vf2    :   1 (+  0,=  0,-  1),  0.0 %

2 Stockfish 14_202108051641 : 3500    2 (+  1,=  0,-  1), 50.0 %

KomodoDragon 2774.00          :   1 (+  0,=  0,-  1),  0.0 %
LCZero 0.28-dev+_69722-vf2    :   1 (+  1,=  0,-  0), 100.0 %

3 LCZero 0.28-dev+_69722-vf2: 3500    2 (+  1,=  0,-  1), 50.0 %

KomodoDragon 2774.00          :   1 (+  1,=  0,-  0), 100.0 %
Stockfish 14_202108051641     :   1 (+  0,=  0,-  1),  0.0 %
Parent - By Jörg Oster Date 2021-08-15 12:50 Upvotes 3
Peter Martan schrieb:

Jörg Oster schrieb:

Einen gravierenden Nachteil können wir auch gerade bei TCEC VVLT-Bonus live in Aktion sehen.

Du meinst, dass sich die lange TC weniger bezahlt macht als für die A-B-Suche?


Das auch.
Sobald der Suchbaum erstmal aufgebaut ist, mit mehreren Tausenden, evtl. sogar Millionen von visits in den niedrigeren plies,
haben die neueren Bewertungen der entfernteren Positionen kaum eine Chance,
noch grundlegend was an der Bewertung und damit an der Zugauswahl zu ändern.
Sie gehen quasi in der Masse der früheren Bewertungen unter.

Mir ging es aber mehr darum, dass MCTS Probleme damit hat, sog. search traps zu entdecken.
Lc0 kann das meistens durch die Bewertungen und die Zugprioritäten kompensieren.
Aber halt nicht immer.

Eine AB-Suche kann da mehr oder weniger sofort reagieren, egal ob bisher 20 Tausend
oder auch 20 Milliarden Stellungen durchsucht wurden!

Man müsste also sowas wie einen "Reset" bei einer MCTS machen, damit die neueren Bewertungen wieder besser greifen können.
Ich habe aber keine Ahnung, wie das gehen sollte. Und ob überhaupt.

Gruß,
Jörg.
Parent - By Lothar Jung Date 2021-08-16 13:22 Upvotes 1
Hier einige Veröffentlichungen zur Parallelisierung von MCTS:

MCTS, Tree Parallelization, Lock-free Tree, Synchronization Overhead, and Memory Ordering

https://liacs.leidenuniv.nl/~plaata1/papers/paper_ICAART18.pdf

https://dke.maastrichtuniversity.nl/m.winands/documents/multithreadedMCTS2.pdf

https://arxiv.org/pdf/2003.13741.pdf

https://www.researchgate.net/publication/220951246_Large-Scale_Parallel_Monte_Carlo_Tree_Search_on_GPU
Parent - By Jörg Oster Date 2022-11-03 14:26 Upvotes 2
Aus dem CCC übernommen:
Monte-Carlo Tree Search Solver
https://dke.maastrichtuniversity.nl/m.winands/documents/uctloa.pdf

Behandelt das Problem einer MCTS und Matt-Bewertungen.
- - By Lothar Jung Date 2021-08-12 18:58 Upvotes 1
Hier MCTS-Suchroutinen von Lc0 mit Figurenbewertungen:

https://github.com/LeelaChessZero/lc0/blob/master/src/mcts/search.cc
Parent - By dkappe Date 2021-08-13 03:08 Upvotes 3
A0lite, etwas übersichtlicher und in python.

https://github.com/dkappe/a0lite
- By Lothar Jung Date 2021-08-27 10:28 Upvotes 1
Hier eine Veröffentlichung über „ Monte-Carlo Graph Search for AlphaZero“:

https://arxiv.org/pdf/2012.11045v1.pdf
- By Lothar Jung Date 2021-09-26 11:52 Upvotes 1
Hier eine Veröffentlichung über „Dual Monte Carlo Tree Search“:

https://arxiv.org/pdf/2103.11517.pdf?
- - By Lothar Jung Date 2021-11-11 17:42 Upvotes 1
Multiple Policy Value Monte Carlo Tree Search

https://arxiv.org/pdf/1905.13521.pdf
Parent - By Lothar Jung Date 2022-01-12 21:11 Upvotes 1
Hier die grundlegende Veröffentlichung über PUCB:

http://gauss.ececs.uc.edu/Workshops/isaim2010/papers/rosin.pdf
- By Lothar Jung Date 2022-05-22 17:22 Upvotes 1
https://www.chessprogramming.org/UCT

Hier eine Beschreibung von UTC:

UCT (auf Bäume angewendete obere Vertrauensgrenzen),
Ein beliebter Algorithmus, der sich mit dem Fehler der Monte-Carlo-Baumsuche befasst, wenn ein Programm einen verlorenen Zug mit nur einer oder wenigen erzwungenen Widerlegungen bevorzugt, aber aufgrund der überwiegenden Mehrheit anderer Züge eine bessere zufällige Playout-Punktzahl liefert als andere,  bessere Bewegungen.  UCT wurde 2006 von Levente Kocsis und Csaba Szepesvári eingeführt [1], was die Monte-Carlo-Revolution im Computer-Go [2] und statisch schwer zu bewertenden Spielen beschleunigte.  Bei unbegrenzter Zeit und unbegrenztem Speicher konvergiert UCT theoretisch zu Minimax.
- - By Lothar Jung Date 2022-05-25 09:27 Upvotes 1
Monte-Carlo tree search as regularized policy optimization:

https://arxiv.org/pdf/2007.12509.pdf
Parent - - By Jörg Oster Date 2022-05-25 13:14 Upvotes 1
Lothar Jung schrieb:

Monte-Carlo tree search as regularized policy optimization:

<a class='ura' href='https://arxiv.org/pdf/2007.12509.pdf'>https://arxiv.org/pdf/2007.12509.pdf</a>

Um was geht es denn da in der Hauptsache?

Ich finde es ja durchaus bemerkenswert, was du so alles hier zusammenträgst.
Danke mal dafür an dieser Stelle. 
Parent - By Lothar Jung Date 2022-05-25 17:28 Upvotes 2
Hallo Jörg,

Danke für Deine Wertschätzung meiner Arbeit an dem Thema.

Zusammenfassung der Veröffentlichung:

„Die Kombination von Monte-Carlo Tree Search (MCTS) mit Deep Reinforcement Learning hat zu bedeutenden Fortschritten in der künstlichen Intelligenz geführt.  Allerdings stützt sich AlphaZero, der aktuelle State-of-the-Art-MCTS-Algorithmus, immer noch auf handgefertigte Heuristiken, die nur teilweise verstanden werden.  In diesem Artikel zeigen wir, dass die Suchheuristiken von AlphaZero zusammen mit anderen gebräuchlichen wie UCT eine Annäherung an die Lösung eines spezifischen Problems der regularisierten Richtlinienoptimierung sind.  Mit dieser Erkenntnis schlagen wir eine Variante von AlphaZero vor, die die exakte Lösung für dieses Problem der Richtlinienoptimierung verwendet, und zeigen experimentell, dass sie den ursprünglichen Algorithmus in mehreren Domänen zuverlässig übertrifft.“

Die Veröffentlichung wurde bei Discord kürzlich empfohlen.
Sie sei mathematisch ausführlich unterlegt und für die Entwicklung der Suche von Lc0 maßgebend.

Lothar
Parent - By Lothar Jung Date 2022-05-29 10:05 Upvotes 1
Hier eine weitere wichtige Veröffentlichung „MCTS Based on Simple Regret“:

https://arxiv.org/pdf/1207.5536.pdf
- By Lothar Jung Date 2022-06-07 14:46 Upvotes 1
POLICY GRADIENT ALGORITHMS WITH MONTE-CARLO TREE SEARCH FOR NON-MARKOV DECISION PROCESSES

https://arxiv.org/pdf/2206.01011.pdf
- By Lothar Jung Date 2022-06-16 16:30 Upvotes 1
Hier eine weitere Veröffentlichung zu MCTS: Convex Regularization in Monte-Carlo Tree Search

https://arxiv.org/pdf/2007.00391.pdf
- By Lothar Jung Date 2022-07-30 16:38 Upvotes 1
Hier eine Veröffentlichung über „Monte-Carlo tree search as regularized policy optimization“:

https://arxiv.org/pdf/2007.12509.pdf
- By Lothar Jung Date 2022-08-30 12:26 Upvotes 1
Hier die Veröffentlichung „Accelerating Monte-Carlo Tree Search on CPU-FPGA Heterogeneous Platform“:

https://arxiv.org/pdf/2208.11208.pdf
- By Lothar Jung Date 2022-09-03 17:07 Edited 2022-09-03 17:57 Upvotes 1
Veröffentlichung „Tree Search Algorithms For Chinese Chess“

Kombinierte A/B und MCTS Suche

https://drpress.org/ojs/index.php/HSET/article/view/1358/1289

Highlights in Science, Engineering and TechnologyISET2022Volume 12(2022)13Tree Search Algorithms For Chinese ChessSiyu HengNanjing Institute of Technology, Nanjing,ChinaAbstract. 

Computerspiele sind ein wichtiger Aspekt der künstlichen Intelligenz (KI), die viele repräsentative Algorithmen optimaler Strategien hervorgebracht hat.  Daher haben viele KI-Forscher die Spieltheorie auf verschiedene Brettspiele angewendet, um die Essenz von Spielen zu finden und den Kern des KI-Verhaltens zu erfassen.  AlphaGo ist ein sehr bekanntes und typisches Schachprogramm, das die Monte-Carlo-Baumsuche (MCTS) verwendet, um den Wert jedes Knotens im Suchbaum zu schätzen und die möglichen Ergebnisse zu optimieren.  Chinesisches Schach ist eine der traditionellen Schachvarianten mit seiner typischen Strategie.  Aufgrund des späten Starts und der hohen Komplexität sind jedoch noch viele weitere technische Probleme zu lösen.  In diesem Artikel empfehlen wir zwei häufig verwendete Such-Frameworks für chinesisches Schach: den Minimax-Algorithmus und den Alpha-Beta-Pruning-Algorithmus.  Auf dieser Grundlage, um mit der komplexen und veränderlichen Situation fertig zu werden, basiert der chinesische Schachalgorithmus auf der Monte-Carlo-Baumsuche und eine geeignete Bewertungsfunktion für neuronale Netzwerke wird untersucht.
- By Lothar Jung Date 2022-10-12 09:35 Upvotes 1
Zu MCGS (Monte Carlo Graph Search) siehe folgende Veröffentlichung:

https://arxiv.org/pdf/2210.01426.pdf

Hier die (übersetzte) Zusammenfassung der Veröffentlichung:

Bei vielen komplexen Aufgaben der sequentiellen Entscheidungsfindung ist die Online-Planung entscheidend für eine hohe Leistung.  Für eine effiziente Online-Planung verwendet die Monte-Carlo-Baumsuche (MCTS) einen prinzipiellen Mechanismus zum Abwägen zwischen Exploration und Exploitation.  MCTS übertrifft Vergleichsmethoden in verschiedenen Bereichen der diskreten Entscheidungsfindung wie Go, Schach und Shogi.  Nachfolgend wurden Erweiterungen von MCTS auf kontinuierliche Domänen vorgeschlagen.  Der inhärente hohe Verzweigungsfaktor und die resultierende Explosion der Größe des Suchbaums schränken jedoch bestehende Verfahren ein.  Um dieses Problem zu lösen, schlägt dieser Beitrag Continuous Monte Carlo Graph Search (CMCGS) vor, eine neuartige Erweiterung von MCTS zur Online-Planung in Umgebungen mit kontinuierlichen Zustands- und Aktionsräumen.  CMCGS macht sich die Erkenntnis zunutze, dass während der Planung die gemeinsame Nutzung der gleichen Aktionsrichtlinie zwischen mehreren Zuständen eine hohe Leistung erbringen kann.  Um diese Idee zu implementieren, bündelt CMCGS bei jedem Zeitschritt ähnliche Zustände in einer begrenzten Anzahl von stochastischen Action-Bandit-Knoten, die anstelle eines MCTS-Suchbaums einen geschichteten Graphen erzeugen.  Die experimentelle Auswertung mit begrenzten Stichprobenbudgets zeigt, dass CMCGS Vergleichsmethoden übertrifft
in mehreren komplexen kontinuierlichen DeepMind Control Suite-Benchmarks und einer 2D-Navigationsaufgabe.
- By Lothar Jung Date 2022-10-16 09:03 Edited 2022-10-16 09:07 Upvotes 1
Hier drei weitere Veröffentlichungen:

<https://arxiv.org/pdf/2111.06266.pdf> **AlphaDDA: strategies for adjusting the playing strength of a fully trained AlphaZero system to a suitable human training partner**
<https://peerj.com/articles/cs-1123/>
Seems to be an old article but was recently updated.

<https://arxiv.org/pdf/2210.01426.pdf> **CONTINUOUS MONTE CARLO GRAPH SEARCH**
They are trying to adapt MCGS to tasks without descrete moves (like board games) but rather continuous processes (like videogames?).

https://arxiv.org/pdf/2111.06266.pdf

https://peerj.com/articles/cs-1123/

https://arxiv.org/pdf/2210.01426.pdf
- By Lothar Jung Date 2022-10-31 08:13 Upvotes 1
Papier über die Gründe des Einsatzes von MCTS gegenüber A/B in AlphaZero:

https://ai.stackexchange.com/questions/37419/the-reason-behind-using-mcts-over-alpha-beta-pruning-in-alphazero
- By Lothar Jung Date 2022-10-31 15:06 Upvotes 1
Hier das Reference paper zu MCTS bei Alpha Go:

„The Grand Challenge of Computer Go: Monte Carlo Tree Search and Extensions“.

https://hal.inria.fr/hal-00695370v3/document
- - By Lothar Jung Date 2022-11-03 12:29 Upvotes 1
Hier eine deutschsprachige und allgemein verständliche Veröffentlichung zum MCTS Algorithmus:

https://de.jberries.com/artikel/ein-zahlenspiel-zur-erl%C3%A4uterung-des-monte-carlo-tree-search-algorithmus-118
Parent - - By Rainer Neuhäusler Date 2022-11-03 22:37
Lothar Jung schrieb:

Hier eine deutschsprachige und allgemein verständliche Veröffentlichung zum MCTS Algorithmus:

<a class='ura' href='https://de.jberries.com/artikel/ein-zahlenspiel-zur-erl%C3%A4uterung-des-monte-carlo-tree-search-algorithmus-118'>https://de.jberries.com/artikel/ein-zahlenspiel-zur-erl%C3%A4uterung-des-monte-carlo-tree-search-algorithmus-118</a>

Ich kenne den Link schon aus Deinem Archiv. Die Mehrheit der Gemeinde begnügt sich vielleicht schon mit dieser kurzen, gut erklärten Abhandlung auf ChessBase-Niveau.
https://de.chessbase.com/post/monte-carlo-statt-alpha-beta
Parent - By Rainer Neuhäusler Date 2022-11-04 18:13
Rainer Neuhäusler schrieb:

Lothar Jung schrieb:

Hier eine deutschsprachige und allgemein verständliche Veröffentlichung zum MCTS Algorithmus:

<a class='ura' href='<a class='ura' href='https://de.jberries.com/artikel/ein-zahlenspiel-zur-erl%C3%A4uterung-des-monte-carlo-tree-search-algorithmus-118'>https://de.jberries.com/artikel/ein-zahlenspiel-zur-erl%C3%A4uterung-des-monte-carlo-tree-search-algorithmus-118</a>'>https://de.jberries.com/artikel/ein-zahlenspiel-zur-erl%C3%A4uterung-des-monte-carlo-tree-search-algorithmus-118</a>

Ich kenne den Link schon aus Deinem Archiv. Die Mehrheit der Gemeinde begnügt sich vielleicht schon mit dieser kurzen, gut erklärten Abhandlung auf ChessBase-Niveau.
<a class='ura' href='https://de.chessbase.com/post/monte-carlo-statt-alpha-beta'>https://de.chessbase.com/post/monte-carlo-statt-alpha-beta</a>


Huch 
ich hab den Beitrag nicht vom Hauptforum hierher verschoben bzw. zweimal verfasst ??
Es ergibt auch keinen so rechten Sinn, wenn ich darauf hinweise, daß ich Lothar's Beitrag schon aus dem Archiv kenne und mich dabei schon in demselben befinde   
Zudem ist mein ChessBase-Link ja wegen seiner Knappheit und Allgemeinverständlichkeit ausdrücklich an die Community des Hauptforums gerichtet und nicht an die Inisder und Spezialisten der Schachprogrammierung.
Drittens ist Lothars Ausgangsbeitrag nun zweimal vorhanden, hier und im Hauptforum. Threadstrukturbedingt oder wie?
- By Lothar Jung Date 2022-11-20 10:07 Upvotes 1
Veröffentlichung über „Spending Thinking Time Wisely: Accelerating MCTS with Virtual Expansions“:

https://arxiv.org/abs/2210.12628
- By Lothar Jung Date 2022-11-29 16:43 Upvotes 1
Hier ein umfangreicher Vorschlag zur Verbesserung und Übersichtlichkeit der Lc0-Suche:

https://github.com/LeelaChessZero/lc0/issues/1734
- By Lothar Jung Date 2022-12-24 13:22 Upvotes 1
Hier eine aktuelle Veröffentlichung über Monte Carlo Search:

https://webdocs.cs.ualberta.ca/~mmueller/ps/2022/Aghakasiri_Kiarash_MSc.pdf
- By Lothar Jung Date 2023-04-22 15:33
Veröffentlichung über „Memory Bounded Monte Carlo Tree Search“:

http://repository.falmouth.ac.uk/2782/1/MemoryLimiting.pdf
- By Lothar Jung Date 2023-05-26 06:57
Veröffentlichung über „A SIMPLE APPROACH TO PARALLELIZING MONTE CARLO TREE SEARCH“:

https://export.arxiv.org/pdf/1810.11755
- - By Lothar Jung Date 2023-06-25 14:27
MCTS steht für Monte-Carlo Tree Search (Monte-Carlo-Baumsuche) und ist ein Algorithmus, der in der künstlichen Intelligenz und der Entscheidungsfindung eingesetzt wird. MCTS wurde ursprünglich für die Lösung von Spielen entwickelt, hat aber Anwendungen in verschiedenen Bereichen gefunden.

Der MCTS-Algorithmus basiert auf der Idee, den Suchraum eines Problems durch zufällige Simulationen zu erkunden. Dabei wird ein Entscheidungsbaum aufgebaut, der mögliche Spielzüge oder Aktionen repräsentiert. Der Baum wird schrittweise erweitert, indem Simulationen durchgeführt werden, um die Auswirkungen verschiedener Aktionen zu bewerten.

Der MCTS-Algorithmus besteht aus vier Hauptphasen: Auswahl, Expansion, Simulation und Rückpropagierung.

1. Auswahl: Der Algorithmus beginnt an der Wurzel des Entscheidungsbaums und wählt rekursiv einen Pfad hinunter zum Blatt des Baums aus, basierend auf einer Auswahlstrategie wie dem UCT (Upper Confidence Bound for Trees)-Algorithmus. Die Auswahlstrategie berücksichtigt sowohl die durchgeführten Simulationen als auch die potenziellen Vorteile der unerforschten Pfade.

2. Expansion: Sobald ein unerforschtes Blatt erreicht ist, wird der Baum um einen oder mehrere Kindknoten erweitert, die mögliche Aktionen repräsentieren.

3. Simulation: Von dem neu erstellten Knoten aus werden zufällige Simulationen durchgeführt, um den Wert oder die Qualität der Aktionen zu bewerten. Diese Simulationen werden typischerweise bis zu einem Endzustand oder einer Abbruchbedingung durchgeführt.

4. Rückpropagierung: Nach Abschluss der Simulation werden die Ergebnisse auf dem ausgewählten Pfad vom Blatt bis zur Wurzel des Baums rückwärts propagiert. Die Ergebnisse werden in den Knoten des Baums akkumuliert, um die Statistiken der Aktionen zu aktualisieren, z. B. die Anzahl der Besuche und die erzielte Belohnung. Dies ermöglicht eine bessere Bewertung der Aktionen bei zukünftigen Durchläufen.

Durch wiederholtes Durchlaufen dieser vier Phasen sammelt MCTS Informationen über den Suchraum und verbessert die Bewertung der Aktionen im Entscheidungsbaum. Am Ende der Suche wird die vielversprechendste Aktion basierend auf den gesammelten Statistiken ausgewählt und ausgeführt.

MCTS hat sich als leistungsstarker Algorithmus erwiesen, der in vielen Spielen wie Schach, Go und Poker erfolgreich eingesetzt wird. Es hat auch Anwendungen in anderen Bereichen wie der Planung, der Robotik und der Entscheidungsfindung unter Unsicherheit gefunden.
Parent - By Lothar Jung Date 2023-11-25 11:19
Monte Carlo Tree Search (MCTS) ist ein fortschrittlicher Algorithmus, der in der künstlichen Intelligenz für Entscheidungsfindungen in komplexen Umgebungen wie Spielen eingesetzt wird. Um MCTS zu verstehen, ist es hilfreich, den Prozess in seine grundlegenden Komponenten zu zerlegen und zu sehen, wie diese zusammenarbeiten.

### Grundkonzept von MCTS

MCTS kann man sich wie einen Entscheidungsbaum vorstellen, bei dem jeder Knoten einen möglichen Spielzustand und jede Verzweigung einen möglichen Zug darstellt. Der Algorithmus durchläuft vier Hauptphasen:

1. **Auswahl (Selection):** Der Algorithmus beginnt an der Wurzel des Baumes (dem aktuellen Spielzustand) und wählt basierend auf bisherigen Erfahrungen und statistischen Berechnungen einen Pfad durch den Baum. Dieser Prozess wird fortgesetzt, bis ein Knoten erreicht wird, der nicht vollständig erforscht ist.

2. **Expansion (Expansion):** In diesem Schritt fügt der Algorithmus dem bisher unerforschten Knoten neue Verzweigungen (mögliche Züge) hinzu.

3. **Simulation (Simulation):** Von einem der neuen Knoten aus führt der Algorithmus eine zufällige Simulation des Spiels durch, um zu sehen, was passieren könnte.

4. **Rückmeldung (Backpropagation):** Nachdem die Simulation abgeschlossen ist, wird das Ergebnis entlang des Pfades zurück zur Wurzel des Baumes weitergegeben, wodurch die Statistiken jedes besuchten Knotens aktualisiert werden.

### Speicherung und Bewertung von Erfahrungen

Die Erfahrungen, die der MCTS-Algorithmus sammelt, werden in den Knoten des Entscheidungsbaums gespeichert. Jeder Knoten hält Informationen wie die Anzahl der Besuche und die Gewinn-Statistik fest. Diese Daten werden verwendet, um die Entscheidungen des Algorithmus zu leiten.

Die Bewertung dieser Erfahrungen erfolgt durch die UCB1-Formel (Upper Confidence Bound), die sowohl die Erfolgsrate als auch die Anzahl der Besuche berücksichtigt. Diese Formel hilft, eine Balance zwischen der Erkundung neuer Möglichkeiten und der Ausnutzung bekannter erfolgreicher Züge zu finden.

### Zusammenfassung

MCTS ist ein dynamischer Prozess, der sich im Laufe der Zeit selbst verbessert. Durch die ständige Wiederholung der vier Phasen – Auswahl, Expansion, Simulation und Rückmeldung – und die Speicherung sowie Bewertung der gesammelten Erfahrungen wird der Algorithmus zunehmend effektiver in der Vorhersage von erfolgversprechenden Zügen. Dies macht MCTS besonders mächtig in Spielen oder Situationen, in denen es eine riesige Anzahl von möglichen Zügen gibt, wie z.B. im Go oder Schach.
- By Lothar Jung Date 2023-08-15 12:41
Veröffentlichung über „E-MCTS: Deep Exploration in Model-Based Reinforcement Learning by Planning with Epistemic Uncertainty“:

https://arxiv.org/pdf/2210.13455.pdf
- By Lothar Jung Date 2023-08-20 11:04
Veröffentlichung über „Monte-Carlo tree search as regularized policy optimization“:

https://arxiv.org/pdf/2007.12509.pdf
- By Lothar Jung Date 2023-10-28 15:55
Veröffentlichung über „HYBRID MINIMAX-MCTS AND DIFFICULTY ADJUSTMENT FOR GENERAL GAME PLAYING“:

https://arxiv.org/pdf/2310.16581.pdf
- By Lothar Jung Date 2024-05-23 07:56
Enhancing Reinforcement Learning Through Guided Search

https://ala2024.github.io/papers/ALA2024_paper_29.pdf
- By Lothar Jung Date 2024-05-23 07:58 Upvotes 1
Learning to Search with MCTSnets

https://arxiv.org/pdf/1802.04697
- By Lothar Jung Date 2024-10-18 15:21 Upvotes 1
Interessante Veröffentlichung über „ IMPLICIT SEARCH VIA DISCRETE DIFFUSION: A
STUDY ON CHESS“:

https://openreview.net/pdf?id=A9y3LFX4ds
Up Topic Hauptforen / Schachprogrammierung / Monte Carlo Tree Search (MCTS)

Powered by mwForum 2.29.3 © 1999-2014 Markus Wichitill