まず初めに、こんな簡単なゲームのことを考えてみてください。
2人でじゃんけんをして、勝った側は負けた側から「勝った時に出していた指の本数+1点」をもらう。
ex.グーで勝ったなら1点、チョキで勝ったなら3点、パーで勝ったなら6点を相手からもらう
さて、このゲームで最も起こりづらいことは次のうちどれでしょうか？
- どちらもグーを出してあいこになる
- どちらもチョキを出してあいこになる
- どちらもパーを出してあいこになる
直感的には、起きやすい方から順に2>3>1か、3>2>1の順を想像するのではないでしょうか。人間同士がやるといかにも下から順に起きやすそうですよね。
このゲームに絶対に負けない最適戦略を双方がとった場合、正解は
Contents
導入
麻雀、人狼、ポーカーなどが流行るにつれ、不完全情報ゲームの最適戦略というトピックは日に日に重要になっている気がします。これは経済学のゲーム理論という分野についてよく学習しないと理解が難しく、基本的に大学レベルの知識が求められるテーマです。実際インターネットで素人が軽く調べても、難解な数式と英語の論文に圧倒されるばかりだと思います。今回はそんな不完全情報ゲームの最適戦略を求めるアルゴリズムのひとつであるCFRについて、専門的な知識が一切なくてもなんとなく雰囲気が掴めるような解説記事です。
ちょうど「あーなんか経済学にそういう分野あるよねしってるしってる」ぐらいのテンションの人なら読破できると思います。私がそうでしたので。
なお、本来はプログラミングの知識を持ってやりたいことではあるのですが、ここに書いてある内容だけならExcel程度の表計算ソフトでも（マクロなどは不要で）実行できます。
不完全情報ゲームの最適戦略とは
この手のトピックに触れたことがあれば、ナッシュ均衡という言葉を見たことがあるかと思います。これは全てのプレイヤーがある一定の戦略を取る時、戦略を変えると自分だけが損する状態になってしまうために誰も戦略を変える動機を持たない状態のことを指します。この状態は複数人の戦略間で均衡が取れている、ということでナッシュ「均衡」と呼ぶわけです。
なお、2人のゲームと3人以上のゲームで話がだいぶ変わってくるので、ここから下は2人で行われるゲームについての話だと思ってください。
一般的にゲーム理論の考え方によって最適戦略を求めることは、このナッシュ均衡を求めることに帰着すると考えて良い（はず）です。というのも、零和ゲーム（片方が勝つともう片方が同じだけ負ける、というように、利得の総和がゼロであるゲームのことです。だいたいのゲームはそうですね）であれば、各プレイヤーはとりあえずナッシュ均衡で得られた解に従っている限りにおいては、一定の利益が保障されるからです。
CFR とは
CFRはそんな不完全情報ゲームにおけるナッシュ均衡戦略を求めるアルゴリズムのひとつで、Counterfactual Regret Minimization の略です。
- Counterfactual：反実仮想。「実際にはそんなことはないけど、もしこうだったら～」みたいなやつ。
- Regret：後悔
- Minimization：最小化
ということで、これらを合わせると雰囲気としては
もしこっちの戦略を取ってたらこれくらい良くなったのにな、という後悔の度合いを最小化することで最適戦略を構築する方法
という感じになります。実際のアルゴリズムの内容もそんな感じです。
アルゴリズムの概略
二人零和不完全情報ゲームのごく簡単な例として、以下のようなじゃんけんゲームを考えます。
格差じゃんけん
AさんとBさんの2人がじゃんけんをし、勝敗を決定する。ただし、点数(利得)は以下のように決定する。
| 勝った時の手 | Aさんの勝ち | Bさんの勝ち |
| グー | {+1, -1} | {0, 0} |
| チョキ | {+3, -3} | {+2, -2} |
| パー | {+5, -5} | {+5, -5} |
このゲーム程度のナッシュ均衡戦略ならちょっと調べれば簡単に出てきますが（いわゆるグリコ・チョコレート・パイナップルゲームと考え方は似ています）、これをCFRアルゴリズムがどのように解決するかを見ていきます。
まず、このゲームのゲーム木を描きます（このレベルのゲームだと利得行列を描けばいいのですが、後に手番を導入した際の説明の都合を考え、ゲーム木で見ていきます）。
各ノードで、プレイヤーは今自分に与えられている情報を基に戦略を決定します（ただし、このゲームにおいては確定している事前情報はありません。他のゲームの場合、これが履歴という形で表され、戦略に影響を及ぼすことになります）。
例として、「Aさん、Bさんともに全ての手を1/3ずつの確率で出す」という戦略から検討を始めます。すると、Aさんについて、戦略全体としては以下のような利得になります。
| 出した手 | グー | チョキ | パー |
| 利得 | $$-\frac{4}{3}$$ | $$1$$ | $$1$$ |
ノード全体の利得は「各戦略の利得×その戦略を取る確率」の総和で表されます。この場合は
$$-\frac{4}{3}\times\frac{1}{3}+1\times\frac{1}{3}+1\times\frac{1}{3}=\frac{2}{9}$$
となります。
後悔値を取る
後悔値(適切な訳語が無いのでここではそう呼称することにします)とは、ノード全体の利得と、そのノードにおけるある特定の戦略の利得の差のことを指します。
基本的に、この後悔値が負の値を取る場合、その戦略はいらなかったんじゃない？という話になります。その戦略を取ったことでノード全体の利得が押し下げられていることになるからです。これは下の図を見て頂ければわかりやすいと思います。
逆にこの後悔値が正なら、それも大きければ大きいほど、その戦略を取りたいということにもなります。
先程計算した各戦略の利得とノードの利得から、Aさんの各戦略の後悔値を出します。
| 出した手 | グー | チョキ | パー |
| 利得 | $$-\frac{4}{3}$$ | $$1$$ | $$1$$ |
| 後悔値 | $$-\frac{14}{9}$$ | $$\frac{7}{9}$$ | $$\frac{7}{9}$$ |
これを見ると、グーを出すという戦略はどうやら利得を下げるだけなので不要なようです。
これを踏まえ、戦略を後悔値に比例するように割り振り直して修正します（正規化と呼ばれる手順です）。なおこの時、0以下の後悔値を取った戦略については、全て0であるとして正規化を行います。
つまり、グー：チョキ：パー＝\(0:\frac{7}{9}:\frac{7}{9}\)になるようにします。
これによりAさんの戦略はチョキとパーを等確率で出す戦略に修正されました。
反復する(イテレーション)
ここまでの作業がこのアルゴリズムの１単位です。実際に近似解を求めるためには、新しく得られた戦略に対してこの作業を繰り返します。今の例はAさんについて計算しましたが、Bさんについても同じ作業をします。さながら6項間漸化式を一つ一つ求めていく作業です。こうなってくるとだんだん手計算では追い付かなくなってきます。
その際に使う後悔値ですが、これは累積します。例えば、1回目の計算でAさんの戦略は{\(0,\frac{1}{2},\frac{1}{2}\)}に修正されましたが、同じ要領でBさんの戦略は{\(0,\frac{5}{13},\frac{8}{13}\)}に修正されています。これを基に2回目の計算を行うとAさんの後悔値はだいたい\(0, 0.624, 0\)となるので、これを1回目の計算で得た後悔値に足し合わせ、その数字をもとに正規化を行います。(やや雑な説明ですいませんがそういうことです)
6項間漸化式という言葉で、もしかしたら……？と思った方もいるかもしれませんが、そうですね、多分手作業でも値の収束する先が計算できるのではないでしょうか。私はやりたいとは思いませんでしたので、表計算ソフトに軽く1000回程度反復をやらせてみました。こういうことは機械に任せてこそ文明人です。
多少の波がありつつも、ある一定の値に向かって収束していきそうな雰囲気です。特にAさんもBさんも最初一瞬（グー打点低いしいらないな）って判断してから（やっぱグーあった方がええな）って考え直しているあたりに人間味を感じますね。やっている計算の内容を知ってしまうと人間味もへったくれもないのですが。
ちなみにこのゲームの混合戦略ナッシュ均衡は3×3行列で簡単に表して求めることができ、その場合
Aの戦略は\(\{g, c, p\} = \{\frac{21}{64}, \frac{5}{8}, \frac{3}{64}\}\)
Bの戦略は\(\{g, c, p\} = \{\frac{19}{64}, \frac{5}{8}, \frac{5}{64}\}\)
が最適となります。また、その際の期待値はAが\(+\frac{15}{64}=0.234375\)となります。ここから片方だけが戦略を修正すると、修正した側が必ず損をします。直感に反して、最も高い点数を得られるはずのパーが最も低頻度にならなければならない、というのが興味深いです。
これをよりとっつきやすいように単純化したのが冒頭の問題でした。
今後の応用のために
これを例えば手番がある複雑なゲームに応用したり、3人以上のゲームに応用したりと言ったことが考えられますが、いずれもより深い計算が必要になってくるほか、前提自体が変わることにもなります。その辺りの話を絡めてくるとさすがにExcelでは厳しいので、そこでついにプログラミングの出番です。
この記事は今後これをポーカーやそのほかいろいろなゲームに応用するための、いわば導入部分の話になります。次回、簡単にポーカーに勝つための……？ お楽しみに。
注意
いろんな記事で書いてる気がしますが、私は経済学の専門家ではありません。微細な表現に誤りがある場合があります。twitterでご指摘いただくか、大目に見てください。
