Original title: Algorithms for solving strong positional games with high symmetry
Translated title: Algorithms for solving strong positional games with high symmetry
Authors: Novotná, Jitka ; Valla, Tomáš (advisor) ; Kit, Michal (referee)
Document type: Bachelor's theses
Year: 2012
Language: eng
Abstract: [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.
Keywords: clique game; high symmetry; PN-search; strong positional games; kliková hra; PN-search; silné poziční hry; vysoká simetrie

Institution: Charles University Faculties (theses) (web)
Document availability information: Available in the Charles University Digital Repository.
Original record: http://hdl.handle.net/20.500.11956/40623

Permalink: http://www.nusl.cz/ntk/nusl-464687


The record appears in these collections:
Universities and colleges > Public universities > Charles University > Charles University Faculties (theses)
Academic theses (ETDs) > Bachelor's theses