Data structure for poker deck/hands

[pt]

I'm trying to figure out a fast, efficient way to represent a single,
52 card deck plus player & community card hands for a Texas holdem
poker simulation. I need to be able to detect hand classifications
(X-of-a-kind, flush, straight, etc) and winning hands. I was thinking
of using a string & RE. I was assuming (yea, I know...) that a "hand"
data structure based on hash or array would slow things down. Here's
my string-based hand idea:
Cards are represented by 2 chars: rank & suit. 2-9,T,J,Q,K,A and
DCHS. 5 of Diamonds would be "5D". Player's hand (as a string) would
be concatenated with community cards to form a searchable string :
"5DTH2C3S4H". Pair detection regex would be /(.)[DCHS].*\1/
This makes straight detection hard without sorting, and I'm trying to
make this fast.

Any suggestions would be appreciated. Thanks in advance.

 

[usenet]

I'm trying to figure out a fast, efficient way to represent a single,
52 card deck plus player & community card hands for a Texas holdem

Have you investigated prior art? Such as...

http://search.cpan.org/~simon/Games-Poker-TexasHold-em-1.4/em.pm
http://search.cpan.org/~pip/Games-Cards-Poker-1.2.565CHh5/Poker.pm
http://search.cpan.org/~akarger/Games-Cards-1.45/lib/Games/Cards.pm

Code reuse... it's a wonderful thing...

 

[xhoster]

I'm trying to figure out a fast, efficient way to represent a single,
52 card deck plus player & community card hands for a Texas holdem
poker simulation. I need to be able to detect hand classifications
(X-of-a-kind, flush, straight, etc) and winning hands. I was thinking
of using a string & RE. I was assuming (yea, I know...) that a "hand"
data structure based on hash or array would slow things down.

Complicated regexes can get pretty slow, too. Plus your probably going to
need to go into arrays or hashes for some things, anyway.

Here's
my string-based hand idea:
Cards are represented by 2 chars: rank & suit. 2-9,T,J,Q,K,A

That would need a custom sorting routine. I'd represent them by
some bytes already in value order (Can A be low in Texas Hold-em? That
would throw a spanner in the works)

and
DCHS. 5 of Diamonds would be "5D". Player's hand (as a string) would
be concatenated with community cards to form a searchable string :
"5DTH2C3S4H". Pair detection regex would be /(.)[DCHS].*\1/

How about a full house?

This makes straight detection hard without sorting, and I'm trying to
make this fast.

If speed is the overriding concern, I'd do it in C, not Perl. (or maybe C
and Perl).

Xho

 

[pt]

Complicated regexes can get pretty slow, too. Plus your probably going to
need to go into arrays or hashes for some things, anyway.

I was hoping a regex would be faster than hash/array lookups, but
that's just based on ignorance on my part.

That would need a custom sorting routine. I'd represent them by
some bytes already in value order (Can A be low in Texas Hold-em? That
would throw a spanner in the works)

Yep. Consider that spanner thrown.

and
DCHS. 5 of Diamonds would be "5D". Player's hand (as a string) would
be concatenated with community cards to form a searchable string :
"5DTH2C3S4H". Pair detection regex would be /(.)[DCHS].*\1/

How about a full house?

More interesting. The "3-of-a-kind" regex AND the "pair" regex, where
the "pair" rank isn't the same as the 3OAK rank:
return $Hand =~ /(.)[DCHS].*\1[DCHS].*\1[DCSC]/ &&
($Hand =~ /([^$1])[DCHS].*\1[DCHS]/) ;

If speed is the overriding concern, I'd do it in C, not Perl. (or maybe C
and Perl).

Ack! Haven't done C in a while.

Maybe a radix sort ..... hmmmm.

 

[Anno Siegel]

Complicated regexes can get pretty slow, too. Plus your probably going to
need to go into arrays or hashes for some things, anyway.

I was hoping a regex would be faster than hash/array lookups, but
that's just based on ignorance on my part.

That would need a custom sorting routine. I'd represent them by
some bytes already in value order (Can A be low in Texas Hold-em? That
would throw a spanner in the works)

Yep. Consider that spanner thrown.

and
DCHS. 5 of Diamonds would be "5D". Player's hand (as a string) would
be concatenated with community cards to form a searchable string :
"5DTH2C3S4H". Pair detection regex would be /(.)[DCHS].*\1/

How about a full house?

More interesting. The "3-of-a-kind" regex AND the "pair" regex, where
the "pair" rank isn't the same as the 3OAK rank:
return $Hand =~ /(.)[DCHS].*\1[DCHS].*\1[DCSC]/ &&
($Hand =~ /([^$1])[DCHS].*\1[DCHS]/) ;

If speed is the overriding concern, I'd do it in C, not Perl. (or maybe C
and Perl).

Ack! Haven't done C in a while.

Maybe a radix sort ..... hmmmm.

Instead of an explicit radix sort you could consider a bit table
representation of hands. Use (0 .. 51) to represent the individual
cards. For list @cards (a list of integers in that range) construct
a bit vector:

my $hand = "\0" x 7;
vec( $hand, $_, 1) = 1 for @cards;

That gives you a unique representation for each hand with no explicit
sorting (this is your radix sort). Further, you can prepare masks that
indicate all cards of one suit, or of one rank, or other combinations
that may be useful. Thus

my $kings = $hand & $suit_mask{ king};

would leave only the bits for kings that were set in the original
hand. A fast way of counting bits is documented in unpack:

my $n_of_kings = unpack '%32b', $kings;

would give you their number.

I don't know how this would work out in a full analysis of a poker hand.
Your mention of radix sort made me think of it. (Code untested)

Anno

 

[Anno Siegel]

Complicated regexes can get pretty slow, too. Plus your probably going to
need to go into arrays or hashes for some things, anyway.

I was hoping a regex would be faster than hash/array lookups, but
that's just based on ignorance on my part.

That would need a custom sorting routine. I'd represent them by
some bytes already in value order (Can A be low in Texas Hold-em? That
would throw a spanner in the works)

Yep. Consider that spanner thrown.

and
DCHS. 5 of Diamonds would be "5D". Player's hand (as a string) would
be concatenated with community cards to form a searchable string :
"5DTH2C3S4H". Pair detection regex would be /(.)[DCHS].*\1/

How about a full house?

More interesting. The "3-of-a-kind" regex AND the "pair" regex, where
the "pair" rank isn't the same as the 3OAK rank:
return $Hand =~ /(.)[DCHS].*\1[DCHS].*\1[DCSC]/ &&
($Hand =~ /([^$1])[DCHS].*\1[DCHS]/) ;

If speed is the overriding concern, I'd do it in C, not Perl. (or maybe C
and Perl).

Ack! Haven't done C in a while.

Maybe a radix sort ..... hmmmm.

Instead of an explicit radix sort you could consider a bit table
representation of hands. Use (0 .. 51) to represent the individual
cards. For list @cards (a list of integers in that range) construct
a bit vector:

my $hand = "\0" x 7;
vec( $hand, $_, 1) = 1 for @cards;

That gives you a unique representation for each hand with no explicit
sorting (this is your radix sort). Further, you can prepare masks that
indicate all cards of one suit, or of one rank, or other combinations
that may be useful. Thus

my $kings = $hand & $suit_mask{ king};

would leave only the bits for kings that were set in the original
hand. A fast way of counting bits is documented in unpack:

my $n_of_kings = unpack '%32b*', $kings;

would give you their number.

I don't know how this would work out in a full analysis of a poker hand.
Your mention of radix sort made me think of it. (Code untested)

Anno