Click here to Skip to main content
14,662,524 members
Articles » General Programming » Game Development » Games
Article
Posted 1 Dec 2005

Stats

956K views
17.5K downloads
164 bookmarked

Fast, Texas Holdem Hand Evaluation and Analysis

Rate this:
4.89 (98 votes)
Please Sign up or sign in to vote.
4.89 (98 votes)
18 Apr 2006GPL3
A C# native, fast Texas Holdem Hand Evaluator.

Hand Odds Application Image

Introduction

Recently, I was laid up with a prolonged illness. During that time, I needed to entertain myself. I quickly determined that daytime TV was not worth watching. Instead, I started playing Texas Holdem online. A few thousand hands later, I determined that the medication I was taking was interfering with my ability to concentrate. This limited the skill level that I could consistently play at. So instead of continuing to play Texas Holdem poorly, I decided to write a software to analyze poker.

The first thing I realized I needed was a fast way to iterate through and evaluate Texas Holdem hands. After searching the net and trying several libraries, I found that nothing met my needs. Native C# code was too slow, and the best C library (poker-eval) was very difficult to connect to C# using interop. So I started writing my own C# library.

After a few days of work, I was able to evaluate a few hundred thousand hands a second. This was several orders of magnitude slower than I needed. So I looked at poker-eval again. After working through this gnarly, heavily macroed and table driven C library, I realized that the techniques they were using should work with C#. I ported the portion of the tables and evaluation functions that I needed to analyze Texas Holdem. The resulting code is definitely fast enough for most of my needs.

The following article walks through using my C# variant of the poker.eval hand evaluator library, and includes a few of the nifty tools I built with it. These tools include:

  • A fast Texas Holdem hand evaluator class library with a benchmark application.
  • A vector card image class for displaying high quality, scalable card faces.
  • A Hand Odds application that displays hand probability like you see on TV Poker shows.
  • An Odds Grid application that gives the chances of a hand winning against an average opponent.
  • A Jacks or Better Video Poker trainer. This program helps to learn how to play Jacks or Better Video poker perfectly.

Taking from the Best

When analyzing poker hands, doing an exhaustive search quickly is much more straightforward and more accurate than having to do a Monte Carlo simulation or coming up with some clever heuristic. The Poker-eval library appears to be one of the fastest and the most used Poker libraries around.

