《math of poker》由会员分享，可在线阅读，更多相关《math of poker（8页珍藏版）》请在金锄头文库上搜索。
1、Approximating Game-Theoretic Optimal Strategies for Full-scale PokerD. Billings, N. Burch, A. Davidson, R. Holte, J. Schaeffer, T. Schauenberg, and D. Szafron Department of Computing Science, University of Alberta Edmonton, Alberta, T6G 2E8, Canada Email:?darse,burch,davidson,holte,jonathan,terence,
2、duane?cs.ualberta.caAbstractThe computation of the first complete approxima- tions of game-theoretic optimal strategies for full- scale poker is addressed. Several abstraction tech- niques are combined to represent the game of 2- player Texas Holdem, having size? ? ? , using closely related models e
3、ach having size? . Despite the reduction in size by a factor of 100 billion, the resulting models retain the key prop- erties and structure of the real game. Linear pro- grammingsolutionsto theabstractedgame areused to create substantially improved poker-playing pro- grams, able to defeat strong hum
4、an players and be competitive against world-class opponents.1IntroductionMathematical game theory was introduced by John von Neu- mann in the 1940s, and has since become one of the founda- tions of modern economics von Neumann and Morgenstern, 1944.Von Neumann used the game of poker as a basic model
5、 for 2-player zero-sum adversarial games, and provedthe first fundamental result, the famous minimax theorem. A few years later, John Nash added results for-player non- cooperative games, for which he later won the Nobel Prize Nash, 1950. Many decision problems can be modeled using game theory, and
6、it has been employed in a wide variety of domains in recent years. Of particular interest is the existence of optimal solutions, or Nash equilibria. An optimal solution provides a random- ized mixed strategy, basically a recipe of how to play in each possible situation. Using this strategy ensures t
7、hat an agent will obtain at least the game-theoretic value of the game, re-gardless of the opponents strategy. Unfortunately, finding exact optimal solutions is limited to relatively small problem sizes, and is not practical for most real domains. This paper explores the use of highlyabstracted math
8、emat- ical models which capture the most essential properties of the real domain, such that an exact solution to the smaller prob- lem provides a useful approximation of an optimal strategy for the real domain. The application domain used is the gameof poker, specifically Texas Holdem, the most popu
9、lar form of casino poker and the poker variant used to determine the world champion at the annual World Series of Poker.Dueto thecomputationallimitationsinvolved, onlysimpli-fied pokervariations have beensolved in the past (e.g. Kuhn, 1950; Sakaguchi and Sakai, 1992). While these are of the- oretica
10、l interest, the same methods are not feasible for real games, which are too large by many orders of magnitude (Koller and Pfeffer, 1997). Shi and Littman, 2001 investigated abstraction tech- niques to reduce the large search space and complexity of theproblem, using a simplified variant of poker. Ta
11、kusagawa, 2000 created near-optimal strategies for the play of threespecific Holdem flops and betting sequences. Selby, 1999 computed an optimal solution for the abbreviated game ofpreflop Holdem. Using new abstraction techniques, we have produced vi- able “pseudo-optimal” strategies for the game of
12、 2-player Texas Holdem. The resulting poker-playing programs have demonstrated a tremendous improvement in performance. Whereas the previous best pokerprograms were easily beaten by any competent human player, the new programs are capa- ble of defeating very strong players, and can hold their own ag
13、ainst world-class opposition.Although some domain-specific knowledge is an asset in creating accurate reduced-scale models, analogous methods can be developed for many other imperfect information do- mains and generalized game trees. We describe a general method of problem reformulation that permits
14、 the indepen- dent solution of sub-trees by estimating the conditional prob- abilities needed as input for each computation. This paper makes the following contributions:1. Abstraction techniques that can reduce an? poker search space to a manageable? ? , without losing the most important properties
15、 of the game.2. A poker-playing program that is a major improvement over previous efforts, and is capable of competing with world-class opposition.2Game TheoryGame theory encompasses all forms of competition between two or more agents. Unlike chess or checkers, poker is a game of imperfect informati
16、on and chance outcomes. It can be represented with an imperfect information game tree hav- ing chance nodes and decision nodes, which are grouped into information sets.Since the nodes in this tree are not independent, divide- and-conquer methods for computing sub-trees (such as the alpha-beta algorithm) are not applicable. For a more detailed description of imperfect information game tree structure, see Koller and Megiddo, 1992. A strategy
