The use of imperfect information concepts from game theory in the solution of games of simultaneous moves in artificial intelligence

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.