Searching through game tree using Monte-Carlo methods

Kluczowym elementem niezbędnym do rozwoju sztucznej inteligencji jest odnalezienie dobrej strategii w procesie podejmowania decyzji. Konstruowanie zaawansowanych struktur często prowadzi do zbyt złożonych wydajnościowo obliczeń i w rezultacie daje przeciętne skutki. Ryzyko, że bazowy algorytm jest słabym fundamentem, maleje, gdy wprowadza się prostsze i bardziej eleganckie rozwiązania.Głównym celem pracy jest implementacja algorytmu przeszukiwania drzewa decyzji w grach deterministycznych wspomagane symulacjami Monte-Carlo. Metoda odniosła duży sukces w programie AlphaZero, który zdominował wszystkie poprzednio istniejące programy do gry Go, jak i szachów. W pierwszej części pracy wprowadzone są podstawowe pojęcia potrzebne do zrozumienia tej metody, a następnie przedstawiona jest najprostsza wersja algorytmu przeszukiwania, powszechnie znanego pod nazwą Monte Carlo Tree Search. Idea wykorzystania symulacji i umiejętnej klasyfikacji próbek jest zwięzła i nieskomplikowana, pozwalając na szybkie zrozumienie problemu. Jednakże, aby rozwiązanie zbiegało się do optimum, wymagana jest duża liczba iteracji, co powoduje, że bez modyfikacji optymalizujących mogą być podjęte złe decyzje. Wszystko zależy od rodzaju gry, a dokładniej od tego ile jest możliwości oraz jak długo trwa jedna rozgrywka. Zaimplementowane gry to kółko krzyżyk 3x3, 5x5 i warcaby angielskie.The key to development of artificial intelligence lies in finding a good strategy algorithm for a decision process. The creation of advanced structures often leads to heavy calculations in terms of performance and eventually gives average results. The risk of a base algorithm being a weak foundation is smaller, the simpler and more elegant the solutions are.The purpose of this study is to implement a search algorithm of a decision tree for deterministic games using Monte-Carlo playouts. This method has shown to be successful in AlphaZero program who dominated all previous algorithms for the game of Go and Chess. The beginning of the work explains basic concepts, necessary to understand the method and then demonstrates a pure version of the algorithm, widely known as Monte Carlo Tree Search. The idea of simulations along with competent classification of game samples is concise and simple thus allowing quick understanding of the problem. Yet, a large number of iterations is required for the solution to converge to optimum implying the use of optimizations without which the algorithm could fail. All in all, the complexity increases depending on how long a game lasts and how many possibilities a game has. Implemented games are Tic-tac-toe 3x3, 5x5 and English Draughts (Checkers)