28 April 2010

A Texas Hold'em 7-card evaluator: Part I

(This post is a continued in Part II here.)

The idea for a new 7-card evaluator was inspired by Cactus Kev's blog, describing his 5-card evaluator. Setting flushes to one side for the time being, his idea is to assign thirteen pairwise distinct prime numbers as the face values of each card. He chooses the first thirteen prime numbers, from 2 to 41 inclusive. Every integer greater than or equal to 2 is uniquely expressed as a finite product of primes so all the information we need regarding the five-card hand modulo flushes can be recovered from the product of its face values, its "signature" or key. This neatly gets around having to worry about whether or how a hand should be presented in some standard form before carrying out a lot of computationally expensive sorting to achieve this. It's a smart thing to do.

On the other hand, we recognised that we really don't need anything like the full power of the fundamental theorem here. For instance we don't need to know that 43*47*53*59*61 is a unique factorisation, and more to the point we don't even need to know that 41*41*41*41*41 is also a unique factorisation because no legitimate poker hand ever contains five cards with the same face value. Pushing this scheme further a legitimate 7-card hand could find itself with the key 143,133,271,933 (~143 billion), equal to the product 41*41*41*41*37*37*37 and corresponding to a 7-card hand comprising all four aces and three of the four kings. An array of short-integers that size would be enormous, requiring almost 280Gb of contiguous memory virtually all of which would go unused. We can use a 5-card evaluator to evaluate 7-card hands but we will always be faced with the overhead of comparing the twenty-one possible 5-card hands from a hand of seven.

With these observations we've found a new key-scheme that gives us just enough uniqueness to correctly identify the integral rank of any 7-card hand, where the greater this rank is the better the hand we hold and two hands of the same rank always draw. We computed by brute force the first thirteen non-negative integers such that the sum of exactly seven with each taken at most four times is unique among all such sums, namely 0, 1, 5, 22, 98, 453, 2031, 8698, 22854, 83661, 262349, 636345 and 1479181. A valid sum might be 0+0+1+1+1+1+5 = 9 or 0+98+98+453+98+98+1 = 846, but invalid sum expressions include 0+262349+0+0+0+1 (too few summands), 1+1+5+22+98+453+2031+8698 (too many summands), 0+1+5+22+98+453+2031+8698 (again too many summands, although 1+5+22+98+453+2031+8698 is a legitimate expression) and 1+1+1+1+1+98+98 (too many 1's).

We assign these integers as the card face values and add these together to generate a key for any non-flush 7-card hand. The largest non-flush key we see is 7825759, corresponding to any of the four quad-of-aces-full-of-kings, and similarly the largest flush key we see is 7999, corresponding to any of the four 7-card straight flushes with ace high. These keys are all small enough to act as indices for all of the ranks stored in two arrays, one for the non-flushes and one for the flushes. The memory footprint can be reduced by mapping the array of 7-card ranks on to a circle of circumference 4565145, again computed by brute force; given the Birthday problem, it seems lucky that such a good circumference should even exist. This all comfortably runs on 32-bit systems.

We expect this schema can be applied in other similar contexts.

An early beta version of this work is now available publicly over on Google Projects under GNU General Public License (GPL). The accuracy of this work is in no way guaranteed by the author and, needless to say, it is to be used entirely at your own risk. We advise that you therefore carry out your own due diligence before making any use of this algorithm. That is, don't just take our word for it that we are correct.

Click SpecialKEvalBeta to begin downloading a .zip file containing the Objective-C, Java and C++ source code files. In doing so you are accepting all of the terms and conditions of the GNU General Public License v3 under which the work is distributed. Please also carefully report any bugs you encounter either by commenting on this article or by sending an e-mail to the address made available here.

The list of references here is not intended to be exhaustive or even representative of what is available online these days, it's just the result of sifting through the first twenty pages or so of a Google search. If there's a hand evaluator you would like to have linked here that is not already listed then by all means let us know and we'll be happy to oblige. If you decide to include my work and ideas in a GPL-project of your own I'd appreciate being openly acknowledged in your work and if you would like us to advertise your project here let us know and we will be happy to oblige.

A commercial-grade evolution of the beta evaluator has been released under a different license and in a different guise on the iTunes Store. It's called "Poker Ace".

