coding, photo, plant and demo

*テキサスホールデムの最適解は求まるか

poker tech 20131224 223454
これは以前テキサスホールデムのゲーム理論上の最適解について調べ物をしていたときの備忘録です。

ゲーム理論とは

ここを読んでいただくのが手っ取り早いですが、複数人のプレイヤでゲームをするとき、どうやったら最大の利益が得られるかを考える学問です。第二次世界大戦前後にフォン・ノイマンが戦略を確率的に混ぜた混合戦略を用いることで様々なゲームにおいて均衡が見つかることを示し、そこから軍事等に応用されました。さらにナッシュが非協力n人ゲームでも均衡が存在することを示し、殆どの現実のモデルにゲーム理論を適用可能となりました。当然ポーカーにも理論上は適用可能です。もし均衡が分かれば、それは絶対に搾取されない無敵の戦略となります。(ただし誰にも負けないことを保証するだけで、プラスになるとは限りません。例えば、ジャンケンのナッシュ均衡はグーチョキパーを1/3ずつの割合で出す戦略ですが、誰にも負けませんが誰にも勝てません)

複雑な意思決定とゲーム理論を読むと、実際にどう解くかも含めて分かるかと思います。

テキサスホールデムを解くことの難しさ

テキサスホールデムをゲーム理論の面から研究している方は多数いるようです。
しかしながら、多人数のノーリミットテキサスホールデム(NLHM)は現在ある膨大な計算資源を使っても、解明は難しいとされています。何故なら下記の理由で、状態数が爆発するからです。

  • 各プレイヤーの行動はレイズ、コール、フォールドの3種類だが、ノーリミットの場合はレイズ額を自由にコントロールできるため選択肢が無数にある
  • ベッティンする機会が多い(プリフロップ、フロップ、ターン、リバーの4回)。さらにリレイズ、リリレイズもできる
  • 手札は2枚で1326種類、フロップは3枚で19600種類。ターンやリバー、他プレイヤーの状態も含めたら天文学的な状態数
  • 参加人数が多い(9人テーブルが主流)。参加者が1人増えると状態数は爆発的に増える

ノーリミットホールデムの場合、2人対戦だけでも教科書通りにゲーム理論を解くことは計算量的に不可能と思われます。

ポーカーの研究の現状

英語の論文は多数出ているのですが、日本語の論文は少ないです。
ひとつ参考になるのは修士論文の相手の抽象化による多人数ポーカーの戦略の決定です。この1.1の背景に近年のポーカーの研究事情が書いてあります。

状況をまとめると、ヘッズアップ(2人)のリミットホールデムならチャンピオンクラスに近づいてきたようです(リミットとはレイズの額が制限されているゲーム。例えば、フロップまでは1BBまでフロップ以降は2BBなど)。そこで一役買っているのがCFRというアルゴリズムです。生真面目にゲーム理論の教科書通りに線形計画法で解く場合と比べて、扱える状態数が10^8から10^12まで大きくなったそうです。これにより、限定された状況下ならナッシュ均衡を求めることができるようになったようです。

CFR

ではその凄いアルゴリズム、CFRとは何でしょうか。
大元の論文はRegret Minimization in Games with Incomplete Informationです。

CFRとはCounterFactual Regret minimizationの略で直訳すれば「反事実的後悔最小化」。分かりやすく言えば「あの時ああしていれば!という後悔を最小化するアルゴリズム」でしょうか。この後悔を最小化すればヘッズアップのリミットテキサスホールデムに関しては、ナッシュ均衡に収束することが証明されています。しかし現実は「あのときああすれば良かったのに!」と言っても本当に良かったのか分かる場合は少ないでしょう。

例えば、「3ヶ月前にA子ちゃんに告白しておけば良かった!そうすればクリスマスを寂しく過ごさなくてよかったかもしれない」と今あなたが思ったとしても、現実に告白していればうまくいく可能性もありましたが、単純に振られる可能性もありますし、仮に付き合ってもとんでもない悪女で一人の方がマシだった可能性もあり、つまり告白すれば本当に良かったのかは分かりません *0 。ポーカーでも同様で、自分がトップペアだけどボードがストレート気味のときに相手がオールインしてきたとします。ブラフだと思いコールして相手がストレートだったら「あのとき無理せず降りれば良かった!」と後悔ができますが、インマネ間近だったりしたら降りるでしょう。そのときは相手がブラフだったか分からないため、後悔しようがありませんので学習もできません。

と、現実世界では後悔を元にうまく学習することは難しいのですが、シミュレーションの世界ではゲームが終わる度に手札を公開して、毎回ああすれば良かった!という後悔が得られるので、それが最小になるように判断基準を修正していくことで最適な戦略に近づくことができます。

