PNS for the game Arimaa
| Thesis title in Czech: | PNS for the game Arimaa |
|---|---|
| Thesis title in English: | PNS for the game Arimaa |
| Key words: | Proof-Number Search, Arimaa, koncovky her, umělá inteligence |
| English key words: | Proof-Number Search, Arimaa, endgames, artificial intelligence |
| Academic year of topic announcement: | 2011/2012 |
| Thesis type: | Bachelor's thesis |
| Thesis language: | angličtina |
| Department: | Department of Theoretical Computer Science and Mathematical Logic (32-KTIML) |
| Supervisor: | RNDr. Jan Hric |
| Author: | hidden - assigned and confirmed by the Study Dept. |
| Date of registration: | 14.02.2012 |
| Date of assignment: | 20.06.2012 |
| Confirmed by Study dept. on: | 26.06.2012 |
| Date and time of defence: | 06.09.2012 10:00 |
| Date of electronic submission: | 01.08.2012 |
| Date of submission of printed version: | 02.08.2012 |
| Date of proceeded defence: | 06.09.2012 |
| Opponents: | doc. RNDr. Tomáš Valla, Ph.D. |
| Guidelines |
| Proof-number search (PNS) is a method for exact solution of end-game positions or local goals. It uses a shape of a tree during tree expansion and creates nonsymmetric trees. There were suggested various extensions to this method, for example variants with iterative deepening, with limited width and with subtrees sharing.
The goal of the thesis is to implement the PNS method for the game Arimaa. It means to use and adapt some known techniques or suggest new techniques aimed for Arimaa. |
| References |
| [1] S. Russell, P. Norvig: Artificial Intelligence, A Modern Approach, Prentice Hall, 2003
[2] Omar Syed: Arimaa: A New Game Designed to be Difficult for Computers. ICGA Journal Vol. 26, No.2, pp.138-139. [3] Mark H. M. Winands, Jos W. H. M. Uiterwijk, Jaap van den Herik: PDS-PN: A New Proof-Number Search Algorithm, in: Computers and Games 2002, LNCS 2883, Springer, 2003, pp. 61-74 [4] A. Kishimoto, M. Müller: Df-pn in Go: an application to the one-eye problem. In : Advances in Computer Games 10, editors: J. van den Herik, H. Iida, E. Heinz, pp. 125-141, Kluwer, 2004; online http://webdocs.cs.ualberta.ca/~mmueller/cgo/ps/acg_kishimoto_mueller.pdf [5] H. Jaap van den Herik, Mark H. M. Winands: Proof-Number Search and Its Variants. Oppositional Concepts in Computational Intelligence, Studies in Computational Intelligence, 2008, Vol. 155/2008, Springer, pp. 91-118, DOI: 10.1007/978-3-540-70829-2_6 |
| Preliminary scope of work |
| Proof-number search (PNS) je metoda pro přesné řešení koncovek anebo lokálních cílů. Při rozvíjení stromu hry přihlíží k jeho tvaru a staví nesymetrické stromy. Kromě základní metody byly navrženy různé úpravy, např. varianty procházející strom iterovaně do hloubky, pracující s omezenou šířkou a využívající sdílení podstromů.
Cílem práce je naprogramovat metodu PNS pro hru Arimaa, využít a adaptovat některé známé techniky, případně navrhnout nové techniky zaměřené na tuto hru. |
| Preliminary scope of work in English |
| Proof-number search (PNS) is a method for exact solution of end-game positions or local goals. It uses a shape of a tree during tree expansion and creates nonsymmetric trees. There were suggested various extensions to this method, for example variants with iterative deepening, with limited width and with subtrees sharing.
The goal of the thesis is to implement the PNS method for the game Arimaa. It means to use and adapt some known techniques or suggest new techniques aimed for Arimaa. |