20.500.12556/RUL-72441 Drevesno preiskovanje Monte Carlo v porazdeljenem okolju diplomsko delo Monte Carlo tree search in a distributed environment Algoritem drevesnega preiskovanja Monte Carlo (MCTS) je računsko precej zahteven, poleg tega pa čas računanja vpliva na kakovost rezultatov. Namen dela je zato paralelizacija metode MCTS. S paralelizacijo se poveča število iger in drugih parametrov - rezultati so boljši in bolj zanesljivi. Paralelni algoritem smo napisali s pomočjo knjižnice MPI, ki omogoča izvajanje na več računalnikih. Čas izvajanja algoritma smo merili na različnih velikostih problema. Rezultati paralelizacije so bili zadovoljivi, saj je bila pohitritev večinoma linearna. Algoritem smo izvajali na omrežju grid, za katerega skrbi Slovenska iniciativa za nacionalni grid. V okviru dela so nastala tudi navodila za uporabo omrežja grid. Monte Carlo Tree Search algorithm (MCTS) is a computationally expensive algorithm. The time needed for computation correlates with the quality of the results. The purpose of this work is to parallelize MCTS method. With parallelization we gain an ability to increase the number of simulated games per turn and other parameters and still be able to receive results in sufficient time. Quality of results has been improved significantly. Parallel algorithm was written in MPI library which enables the program to run on multiple computers. Algorithm was evaluated on different problem sizes. With big enough problem, the speedup was approximately linear. Algorithm was run on a grid network which is administered by Slovenian Initiative for National Grid (SLING). As a part of this work, instructions for usage of grid network were created. drevesno preiskovanje Monte Carlo porazdeljeni sistemi SLING umetna inteligenca MPI Monte Carlo Tree Search distributed systems SLING artificial intelligence MPI true false false [J. Grabnar] Slovenski jezik Angleški jezik Diplomsko delo/naloga 2015-09-17 15:40:01 2015-09-17 15:40:01 2024-07-31 13:45:55 0000-00-00 00:00:00 2015 0 0 35 str. 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 16239 1536568771 Grabnar_Jure_-_Drevesno_preiskovanje_Monte_Carlo_v_porazdeljenem_okolju.pdf Grabnar_Jure_-_Drevesno_preiskovanje_Monte_Carlo_v_porazdeljenem_okolju.pdf 1 678DCE8F62C85345E1A58E5C53498A76 bcf54d1cad5df5d6ee86debc317a3add0bac0e364e1228f2715b22e8bc7ab19d 7eb5b555-a1a8-11eb-a523-00155dcfd717 20.500.12556/rul/7170eb8e-1a5f-41f8-bfb7-5726e29f05d8 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=72480 Fakulteta za računalništvo in informatiko 0 0 0