Wizard
• Posts: 26842
Joined: Oct 14, 2009
Thanked by
March 20th, 2024 at 11:35:05 AM permalink
The recent discussion about face up cards in Ultimate Texas Hold 'em (UTH) touched on the topic of fast ways of scoring 7-card hands.

When I originally wrote my UTH program the compiler didn't let me declare an array as large as all 133,784,560 ways of choosing 7 cards out of 52. However, now it does. My basic idea is to score each hand only once and store those scores in an array. Without shortcuts, there are 5,023,174,090,334,400 combinations to loop through in UTH. That can be cut down to 640,208,462,493,600 if you analyze only the 169 different types of starting hands, as opposed to all combin(52,2)=1,326 ways to choose 2 cards out of 52 for the player's initial two cards.

If I redid the program or analyzed any other game involving scoring 7-card poker hands, I would use this new and improved method of populating an array of all 134 million ways to choose 7 cards out of a deck only once and then referring to that array for any set of 7 cards.

A tricky part is going from 7 numbers out of a range of 52 to a single number that ranges from 0 to 133,784,560. Here is the mapping code I use:

`int HandIndex7(int CardIndex[]){	int r;	r = combin_array[52][7] - combin_array[52 - CardIndex[0]][7];	r += combin_array[51 - CardIndex[0]][6] - combin_array[52 - CardIndex[1]][6];	r += combin_array[51 - CardIndex[1]][5] - combin_array[52 - CardIndex[2]][5];	r += combin_array[51 - CardIndex[2]][4] - combin_array[52 - CardIndex[3]][4];	r += combin_array[51 - CardIndex[3]][3] - combin_array[52 - CardIndex[4]][3];	r += combin_array[51 - CardIndex[4]][2] - combin_array[52 - CardIndex[5]][2];	r += CardIndex[6] - CardIndex[5] - 1;	return r;}`

combin_array is a two-dimensional array of the number of combinations up to 7 out of 52. I do this to cut down on time doing combinatorial math. The array CardIndex is an array of 7 integers from 0 to 51, sorted from least to highest.

If there is interest, I'll explain the logic of this function.

Bottom line is my program takes 56 seconds to populate the initial array of all possible 7-card hands out of 52.

After that, it takes 3.41 seconds to go through all 133,784,560 possible combinations of 7 cards out of 52, map each set to an integer, and get the poker value from the array given the integer mapping.

For a program like UTH, this should speed up the time by about 93%.

The full code is below.