具体的にどうやって実装するかは、下記が参考になります。
分かりやすい解説やKuhnPoker(手札がKQJしかない単純なワンカードポーカー)を解くサンプルがあります。
http://cs.gettysburg.edu/~tneller/modelai/2013/cfr/index.html

OSSでCFRを使ったホールデムのボットを実装したものも幾つかあります。

A version of AoBot trained for two days competed in AAAI 2009 and broke even.
https://code.google.com/p/alexoholdem

An open implementation of Pure CFR applied to ACPC poker games.
https://github.com/rggibson/open-pure-cfr

脳科学におけるregret

ちょっと脱線しますが、学術的にはregretは「自分が行った選択と行わなかった選択を比較した結果生じる」(Kahneman, 1986)と定義されているようです。面白いのは、
経済学の観点から,ヒトの意思決定は報酬が最大になる方向へ最適化される.
ところが,宝くじなど,それのみでは説明できない現象がある.
宝くじ:買わない方が最終的な損失を防げることがわかっているにも関わらず,「もしあのとき買っていれば・・・」と思う.
このような考え方・推論を,counterfactual reasoning(反事実推論;Roese, 1995; Byrne, 2002)と呼ぶ. 
2007. 5. 23. 脳イメージング研究会より

だそうです。確かに、麻雀でも期待値ではやっちゃいけないと分かっているのに「後悔したくないから立直!」とすることはあります。で、それは感情的な駄目なプレイとされていたわけです。私はギャンブルというのは、感情ではなく期待値に沿って動かなければいけないと教わってきました。しかしながら、CFRではその後悔を最小にするこがナッシュ均衡に近づくことになるというのだから(あくまでヘッズアップホールデムに関して証明されているだけのようですが)、ちょっと僕の常識から外れた感覚で面白く感じます。

そしてまた面白いのが、そのregretという感情を作り出しているのが眼窩野とfMRIから分かっていることです。眼窩野損傷患者は、その特徴として「社会的・個人的意思決定能力が乏しい」「異常な自律神経反応」等の特徴があるそうです。つまりregetは人が正常或いは有利な社会生活を送るために必要な感情であると言えるかもしれません(もっともそれがあるために正しい選択ができない場合や、余計な悩みが生まれる事もあるわけですが)。眼窩野にはCFRのように後悔を最小化する回路が組み込まれていて、ゲーム理論によって利益が最大になるように自分自身の行動を決定しているのかもしれません。たかがポーカーと侮る事なかれ、その真理は人間とは何かという問いと根底では繋がっているのです。たぶん。

よりディープな研究

話がずれましたが本題のポーカーに戻ります。
ポーカーがゲーム理論によって解けるのか?解けるとしたら現状どういう条件下か、といったことについてディープな議論をしているのが海外の掲示板に有ります(from 出来事さん)。
Heads Up Hold'em Solved?

先の日本語の論文の引用2にも出てくるJohanson氏がFullyCompletelyというハンドルで幾つか興味深い書き込みをしています。
http://forumserver.twoplustwo.com/showpost.php?p=40513031&postcount=63
氏の研究内容について、論文などへのリンク。

http://forumserver.twoplustwo.com/showpost.php?p=40523137&postcount=75
近年のコンピューターポーカーの進化のグラフ

http://forumserver.twoplustwo.com/showpost.php?p=40551355&postcount=112
100BBのリミットホールデムはヘッズアップでも3.17*10^17 game states and 3.19*10^14decision points だそうです。分かりやすく書くと100000T個の状態と、100T個の判断ポイントがあると。そしてノーリミットの場合それは、8.72*10^38 game states and 8.81*10^35 decision pointsとなります。劣化なしの抽象化をすれば状態数は何桁か少なるそうですが、もはや焼け石に水。各状態(の確率)を1byteで表現できるとしてもその戦略を書き出すには、プリフロップで5.5ペタバイトが必要で、フロップだと6000ヨッタバイトが必要だそうです。ヨッタって何?

ということで単純ではあるけど、とても奥が深いポーカーの世界。プレイするのも面白いですが、コンピュータサイエンスの面からも非常に面白いんじゃないかと思います。

余談

ちなみにチェスやポーカーでは評価関数の自動学習により、近年猛烈にコンピュータが強くなったのは御存知の通り。研究の盛んなチェスでは、グランドマスターが90年代半ばにスーパーコンピュータに負け、現在ではアルゴリズムの進歩もありスマホレベルでもグランド・マスター級の強さになっているそうです。(参考)。囲碁もMonte-Carlo Tree Searchでかなり強くなったようですし、同時多発的に様々な方面のゲームを解くアルゴリズムの革新が起きている現在はとても面白い時代と言えます。(参考 機械学習の理論と実践)

参考
togetter:自然言語処理とAI
*0 : クリスマスイブなので無理やりそれっぽい話を入れようとしたけど完全に蛇足だった感ある