Zastosowania MCTS / UCT

MCTS / UCT to metoda wyszukiwania drzewa gry, która wykorzystuje algorytm bandyty do wybierania obiecujących węzłów do eksploracji. Gry są rozgrywane losowo, a węzły prowadzące do większej liczby zwycięstw są eksplorowane bardziej intensywnie. Algorytm bandytów utrzymuje równowagę między eksploracją węzłów o wysokich wskaźnikach wygranych a eksploracją nieznanych węzłów (i w czystej postaci niekoniecznie korzysta z funkcji oceny heurystycznej). Programy oparte na tej ogólnej technice osiągnęły niesamowite wyniki w komputerze Go .

Czy wyszukiwania Monte-Carlo prowadzone przez bandytów zostały zastosowane do innych problemów z wyszukiwaniem? Na przykład, czy byłoby to użyteczne podejście do przybliżania rozwiązań MAX-SAT, BKP lub innych problemów optymalizacji kombinatorycznej? Czy są jakieś szczególne cechy problemu (strukturalne / statystyczne / itp.), Które sugerowałyby, czy podejście w stylu bandyty byłoby skuteczne?

Czy są jakieś znane problemy deterministyczne, które byłyby całkowicie odporne na metody bandyty, ze względu na charakter przestrzeni rozwiązań?

To nie jest pełna odpowiedź, ale kilka podstawowych spostrzeżeń na temat zastosowania tego do MAX-SAT.

$7/8$$x=0$$x=1$$x=0$$x=1$$7/8$$7/8$

$7/8$$NP$$7/8$heurystyka, której używasz, nawet jeśli zgadniesz doskonale, wciąż istnieją niezadowalające formuły, dla których cofanie się do skutku tylko stwierdzi, że są niezadowalające po wykładniczo wielu krokach. Dolne granice długości próbnych rozdzielczości dają te wyniki. Jedno odniesienie to:

Pavel Pudlák, Russell Impagliazzo: Dolna granica dla algorytmów DLL dla k-SAT (wersja wstępna). SODA 2000: 128–136

Jeśli chodzi o pytanie, jakie cechy sprawiają, że problem jest podatny na podejście oparte na bandytach, w niniejszym dokumencie opisano zachowanie UCT w różnych przestrzeniach wyszukiwania:

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

Pozdrawiam, Cameron

W tym ostatnim artykule ankietowym wymieniono zastosowanie MCTS do szeregu problemów związanych z wyszukiwaniem i optymalizacją innych niż gry, w rozdziale 7.8:

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

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

Jeśli chodzi o domeny, które są całkowicie odporne na metody oparte na bandytach, nie jestem świadomy żadnego podstępu. Szachy są jednym rażącym pominięciem w literaturze MCTS, być może z powodu „stanów pułapek”, które szkodzą wyszukiwaniu, ale także z powodu faktu, że komputerowi gracze w szachy są tak wysoce zoptymalizowani i dobrzy w dzisiejszych czasach, że jakiekolwiek nowe podejście jest mało prawdopodobne wgniecenie na nich.

Pozdrawiam, Cameron