Counting poker hands

[Simon Biber]

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_straight_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_straight_flush(hand)) return
STRAIGHT_FLUSH;
if(max_rank_count >= 4) return FOUR;
if(max_rank_count == 3 && sub_rank_count >= 2) return FULL_HOUSE;
if(flush) return FLUSH;
if(straight) return STRAIGHT;
if(max_rank_count == 3) return THREE;
if(max_rank_count == 2 && sub_rank_count == 2) return TWO_PAIR;
if(max_rank_count == 2) return ONE_PAIR;
return NO_PAIR;
}

void print_counts(long long *counts)
{
int i;
long long total = 0;
for(i = 0; i < NUM_CLASSES; i++)
{
printf("%s%12lld\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(counts);
return 0;
}

--
Simon.

[Keith Thompson]

Simon Biber <ne**@ralmin.ccwrites:

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.

[...]

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.

[...]

#define RANK(card) ((card) % 13)
#define SUIT(card) ((card) / 13)

[...]

I haven't looked at your code in any detail, but just off the top of
my head, you might get some performance improvement (on many
platforms) by dividing by 16 rather than 13, leaving three gaps in the
sequence for each suit. Or you can set up a 52-entry lookup table for
each.

(Certainly the C standard gives no hint that this will either help or
hurt.)

See if your profiler can be persuaded to give you per-line information
rather than per-function information.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <* <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

[Lane Straatman]

"Simon Biber" <ne**@ralmin.ccwrote in message
news:45**********@news.peopletelecom.com.au...

<snip>

void print_counts(long long *counts)
{
int i;
for(i = 0; i < N; i++) hand[i] = i;

do
{
counts[classify(hand)]++;
} while(!inc(hand));
print_counts(counts);
return 0;
}

Did this compile for you with a long long? My compiler doesn't like it.

I'm all about poker, so I love the post. LS

[Flash Gordon]

Keith Thompson wrote, On 17/01/07 00:46:

Simon Biber <ne**@ralmin.ccwrites:

>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.

[...]

>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.

[...]

>#define RANK(card) ((card) % 13)
#define SUIT(card) ((card) / 13)

[...]

I haven't looked at your code in any detail, but just off the top of
my head, you might get some performance improvement (on many
platforms) by dividing by 16 rather than 13, leaving three gaps in the
sequence for each suit.

On my notebook this only gave about a 1 second improvement, from 40s to
39s (gcc with -O2). Just goes to show that first impressions when it
comes to optimisation can be very misleading, as I know you already know.

BTW doing something about the division was my first thought ;-)

If the OP has not enabled the optimiser then doing so would be a far
better option than anything else.

Or you can set up a 52-entry lookup table for
each.

I did not try it but I don't think that would do much better.

(Certainly the C standard gives no hint that this will either help or
hurt.)

See if your profiler can be persuaded to give you per-line information
rather than per-function information.

That is also worth doing, although using the optimiser might mess up any
such statistics.
--
Flash Gordon

[Flash Gordon]

Lane Straatman wrote, On 17/01/07 00:52:

"Simon Biber" <ne**@ralmin.ccwrote in message
news:45**********@news.peopletelecom.com.au...

<snip>

>void print_counts(long long *counts)
{
int i;
for(i = 0; i < N; i++) hand[i] = i;

do
{
counts[classify(hand)]++;
} while(!inc(hand));
print_counts(counts);
return 0;
}

Did this compile for you with a long long? My compiler doesn't like it.

I'm all about poker, so I love the post. LS

long long was not in the C89 standard so it will produce a diagnostic
(error or warning) on any compiler in C89 conforming mode. It was,
however, a common extension and has been added to C99, so any C99
compiler (few and far between) and any compiler supporting it as an
extension will accept it when properly poked.
--
Flash Gordon

[Flash Gordon]

Flash Gordon wrote, On 17/01/07 01:20:

Keith Thompson wrote, On 17/01/07 00:46:

>Simon Biber <ne**@ralmin.ccwrites:

>>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.

[...]

>>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.

[...]

>>#define RANK(card) ((card) % 13)
#define SUIT(card) ((card) / 13)

[...]

I haven't looked at your code in any detail, but just off the top of
my head, you might get some performance improvement (on many
platforms) by dividing by 16 rather than 13, leaving three gaps in the
sequence for each suit.

On my notebook this only gave about a 1 second improvement, from 40s to
39s (gcc with -O2). Just goes to show that first impressions when it
comes to optimisation can be very misleading, as I know you already know.

<snip>

Increasing the optimisation from -O2 to -O3 knocked the original version
down to 29 seconds whilst leaving the version with %16 /16 at 38
seconds! So increasing the optimisation level beyond what I normally use
had a *far* greater effect!

For reference, without any optimisation it was about 75 seconds for the
original and 65 with the optimisation.

So the OP should definitely play with optimisation levels in the
compiler as a first step and will probably find it very difficult to
make code changes that increase the performance with the best compiler
optimisation available.

An interesting little exercise though for learning about optimisation.
--
Flash Gordon

[Keith Thompson]

Flash Gordon <sp**@flash-gordon.me.ukwrites:

Keith Thompson wrote, On 17/01/07 00:46:

>Simon Biber <ne**@ralmin.ccwrites:

[...]

>>#define RANK(card) ((card) % 13)
#define SUIT(card) ((card) / 13)

[...]
I haven't looked at your code in any detail, but just off the top of
my head, you might get some performance improvement (on many
platforms) by dividing by 16 rather than 13, leaving three gaps in the
sequence for each suit.

On my notebook this only gave about a 1 second improvement, from 40s
to 39s (gcc with -O2). Just goes to show that first impressions when
it comes to optimisation can be very misleading, as I know you already
know.

BTW doing something about the division was my first thought ;-)

