Analiza drevesnega preiskovanja Monte Carlo v enostavnih šahovskih končnicah

BARACHINI, ROBERT (author), Guid, Matej (mentor)

V diplomskem delu smo analizirali obnašanje algoritma drevesno preiskovanje Monte Carlo (ang. Monte Carlo tree search -- MCTS) v domeni enostavnih šahovskih končnic. Implementirali smo več hevristik za usmerjanje Monte Carlo simulacij in skozi postopek eksperimentiranja razvili več različic programa ter analizirali uspešnost posameznih hevristik in različnih konfiguracij algoritma. Odigrane poteze smo primerjali s popolno igro, pri čemer smo uporabili tabele šahovskih končnic Gaviota. V sklopu programskih rešitev je bil izdelan grafični vmesnik, ki omogoča spremljanje igre proti inteligentnemu agentu. Razvili smo več programov za analizo igre, poganjanje simulacij z različnimi nastavitvami ter vizualizacijo iskalnih dreves in ostalih rezultatov. Izvedli smo empirično študijo, v kateri smo ugotavljali vplive parametrov algoritma MCTS in kombinacij domenskih hevristik na kakovost igre programa.

• Language: Slovenian
• Keywords: drevesno preiskovanje Monte Carlo, MCTS, šah, šahovske končnice, hevristike, Stockfish, tabele končnic, Gaviota
• Work type: Bachelor thesis/paper
• Typology: 2.11 - Undergraduate Thesis
• Organization: FRI - Faculty of Computer and Information Science
• Year: 2020
• PID: 20.500.12556/RUL-114084
• COBISS.SI-ID: 1538535107
• Publication date in RUL: 13.02.2020

Secondary language

• Language: English
• Title: Analysis of Monte Carlo tree search in simple chess endgames

Abstract

In the thesis, we analyzed the behavior of the Monte Carlo tree search algorithm (MCTS) in the domain of simple chess endgames. We have implemented several heuristics for routing Monte Carlo simulations. Through the experimental process we have developed several versions of the program and analyzed the performance of individual heuristics and different configurations of the algorithm. The played moves were compared with perfect information using the Gaviota chess tablebases. As part of the software solutions, a graphical interface was created that allows monitoring the game against an intelligent agent. We have developed several programs to analyze the game, run simulations with different settings and visualize search trees and other results. We conducted an empirical study to determine the effect of the parameters of the MCTS algorithm and combinations of domain heuristics on the quality of play of the program.

• Keywords: Monte Carlo tree search, MCTS, chess, chess endgames, heuristics, Stockfish, chess tablebases, Gaviota