46 comments:

  1. I like the idea, but I think I have found a bug in your implementation. I run the following two hands through SevenEval.java, and get the same rank when they should be different ranks:

    eval.getRankOf(1,2,3,4,5,14,15)
    7296

    eval.getRankOf(1,2,3,4,5,6,8)
    7296

    The second should have a higher rank because it is a higher straight flush. I'd like to use your engine to do some analysis, but I can't tell whether this problem is just with straight flushes or with hands in general. It seems to be a deeper problem in your codebase. Please let me know when it is fixed.

    ReplyDelete
    Replies
    1. Hello J2kun,

      Thanks for your post and for going through my code.

      This doesn't appear to be a bug, rather a misunderstanding of how I've encoded the deck of cards.

      The two hands you've described share the same best five card hand - namely, a full house (three aces, two kings). Remember, 0 to 3 inclusive are the aces (0 is the ace of spades, 1 the ace of hearts and so forth).

      The remaining two cards in either hand of seven are extraneous. Thus, the two hands are expected to have the same rank.

      You asked me to contact you to let you know (that there doesn't appear to be a problem). I clicked through your blog but I regret I couldn't find a contact address for you.

      SpecialK

      Delete
  2. I am just a little confused on how this works. Correct me if I am wrong, but by what you have recently posted, the numbers entered in "getRankOf" correspond to cards in the deck as follows:

    0 1 2 3 = A spades, A hearts, A clubs, A diamonds
    4 5 6 7 = K spades, K hearts, K clubs, K diamonds

    Is this correct?

    ReplyDelete
    Replies
    1. Hello Taskforce141,

      That's essentially correct - just switch clubs and diamonds to use my scheme.

      i.e.

      0 = Ace of Spades
      1 = Ace of Hearts
      2 = Ace of Diamonds
      3 = Ace of Clubs

      4 = King of Spades
      5 = King of Hearts
      6 = King of Diamonds
      7 = King of Clubs

      and so forth.

      There's nothing stopping you reworking this to suit your preferred index, this is just how I chose to set it up.

      Delete
  3. Thanks a bunch. I also am trying to create a poker calculator online application like what you have done in "poker ace." My user interface is all done, but I am really struggling with coding the math portion of it. I understand the math portion of it, but coding it is too advanced for me. Do you have any tips or advice, or other downloadable code I can use to finish this project? It would be much appreciated. Thanks.

    ReplyDelete
    Replies
    1. Hello taskforce141,

      You're very welcome.

      As for advice - it really depends on exactly what you want to do. Are you wanting to calculate equity, and if so in which language? For performance reasons I'd recommend doing this in C or C++. If there's any demand I can add equity calculating methods to the code I made public in due course. You're welcome to write to me further at codingfeedback@gmail.com.

      That said, I'll add that I started out on this project to learn how to code - I really didn't know a thing back then and it embarrassed me a lot. But I was interested enough in this area to use it to cut my teeth, and while I'm happy to help you out I really recommend you take this as an opportunity.

      SpecialK

      Delete
  4. I sent an e-mail to the given address under b.bilfred@gmail.com. Thanks for the help again.

    ReplyDelete
  5. Hey man, was just wondering if a java version will be available soon. It would help a lot. Thanks

    ReplyDelete
    Replies
    1. The Java version now has at least one equity method. More to follow in time. See the latest version on Google projects or over on github. Links at the bottom of the right hand panel on this page.

      Delete
  6. Great work. One question

    'The memory footprint can be reduced by mapping the array of 7-card ranks on to a circle of circumference 4565145, again computed by brute force'

    Can you explain further how this was done?

    Thanks,

    ReplyDelete
    Replies
    1. Brute force: Starting with a circumference of 1, I checked every pair of hands for a collision. That is, if two distinct valid sums of seven were equal modulo a candidate circumference I rejected this circumference, incremented the circumference by 1, and tried again. Only when there were no collisions did I then accept a circumference. The circumference I arrived at is minimal.

      Delete
  7. I can't seem to understand bits of your code - I'm using Xcode 4.2, so a lot of the releasing doesn't agree with ARC. But was confused by:

    deckcardsKey[4*n] = (face[n] << NON_FLUSH_BIT_SHIFT) + SPADE;
    deckcardsKey[4*n + 1] = (face[n] << NON_FLUSH_BIT_SHIFT) + HEART;
    deckcardsKey[4*n + 2] = (face[n] << NON_FLUSH_BIT_SHIFT) + DIAMOND;
    deckcardsKey[4*n + 3] = (face[n] << NON_FLUSH_BIT_SHIFT) + CLUB;

    Since NON_FLUSH_BIT_SHIFT appears to be undefined... So my code won't compile.

    ReplyDelete
  8. So I had a hunt through the code for the other versions and realised that these two lines were missing from your prefix file:

    //Bit masks
    #define SUIT_BIT_MASK 511
    #define NON_FLUSH_BIT_SHIFT 9
    /////////

    The code is now working wonderfully! Thank you so much!

    ReplyDelete
  9. Great job on this evaluator and thanks for making it GPL.

    I was wondering if there was a way to get the hand category (i.e. Flush, 2-pair, Full House, etc) from the rank of a 7-card hand or if there was some advice you could give me on how to program a way to get the hand category so that it works with your code.

    ReplyDelete
    Replies
    1. After finding the rank for the 7-card hand, check if it lies in a certain range. For example, if it has rank at least 5854 and at most 5863 then it must be a non-flush straight.

      Delete
    2. How do I determine what the ranges are? What is the range for a pair? what is the range for three of a kind, etc?

      Delete
    3. Decide what the best pair would be for a seven card hand (two aces, king, queen, jack, nine, eight no flush), and likewise decide the worst pair (two twos, three, four, five, seven, eight no flush). Ask SevenEval for the rank of both. Any seven card hand with a rank at least the latter but at most the former is a seven card hand offering only a pair.

      Delete
    4. I've ran a test and came up with this:

      if (rank < 1278) // high card 1277 - 49
      return @"High Card";

      if (rank < 4138) // pair 4137 - 1296
      return @"Pair";

      if (rank < 5854) // set 5853 - 5004
      return @"3 of a Kind";

      if (rank < 5864) // straight 5863 - 5857
      return @"Straight";

      if (rank < 7141) // flush 7140 - 5865
      return @"Flush";

      if (rank < 7297) // full 7296 - 7141
      return @"Full House";

      if (rank < 7453) // quad 7452 - 7299
      return @"4 of a Kind";

      if (rank == 7462) // royal 7462
      return @"Royal Flush";

      Problem is that I don't understand where you say in your above article that 7999 is the highest number where I have 7462 as the highest number. ???

      Delete
    5. I say that 7999 is the highest flush key, but I make no mention of it being the highest rank (as you seem to be suggesting).

      Delete
    6. Forgot to add two pair:

      if (rank < 4996) // two pair 4995 - 4141
      return @"Two Pair";

      Delete
    7. Nice. Aren't you also missing straight flushes besides the Royal Flush?

      Delete
    8. By no means exhaustive, but there is a list of constants like `RANK_OF_BEST_FLUSH` in the .pch file of the Objective C project. This one seems to agree with yours, but our worst straight ranks seem to differ. Please check yours, as I reckon there are ten non-flush straights up to equivalence.

      Delete
    9. In case anyone else is wondering, here is the code (Objective-C) I used to get the range values for the ranks:

      - (void)testRanks {
      int pRank = [fiveCardEvaluator rankOfSeven:0 :4 :8 :12 :16 :20 :24]; //AKQJ1098 royal flush

      pRank = [fiveCardEvaluator rankOfSeven:0 :1 :6 :11 :12 :21 :26]; //AAKQJ98 high pair
      pRank = [fiveCardEvaluator rankOfSeven:48 :49 :46 :43 :38 :29 :24]; //2234578 low pair

      pRank = [fiveCardEvaluator rankOfSeven:0 :1 :6 :7 :8 :13 :23]; //AAKKQJ9 high two pair
      pRank = [fiveCardEvaluator rankOfSeven:48 :49 :46 :47 :40 :37 :31]; //2233457 low two pair

      pRank = [fiveCardEvaluator rankOfSeven:0 :1 :2 :7 :10 :13 :20]; //AAAKQJ9 high set
      pRank = [fiveCardEvaluator rankOfSeven:48 :49 :50 :47 :42 :37 :28]; //2223457 low set

      pRank = [fiveCardEvaluator rankOfSeven:0 :1 :2 :3 :4 :9 :14]; //AAAAKQJ high quad
      pRank = [fiveCardEvaluator rankOfSeven:48 :49 :50 :51 :44 :41 :38]; //2222345 low quad

      pRank = [fiveCardEvaluator rankOfSeven:0 :1 :2 :7 :10 :13 :6]; //AAAKQJK high full
      pRank = [fiveCardEvaluator rankOfSeven:48 :49 :50 :47 :42 :37 :46]; //2223453 low full

      pRank = [fiveCardEvaluator rankOfSeven:0 :4 :8 :12 :20 :25 :30]; //AKQJ987 high flush
      pRank = [fiveCardEvaluator rankOfSeven:48 :44 :40 :32 :28 :25 :21]; //2345789 low flush

      pRank = [fiveCardEvaluator rankOfSeven:0 :4 :8 :12 :17 :21 :25]; //AKQJ1098 high straight
      pRank = [fiveCardEvaluator rankOfSeven:48 :44 :40 :36 :33 :29 :25]; //2345678 low straight

      pRank = [fiveCardEvaluator rankOfSeven:0 :4 :8 :12 :21 :25 :30]; //AKQJ987 high card
      pRank = [fiveCardEvaluator rankOfSeven:48 :44 :40 :36 :29 :25 :21]; //2345789 low card
      }

      Delete
    10. forgot the straight flush:


      pRank = [fiveCardEvaluator rankOfSeven:4 :8 :12 :16 :20 :25 :1]; //KQJ1098A high straight flush
      pRank = [fiveCardEvaluator rankOfSeven:48 :44 :40 :36 :32 :29 :25]; //2345678 low straight flush
      and in the code above posted add this if statement:

      else if (rank < 7462) // straight flush 7461 - 7454
      tempStr = @"Straight Flush";

      anyway, I hope that I'm done with this. thanks to SpecialK for his code!!!

      Delete
    11. Lets see, not quite... 1. You mean 23456-89, but really 2. Don't forgot the straight with Ace low :), i.e. A234578 non-flush (which I think can be :0 :51 :47 :43 :39 :30 :26).

      Delete
  10. I am noob to poker. I am trying to find out something similar to : http://gna.org/projects/pokersource/

    Is specialk same as above link ? Can i get the solutions as above link does

    Thanks
    Vishwas

    ReplyDelete
  11. on MAC i am getting :
    GDB: Program received signal: "SIGABRT"

    when i press continue execution, the application crashes. :(

    ReplyDelete
    Replies
    1. Hmm. I just downloaded the project from Google Projects and from Github, hit Command-R as is, and they both build and run fine for me.

      Delete
    2. In the article I do say "Please also carefully report any bugs you encounter either by commenting on this article or by sending an e-mail to the address made available here".

      Out of interest, are you using ARC?

      Delete
  12. i have a new type of hand evaluator. it it seems to be almost twice as fast as XPokerEval.CactusKev.Test.

    do you think this would be of any interest to people?

    thanks

    ReplyDelete
    Replies
    1. Many thanks for your query. New ways of doing things or improvements to existing ways are always interesting in of themselves, so do publish.

      As I recall, CactusKev is a fast 5-card evaluator. Every 5-card evaluator has some serious overhead if you wish to use it for evaluating 7-card hands though. Even a 5-card evaluator twice as fast as CactusKev's can't match a 7-card evaluator here.

      Delete
    2. yes. mine would take 21 times a long as my 5 card version

      Delete
  13. Pick 7 cards from a deck of 52 cards, regardless of the suit, and regardless of the order, how many combinations?
    I write a program to calculate this value, and get a surprisingly small result: 49205. I will check my program again to make sure this number is correct. If it's true, does it mean there may be a better encoding method?

    ReplyDelete
    Replies
    1. Many thanks for your comment. 49205 sounds about right, off memory. Unfortunately it doesn't immediately imply that there should a more effective way to choose the keys and in a smaller space, although there may be one. Even in a large space, an array with millions of entries, there is still a high expectation of collision. The only way to know if one exists.... Is to try.

      Delete
  14. Is there any possibility to set an undetermined value for a card?

    Thanks

    ReplyDelete
    Replies
    1. Many thanks for your question, J.S.A. Yes it is - take the average over the space of all combinations. For example, in heads up, give your opponent all pairs of cards you don't have, add each equity up and divide by the number of such pairs. If you hold a pair of aces, you have around 80% equity.

      Delete
    2. And for 3 or more players? Let's say about 3 players, with the cards of player 1 set and the cards for players 2 and 3 undetermined. Would you fix a pair of cards for player 2 and then iterate the remaining cards for player 3? How would be the math then? Is there any better procedure to do it?

      Delete
  15. Is there a way to do this for any number of cards in a player's hand. For example if a player has 9 card hand, what are the 5 best poker hands.

    ReplyDelete
  16. Good job for the evaluation!
    After getting the hand interval, is it possible to actually deduce more information, eg the leading card in the "high card" hand type? or the highest card in the straight?
    Thanks!

    ReplyDelete
    Replies
    1. The higher the rank the straight has, the higher the leading card. Take a look at the SpecialKEval-Prefix.pch file, the lines `#define RANK_OF_WORST_STRAIGHT 5854` etc. will help you.

      Delete
  17. This comment has been removed by the author.

    ReplyDelete
  18. Hi I was wondering if there was a README file or description for what number correspond to what cards and what the score evaluations mean? Thanks!

    ReplyDelete
    Replies
    1. Hello Leon,

      Many thanks for your comment and my apologies for the lateness of this reply. Currently there is no readme file which tells you the hand for a given number. It isn't quick to decide what a hand may have been given its rank. However, there are ranges buried in the Objective-C .pch file as I recall which you can use.

      The score evaluation is just some rank, the higher this number the stronger the hand. The ranks don't make up an interval, between two ranks there can be a number for which no hand has that as a rank.

      Delete
  19. Texas Holdem Poker Hack [Free Download] For More Info & Download, Go To - bit.ly/11tgWUn

    ReplyDelete