The game of Hex is of interest to the mathematics, algorithms, and artificial intelligence communities. It is a classical PSPACE-complete problem, and its invention is intrinsically tied to the Four Colour Theorem and the well-known strategy-stealing argument. Nash, Shannon, Tarjan, and Berge are among the mathematicians who have researched and published about this game.
In this thesis we expand on previous research, further developing the mathematical theory and algorithmic techniques relating to Hex. In particular, we identify new classes of moves that can be pruned from consideration, and devise new algorithms to identify connection strategies efficiently.
As a result of these theoretical improvements, we produce an automated solver capable of solving all 8 x 8 Hex openings and most 9 x 9 Hex openings; this marks the first time that computers have solved all Hex openings solved by humans. We also produce the two strongest automated Hex players in the world --- Wolve and MoHex --- and obtain both the gold and silver medals in the 2008 and 2009 International Computer Olympiads.
| Identifer | oai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:AEU.10048/1311 |
| Date | 11 1900 |
| Creators | Henderson, Philip |
| Contributors | Hayward, Ryan (Computing Science), Nowakowski, Richard (Mathematics and Statistics, Dalhousie University), Shirvani, Mazi (Mathematical and Statistical Sciences), Culberson, Joseph (Computing Science), Mueller, Martin (Computing Science) |
| Source Sets | Library and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada |
| Language | English |
| Detected Language | English |
| Type | Thesis |
| Format | 1219541 bytes, application/pdf |
| Relation | Henderson, Philip (2010). http://www.cs.ualberta.ca/~ph/research.html |
Page generated in 0.0031 seconds