Algorithms - pokerhand evaluators, bit shifting and unique values...
Hi,
Oh, and I originally posted this in the programming section and was told to move it! So here it is again:
I have been experimenting with converting some code from c to java. I used cactus kevs card hand analyser (http://www.suffecool.net/poker/evaluator.html) as my base unit and having converted it, have been messing around with the algorithms for the fun of it!
I have one thing I can't quite work out though. This is the card value layout, he uses a 32 bit number like this:
+--+--+--+--+
xxxbbbbb | bbbbbbbb | cdhsrrrr | xxpppppp |
+--+--+--+--+
p = prime number of rank (deuce=2,trey=3,four=5,...,ace=41)
r = rank of card (deuce=0,trey=1,four=2,five=3,...,ace=12)
cdhs = suit of card (bit turned on based on suit of card)
b = bit turned on depending on rank of card
Using such a scheme, here are some bit pattern examples:
xxxAKQJT 98765432 CDHSrrrr xxPPPPPP
00001000 00000000 01001011 00100101 King of Diamonds
00000000 00001000 00010011 00000111 Five of Spades
00000010 00000000 10001001 00011101 Jack of Clubs
Now, he states that the 'distinct' value for all AKQJ9 Flushes is 323, likewise a 6-high straight flush should be 9. How is he generating those values? I have attempted but cant get anywhere near those values! Now, there are examples of everything else in the code, but all these values come pre computed in tables and I can't figure out how he is getting those values.
Many thanks, Ron
Message was edited by:
cake
[1740 byte] By [
cakea] at [2007-11-26 23:07:49]
# 1
You need to read his write up carefully
He had made the choice to map each 5 card hand into a single number, where the smaller the number the higher the value of the poker hand. He also decided to make the mapping compact (no gaps) with no justification for that choice. He also decided to start his count at 1.
Given those choices he made, a RoyalFlush, being the highest value hand, maps to a score of 1. As you move on down through the hands you find that a AKQJ9 Flush, which is the highest possible ranking Flush, will have a number 323.
What this means (because he is using a compact map) is that there are 322 different poker hands, various straight flushes and four of a kinds etc., that have a higher value than that particular flush.
That is all the number 323 means. He wrote down a list of poker hands and that particular flush was number 323 on that list. It came from his choice to encode hands in a compact manner.
Personally, I wouldn't waste my time with that evaluator. Is it fast? Probably. Is it as fast as possible, certainly not. Is it obscure and complicated, absolutely.
He lost me in his write up when he commented that by mapping the ranks into primes he could multiply the numbers together and save himself a sort, which would shave off "hundreds of miliseconds." A single hundred miliseconds is a tenth of a second. What is he running his algorithm on, an abacus? You can bubble sort a list of 5 elements in 15 compares. Yes that is more instructions than 5 multiplications, but tenths of seconds!!! Nonsense. He makes no comment about the time taken to look up prime numbers in a table. No comment about time taken to shift elements into and out of his packed format.
This is not sane code. It is some gnarly bit twitching hiding behind the excuse of speed. What I mean is this: Everyone knows that in the interests of speed you may need to sacrifice some code beauty. So if you want to write ugly code, you just claim that you did it for speed. This is not a carefully reasoned attempt for a speed record, it is just an ugly hack.
Of course, that is just my opinion.
# 2
He lost me in his write up when he commented that by mapping the
ranks into primes he could multiply the numbers together and save
himself a sort
He lost me at "Since multiplication is one of the fastest calculations a computer can make". Any micro-optimiser can tell you to favour addition over multiplication, and replacing his encoding with 00cdhs0a0k0q0j0t0908070605040302 should allow you to mask with 0x3fffff, add, and get a number which plays the same role as his product of primes. (Not to mention that his binary chop is almost certainly the real bottleneck).
He makes no comment about the time taken to look up prime
numbers in a table. No comment about time taken to shift
elements into and out of his packed format.
(Speaking for the way I'd implement his algorithm - I haven't seen his code). The former is a one-off cost involved in setting up a lookup table which maps the obvious suit*13+value to the encoded value.
Edit: bah. The addition is slightly flawed, and requires switching to longs and using 3 bits per rank. At this point I'd have to profile to know which is faster.