[...]

Hypothesis: either your compiler knows a clever way to divide by 13,
or your hardware does division quickly.

(By "hypothesis", of course, I mean "wild guess unsupported by any
facts or research".)

(gcc, on one x86 platform, implements division by 13 without using a
division instruction; it involves multiplication by 1321528399, which
is close to 2**34/13, but I'm too lazy to analyze the code in any
depth.)

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <* <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

[Keith Thompson]

"Lane Straatman" <in*****@invalid.netwrites:

"Simon Biber" <ne**@ralmin.ccwrote in message
news:45**********@news.peopletelecom.com.au...

<snip>

>void print_counts(long long *counts)
{
int i;
for(i = 0; i < N; i++) hand[i] = i;

do
{
counts[classify(hand)]++;
} while(!inc(hand));
print_counts(counts);
return 0;
}

Did this compile for you with a long long? My compiler doesn't like it.

How exactly did your compiler make its displeasure known? Does it not
recognize the type "long long", or was there some other problem?

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <* <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

[websnarf]

Simon Biber wrote:

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.

Indeed. Please take a look at:

http://www.pobox.com/~qed/poker.zip

It does both 5 and 7 card stud calculations by monotonically mapping
each hand to a score metric. All exact ties are all calculated
correctly, for example. Also the two few bits of the metric correctly
classify the hand into the rough hand categorization (two of a kind,
flush, etc).

(I was also working on a full general heads-up situation evaluator, but
got side tracked. There are non-loop based methods for accelerating
that but it starts getting really really complicated. I would probably
require several days of working at it to get it.)

--
Paul Hsieh
http://www.pobox.com/~qed/
http://bstring.sf.net/

[Michael]

Simon Biber wrote:

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.

<snip>

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_straight_flush(hand)) return
STRAIGHT_FLUSH;
if(max_rank_count >= 4) return FOUR;
if(max_rank_count == 3 && sub_rank_count >= 2) return FULL_HOUSE;
if(flush) return FLUSH;
if(straight) return STRAIGHT;
if(max_rank_count == 3) return THREE;
if(max_rank_count == 2 && sub_rank_count == 2) return TWO_PAIR;
if(max_rank_count == 2) return ONE_PAIR;
return NO_PAIR;
}

1) How about combining inc and classify? Basically, when you increment
one of the cards, you'd adjust rank_counts and suit_counts - it looks
like you're recalculating N of those each time, even if you only change
1 card.

You could also calculate 'flush' at the same time (another loop
removed), and max_rank_count sometimes (i.e., if you increase a number
to more than max_rank count, but not if you decrement the number that
was previously max_rank_count, as there could be another equal one
somewhere).

2) If you re-order the ifs at the end in a way that is logically
consistent, but that minimizes the expected path through it, you'd be
executing less code on average. For example, right now if you have
NO_PAIR (which is very common), you have to do all the checks. If that
were first (with appropriate logic), your average number of ifs would
decrease.

