0. はじめに
ポーカーのハンドは 2,598,960 通りある(52枚から5枚選ぶので C(52, 5))。それらにハンドの強さを表す整数値を割り振るアルゴリズムが存在する
1. 基本
"Cactus Kev's Poker Hand Evaluator" by Kevin Suffecool
- 全てのハンドの強さは、1 ～ 7462 の整数値で表現できることを示した
- 数字が小さいほど強い。1 はロイヤルストレートフラッシュ
- 対応表: http://suffe.cool/poker/7462.html
- アルゴリズムの説明: http://suffe.cool/poker/evaluator.html
- ソースコード: http://suffe.cool/poker/code/
- C での実装
- パーフェクトハッシュを使って高速化したという報告あり
- by Paul Senzee
- http://www.paulsenzee.com/2006/06/some-perfect-hash.html
- ソースコードはリンク切れ
手札を5枚と想定しているため、そのままでは、ホールデムで使えない
1-1. カードのデータ構造
// +--------+--------+--------+--------+
// |xxxbbbbb|bbbbbbbb|cdhsrrrr|xxpppppp|
// +--------+--------+--------+--------+
// p = prime number of rank (deuce=2,trey=3,four=5,five=7,...,ace=41)
// r = rank of card (deuce=0,trey=1,four=2,five=3,...,ace=12)
// cdhs = suit of card
// b = bit turned on depending on rank of card
//
// i.e.
// xxxAKQJT 98765432 CDHSrrrr xxPPPPPP
// 00001000 00000000 01001011 00100101 King of Diamonds
// 00000000 00001000 00010011 00000111 Five of Spades
// 00000010 00000000 10001001 00011101 Jack of Clubs
上述のように 各カードは 4byte に符号化されて、以下の情報を持つ:
- 13bit のランクビット
- 4 bit のスートビット
- 4 bit の10進ランク表現
- 6 bit の素数ランク表現
1-2. アルゴリズム概要
前節のように符号化すると、役の判定の大部分をビット演算に落とし込める。以下 5枚のカードを c1, c2, c3, c4, c5 とし、特に断りがない限りそれを整数値とみなす。
Step1: フラッシュの時
以下のビット演算で、フラッシュ(含ストレートフラッシュ）か否かがわかる（スートマスク0xF000を被せて AND すると全部同じスートの時のみ非ゼロになる）:
c1 & c2 & c3 & c4 & c5 & 0xF000
フラッシュだとわかった場合、（フラッシュのハンド間の）役の強さはスート情報を落としてしまって問題ないし、5枚のカードのランクは全て異なるので、以下の数字 q は役の強さの識別子となる(16bit シフトするとランクのみになる。5枚のカードは全て異なるので OR をとると 5か所に1が立つ数になる):
q = (c1 | c2 | c3 | c4 | c5) >> 16;
q の値はどんなに大きくても 7936 = 0b1111100000000 なので 7937 の要素数の配列flushesを用意しておき、0 で初期化し 1278 = C(13, 5) 箇所を 事前計算で計算したスコアで埋めるという作業をしておくと、以下のように q値からスコアを引ける:
flushes[q]
事前計算結果は array.h に定義されている flushesテーブル。
Step2. ストレート/ブタの時
フラッシュでない場合、ストレート/ブタの判定・すなわち5枚のカードのランクが全て異なっているかの判定をする。5枚のカードのランクが全て異なるときの q にのみ 事前計算したスコアを格納しそれ以外は0で初期化した unique5 テーブルを作っておく。
unique5[q]
上記のように unique5を引いてそれが非ゼロであれば、それがストレート/ブタであるとわかり、値が役の強さになる。引いた結果が 0 であれば、次のステップに進む。
Step3. それ以外の時
以上 Step1, Step2 に引っかからない場合を考える。まずフラッシュでないのでスート情報を落としてしまってよいだろう（マスク0xFFをかけてよい）。重複しているかもしれないので、ビット演算に落とし込めないので、素数表現にして5数をかけ算するとハンドの識別子 q2になる:
q2 = (c1 & 0xFF) * (c2 & 0xFF) * (c3 & 0xFF) * (c4 & 0xFF) * (c5 & 0xFF);
5つの素数をかけ算するので数はめちゃくちゃ大きくなるのでStep1,2でやったようなテーブルルックアップの方法は使えない。一方、q2の要素数は4888と それほど多くない。そこで、要素数 4888の配列PRODUCT にq2の取りうる値を小さい順に詰め込んで、要素数 4888の配列 values にそれに対応づく事前計算したスコアを格納しておけば、q2の値を(2分木探索で)productの中に見つけて、それに対応するvaluesの要素がスコアになる。
idx = findIndexFromProd(q2); // ニ分木探索で products を探索し場所を知り
values[idx] // 対応する values を引くとスコアが求まる
2. 応用
"PokerHandEvaluator" by Henry Lee
-
n枚 (n = 5,6,7) のカードから最大の役を作成し、前述の数値を返すようにした- ホールデムでも使える！
- アルゴリズムの説明: https://github.com/HenryRLee/PokerHandEvaluator/tree/master/Documentation
- HashNBinaryKSum
- コード: https://github.com/HenryRLee/PokerHandEvaluator/
- 実装はC
- 各種のポートがある
- JavaScript: https://github.com/thlorenz/phe きになる。
2-1. ハンドのデータ構造
シンプルに考えると、 52bit のデッキに対して、7か所のビットを立てると考えられるが、ハンドがフラッシュではないことがわかっている場合、 13bit （つまりランクのみに注目）の5を基数とする表現として表すこともできる（5＝なし、1 枚ある、2枚ある、3枚ある、4枚ある）。
// 52bit: simple but large
| Spades | Hearts | Diamonds | Clubs |
23456789TJQKA23456789TJQKA23456789TJQKA23456789TJQKA
0001010010000000100000000000000000010000010000000001
// 13bit quinary(基数:5)
23456789TJQKA
2010010000201
2-2. ハンドの完全ハッシュ関数
完全ハッシュ関数とは？: Wikipedia
フラッシュでない任意のハンド（要素数: 49205）に対する完全ハッシュ関数があれば、あとはテーブルを引くだけになる。ハンドの13bit quinary 表現 q が与えられた際に、辞書順に並べた際の順序を返すような関数が完全ハッシュ関数なのでこれを採用する。
つまり以下の関数が本質的に重要。
int hash_quinary(unsigned char q[], int len, int k)
これは dynamic programming(動的計画) で解ける。dp[5][14][8] という部分に分割でして解く。