Masters Theses

Date of Award

5-1993

Degree Type

Thesis

Degree Name

Master of Science

Major

Computer Science

Major Professor

David Mutchler

Committee Members

Jean Blair, Michael Vose

Abstract

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.

Download
Files over 3MB may be slow to open. For best results, right-click and select "save as..."

Share

COinS