« 2ちゃんねるブラウザ BonBon Ver. 0.1 | トップページ | C言語で要素を数える »

2014年11月12日 (水)

テキサスホールデムの役を判定する

プログラム技術板スレ立てるまでもない質問はここで 139匹目において、テキサスホールデムというゲームがあることを知った。

レス番483で提案されてるのは、7枚のカードのうち2枚を決定し成立する可能性のある役を絞り込むというものだ。しかし、このアルゴリズムだと最外周ループが42周するというのを、どうやっても削減できない。

しかし、7枚のカードでフラッシュが成立するかを調べるのは難しくない。複数のフラッシュが同時に成立する可能性がないから。スイートごとに枚数をカウントして5を超えたら打ち切ればよい。

ストレートが成立するかどうかを調べるのも難しくない。6枚以上連続する可能性があるので、ロイヤルストレートが成立するかを調べるためにデータ構造を工夫する必要があるだろう。

あとは、ペア、スリーカード、フォーカードの数を調べれば役を判定できるはずだ。ここでは集計を簡単にするために、スリーカードはtwo_or_moreとthree_or_moreの両方にカウントするものとする。同様に、フォーカードは、two_or_more, three_or_more, fourの全てでカウントする。そうするとフルハウスは、three_or_more>=1 && two_or_more>=2で判定できる。

この方針で作成したプログラムを以下に示す。1000万回のループを0.8秒で抜ける。(Core i5-2500K, Windows 7 64bit, VisualC++ 2013, Release構成)

// texasholdem1.cpp : コンソール アプリケーションのエントリ ポイントを定義します。
//

#include "stdafx.h"

const int LOOP = 10000000;
const char SUITE_CHAR[] = "SHDC";
char* RESULT;

typedef enum
{
	SUITE_NONE = -1,
	SUITE_SPADES = 0,
	SUITE_HEARTS = 1,
	SUITE_DIAMONDS = 2,
	SUITE_CLUBS = 3
} suite_t;

typedef struct
{
	int number;
	suite_t suite;
} card_t;

// ストレートを判定するため、数字が5枚以上連続するカードの開始点と終了点を記録する構造体
// 13-1境界を処理しやすくするために、1=14,2=15……とみなし、endは13を超えることがある
// ストレートが成立しないときは、begin, endともに0とする
typedef struct
{
	int begin;
	int end;
} straight_range_t;

typedef struct
{
	int two_or_more;
	int three_or_more;
	int four;
} pair_count_t;

void get_card(card_t cards[])
{
	bool exist[13 + 1][4];
	for (int i = 1; i <= 13; i++)
		for (int j = 0; j < 4; j++)
			exist[i][j] = false;

	srand((unsigned int)time(NULL));

	for (int i = 0; i < 7; i++)
	{
		while (true)
		{
			int number = rand() % 13 + 1;
			suite_t suite = (suite_t)(rand() % 4);
			if (!exist[number][suite])
			{
				cards[i].number = number;
				cards[i].suite = suite;
				exist[number][suite] = true;
				break;
			}
		}
	}
}

void print_card(card_t cards[])
{
	for (int i = 0; i < 7; i++)
		printf("%2d ", cards[i].number);
	printf("\n");

	for (int i = 0; i < 7; i++)
		printf(" %c ", SUITE_CHAR[cards[i].suite]);
	printf("\n");
}

suite_t check_flush(card_t cards[])
{
	int suite_count[4] = {};

	for (int i = 0; i < 7; i++)
		if (++suite_count[cards[i].suite] == 5)
			return cards[i].suite;

	return SUITE_NONE;
}

void count_number(card_t cards[], int number_count[])
{
	for (int i = 0; i < 7; i++)
	{
		number_count[cards[i].number]++;
		number_count[cards[i].number + 13]++;
	}
}

void check_number(card_t cards[], suite_t suite_flush, int number_exist[])
{
	for (int i = 0; i < 7; i++)
		if (cards[i].suite == suite_flush)
		{
			number_exist[cards[i].number]++;
			number_exist[cards[i].number + 13]++;
		}
}
void check_straight(int number_count[], straight_range_t &straight_range)
{
	for (int i = 1; i <= 13; i++)
	{
		if (number_count[i] != 0 &&
			number_count[i + 1] != 0 &&
			number_count[i + 2] != 0 &&
			number_count[i + 3] != 0 &&
			number_count[i + 4] != 0)
		{
			straight_range.begin = i;
			if (number_count[i + 5] != 0)
			{
				if (number_count[i + 6] != 0)
				{
					straight_range.end = i + 6;
					return;
				}
				straight_range.end = i + 5;
				return;
			}
			straight_range.end = i + 4;
			return;
		}
	}

	straight_range.begin = 0;
	straight_range.end = 0;
}

void count_pair(int number_count[], pair_count_t &pair_count)
{
	for (int i = 1; i <= 13; i++)
	{
		if (number_count[i] >= 2)
		{
			pair_count.two_or_more++;
			if (number_count[i] >= 3)
			{
				pair_count.three_or_more++;
				if (number_count[i] >= 4)
					pair_count.four++;
			}
		}
	}
}

