Optimized Hand Evaluator and Optimal Play Simulation

[BinaryMan]

I am currently writing a poker calculator. It has been a very fun and educational experience because many of the maths and methods used in poker (specifically, Texas Hold'em) are unique. I've been reading many articles, posts, and academic papers on the subject.

My goal right now is to achieve near-optimal play by simulating a 10-person table where agents evolve until they converge on an optimal strategy. Playing this approach, one makes minimal assumptions about what other player's behaviors mean; most of the decisions are math-based. I'd also like to measure the EV and distribution curve of odds for a particular hand (provides the chance that the next card will create a situation where I would fold, etc) using enumeration or monte-carlo simulation. A quick hand evaluation method is needed for this and other purposes.

Most people want to find maximal play, but in limit poker you can leverage time and probabilities to be profitable with lower risk and bankroll volatility. A major goal is to play such that other players cannot take advantage of you and you are (almost) mathematically guaranteed to break even or make money over time (especially at micro and low-limit tables). No-limit poker is different altogether as you have a risk of ruin at Sit-n-Go tables that can't be ignored, but that's a separate problem I might tackle later as I get more experience.

I have been trying to implement a fast hand evalutator in VB using some of the suggestions found on the forum, but I realized that I can never achieve high performance because of the way VB handles array accesses and other calculations (the SAFEARRAY type protects you, but it also slows the code a bit).

I've tried using large tables and hash arrays to hold all combinations of cards, but the memory overhead is ridiculous. Using VB classes isn't a solution either because of memory and process overhead (I kind of anticipated this, but tried anyway). While VB makes most of the speed-insensitive coding tasks easier, I'm turning to optimized assembly code to do the hand evaluations in an external library (sort of a compromise).

The way I'm doing it now seems relatively efficient and straightforward, though I'm sure there are more complicated (and faster) ways. Here is the outline for the process:

VB has preprocessed the cards into an array Card(1 to 7). VB passes a pointer to Card(1) to the external optimized library. Each card is represented by a 64-bit structure containing one 16-bit integer per suit as recommended by several people. Bits 0-12 are set for each suit to represent the card ranks contained in the hand. The library can easily address the card data using this format.

The evaluator first uses each 16-bit rank mask in an 8K lookup table to determine if a flush is present. It then combines all four rank masks using the OR operation. A different 8K table lookup determines if the hand is a straight or high card hand. The only hand types that remain undetected so far are rank-count-based (pair, 2 pair, trip, full house, quad).

This is where optimization is critical (at least in my case). I have seen methods of using boolean operations on the rank masks to figure out which ranks are paired, triped, etc. However, there is still additional processing to identify the true hand type and final hand rank. Rather than working with the rank masks in this way, I am trying to find assembly code methods that more directly lead to a lookup table access or hand rank value.

Idea: If assembly code can quickly sort the ranks from high-low or vice versa accross all four rank masks, then the table size for a 7-vector rank set lookup is reduced from 60M+ to around 50K. I am testing using the BSR (Bit Scan Reverse; finds the index of the high bit in a register) instruction followed by BTR (Bit Test with Reset) to quickly extract the sorted rank bits. The BSR/BTR instructions only take one cycle on modern processors, and so they seem relatively efficient for this purpose. There are two factors I see that may allow for optimization tricks: (1) Each rank mask contains at most 4 set bits (because a flush has been ruled out in an earlier test). (2) All rank masks together contain at most 6 set bits (because a high card hand was also ruled out).

Problem: The high bits may be in different rank masks and the bits are not implicitly ordered between the masks (only within each individual mask). I can extract all seven card ranks, but they would not always be in order.

Could someone with assembly knowledge tell me how they would solve this problem (or anyone who has an alternative)? It may require a specialized trick. I can get the population count of each rank mask using an 8K table lookup if it helps with the solution. Array memory lookups for Core 2 processors probably aren't too bad. The IMUL instruction if needed for other purposes takes about three cycles. The CMOV instruction takes about one cycle and might avoid some JMPs.

If seven bytes (the bit indexes) contained in registers can be sorted/swapped quickly, then it alleviates the problem quite a bit; the hand rank is simply the vector of the sorted bytes representing the card ranks (4 bits are needed per card index for the rank; all seven cards will fit in a 32-bit register). The problem might come with the fact that VB code could displace the data cache, so I will assume that the 8K tables will not be resident in the L1 cache, therefor I will not expect the near-maximum performance attained by some people. However, I think I can do much better than 100K comparisons per second in pure VB (should hit at least several million per second using optimized library code).

[lucky_mf]

All I can say is good luck man.

Lucky

[kmak]

tl;dr
All I can say is wow. If you are successful in your endeavors you will have invented a money machine.

[faststeady]

just dont play on FT with it [img]/images/graemlins/smile.gif[/img]

[BinaryMan]

Most of the online casinos have told me that poker calculators or other tools are OK as long as they aren't bots. I use my programs as additional information sources, but I personally make the call (or raise lol). I also play no-limit SNGs to practice other skills so I don't rely on the tools too much.

[uDevil]

You should probably ask in the Software Forum.

There are some resources for hand evaluators on the web that may be helpful, though I don't recall anything in VB.

There is a list here.