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 2
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 2
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 4
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 2
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 2
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 2
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 2
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 2
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 3
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 2
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
Up Topic Hauptforen / Schachprogrammierung / Monte Carlo Tree Search (MCTS)

Powered by mwForum 2.29.3 © 1999-2014 Markus Wichitill