`// poker-fast-score.cpp : This file contains the 'main' function. Program execution begins and ends there.//#include <iostream>#include <time.h>struct card{	int r;	int s;};void load_array();int HandIndex7(int CardIndex[]);void CombinArray(void);int combin(int x, int y);int score7ex(card t[]);void score_fast(int poker_score[]);int combin_array[53][8];int score_array[133784560];void main(){	unsigned int t1, t2,t3;	int i,poker_score[9];	t1 = time(NULL);    std::cerr << "Loading combinations array\n";	CombinArray();	std::cerr << "Loading score array\n";	load_array();	t2 = time(NULL);	std::cerr << "Time to populate score array =\t" << t2 - t1 << " seconds\n"; // 56 seconds	for (i = 1; i <= 100; i++) // 100 times = 341 seconds	{		score_fast(poker_score);		std::cerr << "Scoring # =\t" << i << "\n";	}	for (i = 8; i >= 0; i--)		std::cout << i << "\t" << poker_score << "\n";	t3 = time(NULL);	std::cerr << "Time to score all combinations (fast) 100 times =\t" << t3 - t2 << " seconds\n";	return;}void load_array(){	int i, count,c0,c1,c2,c3,c4,c5,c6,sc;	card deck[52],hand[7];	for (i = 0; i <= 51; i++)	{		deck.r = (int)(i / 4);		deck.s = i % 4;	}	count = 0;	for (c0 = 0; c0 <= 45; c0++)	{		hand[0].r = (int)(c0 / 4);		hand[0].s = c0 % 4;		for (c1 = c0+1; c1 <= 46; c1++)		{			hand[1].r = (int)(c1 / 4);			hand[1].s = c1 % 4;			for (c2 = c1 + 1; c2 <= 47; c2++)			{				hand[2].r = (int)(c2 / 4);				hand[2].s = c2 % 4;				for (c3 = c2 + 1; c3 <= 48; c3++)				{					hand[3].r = (int)(c3 / 4);					hand[3].s = c3 % 4;					for (c4 = c3 + 1; c4 <= 49; c4++)					{						hand[4].r = (int)(c4 / 4);						hand[4].s = c4 % 4;						for (c5 = c4 + 1; c5 <= 50; c5++)						{							hand[5].r = (int)(c5 / 4);							hand[5].s = c5 % 4;							for (c6 = c5 + 1; c6 <= 51; c6++)							{								hand[6].r = (int)(c6 / 4);								hand[6].s = c6 % 4;								sc = score7ex(hand);								score_array[count] = sc;								count++;								if (count % 1000000 == 0)									std::cerr << (double)count / 133784560.0 << "\n";							}						}					}				}			}		}	} }void score_fast(int poker_score[]){	int index,CardIndex[7], c0, c1, c2, c3, c4, c5, c6,sc,sc_ex;	for (c0 = 0; c0 <= 9; c0++)		poker_score[c0] = 0;	for (c0 = 0; c0 <= 45; c0++)	{		CardIndex[0] = c0;		for (c1 = c0 + 1; c1 <= 46; c1++)		{			CardIndex[1] = c1;			for (c2 = c1 + 1; c2 <= 47; c2++)			{				CardIndex[2] = c2;				for (c3 = c2 + 1; c3 <= 48; c3++)				{					CardIndex[3] = c3;					for (c4 = c3 + 1; c4 <= 49; c4++)					{						CardIndex[4] = c4;						for (c5 = c4 + 1; c5 <= 50; c5++)						{							CardIndex[5] = c5;							for (c6 = c5 + 1; c6 <= 51; c6++)							{								CardIndex[6] = c6;								index = HandIndex7(CardIndex);								sc_ex = score_array[index];								sc = (int)(sc_ex / 371293);								poker_score[sc]++;							}						}					}				}			}		}	}}int HandIndex7(int CardIndex[]){	int r;	r = combin_array[52][7] - combin_array[52 - CardIndex[0]][7];	r += combin_array[51 - CardIndex[0]][6] - combin_array[52 - CardIndex[1]][6];	r += combin_array[51 - CardIndex[1]][5] - combin_array[52 - CardIndex[2]][5];	r += combin_array[51 - CardIndex[2]][4] - combin_array[52 - CardIndex[3]][4];	r += combin_array[51 - CardIndex[3]][3] - combin_array[52 - CardIndex[4]][3];	r += combin_array[51 - CardIndex[4]][2] - combin_array[52 - CardIndex[5]][2];	r += CardIndex[6] - CardIndex[5] - 1;	return r;}int combin(int x, int y){	int i;	float r = 1;	for (i = x - y + 1; i <= x; i++)	{		r *= i;		r /= (i - x + y);	}	return (int)r;}void CombinArray(void){	int i, j;	for (i = 0; i <= 52; i++)	{		for (j = 0; j <= 7; j++)			combin_array = combin(i, j);	}}int score7ex(card t[]) // exact value of 7-card hand{	int straight = 0;	int flush = 0;	int i, r, s, pt, value[8], SuitTot, TotStr;	for (i = 0; i <= 7; i++)		value = 0;	if ((t[0].r == t[3].r) || (t[1].r == t[4].r) || (t[2].r == t[5].r))	{		value[0] = 7; // four of a kind 		value[1] = t[3].r;		value[2] = t[6].r;		return value[5] + 13 * value[4] + 169 * value[3] + 2197 * value[2] + 28561 * value[1] + 371293 * value[0];	}	else if (t[3].r == t[6].r)	{		value[0] = 7; // four of a kind 		value[1] = t[3].r;		value[2] = t[2].r;		return value[5] + 13 * value[4] + 169 * value[3] + 2197 * value[2] + 28561 * value[1] + 371293 * value[0];	}	else if (t[4].r == t[6].r)	{		if (t[2].r == t[3].r)		{			value[0] = 6; // full house 			value[1] = t[4].r;			value[2] = t[2].r;			return value[5] + 13 * value[4] + 169 * value[3] + 2197 * value[2] + 28561 * value[1] + 371293 * value[0];		}		else if (t[1].r == t[2].r)		{			value[0] = 6; // full house 			value[1] = t[4].r;			value[2] = t[1].r;			return value[5] + 13 * value[4] + 169 * value[3] + 2197 * value[2] + 28561 * value[1] + 371293 * value[0];		}		else if (t[0].r == t[1].r)		{			value[0] = 6; // full house 			value[1] = t[4].r;			value[2] = t[0].r;			return value[5] + 13 * value[4] + 169 * value[3] + 2197 * value[2] + 28561 * value[1] + 371293 * value[0];		}	}	else if (t[3].r == t[5].r)	{		if (t[1].r == t[2].r)		{			value[0] = 6; // full house 			value[1] = t[3].r;			value[2] = t[1].r;			return value[5] + 13 * value[4] + 169 * value[3] + 2197 * value[2] + 28561 * value[1] + 371293 * value[0];		}		else if (t[0].r == t[1].r)		{			value[0] = 6; // full house 			value[1] = t[3].r;			value[2] = t[0].r;			return value[5] + 13 * value[4] + 169 * value[3] + 2197 * value[2] + 28561 * value[1] + 371293 * value[0];		}	}	else if (t[2].r == t[4].r)	{		if (t[5].r == t[6].r)		{			value[0] = 6; // full house 			value[1] = t[2].r;			value[2] = t[5].r;			return value[5] + 13 * value[4] + 169 * value[3] + 2197 * value[2] + 28561 * value[1] + 371293 * value[0];		}		else if (t[0].r == t[1].r)		{			value[0] = 6; // full house 			value[1] = t[2].r;			value[2] = t[0].r;			return value[5] + 13 * value[4] + 169 * value[3] + 2197 * value[2] + 28561 * value[1] + 371293 * value[0];		}	}	else if (t[1].r == t[3].r)	{		if (t[5].r == t[6].r)		{			value[0] = 6; // full house 			value[1] = t[1].r;			value[2] = t[5].r;			return value[5] + 13 * value[4] + 169 * value[3] + 2197 * value[2] + 28561 * value[1] + 371293 * value[0];		}		else if (t[4].r == t[5].r)		{			value[0] = 6; // full house 			value[1] = t[1].r;			value[2] = t[4].r;			return value[5] + 13 * value[4] + 169 * value[3] + 2197 * value[2] + 28561 * value[1] + 371293 * value[0];		}	}	else if (t[0].r == t[2].r)	{		if (t[5].r == t[6].r)		{			value[0] = 6; // full house 			value[1] = t[0].r;			value[2] = t[5].r;			return value[5] + 13 * value[4] + 169 * value[3] + 2197 * value[2] + 28561 * value[1] + 371293 * value[0];		}		else if (t[4].r == t[5].r)		{			value[0] = 6; // full house 			value[1] = t[0].r;			value[2] = t[4].r;			return value[5] + 13 * value[4] + 169 * value[3] + 2197 * value[2] + 28561 * value[1] + 371293 * value[0];		}		else if (t[3].r == t[4].r)		{			value[0] = 6; // full house 			value[1] = t[0].r;			value[2] = t[3].r;			return value[5] + 13 * value[4] + 169 * value[3] + 2197 * value[2] + 28561 * value[1] + 371293 * value[0];		}	}	for (s = 0; s <= 3; s++)	{		SuitTot = (t[0].s == s ? 1 : 0) + (t[1].s == s ? 1 : 0) + (t[2].s == s ? 1 : 0) + (t[3].s == s ? 1 : 0) + (t[4].s == s ? 1 : 0) + (t[5].s == s ? 1 : 0) + (t[6].s == s ? 1 : 0);		if (SuitTot >= 5)		{			for (r = 8; r >= 0; r--)			{				TotStr = 0;				for (i = 0; i <= 4; i++)					TotStr += (t[0].r == r + i ? 1 : 0) * (t[0].s == s ? 1 : 0)					+ (t[1].r == r + i ? 1 : 0) * (t[1].s == s ? 1 : 0)					+ (t[2].r == r + i ? 1 : 0) * (t[2].s == s ? 1 : 0)					+ (t[3].r == r + i ? 1 : 0) * (t[3].s == s ? 1 : 0)					+ (t[4].r == r + i ? 1 : 0) * (t[4].s == s ? 1 : 0)					+ (t[5].r == r + i ? 1 : 0) * (t[5].s == s ? 1 : 0)					+ (t[6].r == r + i ? 1 : 0) * (t[6].s == s ? 1 : 0);				if (TotStr == 5) // consecutive straight				{					value[0] = 8;					value[1] = r + 4;					value[2] = r + 3;					value[3] = r + 2;					value[4] = r + 1;					value[5] = r;					return value[5] + 13 * value[4] + 169 * value[3] + 2197 * value[2] + 28561 * value[1] + 371293 * value[0];				}			}			TotStr = 0;			TotStr += (t[0].r == 12 ? 1 : 0) * (t[0].s == s ? 1 : 0) + (t[1].r == 12 ? 1 : 0) * (t[1].s == s ? 1 : 0) + (t[2].r == 12 ? 1 : 0) * (t[2].s == s ? 1 : 0) + (t[3].r == 12 ? 1 : 0) * (t[3].s == s ? 1 : 0) + (t[4].r == 12 ? 1 : 0) * (t[4].s == s ? 1 : 0) + (t[5].r == 12 ? 1 : 0) * (t[5].s == s ? 1 : 0) + (t[6].r == 12 ? 1 : 0) * (t[6].s == s ? 1 : 0);			TotStr += (t[0].r == 0 ? 1 : 0) * (t[0].s == s ? 1 : 0) + (t[1].r == 0 ? 1 : 0) * (t[1].s == s ? 1 : 0) + (t[2].r == 0 ? 1 : 0) * (t[2].s == s ? 1 : 0) + (t[3].r == 0 ? 1 : 0) * (t[3].s == s ? 1 : 0) + (t[4].r == 0 ? 1 : 0) * (t[4].s == s ? 1 : 0) + (t[5].r == 0 ? 1 : 0) * (t[5].s == s ? 1 : 0) + (t[6].r == 0 ? 1 : 0) * (t[6].s == s ? 1 : 0);			TotStr += (t[0].r == 1 ? 1 : 0) * (t[0].s == s ? 1 : 0) + (t[1].r == 1 ? 1 : 0) * (t[1].s == s ? 1 : 0) + (t[2].r == 1 ? 1 : 0) * (t[2].s == s ? 1 : 0) + (t[3].r == 1 ? 1 : 0) * (t[3].s == s ? 1 : 0) + (t[4].r == 1 ? 1 : 0) * (t[4].s == s ? 1 : 0) + (t[5].r == 1 ? 1 : 0) * (t[5].s == s ? 1 : 0) + (t[6].r == 1 ? 1 : 0) * (t[6].s == s ? 1 : 0);			TotStr += (t[0].r == 2 ? 1 : 0) * (t[0].s == s ? 1 : 0) + (t[1].r == 2 ? 1 : 0) * (t[1].s == s ? 1 : 0) + (t[2].r == 2 ? 1 : 0) * (t[2].s == s ? 1 : 0) + (t[3].r == 2 ? 1 : 0) * (t[3].s == s ? 1 : 0) + (t[4].r == 2 ? 1 : 0) * (t[4].s == s ? 1 : 0) + (t[5].r == 2 ? 1 : 0) * (t[5].s == s ? 1 : 0) + (t[6].r == 2 ? 1 : 0) * (t[6].s == s ? 1 : 0);			TotStr += (t[0].r == 3 ? 1 : 0) * (t[0].s == s ? 1 : 0) + (t[1].r == 3 ? 1 : 0) * (t[1].s == s ? 1 : 0) + (t[2].r == 3 ? 1 : 0) * (t[2].s == s ? 1 : 0) + (t[3].r == 3 ? 1 : 0) * (t[3].s == s ? 1 : 0) + (t[4].r == 3 ? 1 : 0) * (t[4].s == s ? 1 : 0) + (t[5].r == 3 ? 1 : 0) * (t[5].s == s ? 1 : 0) + (t[6].r == 3 ? 1 : 0) * (t[6].s == s ? 1 : 0);			if (TotStr == 5) // A2345 straight			{				value[0] = 8;				value[1] = 3;				value[2] = 2;				value[3] = 1;				value[4] = 0;				value[5] = -1;				return value[5] + 13 * value[4] + 169 * value[3] + 2197 * value[2] + 28561 * value[1] + 371293 * value[0];			}		}	}	for (s = 0; s <= 3; s++)	{		SuitTot = (t[0].s == s ? 1 : 0) + (t[1].s == s ? 1 : 0) + (t[2].s == s ? 1 : 0) + (t[3].s == s ? 1 : 0) + (t[4].s == s ? 1 : 0) + (t[5].s == s ? 1 : 0) + (t[6].s == s ? 1 : 0);		if (SuitTot >= 5)		{			value[0] = 5;			pt = 1;			for (i = 6; i >= 0; i--)			{				if (t.s == s)				{					value[pt] = t.r;					pt++;				}			}			return value[5] + 13 * value[4] + 169 * value[3] + 2197 * value[2] + 28561 * value[1] + 371293 * value[0];		}	}	for (r = 8; r >= 0; r--)	{		TotStr = 0;		for (i = 0; i <= 4; i++)			TotStr += (((t[0].r == r + i ? 1 : 0) + (t[1].r == r + i ? 1 : 0) + (t[2].r == r + i ? 1 : 0) + (t[3].r == r + i ? 1 : 0) + (t[4].r == r + i ? 1 : 0) + (t[5].r == r + i ? 1 : 0) + (t[6].r == r + i ? 1 : 0)) > 0 ? 1 : 0);		if (TotStr == 5) // consecutive straight		{			value[0] = 4;			value[1] = r + 4;			value[2] = r + 3;			value[3] = r + 2;			value[4] = r + 1;			value[5] = r;			return value[5] + 13 * value[4] + 169 * value[3] + 2197 * value[2] + 28561 * value[1] + 371293 * value[0];		}	}	TotStr = 0;	TotStr += (((t[0].r == 12 ? 1 : 0) + (t[1].r == 12 ? 1 : 0) + (t[2].r == 12 ? 1 : 0) + (t[3].r == 12 ? 1 : 0) + (t[4].r == 12 ? 1 : 0) + (t[5].r == 12 ? 1 : 0) + (t[6].r == 12 ? 1 : 0)) > 0 ? 1 : 0);	TotStr += (((t[0].r == 0 ? 1 : 0) + (t[1].r == 0 ? 1 : 0) + (t[2].r == 0 ? 1 : 0) + (t[3].r == 0 ? 1 : 0) + (t[4].r == 0 ? 1 : 0) + (t[5].r == 0 ? 1 : 0) + (t[6].r == 0 ? 1 : 0)) > 0 ? 1 : 0);	TotStr += (((t[0].r == 1 ? 1 : 0) + (t[1].r == 1 ? 1 : 0) + (t[2].r == 1 ? 1 : 0) + (t[3].r == 1 ? 1 : 0) + (t[4].r == 1 ? 1 : 0) + (t[5].r == 1 ? 1 : 0) + (t[6].r == 1 ? 1 : 0)) > 0 ? 1 : 0);	TotStr += (((t[0].r == 2 ? 1 : 0) + (t[1].r == 2 ? 1 : 0) + (t[2].r == 2 ? 1 : 0) + (t[3].r == 2 ? 1 : 0) + (t[4].r == 2 ? 1 : 0) + (t[5].r == 2 ? 1 : 0) + (t[6].r == 2 ? 1 : 0)) > 0 ? 1 : 0);	TotStr += (((t[0].r == 3 ? 1 : 0) + (t[1].r == 3 ? 1 : 0) + (t[2].r == 3 ? 1 : 0) + (t[3].r == 3 ? 1 : 0) + (t[4].r == 3 ? 1 : 0) + (t[5].r == 3 ? 1 : 0) + (t[6].r == 3 ? 1 : 0)) > 0 ? 1 : 0);	if (TotStr == 5) // A2345 straight	{		value[0] = 4;		value[1] = 3;		value[2] = 2;		value[3] = 1;		value[4] = 0;		value[5] = -1;		return value[5] + 13 * value[4] + 169 * value[3] + 2197 * value[2] + 28561 * value[1] + 371293 * value[0];	}	if (t[4].r == t[6].r)	{		value[0] = 3; // three of a kind		value[1] = t[4].r;		value[2] = t[3].r;		value[3] = t[2].r;		return value[5] + 13 * value[4] + 169 * value[3] + 2197 * value[2] + 28561 * value[1] + 371293 * value[0];	}	else if (t[3].r == t[5].r)	{		value[0] = 3; // three of a kind		value[1] = t[3].r;		value[2] = t[6].r;		value[3] = t[2].r;		return value[5] + 13 * value[4] + 169 * value[3] + 2197 * value[2] + 28561 * value[1] + 371293 * value[0];	}	else if (t[2].r == t[4].r)	{		value[0] = 3; // three of a kind		value[1] = t[2].r;		value[2] = t[6].r;		value[3] = t[5].r;		return value[5] + 13 * value[4] + 169 * value[3] + 2197 * value[2] + 28561 * value[1] + 371293 * value[0];	}	else if (t[1].r == t[3].r)	{		value[0] = 3; // three of a kind		value[1] = t[1].r;		value[2] = t[6].r;		value[3] = t[5].r;		return value[5] + 13 * value[4] + 169 * value[3] + 2197 * value[2] + 28561 * value[1] + 371293 * value[0];	}	else if (t[0].r == t[2].r)	{		value[0] = 3; // three of a kind		value[1] = t[0].r;		value[2] = t[6].r;		value[3] = t[5].r;		return value[5] + 13 * value[4] + 169 * value[3] + 2197 * value[2] + 28561 * value[1] + 371293 * value[0];	}	if (t[5].r == t[6].r)	{		if (t[3].r == t[4].r)		{			value[0] = 2; // two pair			value[1] = t[5].r;			value[2] = t[3].r;			value[3] = t[2].r;			return value[5] + 13 * value[4] + 169 * value[3] + 2197 * value[2] + 28561 * value[1] + 371293 * value[0];		}		else if (t[2].r == t[3].r)		{			value[0] = 2; // two pair			value[1] = t[5].r;			value[2] = t[2].r;			value[3] = t[4].r;			return value[5] + 13 * value[4] + 169 * value[3] + 2197 * value[2] + 28561 * value[1] + 371293 * value[0];		}		if (t[1].r == t[2].r)		{			value[0] = 2; // two pair			value[1] = t[5].r;			value[2] = t[1].r;			value[3] = t[4].r;			return value[5] + 13 * value[4] + 169 * value[3] + 2197 * value[2] + 28561 * value[1] + 371293 * value[0];		}		if (t[0].r == t[1].r)		{			value[0] = 2; // two pair			value[1] = t[5].r;			value[2] = t[0].r;			value[3] = t[4].r;			return value[5] + 13 * value[4] + 169 * value[3] + 2197 * value[2] + 28561 * value[1] + 371293 * value[0];		}	}	if (t[4].r == t[5].r)	{		if (t[2].r == t[3].r)		{			value[0] = 2; // two pair			value[1] = t[4].r;			value[2] = t[2].r;			value[3] = t[6].r;			return value[5] + 13 * value[4] + 169 * value[3] + 2197 * value[2] + 28561 * value[1] + 371293 * value[0];		}		else if (t[1].r == t[2].r)		{			value[0] = 2; // two pair			value[1] = t[4].r;			value[2] = t[1].r;			value[3] = t[6].r;			return value[5] + 13 * value[4] + 169 * value[3] + 2197 * value[2] + 28561 * value[1] + 371293 * value[0];		}		else if (t[0].r == t[1].r)		{			value[0] = 2; // two pair			value[1] = t[4].r;			value[2] = t[0].r;			value[3] = t[6].r;			return value[5] + 13 * value[4] + 169 * value[3] + 2197 * value[2] + 28561 * value[1] + 371293 * value[0];		}	}	if (t[3].r == t[4].r)	{		if (t[1].r == t[2].r)		{			value[0] = 2; // two pair			value[1] = t[3].r;			value[2] = t[1].r;			value[3] = t[6].r;			return value[5] + 13 * value[4] + 169 * value[3] + 2197 * value[2] + 28561 * value[1] + 371293 * value[0];		}		else if (t[0].r == t[1].r)		{			value[0] = 2; // two pair			value[1] = t[3].r;			value[2] = t[0].r;			value[3] = t[6].r;			return value[5] + 13 * value[4] + 169 * value[3] + 2197 * value[2] + 28561 * value[1] + 371293 * value[0];		}	}	if (t[2].r == t[3].r)	{		if (t[0].r == t[1].r)		{			value[0] = 2; // two pair			value[1] = t[2].r;			value[2] = t[0].r;			value[3] = t[6].r;			return value[5] + 13 * value[4] + 169 * value[3] + 2197 * value[2] + 28561 * value[1] + 371293 * value[0];		}	}	if (t[5].r == t[6].r)	{		value[0] = 1;		value[1] = t[5].r;		value[2] = t[4].r;		value[3] = t[3].r;		value[4] = t[2].r;		return value[5] + 13 * value[4] + 169 * value[3] + 2197 * value[2] + 28561 * value[1] + 371293 * value[0];	}	else if (t[4].r == t[5].r)	{		value[0] = 1;		value[1] = t[4].r;		value[2] = t[6].r;		value[3] = t[3].r;		value[4] = t[2].r;		return value[5] + 13 * value[4] + 169 * value[3] + 2197 * value[2] + 28561 * value[1] + 371293 * value[0];	}	else if (t[3].r == t[4].r)	{		value[0] = 1;		value[1] = t[3].r;		value[2] = t[6].r;		value[3] = t[5].r;		value[4] = t[2].r;		return value[5] + 13 * value[4] + 169 * value[3] + 2197 * value[2] + 28561 * value[1] + 371293 * value[0];	}	else if (t[2].r == t[3].r)	{		value[0] = 1;		value[1] = t[2].r;		value[2] = t[6].r;		value[3] = t[5].r;		value[4] = t[4].r;		return value[5] + 13 * value[4] + 169 * value[3] + 2197 * value[2] + 28561 * value[1] + 371293 * value[0];	}	else if (t[1].r == t[2].r)	{		value[0] = 1;		value[1] = t[1].r;		value[2] = t[6].r;		value[3] = t[5].r;		value[4] = t[4].r;		return value[5] + 13 * value[4] + 169 * value[3] + 2197 * value[2] + 28561 * value[1] + 371293 * value[0];	}	else if (t[0].r == t[1].r)	{		value[0] = 1;		value[1] = t[0].r;		value[2] = t[6].r;		value[3] = t[5].r;		value[4] = t[4].r;		return value[5] + 13 * value[4] + 169 * value[3] + 2197 * value[2] + 28561 * value[1] + 371293 * value[0];	}	value[0] = 0;	value[1] = t[6].r;	value[2] = t[5].r;	value[3] = t[4].r;	value[4] = t[3].r;	value[2] = t[2].r;	return value[5] + 13 * value[4] + 169 * value[3] + 2197 * value[2] + 28561 * value[1] + 371293 * value[0];}`

