1. ハンドメータとは
作った結果は↓。計算時間は 数秒程度なので十分実用的。
$ node 06-handmeter.js
[ '74%', '26%' ]
[ '84%', '16%' ]
[ '93%', '7%' ]
2. 作り方
全ての組み合わせを計算し、どちらのハンドが勝つかの統計値をとり、100%で規格化する(合計値が100となるようにする)。なお、ドローの場合は、両者勝ちとして計算した。
計算量が問題となる。プリフロップでのハンドメーターは、組み合わせとして C(48, 5) = 1712304
通りの可能性がある。これは大きすぎるほどの量ではないが、ナイーブにポーカーの実装をすると、数分~数十分程度の計算時間がかかってしまう。(参考値: ナイーブ: 1,000~10,000回/sec
, 専用アルゴ: 100,000~/sec
)。なお、フロップ後(C(45, 2)= 440通り
)、ターン後(C(44, 1)=44通り
)のハンドメーターの計算は一瞬で終わる。
3. 実装
そんなに難しくはない。
- コミュニティカードと手札のカードを 52枚のデッキから取り除き、
- あと何枚引くか?を計算して(
numDraw
) - 全ての場合を持ってくる(
combinations
ジェネレータ) - それぞれの場合に、各人のハンドのスコアを計算し(
handval
) - 勝者のカウンタをインクリメントする(ドローの場合は勝者が複数いるとして計算)
- 最後に、規格化して終了
const handmeter = (board, hands) => {
let deck = range(52).filter(c => !board.includes(c));
hands.map((hand) => { deck = deck.filter(c => !hand.includes(c)); });
const counter = hands.map(() => 0);
const numDraw = 5 - board.length;
for (const cards of combinations(numDraw, deck)) { // really big loop
const values = hands.map(h => [...board, ...cards, ...h]).map(handval);
const winval = values.reduce((acc, x) => (acc > x ? x : acc), 9999);
// draw will result in multiple winners
values.forEach((val, i) => { if (val === winval) counter[i] += 1; });
}
const sum = counter.reduce((acc, x) => acc + x, 0);
return counter.map(x => x / sum * 100.0);
};
全ての場合を持ってくる部分は、C(n, k)
通りの全ての場合を生成するという、比較的一般的なユースケースである。メモリを抑えるためジェネレータを使って実装したが、一度に作ってしまった方が早いかもしれない。
function* combinations(size, arr) {
if (size === 1) {
for (const x of arr) yield [x];
return;
}
for (const fst of arr) {
const filtered = arr.filter(x => x > fst);
const ite = combinations(size - 1, filtered);
for (const snd of ite) yield [fst, ...snd];
}
}
スコア計算(handval
)は、高速化のための工夫がいるが、前に書いた記事 に記載したように、"PokerHandEvaluator" by Henry Lee のアルゴリズムを使った。
4. ボトルネック
明らかにジェネレータの実装が遅い。まとめて作った方が良いかもしれない。
ジェネレータで値の生成のみ C(48, 5): 3.317s
上記 + ハンド評価: 6.689s
5. 次のアクション
ハンドメータはしょせんテレビショー向けの機能である。実際には、相手の手がわからない。相手の手がわからない状態で、自身の2 枚のハンドと場に出ている n = 0, 3, 4
枚のカードから、自身のハンドの強さを数値化することができるだろうか?
答えはできる。特に 2-players フロップ後の場合の数はC(47, 2) * C(45, 2) = 1070190通り
なので全数チェックが可能である。ただ、プリフロップでは C(50, 5) * C(45, 2) = 2097572400通り
の計算は難しいのでシミュレーションを利用する必要がある。もちろん、3人以上の場合にもシミュレーションが必要だ。後日実施するかもしれない。