velikost textu

Advanced methods of searching the game tree of 3-dimensional Tic-Tac-Toe

Upozornění: Informace získané z popisných dat či souborů uložených v Repozitáři závěrečných prací nemohou být použity k výdělečným účelům nebo vydávány za studijní, vědeckou nebo jinou tvůrčí činnost jiné osoby než autora.
Název:
Advanced methods of searching the game tree of 3-dimensional Tic-Tac-Toe
Název v češtině:
Pokročilé metody prohledávání herního stromu trojrozměrných piškvorek
Typ:
Bakalářská práce
Autor:
Bc. Pavel Dvořák
Vedoucí:
RNDr. Tomáš Valla, Ph.D.
Oponent:
Mgr. Robert Šámal, Ph.D.
Id práce:
116743
Fakulta:
Matematicko-fyzikální fakulta (MFF)
Pracoviště:
Katedra aplikované matematiky (32-KAM)
Program studia:
Informatika (B1801)
Obor studia:
Obecná informatika (IOI)
Přidělovaný titul:
Bc.
Datum obhajoby:
20. 6. 2013
Výsledek obhajoby:
výborně (1)
Jazyk práce:
Angličtina
Klíčová slova:
vícerozměrné piškvory, paralelizace, automorfismy
Klíčová slova v angličtině:
multidimensional tic-tac-toe, parallelization, automorphisms
Abstrakt:
Abstrakt: V této práci zkoumáme poziční hry, zejména pak vícerozměrné piškvorky. Porovnáváme existující pokročilé algoritmy (Pn-search, Db-Search, λ-search) pro řešení pozic v pozičních hrách. Algoritmy nasazujeme na domény her 43 a 53, což jsou první netriviální připady trojrozměrných piškvorek. Paralelizujeme Pn-search pro případ, kdy existuje více počátečních pozic. Pn-search aplikujeme jako jed- novláknovou úlohu a řešíme, jak sdílet transpoziční tabulku s vyřešenými poz- icemi. Hlavním a čistě teoretickým výsledkem je charakterizace grupy auto- morfismů kombinatorické krychle nd se stejnou množinou linií jako vícerozměrné piškvorky. Toto je zobecnění Silvera [The American Mathematical Monthly, Vol. 74, No. 3, 1967], který popsal automorfismy hry 43. 1
Abstract v angličtině:
Abstract: In this thesis we study positional games, especially multidimensional tic-tac-toe. We compare present advanced algorithms (Pn-search, Db-search and λ-search) for position solving in positional games. We apply the algorithms on the do- main of 43 and 53 games, which are the first nontrivial cases of 3-dimensional tic-tac-toe. We parallelize Pn-search for cases when there are more starting po- sitions. We apply Pn-search as a single-thread task and we solve how to share the transposition table with solved positions. Our main and clearly theoretical result is the characterization of the group of all automorphisms of combinatorial cube nd with the same set of lines as multidimensional tic-tac-toe has. This is a generalization of Silver [The American Mathematical Monthly, Vol. 74, No. 3, 1967], who characterized the automorphisms of the game 43. 1
Dokumenty
Stáhnout Dokument Autor Typ Velikost
Stáhnout Text práce Bc. Pavel Dvořák 451 kB
Stáhnout Příloha k práci Bc. Pavel Dvořák 220 kB
Stáhnout Abstrakt v českém jazyce Bc. Pavel Dvořák 11 kB
Stáhnout Abstrakt anglicky Bc. Pavel Dvořák 11 kB
Stáhnout Posudek vedoucího RNDr. Tomáš Valla, Ph.D. 53 kB
Stáhnout Posudek oponenta Mgr. Robert Šámal, Ph.D. 177 kB
Stáhnout Záznam o průběhu obhajoby prof. RNDr. Martin Loebl, CSc. 194 kB