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

Powered by mwForum 2.29.3 © 1999-2014 Markus Wichitill