I know Mental uses a hash algorithm, which I quickly failed at implementing. I'm happy to hear more about that and all other ideas for analyzing games like UTH in a matter of hours as opposed to days.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
Mental
• Posts: 1508
Joined: Dec 10, 2018
March 20th, 2024 at 5:08:17 PM permalink
Quote: Wizard

The recent discussion about face up cards in Ultimate Texas Hold 'em (UTH) touched on the topic of fast ways of scoring 7-card hands.

When I originally wrote my UTH program the compiler didn't let me declare an array as large as all 133,784,560 ways of choosing 7 cards out of 52. However, now it does. My basic idea is to score each hand only once and store those scores in an array. Without shortcuts, there are 5,023,174,090,334,400 combinations to loop through in UTH. That can be cut down to 640,208,462,493,600 if you analyze only the 169 different types of starting hands, as opposed to all combin(52,2)=1,326 ways to choose 2 cards out of 52 for the player's initial two cards.

If I redid the program or analyzed any other game involving scoring 7-card poker hands, I would use this new and improved method of populating an array of all 134 million ways to choose 7 cards out of a deck only once and then referring to that array for any set of 7 cards.

A tricky part is going from 7 numbers out of a range of 52 to a single number that ranges from 0 to 133,784,560. Here is the mapping code I use:

`int HandIndex7(int CardIndex[]){	int r;	r = combin_array[52][7] - combin_array[52 - CardIndex[0]][7];	r += combin_array[51 - CardIndex[0]][6] - combin_array[52 - CardIndex[1]][6];	r += combin_array[51 - CardIndex[1]][5] - combin_array[52 - CardIndex[2]][5];	r += combin_array[51 - CardIndex[2]][4] - combin_array[52 - CardIndex[3]][4];	r += combin_array[51 - CardIndex[3]][3] - combin_array[52 - CardIndex[4]][3];	r += combin_array[51 - CardIndex[4]][2] - combin_array[52 - CardIndex[5]][2];	r += CardIndex[6] - CardIndex[5] - 1;	return r;}`

combin_array is a two-dimensional array of the number of combinations up to 7 out of 52. I do this to cut down on time doing combinatorial math. The array CardIndex is an array of 7 integers from 0 to 51, sorted from least to highest.

If there is interest, I'll explain the logic of this function.

Bottom line is my program takes 56 seconds to populate the initial array of all possible 7-card hands out of 52.

After that, it takes 3.41 seconds to go through all 133,784,560 possible combinations of 7 cards out of 52, map each set to an integer, and get the poker value from the array given the integer mapping.

For a program like UTH, this should speed up the time by about 93%.

The full code is below.

