Hatena::ブログ(Diary)

yuizumi’s diary

2015-12-31

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 はプレイヤーの数。

スパム対策のためのダミーです。もし見えても何も入力しないでください
ゲスト


画像認証

トラックバック - http://d.hatena.ne.jp/yuizumi/20151231/1451562475