I know I'm kinda late to the party writing a hand evaluator in year 2016, but I actually didn't find that many good open source libraries for poker evaluation. There's SKPokerEval which is reasonably fast, and there's 2+2 evaluator, which is pretty much optimal at sequential evaluation but really sucks at Monte Carlo because of the 130MB lookup. There's also Pokerstove which I didn't try but the code looked slow.

Anyway I wrote my own C++ evaluator and equity calculator, and I felt like I managed to come up with some cool ideas so I thought I'd share the code. It's available at GitHub. The evaluator is based on the same type of lookup method as SKPokerEval, but I'm also using perfect hashing, faster flush check, and a 128-bit structure for storing partial hand data. I really wanted to get it down to 64 bits, but couldn't find a way to fit the flush data. And then I found out I can use a single SSE4 op to combine the structs which gives it a small speed boost so it's kinda okay using a 128-bit struct.

I'm currently getting 720M evals/s (with MSVC it's slower though) when enumerating, which is 3x faster than SKPE, and half the speed of 2+2 evaluator, but honestly it's getting to the point where it hardly matters anymore because for any practical purpose the overhead from the loop and processing the results is going to dominate. For example my equity calculator is only getting 75M showdowns/s for two players (so it's like 150M evals/s, i.e. evaluation is maybe 1/4 of the total cost).

In random evaluation I'm getting 235M/s so it beats both SKPE (146M/s) and 2+2 (19M/s). The biggest difference to 2+2 of course comes from caching. After perfect hashing my lookup is only 400kB. I could get it to 200kB if I dropped the support for evaluating fewer than 7 cards, but there was negligible performance difference.

For the equity calculator I created both Monte Carlo and enumeration algorithms, and both support multithreading. The Monte Carlo simulation is based on a random walk algorithm which changes only one of the hands on each iteration. It's much faster than a naive monte carlo and yet in practice it has the same variance. But the biggest benefit is that it avoids the problem of having to to do a full resample on holecard collisions. There are scenarios where the naive method fails 99.9% of the time and it slows down to 0.1M hands/s, but the worst case I've seen for the random walker is around 10M/s. With too many dead cards it gets worse but that's fixable. Overall it works amazingly well and beats Equilab to the ground! (Btw does anyone know if Power-Equilab is any better?)

The enumeration algo is maybe not as good but still much faster than Equilab. I use a lookup table for detecting preflop isomorphism, and it works really well as long as the lookup table doesn't get full. After that it kinda suffers. The lookup also cannot be used if the postflop is too fast to iterate (4+ fixed board cards) because of the overhead. In postflop my algorithm also merges the suits that cannot make a flush anymore which gives it a nice 3x speed boost.

I'd be happy to read any comments/suggestions and answer questions.

Muchas gracias, cool beans, I'll have a look.

I'm also coding an equity calculator! The main requirement is to estimate equities in full-ring games, so it should have fairly strong Monte Carlo capabilities.

(I don't think writing an evaluator & equity calculator in 2016 is out of order; I've looked extensively and my conclusion is that the open source supply of such tools is lacking.)

Note: all timings that follow refer to a single Xeon core @2.2GHz.

The first stage was to find a good PRNG. I tested a bunch, and the fastest was this PCG snippet:

It can run about 2 billion times each second, generating 32 random bits each time.