`// poker-fast-score.cpp : This file contains the 'main' function. Program execution begins and ends there.//#include <iostream>#include <time.h>struct card{	int r;	int s;};void load_array();int HandIndex7(int CardIndex[]);void CombinArray(void);int combin(int x, int y);int score7ex(card t[]);void score_fast(int poker_score[]);int combin_array[53][8];int score_array[133784560];void main(){	unsigned int t1, t2,t3;	int i,poker_score[9];	t1 = time(NULL);    std::cerr << "Loading combinations array\n";	CombinArray();	std::cerr << "Loading score array\n";	load_array();	t2 = time(NULL);	std::cerr << "Time to populate score array =\t" << t2 - t1 << " seconds\n"; // 56 seconds	for (i = 1; i <= 100; i++) // 100 times = 341 seconds	{		score_fast(poker_score);		std::cerr << "Scoring # =\t" << i << "\n";	}	for (i = 8; i >= 0; i--)		std::cout << i << "\t" << poker_score << "\n";	t3 = time(NULL);	std::cerr << "Time to score all combinations (fast) 100 times =\t" << t3 - t2 << " seconds\n";	return;}void load_array(){	int i, count,c0,c1,c2,c3,c4,c5,c6,sc;	card deck[52],hand[7];	for (i = 0; i <= 51; i++)	{		deck.r = (int)(i / 4);		deck.s = i % 4;	}	count = 0;	for (c0 = 0; c0 <= 45; c0++)	{		hand[0].r = (int)(c0 / 4);		hand[0].s = c0 % 4;		for (c1 = c0+1; c1 <= 46; c1++)		{			hand[1].r = (int)(c1 / 4);			hand[1].s = c1 % 4;			for (c2 = c1 + 1; c2 <= 47; c2++)			{				hand[2].r = (int)(c2 / 4);				hand[2].s = c2 % 4;				for (c3 = c2 + 1; c3 <= 48; c3++)				{					hand[3].r = (int)(c3 / 4);					hand[3].s = c3 % 4;					for (c4 = c3 + 1; c4 <= 49; c4++)					{						hand[4].r = (int)(c4 / 4);						hand[4].s = c4 % 4;						for (c5 = c4 + 1; c5 <= 50; c5++)						{							hand[5].r = (int)(c5 / 4);							hand[5].s = c5 % 4;							for (c6 = c5 + 1; c6 <= 51; c6++)							{								hand[6].r = (int)(c6 / 4);								hand[6].s = c6 % 4;								sc = score7ex(hand);								score_array[count] = sc;								count++;								if (count % 1000000 == 0)									std::cerr << (double)count / 133784560.0 << "\n";							}						}					}				}			}		}	} }void score_fast(int poker_score[]){	int index,CardIndex[7], c0, c1, c2, c3, c4, c5, c6,sc,sc_ex;	for (c0 = 0; c0 <= 9; c0++)		poker_score[c0] = 0;	for (c0 = 0; c0 <= 45; c0++)	{		CardIndex[0] = c0;		for (c1 = c0 + 1; c1 <= 46; c1++)		{			CardIndex[1] = c1;			for (c2 = c1 + 1; c2 <= 47; c2++)			{				CardIndex[2] = c2;				for (c3 = c2 + 1; c3 <= 48; c3++)				{					CardIndex[3] = c3;					for (c4 = c3 + 1; c4 <= 49; c4++)					{						CardIndex[4] = c4;						for (c5 = c4 + 1; c5 <= 50; c5++)						{							CardIndex[5] = c5;							for (c6 = c5 + 1; c6 <= 51; c6++)							{								CardIndex[6] = c6;								index = HandIndex7(CardIndex);								sc_ex = score_array[index];								sc = (int)(sc_ex / 371293);								poker_score[sc]++;							}						}					}				}			}		}	}}int HandIndex7(int CardIndex[]){	int r;	r = combin_array[52][7] - combin_array[52 - CardIndex[0]][7];	r += combin_array[51 - CardIndex[0]][6] - combin_array[52 - CardIndex[1]][6];	r += combin_array[51 - CardIndex[1]][5] - combin_array[52 - CardIndex[2]][5];	r += combin_array[51 - CardIndex[2]][4] - combin_array[52 - CardIndex[3]][4];	r += combin_array[51 - CardIndex[3]][3] - combin_array[52 - CardIndex[4]][3];	r += combin_array[51 - CardIndex[4]][2] - combin_array[52 - CardIndex[5]][2];	r += CardIndex[6] - CardIndex[5] - 1;	return r;}int combin(int x, int y){	int i;	float r = 1;	for (i = x - y + 1; i <= x; i++)	{		r *= i;		r /= (i - x + y);	}	return (int)r;}void CombinArray(void){	int i, j;	for (i = 0; i <= 52; i++)	{		for (j = 0; j <= 7; j++)			combin_array = combin(i, j);	}}int score7ex(card t[]) // exact value of 7-card hand{	int straight = 0;	int flush = 0;	int i, r, s, pt, value[8], SuitTot, TotStr;	for (i = 0; i <= 7; i++)		value = 0;	if ((t[0].r == t[3].r) || (t[1].r == t[4].r) || (t[2].r == t[5].r))	{		value[0] = 7; // four of a kind 		value[1] = t[3].r;		value[2] = t[6].r;		return value[5] + 13 * value[4] + 169 * value[3] + 2197 * value[2] + 28561 * value[1] + 371293 * value[0];	}	else if (t[3].r == t[6].r)	{		value[0] = 7; // four of a kind 		value[1] = t[3].r;		value[2] = t[2].r;		return value[5] + 13 * value[4] + 169 * value[3] + 2197 * value[2] + 28561 * value[1] + 371293 * value[0];	}	else if (t[4].r == t[6].r)	{		if (t[2].r == t[3].r)		{			value[0] = 6; // full house 			value[1] = t[4].r;			value[2] = t[2].r;			return value[5] + 13 * value[4] + 169 * value[3] + 2197 * value[2] + 28561 * value[1] + 371293 * value[0];		}		else if (t[1].r == t[2].r)		{			value[0] = 6; // full house 			value[1] = t[4].r;			value[2] = t[1].r;			return value[5] + 13 * value[4] + 169 * value[3] + 2197 * value[2] + 28561 * value[1] + 371293 * value[0];		}		else if (t[0].r == t[1].r)		{			value[0] = 6; // full house 			value[1] = t[4].r;			value[2] = t[0].r;			return value[5] + 13 * value[4] + 169 * value[3] + 2197 * value[2] + 28561 * value[1] + 371293 * value[0];		}	}	else if (t[3].r == t[5].r)	{		if (t[1].r == t[2].r)		{			value[0] = 6; // full house 			value[1] = t[3].r;			value[2] = t[1].r;			return value[5] + 13 * value[4] + 169 * value[3] + 2197 * value[2] + 28561 * value[1] + 371293 * value[0];		}		else if (t[0].r == t[1].r)		{			value[0] = 6; // full house 			value[1] = t[3].r;			value[2] = t[0].r;			return value[5] + 13 * value[4] + 169 * value[3] + 2197 * value[2] + 28561 * value[1] + 371293 * value[0];		}	}	else if (t[2].r == t[4].r)	{		if (t[5].r == t[6].r)		{			value[0] = 6; // full house 			value[1] = t[2].r;			value[2] = t[5].r;			return value[5] + 13 * value[4] + 169 * value[3] + 2197 * value[2] + 28561 * value[1] + 371293 * value[0];		}		else if (t[0].r == t[1].r)		{			value[0] = 6; // full house 			value[1] = t[2].r;			value[2] = t[0].r;			return value[5] + 13 * value[4] + 169 * value[3] + 2197 * value[2] + 28561 * value[1] + 371293 * value[0];		}	}	else if (t[1].r == t[3].r)	{		if (t[5].r == t[6].r)		{			value[0] = 6; // full house 			value[1] = t[1].r;			value[2] = t[5].r;			return value[5] + 13 * value[4] + 169 * value[3] + 2197 * value[2] + 28561 * value[1] + 371293 * value[0];		}		else if (t[4].r == t[5].r)		{			value[0] = 6; // full house 			value[1] = t[1].r;			value[2] = t[4].r;			return value[5] + 13 * value[4] + 169 * value[3] + 2197 * value[2] + 28561 * value[1] + 371293 * value[0];		}	}	else if (t[0].r == t[2].r)	{		if (t[5].r == t[6].r)		{			value[0] = 6; // full house 			value[1] = t[0].r;			value[2] = t[5].r;			return value[5] + 13 * value[4] + 169 * value[3] + 2197 * value[2] + 28561 * value[1] + 371293 * value[0];		}		else if (t[4].r == t[5].r)		{			value[0] = 6; // full house 			value[1] = t[0].r;			value[2] = t[4].r;			return value[5] + 13 * value[4] + 169 * value[3] + 2197 * value[2] + 28561 * value[1] + 371293 * value[0];		}		else if (t[3].r == t[4].r)		{			value[0] = 6; // full house 			value[1] = t[0].r;			value[2] = t[3].r;			return value[5] + 13 * value[4] + 169 * value[3] + 2197 * value[2] + 28561 * value[1] + 371293 * value[0];		}	}	for (s = 0; s <= 3; s++)	{		SuitTot = (t[0].s == s ? 1 : 0) + (t[1].s == s ? 1 : 0) + (t[2].s == s ? 1 : 0) + (t[3].s == s ? 1 : 0) + (t[4].s == s ? 1 : 0) + (t[5].s == s ? 1 : 0) + (t[6].s == s ? 1 : 0);		if (SuitTot >= 5)		{			for (r = 8; r >= 0; r--)			{				TotStr = 0;				for (i = 0; i <= 4; i++)					TotStr += (t[0].r == r + i ? 1 : 0) * (t[0].s == s ? 1 : 0)					+ (t[1].r == r + i ? 1 : 0) * (t[1].s == s ? 1 : 0)					+ (t[2].r == r + i ? 1 : 0) * (t[2].s == s ? 1 : 0)					+ (t[3].r == r + i ? 1 : 0) * (t[3].s == s ? 1 : 0)					+ (t[4].r == r + i ? 1 : 0) * (t[4].s == s ? 1 : 0)					+ (t[5].r == r + i ? 1 : 0) * (t[5].s == s ? 1 : 0)					+ (t[6].r == r + i ? 1 : 0) * (t[6].s == s ? 1 : 0);				if (TotStr == 5) // consecutive straight				{					value[0] = 8;					value[1] = r + 4;					value[2] = r + 3;					value[3] = r + 2;					value[4] = r + 1;					value[5] = r;					return value[5] + 13 * value[4] + 169 * value[3] + 2197 * value[2] + 28561 * value[1] + 371293 * value[0];				}			}			TotStr = 0;			TotStr += (t[0].r == 12 ? 1 : 0) * (t[0].s == s ? 1 : 0) + (t[1].r == 12 ? 1 : 0) * (t[1].s == s ? 1 : 0) + (t[2].r == 12 ? 1 : 0) * (t[2].s == s ? 1 : 0) + (t[3].r == 12 ? 1 : 0) * (t[3].s == s ? 1 : 0) + (t[4].r == 12 ? 1 : 0) * (t[4].s == s ? 1 : 0) + (t[5].r == 12 ? 1 : 0) * (t[5].s == s ? 1 : 0) + (t[6].r == 12 ? 1 : 0) * (t[6].s == s ? 1 : 0);			TotStr += (t[0].r == 0 ? 1 : 0) * (t[0].s == s ? 1 : 0) + (t[1].r == 0 ? 1 : 0) * (t[1].s == s ? 1 : 0) + (t[2].r == 0 ? 1 : 0) * (t[2].s == s ? 1 : 0) + (t[3].r == 0 ? 1 : 0) * (t[3].s == s ? 1 : 0) + (t[4].r == 0 ? 1 : 0) * (t[4].s == s ? 1 : 0) + (t[5].r == 0 ? 1 : 0) * (t[5].s == s ? 1 : 0) + (t[6].r == 0 ? 1 : 0) * (t[6].s == s ? 1 : 0);			TotStr += (t[0].r == 1 ? 1 : 0) * (t[0].s == s ? 1 : 0) + (t[1].r == 1 ? 1 : 0) * (t[1].s == s ? 1 : 0) + (t[2].r == 1 ? 1 : 0) * (t[2].s == s ? 1 : 0) + (t[3].r == 1 ? 1 : 0) * (t[3].s == s ? 1 : 0) + (t[4].r == 1 ? 1 : 0) * (t[4].s == s ? 1 : 0) + (t[5].r == 1 ? 1 : 0) * (t[5].s == s ? 1 : 0) + (t[6].r == 1 ? 1 : 0) * (t[6].s == s ? 1 : 0);			TotStr += (t[0].r == 2 ? 1 : 0) * (t[0].s == s ? 1 : 0) + (t[1].r == 2 ? 1 : 0) * (t[1].s == s ? 1 : 0) + (t[2].r == 2 ? 1 : 0) * (t[2].s == s ? 1 : 0) + (t[3].r == 2 ? 1 : 0) * (t[3].s == s ? 1 : 0) + (t[4].r == 2 ? 1 : 0) * (t[4].s == s ? 1 : 0) + (t[5].r == 2 ? 1 : 0) * (t[5].s == s ? 1 : 0) + (t[6].r == 2 ? 1 : 0) * (t[6].s == s ? 1 : 0);			TotStr += (t[0].r == 3 ? 1 : 0) * (t[0].s == s ? 1 : 0) + (t[1].r == 3 ? 1 : 0) * (t[1].s == s ? 1 : 0) + (t[2].r == 3 ? 1 : 0) * (t[2].s == s ? 1 : 0) + (t[3].r == 3 ? 1 : 0) * (t[3].s == s ? 1 : 0) + (t[4].r == 3 ? 1 : 0) * (t[4].s == s ? 1 : 0) + (t[5].r == 3 ? 1 : 0) * (t[5].s == s ? 1 : 0) + (t[6].r == 3 ? 1 : 0) * (t[6].s == s ? 1 : 0);			if (TotStr == 5) // A2345 straight			{				value[0] = 8;				value[1] = 3;				value[2] = 2;				value[3] = 1;				value[4] = 0;				value[5] = -1;				return value[5] + 13 * value[4] + 169 * value[3] + 2197 * value[2] + 28561 * value[1] + 371293 * value[0];			}		}	}	for (s = 0; s <= 3; s++)	{		SuitTot = (t[0].s == s ? 1 : 0) + (t[1].s == s ? 1 : 0) + (t[2].s == s ? 1 : 0) + (t[3].s == s ? 1 : 0) + (t[4].s == s ? 1 : 0) + (t[5].s == s ? 1 : 0) + (t[6].s == s ? 1 : 0);		if (SuitTot >= 5)		{			value[0] = 5;			pt = 1;			for (i = 6; i >= 0; i--)			{				if (t.s == s)				{					value[pt] = t.r;					pt++;				}			}			return value[5] + 13 * value[4] + 169 * value[3] + 2197 * value[2] + 28561 * value[1] + 371293 * value[0];		}	}	for (r = 8; r >= 0; r--)	{		TotStr = 0;		for (i = 0; i <= 4; i++)			TotStr += (((t[0].r == r + i ? 1 : 0) + (t[1].r == r + i ? 1 : 0) + (t[2].r == r + i ? 1 : 0) + (t[3].r == r + i ? 1 : 0) + (t[4].r == r + i ? 1 : 0) + (t[5].r == r + i ? 1 : 0) + (t[6].r == r + i ? 1 : 0)) > 0 ? 1 : 0);		if (TotStr == 5) // consecutive straight		{			value[0] = 4;			value[1] = r + 4;			value[2] = r + 3;			value[3] = r + 2;			value[4] = r + 1;			value[5] = r;			return value[5] + 13 * value[4] + 169 * value[3] + 2197 * value[2] + 28561 * value[1] + 371293 * value[0];		}	}	TotStr = 0;	TotStr += (((t[0].r == 12 ? 1 : 0) + (t[1].r == 12 ? 1 : 0) + (t[2].r == 12 ? 1 : 0) + (t[3].r == 12 ? 1 : 0) + (t[4].r == 12 ? 1 : 0) + (t[5].r == 12 ? 1 : 0) + (t[6].r == 12 ? 1 : 0)) > 0 ? 1 : 0);	TotStr += (((t[0].r == 0 ? 1 : 0) + (t[1].r == 0 ? 1 : 0) + (t[2].r == 0 ? 1 : 0) + (t[3].r == 0 ? 1 : 0) + (t[4].r == 0 ? 1 : 0) + (t[5].r == 0 ? 1 : 0) + (t[6].r == 0 ? 1 : 0)) > 0 ? 1 : 0);	TotStr += (((t[0].r == 1 ? 1 : 0) + (t[1].r == 1 ? 1 : 0) + (t[2].r == 1 ? 1 : 0) + (t[3].r == 1 ? 1 : 0) + (t[4].r == 1 ? 1 : 0) + (t[5].r == 1 ? 1 : 0) + (t[6].r == 1 ? 1 : 0)) > 0 ? 1 : 0);	TotStr += (((t[0].r == 2 ? 1 : 0) + (t[1].r == 2 ? 1 : 0) + (t[2].r == 2 ? 1 : 0) + (t[3].r == 2 ? 1 : 0) + (t[4].r == 2 ? 1 : 0) + (t[5].r == 2 ? 1 : 0) + (t[6].r == 2 ? 1 : 0)) > 0 ? 1 : 0);	TotStr += (((t[0].r == 3 ? 1 : 0) + (t[1].r == 3 ? 1 : 0) + (t[2].r == 3 ? 1 : 0) + (t[3].r == 3 ? 1 : 0) + (t[4].r == 3 ? 1 : 0) + (t[5].r == 3 ? 1 : 0) + (t[6].r == 3 ? 1 : 0)) > 0 ? 1 : 0);	if (TotStr == 5) // A2345 straight	{		value[0] = 4;		value[1] = 3;		value[2] = 2;		value[3] = 1;		value[4] = 0;		value[5] = -1;		return value[5] + 13 * value[4] + 169 * value[3] + 2197 * value[2] + 28561 * value[1] + 371293 * value[0];	}	if (t[4].r == t[6].r)	{		value[0] = 3; // three of a kind		value[1] = t[4].r;		value[2] = t[3].r;		value[3] = t[2].r;		return value[5] + 13 * value[4] + 169 * value[3] + 2197 * value[2] + 28561 * value[1] + 371293 * value[0];	}	else if (t[3].r == t[5].r)	{		value[0] = 3; // three of a kind		value[1] = t[3].r;		value[2] = t[6].r;		value[3] = t[2].r;		return value[5] + 13 * value[4] + 169 * value[3] + 2197 * value[2] + 28561 * value[1] + 371293 * value[0];	}	else if (t[2].r == t[4].r)	{		value[0] = 3; // three of a kind		value[1] = t[2].r;		value[2] = t[6].r;		value[3] = t[5].r;		return value[5] + 13 * value[4] + 169 * value[3] + 2197 * value[2] + 28561 * value[1] + 371293 * value[0];	}	else if (t[1].r == t[3].r)	{		value[0] = 3; // three of a kind		value[1] = t[1].r;		value[2] = t[6].r;		value[3] = t[5].r;		return value[5] + 13 * value[4] + 169 * value[3] + 2197 * value[2] + 28561 * value[1] + 371293 * value[0];	}	else if (t[0].r == t[2].r)	{		value[0] = 3; // three of a kind		value[1] = t[0].r;		value[2] = t[6].r;		value[3] = t[5].r;		return value[5] + 13 * value[4] + 169 * value[3] + 2197 * value[2] + 28561 * value[1] + 371293 * value[0];	}	if (t[5].r == t[6].r)	{		if (t[3].r == t[4].r)		{			value[0] = 2; // two pair			value[1] = t[5].r;			value[2] = t[3].r;			value[3] = t[2].r;			return value[5] + 13 * value[4] + 169 * value[3] + 2197 * value[2] + 28561 * value[1] + 371293 * value[0];		}		else if (t[2].r == t[3].r)		{			value[0] = 2; // two pair			value[1] = t[5].r;			value[2] = t[2].r;			value[3] = t[4].r;			return value[5] + 13 * value[4] + 169 * value[3] + 2197 * value[2] + 28561 * value[1] + 371293 * value[0];		}		if (t[1].r == t[2].r)		{			value[0] = 2; // two pair			value[1] = t[5].r;			value[2] = t[1].r;			value[3] = t[4].r;			return value[5] + 13 * value[4] + 169 * value[3] + 2197 * value[2] + 28561 * value[1] + 371293 * value[0];		}		if (t[0].r == t[1].r)		{			value[0] = 2; // two pair			value[1] = t[5].r;			value[2] = t[0].r;			value[3] = t[4].r;			return value[5] + 13 * value[4] + 169 * value[3] + 2197 * value[2] + 28561 * value[1] + 371293 * value[0];		}	}	if (t[4].r == t[5].r)	{		if (t[2].r == t[3].r)		{			value[0] = 2; // two pair			value[1] = t[4].r;			value[2] = t[2].r;			value[3] = t[6].r;			return value[5] + 13 * value[4] + 169 * value[3] + 2197 * value[2] + 28561 * value[1] + 371293 * value[0];		}		else if (t[1].r == t[2].r)		{			value[0] = 2; // two pair			value[1] = t[4].r;			value[2] = t[1].r;			value[3] = t[6].r;			return value[5] + 13 * value[4] + 169 * value[3] + 2197 * value[2] + 28561 * value[1] + 371293 * value[0];		}		else if (t[0].r == t[1].r)		{			value[0] = 2; // two pair			value[1] = t[4].r;			value[2] = t[0].r;			value[3] = t[6].r;			return value[5] + 13 * value[4] + 169 * value[3] + 2197 * value[2] + 28561 * value[1] + 371293 * value[0];		}	}	if (t[3].r == t[4].r)	{		if (t[1].r == t[2].r)		{			value[0] = 2; // two pair			value[1] = t[3].r;			value[2] = t[1].r;			value[3] = t[6].r;			return value[5] + 13 * value[4] + 169 * value[3] + 2197 * value[2] + 28561 * value[1] + 371293 * value[0];		}		else if (t[0].r == t[1].r)		{			value[0] = 2; // two pair			value[1] = t[3].r;			value[2] = t[0].r;			value[3] = t[6].r;			return value[5] + 13 * value[4] + 169 * value[3] + 2197 * value[2] + 28561 * value[1] + 371293 * value[0];		}	}	if (t[2].r == t[3].r)	{		if (t[0].r == t[1].r)		{			value[0] = 2; // two pair			value[1] = t[2].r;			value[2] = t[0].r;			value[3] = t[6].r;			return value[5] + 13 * value[4] + 169 * value[3] + 2197 * value[2] + 28561 * value[1] + 371293 * value[0];		}	}	if (t[5].r == t[6].r)	{		value[0] = 1;		value[1] = t[5].r;		value[2] = t[4].r;		value[3] = t[3].r;		value[4] = t[2].r;		return value[5] + 13 * value[4] + 169 * value[3] + 2197 * value[2] + 28561 * value[1] + 371293 * value[0];	}	else if (t[4].r == t[5].r)	{		value[0] = 1;		value[1] = t[4].r;		value[2] = t[6].r;		value[3] = t[3].r;		value[4] = t[2].r;		return value[5] + 13 * value[4] + 169 * value[3] + 2197 * value[2] + 28561 * value[1] + 371293 * value[0];	}	else if (t[3].r == t[4].r)	{		value[0] = 1;		value[1] = t[3].r;		value[2] = t[6].r;		value[3] = t[5].r;		value[4] = t[2].r;		return value[5] + 13 * value[4] + 169 * value[3] + 2197 * value[2] + 28561 * value[1] + 371293 * value[0];	}	else if (t[2].r == t[3].r)	{		value[0] = 1;		value[1] = t[2].r;		value[2] = t[6].r;		value[3] = t[5].r;		value[4] = t[4].r;		return value[5] + 13 * value[4] + 169 * value[3] + 2197 * value[2] + 28561 * value[1] + 371293 * value[0];	}	else if (t[1].r == t[2].r)	{		value[0] = 1;		value[1] = t[1].r;		value[2] = t[6].r;		value[3] = t[5].r;		value[4] = t[4].r;		return value[5] + 13 * value[4] + 169 * value[3] + 2197 * value[2] + 28561 * value[1] + 371293 * value[0];	}	else if (t[0].r == t[1].r)	{		value[0] = 1;		value[1] = t[0].r;		value[2] = t[6].r;		value[3] = t[5].r;		value[4] = t[4].r;		return value[5] + 13 * value[4] + 169 * value[3] + 2197 * value[2] + 28561 * value[1] + 371293 * value[0];	}	value[0] = 0;	value[1] = t[6].r;	value[2] = t[5].r;	value[3] = t[4].r;	value[4] = t[3].r;	value[2] = t[2].r;	return value[5] + 13 * value[4] + 169 * value[3] + 2197 * value[2] + 28561 * value[1] + 371293 * value[0];}`