You could do something like:
switch (max_rank_count) {
case 1:
logic for straight and straight flush
case 2:
logic for flush and pair and two pair
case 3:
logic for flush and full house and three
etc.
Note that straight implies max_rank_count = 1, so you should only
execute the loop to calculate 'state' and 'straight' in case 1.

This one is a little trickier, so you'll have to be careful not to mess
up the logic.

Good luck.

Michael

[Lane Straatman]

"Keith Thompson" <ks***@mib.orgwrote in message
news:ln************@nuthaus.mib.org...

"Lane Straatman" <in*****@invalid.netwrites:

>"Simon Biber" <ne**@ralmin.ccwrote in message

>>void print_counts(long long *counts)

Did this compile for you with a long long? My compiler doesn't like it.

How exactly did your compiler make its displeasure known? Does it not
recognize the type "long long", or was there some other problem?

It gives me a full-fledged error:
http://www.billfordx.net/screendumps/cstuff_2.htm

I think this is the end of the road for MS Visual Studio and me. The
convenience of the IDE is now compromised by the hassle of working around
the differences between C90 and what is currently standard.
--
LS
Never underestimate the staining power of jello.

[Barry]

<we******@gmail.comwrote in message
news:11**********************@s34g2000cwa.googlegr oups.com...

Simon Biber wrote:

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.

Indeed. Please take a look at:

http://www.pobox.com/~qed/poker.zip

It does both 5 and 7 card stud calculations by monotonically mapping
each hand to a score metric. All exact ties are all calculated
correctly, for example. Also the two few bits of the metric correctly
classify the hand into the rough hand categorization (two of a kind,
flush, etc).

(I was also working on a full general heads-up situation evaluator, but
got side tracked. There are non-loop based methods for accelerating
that but it starts getting really really complicated. I would probably
require several days of working at it to get it.)

Paul, I took the OPs program and linked it with pokeref.c and it cut
the execution time from about 190 secs. to 100 secs. on my old
laptop. That included the fact that I undid some of the work done
by masking the score of the hand back out so I could classify
it in the same manner the OP had originally and verify the results.

[Simon Biber]

Barry wrote:

<we******@gmail.comwrote in message
news:11**********************@s34g2000cwa.googlegr oups.com...

>Simon Biber wrote:

>>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.

Indeed. Please take a look at:

http://www.pobox.com/~qed/poker.zip

It does both 5 and 7 card stud calculations by monotonically mapping
each hand to a score metric. All exact ties are all calculated
correctly, for example. Also the two few bits of the metric correctly
classify the hand into the rough hand categorization (two of a kind,
flush, etc).

(I was also working on a full general heads-up situation evaluator, but
got side tracked. There are non-loop based methods for accelerating
that but it starts getting really really complicated. I would probably
require several days of working at it to get it.)

Paul, I took the OPs program and linked it with pokeref.c and it cut
the execution time from about 190 secs. to 100 secs. on my old
laptop. That included the fact that I undid some of the work done
by masking the score of the hand back out so I could classify
it in the same manner the OP had originally and verify the results.

I did something quite similar. My code can now use Paul's fast
bit-twiddling functions when N is 5 or 7, or revert to my slow function
when N is something else.
#define USE_FAST

#if defined(USE_FAST) && (N == 7 || N == 5)

int classify(int *hand)
{
int i;
unsigned char tmp[N];
unsigned long score;
for(i = 0; i < N; i++) tmp[i] = hand[i];
if(N == 7) score = SevenCardDrawScore(tmp);
else if(N == 5) score = FiveCardDrawScore(tmp);
else return 0;
if(score >= STRAIGHT_FLUSH_SCORE) return STRAIGHT_FLUSH;
if(score >= FOUR_KIND_SCORE) return FOUR;
if(score >= FULL_HOUSE_SCORE) return FULL_HOUSE;
if(score >= FLUSH_SCORE) return FLUSH;
if(score >= STRAIGHT_SCORE) return STRAIGHT;
if(score >= THREE_KIND_SCORE) return THREE;
if(score >= TWO_PAIR_SCORE) return TWO_PAIR;
if(score >= TWO_KIND_SCORE) return ONE_PAIR;
return NO_PAIR;
}

#else

.... old classify function ...

#endif

--
Simon.

[Simon Biber]

Lane Straatman wrote:

"Simon Biber" <ne**@ralmin.ccwrote in message
news:45**********@news.peopletelecom.com.au...

<snip>

>void print_counts(long long *counts)
{
int i;
for(i = 0; i < N; i++) hand[i] = i;

do
{
counts[classify(hand)]++;
} while(!inc(hand));
print_counts(counts);
return 0;
}

Did this compile for you with a long long? My compiler doesn't like it.

I'm all about poker, so I love the post. LS

Yes, it compiles with long long on both Cygwin/GCC (version 3.4.4) and
Microsoft Visual Studio 2003 (cl.exe version 13.10.1077).

There is no compiler error from MSVC, but the library is non-conforming.
It prints the wrong value at run time if the value of the long long is
1<<32 or larger. This can be solved using a non-standard formatting
flag, 'I64' instead of 'll'.

#ifdef _WIN32
# define FORMAT_LONG_LONG "I64"
#else
# define FORMAT_LONG_LONG "ll"
#endif

....
printf("%" FORMAT_LONG_LONG "d\n", value);
....

With N == 7 or less, there's no need for long long really, it should
work fine with just long. Just replace 'long long' with 'long' in main
and print_counts, and replace '%lld' with '%ld' in the printf statements
in the print_counts function.

--
Simon.

[Lane Straatman]

"Simon Biber" <ne**@ralmin.ccwrote in message
news:45**********@news.peopletelecom.com.au...

Lane Straatman wrote:

Yes, it compiles with long long on both Cygwin/GCC (version 3.4.4) and
Microsoft Visual Studio 2003 (cl.exe version 13.10.1077).

There is no compiler error from MSVC, but the library is non-conforming.
It prints the wrong value at run time if the value of the long long is
1<<32 or larger. This can be solved using a non-standard formatting flag,
'I64' instead of 'll'.

#ifdef _WIN32
# define FORMAT_LONG_LONG "I64"
#else
# define FORMAT_LONG_LONG "ll"
#endif

...
printf("%" FORMAT_LONG_LONG "d\n", value);
...

With N == 7 or less, there's no need for long long really, it should work
fine with just long. Just replace 'long long' with 'long' in main and
print_counts, and replace '%lld' with '%ld' in the printf statements in
the print_counts function.

#define N 41
#ifdef _WIN32
#define N 42
#define FORMAT_LONG_LONG "I64"
#endif
#include <stdio.h>

int main(void)
{
type? m;
m = 123451234512345;
printf("%" FORMAT_LONG_LONG "d\n", m);
printf("%i\n", N);
return 0;
}
I was ready to chuck my compiler last night, but if there's a type that
could make m work, then that would be groovy. I tried anything I could
think of that looked like int64. LS

[robertwessel2]

Lane Straatman wrote:

"Simon Biber" <ne**@ralmin.ccwrote in message
news:45**********@news.peopletelecom.com.au...

Lane Straatman wrote:

Yes, it compiles with long long on both Cygwin/GCC (version 3.4.4) and
Microsoft Visual Studio 2003 (cl.exe version 13.10.1077).

There is no compiler error from MSVC, but the library is non-conforming.
It prints the wrong value at run time if the value of the long long is
1<<32 or larger. This can be solved using a non-standard formatting flag,
'I64' instead of 'll'.

#ifdef _WIN32
# define FORMAT_LONG_LONG "I64"
#else
# define FORMAT_LONG_LONG "ll"
#endif

...
printf("%" FORMAT_LONG_LONG "d\n", value);
...

With N == 7 or less, there's no need for long long really, it should work
fine with just long. Just replace 'long long' with 'long' in main and
print_counts, and replace '%lld' with '%ld' in the printf statements in
the print_counts function.

#define N 41
#ifdef _WIN32
#define N 42
#define FORMAT_LONG_LONG "I64"
#endif
#include <stdio.h>

int main(void)
{
type? m;
m = 123451234512345;
printf("%" FORMAT_LONG_LONG "d\n", m);
printf("%i\n", N);
return 0;
}
I was ready to chuck my compiler last night, but if there's a type that
could make m work, then that would be groovy. I tried anything I could
think of that looked like int64. LS

While this is quite OT, the 64 bit integer type in MSVC is "__int64".
(Note two underscores.)

[Flash Gordon]

Keith Thompson wrote, On 17/01/07 02:50:

Flash Gordon <sp**@flash-gordon.me.ukwrites:

>Keith Thompson wrote, On 17/01/07 00:46:

>>Simon Biber <ne**@ralmin.ccwrites:

[...]

>>>#define RANK(card) ((card) % 13)
#define SUIT(card) ((card) / 13)
[...]
I haven't looked at your code in any detail, but just off the top of
my head, you might get some performance improvement (on many
platforms) by dividing by 16 rather than 13, leaving three gaps in the
sequence for each suit.

On my notebook this only gave about a 1 second improvement, from 40s
to 39s (gcc with -O2). Just goes to show that first impressions when
it comes to optimisation can be very misleading, as I know you already
know.

BTW doing something about the division was my first thought ;-)

