Algorithms for solving strong positional games with high symmetry

• Thesis title in Czech: Algorithms for solving strong positional games with high symmetry
• Thesis title in English: Algorithms for solving strong positional games with high symmetry
• Key words: PN-search, silné poziční hry, vysoká simetrie, kliková hra
• English key words: PN-search, strong positional games, high symmetry, clique game
• Academic year of topic announcement: 2011/2012
• Thesis type: Bachelor's thesis
• Thesis language: angličtina
• Department: Computer Science Institute of Charles University (32-IUUK)
• Supervisor: doc. RNDr. Tomáš Valla, Ph.D.
• Author: hidden - assigned and confirmed by the Study Dept.
• Date of registration: 04.05.2012
• Date of assignment: 04.05.2012
• Confirmed by Study dept. on: 17.05.2012
• Date and time of defence: 06.09.2012 09:00
• Date of electronic submission: 02.08.2012
• Date of submission of printed version: 02.08.2012
• Date of proceeded defence: 06.09.2012
• Opponents: Michał Kit, Ph.D.

Guidelines

Tématem práce je počítačové řešení tzv. silných pozičních her s vysokou symetrií herního plánu.
Pro silné poziční hry obecně neexistují efektivní algoritmy na jejich řešení a je proto třeba
používat pokročilé heuristické metody prohledávání herního stromu.
Cílem této práce je navrhnout nejvhodnější metody řešení her s vysokou symetrií hracího
plánu (a tedy s vysokým počtem izomorfních pozic).
Zejména se zaměříme na tzv. silnou klikovou hru, u níž i malé instance hry jsou otevřeným problémem.
Součástí práce bude odladěný software pro řešení pozic v této hře.

References

József Beck: Combinatorial games - Tic-Tac-Toe Theory, Cambridge University Press
Louis Victor Allis: Searching for Solutions in Games and Artificical Intelligence, Rijksuniversiteit Limburg te Maastricht
Ueda, Hashimoto, Hashimoto, Iida: Weak Proof-number Search
Pawlewicz, Lew: Improving Depth-first PN-Search: 1+epsilon Trick