Poker-eval can be found at the poker-eval web page. It is a very fast, heavily macroed C library. It has limited documentation and is very gnarly (which means it's not terribly programmer friendly), but it is very, very fast -- which makes up for most other deficiencies.

On the other hand, most object oriented poker hand evaluation libraries like to have classes for card decks, individual cards, and poker hands. These abstractions, though nice for human programmers, really get in the way of making a fast library. Lots of objects have to be created and deleted to do even simple analysis. This makes this style of a library slow.

Poker-eval dispenses with all of this object oriented non-sense and defines everything as bit-fields in unsigned integers. This may not be the clearest way for humans to represent this information, but for computers it's natural, and in this case natural means fast.

Ease of Use

My second goal (after making it fast) was to make it easy to use this class for simple things. The class is built by wrapping the underlying, fast, static methods with a C# class. This makes the code easy to use without having to get into the internal details of the implementation. However, the underlying static methods can still be accessed for more advanced usage.

The following example shows how to create instances of two Texas Holdem hands, prints out a description of each hand, and then compares the two hands:

using System;
using HoldemHand;

// Simple example of comparing hands using Hand instances.
class Program
{
    static void Main(string[] args)
    {
        string board = "4d 5d 6c 3c 2d";
        Hand player1 = new Hand("ac as", board);
        Hand player2 = new Hand("ad ks", board);

        // Print out a hand description: in this case both hands are
        // A straight, six high
        Console.WriteLine("Player1 Hand: {0}", player1.Description);
        Console.WriteLine("Player2 Hand: {0}", player2.Description);

        // Compare hands
        if (player1 == player2)
        {
            Console.WriteLine("player1's hand is" + 
                              " equal to player2's hand");
        } 
        else if (player1 > player2)
        {
            Console.WriteLine("player1's hand is " + 
                              "greater than player2's hand");
        }
        else
        {
            Console.WriteLine("player2's hand is greater" + 
                              " than or equal player1's hand");
        }
    }
}

Make it Fast

My primary goal when porting Poker-eval to C# was to make a very fast native C# poker hand evaluator that does not require any interop.

Currently, using custom iteration, I can get between 23 million and 33 million hand evaluations per second on my laptop computer (and even more on my desktop computer) depending on the number of cards in each hand.

If I use C# iterator functions, I get about half that speed, but the C# iterator functions are much easier to use than hand in-lined iterations.

Benchmark Application Image

By the way, you must run the benchmark twice to get good results. The first time, you are benchmarking the JIT time too. The second run produces more reasonable results.

The Poker-eval Model

The Poker-eval defines two basic kinds of masks. One is a hand mask. This consists of a bit field containing 52 bits, one bit for each card. A hand is represented by ORing each card bit to create a definition of a hand.

The second kind of mask is called a hand value. A hand value is produced by passing a hand mask into a Poker-eval evaluation function. A hand value can be compared, using standard integer comparison operators, with other hand values to determine whether one hand beats another.

To make the code fast, I've preserved the notion of a hand mask and a hand value. Most of the high speed code is defined in static member functions found in the HoldemHand.Hand class. The following code snippet shows how to parse a string description of a hand into a hand mask and then evaluate the hand mask to create a hand value:

using System;
using HoldemHand;

// Simple example of parsing and evaluating a Texas Holdem hand.
class Program
{
    static void Main(string[] args)
    {
        // Parse hand into a hand mask
        ulong handmask = Hand.ParseHand("ac as 4d 5d 6c 7c 8d");

        // Convert hand mask into a compariable hand value.
        uint handval = Hand.Evaluate(handmask, 7);

        // Print a description of the hand.
        Console.WriteLine("Hand: {0}", 
                Hand.DescriptionFromHandValue(handval));
    }
}

Hand Iteration

Iterating through hands simply requires toggling all of the possible 7 bit combinations for 7 card hands or 5 bit combinations for 5 card hands. To assist in this task, C# iterators can be used to simplify the process.

There are two iterator functions defined:

static IEnumerable Hand.Hands(int numberOfCards)

and

static IEnumerable Hand.Hands(ulong shared, ulong dead, int numberOfCards)

The Hand.Hands(int numberOfCards) method iterates through all possible hand mask combinations for a given number of cards.

The Hand.Hands(ulong shared, ulong dead, int numberOfCards) method iterates through all possible hand mask combinations for the specified number of cards, where the hand mask shares the cards passed in the shared argument and must not contain cards in from the dead argument.

using System;
using HoldemHand;

// Simple example of iteration using Holdem.Hand class.
class Program
{
    static void Main(string[] args)
    {
        long count = 0;

        /// Parse hand and create a mask
        ulong partialHandmask = Hand.ParseHand("ac as 4d 5d 6c");

        /// iterate through all 7 card hands
        /// that share the cards in our partial hand.
        foreach (ulong handmask in Hand.Hands(partialHandmask, 0UL, 7))
        {
            count++;
        }

        Console.WriteLine("Total hands to check: {0}", count);
    }
}

Though the C# iterator functions are simple to use and reasonably fast for many things, they aren't as fast as inlining the equivalent loops.

The equivalent code with the iteration code inlined looks like the following:

using System;
using HoldemHand;

// Simple inlined iteration using Holdem.Hand class.
class Program
{
    static void Main(string[] args)
    {
        int     _i1, _i2;
        ulong   _card1, _card2, dead, handmask;
        long    count = 0;

        /// Parse hand and create a mask
        ulong partialHandmask = Hand.ParseHand("ac as 4d 5d 6c");

        // We should not repeat cards we already hold.
        dead = partialHandmask;

        // Loop through the all remaining two card combinations.
        for (_i1 = Hand.NumberOfCards - 1; _i1 >= 0; _i1--)
        {
            _card1 = (1UL << _i1);
            if ((dead & _card1) != 0) continue; // Ignore dead cards
            for (_i2 = _i1 - 1; _i2 >= 0; _i2--)
            {
                _card2 = (1UL << _i2);
                if ((dead & _card2) != 0) continue; // Ignore dead cards
                // OR back our 5 card partial hand mask to make a seven card hand.
                handmask = _card1 | _card2 | partialHandmask;
                count++;
            }
        }

        Console.WriteLine("Total hands to check: {0}", count);
    }
}

Though much uglier than using C# iterator methods, this inlined loop is usually 2x to 3x times faster.

Building a Hand Odds Calculator

Hand Odds Application Image

If you've watched poker on TV, you've seen the on-screen display of the odds each player has for winning the hand. This application makes the same calculations used on those TV shows.

The underlying algorithm is extremely simple. All possible board combinations are iterated through. For each board combination, a hand mask is calculated for each set of pocket cards. The hand masks are evaluated and then compared. The winners are tallied for each player. The probability is determined by simply dividing the winning hands for each player by the total number of hands.

The following code illustrates how this is calculated:

using System;
using HoldemHand;

// Iterate through all possible hands
// to see how these two hands compare
class Program
{
    static void Main(string[] args)
    {
        // Create hand masks
        ulong player1Mask = Hand.ParseHand("as ks");
        ulong player2Mask = Hand.ParseHand("jd jc");
        ulong deadcards = Hand.ParseHand("2h 8s");
        long player1Wins = 0, player2Wins = 0;
        long count = 0;

        // Iterate through all possible boards
        foreach (ulong board in Hand.Hands(0UL, 
                       deadcards | player1Mask | player2Mask, 5))
        {
            // Create a hand value for each player
            uint player1HandValue = Hand.Evaluate(board | player1Mask, 7);
            uint player2HandValue = Hand.Evaluate(board | player2Mask, 7);

            // Calculate Winners
            if (player1HandValue > player2HandValue)
            {
                player1Wins++;
            }
            else if (player1HandValue < player2HandValue)
            {
                player2Wins++;
            }
            count++;
        }

        // Print results
        Console.WriteLine("Player1: {0:0.0}%", 
                ((double) player1Wins) / ((double) count) * 100.0);
        Console.WriteLine("Player2: {0:0.0}%", 
                ((double) player2Wins) / ((double) count) * 100.0);
    }
}

Building a Detailed Hand Odds Calculator

Hand Odds Grid Application Image

When you are playing poker on-line, you don't have access to other players' pocket cards. One technique that can be used is to analyze the potential of a player's hand compared to an average opponent. This is calculated by comparing all possible boards and all possible opponent pocket cards to the player’s hand. This gives a good feeling for the potential of a hand. However, rarely are you playing against an "average" player. So keep that in mind if you are using this technique in real poker play.

The following code example shows how this calculation is made:

using System;
using HoldemHand;

// Compare a player hand to all possible opponent hands
class Program
{
    static void Main(string[] args)
    {
        ulong playerMask = Hand.ParseHand("as ks"); // Player Pocket Cards
        ulong board = Hand.ParseHand("Ts Qs 2d");   // Partial Board
        // Calculate values for each hand type
        double[] playerWins =   { 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0 };
        double[] opponentWins = { 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0 }; 
        // Count of total hands examined.
        long count = 0;

        // Iterate through all possible opponent hands
        foreach (ulong opponentMask in Hand.Hands(0UL, 
                             board | playerMask, 2)) {
            // Iterate through all possible boards
            foreach (ulong boardMask in Hand.Hands(board, 
                           opponentMask | playerMask, 5))
            {
                // Create a hand value for each player
                uint playerHandValue = 
                       Hand.Evaluate(boardMask | playerMask, 7);
                uint opponentHandValue = 
                       Hand.Evaluate(boardMask | opponentMask, 7);

                // Calculate Winners
                if (playerHandValue > opponentHandValue)
                {
                    // Player Win
                    playerWins[Hand.HandType(playerHandValue)] += 1.0;
                }
                else if (playerHandValue < opponentHandValue)
                {
                    // Opponent Win
                    opponentWins[Hand.HandType(opponentHandValue)] += 1.0;
                }
                else if (playerHandValue == opponentHandValue)
                {
                    // Give half credit for ties.
                    playerWins[Hand.HandType(playerHandValue)] += 0.5;
                    opponentWins[Hand.HandType(opponentHandValue)] += 0.5;
                }
                count++;
            }
        }

        // Print results
        Console.WriteLine("Player Results");
        Console.WriteLine("High Card:\t{0:0.0}%", 
          playerWins[(int) Hand.HandTypes.HighCard] / ((double)count) * 100.0);
        Console.WriteLine("Pair:\t{0:0.0}%", 
          playerWins[(int) Hand.HandTypes.Pair]/((double) count)*100.0);
        Console.WriteLine("Two Pair:\t{0:0.0}%", 
          playerWins[(int) Hand.HandTypes.TwoPair] / ((double)count) * 100.0);
        Console.WriteLine("Three of Kind:\t{0:0.0}%", 
          playerWins[(int) Hand.HandTypes.Trips] / ((double)count) * 100.0);
        Console.WriteLine("Straight:\t{0:0.0}%", 
          playerWins[(int) Hand.HandTypes.Straight] / ((double)count) * 100.0);
        Console.WriteLine("Flush:\t{0:0.0}%", 
          playerWins[(int) Hand.HandTypes.Flush] / ((double)count) * 100.0);
        Console.WriteLine("Fullhouse:\t{0:0.0}%", 
          playerWins[(int)Hand.HandTypes.FullHouse] / ((double)count) * 100.0);
        Console.WriteLine("Four of a Kind:\t{0:0.0}%", 
          playerWins[(int)Hand.HandTypes.FourOfAKind] / ((double)count) * 100.0);
        Console.WriteLine("Straight Flush:\t{0:0.0}%", 
          playerWins[(int)Hand.HandTypes.StraightFlush] / ((double)count) * 100.0);

        Console.WriteLine();
        Console.WriteLine("Opponent Results");
        Console.WriteLine("High Card:\t{0:0.0}%", 
          opponentWins[(int)Hand.HandTypes.HighCard] / ((double)count) * 100.0);
        Console.WriteLine("Pair:\t{0:0.0}%", 
          opponentWins[(int)Hand.HandTypes.Pair] / ((double)count) * 100.0);
        Console.WriteLine("Two Pair:\t{0:0.0}%", 
          opponentWins[(int)Hand.HandTypes.TwoPair] / ((double)count) * 100.0);
        Console.WriteLine("Three of Kind:\t{0:0.0}%", 
          opponentWins[(int)Hand.HandTypes.Trips] / ((double)count) * 100.0);
        Console.WriteLine("Straight:\t{0:0.0}%", 
          opponentWins[(int)Hand.HandTypes.Straight] / ((double)count) * 100.0);
        Console.WriteLine("Flush:\t{0:0.0}%", 
          opponentWins[(int)Hand.HandTypes.Flush] / ((double)count) * 100.0);
        Console.WriteLine("Fullhouse:\t{0:0.0}%", 
          opponentWins[(int)Hand.HandTypes.FullHouse] / ((double)count) * 100.0);
        Console.WriteLine("Four of a Kind:\t{0:0.0}%", 
          opponentWins[(int)Hand.HandTypes.FourOfAKind] / ((double)count) * 100.0);
        Console.WriteLine("Straight Flush:\t{0:0.0}%", 
          opponentWins[(int)Hand.HandTypes.StraightFlush] / ((double)count) * 100.0);
    }

Building a Jacks or Better Video Poker Trainer

Video Poker Trainer Application Image

A while back, a family member loaned me a hand held Jacks or Better poker game. After playing it for a few hours, I began to wonder what the correct strategy for playing each hand was. To explore this, I built a Jacks or Better video poker trainer.

The program is a very simple Jacks or Better Video poker application. The one difference is that it tells you what the best expected value is (see the text in the upper right) and the current expected value based on the hold settings.

The algorithm for computing the best expected value is straightforward. There are 32 possible hold settings. Each of the 32 possible values is iterated through in Main(). For each hold setting, the expected value is calculated by iterating through all possible 5 card hands and summing the winning amount. The expected value is simply the summed winnings divided by the total number of hands evaluated. The best expected value and its associated hold mask is saved and printed out. The following code illustrates this. To modify this to handle a different video poker payout schedule, you need to replace the JacksOrBetterWinnings function with the alternate payout schedule.

using System;
using HoldemHand;

// Determine best possible cards to hold.
class Program
{
    // Returns the pay off on a 9/6 Jacks or better machine
    static double JacksOrBetterWinnings(uint handval, int coins)
    {
        switch ((Hand.HandTypes)Hand.HandType(handval))
        {
            case Hand.HandTypes.StraightFlush:
                if (Hand.CardRank((int)Hand.TopCard(handval)) == Hand.RankAce)
                    if (coins < 5) return 250.0 * coins;
                    else return 4000.0;
                return 40.0 * coins;
            case Hand.HandTypes.FourOfAKind: return 20.0 * coins;
            case Hand.HandTypes.FullHouse: return 9.0 * coins;
            case Hand.HandTypes.Flush: return 6.0 * coins;
            case Hand.HandTypes.Straight: return 4.0 * coins;
            case Hand.HandTypes.Trips: return 3.0 * coins;
            case Hand.HandTypes.TwoPair: return 2.0 * coins;
            case Hand.HandTypes.Pair:
                if (Hand.CardRank((int)Hand.TopCard(handval)) >= Hand.RankJack)
                    return 1.0 * coins;
                break;
        }
        return 0.0;
    }

    // Calculate the expected value with the specified holdmask
    static double ExpectedValue(uint holdmask, ref int[] cards, int bet)
    {
        ulong handmask = 0UL, deadcards = 0UL;
        double winnings = 0.0;
        long count = 0;

        // Create Hold mask and Dead card mask
        for (int i = 0; i < 5; i++)
        {
            if ((holdmask & (1UL << i)) != 0)
                handmask |= (1UL << cards[i]);
            else
                deadcards |= (1UL << cards[i]);
        }

        // Iterate through all possible masks
        foreach (ulong mask in Hand.Hands(handmask, deadcards, 5))
        {
            winnings += JacksOrBetterWinnings(Hand.Evaluate(mask, 5), bet);
            count++;
        }

        return (count > 0 ? winnings / count : 0.0);
    }

    // Calculate Best cards to hold.
    static void Main(string[] args)
    {
        double bestev = 0.0; 
        ulong bestmask = 0UL;
        int bet = 5; // coins bet

        string[] cardString = { "as", "ks", "kh", "4s", "4d" };
        int[] cards = new int[cardString.Length];

        // Parse Cards
        for (int i = 0; i < cardString.Length; i++)
            cards[i] = Hand.ParseCard(cardString[i]);

        // Try all possible hold masks
        for (uint holdmask = 0; holdmask < 32; holdmask++)
        {
            double expectedValue = ExpectedValue(holdmask, ref cards, bet);
            if (expectedValue > bestev)
            {
                bestev = expectedValue;
                bestmask = holdmask;
            }
        }

        // Print Out Results
        Console.WriteLine("Best EV: {0:0.0###}", bestev);
        for (int i = 0; i < 5; i++)
        {
            if ((bestmask & (1UL << i)) != 0)
                Console.WriteLine("{0}\t Hold", cardString[i]);
            else
                Console.WriteLine("{0}", cardString[i]);
        }
    }
}

Vector Card Images

Card Vector

All of the card image code and controls that I've run across use bitmaps for card images. This has the advantage of being straightforward, but bitmap images don't scale well and have other issues.

A while back, I found David Bellot's SVG card website. He has a vector based card library that I was able to import into Adobe Illustrator. I have access to an Illustrator plug-in that emits C#/GDI+ code. I took David Bellot's cards and emitted them as C# code and wrapped that as a user control. This makes a very useful vector card control. The advantage of this control is that the cards look good regardless of their size. The disadvantage is that the control is large (about 7 Megs) and the source code is even larger (clocking in at a whopping 22.5 Megs). Even though the control is large, it renders reasonably quickly. However, loading and JITing can take a few seconds.

The usage is very straightforward. You load it as you would load any other control into the toolbox (right click on the Toolbox, select "Choose Items...", and then Browse for the "CardVectorImage.dll"). Once loaded, you can drag it on to a form. The property "Card" is an enumeration of the card faces and card backs that can be displayed. The values for the card faces correspond with the card values used by the Hand.Hands class. This simplifies the assignment of card values to the control.

If you visit David Bellot's website, you will notice that he has a newer (and nicer) version of his SVG cards. However, for some reason, Adobe Illustrator doesn't load the new cards correctly. I haven't found a workaround for that. Until I do, this older version of his card library will have to do.

Compatibility

All of the applications and libraries are written in C# and can be compiled in Visual Studio 2005 or Visual C# Express 2005 (which is free).

The file HandEvaluator.cs can be compiled in Visual Studio 2003 if the partial keyword is removed from the Hand class declaration. However, the HandIterator.cs file uses C# 2.0 features and will not work on previous versions of C#.

Acknowledgements

  • Poker-eval - a great C library for card evaluation that I used as a basis for my class library.
  • David Bellot's SVG Card Library - the source art work for the vector based card control.

I've been working on this code for quite a while (I was on sick leave for 5 months). I'm sure there are several websites that gave me ideas. These are just the ones that I can document as making it into this software.

Interesting Issues

I started this project because I was interested in doing some analysis of poker, and I wanted a real project to try out Visual Studio 2005 (it was beta at the time). During the process of trying to speed things up, I discovered several things that surprised me.

  1. The JITer doesn't inline anything for you - I found this surprising because of all of the promises from Microsoft that JITed C# code will be faster than native C++ code. I found myself missing the "inline" construct of C++. I've even been tempted to port the C# library into managed C++ just because I can still inline code there.
  2. It's faster to lookup a single bit left shift from a table than it is to do a left shift directly - This one left me scratching my head. This shouldn't be true, but try for yourself and you'll see that a lookup table is faster. Compare the operator (1UL << n) to the lookup table cardMasksTable[n] in the Hand class if you'd like to confirm this.
  3. It's amazing how much of a difference look up tables can make in speeding up code - It makes sense that the pre-calculated data will speed code up. But looking at poker.eval, it's impressive how many tables where used and how much faster it makes the evaluation code.
  4. The Visual Studio 2005 IDE is a bit flaky with large source files - I am sure that Microsoft doesn't consider 20+ Meg C# files to be a likely usage scenario, but when you have one, strange things seem to happen. I've had the IDE crash and then crash again when trying to send the error report to Microsoft because of a heap corruption. Intellisense occasionally goes a bit bonkers, and load time is very long on big files.
  5. Vector Cards don't run correctly on the 64 bit version of .NET 2.0 - I ran this library on a 64 bit processor with a 64-bit version of .NET 2.0. Most things worked as expected, but the vector card control is very slow. I suspect this is an issue with the 64-bit runtime and very large methods.

History

  • First version released - Dec 1st 2005.
  • Updated Dec 9th 2005 - Fixed a problem where the build failed for users of VS 2005 Team Editions.
  • Updated Feb 6th, 2006 - Fixed table used for two card hand odds. Added random hand iterator (for Monte Carlo analysis), included NUnit test, speeded up hand iterators by strongly typing the return value.
  • Updated April 18th 2006 - Fixed two reported bugs. One related to the generation of hand description strings (flushes and straight-flushes were labeled with the incorrect suit). Another issue was fixed related to stack overflow when the equal operator was used on a Hand instance.

License

The code that the hand evaluator is based on (poker-eval) is GPLed. The art used for the vector card images is from David Bellot's SVG playing cards. He has also LGPLed his images. That means the HandEvaluator assembly and the CardVectorImage control are both GPLed by other authors.

Since that covers most of the core pieces of the applications I've written, I also am GPLing my code. See each project for more information.

Conclusion

This article shows just a small amount of the code I wrote when I had nothing better to do than tinker. Hopefully, it's interesting and useful to those poker players (and bot writers) out there.

License

This article, along with any associated source code and files, is licensed under The GNU General Public License (GPLv3)

Share

About the Author

Keith Rule
Software Developer (Senior)
United States United States
I work at Tektronix in Beaverton OR. I've been programming for fun since 1975 (I started while in a Computer Explorer Scout group in Spokane WA). I've been programming in C since 1979 and I've been working professionally since 1983.

I really enjoy www.codeproject.com. It has saved me an incredible amount of time. I only hope my small contributions have given back some of what I've taken.

Comments and Discussions

 
GeneralRe: Modifying the outs function [modified] Pin
MogobuTheFool27-Jun-06 9:48
MemberMogobuTheFool27-Jun-06 9:48 
GeneralRe: Modifying the outs function Pin
Keith Rule27-Jun-06 18:29
professionalKeith Rule27-Jun-06 18:29 
GeneralThe explanation behind the code Pin
mjb24-Oct-06 8:56
Membermjb24-Oct-06 8:56 
GeneralThe modified code Pin
mjb24-Oct-06 9:00
Membermjb24-Oct-06 9:00 
GeneralTest Harness Pin
mjb24-Oct-06 9:02
Membermjb24-Oct-06 9:02 
QuestionHow to generate those bit tables? Pin
Kharlog-25-Apr-06 2:18
MemberKharlog-25-Apr-06 2:18 
AnswerRe: How to generate those bit tables? Pin
Keith Rule25-Apr-06 6:23
professionalKeith Rule25-Apr-06 6:23 
AnswerRe: How to generate those bit tables? Pin
MogobuTheFool28-Apr-06 9:56
MemberMogobuTheFool28-Apr-06 9:56 
Since Keith saved me the trouble of writing this in C#, I'll spend my time explaining it to you. (I've previously written a similar implementation in VB, also based on Poker-Eval, but was going to move it to C# and then start optimizing; Keith has done a great job here.)

Those lookup tables are generated with a separate program which goes through all the conventional logic necessary, and just outputs the table. The idea is to do all that logic once, and then then not have to do it again.

To understand the tables, you need to wrap your head around how this method approaches bit masks and thinks of them as packets of cards.

If you have a 16-bit number, the actual bits look like this:
0000000000000000 (that's a zero in binary, right?)
0000000000000010 (that's a two in binary.)

In the Poker-Eval approach, instead of thinking of the bits as binary representations of numbers, think of them as binary representations of cards. If a bit is on, you "have that card," and if it's off, you don't. So we can map the 13 cards to the first 13 bits like this:

XXXAKQJT98765432 (the x's are unused bits)
0001110011000000 (this represents a hand with an A,K,Q,9,8)

You can use a long integer (which fits up to 64 bits) to hold all the 52 cards of a regular deck, with 13 for each suit, and 12 unused bits. For my explanation here - and the lookup tables - we only need 13 bits, so we use a smaller integer.

Note that when reduce the actual hand holding of cards to a card bitmask like this, we lose information about multiple cards. If you hold two sevens, a nine, and a ten, the mask is:
xxxAKQJT98765432
0000000110100000

Notice all you know is that you "have seven(s)", but not how many. This means that this card bitmask is useful for stuff like "do I have a straight?" but not for "do I have a pair?"

We call this a card rank bitmask. Each bit represents one possible card rank; we're not interested in suits right now.

Now, if you just take hands and make the bitmask, you can do some logic to figure out if there is a straight. For example,

This has a straight:
XXXAKQJT98765432
0000000111110010

This does not:
XXXAKQJT98765432
0000010110010000

The logic is simple, right? Look for five sequential bits, and remember to count the 2-5 as a straight if you also have an A. But the logic takes time to run each time.

Here's the neat part: Notice that each possible card combination, as a bitmask, also represents an integer in binary. So each possible card combination has a corresponding NUMBER! And not only are they numbered, you don't even need to do a conversion to come up with the number; the card mask IS a number!

You can write a program to go through all the card combinations, check for a straight, and note which ones have straights. For example, a binary zero looks like this:
0000000000000000
Does that have a straight? No.

The number 31 looks like this in binary:
0000000000011111
Does that have a straight? Yes. It's the first number which does. That would be a six-high straight. (Remember, those last five bits are 65432; ace is high.)

If you look at the straights table, the entries in rows 0 to 30 all have a zero, meaning there's no straight. The entry at 31, however, is not a zero, because there IS a straight. What number is there? It's the number 4. That tells us that it's a six-high straight. How? The biggest bit in the straight is at position 4; there are bits at the positions 43210. So we have:


FEDCBA9876543210 < -- Bit Position, in Hex
XXXAKQJT98765432 < -- represented cards
0000000000011111 < -- Our six-high straight, in card mask
31 < -- Our six-high straight, as an integer

So again, in rows 0 to 30 of the straights table, the entries are all "zero" for "no straight." The next row, for integer number "31", has a 4, which means that Bit Position four is the highest bit in the straight.

Once you've built this list of numbers with simple programming logic, you save it as a lookup table. Because there are 13 possible cards, your table will be nearly 9,000 entries long. Long, but not impossibly long. The table will take some space in memory, sure, but looking up a number in a table is a very fast process, and machines today have lots of memory.

In the future, whenever you need to know if a particular hand has a straight, you just use the bit mask as an integer, look up that number in the table and you know instantly if there's a straight and, if so, what the high card is.

The Poker-Eval approach uses several lookup tables, each of which speeds a different step of the logic. I've explained the straightT table in detail above. There are also tables for:

nbitsT -- this takes a card mask and gives you the number of cards in it. If you feed it a 7-card hand and it tells you there are five cards, you know you have two duplicate cards; you have either two pair or trips, and a straight is possible. If you feed it 7 cards and it tells you there are only 4 unique cards, you can NOT have a straight, but you DO have three duplicate cards -- either three pair, a full house, or quads. Also, if you feed it all your cards in a particular suit and it says you have 5 or more, you know you have a flush!

Top Card -- feed this table a card rank mask, and it just responds with the highest ranking card in the set of cards. Again, a trivial process, but the lookup table method is still quicker than performing the logic of, "do we have an ace? No? How about a king? etc. . ."

Top Five -- feed this lookup table your card rank mask and it responds with a 5-card rank mask representing the best five cards. This is useful for comparing two "high card" hands at showdown; after running the two hands through to get these numbers, the bigger number wins. It's a trivial task, but it's done a bazillion times, and doing this lookup table is quicker than manually choosing the best five cards to compare two hands.

Well, I hope that explanation helps. If you understand the logic behind the tables, you can easily envision the code that was originally used to create the tables. Today, you don't need to make the tables yourself - you can just copy them from the original Poker-Eval project, or from implementations of it like Keith's.

Note that there MAY be the possibility to make the program even faster by doing some more lookup tables. The original designers were limited, in part, by the amount of memory available. Some other useful tables might be possible, if you don't care about sucking up more memory.

Some day, when there is copious memory available, it might even make sense to make a lookup table that handles all the 52-card combinations in one shot. Of course, that table would have 2^52 rows in it, or about 4,000 Terabytes, if my quickie math is correct. Right now, that lookup table wouldn't even fit on a SAN, much less my hard drive, so we've got a ways to go. . .

-- modified at 18:12 Saturday 29th April, 2006
GeneralRe: How to generate those bit tables? Pin
Keith Rule28-Apr-06 10:28
professionalKeith Rule28-Apr-06 10:28 
GeneralConverting handiterator.cs to VS2003 compatible code Pin
Kharlog-23-Apr-06 8:51
MemberKharlog-23-Apr-06 8:51 
GeneralRe: Converting handiterator.cs to VS2003 compatible code Pin
Keith Rule23-Apr-06 17:28
professionalKeith Rule23-Apr-06 17:28 
GeneralOdds seem to assume only one opponent Pin
gt4x20-Apr-06 16:06
Membergt4x20-Apr-06 16:06 
GeneralRe: Odds seem to assume only one opponent Pin
Keith Rule20-Apr-06 19:35
professionalKeith Rule20-Apr-06 19:35 
GeneralInlining Pin
mertner20-Apr-06 1:50
Membermertner20-Apr-06 1:50 
GeneralUpdate Info (April 18th, 2006) Pin
Keith Rule18-Apr-06 12:15
professionalKeith Rule18-Apr-06 12:15 
Generalstack overflow Pin
Sephirmus17-Apr-06 6:59
MemberSephirmus17-Apr-06 6:59 
GeneralRe: stack overflow Pin
Sephirmus17-Apr-06 7:14
MemberSephirmus17-Apr-06 7:14 
GeneralHandEvaluator.cs has a small problem Pin
Rob Simpson11-Apr-06 7:30
MemberRob Simpson11-Apr-06 7:30 
GeneralRe: HandEvaluator.cs has a small problem Pin
Keith Rule11-Apr-06 8:09
professionalKeith Rule11-Apr-06 8:09 
GeneralRe: HandEvaluator.cs has a small problem Pin
Keith Rule11-Apr-06 11:10
professionalKeith Rule11-Apr-06 11:10 
GeneralRe: HandEvaluator.cs has a small problem Pin
Keith Rule12-Apr-06 2:12
professionalKeith Rule12-Apr-06 2:12 
GeneralRe: HandEvaluator.cs has a small problem Pin
Kholopov Vassily16-Apr-06 22:24
MemberKholopov Vassily16-Apr-06 22:24 
GeneralNice Article Pin
Paul Conrad25-Feb-06 11:08
professionalPaul Conrad25-Feb-06 11:08 
QuestionInterfacing with online poker programs... Pin
Psytherium8-Feb-06 12:12
MemberPsytherium8-Feb-06 12:12 
AnswerRe: Interfacing with online poker programs... Pin
theDiver21-Feb-06 21:16
MembertheDiver21-Feb-06 21:16 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.