Masters Theses

Date of Award

8-1992

Degree Type

Thesis

Degree Name

Master of Science

Major

Computer Science

Major Professor

David Mutchler

Committee Members

David Straight, Michael Vose

Abstract

There is an increasing fascination with programs that play games and especially those that play well. One game that is enjoyable to play, though difficult for programs to play well, is contract bridge. There are several reasons for this difficulty. Two of these difficulties are: 1) that the game consists of imperfect information, and 2) that the size of the game tree is too large for current searching techniques to solve. One goal described in this paper is to produce a bridge-playing program that can overcome these two difficulties. This program, referred to as the Bridge-player, used two ideas, sampling and precomputation, to assist it in the decision-making processes that enable it to play a single-dummy, no-trump contract bridge game. By using sampling to create hands for the unknown hands, the Bridge-player turns a game of imperfect information to one of perfect information. The precomputation is performed by constructing a game similar to contract bridge that is small enough to be exhaustively searched. The idea is that the solutions that work for this similar game will be beneficial to the sampling process for determining a correct play. This repeated action of generating hands and calculating an estimate of tricks to be won for each legal alternative allows the best alternative to be selected by maximizing on these estimates. The experiments and results described in this paper show that these two ideas are helpful in creating a bridge-playing program that plays the game well and suggests the usefulness of these ideas for other games as well.

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

Share

COinS