I know Mental uses a hash algorithm, which I quickly failed at implementing. I'm happy to hear more about that and all other ideas for analyzing games like UTH in a matter of hours as opposed to days.

I think your HandIndex7() method would qualify as a perfect hash function. It takes seven 6-bit card indices (42 bits of information) and maps it uniquely to a 27-bit number, 0-134M, as I understand it. Paul's perfect hash function maps a 52-bit representation of seven cards to the same 27-bit range. Congratulations on developing this solution.

I recall that this is the same technique you described 20 years ago for indexing 5-card video poker hands. I had created my own solution for the same VP problem that used a four dimensional array. When I compared my indices to your indices, they were identical for every hand. So I believe your technique is equivalent to taking a sparse array of dimension N-1 and calculating the indexes of the contiguous populated segments of the array. I had compared the speed of your hash to mine for the 5-card problem years ago. I concluded that my 4-dimensional array was faster, but your algorithm did not require a large array. My 4-dimensional array was small enough that I could keep it in RAM on a home computer 20 years ago. The 6-dimensional array that I would need for the 7-card problem would be a problem even for a modern home computer. Thus I knew I that needed to find a hash function that consumed less memory. I would be interest to see how fast your hash is compared to Paul Senzee's hash.

I am guessing that your score7ex() method returns 7462 distinct values that can be used directly to see which hand ranks higher. Is that right?

I suspect that you could send your compiler a flag to allocate more memory and this would have allowed you to compile a 134M array. My gnu compiler won't allow me to allocate arrays much larger than 134M 16-bit numbers without requesting more memory.
Gambling is a math contest where the score is tracked in dollars. Try not to get a negative score.
Mental
• Posts: 1508
Joined: Dec 10, 2018
March 20th, 2024 at 6:01:47 PM permalink
Quote: Wizard

Bottom line is my program takes 56 seconds to populate the initial array of all possible 7-card hands out of 52.

After that, it takes 3.41 seconds to go through all 133,784,560 possible combinations of 7 cards out of 52, map each set to an integer, and get the poker value from the array given the integer mapping.

For a program like UTH, this should speed up the time by about 93%.

The full code is below.

Is this C# code? I was able to convert your code to C++ and run it on my MacBook.

Time to populate score array = 11 seconds
It took 46 seconds to score all combinations 100 times. It seems like my hardware runs this particular algorithm a lot faster than your computer.

My MacBook is about three times faster than my Dell Pavillion desktop computer. It also has 8 processors and can handle five simultaneous instances of my UTH program, whereas my desktop gets bogged down running three instances. I was surprised to see how fast the MacBook was compared to a desktop computer.

So, some of my speed advantage is just hardware. I am using the GNU gcc compiler with -O2 optimization.
Gambling is a math contest where the score is tracked in dollars. Try not to get a negative score.
Wizard
• Posts: 26842
Joined: Oct 14, 2009
March 21st, 2024 at 8:55:46 AM permalink
Quote: Mental

Quote:

I know Mental uses a hash algorithm, which I quickly failed at implementing. I'm happy to hear more about that and all other ideas for analyzing games like UTH in a matter of hours as opposed to days.

I think your HandIndex7() method would qualify as a perfect hash function. It takes seven 6-bit card indices (42 bits of information) and maps it uniquely to a 27-bit number, 0-134M, as I understand it. Paul's perfect hash function maps a 52-bit representation of seven cards to the same 27-bit range. Congratulations on developing this solution.

I recall that this is the same technique you described 20 years ago for indexing 5-card video poker hands. I had created my own solution for the same VP problem that used a four dimensional array. When I compared my indices to your indices, they were identical for every hand. So I believe your technique is equivalent to taking a sparse array of dimension N-1 and calculating the indexes of the contiguous populated segments of the array. I had compared the speed of your hash to mine for the 5-card problem years ago. I concluded that my 4-dimensional array was faster, but your algorithm did not require a large array. My 4-dimensional array was small enough that I could keep it in RAM on a home computer 20 years ago. The 6-dimensional array that I would need for the 7-card problem would be a problem even for a modern home computer. Thus I knew I that needed to find a hash function that consumed less memory. I would be interest to see how fast your hash is compared to Paul Senzee's hash.

I am guessing that your score7ex() method returns 7462 distinct values that can be used directly to see which hand ranks higher. Is that right?

I suspect that you could send your compiler a flag to allocate more memory and this would have allowed you to compile a 134M array. My gnu compiler won't allow me to allocate arrays much larger than 134M 16-bit numbers without requesting more memory.

Thank you for all the kind words and valuable comments.

Yes, score7ex calculates the exact value of the poker hand. So it could be used to compare to hands to see which was higher, down to the 5th card in cases of trash or a flush.

Yes, this is included in my method in my video poker program. It helped get the running time from about 40 minutes to about one second.

My UTH program declares a 7-dimension array for the poker value of 7 cards, assuming no flush is possible. There is a separate 7-dimensional array for cases of suited cards. I think it respected a dummy value in cases where 5 or 6 cares were suited, for the non-suited one. If a flush was possible, it went with the higher of the two possible ways to score the hand -- without looking at the suits and looking only at the suited cards. It got the program to run in an acceptable period of time, I think a few days.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
Wizard
• Posts: 26842
Joined: Oct 14, 2009
March 21st, 2024 at 12:50:31 PM permalink
Quote: Mental

Is this C# code? I was able to convert your code to C++ and run it on my MacBook.

Time to populate score array = 11 seconds
It took 46 seconds to score all combinations 100 times. It seems like my hardware runs this particular algorithm a lot faster than your computer.

My MacBook is about three times faster than my Dell Pavillion desktop computer. It also has 8 processors and can handle five simultaneous instances of my UTH program, whereas my desktop gets bogged down running three instances. I was surprised to see how fast the MacBook was compared to a desktop computer.

So, some of my speed advantage is just hardware. I am using the GNU gcc compiler with -O2 optimization.

My code is C++.

Wow, your MacBook is about 70% faster than my new Dell desktop.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
Mental
• Posts: 1508
Joined: Dec 10, 2018
Thanked by
March 21st, 2024 at 2:17:38 PM permalink
Quote: Wizard

Quote: Mental

Is this C# code? I was able to convert your code to C++ and run it on my MacBook.

Time to populate score array = 11 seconds
It took 46 seconds to score all combinations 100 times. It seems like my hardware runs this particular algorithm a lot faster than your computer.

My MacBook is about three times faster than my Dell Pavillion desktop computer. It also has 8 processors and can handle five simultaneous instances of my UTH program, whereas my desktop gets bogged down running three instances. I was surprised to see how fast the MacBook was compared to a desktop computer.

So, some of my speed advantage is just hardware. I am using the GNU gcc compiler with -O2 optimization.

My code is C++.

Wow, your MacBook is about 70% faster than my new Dell desktop.

The MacBook was a online casino gift. I have received three other casino laptops and they were all discontinued garbage. I was really shocked at how good this one was. I received a much better computer from a different online casino recently, but it is still in the box. It seems to retail for \$2500 and is specialized for gaming/graphics. Maybe I should see what it can do.

I put Wizard's hash algorithm into my test loop. It is fast and it is a perfect hash. Every 7-card hand maps on to a unique index, and these indices run consecutively from 0 to 133784560, which ideal for this type of hash.

For those who are not familiar with hashing, often you are looking to hash a very large number of bits to a small number of bits that can be used for an array index. For supercomputers, this can be a large number of bits, but for a PC, you want to hash to less than 30 bits. It is impossible to stuff 200 bits of information into 30 bits. What happens is that multiple input numbers hash to the same number. The hash table needs to store information about multiple input number and resolve these hash collisions. This is messy and slows things down.

Since the 7-card problem is only trying to compress the hand representation by a small factor, it is possible to get a perfect hash with no collisions to resolve. Both of our hash functions are perfect and hash down to 27 bits.
Gambling is a math contest where the score is tracked in dollars. Try not to get a negative score.
Mental
• Posts: 1508
Joined: Dec 10, 2018
Thanked by
March 21st, 2024 at 8:56:29 PM permalink
I was unable to get your hash to run 100% correctly on my MacBook. Only 10 of the 133,784,560 hash indices were wrong. I tracked the problem down to this function.
`int combin(int x, int y){	int i;	float r = 1;	for (i = x - y + 1; i <= x; i++)	{		r *= i;		r /= (i - x + y);	}	return (int)r;}`
If you use a float for variable r here, the cast to an integer will sometimes give the wrong answer because it is rounding down. For example, r= 1.999999999 becomes 1 due to rounding, so the cast does not give you the integer 2 you were expecting. This error depends on the exact architecture of the math processor. Your hash worked perfectly on my Dell but not on my Mac. I just changed the variable r to an int and the problems went away. There is no need to use a float here.

I also found a way to simplify your HandIndex7(CardIndex) so that it runs 60% faster on the Dell desktop computer. When I compared the two algorithms on the Mac, the results were exactly the opposite. I can index all 133,784,560 hands in 88 milliseconds using your original function, while my improvement takes 192 milliseconds. I believe the compiler is able to optimize your hash algorithm much more effectively than my hash algorithm for the Mac architecture.

Your hash function is amazingly fast on my MacBook Pro, which is where I run all the computationally intensive calculations. I am going to try and integrate your hash function into my UTH and Casino Holdem programs.

Great stuff! I hope you are making progress integrating your hash index into your poker programs.
Gambling is a math contest where the score is tracked in dollars. Try not to get a negative score.
Mental
• Posts: 1508
Joined: Dec 10, 2018
Thanked by
March 23rd, 2024 at 12:47:19 PM permalink
I have been using a set of lookup functions to index poker hands with 2-5 cards. I created these functions 25 years ago. These functions take an ordered set of card indices, 0-51, and return a unique hash index for that hand. I provide full working code below in the spoilers. The main() function just creates a Lookup class instance and calls the test function. This test function creates all possible hands with 2-5 cards and tests to make sure that every combination of cards hashes to a unique index. The test() function returns zero if the test passes.

`#ifndef Lookup_H_#define Lookup_H_class Lookup {  static int start2[51];  static int start3[50][51];  static int start4[49][50][51];  static int start5[48][49][50][51];  static unsigned char unique[];  static const int nUnique[];public:  Lookup();  ~Lookup() {}  void setup(int v);  int test(int v);  int key1(int * sort);  int key2(int * sort);  int key3(int * sort);  int key4(int * sort);  int key5(int * sort);  static const int NDECK;};#endif /*Lookup_H_*/`

