Drevesno preiskovanje Monte Carlo v porazdeljenem okolju

diplomsko delo

Jure Grabnar (Avtor), Branko Šter (Mentor), Uroš Lotrič (Komentor)

Povzetek

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.

Ključne besede

drevesno preiskovanje Monte Carlo;porazdeljeni sistemi;SLING;umetna inteligenca;MPI;računalništvo;računalništvo in informatika;univerzitetni študij;diplomske naloge;

Podatki

Jezik:	Slovenski jezik
Leto izida:	2015
Tipologija:	2.11 - Diplomsko delo
Organizacija:	UL FRI - Fakulteta za računalništvo in informatiko
Založnik:	[J. Grabnar]
UDK:	004.83(043.2)
COBISS:	1536568771
Št. ogledov:	1541
Št. prenosov:	484
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Angleški jezik
Sekundarni naslov:	Monte Carlo tree search in a distributed environment
Sekundarni povzetek:	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.
Sekundarne ključne besede:	Monte Carlo tree search;distributed systems;SLING;artificial intelligence;MPI;computer science;computer and information science;diploma;
Vrsta datoteke:	application/pdf
Vrsta dela (COBISS):	Diplomsko delo/naloga
Študijski program:	1000468
Konec prepovedi (OpenAIRE):	1970-01-01
Komentar na gradivo:	Univ. v Ljubljani, Fak. za računalništvo in informatiko
Strani:	[XVIII], 35 str.
ID:	8966418