Actually, I wrote some C++ code to do exactly this - I actually worked out a
minimal perfect hash for the representations. Basically, an evaluation is a
sort of the 5 cards (which is usually not necessary since I generate cards
in sorted order already in my source code) followed by the calculation of
the hash followed by a single lookup. Calculating the hash is pretty quick -
it's all integer math with data in registers already. The only hard part is
the sorting - I use sorting networks to make this as quick as possible. I'm
trying to figure out how to build a version of the sorting networks (a topic
I love!) that doesn't involve any JMPs - there's a discussion of that in:

http://www.iguanarama.com/programming/

I'm still buggering around with it. It's pretty quick - I use it in my home
rolled pokerbot. I can do exhaustive searches of the post-flop possibilities
in a fraction of a second on my Pentium IV.

I stuck the classes (card & phand) with a brief description of what I did on
my website:

http://www.iguanarama.com/programming/poker_bot.html

Enjoy, Sn0rt.

-----Original Message-----
From: pokersource@yahoogroups.com [mailto:pokersource@yahoogroups.com] On
Behalf Of Darse Billings
Sent: Thursday, January 04, 2007 3:07 PM
To: pokersource@yahoogroups.com
Subject: Re: [pokersource] 2+2 thread on super fast evaluators


Having suggested the bit-friendly representation, I'm now working on making
it obsolete. :) If we roll-up the cards
6 bits at a time and compose a 4-card 24-bit index look-up with 3-card
18-bit look-ups, then the card representation doesn't matter. Any amount of
computation can be encoded in the magic table values, with sufficient head
scratching.

I don't know much about the relative speeds of operations on modern
architectures. Maybe Google knows. (I suspect that cache coherence is at
least as important though).

You're right about testing -- it's hard to know all of the clever short-cuts
today's optimizing compliers can come up with. If we take the test set from
a file, then a comparison version doing no-ops might be used to estimate the
overhead.
One advantage of this scheme is that the cards in the file can be from a
truly random source, such as random.org.

- Darse.


On 4-Jan-07, at 12:19 PM, Jeffrey Siegal wrote:
>> On 4-Jan-07, at 9:23 AM, Darse Billings wrote:
>>>
>>> I'm thinking it might be advantageous to represent cards keeping the
>>> rank and suit separated (4+2 bits), rather than having to unravel
>> the
>>> 6-bit representation for integers 0-51. Now the unordered rank
>> pattern
>>> can be determined quickly with bit operations, (28 bits = 268
>> million
>>> table entries), and the suit pattern determines the flush
>> exceptions.
>>>
>>
>> Specifically:
>>
>> 2c 001000 2d 001001 2h 001010 2s 001011 3c 001100 3d 001101 3h 001110
>> 3s 001111 4c 010000 4d 010001 4h 010010 4s 010011 5c 010100 5d 010101
>> 5h 010110 5s 010111 6c 011000 6d 011001 6h 011010 6s 011011 7c 011100
>> 7d 011101 7h 011110 7s 011111 8c 100000 8d 100001 8h 100010 8s 100011
>> 9c 100100 9d 100101 9h 100110 9s 100111 Tc 101000 Td 101001 Th 101010
>> Ts 101011 Jc 101100 Jd 101101 Jh 101110 Js 101111 Qc 110000 Qd 110001
>> Qh 110010 Qs 110011 Kc 110100 Kd 110101 Kh 110110 Ks 110111 Ac 111000
>> Ad 111001 Ah 111010 As 111011
>>
>> Note that an unordered set of 5 cards can be held in a single 32-bit
>> integer, which can then be converted to a hand value with a table
>> look-up, and to a (sorted) canonical representative with another
>> (small) table look-up...
> If you're going to do a table lookup, is there some significant
> advantage from the binary representation over, say,
>
> index = card0+52*(card1 + 52*(card2 ... ))
>
> which results in a smaller table (though not by enough to pack another
> card into 32 bits).
>
> Is the binary manipulation faster than multiply/add on current
> processors?
>
> Also (directed at everyone), in doing these tests, you should try some
> mode of usage other than sequentially iterating through hands, since
> that introduces a large degree of locality and may (depending on the
> algorithm) reduce the cost of table lookups and/or unpredictable
> branches. (This applies to the existing poker-eval code as well.) For
> example, a good test would be evaluating randomly generated hands
> against each other, with a control test to remove the cost of
> generating the hands.
>




Yahoo! Groups Links