Anwendungen von MCTS / UCT

MCTS / UCT ist eine Suchmethode für Spielbäume, bei der mithilfe eines Banditenalgorithmus vielversprechende Knoten für die Erkundung ausgewählt werden. Spiele werden nach dem Zufallsprinzip bis zum Ende gespielt und Knoten, die zu mehr Gewinnen führen, werden stärker untersucht. Der Banditenalgorithmus hält ein Gleichgewicht zwischen dem Erkunden von Knoten mit hohen Gewinnraten und dem Erkunden unbekannter Knoten aufrecht (und verwendet in seiner reinen Form nicht unbedingt eine heuristische Bewertungsfunktion). Programme, die auf dieser allgemeinen Technik basieren, haben in Computer Go ziemlich erstaunliche Ergebnisse erzielt .

Wurden banditengesteuerte Monte-Carlo-Suchen auf andere Suchprobleme angewendet? Wäre dies beispielsweise ein nützlicher Ansatz, um Lösungen für MAX-SAT-, BKP- oder andere kombinatorische Optimierungsprobleme zu approximieren? Gibt es bestimmte Merkmale eines Problems (strukturell / statistisch / etc.), Die darauf hindeuten, ob ein banditenartiger Ansatz effektiv wäre oder nicht?

Gibt es bekannte deterministische Probleme, die aufgrund der Art des Lösungsraums gegenüber Banditenmethoden völlig resistent wären?

Dies ist keine vollständige Antwort, sondern einige grundlegende Beobachtungen zur Anwendung auf MAX-SAT.

Auf hoher Ebene sieht es so aus, als würde dieser heuristische Ansatz (bei Anwendung auf MAX-SAT) einem Verzweigungsalgorithmus ähneln, der auf der Methode der "bedingten Erwartung" basiert, einer Standardmethode bei der Derandomisierung. Um beispielsweise eine deterministische Annäherung für MAX 3-SAT (mit 3 Variablen pro Klausel) zu erhalten, setzt man eine Variable und schätzt den erwarteten Anteil der Klauseln, die durch eine zufällige Zuordnung in den verbleibenden Klauseln erfüllt werden Formel, setzt dann und führt die gleiche Berechnung durch. (Dies sieht sehr ähnlich aus wie "Zufällig ein Spiel bis zum Ende spielen".) Die Variableneinstellung mit dem höheren erwarteten Anteil an Klauseln ( oder ) wird ausgewählt. Dieser Polynomzeitalgorithmus ergibt a$7/8$$x=0$$x=1$$x=0$$x=1$$7/8$ Annäherung und ist bekanntermaßen eng (Sie können es täuschen, nur der Klauseln zu erfüllen ). Diese Verbindung sollte es ermöglichen, Untergrenzen für die Fähigkeit dieser Heuristik zu beweisen.$7/8$

Es ist bekannt , dass eine bessere MAX 3-SAT annähert als ist -hard, so dass wir besser nicht eine effiziente heuristische erwarten zu tun , als dies. Es wäre interessant zu zeigen (und ich vermute, es ist wahr), dass ein Verzweigungsalgorithmus, der auf der obigen Heuristik mit variabler Auswahl basiert, exponentiell viele Schritte erfordert, um eine Annäherung von besser als zu finden . Es gibt bereits Untergrenzen für das Backtracking, die besagen, dass es unabhängig von der verwendeten Heuristik, auch wenn Sie perfekt raten, immer noch unbefriedigende Formeln gibt, für die das Backtracking erst nach exponentiell vielen Schritten zu dem Ergebnis führt, dass sie nicht zufriedenstellend sind. Untergrenzen für die Länge der Auflösungsbeweise ergeben diese Ergebnisse. Eine Referenz ist:$7/8$$NP$$7/8$

Pavel Pudlák, Russell Impagliazzo: Eine Untergrenze für DLL-Algorithmen für k-SAT (vorläufige Version). SODA 2000: 128 & ndash; 136

In Bezug auf die Frage, welche Merkmale ein Problem für banditenbasierte Ansätze zugänglich machen, beschreibt dieses Papier das Verhalten von UCT in verschiedenen Suchräumen:

http://www.cs.cornell.edu/~raghu/Raghuram_Ramanujan_files/mcts11.pdf

Grüße, Cameron

In diesem kürzlich erschienenen Umfragepapier wird die Anwendung von MCTS auf eine Reihe anderer Such- und Optimierungsprobleme als Spiele in Abschnitt 7.8 aufgeführt:

http://pubs.doc.ic.ac.uk/survey-mcts-methods/survey-mcts-methods.pdf

http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=6145622

Bei Domains, die gegenüber banditenbasierten Methoden völlig resistent sind, sind mir keine Nebeneffekte bekannt. Schach ist eine eklatante Lücke in der MCTS-Literatur, möglicherweise aufgrund von "Fallenzuständen", die die Suche beeinträchtigten, aber möglicherweise auch aufgrund der Tatsache, dass Computerschachspieler heutzutage so hoch optimiert und gut sind, dass ein neuer Ansatz unwahrscheinlich ist eine Beule auf ihnen.

Grüße, Cameron