Texas Hold 'em の勝率計算
年末にこんなコードを書いていた。
https://gist.github.com/yuizumi/a15bdde89f79fab9dded
ポーカー(テキサス・ホールデム)の大会中継なんかを見ていると、各プレイヤーの勝率(ポットを獲得する確率)が画面上に表示されたりする。聞いた話によると、それらの勝率の値はモンテカルロ・シミュレーションで計算されているらしいのだけれど、52C5 = ~2.6M だし、全パターン列挙しても大丈夫じゃないの?という話になった。
この見積もりは実際には少し甘い。たとえば一対一の場面(ヘッズ・アップ)であれば 48C5 × 7C5 × 2 = ~72M 回*1ほど役判定をしなければならず、毎回愚直に役判定を行ってしまうと秒単位で時間がかかる。しかしよく考えると、スートが関係する役ってフラッシュ(とストレート・フラッシュ)だけだし、ランク(数)の組み合わせって全部で 13^5 = ~370K ぐらいしかないし、競プロ御用達の前計算でもしておけば速くなるんじゃないの?みたいな感じでできあがったのが上のコードである。
手元のラップトップ(MBA w/ Core i7)で走らせるとこんな感じになる。計算時間的にはプレイヤーが 4 人のときが一番大変なのだが、それでも 200 ms 未満で結果が帰ってくる。
$ time ./holdem TC2D 2HQH 7D5D 4H2S Player #1: TC2D -- 17.66% / 80.68% Player #2: 2HQH -- 35.09% / 63.25% Player #3: 7D5D -- 34.06% / 65.11% Player #4: 4H2S -- 11.53% / 86.82% real 0m0.165s user 0m0.160s sys 0m0.003s
一番上の行は 10♣2♦ を持ったプレイヤーの単独勝利(ポットを独占)の確率が 17.66% で、敗北(ポットを完全に失う)の確率が 80.68% であるという意味。引き分け(スプリット)があるので両者を足しても 100% にはならない。
一応、場札(の一部)の指定も可能にした。場札があると考えるパターンの数が激減するので計算も一瞬で終わるようになる。以下は場札の最初の 3 枚(フロップ)が 3♦3♥A♦ とわかった場面。
$ time ./holdem TC2D 2HQH 7D5D 4H2S +3D3HAD Player #1: TC2D -- 6.10% / 86.34% Player #2: 2HQH -- 28.78% / 63.66% Player #3: 7D5D -- 44.27% / 50.98% Player #4: 4H2S -- 13.29% / 79.15% real 0m0.021s user 0m0.018s sys 0m0.003s
みなさまよいお年を。
〔22:45 更新〕つまらないことに気がついて 2〜3 割ほど高速化したので計算時間に関する記述を改めました。どれだけつまらないかは Revisions を参照してください。
*1:各々に 2 枚ずつ、合計 4 枚が手札として配られているので、場札は残り 48 枚のうちの 5 枚。また、手札 2 枚と場札 5 枚の合計 7 枚から任意に 5 枚を選ぶので 7C5 が掛かる。最後の 2 はプレイヤーの数。