[...]

Hypothesis: either your compiler knows a clever way to divide by 13,
or your hardware does division quickly.

(By "hypothesis", of course, I mean "wild guess unsupported by any
facts or research".)

(gcc, on one x86 platform, implements division by 13 without using a
division instruction; it involves multiplication by 1321528399, which
is close to 2**34/13, but I'm too lazy to analyze the code in any
depth.)

I did you gcc on an x86 so it probably is doing something like that,
yes. I've actually used that kind of optimisation myself when working in
assembler or with a compiler that I knew would not do it for me,
appropriately commented of course.

I could have tried it on other systems, but having hit a nice
counter-intuitive result on the first system I tried I did not bother. I
will probably be getting rid of one of my systems at some point so I
will have fewer slightly odd boxes to test things on when I want to find
a system where something fails :-(

I do recognise that you would not be doing this kind of optimisation on
real code without proper measurements and tests, my comments were more
aimed at the OP.
--
Flash Gordon

[Lane Straatman]

<ro***********@yahoo.comwrote:

While this is quite OT, the 64 bit integer type in MSVC is "__int64".
(Note two underscores.)

But if we don't dwell on it, we won't have to don asbestos suits.
http://www.billfordx.net/screendumps/cstuff_3.htm
--
LS

[Randy Howard]

On Wed, 17 Jan 2007 10:27:10 -0600, Simon Biber wrote
(in article <45**********@news.peopletelecom.com.au>):

#ifdef _WIN32
# define FORMAT_LONG_LONG "I64"
#else
# define FORMAT_LONG_LONG "ll"
#endif

...
printf("%" FORMAT_LONG_LONG "d\n", value);

If anyone ever needs a convincing argument for why not to use Microsoft
development tools, the above should suffice.
--
Randy Howard (2reply remove FOOBAR)
"The power of accurate observation is called cynicism by those
who have not got it." - George Bernard Shaw

[Lane Straatman]

"Randy Howard" wrote:

If anyone ever needs a convincing argument for why not to use Microsoft
development tools, the above should suffice.

What if one doesn't need convincing?
http://www.billfordx.net/screendumps/cstuff_4.htm
--
LS

[CBFalconer]

Randy Howard wrote:

On Wed, 17 Jan 2007 10:27:10 -0600, Simon Biber wrote

>#ifdef _WIN32
# define FORMAT_LONG_LONG "I64"
#else
# define FORMAT_LONG_LONG "ll"
#endif

...
printf("%" FORMAT_LONG_LONG "d\n", value);

If anyone ever needs a convincing argument for why not to use
Microsoft development tools, the above should suffice.

Or operating systems. See the URL in my sig. for horror story
about Vista.

--
"A man who is right every time is not likely to do very much."
-- Francis Crick, co-discover of DNA
"There is nothing more amazing than stupidity in action."
-- Thomas Matthews
<http://www.cs.auckland.ac.nz/~pgut001/pubs/vista_cost.txt>

[Randy Howard]

On Fri, 19 Jan 2007 05:15:46 -0600, CBFalconer wrote
(in article <45***************@yahoo.com>):

Randy Howard wrote:

>On Wed, 17 Jan 2007 10:27:10 -0600, Simon Biber wrote

>>#ifdef _WIN32
# define FORMAT_LONG_LONG "I64"
#else
# define FORMAT_LONG_LONG "ll"
#endif

...
printf("%" FORMAT_LONG_LONG "d\n", value);

If anyone ever needs a convincing argument for why not to use
Microsoft development tools, the above should suffice.

Or operating systems.

Very true. I haven't bought anything from Microsoft for a few years
now, and computer issues have been on a very steep decline since I
started weaning people off of Windows. It's quite nice, and I highly
recommend it.

See the URL in my sig. for horror story about Vista.

It's only been posted about 10,000 places, commented on far and wide,
and even made several tech podcasts of late. But thanks for adding
that 10,001st copy. :-)

--
Randy Howard (2reply remove FOOBAR)
"The power of accurate observation is called cynicism by those
who have not got it." - George Bernard Shaw

[CBFalconer]

Randy Howard wrote:

cbfalconer wrote:

.... snip ...

>
Very true. I haven't bought anything from Microsoft for a few years
now, and computer issues have been on a very steep decline since I
started weaning people off of Windows. It's quite nice, and I highly
recommend it.

>See the URL in my sig. for horror story about Vista.

It's only been posted about 10,000 places, commented on far and wide,
and even made several tech podcasts of late. But thanks for adding
that 10,001st copy. :-)

