Algorithms for Large Incomplete-Information Games

Incomplete-information games - such as most auctions, negotiations, card games, and future security games - cannot be solved using minimax search; rather, totally different algorithms are needed. I will overview our work on incomplete-information games from the last seven years. I will start by discussing lossless and lossy abstraction algorithms. I will present brand new results on the first lossy abstraction algorithms with bounds on solution quality. I will then discuss first-order algorithms for finding an epsilon-equilibrium in two-person zero-sum games; one of these algorithms has O(log(1/epsilon)) convergence, which is exponentially faster than prior first-order methods. I will then discuss how qualitative knowledge of the structure of equilibrium can be used to enable and speed up equilibrium finding.  I will finish with brand new results on safe opponent exploitation and strategy purification.  We have applied the techniques discussed in this talk to poker, yielding some of the world's best poker-playing programs.