Mašininio mokymosi algoritmų skirtų žaidimams, analizė ir lyginamasis tyrimas

Baigiamasis darbas skirtas lentos žaidimų kompiuterinių mašininio mokymosi algoritmų tyrimui. Vienas iš geriausiai ištirtų ir gerai žinomų lentos žaidimų yra šaškės, todėl darbo aktualumo apžvalga pradedama nuo mašininio mokymosi taikymo kompiuterizuojant šį žaidimą aptarimo. Prie lentos žaidimų kategorijos dar priklauso tokie plačiai žinomi žaidimai kaip šachmatai, su-doku, gyvatėlė, ir t.t. Šiame darbe daugiausia dėmesio skirta gyvatėlei, nes jį patogiau realizuoti ir analizuoti, o žaidimo analizės metodika ir gautos išvados, gali būti pritaikytos ir kitiems žaidimams. Šis darbas susideda iš įvado ir trijų dalių – analitinės, projektavimo ir praktinės. Įvadinėje dalyje aptariamas temos aktualumas, sprendžiama problema, formuluojamas darbo tikslas ir uždaviniai. Toliau analitinėje dalyje yra apžvelgiamos pagrindinės lentos žaidimų savybės: tobula informacija, konvergencija, staigi baigtis, sudėtingumas. Šios savybės analizuojamos mašininio mokymosi algoritmų kontekste. Toliau apžvelgiama mašininio mokymosi algoritmų sėkmė konkrečiuose žaidimuose: šaškėse, šachmatuose, narduose, „Otelo“, žodžių loto. Nagrinėjama mašininio mokymosi algoritmų taikymo istorinė raida ir pasiekimai, pradedant tokio taikymo pradžia šaškių žaidime. Pereinama į gilaus mokymosi algoritmų taikymą, akcentuojant gilųjį mokymąsi šachmatuose ir jo laimėjimus. Galiausiai išnagrinėjama paskutinė mašininio mokymosi algoritmų taikymo sėkmė „Go“ žaidime. Praktinėje dalyje yra atliekamas eksperimentas, kuriame suprogramuojama prižiūrimu mokymusi pagrįsta aplikacija (žaidimas) ir jį žaidžiantis agentas bei palyginama su atviro kodo sustiprinto mokymosi agentu, suprogramuotu Google inžinierių. Prižiūrimo mokymosi žaidimui ir jo agentui suprogramuoti yra naudojamos tokios priemonės kaip Firebase, Realtime Database, TensorFlow.js, Three.js ir kitos. Apžvelgiamas kodas, bibliotekų integracija, agento logika ir aplikacijos architektūra. Taip pat nagrinėjami optimizavimo klausimai: Adam optimizatoriaus ir kategorinės kryžminės entropijos praradimų funkcijos pasirinkimai. Atlikto eksperimento su sukurta aplikacija (gyvatėlės žaidimu) rezultatai leidžia prieiti prie išvados, kad prižiūrimo mokymosi agentas efektyviau žaidžia žaidimą nei sustiprinto mokymosi agentas.

The thesis is devoted to the study of computer-based machine learning algorithms for board games. One of the most well-studied and well-known board games is checkers, so a review of the relevance of this work begins with a discussion of machine learning in the computerization of this game. Board games also include chess, sudoku, snake, etc. And the work focused mainly on the snake, because the conclusions and game analysis methodology can be applied to other games as well. This work consists of two parts - analytical and practical. The analytical section first reviews the remainder of the introductory section. The properties of games are reviewed below: perfect information, convergence, abrupt ending, complexity. Features are analyzed in the context of machine learning algorithms. The following reviews the success of machine learning algorithms in specific games: checkers, chess, backgammon, Othello, word lotto. The history of the application of machine learning algorithms and the success of its development are examined. The following examines the application of machine learning algorithms in chess from the beginning of such application in general. Moving on to the transition of algorithms to deep learning in chess. Finally, the recent success of applying machine learning algorithms to the game Go is examined. In the practical part, an experiment is carried out in which a supervised learning-based application (game) and an agent playing it are programmed and compared with an open-source reinforcement learning agent programmed by Google engineers. Tools like Firebase, Realtime Database, TensorFlow.js, Three.js and others are used to program the supervised learning game and its agent. Code, library integration, agent logic, and application architecture are reviewed. Choices of the Adam optimizer and the categorical cross-entropy loss function are also explored. The work concludes that the supervised learning agent plays the game more efficiently than the reinforcement learning agent.