Track:
Contents
Downloads:
Abstract:
IMP-minimax is the analog to minimax for games with imperfect information, like card games such as bridge or poker. It computes an optimal strategy for the game if the game has a single player and a certain natural property called perfect recall. IMP-minimax is described fully in a companion paper in this proceedings. Here we introduce an algorithm IMP-alpha-beta that is to IMP-minimax as alpha-beta is to minimax. That is, IMP-alpha-beta computes the same value as IMP-minimax does, but usually faster through pruning (i.e., not examining the value of some leaves). IMP-alpha-beta includes common pruning techniques and introduces a new technique, information set pruning. We suggest a natural model in which to study the performance of search algorithms for imperfect information games and we analyze IMP-alpha-beta in the context of that model. Our analysis includes both theorems bounding the performance of IMP-alpha-beta and empirical data indicating its average-case behavior.