nogawaparkのブログ

書く練習。

Kuhn Poker で実験する CFR(Counterfactual Regret Minimization) with Common Lisp

はじめに

以前QiitaにCounterfactual Regret Minimaization(CFR)の基礎 - QiitaというCFRの提案論文の概要をまとめた記事を書いたが、今回は理解を深めるために、実際にkuhnpokerというミニ版のポーカーでCFR計算を実装しナッシュ均衡戦略を求めた。

実装の参考として主にこの記事を用いた: Vanilla Counterfactual Regret Minimization for Engineers | Justin Sermeno この記事はCFRの基礎とPython実装がよくまとまっている。ただし、Python実装をそのまま写経しても身につかないと思ったので他の言語Common Lispに書き直しながら実装を行った。

結果、以下のことが分かった。

CFRについて

CFR とは展開型ゲームのナッシュ均衡戦略を求める手法である。 詳細は解説記事1に譲る。 簡単に書いておく。

(1)求めるものは、平均戦略 \bar{\sigma}_i^ T(a|I) である。

(2)この平均戦略がナッシュ均衡に従うためには、以下のように各ラウンドでの戦略 \sigma_i^ T(a|I)を更新すると実現できる。


\sigma _ i^ {T+1}(a|I) = \begin{cases}
\frac{R _ i^ {T,+}(I,a)}{\sum _ {a\in A(I)}R _ i^ {T,+}(I,a)} &
 {\rm if\ } \sum _ {a\in A(I)} R _ i^ {T,+}(I,a)>0 \\\\
\frac{1}{|A(I)|} & {\rm otherwise.}
\end{cases}

(3)実は、上の更新式は、下に定義するimmediate counterfactual regret R^ T _ {i, imm} (I) の正の部分が0に収束するように更新される。

R^ T _ {i,imm}(I) = \frac{1}{T}{\rm max} _ {a\in A(I)}\sum _ {t=1}^ T\pi _ {-i}^ {\sigma^ t}(I)(u _ i(\sigma^ t| _ {I\to a},I)-u _ i(\sigma^ t,I))

(4)最後に、二人組ゼロサムゲームで 二人の max(0, R^ T _ {i, imm} (I)) の和が \epsilon の時、戦略 \bar{\sigma}_i^ T による利益のナッシュ均衡との差は 2\epsilon 以下である。

kuhnpoker

kuhnpoker とは

kuhnpoker とは、ミニ版の二人制ポーカーである。カードはJ, Q, K の三枚しか使わないがブラフを使う必要が出てくるため、小さいながらもポーカーの本質を備えていると思われる。

ゲームの流れとしては、まずカードが二人のプレイヤーに一枚ずつ配られる。先手後手ともに最初に1ずつ賭ける。先手は check か bet を選ぶ。後手は先手が check の場合は check か bet、先手が bet のときは fold か call を選ぶ（reraise はない）。また、check-bet と来たときのみもう一度先手はfoldかcallを選ぶ。ここでbetの単位は1のみである。最終的にfoldが選ばれたら相手に+1、checkかcallが選ばれたら強いカードを持っている方に+1または+2となる。

以下のゲーム図と合わせて理解できる。

f:id:nogawapark:20200414081814p:plain
ゲーム図 https://justinsermeno.com/posts/cfr/ より引用

ブラフを使う必要性がどこで現れるか説明する。例えば先手が最弱のJだったとしても、強気のbetを行うことで（自分はKを持ってると見せかける）、後手をfoldさせ利益を得ることが可能である。

逆に後手がQを持っているときに先手がbetした場合、後手はfoldする（相手はKだろう）かcallする（相手はブラフのJだろう）か選ばないといけない。 相手がブラフする確率を織り込んで自分もcallする確率を何割か持っていなければならない。

kuhnpoker のナッシュ均衡解

実は kuhnpoker のナッシュ均衡は無数にある。Kuhn poker - Wikipedia の説明を引用しておく。

Kuhn demonstrated there are infinitely many equilibrium strategies for the first player, forming a continuum governed by a single parameter. In one possible formulation, player one freely chooses the probability \alpha \in [0,1/3] with which he will bet when having a Jack (otherwise he checks; if the other player bets, he should always fold). When having a King, he should bet with the probability of 3\alpha (otherwise he checks; if the other player bets, he should always call). He should always check when having a Queen, and if the other player bets after this check, he should call with the probability of \alpha +1/3. The second player has a single equilibrium strategy: Always betting or calling when having a King; when having a Queen, checking if possible, otherwise calling with the probability of 1/3; when having a Jack, never calling and betting with the probability of 1/3.

果たして、CFRにより求められるナッシュ均衡戦略は上記の Kuhn が例示した均衡戦略と同じものが得られるだろうか。