`#include <stdio.h>#include <cstdio>#include "Lookup.h"int main(){  Lookup lu;  lu.test(1);}const int Lookup::NDECK = 52;int Lookup::start2[51];int Lookup::start3[50][51];int Lookup::start4[49][50][51];int Lookup::start5[48][49][50][51];unsigned char Lookup::unique[2598960];const int Lookup::nUnique[6] = { 1, 52, 1326, 22100, 270725, 2598960 };Lookup::Lookup(){  setup(0);}void Lookup::setup(int v){  int i0, i1, i2, i3, i4, j;  // create start index arrays  for (j = 0, i0 = 0; i0 < NDECK - 1; i0++) {    int start = start2[i0] = j - i0 - 1;    if (v) printf("%2d  %5d  --> %5d\n", i0, start, j);    for (i1 = i0 + 1; i1 < NDECK; i1++, j++) { }  }  for (j = 0, i0= 0; i0 < NDECK - 2; i0++) {    for (i1 = i0 + 1; i1 < NDECK - 1; i1++) {      int start = start3[i0][i1] = j - i1 - 1;      if (v) printf("%2d %2d  %5d  --> %5d\n", i0, i1, start, j);      for (i2 = i1 + 1; i2 < NDECK; i2++, j++) { }    }  }  for (j = 0, i0 = 0; i0 < NDECK - 3; i0++) {    for (i1 = i0 + 1; i1 < NDECK - 2; i1++) {      for (i2 = i1 + 1; i2 < NDECK - 1; i2++) {        int start = start4[i0][i1][i2] = j - i2 - 1;        if (v) printf("%2d %2d %2d  %5d  --> %5d\n", i0,  i1, i2, start, j);        for (i3 = i2 + 1; i3 < NDECK; i3++, j++) { }      }    }  }  for (j = 0, i0 = 0; i0 < NDECK - 4; i0++) {    for (i1 = i0 + 1; i1 < NDECK - 3; i1++) {      for (i2 = i1 + 1; i2 < NDECK - 2; i2++) {        for (i3 = i2 + 1; i3 < NDECK - 1; i3++) {          int start = start5[i0][i1][i2][i3] = j - i3 - 1;          if (v) printf("%2d %2d %2d %2d  %5d  --> %5d\n"            , i0, i1, i2, i3, start, j);          for (i4 = i3 + 1; i4 < NDECK; i4++, j++) { }        }      }    }  }}int Lookup::test(int v){  printf("Lookup::test(%d)\n", v);  int i0, i1, i2, i3, i4, j, k;  int sort[7];  for (k = 0; k < nUnique[5]; k++) unique[k] = 0;  printf("Lookup::test(%d)\n", v);  // test start index arrays  for (i0 = 0; i0 < NDECK - 1; i0++) {    sort[0] = i0;    for (i1 = i0 + 1; i1 < NDECK; i1++, j++) {      sort[1] = i1;      int k = key2(sort);      unique[k]++;      if (v) printf("%2d (%2d +%5d) = %5d\n", i0, i1, start2[i0], k);    }  }  for (k = 0; k < nUnique[2]; k++) {    if (unique[k] != 1) {      if (v) printf("%2d != 1 at position %d\n", int(unique[k]), k);      return 1;    }    unique[k] = 0;  }  for (i0= 0; i0 < NDECK - 2; i0++) {    sort[0] = i0;    for (i1 = i0+1; i1 < NDECK - 1; i1++) {      sort[1] = i1;      for (i2 = i1 + 1; i2 < NDECK; i2++) {        sort[2] = i2;        int k = key3(sort);        unique[k]++;        if (v) printf("%d %2d (%2d +%5d) = %5d\n"          , i0, i1, i2, start3[i0][i1], k);      }    }  }  for (k = 0; k < nUnique[3]; k++) {    if (unique[k] != 1) {      if (v) printf("%2d != 1 at position %d\n", int(unique[k]), k);      return 1;    }    unique[k] = 0;  }  for (i0 = 0; i0 < NDECK - 2; i0++) {    sort[0] = i0;    for (i1 = i0 + 1; i1 < NDECK - 2; i1++) {      sort[1] = i1;      for (i2 = i1+1; i2 < NDECK - 1; i2++) {        sort[2] = i2;        for (i3 = i2 + 1; i3 < NDECK; i3++) {          sort[3] = i3;          int k = key4(sort);          unique[k]++;          if (v) printf("%d %d %2d (%2d +%5d) = %5d\n"            , i0, i1, i2, i3, start4[i0][i1][i2], k);        }      }    }  }  for (k = 0; k < nUnique[4]; k++) {    if (unique[k] != 1) {      if (v) printf("%2d != 1 at position %d\n", int(unique[k]), k);      return 1;    }    unique[k] = 0;  }  for (i0 = 0; i0 < NDECK - 2; i0++) {    sort[0] = i0;    for (i1 = i0 + 1; i1 < NDECK - 2; i1++) {      sort[1] = i1;      for (i2 = i1+1; i2 < NDECK - 1; i2++) {        sort[2] = i2;        for (i3 = i2 + 1; i3 < NDECK; i3++) {          sort[3] = i3;          for (i4 = i3 + 1; i4 < NDECK; i4++, j++) {            sort[4] = i4;            int k = key5(sort);            unique[k]++;            if (v) printf("%d %d %d %2d (%2d +%5d) = %5d\n"              , i0, i1, i2, i3, i4, start5[i0][i1][i2][i3], k);          }        }      }    }  }  for (k = 0; k < nUnique[5]; k++) {    if (unique[k] != 1) {      if (v) printf("%2d != 1 at position %d\n", int(unique[k]), k);      return 1;      unique[k] = 0;  }  return 0;}int Lookup::key2(int * sort){  return start2[sort[0]] + sort[1];}int Lookup::key5(int * sort){  return start5[sort[0]][sort[1]][sort[2]][sort[3]] + sort[4];}int Lookup::key4(int * sort){  return start4[sort[0]][sort[1]][sort[2]] + sort[3];}int Lookup::key3(int * sort){  return start3[sort[0]][sort[1]] + sort[2];}`

Each lookup function for N cards uses an N-1 dimensional array to store the starting hash index for the first N-1 cards. The index of the Nth card is added to this start value to get the final hash index.

Rather than storing the starting index in a N-1 dimensional array, you could calculate the starting index each time you want to index a hand. I believe this is exactly what Wizard is doing with his int HandIndex7(int CardIndex[]) method. Wizard had published a version of this for 5 card indexing many years ago. I have never worked out the math for finding the indices this way. I trust that Wizard got it right because his HandIndex7 does a perfect job of indexing 7-card hands.

I tested the two methods a long time ago. I found that my array lookup was about 50% faster, but I needed to keep a very large array in memory. If you tried to run this on an old computer where memory was very limited, swapping would slow my method down and potentially make it perform worse than the Wizard method. I use an array of a size 48*49*50*51*4 = 24 megabytes. This is absolutely not a problem on a modern computer. However, extending this lookup method to 7-card indexing would require a 6D array of size 46*47*48*49*50*51*4 = 51Gbytes. This is not practical at all.

It is important to note that both our methods require the card indices to be ordered (for example, 4,7,11,22,28,33,45). If you try putting an unordered array (for example, 33,22,45,4,7,28,11) into the index functions they will fail (and possibly crash the program with a memory violation). For five-card indexing, both methods produced the same index for the same input hand. This shows that Wizards method is mathematically equivalent to calculating the starting points for each segment of nested loop iterating through all possible hands. I hope Wizard will explain how he arrived at his formula.

Paul Senzee's hash function uses a 52-bit integer to represent a hand. If there is a 1 in the Kth bit position, then the card with index K is present in the hand. There is clearly no need to sort any cards by index order before using his hash method. His method will crash if there are not exactly 7 bits set to 1 in the hand. I do not know how Paul's hash works.

I believe it is much faster to work with bitwise representations of all hands. In my code, b2 represents the two hole cards, b5 represents the flop cards, and b7 represents the turn/river cards. The player hand is obtained by bitwise 'OR' operation (pHand = b2|b5|b7). If b9 represents the dealers cards, his hand is dHand = b2|b5|b9. My analysis program depends on these very fast bitwise operations to speed up my inner program loop.

If I want to use Wizard's new hash function, then I need to convert the bitwise representation of the hand to an ordered integer array. It is simple to do this by bit shifting the hand 52 times, reading each bit with an 'AND' operation, and assigning a card if the bit is a 1. However, this would be very slow. I have some ideas of how to do this in a lot fewer than 52 iterations. I will need to do some tests to see what method is fastest.

Testing the speed of an algorithm is tricky. An algorithm that test out faster on an Intel 4-core processor might turn out to be slower on a MacBook Air processor (Apple M3 chip 8-core CPU). I will test on both computers.
Gambling is a math contest where the score is tracked in dollars. Try not to get a negative score.
gordonm888
• Posts: 5268
Joined: Feb 18, 2015
Thanked by
March 24th, 2024 at 10:31:02 AM permalink
Mental, you are a superstar; sort of a nerd rockstar! Thank you for your posts. I am not commenting because I don't have anything to add, but I am reading, following and learning (and learning is enjoyment). Just want you to know that what you are doing and posting is very much appreciated by me and many others.
So many better men, a few of them friends, are dead. And a thousand thousand slimy things live on, and so do I.
Mental
• Posts: 1508
Joined: Dec 10, 2018
Thanked by
March 24th, 2024 at 4:53:25 PM permalink
Quote: gordonm888

Mental, you are a superstar; sort of a nerd rockstar! Thank you for your posts. I am not commenting because I don't have anything to add, but I am reading, following and learning (and learning is enjoyment). Just want you to know that what you are doing and posting is very much appreciated by me and many others.

Thanks. I am glad there are people here who enjoy what I am doing and writing. I like to think about problems like this while I am exercising. I do my best thinking when the blood is flowing. I feel compelled to try my new ideas out in a concrete form when I get home. I would do it even if I didn't have a knowledgeable audience. However, I spend so much time writing up my nerdy experiments that I am glad someone is reading them.

I made some major progress on the indexing problem for unordered cards today. I also sped up the Wizards perfect hash function. Stay tuned.
Gambling is a math contest where the score is tracked in dollars. Try not to get a negative score.
Wizard
• Posts: 26842
Joined: Oct 14, 2009
March 25th, 2024 at 1:01:50 AM permalink
`int combin(int x, int y){	int i;	float r = 1;	for (i = x - y + 1; i <= x; i++)	{		r *= i;		r /= (i - x + y);	}	return (int)r;}`

Quote: Mental

I was unable to get your hash to run 100% correctly on my MacBook. Only 10 of the 133,784,560 hash indices were wrong. I tracked the problem down to this function.If you use a float for variable r here, the cast to an integer will sometimes give the wrong answer because it is rounding down. For example, r= 1.999999999 becomes 1 due to rounding, so the cast does not give you the integer 2 you were expecting. This error depends on the exact architecture of the math processor. Your hash worked perfectly on my Dell but not on my Mac. I just changed the variable r to an int and the problems went away. There is no need to use a float here.

That is good, thank you!

Quote:

I also found a way to simplify your HandIndex7(CardIndex) so that it runs 60% faster on the Dell desktop computer.

Can you expand on that?
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
Mental
• Posts: 1508
Joined: Dec 10, 2018
March 25th, 2024 at 6:26:37 AM permalink
Quote: Wizard

Quote:

I also found a way to simplify your HandIndex7(CardIndex) so that it runs 60% faster on the Dell desktop computer.

Can you expand on that?

I did not improve your algorithm. I just precomputed some arrays to reduce the number of math an dereferencing operations inside the HandIndex7() method. I pulled your method into my UTH/Casino Holdem program to do this optimization. If I have time later, I can integrate the changes back into your program. The code below will look a lot different than you code, but you might be able to follow along.

The first thing I did was shorten the names of your variables and align the code to see the underlying structure of your algorithm better. I also made it a member of a class Chem (Casino Holdem).
`int Chem::index7(int * cards){  int r;  r = choose[52][7]             - choose[52 - cards[0]][7];  r += choose[51 - cards[0]][6] - choose[52 - cards[1]][6];  r += choose[51 - cards[1]][5] - choose[52 - cards[2]][5];  r += choose[51 - cards[2]][4] - choose[52 - cards[3]][4];  r += choose[51 - cards[3]][3] - choose[52 - cards[4]][3];  r += choose[51 - cards[4]][2] - choose[52 - cards[5]][2];  r += cards[6] - cards[5] - 1;  return r;}`
This is functionally identical to your algorithm. The first thing I noticed was that none of the expressions depend on two different cards. This means I can precompute each term. In particular, I no longer calculate things like [52 - cards[0]] inside the function.
`// precomputed arrays for use in Mike's hash function  for (int i = 0; i < 52; i++) {    ch52_7 = choose[52 - i][7];    ch52_6 = choose[52 - i][6];    ch52_5 = choose[52 - i][5];    ch52_4 = choose[52 - i][4];    ch52_3 = choose[52 - i][3];    ch52_2 = choose[52 - i][2];    ch51_6 = choose[51 - i][6];    ch51_5 = choose[51 - i][5];    ch51_4 = choose[51 - i][4];    ch51_3 = choose[51 - i][3];    ch51_2 = choose[51 - i][2];  }int Chem::fast7(int * cards){  int r;  r = choose[52][7]     - ch52_7[cards[0]];  r += ch51_6[cards[0]] - ch52_6[cards[1]];  r += ch51_5[cards[1]] - ch52_5[cards[2]];  r += ch51_4[cards[2]] - ch52_4[cards[3]];  r += ch51_3[cards[3]] - ch52_3[cards[4]];  r += ch51_2[cards[4]] - ch52_2[cards[5]];  r += cards[6]         - cards[5] - 1;  return r;}`
Then, I combined all of the terms that referenced the same card into one array, sumJK[]. I also combined the constants choose[52][7] and -1 into one constant term.
` choose52_7 = choose[52][7] - 1; for (int i = 0; i < 52; i++) {    sum67[\i] = ch51_6 - ch52_7; // I have to put a backslashes here to prevent [\i] from coding for italics    sum56[\i] = ch51_5 - ch52_6;    sum45[\i] = ch51_4 - ch52_5;    sum34[\i] = ch51_3 - ch52_4;    sum23[\i] = ch51_2 - ch52_3;  }int Chem::faster7(int * cards){  int r = choose52_7;  r += sum67[cards[0]];  r += sum56[cards[1]];  r += sum45[cards[2]];  r += sum34[cards[3]];  r += sum23[cards[4]];  r -= ch52_2[cards[5]];  r += cards[6];  r -= cards[5];  return r;}`
Note that faster7(int * cards) is equivalent to faster7(int cards[7]), but I prefer pointer notation for arguments.

