Monday, September 24, 2012

Poker 4: Monte Carlo Analysis

Why using Monte Carlo to compute poker probabilities ?
Because in a number of cases, the number of possibilities is way to large to be explored.

For example, computing the equity of on player's PreFlop hand that has NbOpp opponents sitting around the table requires to go through N different game configurations:
$\left( \begin{array}{c} 52-2(\text{NbOpp}+1) \\ 5 \\ \end{array} \right)\prod _{i=1}^{\text{NbOpp}} \left( \begin{array}{c} 52-2i \\ 2 \\ \end{array} \right)$
Even a very fast hand evaluator on a modern machine does not parse much more than 300 millions hands per second, which leaves the exact computation of a PreFlop hand equity for 4 or more players completely out of reach.

As cheesy as it may be, the table below helps visualizing the kind of numbers at play.

Naturally the numbers are meaningless past the 1 or 2 opponents case.
So computing the equity of PreFlop hand in the general case is practically impossible.
Let us turn to Monte Carlo simulations to at least approach these values.

I have used the Mersenne-Twister random number generator (implemented in Mathematica 8.0.4) to run these simulations. For each of the 169 PreFlop hands, and a number of opponents from 1 to 9, I have generated 303 million games. The value of the equity, specifically the fraction of the equity contributed by the wins and the value of the equity contributed by the ties, was recorded after each step of 1 million random games.

The very good - and surprising - news is that the Monte Carlo seems to converge very fast. For all PreFlop hands, a precision of ~0.1% in the aggregate (i.e. wins+ties) equity (well enough for any practical purpose) is reached after a few million random games. Disclaimer: I do not advance any proof of the convergence, only report my observations.

Below is a CDF displaying the evolution of the value of the equity contributed by wins, and that contributed by ties, for each PreFlop hand and all number of opponents.

You can view it with the free CDF (computable document format) player.
The CDFs were created with Mathematica 8.0.4 and the CDF player enables you to locally run Mathematica code.
You may have to 'Enable Dynamics' to view the contents.
Warning: The initialization of this CDF is very slow. It downloads and imports a ~20MB. Count ~1mn (!)

You can browse the results and judge by yourself. If, like me, you are satisfied with the convergence, you can consider the PreFlop hand equity tables below.

The first series of tables contains for each PreFlop hand and each number of opponent the aggregate equity (wins+ties), and next to it between brackets the fraction of the equity contributed by the ties. In almost all interesting cases (the reasonably strong hands) the latter is very small.

The second series of tables is based on the same data, except the aggregate equity is multiplied by the number of players (i.e the number of opponents + 1). This is to compare the amount that the player has put in the pot and the amount the player stands to win with his PreFlop hand. The breakeven is 100%.

• PreFlop hand equity

• PreFlop hand equity times player's bet

The data is available in .xlsx format, should you wish to manipulate it.

Now let us try to show a meaningful overview of this data.
Below is a CDF displaying a 3D representation of the tables.
The first 3D graph represents the PreFlop hand equity, and the second the PreFlop hand equity times player's bet. You can rotate the graphs so as to examine their shape in details.

You can view it with the free CDF (computable document format) player.
The CDFs were created with Mathematica 8.0.4 and the CDF player enables you to locally run Mathematica code.
You may have to 'Enable Dynamics' to view the contents.

One can also be interested in how the strength of a preFlop hand changes with the number of opponents. In the series of tables below we have sorted the PreFlop hand equities in decreasing order for each number of opponents. The ranking is the leftmost column, and for each number of opponents, the table shows the PreFlop hand/equity/equity times player's bet.

• Sorted PreFlop hand equity

Nothing is more convenient than a direct view of the evolution a given PreFlop hand strength as the number of opponents change.

Below is a CDF displaying a all the data for a PreFlop hand: equity contributed by wins/ties, equity measured as fraction of a player's bet, contributed by wins/ties, and ranking (from 1 to 169).

You can view it with the free CDF (computable document format) player.
The CDFs were created with Mathematica 8.0.4 and the CDF player enables you to locally run Mathematica code.
You may have to 'Enable Dynamics' to view the contents.
Finally we can use this Monte Carlo approach to assess the equity of a PreFlop hand in real game settings.

Here, only one player's hole cards are determined, in addition to the table already showing. The other players' hole cards are unknown and randomly generated by the Monte Carlo simulator. So are the table cards not yet showing. But there is one difference: The table cards are randomly generated, assuming all cards have the same probability, while the other players' cards are randomly generated under arbitrary constraints. They can be assumed to be of a certain type. It is up to the user to impose these constraints based on what he/she feels based on a player's behavior, bet, position around the table, etc.

The PreFlop hands available categories are in the table below. Several categories can be selected at the same time, expanding the range of possibilities the Monte Carlo engine randomly draws from. Category 'All' prevails and means no contraint. Category 'Others' means any PreFlop hand that is not in another category. The number of PreFlop hands in each category is indicated to get a sense of how narrow a category is, i.e. how strong a constraint is. If the cards making a PreFlop hand in a category are not available (player hole cards, or table cards), then the category is reduced accordingly.

Below is an interactive CDF,  in which you can set the number of players, choose or shuffle the hole cards and the table cards Flop/Turn/River. The result is the equity of the player's hand, split in (1) the equity contributed by wins (i.e. the player takes the whole pot) and (2) the equity contributed by ties (i.e. at least two players have the best hand and the pot is equally split between the winners). The number of random games generated is 1 million. Based on the the Monte Carlo convergence speed observed above in this post, this is precise enough to help a human player make a decision. The result is displayed in a fraction of a second, so you can run it several times in a row and notice that two results seldom differ by more than 0.10%.

You can view them with the free CDF (computable document format) player.
The CDFs were created with Mathematica 8.0.4 and the CDF player enables you to locally run Mathematica code.
You may have to 'Enable Dynamics' to view the contents.

The hand evaluator is coded in C for speed. The resulting executable must be stored in a directory named 'MathLinkExec' under your home directory, for the CDF to know where to look the hand evaluator. Beware: You must give the CDF access to this executable only if you trust that there is nothing harmful in it. Naturally, I guarantee this executable is indeed safe !

More generally, in the github repo containing everything about these poker posts, there is a one to one match between the source files in the MathLink folder and the executable in the Exec folder.

• Hand evaluator executable - to be stored in <user>/MathLinkExec/ and named equityPreFlopHand. For example under OSX, you must have the executable as follows: ~/MathLinkExec/equityPreFlopHand