実装

common lisp の処理系として SBCL を用いた。 roswel をインストールして $ ros emacs とするだけでcommon lisp が書き始められるのは驚きだった。 コードはgithubに上げた GitHub - RyotoYamashita/KuhnPokerCFRExperiment

ので興味があればご覧下さい。

結果

実行速度

Vanilla Counterfactual Regret Minimization for Engineers | Justin Sermeno の記事の python コードと、作成したlispコードを手元のマシンで実行し、速度比較した。 cfr 10,000 イテレーションで行った。

python lisp
4.009 s 0.406 s

実行結果は上記となり、速度はcommon lisp 実装の方が10倍程度速い。 common lisp コードは特に最適化などはしていないが、 floatの値は明示的に 1.0 などとした。 そうしないと、ひたすら有理数の計算をしてめちゃくちゃ重くなった。 平気で分母が10桁の分数の足し算をしだしてしまう。

CFR の収束性

平均戦略の収束性

f:id:nogawapark:20200417085649p:plain
平均戦略: 凡例の情報の元で check or fold を選ぶ確率

各iteration各情報集合のもとで、弱気な選択（check or fold）をする確率を表示した。 Kuhn poker では各情報集合で2つの行動しか選択できないため、片方の選択をする確率のみを表示している。

10000iteration 行くころには、何らかの確率に収束している。 収束の仕方は、確率が0or1となる、おそらく自明な行動では収束が速く、 そうではない自明ではない行動の確率の求解ではぎざぎざとゆっくりと収束する、ように見える。

平均戦略の収束がぎざぎざしている情報集合は以下のグループである。 [J rr, J rrc, Q rrb, Q rrcb, K rr]

得られた解と、Kuhnが示したナッシュ均衡戦略と比べる。 まず、Kuhnによると後手のナッシュ均衡戦略は一通りしかないみたいだが、 今回の結果はそれと同じ解になっている！ また先手についても、Kuhn がいうところの \alpha=0.21 のナッシュ均衡戦略を実現していると考えられる。 ただ、なぜ \alpha=0.21がCFRで求められたかは分からない。 （ \alpha \in [0, 1/3] についてナッシュ均衡戦略が構築できる）

immediate counterfactual regret の収束性

f:id:nogawapark:20200417090109p:plain
先手のimmediate counterfactual regret

f:id:nogawapark:20200417090200p:plain
後手のimmediatecounterfactual regret

immediate counterfactual regret の収束性を、先手と後手に分け、両対数グラフで図示した。

この結果から、各情報集合での immediate counterfactual regret の 両対数グラフでの傾きは -1 と -1/2 のグループがあることが分かった。 傾きが -1/2 のグループは、 [J rr, Q rrcb, K rr, J rrc, Q rrb] であり、 これは、平均戦略が0から1の間をとる（混合戦略をとる）情報集合グループと同じである。 つまり、平均戦略とimmediate counterfactual regret の収束性には関係があることが分かる。

実は、このことは数学の定理として予言されていたことが現れた形になる。 immediate counterfactual regret の収束は、平均戦略の収束を上から抑える、という定理があるのだ。 immediate counterfactual regretの収束が速い情報集合における平均戦略の収束は確かに速く、 immediate counterfactual regretの収束が遅い情報集合における平均戦略の収束は 上から抑える速さが緩くなっている分遅くなっていることが分かる。

混合戦略での収束の速さは O(iter^ {-1/2}) であることが両対数グラフから読み取れるが、 実はこれは理論で言われている収束の最大の遅さと一致している！

exploitability の収束性

（実験中）

immediate counter factual regret < epsilon -> exploitabity < 2 epsilon は成り立っているか

（実験中）

まとめ

  • CFRでナッシュ均衡戦略を求められることが実験的に確かめられた。
  • 次の行動が自明な情報集合と、自明でない情報集合で、収束の速さが異なることが分かった。

今後気になること

アルゴリズム、理論の調査

  • CFR+
  • MCCFR
  • DeepCFR
  • CFRの証明
  • MCCFRの証明
  • なんで三人、六人でも上手くいくのか
  • ナッシュ均衡についての理解を深めたい
  • exploitability を近似的に求める手法について
  • 状態遷移規則を仮定しない fictious play
  • CFRはナッシュ均衡のうちどのような均衡解にたどり着いているのか
  • 平均戦略の収束がぎざぎざしているのはなぜか

実装方針

  • 他のゲームにも切り替えられるように実装する。
  • ゲームの実装、CFRとの連携も考えておく
  • ゲームの実装のとき、実際にプレイするモードが欲しい。
  • ちゃんとasdfを使う

  1. 原論文, Counterfactual Regret Minimaization(CFR)の基礎 - Qiita 等↩