Around here (sparse population) doctors are highly dependant on
images over the internet, as I observed with my recent colon
problems etc. So I have been propagating that to them. My
principal physician has a major system on XP that he curses
regularly. I advised him to refuse any offered upgrades to Vista,
to read the URL, and hound his supplier for a Linux version.
However, his software supplier is located in Seattle, so I suspect
bedmates.

--
"A man who is right every time is not likely to do very much."
-- Francis Crick, co-discover of DNA
"There is nothing more amazing than stupidity in action."
-- Thomas Matthews
<http://www.cs.auckland.ac.nz/~pgut001/pubs/vista_cost.txt>

[Lane Straatman]

"CBFalconer" <cb********@yahoo.comwrote in message
news:45***************@yahoo.com...

Randy Howard wrote:

>cbfalconer wrote:

... snip ...

>>
Very true. I haven't bought anything from Microsoft for a few years
now, and computer issues have been on a very steep decline since I
started weaning people off of Windows. It's quite nice, and I highly
recommend it.

>>See the URL in my sig. for horror story about Vista.

It's only been posted about 10,000 places, commented on far and wide,
and even made several tech podcasts of late. But thanks for adding
that 10,001st copy. :-)

Around here (sparse population) doctors are highly dependant on
images over the internet, as I observed with my recent colon
problems etc. So I have been propagating that to them. My
principal physician has a major system on XP that he curses
regularly. I advised him to refuse any offered upgrades to Vista,
to read the URL, and hound his supplier for a Linux version.
However, his software supplier is located in Seattle, so I suspect
bedmates.

