Drevesno preiskovanje Monte Carlo v porazdeljenem okolju

diplomsko delo

Jure Grabnar (Author), Branko Šter (Mentor), Uroš Lotrič (Co-mentor)

Abstract

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.

Keywords

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

Data

Language:	Slovenian
Year of publishing:	2015
Typology:	2.11 - Undergraduate Thesis
Organization:	UL FRI - Faculty of Computer and Information Science
Publisher:	[J. Grabnar]
UDC:	004.83(043.2)
COBISS:	1536568771
Views:	1541
Downloads:	484
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	English
Secondary title:	Monte Carlo tree search in a distributed environment
Secondary abstract:	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.
Secondary keywords:	Monte Carlo tree search;distributed systems;SLING;artificial intelligence;MPI;computer science;computer and information science;diploma;
File type:	application/pdf
Type (COBISS):	Bachelor thesis/paper
Study programme:	1000468
Embargo end date (OpenAIRE):	1970-01-01
Thesis comment:	Univ. v Ljubljani, Fak. za računalništvo in informatiko
Pages:	[XVIII], 35 str.
ID:	8966418