I have a test loop that creates all 133,784,560 unique 7-card hands in 52-bit representation and int cards[7] representation. The cards in the int cards[7] representation are already sorted based on the way the loop is structured. This means I do not need to do an expensive sort() operation in these tests. (I will address sorting in another post.)

Here are my timing results on my Dell desktop. The basic loop takes 18 msec to create 133,784,560 unique 7-card hands and simply count them.

10,400 msec: index52c7(uint64_t b7) the Senzee hash using the 52-bit representation
940 msec: index7(int * cards), the equivalent to the Wizard hash method
680 msec: fast7(int * cards), my intermediate improvement of the Wizard hash method
180 msec: faster7(int * cards), my final improvement of the Wizard hash method

In every test, I am checking to make sure the result is a perfect hash. All four methods pass this test.

However, testing on the Dell makes Wizard's original hash look much worse than it really is. If I repeat these tests on the MacBook Air, my algorithmic improvements barely make a difference. The optimizing compiler on the MacBook apparently figures out on its own how to precompute the values that I precomputed and avoids many unnecessary math operations. It is also possible that it is able to pipeline the code to do multiple operations in parallel. Whatever it is doing, it really speeds all versions up by a big factor.

2,800 msec: index52c7(uint64_t b7) the Senzee hash using the 52-bit representation
70 msec: index7(int * cards), the equivalent to the Wizard hash method
56 msec: faster7(int * cards), my final improvement of the Wizard hash method

All these versions of Wizard's hash are much faster than Paul's hash, but Paul's hash does not need the cards to be sorted in index order. This is a show stopper if your cards are not already sorted. The std::sort algorithm is very slow compared to these index functions. Paul's hash will still outperform Wizard's hash if you start with unsorted cards unless you can sort seven cards very efficiently.
Gambling is a math contest where the score is tracked in dollars. Try not to get a negative score.
Mental
• Posts: 1508
Joined: Dec 10, 2018
Thanked by
March 28th, 2024 at 1:34:04 PM permalink
Quote: Wizard

The recent discussion about face up cards in Ultimate Texas Hold 'em (UTH) touched on the topic of fast ways of scoring 7-card hands.
[SNIP]
I know Mental uses a hash algorithm, which I quickly failed at implementing. I'm happy to hear more about that and all other ideas for analyzing games like UTH in a matter of hours as opposed to days.

I was able to use the Paul Senzee hash right out of the box without problems. However, when I tried to integrate it into Wizard's program, it kept crashing. Mike had problems, too. I wasted a lot of time trying to see if there was some strange interaction will Wizard's code but I was unable to identify any specific problem. Yesterday, Paul's code started crashing within my own UTH program when I was making some changes elsewhere in the program.

It is possible that the Senzee code has some memory access errors that have gone undetected under most conditions. I have decided to abandon the Senzee hash. I know that Mike already gave up on it. I hate working with opaque code that I don't fully understand and that might have have internal errors. Also, I have found a way to sort seven cards that is faster than any general sort algorithm (sorting seven cards is not a general sorting problem). So I don't gain anything by using the Senzee code.

The Wizard's perfect hash function is very fast, but it needs the seven cards to be sorted in index order or it will not work. Sorting the cards is slow. The value of Paul's hash is that its input is a 52-bit representation of the 7-card hands that does not need sorting (is intrinsically sorted). The combination of Mike's fast hash and my fast sorting technique is already faster than the Senzee hash method. I would explain this in more detail, but I already have an idea of how to do a perfect hash that works on a 52-bit hand representation. I would rather work on this new approach than take the time to explain my sorting algorithm. I am making some progress. If it works out as I hope, it looks like my new hash will require a fraction of the math operations compared to the Senzee method.
Gambling is a math contest where the score is tracked in dollars. Try not to get a negative score.
Mental
• Posts: 1508
Joined: Dec 10, 2018
March 31st, 2024 at 8:10:26 AM permalink
Quote: Mental

Quote: Wizard

The recent discussion about face up cards in Ultimate Texas Hold 'em (UTH) touched on the topic of fast ways of scoring 7-card hands.
[SNIP]
I know Mental uses a hash algorithm, which I quickly failed at implementing. I'm happy to hear more about that and all other ideas for analyzing games like UTH in a matter of hours as opposed to days.

I was able to use the Paul Senzee hash right out of the box without problems. However, when I tried to integrate it into Wizard's program, it kept crashing. Mike had problems, too. I wasted a lot of time trying to see if there was some strange interaction will Wizard's code but I was unable to identify any specific problem. Yesterday, Paul's code started crashing within my own UTH program when I was making some changes elsewhere in the program.

It is possible that the Senzee code has some memory access errors that have gone undetected under most conditions. I have decided to abandon the Senzee hash. I know that Mike already gave up on it. I hate working with opaque code that I don't fully understand and that might have have internal errors. Also, I have found a way to sort seven cards that is faster than any general sort algorithm (sorting seven cards is not a general sorting problem). So I don't gain anything by using the Senzee code.

The Wizard's perfect hash function is very fast, but it needs the seven cards to be sorted in index order or it will not work. Sorting the cards is slow. The value of Paul's hash is that its input is a 52-bit representation of the 7-card hands that does not need sorting (is intrinsically sorted). The combination of Mike's fast hash and my fast sorting technique is already faster than the Senzee hash method. I would explain this in more detail, but I already have an idea of how to do a perfect hash that works on a 52-bit hand representation. I would rather work on this new approach than take the time to explain my sorting algorithm. I am making some progress. If it works out as I hope, it looks like my new hash will require a fraction of the math operations compared to the Senzee method.

I woke up at 3am the other day and started thinking about a hashing method based on a 52-bit hand representation. By 4am, I had an algorithm worked out in my head. I got out of bed and got to work. The basic design worked out, but it took me a few days to code it up, optimize the code, and do all the necessary testing.

Like Paul Senzee, I start by breaking the bits up into chunks and then use a lookup table, bc18[], to tell me how many bits are set in each chunk. Paul uses four 16-bit chunks which does not seem optimal for 52 bits. I use two 18-bit chunks and one 16 bit chunk. The bit count in the first two chunks are combined in a shift operation to make an index to be used in a large switch() statement.

The cases in the switch() statement are generated by a different function in my class. There are very few math operations within the code for each case. I am showing a earlier version of the autogenerated code because it is easier to understand. My current version performs all of multiply operations in advance and combines all of the constants into the ind18_7[] arrays. The final algorithm is much simpler and much faster than the one I show below.

It takes a 52-bit number as input, so I don't need to sort an array of seven integers like I do with Wizard's algorithm. It is five times faster than Paul's index52c7() hash. I can index the 133,784,560 hands in under 500 milliseconds. This is less than two times faster than the Wizard's algorithm. However, sorting seven integers with std:sort() takes a very long time: about 20 time more time than the Wizards algorithm. To avoid using std::sort(), I devised a sorting method that was 20 times faster than std:sort(). My fast sort combined with my faster version of Mike's algorithm is still only 40% as fast as my new mentalHash() method.

It takes me less than 4 nanoseconds to index a seven card hand. I could do it a bit faster if I had more computer RAM memory. I could break the 52-bit number into two 26-bit chunks. When I tried using two chunks, the memory usage was large and the program was slowed down by disk swapping of the very large precomputed index arrays that are needed for the two-chunk solution.