Friends don't let friends buy something *fresh* off the rollers at MS. LS

[Lane Straatman]

"Simon Biber" <ne**@ralmin.ccwrote in message
news:45**********@news.peopletelecom.com.au...

Barry wrote:

><we******@gmail.comwrote in message
news:11**********************@s34g2000cwa.googleg roups.com...

>>Simon Biber wrote:
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.
Indeed. Please take a look at:

http://www.pobox.com/~qed/poker.zip

It does both 5 and 7 card stud calculations by monotonically mapping
each hand to a score metric. All exact ties are all calculated
correctly, for example. Also the two few bits of the metric correctly
classify the hand into the rough hand categorization (two of a kind,
flush, etc).

(I was also working on a full general heads-up situation evaluator, but
got side tracked. There are non-loop based methods for accelerating
that but it starts getting really really complicated. I would probably
require several days of working at it to get it.)

Paul, I took the OPs program and linked it with pokeref.c and it cut
the execution time from about 190 secs. to 100 secs. on my old
laptop. That included the fact that I undid some of the work done
by masking the score of the hand back out so I could classify
it in the same manner the OP had originally and verify the results.

I did something quite similar. My code can now use Paul's fast
bit-twiddling functions when N is 5 or 7, or revert to my slow function
when N is something else.
#define USE_FAST

#if defined(USE_FAST) && (N == 7 || N == 5)

int classify(int *hand)

How do you adjust the calls from type 'enum class' to 'int'? LS

[Barry]

"Lane Straatman" <in*****@invalid.netwrote in message
news:12*************@corp.supernews.com...

>
"Simon Biber" <ne**@ralmin.ccwrote in message
news:45**********@news.peopletelecom.com.au...

Barry wrote:

<we******@gmail.comwrote in message
news:11**********************@s34g2000cwa.googlegr oups.com...
Simon Biber wrote:
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.
Indeed. Please take a look at:

