Efficient computation of behavior strategies

We propose the sequence form as a new strategic description for an extensive game with perfect recall. It is similar to the normal form but has linear instead of exponential complexity and allows a direct representation and efficient computation of behavior strategies. Pure strategies and their mixed strategy probabilities are replaced by sequences of consecutive choices and their realization probabilities. A zero-sum game is salved by a corresponding linear program that has linear size in the size of the game tree. General two-person games are studied in the paper by Koller el al., 1996 (Games Econ. Behav. 14, 247-259). (C) 1996 Academic Press, Inc.