int _tmain(int argc, _TCHAR* argv[])
{
	card_t cards[7];
	get_card(cards);
	print_card(cards);

	clock_t start = clock();
	for (int loop = 0; loop < LOOP; loop++)
	{
		// 情報収集 開始
		suite_t suite_flush = check_flush(cards);

		// 数字ごとの枚数を保持する変数
		// 13-1境界を処理しやすくするために、数字+13のカードでもあるとして、2カ所でカウントする
		// カードの数字は1から始まるため、配列サイズに+1する
		int number_count[13 + 13 + 1] = {};
		count_number(cards, number_count);

		straight_range_t straight_range;
		check_straight( number_count, straight_range);

		// フラッシュを構成する数字が存在するかを保持する変数
		int number_exist[13 + 13 + 1] = {};
		straight_range_t straight_flush_range;
		straight_flush_range.begin = straight_flush_range.end = 0;
		if (suite_flush != SUITE_NONE)
		{
			check_number(cards, suite_flush, number_exist);
			check_straight(number_exist, straight_flush_range);
		}

		pair_count_t pair_count;
		// 初期化
		pair_count.two_or_more = pair_count.three_or_more = pair_count.four = 0;
		count_pair(number_count, pair_count);
		// 情報収集 終了

		// 役の判定 開始
		if (straight_flush_range.begin != 0)
		{
			// ストレートフラッシュは確定
			if (straight_flush_range.begin <= 10 && straight_flush_range.end >= 14) // 14=A
				RESULT = "Royal Straight Flush";
			else
				RESULT = "Straight Flush";
		}
		else if (pair_count.four == 1)
			RESULT = "Four of a Kind";
		// three cardもtwo_or_moreに含まれるので、フルハウスならtwo_or_moreは2以上になるはず
		else if (pair_count.three_or_more >= 1 && pair_count.two_or_more >= 2)
			RESULT = "Full House";
		else if (suite_flush != SUITE_NONE)
			RESULT = "Flush";
		else if (straight_range.begin != 0)
			RESULT = "Straight";
		else if (pair_count.three_or_more >= 1)
			RESULT = "Three of a Kind";
		else if (pair_count.two_or_more >= 2)
			RESULT = "Two Pair";
		else if (pair_count.two_or_more == 1)
			RESULT = "One Pair";
		else
			RESULT = "No Pair";
		// 役の判定 終了
	}
	clock_t end = clock();
	printf("%lf sec\n", ((double)end - start) / CLOCKS_PER_SEC);

	printf("%s\n", RESULT);

	return 0;
}

« 2ちゃんねるブラウザ BonBon Ver. 0.1 | トップページ | C言語で要素を数える »

コメント

面白い問題ですね!
ポーカーは詳しくないですが、そのアルゴリズムがわかりやすいですし、良さそうです。

Wikipediaのポーカーの記事によると、「K-A-2を含むものはストレートとはみなされない。」ということのなので、ストレートの判定では、2=15,...の部分は蛇足になってしまう気がします。

> ポーカー - Wikipedia
> A-2-3-4-5も10-J-Q-K-Aもストレートとみなされる。しかしQ-K-A-2-3のようにK-A-2を含むものはストレートとはみなされない。

コメントありがとうございます。
「K-A-2を含むものはストレートとはみなされない」というのは初めて知りました。

ストレートの判定を
straight_range.end <= 14 // 14=A
とすれば対応できそうですね。

セルフ突っ込み

10-11-12-13-1-2と6枚連続している可能性もあるから、straight_range.end <= 14でストレートを判定しちゃいけませんね。

あと自分用メモ。
・check_straight関数においてstraight_rangeを初期化する場所をcaller側に統一する
・check_straight関数において条件判断が多いので削減する

数字をX,スートをYとする表を仮作成、X,Yとも集計Σ,Σ' を行う。
::::A===========K|Σ'
S ----------*--|1
H *---------**-|3
D -*----------*|2
C ------------*|1
===============|=
Σ11--------212|7

S=2111112234
↑ストレート判定値(5を含むなら確定、4以下は期待)の検出ループは10回行う。
Σの集計を小さい方から"5連続して1以上の列がある"時にストレート判定。
但し、余剰を用いてA列を2度調べる必要がある。

集計として数字を出しておけば、「ストレート/フラッシュになる期待値」生成も容易になる。
ストレートフラッシュ判定は "Σ' >= 5"の条件で開始し、単独スートでΣを再集計する必要がある。

H **-------****|6 (ロイヤルフラッシュの例 この場合は10以上のカードで成立)

--- 以下余談

有利・不利の判定は、「見えているカード」と「コミュニティ+見えていない2枚」で勝敗を記録し、
「カードが増えたことによる強さの変化」を読み取る必要があるでしょう。
必然的に、組み合わせテーブルは肥大化しそうです。

補足:
ストレート判定は、強い側から調査し、成立時に打ち切る必要があります。
(あえて弱い側から行い、上書きすることも可能。速度は出ませんが。)

コメントを書く

コメントは記事投稿者が公開するまで表示されません。

(ウェブ上には掲載しません)

トラックバック

この記事のトラックバックURL:
http://app.f.cocolog-nifty.com/t/trackback/1499066/57969835

この記事へのトラックバック一覧です: テキサスホールデムの役を判定する:

« 2ちゃんねるブラウザ BonBon Ver. 0.1 | トップページ | C言語で要素を数える »