http://www.pobox.com/~qed/poker.zip

It does both 5 and 7 card stud calculations by monotonically mapping
each hand to a score metric. All exact ties are all calculated
correctly, for example. Also the two few bits of the metric correctly
classify the hand into the rough hand categorization (two of a kind,
flush, etc).

(I was also working on a full general heads-up situation evaluator,

but

>got side tracked. There are non-loop based methods for accelerating
that but it starts getting really really complicated. I would

probably

>require several days of working at it to get it.)

Paul, I took the OPs program and linked it with pokeref.c and it cut
the execution time from about 190 secs. to 100 secs. on my old
laptop. That included the fact that I undid some of the work done
by masking the score of the hand back out so I could classify
it in the same manner the OP had originally and verify the results.

I did something quite similar. My code can now use Paul's fast
bit-twiddling functions when N is 5 or 7, or revert to my slow function
when N is something else.
#define USE_FAST

#if defined(USE_FAST) && (N == 7 || N == 5)

int classify(int *hand)

How do you adjust the calls from type 'enum class' to 'int'? LS

I must be missing something here, enums are ints aren't they?

[Keith Thompson]

"Barry" <ba****@nullhighstream.netwrites:

"Lane Straatman" <in*****@invalid.netwrote in message
news:12*************@corp.supernews.com...

"Simon Biber" <ne**@ralmin.ccwrote in message

[snip]

I did something quite similar. My code can now use Paul's fast
bit-twiddling functions when N is 5 or 7, or revert to my slow function
when N is something else.
>
>
#define USE_FAST
>
#if defined(USE_FAST) && (N == 7 || N == 5)
>
int classify(int *hand)

How do you adjust the calls from type 'enum class' to 'int'? LS

I must be missing something here, enums are ints aren't they?

Enums are integers; they aren't necessarily ints.

C99 6.7.2.2p4:

Each enumerated type shall be compatible with char, a signed
integer type, or an unsigned integer type. The choice of type is
implementation-defined, but shall be capable of representing the
values of all the members of the enumeration.

Enum literals are of type int by definition (<OT>in C; C++ has
different rules</OT>). But the enum type itself can be of any integer
type of the compiler's choosing. In many cases, this doesn't matter,
since different integer types can be freely and implicitly converted
to each other. But pointers cannot. If you have a pointer to an enum
type, and the compiler has chosen to make the enum type compatible
with short, then that pointer is *not* compatible with int*.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <* <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

[Lane Straatman]

"Barry" <ba****@nullhighstream.netwrote in message
news:12*************@corp.supernews.com...

>
"Lane Straatman" <in*****@invalid.netwrote in message
news:12*************@corp.supernews.com...

>>
"Simon Biber" <ne**@ralmin.ccwrote in message
news:45**********@news.peopletelecom.com.au...

Barry wrote:
<we******@gmail.comwrote in message
news:11**********************@s34g2000cwa.googleg roups.com...
Simon Biber wrote:
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.
Indeed. Please take a look at:

http://www.pobox.com/~qed/poker.zip

It does both 5 and 7 card stud calculations by monotonically mapping
each hand to a score metric. All exact ties are all calculated
correctly, for example. Also the two few bits of the metric
correctly
classify the hand into the rough hand categorization (two of a kind,
flush, etc).

(I was also working on a full general heads-up situation evaluator,

but

>>got side tracked. There are non-loop based methods for accelerating
that but it starts getting really really complicated. I would

probably

>>require several days of working at it to get it.)

Paul, I took the OPs program and linked it with pokeref.c and it cut
the execution time from about 190 secs. to 100 secs. on my old
laptop. That included the fact that I undid some of the work done
by masking the score of the hand back out so I could classify
it in the same manner the OP had originally and verify the results.

I did something quite similar. My code can now use Paul's fast
bit-twiddling functions when N is 5 or 7, or revert to my slow function
when N is something else.
#define USE_FAST

#if defined(USE_FAST) && (N == 7 || N == 5)

int classify(int *hand)

How do you adjust the calls from type 'enum class' to 'int'? LS

I must be missing something here, enums are ints aren't they?

I think it much more likely the case that _I_ am missing something. I think
the bulk of my trouble is in vendor-related questions, and therefore posted
in a different ng:
news:12*************@corp.supernews.com...
--
LS