(Quick question. I've noticed you use XorShiftPlus and MT199937. Which do you use for what kind of stuff?)

I'm currently in the second stage, which (for me) is to find a decent evaluator. Since the idea is to get Monte Carlo equities, we need random evals, so any LUT that doesn't fit in L3 cache (say, around 30MB) is out of the question. (I'm ruling out 2+2 and RayW.)

The fastest such evaluator I've found so far is ACE_eval, which you can also get on Github. It has a few versions, but the fastest one (ace_eval_decompress.c) uses no LUTs at all. I can get about 90M evals per sec.

Each card is a 32-bit int. The 4 least-significant bits encode the suit, the next 2 bits are always zero, and the rest contain the rank. The whole deck looks as follows:

The cards, in human-readable form, can be recorvered from the following table:

So, for example, 2c is 0x41, 3c is 0x101, etc.

Each hand is then an array of five 32-bit ints, but it's built rather non-intuively, so I omit the construction.

The evaluation algorithm itself has a lot of branching, but I can't tell how much this affects performance. (Isn't a branch misprediction supposed to cost like 5ns or something? Just a bit over an L1 cache hit?)

At a high level, the branching structure of the algorithm looks at follows:

I've tried computing equities with Rayeval (Github here), based on RayW's legendary LUT, but I only get about 10M simulations per second.

Anyways, I can't tell you how glad I am to see that people are still interested in this topic, since I think it's not yet quite solved! My intuition is that, with current hardware and an algorithm with little/no branching and tiny LUTS (or none at all), it'd be possible to run a few billions of Monte Carlo simulations per second on massively parallel architectures. It may be wishful thinking, but hey...

Anyways, to cut this short, I'm gonna do a deep dive of your code, but it's already looking better than the best stuff I could find.

I was just always under the assumption that Mersenne Twister was one of the highest quality PRNGs, altough not the fastest. So my plan was to use XorShift128+ for performance critical stuff and MT199937 elsewhere. But apparently MT199937 actually fails more statistical tests, so it's probably never worth using it. And XorShift128+ is already good enough for anything poker related, especially if you only need something like 0.01% error margin in Monte Carlo.

There's actually an improved version of it, Xoroshiro128+, which seems strictly better, and I was about to switch to that. (Although it requires that compiler can optimize rotl to one instruction, otherwise there's no speed gain over XorShift128+).

I was looking at ACE when I started my project, but I just kinda ignored it, because the evaluation function seemed very long. But since it uses no lookups and the hand representation is pretty efficient it might still be competitive. I should benchmark it too.

BTW one thing worth considering about lookup tables is also how sparse they are. In my evaluator the original LUT had a total size of 36MB, but it only touched 1.7MB of cachelines and rest was empty. So even though the perfect hashing reduced it to 0.4MB it didn't have that much performance impact because the original already fit in L3 cache.

These things are a complete mystery to me too, I just make my decisions mostly based on benchmarks.

But I have noticed situations where branch prediction makes difference. I was experimenting with generating uniform random integers using rejection sampling. E.g. if you need a number from 0 to 6, you generate 3 random bits until it falls within the range. But what really kills it is branch misprediction (or I couldn't come up with another explanation). Theoretically if the rejection sampling has 20% failure rate it should be only 25% slower than without failures, but because of branch misprediction it ends up being almost twice as slow.

Probably not billions/s on CPU. But maybe there's a way of doing parallel simulation on GPU with shader programs.

On using parallel architectures, what functionality could run concurrently?

Well, generally, you're going to do N independent simulations. I suppose those could be done nearly entirely in parallel. My implementation used multiple machines via a RPC architecture.

I just finished a very demanding project for a client, and I've finally had the chance to take OMPEval for a spin.

TLDR prelimary tests: it's 2-10 times faster at (random) evaluations than the fastest one I had found so far (ACE).

---------------------
Evaluation tests (one thread of a Xeon Haswell @2.2GHz, g++ 6.1)

Test 1: SSE4 flag OFF; Default flags/code
Flags: -O3 -pthread -Wall
Timings (average over 300 runs)
Random order evaluation (card arrays):
500,000,000 evals 105 MH/s
Random order evaluation (precalculated Hand objects):
500,000,000 evals 305 MH/s

Test 2 SSE4 flag ON; Default flags/code
Flags: -O3 -pthread -Wall -msse4.2
Timings (average over 300 runs)
Random order evaluation (card arrays):
500,000,000 evals 112 MH/s
Random order evaluation (precalculated Hand objects):
500,000,000 evals 262 MH/s

Test 3: SSE4 flag OFF; changed sum += ... to sum = ..., ie. removed the running sum (why do you keep it anyway?); changed XoroShiro128Plus's seed to non-deterministic.
Flags: -Ofast -pthread -mfpmath=both -march=native
Timings (over 300 runs)
Random order evaluation (card arrays):
500,000,000 evals 108 MH/s
Random order evaluation (precalculated Hand objects):
500,000,000 evals 348 M/s

Test 4: SSE4 flag ON; rest same as test 3.
Flags: -Ofast -pthread -mfpmath=both -march=native -msse4.2
Timings (average over 300 runs)
Random order evaluation (card arrays):
500,000,000 evals 117 MH/s
Random order evaluation (precalculated Hand objects):
500,000,000 evals 301 MH/s

Test 5: AVX2 flag ON; rest same as test 3.
Flags: -pthread -Ofast -mfpmath=both -march=native -m64 -funroll-loops -mavx2
Timings (average over 300 runs)
Random order evaluation (card arrays):
500,000,000 evals 130 MH/s
Random order evaluation (precalculated Hand objects):
500,000,000 evals 545 MH/s


Notes:
I also tried g++ 4.8, and it was ~5% slower. I think. Benchmarking is hard.
Intel's guide on GCC performance flags

---------------------
Equity tests

14 physical cores, 28 logical

Using 1 thread I get average r.speed of 10
Using 14 threads I get average r.speed of 135
Using 26 threads I get average r.speed of 200

---------------------
Subsequents comments are coming, later this week.

Nice benchmarks. Are the tests 1-4 on 32bit? Didn't think it would even run with SSE without crashing, altough it should work now after some improvements I made (it's such a pain to get compilers to align __m128i correctly on x86).

