Miyamoto
1 はじめに
今回は強化学習でも今後重要になっていくと思われる「ゲーム理論」について、基礎解説を行いたいと思います。
現在、強化学習というのは、こういった競争的要素を考慮した研究というのはあまり行われていません。
しかし、多くの会社が強化学習AIを導入したビジネスを行う時代になれば、「競合他社のAIに如何に勝つか」という視点が重要になると考えられます。\(^{\ast1}\)
そのため、弊社としては、その時代が来る前に着々と敵対的強化学習の研究を行い、他社に機先を制す準備を進め ています。
この記事の著者は、「ライアーゲーム」「嘘喰い」「アクマゲーム」「たとえ灰になっても」「ワンナウツ」「天」「ドミ ニウム」といった漫画 \(^{\ast 2}\) を非常に好み、また好きなゲームはポケモンであるため、ゲーム理論の内容に対して、こういった作品等での事例を具体例として注釈していきたいと考えています。\(^{\ast 3}\)
\(^{\ast 1}\)火の鳥未来編のような状況になるのはよろしくないですが。
\(^{\ast 2}\)ドミニウムと天の作者さんは、今はギャンブル漫画を描いていません。昔は面白いギャンブル漫画を描いていただけに残念です。
\(^{\ast 3}\)最近のポケモンは「乱数のある将棋」と言われるほど、読みと構築の要素が強いです。
2 ゲーム理論の基礎
この章では、タイトルの通りゲーム理論の基礎について簡単に解説します。
プレイヤーが\(X,Y\) の2 人、行動はそれぞれの状況で、プレイヤー\(X\)の報酬\(r_x\) を最大化する戦略を考えます。
2.1 完全情報ゲーム
2.1.1 ナッシュ均衡
次のような状況を想定します。
| \(Y\)の行動 | |||
|---|---|---|---|
| \((r_x, r_y)\) | \(A_y\) | \(B_y\) | |
| \(X\)の行動 | \(A_x\) | \((2,5)\) | \((3,6)\) |
| \(B_x\) | \((3,2)\) | \((4,3)\) | |
の目線に立って考えてみましょう。
行動\(A_x\) を選んだら、報酬は\(Y\) が\(A_y\)を選んだ場合は\(2\)で、\(B_y\)を選んだ場合は\(3\)になります。
一方で、行動\(B_x\)を選んだら、報酬は\(Y\)が\(A_y\)を選んだ場合は\(3\)で、\(B_y\)を選んだ場合は\(4\)になります。
つまり、このような状況では、\(X\)目線では「\(Y\)がどのような行動をとっても、\(X\)は\(B_x\)を選んだほうが得」であると言えます。\(^{\ast 4}\)
また、これは\(Y\)の目線でも同じことで、\(X\)の行動に関わらず、\(Y\)は\(B_y\) を選択したほうが利得が多くなります。
つまり、二人が共に合理的であるならば、\(B_x,B_y\)が選択されるでしょう。このような状況のことを「ナッシュ均衡」と呼びます。
ナッシュ均衡は必ずしも全体の利益を保証しません。後に「囚人のジレンマ」で解説します。
\(^{\ast 4}\)ポケモンで言うところの「安定行動」です。
2.1.2 非ナッシュ均衡
では、表の一部を改変した状況を考えてみましょう。
| \(Y\)の行動 | |||
|---|---|---|---|
| \((r_x, r_y)\) | \(A_y\) | \(B_y\) | |
| \(X\)の行動 | \(A_x\) | \((3,4)\) | \((2,3)\) |
| \(B_x\) | \((2,2)\) | \((4,5)\) | |
ナッシュ均衡の場合と違い、相手の行動によって最適な戦略は変わってきます。安定行動が存在しません。ジャンケンです。\(^{\ast5}\)
\(^{\ast 5}\)これがいわゆる「択ゲー」と呼ばれる状況です。かなり多くの場面で発生します。ワンポーカーでは和也がこの択に悩み続ける描写が数か月続いて苛立った読者は多いでしょう。
2.1.3 囚人のジレンマ
共有地の悲劇とも言います。ナッシュ均衡が存在するものの、その結果が二人の総算としては最悪のものになってしまう。（少なくとも最善ではない）状況を言います。
| \(Y\)の行動 | |||
|---|---|---|---|
| \((r_x, r_y)\) | \(A_y\) | \(B_y\) | |
| \(X\)の行動 | \(A_x\) | \((-3,-3)\) | \((-7,-2)\) |
| \(B_x\) | \((-2,-7)\) | \((-5,-5)\) | |
二人の犯罪者\(X,Y\)が「\(A\)自白しない」「\(B\)自白する」という二つの選択肢を迫られた状況を考えます。
二人とも口を噤んだ場合、両方が\(-3\)で済むため、全体としては\(-6\)という最小の犠牲で済みます。
しかし、表を見ればわかる通り、お互い相手の選択に関わらず自白してしまう選択をしたほうが、自分にとっては損失が少なく済みます。
結果として、ナッシュ均衡では二人とも自白する選択をしてしまい、全体としては-\(10\)という最悪の状況に陥ります。 \(^{\ast 6}\)
各々が自分の利益だけを考えた結果、最悪の結果を招くという状況です。 \(^{\ast7}\)
\(^{\ast 6}\)筆者はこれを防ぐための装置が宗教だと思っています。
\(^{\ast 7}\)ギャンブル漫画での一例としては、ライアーゲーム実写版の「エデンの園ゲーム」が該当します。全員が赤リンゴを入れ続ければ、全員が13億円手にすることができ、事務局の大損失にすることができますが、大富豪以外は優勝賞金50 億円を諦めることになる上、常に裏切った方が得という環境であるため、作中では最後の1 回しか揃っていません。この1 回も奇跡のようなもの。
2.1.4 背水の陣戦略
退路を絶つ、自らを不利にするという方法で、自らの優位を作り出す・信頼させる・不利を回避するという方法です。
いろんな例があるのですが、表ではその一例として、「不利を回避する」に重きを置いてみます。不利を作って不利を回避するという一見矛盾した状況ですが、次の表をご覧ください。
| \(Y\)の行動 | |||
|---|---|---|---|
| \((r_x, r_y)\) | \(A_y\) | \(B_y\) | |
| \(X\)の行動 | \(A_x\) | \((5,4)\) | \((2,2)\) |
| \(B_x\) | \((4,3)\) | \((3,2)\) | |
| \(C_x\) | \((6,5)\) | \((1,12)\) | |
今度は\(X\)のみ3 つ選択肢があります。この状況で、 \(X\) 目線で最も報酬が得られるのは、自分が\(C_x\)を選んで、相手が\(A_y\)を選んだ場合です。
しかし、相手が\(B_y\)を選択した場合は、最低報酬になってしまう恐れがあります。
特に、\(Y\)が貪欲なギャンブラータイプで在れば、\(B_y\)を選択してくるため、不利に追い込まれやすいでしょう。
そこで、\(X\)はこう宣言します。「俺は\(C_x\)を選ばない。もし選んだら10の報酬をやる」、これに加えて契約書も交わしたとします。すると表はこう変質します。
| \(Y\)の行動 | |||
|---|---|---|---|
| \((r_x, r_y)\) | \(A_y\) | \(B_y\) | |
| \(X\)の行動 | \(A_x\) | \((5,4)\) | \((2,2)\) |
| \(B_x\) | \((4,3)\) | \((3,2)\) | |
| \(C_x\) | \((-4,15)\) | \((-9,22)\) | |
これによって、\(X\)にとって\(C_x\)はあまりに実りのない選択となりました。\(A_x,B_x\)を選ぶしかありません。
当然そのことは\(Y\)にも分かっているので、\(C_x\)がない状況下での\(Y\)目線は、\(A_y\)を選ぶのが合理的という結果になります。
これにより、\(X\)は\(A_x\)を選択することで、安定的に報酬\(5\)を手にすることができるというわけです。\(6\)か\(1\)かのギャンブルをするよりよほどいい状況でしょう。\(^{\ast8}\)
自ら不利を作ることで、望み通りの相手の行動を引き出すという戦略もあります。表は書きません。具体例は注釈をご覧ください。 \(^{\ast9}\)
ここで注意していただきたいのが、「あえてやるはずのない行動で対戦相手にこちらの手札等の錯誤を誘うというのは背水の陣戦略とは異なるという点です。\(^{\ast10}\)
\(^{\ast 8}\)ライアーゲームにおける実写版の「椅子取りゲーム」では、アキヤマが自らメダルを破棄することで、自陣はユウを勝たせるつもりであるということを信用させようとしました。典型的な背水の陣戦略、「信用」の事例です。「感染拡大ゲーム」（実写版では「天使と悪魔ゲーム」で、アキヤマの作戦を潰すためにヨコヤ（実写版ではカツラギ）が活用しました。こちらは厳密には少し異なりますが、不利な状況を相手に教えて有利な条件を引き出すという考え方は一致しています。ワクチン（実写版では十字架）が2つしかないという、チームの不利な点 を、ヤンジャンやキョジンたちを引き入れる戦略に利用しましたね。
\(^{\ast 9}\)これの例としては、Ultra battle SMash！のランドセルvsベルンにおいて、ランドセル氏がキュウコンを早々に切ったのは（自覚があったかはわかりませんが）この背水の陣戦略であると言えます。これによりジャラ\(Z\)の一貫を作り、レッドカードブルンゲルを突き刺しました。
\(^{\ast 10}\)「業の櫓」で捨隈が用いた故意にミスナンバーを入力するという戦略は、ゲーム理論用語としての背水の陣戦略にはあたりません。
2.2 不完全情報ゲーム
ここまで紹介したすべてのゲームは、有限確定完全情報ゲームといい、行動の選択肢が有限でありすべて既知で、かつお互いの行動から結果は決定論的に定まるという状況でした。
該当するのはチェス、将棋、囲碁などです。これを有限確定完全情報ゲームと言います。\(^{\ast11}\)
しかし、世の中の多くのゲーム及び経営戦略は、そうはなっていません。相手の手札は見えないし、結果は確率的に決まります。
お互いの行動から一意に定まるのは結果の確率分布であり、結果そのものはわかりません。ゲームにおいて該当するのは、ポケモン、麻雀、トランプなどがあります。\(^{\ast12}\)
\(^{\ast 11}\)筆者はこのような伏せられた情報や確率が絡まないゲームは好みません。
\(^{\ast 12}\)強化学習AIの発達により、こういったゲームのほうがより高度なものとされる逆転現象が起きるのではないかと睨んでいます。
2.2.1 零和有限確定完全情報ゲーム
また、有限確定完全情報ゲームのうち、ゼロサムゲームになるもののことを零和有限確定完全情報ゲームと言います。
わかりやすいのは勝ちと負けがある2 人対戦でしょうか。緊縮論者以外にとっては、実際の経済はそうなっていません。
零和有限確定完全情報ゲームは、「先手必勝」もしくは「後手必勝」か「千日手（引き分け）」のいずれかであることが数学的に証明されています。
すなわち、先手か後手の（ルールによって定まる）どちらかが最適な行動を取れば、その相手は絶対に勝てません。\(^{\ast13}\)
\(^{\ast 13}\)動物将棋は後手必勝であることが示されていますが、ほとんどのゲームは先手必勝になります。囲碁はコミによって変わります。
2.2.2 不確定不完全情報ゲーム
実際の世の中をゲーム理論に当てはめると、ほとんどの事例がこちらに該当します。
これはつまり、取れる行動の選択肢が相手にわからず、また結果も確率的にしか決まらないというものです。
「撮れるかもしれない戦略」が「取れる戦略」より大幅に大きいため、相手の考慮の外から攻めて意表を突くようなことも可能になります。\(^{\ast14}\)
また、実際に取れない選択肢を、まるで実行可能であるかのように見せかけることで、相手の嫌な行動を抑制するという手法は、ギャンブル用語で「ブラフ」といい、古今東西現実世界から創作の世界まで、広く使われています。
\(^{\ast 14}\)こちらが挑発の入った剣舞/シャドクロ/じゃれつく/影うちのテンプレミミッキュ、相手がヌオーだったとします。通常であればこちらは下がるしかないので、ヌオー側は毒毒や熱湯が安定行動となります。しかしここでシャドークローではなくウッドハンマーを覚えていれば、ヌオーを倒すことができるわけです。
3 ゲーム理論の発展
ここからは、発展的な内容を取り扱います。
3.1 確率微分ゲーム
連続時間のゲーム理論のことを「微分ゲーム」と言います。厳密な定義とは異なりますが、おおむねこの認識で構いません。
モデルにおいて有名なものは「殺人運転手ゲーム」などがあります。
その確率的な実社会における応用例としては、「マーケットメイカーの株の売買」があります。
大株主\(^{\ast15}\)二人が自らの利得を最大化しようとしたとします。
\(^{\ast 15}\)ここでは、自らの売買が株価を変動させるほどの株主という意味。
(1)
\[ d X_{t}=\pi_{X}\left(X_{t}, Y_{t},\left\{\theta_{s}^{X}\right\}_{s \leq t},\left\{\theta_{s}^{Y}\right\}_{s \leq t}\right) f_{X}\left(X_{t}, Y_{t},\left\{\theta_{s}^{X}\right\}_{s \leq t},\left\{\theta_{s}^{Y}\right\}_{s \leq t}\right) d t+\sigma_{X}\left(X_{t}, Y_{t},\left\{\theta_{s}^{X}\right\}_{s \leq t},\left\{\theta_{s}^{Y}\right\}_{s \leq t}\right) d B_{t} \]
(2)
\[ d X_{t}=\pi_{Y}\left(X_{t}, Y_{t},\left\{\theta_{s}^{X}\right\}_{s \leq t},\left\{\theta_{s}^{Y}\right\}_{s \leq t}\right) f_{Y}\left(X_{t}, Y_{t},\left\{\theta_{s}^{X}\right\}_{s \leq t},\left\{\theta_{s}^{Y}\right\}_{s \leq t}\right) d t+\sigma_{Y}\left(X_{t}, Y_{t},\left\{\theta_{s}^{X}\right\}_{s \leq t},\left\{\theta_{s}^{Y}\right\}_{s \leq t}\right) d B_{t} \]
という連立確率微分方程式を考えた時、終了時刻T における保有資産\(X_T\)の期待値を最大化する戦略\(\theta_{t}^{X} \)\( _{0 \leq t \leq T} \)はどのように求めればいいでしょうか。
当然相手の行動の読みも重要になってきますので、ゲーム理論の考え方が必要になります。資料がとても少ない分野ですが、例としては[2]などが挙げられます。
3.2 GAN
ゲーム理論とは少し違いますが、様相が似ているため紹介します。
機械学習においては、「敵対的学習はAI の性能を大幅に高めることが多い」ということが広く知られています。
その考えでおそらく一番結果を出しているのではないかと思われるのが、GAN（敵対的生成ネットワーク）です。
画像を例にとって説明しますと、このジャンルでは画像を自動生成する「生成器」と、生成器で作られた画像か本物の画像か判定する「判別器」という二つのネットワークを学習します。
ここで重要なのが「相手に勝てるように交互に学習する」という点です。\(^{\ast16}\)
\(^{\ast 16}\)片方だけが強くなりすぎるというのが、GAN でありがちな失敗例。
3.3 強化学習への展望
強化学習においては。マルチエージェントの状況下での強化学習[3] などが行われています。
現在は平和的な争いの研究ばかりですが、そのうち「よそのAI の裏をかき続けて相手の売り上げを下落させる研究」といった、敵意の塊のような研究も登場するのではないかと思われます。\(^{\ast17}\)
\(^{\ast 17}\)というか筆者はギャンブル漫画脳なので、強化学習とゲーム理論と聞いて一番に浮かんだのがそういう研究でした。
4 最後に
ここまでゲーム理論の基礎と発展について、解説してきました。
しかし、その学習に関しては、例えば[1] のような書籍を読むよりも、「嘘喰い」「ライアーゲーム」「アクマゲーム」といった良質で論理的なギャンブル漫画や、ポケモン実況動画\(^{\ast18}\)などを、きちんと理解しながら見たほうが、よほどゲーム理論的な考え方が身につくのではないかと考えています。
趣味全開になってしまいましたが、これで説明を終わります。
次回は農協改革とダイナミックプライシングについてお話します。お楽しみに。
\(^{\ast 18}\)特に読みを当てて勝つタイプの実況者の動画が良いです。昔だと暇士氏、最近だとライバロリ氏あたりがおすすめ。暇士氏の愛用する追い打ち不意打ちキリキザンは、使う人の腕が全てなので、神読み型と言われています。
参考文献
[1] 渡辺隆裕, ゼミナールゲーム理論入門, 日本経済新聞社(2008)
[2] Makiko Nishio,Stochastic Control Theory,splinger(2015)
[3] Ann Nowe, Peter Vrancx, and Yann-Michael De Hauwere,Game Theory and Multi-agent Reinforcement Learning, Reinforcement Learning: State-Of-The-Art (2012)