20.500.12556/RUL-114084 Analiza drevesnega preiskovanja Monte Carlo v enostavnih šahovskih končnicah Analysis of Monte Carlo tree search in simple chess endgames 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. 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. drevesno preiskovanje Monte Carlo MCTS šah šahovske končnice hevristike Stockfish tabele končnic Gaviota Monte Carlo tree search MCTS chess chess endgames heuristics Stockfish chess tablebases Gaviota true false false Slovenski jezik Angleški jezik Diplomsko delo/naloga 2020-02-13 10:50:01 2020-02-13 10:50:06 2024-01-03 07:36:40 0000-00-00 00:00:00 2020 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 23247 1538535107 Barachini_Robert_-_Analiza_drevesnega_preiskovanja_Monte_Carlo_v_enostavnih_sahovskih_koncnicah.pdf Barachini_Robert_-_Analiza_drevesnega_preiskovanja_Monte_Carlo_v_enostavnih_sahovskih_koncnicah.pdf 1 2DBB457C66C712A4DBDB39CD758441B2 fa6cf256b9d8e229b03ee616ec4d572d7cf271d472c140b8ac141619fb000c59 2d58a98d-a1b8-11eb-a523-00155dcfd717 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=126199 Fakulteta za računalništvo in informatiko 0 0 0