Saturday, May 27, 2006
Using Monte Carlo Analysis In Poker Software
Monte Carlo Analysis can be used in analysing poker hands. There are many reasons people choose to use Monte Carlo Analysis. In poker, the most common reason is to get a quick answer for something that otherwise would take a prohibitively long-time to calculate.
I resisted using Monte Carlo Analysis for quite some time. I clung to my wish that a sufficently fast Poker Hand Evaluator Library would eliminate the need for needing to use woo-woo techniques like this.
To convince myself of the value of Monte Carlo Analysis I had to work through how to analyse the win odds for one or more players.
Calculating Win Odds
Consider the following code. It calculates the win odds for a player being dealt AKs against a random opponent.
This program takes about 299 seconds (nearly 5 minutes) to calculate with no board cards. That means the code is evaluating 14,084,025 Hands/Sec and a total of 2,097,572,400 (yes billions) of hand match ups. With three cards in the board it takes 0.263 seconds and a total of 1,070,190 hand match ups.
When there are cards on the board, this function is very usable. However, if you are calculating hole card win probabilities with this, then the algorithm is far too slow to be usable.
using System;
using System.Collections.Generic;
using HoldemHand;
namespace ConsoleApplication1
{
class Program
{
static void Main(string[] args)
{
// This code calculates the probablity of As Ks winning against
// another random hand.
ulong pocketmask = Hand.ParseHand("As Ks"); // Hole hand
ulong board = Hand.ParseHand(""); // No board cards yet
long wins = 0, ties = 0, loses = 0, count = 0;
// Iterate through all possible opponent hole cards
foreach (ulong oppmask in Hand.Hands(0UL, board pocketmask, 2))
{
// Iterate through all board cards
foreach (ulong boardmask in Hand.Hands(board, pocketmask oppmask, 5))
{
// Evaluate the player and opponent hands and tally the results
uint pocketHandVal = Hand.Evaluate(pocketmask boardmask, 7);
uint oppHandVal = Hand.Evaluate(oppmask boardmask, 7);
if (pocketHandVal > oppHandVal)
{
wins++;
}
else if (pocketHandVal == oppHandVal)
{
ties++;
}
else
{
loses++;
}
count++;
}
}
// Prints: Win 67.0446323092352%
Console.WriteLine("Win {0}%",
(((double)wins) + ((double)ties) / 2.0) / ((double)count) * 100.0);
}
}
}
Getting "Good Enough" Results Quickly
I'm not a perfectionist and appearently neither are many of the successful professional Texas Holdem Players.
In Phil Gordon's Little Green Book (a very good book I might add) he describes a very simple heuristic that can be calculate in your head that give the approximate odds of hitting your "outs". He calls this "the rule of 4 and 2". The way this heuristic works is that you count your outs. If you've just seen the flop (and not the turn card) then multiply the outs by 4 and you will have the approximate percentage of hitting your outs. If you've seen the turn (but not the river) you multiply the outs by 2 to get the approximate odds of hitting your outs.
These types of simple estimates are used by many of the professional players to help evaluate their situation. If an estimate is good enough for them, then it's probably good enough for the rest of us -- if used correctly. Monte Carlo Analysis is just a method for a computer to quickly estimate the odds in a specific situation.
Consider our previous example. It would take 299 seconds to iterate through all the possible situations and give us an exact anwers.
The following table was calculated using Monte Carlo Analysis. The number on the left is the number of trials, the second number is the estimated win odds (the exact odds were 67.0446323092352%). The third column is the difference between the exact answer and the estimate answer. The fourth column is the time taken in seconds.
Notice at 0.0013 seconds (1.3 milleseconds) we have 3 good digits. At 0.007 (7 milliseconds) we have about 4 good digits. At 0.0357 (36 milliseconds) we have 5 good digits. It's easy to see that we can get very good estimates in well less than a second.
The following code was used to generate the previous table.
using System;
using System.Collections.Generic;
using System.Runtime.InteropServices;
using HoldemHand;
namespace ConsoleApplication1
{
class Program
{
[DllImport("Kernel32.dll")]
private static extern bool QueryPerformanceCounter(out long lpPerformanceCount);
[DllImport("Kernel32.dll")]
private static extern bool QueryPerformanceFrequency(out long lpFrequency);
static void Main(string[] args)
{
// This code calculates the probablity of As Ks winning against
// another random hand.
ulong pocketmask = Hand.ParseHand("As Ks"); // Hole hand
ulong board = Hand.ParseHand(""); // No board cards yet
// Trial numbers
int[] trialsTable = {
10, 50, 100, 500, 1000, 5000, 10000, 15000, 20000,
25000, 30000, 40000, 50000, 100000, 150000, 200000,
500000, 1000000, 2000000, 5000000, 10000000, 20000000
};
// timer values
long start, freq, curtime;
// Get time frequency
QueryPerformanceFrequency(out freq);
Console.WriteLine("Trials,Wins,Difference,Duration");
foreach (int trials in trialsTable)
{
long wins = 0, ties = 0, loses = 0, count = 0;
// Get start time
QueryPerformanceCounter(out start);
// Iterate through a series board cards
foreach (ulong boardmask in
Hand.RandomHands(board, pocketmask, 5, trials))
{
// Get a random opponent hand
ulong oppmask = Hand.RandomHand(boardmask | pocketmask, 2);
// Evaluate the player and opponent hands
uint pocketHandVal = Hand.Evaluate(pocketmask | boardmask, 7);
uint oppHandVal = Hand.Evaluate(oppmask | boardmask, 7);
// Calculate Statistics
if (pocketHandVal > oppHandVal)
{
wins++;
}
else if (pocketHandVal == oppHandVal)
{
ties++;
}
else
{
loses++;
}
count++;
}
// Get Current Time
QueryPerformanceCounter(out curtime);
double duration = ((curtime - start) / ((double)freq));
// Correct answer is 67.0446323092352%
Console.WriteLine("{0},{1},{2}%,{3}",
trials,
string.Format("{0:0.00}%",
(((double)wins) + ((double)ties) / 2.0) / ((double)count) *100.0),
string.Format("{0:0.0000}",
67.0446323092352 - ((((double)wins) +
((double)ties) / 2.0) / ((double)count) * 100.0)),
string.Format("{0:0.0000}", duration));
}
}
}
}
I use the functions QueryPerformanceFrequency
and QueryPerformanceCount
to get highly accurate time duration information for the table. The rest of the code should look very much like the program we used to exhaustively calculate the odds. However, you will notice two new methods. They are Hand.RandomHand() and Hand.RandomHands().
Monte Carlo Analysis Helper Methods
The following method is intentionally similar to the IEnumerable<ulong>
Hands(ulong shared, ulong dead,
int ncards) method.
One additional argument is added which is the number of random hands that are to be iterated through by this enumerator.
public static IEnumerable<ulong> Hand.RandomHands(ulong shared, ulong dead, int ncards, int trials)
This IEnumerable method, allows the foreach command to iterate through random hands. The hands returned must meet the criterion specified. The number of hands specified in the last argument are returned.
public static IEnumerable<ulong> Hand.RandomHands(ulong shared, ulong dead, int ncards, double duration)
This method is similar to the previous method. However, rather than specifying the number of trials, a time duration is specified. This allows a time budget to be specified for getting an answer. I have a mild preference to using this version of these methods.
static public ulong Hand.RandomHand(ulong shared, ulong dead, int ncards)
This method allows a random hand to be returned. It must meet the specified input criterion.
Hopefully this is enough to get you started with Monte Carlo Analysis.
Comments:
<< Home
Nice work. I thought I'd share my method for estimating values versus n opponents. This method is a cross between a Monte Carlo and iteration; it ensures a flatter distribution despite random card selection. In addition, it returns values for 1 to n opponents, but takes less time than evaluating each group separately.
The general idea is this:
You are given a number of opponents and a current board (typically three cards.)
Maintain an n x 3 array which holds wins/losses/ties against each number of opponents (1 to n).
Iterate all possible holdings (and boards) against one opponent as usual. Like you said, this results in 1,070,190 matchups. You will add the result for each iteration in the wins/losses/ties row for one opponent.
As you go through each iteration, if that first result was not a loss, generate an additional random opponent hand (masking out cards as appropriate) and evaluate against that hand as well. Add the result in the wins/losses/ties row in the column for two opponents.
If that second result was not a loss, repeat again for three opponents. Etc.
If the first result was a loss, you can immediately chalk up a loss against every larger number of opponents, as well. (It doesn't matter which opponent was best; if one beats you, you've lost.) If the first was a win but the second was a loss, a loss can be chalked up against three or more; etc.
Once you've iterated through all of the possible 1-opponent situations, you are done and have solutions versus 1 through n opponents.
The 1-opponent analysis is not an approximation, since it's an iteration. For > 1 opponents, the result is a sort of monte-carlo with 1,070,190 runs, but one where the variance is reduced somewhat by the fact that all first opponent and board card combinations have been iterated through. This naturally ensures a flatter distribution over the range of possible holdings, reducing the variance inherent in a Monte Carlo simulation.
As you've shown, a million trials gives a very good estimate. If you have a million trials and you've ensured that every possible board is covered the same number of times, you're doing quite well.
The overall speed is enhanced by a few simple effects:
1. There is only one iteration loop of 1,070,190 trials, yet you have the net result of n simulations with 1,070,190 trials, or n * 1,070,190 trials.
2. The main iteration loop doesn't even call the prng, so it is very quick.
3. Any time an opponent causes a loss, all additional opponent cards and simulations can be skipped. These creates nearly zero-time iterations as far as further opponents are concerned. For very weak hands, nearly all of the processing is skipped, as the player keeps losing against opponent one.
If this appraoch is still taking too long for a given purpose, you can apply the same ideas in a more Monte-Carlo variant: just iterate through the board card permutations and treat the first opponent just like the other.
For each of the 2,162 possible board pairings, do 50 simulations against the first opponent; for each, if the player hasn't lost yet, simulate an additional opponent, then the next, etc. The same technique of applying losses to all opponents after the first defeat apply.
Doing this, you'll have 2,162 * 50 = 108,100 trials, and you'll be done simulating against 1 through n opponents in a much shorter time than running n simulations - and again, because you have exactly 50 instances of every possible board pairing, your results will be slightly less variable than a real Monte Carlo.
I haven't done this yet using your evaluator, but I expect it to be faster than mine!
Post a Comment
The general idea is this:
You are given a number of opponents and a current board (typically three cards.)
Maintain an n x 3 array which holds wins/losses/ties against each number of opponents (1 to n).
Iterate all possible holdings (and boards) against one opponent as usual. Like you said, this results in 1,070,190 matchups. You will add the result for each iteration in the wins/losses/ties row for one opponent.
As you go through each iteration, if that first result was not a loss, generate an additional random opponent hand (masking out cards as appropriate) and evaluate against that hand as well. Add the result in the wins/losses/ties row in the column for two opponents.
If that second result was not a loss, repeat again for three opponents. Etc.
If the first result was a loss, you can immediately chalk up a loss against every larger number of opponents, as well. (It doesn't matter which opponent was best; if one beats you, you've lost.) If the first was a win but the second was a loss, a loss can be chalked up against three or more; etc.
Once you've iterated through all of the possible 1-opponent situations, you are done and have solutions versus 1 through n opponents.
The 1-opponent analysis is not an approximation, since it's an iteration. For > 1 opponents, the result is a sort of monte-carlo with 1,070,190 runs, but one where the variance is reduced somewhat by the fact that all first opponent and board card combinations have been iterated through. This naturally ensures a flatter distribution over the range of possible holdings, reducing the variance inherent in a Monte Carlo simulation.
As you've shown, a million trials gives a very good estimate. If you have a million trials and you've ensured that every possible board is covered the same number of times, you're doing quite well.
The overall speed is enhanced by a few simple effects:
1. There is only one iteration loop of 1,070,190 trials, yet you have the net result of n simulations with 1,070,190 trials, or n * 1,070,190 trials.
2. The main iteration loop doesn't even call the prng, so it is very quick.
3. Any time an opponent causes a loss, all additional opponent cards and simulations can be skipped. These creates nearly zero-time iterations as far as further opponents are concerned. For very weak hands, nearly all of the processing is skipped, as the player keeps losing against opponent one.
If this appraoch is still taking too long for a given purpose, you can apply the same ideas in a more Monte-Carlo variant: just iterate through the board card permutations and treat the first opponent just like the other.
For each of the 2,162 possible board pairings, do 50 simulations against the first opponent; for each, if the player hasn't lost yet, simulate an additional opponent, then the next, etc. The same technique of applying losses to all opponents after the first defeat apply.
Doing this, you'll have 2,162 * 50 = 108,100 trials, and you'll be done simulating against 1 through n opponents in a much shorter time than running n simulations - and again, because you have exactly 50 instances of every possible board pairing, your results will be slightly less variable than a real Monte Carlo.
I haven't done this yet using your evaluator, but I expect it to be faster than mine!
# posted by 
: 5:32 PM
: 5:32 PM << Home