`void Mhash::mentalHash(const uint64_t & b7, uint32_t & rHash){  const uint64_t m0 = 0x3ffffULL; // mask for projecting out 18 bits  uint64_t p0, p1, p2;  uint8_t nb0 = bc18[b7     & 0x3ffffULL];  uint8_t nb1 = bc18[b7>>18 & 0x3ffffULL];  int kind = nb1 | (nb0 << 3);  switch(kind) { // based on how many bits in each bite  case 0: //   0 0 7   (1 * 1 * 11440)  totCnt = 11440    p2 = b7>>36;      // ....................................QKA2.........QKA    rHash = ind18_7[p2] + 0;    return;  case 1: //   0 1 6   (1 * 18 * 8008)  totCnt = 144144    p1 = b7>>18 & m0; // ..................789T...........9TJ........    p2 = b7>>36;      // ....................................QKA2.........QKA    rHash = ind18_7[p2] + (ind18_7[p1] * 8008) + 11440;    int fHash = ind18_7[p2] + ind18_7_6[p1] + 11440;    if (rHash != fHash) exit(0);    return;  case 2: //   0 2 5   (1 * 153 * 4368)  totCnt = 668304    p1 = b7>>18 & m0; // ..................789T...........9TJ........    p2 = b7>>36;      // ....................................QKA2.........QKA    rHash = ind18_7[p2] + (ind18_7[p1] * 4368) + 155584;    int fHash = ind18_7[p2] + ind18_7_5[p1] + 155584;    if (rHash != fHash) exit(0);    return;  case 3: //   0 3 4   (1 * 816 * 1820)  totCnt = 1485120    p1 = b7>>18 & m0; // ..................789T...........9TJ........    p2 = b7>>36;      // ....................................QKA2.........QKA    rHash = ind18_7[p2] + (ind18_7[p1] * 1820) + 823888;    int fHash = ind18_7[p2] + ind18_7_4[p1] + 823888;    if (rHash != fHash) exit(0);    return;  case 4: //   0 4 3   (1 * 3060 * 560)  totCnt = 1713600    p1 = b7>>18 & m0; // ..................789T...........9TJ........    p2 = b7>>36;      // ....................................QKA2.........QKA    rHash = ind18_7[p2] + (ind18_7[p1] * 560) + 2309008;    int fHash = ind18_7[p2] + ind18_7_3[p1] + 2309008;    if (rHash != fHash) exit(0);    return;  case 5: //   0 5 2   (1 * 8568 * 120)  totCnt = 1028160    p1 = b7>>18 & m0; // ..................789T...........9TJ........    p2 = b7>>36;      // ....................................QKA2.........QKA    rHash = ind18_7[p2] + (ind18_7[p1] * 120) + 4022608;    int fHash = ind18_7[p2] + ind18_7_2[p1] + 4022608;    if (rHash != fHash) exit(0);    return;  case 6: //   0 6 1   (1 * 18564 * 16)  totCnt = 297024    p1 = b7>>18 & m0; // ..................789T...........9TJ........    p2 = b7>>36;      // ....................................QKA2.........QKA    rHash = ind18_7[p2] + (ind18_7[p1] * 16) + 5050768;    int fHash = ind18_7[p2] + ind18_7_1[p1] + 5050768;    if (rHash != fHash) exit(0);    return;  case 7: //   0 7 0   (1 * 31824 * 1)  totCnt = 31824    p1 = b7>>18 & m0; // ..................789T...........9TJ........    rHash = ind18_7[p1] + 5347792;    return;  case 8: //   1 0 6   (18 * 1 * 8008)  totCnt = 144144    p0 = b7     & m0; // 2345...........456..........................    p2 = b7>>36;      // ....................................QKA2.........QKA    rHash = ind18_7[p2] + (ind18_7[p0] * 8008) + 5379616;    return;  case 9: //   1 1 5   (18 * 18 * 4368)  totCnt = 1415232    p0 = b7     & m0; // 2345...........456..........................    p1 = b7>>18 & m0; // ..................789T...........9TJ........    p2 = b7>>36;      // ....................................QKA2.........QKA    rHash = ind18_7[p2] + (ind18_7[p1] * 4368) + (ind18_7[p0] * 78624) + 5523760;    return;  case 10: //   1 2 4   (18 * 153 * 1820)  totCnt = 5012280    p0 = b7     & m0; // 2345...........456..........................    p1 = b7>>18 & m0; // ..................789T...........9TJ........    p2 = b7>>36;      // ....................................QKA2.........QKA    rHash = ind18_7[p2] + (ind18_7[p1] * 1820) + (ind18_7[p0] * 278460) + 6938992;    return;  case 11: //   1 3 3   (18 * 816 * 560)  totCnt = 8225280    p0 = b7     & m0; // 2345...........456..........................    p1 = b7>>18 & m0; // ..................789T...........9TJ........    p2 = b7>>36;      // ....................................QKA2.........QKA    rHash = ind18_7[p2] + (ind18_7[p1] * 560) + (ind18_7[p0] * 456960) + 11951272;    return;  case 12: //   1 4 2   (18 * 3060 * 120)  totCnt = 6609600    p0 = b7     & m0; // 2345...........456..........................    p1 = b7>>18 & m0; // ..................789T...........9TJ........    p2 = b7>>36;      // ....................................QKA2.........QKA    rHash = ind18_7[p2] + (ind18_7[p1] * 120) + (ind18_7[p0] * 367200) + 20176552;    return;  case 13: //   1 5 1   (18 * 8568 * 16)  totCnt = 2467584    p0 = b7     & m0; // 2345...........456..........................    p1 = b7>>18 & m0; // ..................789T...........9TJ........    p2 = b7>>36;      // ....................................QKA2.........QKA    rHash = ind18_7[p2] + (ind18_7[p1] * 16) + (ind18_7[p0] * 137088) + 26786152;    return;  case 14: //   1 6 0   (18 * 18564 * 1)  totCnt = 334152    p0 = b7     & m0; // 2345...........456..........................    p1 = b7>>18 & m0; // ..................789T...........9TJ........    rHash = ind18_7[p1] + (ind18_7[p0] * 18564) + 29253736;    return;  case 16: //   2 0 5   (153 * 1 * 4368)  totCnt = 668304    p0 = b7     & m0; // 2345...........456..........................    p2 = b7>>36;      // ....................................QKA2.........QKA    rHash = ind18_7[p2] + (ind18_7[p0] * 4368) + 29587888;    return;  case 17: //   2 1 4   (153 * 18 * 1820)  totCnt = 5012280    p0 = b7     & m0; // 2345...........456..........................    p1 = b7>>18 & m0; // ..................789T...........9TJ........    p2 = b7>>36;      // ....................................QKA2.........QKA    rHash = ind18_7[p2] + (ind18_7[p1] * 1820) + (ind18_7[p0] * 32760) + 30256192;    return;  case 18: //   2 2 3   (153 * 153 * 560)  totCnt = 13109040    p0 = b7     & m0; // 2345...........456..........................    p1 = b7>>18 & m0; // ..................789T...........9TJ........    p2 = b7>>36;      // ....................................QKA2.........QKA    rHash = ind18_7[p2] + (ind18_7[p1] * 560) + (ind18_7[p0] * 85680) + 35268472;    return;  case 19: //   2 3 2   (153 * 816 * 120)  totCnt = 14981760    p0 = b7     & m0; // 2345...........456..........................    p1 = b7>>18 & m0; // ..................789T...........9TJ........    p2 = b7>>36;      // ....................................QKA2.........QKA    rHash = ind18_7[p2] + (ind18_7[p1] * 120) + (ind18_7[p0] * 97920) + 48377512;    return;  case 20: //   2 4 1   (153 * 3060 * 16)  totCnt = 7490880    p0 = b7     & m0; // 2345...........456..........................    p1 = b7>>18 & m0; // ..................789T...........9TJ........    p2 = b7>>36;      // ....................................QKA2.........QKA    rHash = ind18_7[p2] + (ind18_7[p1] * 16) + (ind18_7[p0] * 48960) + 63359272;    return;  case 21: //   2 5 0   (153 * 8568 * 1)  totCnt = 1310904    p0 = b7     & m0; // 2345...........456..........................    p1 = b7>>18 & m0; // ..................789T...........9TJ........    rHash = ind18_7[p1] + (ind18_7[p0] * 8568) + 70850152;    return;  case 24: //   3 0 4   (816 * 1 * 1820)  totCnt = 1485120    p0 = b7     & m0; // 2345...........456..........................    p2 = b7>>36;      // ....................................QKA2.........QKA    rHash = ind18_7[p2] + (ind18_7[p0] * 1820) + 72161056;    return;  case 25: //   3 1 3   (816 * 18 * 560)  totCnt = 8225280    p0 = b7     & m0; // 2345...........456..........................    p1 = b7>>18 & m0; // ..................789T...........9TJ........    p2 = b7>>36;      // ....................................QKA2.........QKA    rHash = ind18_7[p2] + (ind18_7[p1] * 560) + (ind18_7[p0] * 10080) + 73646176;    return;  case 26: //   3 2 2   (816 * 153 * 120)  totCnt = 14981760    p0 = b7     & m0; // 2345...........456..........................    p1 = b7>>18 & m0; // ..................789T...........9TJ........    p2 = b7>>36;      // ....................................QKA2.........QKA    rHash = ind18_7[p2] + (ind18_7[p1] * 120) + (ind18_7[p0] * 18360) + 81871456;    return;  case 27: //   3 3 1   (816 * 816 * 16)  totCnt = 10653696    p0 = b7     & m0; // 2345...........456..........................    p1 = b7>>18 & m0; // ..................789T...........9TJ........    p2 = b7>>36;      // ....................................QKA2.........QKA    rHash = ind18_7[p2] + (ind18_7[p1] * 16) + (ind18_7[p0] * 13056) + 96853216;    return;  case 28: //   3 4 0   (816 * 3060 * 1)  totCnt = 2496960    p0 = b7     & m0; // 2345...........456..........................    p1 = b7>>18 & m0; // ..................789T...........9TJ........    rHash = ind18_7[p1] + (ind18_7[p0] * 3060) + 107506912;    return;  case 32: //   4 0 3   (3060 * 1 * 560)  totCnt = 1713600    p0 = b7     & m0; // 2345...........456..........................    p2 = b7>>36;      // ....................................QKA2.........QKA    rHash = ind18_7[p2] + (ind18_7[p0] * 560) + 110003872;    return;  case 33: //   4 1 2   (3060 * 18 * 120)  totCnt = 6609600    p0 = b7     & m0; // 2345...........456..........................    p1 = b7>>18 & m0; // ..................789T...........9TJ........    p2 = b7>>36;      // ....................................QKA2.........QKA    rHash = ind18_7[p2] + (ind18_7[p1] * 120) + (ind18_7[p0] * 2160) + 111717472;    return;  case 34: //   4 2 1   (3060 * 153 * 16)  totCnt = 7490880    p0 = b7     & m0; // 2345...........456..........................    p1 = b7>>18 & m0; // ..................789T...........9TJ........    p2 = b7>>36;      // ....................................QKA2.........QKA    rHash = ind18_7[p2] + (ind18_7[p1] * 16) + (ind18_7[p0] * 2448) + 118327072;    return;  case 35: //   4 3 0   (3060 * 816 * 1)  totCnt = 2496960    p0 = b7     & m0; // 2345...........456..........................    p1 = b7>>18 & m0; // ..................789T...........9TJ........    rHash = ind18_7[p1] + (ind18_7[p0] * 816) + 125817952;    return;  case 40: //   5 0 2   (8568 * 1 * 120)  totCnt = 1028160    p0 = b7     & m0; // 2345...........456..........................    p2 = b7>>36;      // ....................................QKA2.........QKA    rHash = ind18_7[p2] + (ind18_7[p0] * 120) + 128314912;    return;  case 41: //   5 1 1   (8568 * 18 * 16)  totCnt = 2467584    p0 = b7     & m0; // 2345...........456..........................    p1 = b7>>18 & m0; // ..................789T...........9TJ........    p2 = b7>>36;      // ....................................QKA2.........QKA    rHash = ind18_7[p2] + (ind18_7[p1] * 16) + (ind18_7[p0] * 288) + 129343072;    return;  case 42: //   5 2 0   (8568 * 153 * 1)  totCnt = 1310904    p0 = b7     & m0; // 2345...........456..........................    p1 = b7>>18 & m0; // ..................789T...........9TJ........    rHash = ind18_7[p1] + (ind18_7[p0] * 153) + 131810656;    return;  case 48: //   6 0 1   (18564 * 1 * 16)  totCnt = 297024    p0 = b7     & m0; // 2345...........456..........................    p2 = b7>>36;      // ....................................QKA2.........QKA    rHash = ind18_7[p2] + (ind18_7[p0] * 16) + 133121560;    return;  case 49: //   6 1 0   (18564 * 18 * 1)  totCnt = 334152    p0 = b7     & m0; // 2345...........456..........................    p1 = b7>>18 & m0; // ..................789T...........9TJ........    rHash = ind18_7[p1] + (ind18_7[p0] * 18) + 133418584;    return;  case 56: //   7 0 0   (31824 * 1 * 1)  totCnt = 31824    p0 = b7     & m0; // 2345...........456..........................    rHash = ind18_7[p0] + 133752736;    return;  default:    cout << "Bad case label in switch!" << endl;    exit(0);  }    // cumCnt = 133784560}`
Gambling is a math contest where the score is tracked in dollars. Try not to get a negative score.
Mental
• Posts: 1508
Joined: Dec 10, 2018
March 31st, 2024 at 8:20:22 AM permalink
Modern compilers are very good at executing switch statements. Even though my method has very many lines of code, only one small portion of the code is used for each case. The compiler creates branch statement to dispatch the right code. Paul's algorithm uses the same number of math operations for each hand. I use very few operations for simple cases, like when all seven cards are found within one chunk (which roughly corresponds to one third of the deck). The most common seven card hands have cards in all three chunks, but I deal with this case when I need to.

I do use a lot of memory for precomputed tables in my method, but it is still small enough to fit in RAM. A four-chunk version of the program would use a lot less memory, but would be slower.
Gambling is a math contest where the score is tracked in dollars. Try not to get a negative score.
CrystalMath
• Posts: 1911
Joined: May 10, 2011
Thanked by
March 31st, 2024 at 9:59:17 PM permalink

Here's my function for generating the hash. It works for any number of cards, and likely for any size of deck.
hand values range from 0 to 51.

int PatHandIndex(int[] hand) {
int qtyCards = hand.length;
int r = 0;
while (qtyCards > 0) {
r += combin_array[hand[qtyCards - 1]][qtyCards--];
}
return r;
}

Also, for programs like this where it makes sense to pre-compute combins, this is what I have used, which eliminates floating point errors:

int[][] createCombinArray(int a, int b) {
int[][] combin_array = new int[a+1][b+1];

combin_array[0][0]=1;
for (int i = 1; i <= a; i++) {
combin_array[0] = 1;
for (int j = 1; j <= b; j++) {
combin_array
= combin_array[i - 1][j - 1]
+ combin_array[i - 1]
;
}
}
return combin_array;
}

It was actually the patterns in the combin array, such as the method I used to generate the array, that initially led me to the hash method.
I heart Crystal Math.
Mental
• Posts: 1508
Joined: Dec 10, 2018
Thanked by
April 1st, 2024 at 7:10:52 AM permalink
Quote: CrystalMath

Here's my function for generating the hash. It works for any number of cards, and likely for any size of deck.
hand values range from 0 to 51.

int PatHandIndex(int[] hand) {
int qtyCards = hand.length;
int r = 0;
while (qtyCards > 0) {
r += combin_array[hand[qtyCards - 1]][qtyCards--];
}
return r;
}

Also, for programs like this where it makes sense to pre-compute combins, this is what I have used, which eliminates floating point errors:

int[][] createCombinArray(int a, int b) {
int[][] combin_array = new int[a+1][b+1];

combin_array[0][0]=1;
for (int i = 1; i <= a; i++) {
combin_array[0] = 1;
for (int j = 1; j <= b; j++) {
combin_array

= combin_array[i - 1][j - 1]
+ combin_array[i - 1]
;
}
}
return combin_array;
}

It was actually the patterns in the combin array, such as the method I used to generate the array, that initially led me to the hash method.

Can you show me a real world use of the hash index that produces the card array in index order?

For example, in a VP analyzer, you can produce the starting hands in index order, but when you draw to the hand, some of those replacement cards are out of order.

For UTH, you can loop through all combinations while choosing the hole cards in order, the flop cards in order, the turn and river in order, and the dealer hole cards in order. But when you combine these cards into a seven card array, you need to do sorting if the indexes in order to use your method.

Even if the cards just happened to be in order already, checking this order requires 6 comparisons. If the cards are badly out of order, the number of comparisons and swaps takes an extraordinary amount of time compared to the hash operation.

This is the problem I have avoided by hashing a 52-bit representation of the cards. As I have said, std::sort is a good sorting algorithm for the general problem of sorting seven integers. It is incredibly slow compared to any of our hash functions. This was my attempts to sort a restricted set of seven integers.

`union DualRep // dual representation of a hand{    int64_t bits;    // occupies 64 bits    uint8_t hand[8]; // occupies 64 bits};void Chem::createSortedArray(DualRep & cardMap, uint64_t b7){  DualRep partMap;  int shift = 0, delta = 0;  cardMap.bits = 0;  for (int bite = 0; bite < 3; bite++) {    uint64_t b18 = (b7 >> (bite*18)) & 0x3ffff;    partMap.bits = sortMap[bite][b18];    delta = partMap.bits >> 56;    partMap.bits <<= shift;    cardMap.bits |= partMap.bits;    shift += delta;    if (shift >= 56) break;  }}`
It depends on the fact that the seven integers are in the range 0 <= i < 52. It also depends on a precomputed array, sortMap[bite][b18]. It takes a 52-bit rep of the hand and creates a 56 bit rep of the hand as seven 8-bit integers. My createSortedArray() runs in constant time and is up to 20 times faster than std::sort() depending on how badly out of order the starting hand is.
Last edited by: Mental on Apr 1, 2024
Gambling is a math contest where the score is tracked in dollars. Try not to get a negative score.