Usage of Monte Carlo Tree Search algorithm in games

Praca magisterska przedstawia zagadnienia związane z algorytmem przeszukiwania drzew metodą Monte Carlo w grach. Praca została podzielona na dwa rozdziały. Pierwszy z nich zawiera on opis podstawowych zagadnień teoretycznych wykorzystanych podczas implementacji programu do rozgrywki w grę kółko i krzyżyk. Rozdział prezentuje problematykę opisu gry, opisuje jej klasyfikację, a także przedstawia czym jest macierz wypłat. W dalszej jego części zaprezentowano również zagadnienia związane z podejmowaniem decyzji na podstawie drzewa gry, opisano czym ono jest oraz jak reprezentuje się je w programie komputerowym. Ostatnią część rozdziału poświęcono opisowi działania algorytmu przeszukiwania drzew metodą Monte Carlo. Drugi rozdział pracy magisterskiej prezentuje przykład zastosowania algorytmu przeszukiwania drzew metodą Monte Carlo w grze logicznej kółko i krzyżyk. Ze względu na wysoką popularność swojego papierowego odpowiednika oraz stosunkowo niski poziom skomplikowania zasad gry, idealnie nadaje się ona do przedstawienia procesu projektowania programów do rozgrywki w klasyczne gry planszowe, zastosowania algorytmu w praktyce, a także przeprowadzenia doświadczeń przedstawiających zalety zastosowania MCTS w grach. Rozdział szczegółowo opisuje proces przygotowywania projektu oraz jego analizę. Na zakończenie pracy magisterskiej, na podstawie wcześniejszych rozdziałów następuje podsumowanie zastosowania algorytmu przeszukiwania drzew metodą Monte Carlo w grach na podstawie wniosków wysuniętych podczas przygotowywania projektu gry, a także podsumowane zostają zagadnienia teoretyczne, które pomogły w poprawnym zrozumieniu zagadnień związanych z projektowaniem programu umożliwiającego grę z komputerem. Motywacją do powstania tej pracy była chęć poznania nowoczesnych zagadnień, które coraz częściej znajdują zastosowanie w praktyce dzięki rozwojowi technologicznemu i coraz większej mocy obliczeniowej komputerów.

Master's degree thesis presents topics connected with usage of Monte Carlo Tree Search in games. Thesis has been divided into two chapters. First of them presents theoretical basics used during preparation of program enabling Tic Tac Toe game. Chapter presents issues connected with game description, its classification and presents payoff matrix. Further into the chapter, author presented problems of decision making using game tree and how it is represented inside computer programs. Last part of the chapter focused on Monte Carlo Tree Search algorithm.Second chapter presents usage of Monte Carlo Tree Search algorithm in a sequential game of Tic Tac Toe. Because of popularity of its paper counterpart and lower complexity of game rules, it is ideal to present creation of program playing board games and usage of algorithm in practice as well as conduct some experiments. Chapter presents those topics in details and summarizes analysis of results.Ending of Master's degree thesis summarizes usage of Monte Carlo Tree Search algorith in games and topics from each previous chapter, explaining results generated with programs and charts, as well as sums up theoretical topics.Motivation to explore the topic of usage of Monte Carlo Tree Search algorithm in games was to learn new technologies, which find their application in real life problems thanks to technology progress and greater computing power of machines.