Advanced methods of searching the game tree of 3-dimensional Tic-Tac-Toe
| Thesis title in Czech: | Pokročilé metody prohledávání herního stromu trojrozměrných piškvorek |
|---|---|
| Thesis title in English: | Advanced methods of searching the game tree of 3-dimensional Tic-Tac-Toe |
| Key words: | vícerozměrné piškvory, paralelizace, automorfismy |
| English key words: | multidimensional tic-tac-toe, parallelization, automorphisms |
| Academic year of topic announcement: | 2011/2012 |
| Thesis type: | Bachelor's thesis |
| Thesis language: | angličtina |
| Department: | Department of Applied Mathematics (32-KAM) |
| Supervisor: | doc. RNDr. Tomáš Valla, Ph.D. |
| Author: | hidden - assigned and confirmed by the Study Dept. |
| Date of registration: | 03.11.2011 |
| Date of assignment: | 04.11.2011 |
| Confirmed by Study dept. on: | 01.12.2011 |
| Date and time of defence: | 20.06.2013 00:00 |
| Date of electronic submission: | 22.05.2013 |
| Date of submission of printed version: | 23.05.2013 |
| Date of proceeded defence: | 20.06.2013 |
| Opponents: | doc. Mgr. Robert Šámal, Ph.D. |
| Guidelines |
| Tématem práce je prohledávání obrovských herních stromů pozičních her počítačem, zejména trojrozměrných piškvorek,
za účelem nalezení či popsání výherní strategie prvního hráče. Úkolem studenta bude nastudovat netriviální algoritmy pro prohledávání herních stavových prostorů, zvolit nejvhodnější postup pro řešení trojrozměrných piškvorek, a implementovat je. Nedílnou součástí budou algoritmy pro paralelní a distribuované výpočty (více vláken, více počítačů). Práce si klade za cíl mimo jiné kompletní řešení hry 4x4x4, ale především pokus o vyřešení hry 5x5x5, která je v současnosti otevřeným problémem. Výstupem bude odladěný software procházející herní strom, případně popisující vítěznou strategii. |
| References |
| Oren Patashnik: Qubic: 4x4x4 Tic-Tac-Toe, Mathematics Magazine vol. 52, no. 4 (1980)
Roland Silver: The Group of Automorphisms of the Game of 3-Dimensional Ticktacktoe, The American Mathematical Monthly vol. 74, no. 4 (1967) Louis Victor Allis: Searching for Solutions in Games and Artificical Intelligence, Rijksuniversiteit Limburg te Maastricht |