A recursive algorithm for an imperfect information game with perfect recall

Author

Cheng Liu

Date of Award

8-1992

Degree Type

Thesis

Degree Name

Master of Science

Major

Computer Science

Major Professor

David C. Mutchler

Committee Members

Jean Blair. David Straight

Abstract

The traditional method to find an optimal strategy for a general n-player game is to enumerate all pure strategies and use a linear programming technique to find the strategy with highest payoff. Unfortunately, the number of pure strategies in even a small game is too large to be enumerated. In this work we developed a recursive algorithm to find an optimal solution in a one player game with perfect recall. This algorithm evaluates each leaf in the game tree only once. This significantly reduces the time compared to the traditional method. This algorithm can also be used in an n-player game with perfect recall to check if a pure strategy is an equilibrium point.

Recommended Citation

Liu, Cheng, "A recursive algorithm for an imperfect information game with perfect recall. " Master's Thesis, University of Tennessee, 1992.
https://trace.tennessee.edu/utk_gradthes/12206