Masters Theses

Date of Award

12-1981

Degree Type

Thesis

Degree Name

Master of Science

Major

Computer Science

Major Professor

Charles Pfleeger

Committee Members

David Straight, David Matusek

Abstract

The purpose of this thesis was to solve the Baker game, a one-person, complete information card game. The thesis is case study in the use a artificial of game theory and intelligence techniques to solve a non-trivial game.

The Baker game was solved with a computer program which implements an exhaustive search of the Baker game search space. A large number of algorithms are used by the program to reduce the size of the search space. The algorithms are proven to produce reduced search spaces which are equivalent to the original search space.

The program was able to solve about 90% of a random sample of different Baker game configurations. About 75% of initial Baker game configurations were shown to be winnable, and about 15% of initial Baker game configurations shown to be unwinnable. The other 10% of initial Baker game exceeded the capabilities of the program. configurations were These results represent significant improvements over human play of the Baker game, whereas many artificial intelligence studies produce a level of play inferior to human game playing.

The strategies used to reduce the size of the Baker game search space were specific to the Baker game, but some generalization to other games should be possible. The strategies would be most adaptable to other one-person games.

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

Share

COinS