In part 1 we talked about how you can attach a value to a poker hand in order to compare it versus other hands. While to code there runs quite fast 2.6 mill hands in 1200 ms, we can do better.
Imagine a bit that you are writing your own poker server, which needs to execute this calculation many times a day, or that you write a poker bot which not only needs to calculate the current hand strength, but also make predictions on how your hand evolves (usually after the strength, you calculate the percentage of the hands you win now, and you also do this calculation for each upcoming phase in order to see whether your hands has a high chance to improve or worsen).
Performance as a requirement is in trade-off with storage, usually when you want to increase performance you need to sacrifice storage, or if you want to reduce the used storage you probably end up doing more CPU work.
In our poker hand evaluator we can quickly notice that the value of the hands never change and since there are only 2.6 mill of them, it will be easy to move them to the memory. We need to find a way to assign a unique value for each hand to construct a lookup table. This is called hashing. I wrote the following class.
class CacheHandEvaluator
{
readonly Dictionary<long, int> _handValues;
static int[] primes = // the first 52 prime numbers
{
2, 3, 5, 7, 11, 13, 17, 19, 23, 29,
31, 37, 41, 43, 47, 53, 59, 61, 67,
71, 73, 79, 83, 89, 97, 101, 103, 107,
109, 113, 127, 131, 137, 139, 149, 151,
157, 163, 167, 173, 179, 181, 191, 193,
197, 199, 211, 223, 227, 229,233, 239
};
public CacheHandEvaluator()
{
_handValues = new Dictionary<long, int>();
var eval = new SimpleHandEvaluator();
for (int i1 = 0; i1 < 52; i1++)
{
for (int i2 = i1 + 1; i2 < 52; i2++)
{
for (int i3 = i2 + 1; i3 < 52; i3++)
{
for (int i4 = i3 + 1; i4 < 52; i4++)
{
for (int i5 = i4 + 1; i5 < 52; i5++)
{
var cards = new[] {i1,i2,i3,i4,i5};
var hash = GetHash(cards);
_handValues.Add(hash, eval.Eval(cards));
}
}
}
}
}
}
public int Eval(int[] cards)
{
return _handValues[GetHash(cards)];
}
private static long GetHash(int[] cards)
{
return (long)primes[cards[0]] *
primes[cards[1]] *
primes[cards[2]] *
primes[cards[3]] *
primes[cards[4]];
}
}
We harness our first evaluator for constructing our lookup table. Why primes you ask? To skip over sorting, we need a mechanism that will generate the same hash, regardless of the order in which the cards are sent. My initial instinct was to use bit masks. There are 52 cards in the deck, so a 52 bit value would suffice, turning on the bits for each card in the hand. When i tested this out the performance was slower compared to the prime solution. I i did some performance analysis, and the retrieval of the values from the look-up table was slower. My explanation is that trough prime multiplication you end up generating hash keys that are significantly different and the equality operator over the keys run faster.
So i ended up keeping the prime solution which runs the 2.6 mill different combinations in around 400 ms, being 3x faster then my initial solution.
Since nowadays applications generally have way more ram at their disposal as in the past, and even physical storage is performing fast then before this is a quite a neat little trick.
Generally speaking the longer your calculations take, the better is if you can precalculate them, or store the values after the first calculation. In the financial sector for example, once the month closes, you can generate the reports that usually people will need, or you can wait for the first request and store the outcome for later, would be a good idea.
I hope you enjoyed!