20.500.12556/RUL-72135 Analiza preiskovalnih metod na primeru igre Scotland Yard Monte-Carlo tree search method for the board game Scotland Yard V diplomskem delu se seznanimo s področjem umetne inteligence, ki se ukvarja z raziskovanjem namiznih iger in iskanjem njihovih programskih rešitev. Preučimo algoritem drevesnega preiskovanja Monte-Carlo in ga poskušamo čim bolj spretno prenesti na znano namizno igro Scotland Yard, pri čemer upoštevamo nasvete Nijssena in Winandsa. Osredotočimo se predvsem na tretjo fazo algoritma, simulacijo, katero se odločimo implementirati na tri različne načine (od manj naprednih do bolj naprednih), te načine pa želimo kasneje med seboj primerjati. Poskušamo ugotoviti, do kakšne mere se napredna izvedba simulacije obrestuje v nasprotju s časovno manj potratnimi metodami. Ker želimo izvesti avtomatsko preverjanje iger, implementiramo tudi samo igro, v kateri detektivi igrajo po prej omenjenem algoritmu, lopov pa se premika na dva načina - naključno in pametno. Vseh teh šest kombinacij želimo avtomatsko testirati na večjem številu iger in rezultate primerjati ter jih razložiti. In the thesis we learn about the field of artificial intelligence that investigates board games and their program-based solutions. We examine Monte-Carlo tree search algorithm and transfer it to well-known board game Scotland Yard, considering advices from Nijssen and Winands. We focus mainly on the third phase of the algorithm, playout, and decide to implement it in three different ways (from less to more advanced techniques). We compare these three aproaches. We compare the win rates and computation time of simple and advanced methods. We also implement the game to the purpose of automated testing. In this game, detectives play by Monte-Carlo tree search algorithm and Mister X plays in two different ways - random and advanced. We want to test all of these six combinations on a large number of games, compare the results and explain them. drevesno preiskovanje Monte-Carlo Scotland Yard namizne igre umetna inteligenca Monte-Carlo tree search Scotland Yard board games artificial intelligence true false false Slovenski jezik Angleški jezik Diplomsko delo/naloga 2015-09-04 14:45:01 2015-09-04 14:45:02 2022-08-01 15:21:33 0000-00-00 00:00:00 2015 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 1970-01-01 16224 Belej_Neza_-_Analiza_preiskovalnih_metod_na_primeru_igre_Scotland_Yard.pdf Belej_Neza_-_Analiza_preiskovalnih_metod_na_primeru_igre_Scotland_Yard.pdf 1 B7ED9DEEAC9D5EB984E39067634D3643 a113a1157e3249cb55b016ec5d86827d2691626773c03c0749254ae7f72a6c68 57868b97-a1ad-11eb-a523-00155dcfd717 20.500.12556/rul/21a258ab-2ad0-433c-85c4-91eb13ea1724 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=72166 Fakulteta za računalništvo in informatiko 0 0 0