Modeling Go Game as a Large Decomposable Decision Process

Badania nad algorytmami grającymi w Go są prawie tak stare jak badania nad innymi grami planszowymi. Do niedawna, programy grające w Go nie były uważane za silne. Siła programów Go wzrosła dzięki rozwinięciu nowej techniki - Monte Carlo Go. Kluczem do siły gry obecnych programów jest jakość ruchów w próbkach kontynuacji gry. W najlepszych programach, ruchy w próbkach wybierane są z użyciem lokalnych (względem ruchu) heurystyk. Heurystyki te na ogół są tworzone na bazie zapisów gier dobrych graczy, za pomocą algorytmu Minorization-Maximization (MM). MM, mimo że jest obecnie najlepszym znanym algorytmem, może przetworzyć tylko ograniczoną ilość danych, ze względu na ograniczenia pamięciowe istniejącego sprzętu. W poniższej pracy projektujemy i prezentujemy nowy, lepszy algorytm typu ``online'', który jest zdolny do uczenia się z nieograniczenie dużego zbioru danych. Dowodzimy że nasz algorytm zbiega. Najlepsze programy grają na planszy $19 \times 19$ z siłą dobrego gracza klubowego, a na małej planszy $9 \times 9$ z siłą bliską zawodowego gracza. Taki rozrzut w sile gry nie jest spotykany wśród ludzi, którzy na ogół grają z podobną siłą, niezależnie od rozmiaru planszy. Naszym zdaniem powodem słabości algorytmu Monte Carlo Go na planszy $19 \times 19$ jest nieefektywność globalnego algorytmu Monte Carlo Tree Search (MCTS). Pozycje na planszy $19 \times 19$ składają się na ogół z wielu mniejszych i niezależnych podgier, które ludzie potrafią analizować niezależnie od siebie. MCTS jest zdolne do analizy każdej podgry z osobna. Ale globalnie, gdy ruchy podgier mogą się przeplatać, MCTS jest nieefektywne z powodu kombinatorycznej eksplozji ilości kombinacji. W niniejszej pracy analizujemy dwa obiecujące algorytmy oparte o dekompozycje sytuacji, które próbują obejść tą nieefektywność, wykorzystując lokalność w sytuacjach Go. Dla każdego z nich odkrywamy i opisujemy powód, przez który te algotmy nie mogą dobrze działać. Proponujemy również nowy algorytm typu 'dziel i rządź', oparty o Kombinatoryczną Teorię Gier. Pokazujemy, że algorytm zbiega w przybliżeniu do optymalnej strategii i potwierdzamy to doświadczalnie na małym przykładzie.

Research on computer Go is almost as old as research on the other board games. But until recent developments of Monte Carlo Go, programs were not considered to be particularly strong. The key to the current programs strength is the quality of the moves in the game continuation samples. In the state of the art programs, moves in samples are chosen based on a local (to the move) Go heuristics. This heuristics are usually learnt from game records of good players using Minorization-Maximization (MM) algorithm. MM is the state of the art but it can process only a limited number of games due to memory constraints of existing hardware. In this thesis, we design and present a better, online algorithm, capable of learning from unconstrained data set. We prove its convergence. State of the art Go programs play on a regular, $19 \times 19$ Go board on the level of a strong club player and on a small $9 \times 9$ board on a near professional level. Such discrepancy in playing strength is uncommon among human players, who tend to play on a similar level regardless of the board size. We attribute Monte Carlo Go weakness on a regular board to the ineffectiveness of a global Monte Carlo Tree Search (MCTS). $19 \times 19$ Go positions usually consist of a multiple smaller independent subgames that human players can analyze independently. MCTS is capable of analyzing any of them separately but globally it is ineffective due to combinatorial explosion when subgames' moves can interlace. We review two decomposition-based, promising algorithms trying to work around that ineffectiveness by exploiting locality in Go positions. For each of them, we discover and describe the reason why it can't work well. Finally we propose a new, divide and conquer algorithm based on Combinatorial Game Theory. We show that it must converge to a near-optimal strategy, and experimentally show the convergence on a toy example.