4 ms·

Cool little trick, if you're strictly curious about knowing which hands rank where in relation to which other hands (say in an AI or whatever). While there are

Cool little trick, if you're strictly curious about knowing which hands rank where in relation to which other hands (say in an AI or whatever). While there are C(52, 5) different hands you can have, having 4 diamonds and a heart is the exact same thing as 3 clubs and 2 hearts, etc. so it collapses down to ~2.5k hands. Now the next observation we make is that for most hands, suit doesn't matter, but if it does we still need a way to distinguish it, but again, a flush in hearts is the same as a flush in spades in terms of card ranking. The trick we now pull out is the Fundamental Theorem of Arithmetic, which says that for some natural number N, N can be factored into primes in exactly one way, excluding permutations of the factors. We take advantage of this and assign each card a prime number. 2=2 3=3 4=5 ... A=41 Now, by multiplying the prime numbers together, we get things like a 2 3 A K Q hand is 2 * 3 * 41 * 39 * 37, and if they are all the same suit, you multiply by 43. You can then take these 2.5k hashes, rank them against each other in a lookup table, and know in constant time for the number of hands how hands rank against each other by just multiplying their card's values together with either 1 or 43 if same suit and seeing where it falls in the list. I realize expected value is more widely used as the basis for these types of systems, but I always thought that was a fun trick.

hervature 9y ago
I think it should be noted here that this only ranks garbage hands and flushes. Quad 2's is certainly worth more than 3 Ace's yet 2^4 < 41^3. Edit: I missed >>> rank them against each other in a lookup table I'm just confused about the prime factors thing now. Why not just hash the hand itself? "3459To" where o stands for off suit?
- gopalv 9y ago
  > Why not just hash the hand itself? "3459To" where o stands for off suit? Permutable hashes - you could just sort them and hash again, but the prime multiply hashing is pretty neat way of mapping all items in any order to the same hash code.
  - _asummers 9y ago
    Exactly. Leverages the fundamental theorem of arithmetic, that the product of primes is unique modulo permutations.
- T-hawk 9y ago
  Because 3459T is equivalent to 345T9 and 34T59 and all the other permutations. You need to either hash all the permutations (making your lookup table 5! times bigger) or sort the hand by card value. It is faster to multiply the 5 prime factors in linear time rather than the N log N of sorting.
  - deleted 9y ago
    [deleted]
  - hervature 9y ago
    That makes sense. I was making the assumption that hands are given in order. For example, when generating all hands, your inner loops only start at the current index of the parent loop.
    - T-hawk 9y ago
      The purpose isn't to generate the ranking list. The purpose is to evaluate hands. The list is a one-time cost however you make it, but evaluating the randomly dealt cards would have the ongoing cost of sorting every time if not for the prime-factors trick.
      - hervature 9y ago
        Yea, I guess I'm not convinced that the prime-factors is faster than sorting. Sure, linear time for prime multiplication, but you still have to look up the prime number in a lookup. The question comes down to what the coefficient is in front of N for prime factor method and in front of N log N for sorting. As N=5, the coefficient ratio is pretty small to still warrant using sorting. Also, using Radix sorting makes things even more fuzzy.
splonk 9y ago
In practice, I believe most fast hand value evaluators just use a lookup table, treating each hand as a 52 bit (or 64 with 12 wasted bits, most likely) bitset with 5 bits set to 1 to indicate the cards.
mateo411 9y ago
This is very neat, but I don't think it works for straights. For example how do these two hands compare? A 2 3 4 5 2 3 4 5 6 Maybe there is a way we can extend this to work for straights.
- _asummers 9y ago
  You would have those rankings precomputed beforehand. So you'd know A 2 3 4 5 is one straight, but its computed hash would have a higher ranking than 2 3 4 5 6 in the lookup table. The A straight might go to 735 and the 2 3 4 5 might go to 785 or something There is work to do in the construction of the list, but that happens once, and likely gets loaded from disk after it's created out of band.

hervature 9y ago

I think it should be noted here that this only ranks garbage hands and flushes. Quad 2's is certainly worth more than 3 Ace's yet 2^4 < 41^3. Edit: I missed >>> rank them against each other in a lookup table I'm just confused about the prime factors thing now. Why not just hash the hand itself? "3459To" where o stands for off suit?

gopalv 9y ago
> Why not just hash the hand itself? "3459To" where o stands for off suit? Permutable hashes - you could just sort them and hash again, but the prime multiply hashing is pretty neat way of mapping all items in any order to the same hash code.
- _asummers 9y ago
  Exactly. Leverages the fundamental theorem of arithmetic, that the product of primes is unique modulo permutations.
T-hawk 9y ago
Because 3459T is equivalent to 345T9 and 34T59 and all the other permutations. You need to either hash all the permutations (making your lookup table 5! times bigger) or sort the hand by card value. It is faster to multiply the 5 prime factors in linear time rather than the N log N of sorting.
- deleted 9y ago
  [deleted]
- hervature 9y ago
  That makes sense. I was making the assumption that hands are given in order. For example, when generating all hands, your inner loops only start at the current index of the parent loop.
  - T-hawk 9y ago
    The purpose isn't to generate the ranking list. The purpose is to evaluate hands. The list is a one-time cost however you make it, but evaluating the randomly dealt cards would have the ongoing cost of sorting every time if not for the prime-factors trick.
    - hervature 9y ago
      Yea, I guess I'm not convinced that the prime-factors is faster than sorting. Sure, linear time for prime multiplication, but you still have to look up the prime number in a lookup. The question comes down to what the coefficient is in front of N for prime factor method and in front of N log N for sorting. As N=5, the coefficient ratio is pretty small to still warrant using sorting. Also, using Radix sorting makes things even more fuzzy.

splonk 9y ago

In practice, I believe most fast hand value evaluators just use a lookup table, treating each hand as a 52 bit (or 64 with 12 wasted bits, most likely) bitset with 5 bits set to 1 to indicate the cards.

mateo411 9y ago

This is very neat, but I don't think it works for straights. For example how do these two hands compare? A 2 3 4 5 2 3 4 5 6 Maybe there is a way we can extend this to work for straights.

_asummers 9y ago
You would have those rankings precomputed beforehand. So you'd know A 2 3 4 5 is one straight, but its computed hash would have a higher ranking than 2 3 4 5 6 in the lookup table. The A straight might go to 735 and the 2 3 4 5 might go to 785 or something There is work to do in the construction of the list, but that happens once, and likely gets loaded from disk after it's created out of band.