Saturday, 12 September 2009

pr.probability - Monte Carlo method and possible applications to computer poker?

Monte Carlo methods are appropriate for analyzing some systems involving chance, not incomplete information. Monte Carlo methods tell you nothing about how to model a poker strategy.



For general games of incomplete information, you should look up game theory (and not combinatorial game theory), a branch of mathematics which applies well to games of incomplete information such as poker. Some of the earliest work on game theory involved the analysis of model poker games. A common misconception is that bluffing is not mathematical, but this is simply wrong. A book which seems to have been written for mathematicians is "The Mathematics of Poker" by Bill Chen and Jerrod Ankenman. For example, they study many model poker games where players are dealt a uniformly distributed number on [0,1] with restricted betting options, as did Borel and von Neumann.



Polaris plays one form of poker, 2-player limit hold'em. This is not the form of poker you see on TV, which is usually multiplayer No Limit hold'em. The 2-player game with fixed bet sizes is still too large combinatorially to solve completely, but half-size problems can be solved (preflop games, and postflop games), and some of the research has been based on trying to glue these half-solutions together. The result, after much effort, has been strong heads-up limit hold'em programs like Polaris which crush casual players, and are only behind the best human players. However, these techniques do not extend easily to No Limit Hold'em, or to multiplayer versions of the game.



Other variants such as tournaments with low blinds or different poker games such as Razz and draw poker (which is rarely played now) are more susceptible to complete or numerical solutions. Here is an approximate Nash equilibrium calculator for single table tournaments when players are restricted to raising all-in or folding, and at most 3 players can enter the pot, which is a reasonable approximation to a commonly played variant. In practice, exploitive adjustments are important as well.



If you want to understand the current state of poker AI, then I recommend starting by exploring the web page of the Computer Poker Research Group (University of Alberta) which contains some history and research articles.

No comments:

Post a Comment