I was reading http://en.wikipedia.org/wiki/Poker_probability which has a
good description of how to count the frequency of different types of
poker hands using a mathematical approach. A sample Python program is
given in the discussion page for doing it that way. I wanted to take a
different approach and actually generate all the possible hands,
counting the number of each type.
It's quite do-able on today's hardware, with 5-card (2,598,960
combinations) taking only one second and 7-card (133,784,560
combinations) taking around 60 seconds with my program on my notebook.
Does anyone have any suggestions for ways to improve my program,
especially about how to make it run faster? I'd like to get it down to
10 seconds or 5 seconds rather than 60, if that's possible. Profiling
suggests the vast majority of the run time is spent in the 'classify'
function.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#define N 7
/* N is the number of cards to deal. The best five-card poker hand
will be selected out of the N cards. Set N to 5 to get the
frequencies for 5-card poker hands as follows:
Straight flush 40
Four of a kind 624
Full house 3,744
Flush 5,108
Straight 10,200
Three of a kind 54,912
Two pair 123,552
One pair 1,098,240
No pair 1,302,540
Total 2,598,960
Or set N to 7 to get the frequences for 7-card poker hands
(as in Texas Hold'em) as follows:
Straight flush 41,584
Four of a kind 224,848
Full house 3,473,184
Flush 4,047,644
Straight 6,180,020
Three of a kind 6,461,620
Two pair 31,433,400
One pair 58,627,800
No pair 23,294,460
Total 133,784,560
Or set N to any other positive number and you should get
appropriate results, given enough time and as long as no
overflow occurs.
*/
#define RANK(card) ((card) % 13)
#define SUIT(card) ((card) / 13)
char *ranks[] = {"A", "2", "3", "4", "5", "6", "7", "8", "9", "T", "J",
"Q", "K"};
char *suits[] = {"S", "H", "D", "C"};
/* inc function increments hand to the next combination
of N cards from 52. If already at the last combination,
returns 1 to indicate end, otherwise returns 0.
Algorithm from nextComb function in combEnum.c at
http://reptar.uta.edu/NOTES5314/combEnum.c
*/
int inc(int *hand)
{
int i;
for(i = 0; i < N; i++)
{
if(hand[i] != 52 - N + i) break;
}
if(i == N) return 1;
for(i = N - 1; hand[i] == 52 - N + i; i--);
hand[i]++;
for(i++; i < N; i++)
hand[i] = hand[i - 1] + 1;
return 0;
}
enum class {
STRAIGHT_FLUSH,
FOUR,
FULL_HOUSE,
FLUSH,
STRAIGHT,
THREE,
TWO_PAIR,
ONE_PAIR,
NO_PAIR,
NUM_CLASSES
};
char *class_names[] = {
"Straight flush: ",
"Four of a kind: ",
"Full house: ",
"Flush: ",
"Straight: ",
"Three of a kind: ",
"Two Pair: ",
"One Pair: ",
"No Pair: "
};
void print_hand(int *hand, enum class cl)
{
int i;
for(i = 0; i < N; i++)
{
if(hand[i] < 0 || hand[i] >= 52)
printf("%d ", hand[i]);
else
printf("%s%s ", ranks[RANK(hand[i])], suits[SUIT(hand[i])]);
}
printf(" %s\n", class_names[cl]);
}
int comp(const void *v1, const void *v2)
{
const int *a = v1, *b = v2;
return *a < *b ? -1 : *a *b;
}
/* Even when there is both a straight and a flush in the cards,
they may not be over the same 5-card hand. This function
is called only when there is both a straight and a flush in
the cards, which is fairly rarely, to confirm whether or not
it is actually a straight flush. It operates by sorting the
cards in numerical order (which is suit-major, ensuring that
same-suited cards are together), then checking for a run of
5 adjacent cards each one greater than the last.
The variable 'state' represents the number of adjacent
straight-flush cards seen so far in the current run. It is
incremented when the current card is one greater than the
previous card, and of the same suit.
The hand is considered to contain a straight flush when state
reaches 4, or when state reaches 3 on a king and there is
an ace of the current suit.
*/
int confirm_straigh t_flush(int *hand)
{
int i, state = 0, tmp[N], hasAce[4] = {0, 0, 0, 0};
for(i = 0; i < N; i++)
{
if(RANK(hand[i]) == 0) hasAce[SUIT(hand[i])] = 1;
}
memcpy(tmp, hand, sizeof tmp);
qsort(tmp, N, sizeof *tmp, comp);
for(i = 1; i < N; i++)
{
if(( tmp[i] == tmp[i - 1] + 1
) && SUIT(tmp[i]) == SUIT(tmp[i - 1]))
{
state++;
}
else
{
state = 0;
}
if(state == 4 || (RANK(tmp[i]) == 12 && state == 3 &&
hasAce[SUIT(tmp[i])])) return 1;
}
return 0;
}
enum class classify(int *hand)
{
int rank_counts[13] = {0};
int suit_counts[4] = {0};
int i, flush = 0, straight = 0, state = 0;
int max_rank_count = 0, sub_rank_count = 0;
for(i = 0; i < N; i++)
{
rank_counts[RANK(hand[i])]++;
suit_counts[SUIT(hand[i])]++;
}
for(i = 0; i < 4; i++)
{
if(suit_counts[i] >= 5) flush = 1;
}
for(i = 0; i < 13; i++)
{
if(rank_counts[i] >= max_rank_count)
{
sub_rank_count = max_rank_count;
max_rank_count = rank_counts[i];
}
else if(rank_counts[i] >= sub_rank_count)
{
sub_rank_count = rank_counts[i];
}
if(rank_counts[i] != 0)
{
state++;
}
else
{
state = 0;
}
if(state == 5) straight = 1;
}
if(state == 4 && rank_counts[0] != 0) straight = 1; /* ace-high */
if(flush && straight && confirm_straigh t_flush(hand)) return
STRAIGHT_FLUSH;
if(max_rank_cou nt >= 4) return FOUR;
if(max_rank_cou nt == 3 && sub_rank_count >= 2) return FULL_HOUSE;
if(flush) return FLUSH;
if(straight) return STRAIGHT;
if(max_rank_cou nt == 3) return THREE;
if(max_rank_cou nt == 2 && sub_rank_count == 2) return TWO_PAIR;
if(max_rank_cou nt == 2) return ONE_PAIR;
return NO_PAIR;
}
void print_counts(lo ng long *counts)
{
int i;
long long total = 0;
for(i = 0; i < NUM_CLASSES; i++)
{
printf("%s%12ll d\n", class_names[i], counts[i]);
total += counts[i];
}
printf("Total: %12lld\n", total);
}
int main(void)
{
int i;
long long counts[NUM_CLASSES] = {0};
int hand[N] = {0};
/* initialise hand to first combination */
for(i = 0; i < N; i++) hand[i] = i;
do
{
counts[classify(hand)]++;
} while(!inc(hand ));
print_counts(co unts);
return 0;
}
--
Simon.