That's one thing I've learned about benchmarking. If you simply discard the result of a calculation then compiler is allowed to optimize the entire code away. Another thing you can do is assign the result to volatile variable but that affects some optimizations.

No, they're on 64-bit

Ah, to avoid those pesky optimizations I use the volatile trick. I didn't know it had undesirable side effects. I'll keep that in mind. Thanks!

Looks nice! I didn't check in detail yet, what info do you pre-calculate in the hand objects to get that huge speed increase?

I posted a similar eval a while back with a 512kb lookup and using 64 bit ints to represent hand info. I'm getting around 150 MH/s for random evals in Java, that seems to be roughly in line with your card-array version.

Source can be found here:
http://www.holdemresources.net/misc/handeval/

The C version is just a very basic port from Java, but I didn't write C in 15 years - I'm sure you guys could improve that *lol*. Only requirement is the popcnt instruction (-mpopcnt i guess).

Oh hey plexiq, I did stumble upon your thread month ago. I probably spent an hour then trying to figure out your code and I still don't know where all those shifts and xors and reduce constants are coming from. It's magic. But I adapted your C code to my benchmarks and got 290M for sequential and 156M/232M for random. Significantly beating SKPokerEval.

They're 128-bit objects with the the following structure (and i can add them together with _mm_add_epi32):

// Bits 0-31: Key to non-flush lookup table (linear combination of the rank constants).
// Bits 32-35: Card counter.
// Bits 48-63: Suit counters.
// Bits 64-127: Bit mask for cards (suits are in 16-bit groups).

The card counter isn't even needed by the evaluator, but it's useful in the equity calculator. A bit faster than doing popcount on the mask. I guess the only real "innovation" here was the suit counters. I initialize them to 3 so that when there's five of same suit the 4th bit gets flipped, and I can test for any flush by masking with 0x8888.

The suit counter is indeed a great idea, thanks for sharing! I think that may actually work in my eval as well, I'll do some testing. I've tried working through your code a bit, but my C++ is awfully rusty.

(As for the cryptic reduce/flush constants, the "manual" part gets all non-quad hands to <=26bits and with a bit of manual tweaking that goes down to 24bit. These constants are then basically just brute forced to map down to 18bit without rank collisions. I'm sure there are more elegant ways to achieve that )

I linked this thread in the classic 7 card evaluator thread, seems appropriate

I played around with the suit counter a bit and get a speedup of 5-10% for my eval, it gets rid of the popcnt too. I'm still limited to a 64bit representation and can't "pre-process" the rank structure like you do, so the improvement isn't quite as drastic. (I only had 12bits spare and i couldn't use your 4th bit trick, i resolved that with a 4kb lookup though.)