A pruning algorithm for one player games with hidden information

This thesis makes three contributions to the development of search algorithms for one-player games with hidden information. The first contribution is the description and analysis of a new pruning technique, called information set pruning, that is specific to hidden information games. Second, the One-Player Pruning Algorithm (OPPA) is presented; it is a natural and important extension of the existing One-Player Algorithm to search game trees with hidden information. OPPA uses information set pruning and other pruning techniques to provide gains in search time by exploring fewer leaves while costing nothing in solution quality and very little in implementation complexity. Finally a general model of game trees with hidden information is suggested. This model has many advantages in terms of generality and clarification of the hidden information concept. It is hoped that further work on hidden information games will utilize this model as a standard form of hidden information game trees. These three contributions take the next logical step in the development of search algorithms for hidden information games and suggest many areas for future work.