Masters Theses

Date of Award

3-1981

Degree Type

Thesis

Degree Name

Master of Science

Major

Computer Science

Major Professor

Michael G. Thomason

Committee Members

Lawrence Husch

Abstract

Game-playing programs in artificial intelligence have largely dealt with two-player games with sequential moves. Many other classes of games have not been examined closely. The present study develops solution methods for two-player games with simultaneous moves.

The first portion of the thesis is aimed at the artificial intelligence researcher interested in game playing and reviews some results from game theory which are important for extending the artificial intelligence perspective to classes of games other than two-person zero-sum games. The concept of a player's rationality is discussed and is used to justify a best-reply algorithm which extends the minimax solution for perfect information zero-sum games from two-person to n-person games. Then, classification criteria for games are reviewed and solution methods for the different classes are described.

The main result of this thesis is a simultaneous move algorithm (ASMA), which was developed from game theoretic concepts as a basic method for solving games of simultaneous moves. In a modular way, heuristics can be used with ASMA to increase its efficiency in game-playing programs.

A two-player version of a DIPLOMACY-like game called REDIPT is described, and a game-playing program of the same name is developed. ASMA, the main subroutine of the program REDIPT, is used to calculate a solution for the game.

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

Share

COinS