The game of Hex is a board game that belongs to the family of Shannon games, which are connection-oriented games where players must secure certain connected components in graphs. The problem of solving Hex is a decision problem complete in PSPACE, which implies that the problem is NP-Hard. Although the Hex problem is difficult to solve, there are a number of problem reduction methods that allow solutions to be found for small Hex boards within practical search limits. The present work addresses two problems, the problem of solving the game of Hex for small board sizes and the problem of creating strong artificial Hex players for larger boards. Recently, a leading Hex solving program has been shown to solve the 7x7 Hex board, but failed to solve 8x8 Hex within practical limits. This work investigates Hex-solving techniques and introduces a series of new search optimizations with the aim to develop a better Hex solver. The most significant of these new optimization techniques is a knowledge base approach that stores and reuses search information to prune Hex-solving searches. This technique involves a generalized form of transposition table that stores game features and uses such features to prove that certain board positions are winning. Experimental results demonstrate a knowledge base Hex solver that significantly speeds up the solving of 7x7 Hex. The search optimization techniques for Hex solvers given here are highly specialized. This work reports on a search algorithm for artificial Hex players, called Pattern Enhanced Alpha-Beta search that can utilize these optimization techniques. On large board positions, an artificial Hex player based on the Pattern Enhanced Alpha- Beta search can return moves in practical times if search depths are limited. Such a player can return a good move provided that the evaluated probabilities of winning on board positions at the depth cut-offs are accurate. Given a large database of Hex games, this work explores an apprenticeship learning approach that takes advantage of this database to derive board evaluation functions for strong Hex playing policies. This approach is compared against a temporal difference learning approach and local beam search approach. A contribution from this work is a method that can automatically generate good quality evaluation functions for Hex players.
| Identifer | oai:union.ndltd.org:ADTP/265787 |
| Date | January 2008 |
| Creators | Rasmussen, Rune K. |
| Publisher | Queensland University of Technology |
| Source Sets | Australiasian Digital Theses Program |
| Detected Language | English |
Page generated in 0.0622 seconds