Název: Algorithms for solving strong positional games with high symmetry
Překlad názvu: Algorithms for solving strong positional games with high symmetry
Autoři: Novotná, Jitka ; Valla, Tomáš (vedoucí práce) ; Kit, Michal (oponent)
Typ dokumentu: Bakalářské práce
Rok: 2012
Jazyk: eng
Abstrakt: [eng] [cze]
In this thesis, we analyse several algorithms for solving strong positional games, mostly based on PN-search. We focus on games with high symmetry of the game plan, where it is possible to substantially reduce the partial game tree by joining isomorph positions. We review several known enhancements of PN-search and also propose some of our own design. We measure the effect of the enhancements on the clique game. A part of the thesis is a software solver for clique game for K=4 and N=5...8. We were able to solve (6,4) and (7,4) clique games and prove that the second player has a draw strategy, which was expected but not shown previously. V této práce představujeme několik algoritmů pro počítačové řešení silných pozičních her a to především algoritmů založených na algoritmu PN-search. Zaměřujeme se na hry s vysokou symetrií herního plánu. Spojováním mnoha izomorfních pozic jsme dosáhli velkého zmenšení části herního strumu, kterou je potřeba prohledat. Představujeme již známa vylepšení a také navrhujeme vlastní. Ověřujeme jak tyto heuristiky funguji na příkladu klikové hry. K práci je přiložen software pro řešení silné klikové hry pro K=4 a N=5...8. Software zvládl vyřešit (6,4) a (7,4)-klikovou hru a dokázal, že druhý hráč má neprohrávající strategii, což se očekávalo, ale dosud nebylo potvrzeno.
Klíčová slova: kliková hra; PN-search; silné poziční hry; vysoká simetrie; clique game; high symmetry; PN-search; strong positional games

Instituce: Fakulty UK (VŠKP) (web)
Informace o dostupnosti dokumentu: Dostupné v digitálním repozitáři UK.
Původní záznam: http://hdl.handle.net/20.500.11956/40623

Trvalý odkaz NUŠL: http://www.nusl.cz/ntk/nusl-304927


Záznam je zařazen do těchto sbírek:
Školství > Veřejné vysoké školy > Univerzita Karlova > Fakulty UK (VŠKP)
Vysokoškolské kvalifikační práce > Bakalářské práce