More than 1 year has passed since last update.

【Python】ゲーム理論でグリコゲームを数値的に解く

Last updated at 2022-05-16Posted at 2022-05-16

はじめに

ここで言うグリコゲームとは、グーで勝てば「グリコ」、チョキで勝てば「チョコレート」、パーで勝てば「パイナップル」の文字数だけ進めるという特殊じゃんけんであり、所謂小学校の頃やったりやらなかったりしたやつである。

この記事では、このグリコゲームのナッシュ均衡解(両者が最適な行動を取るときの戦略)の求め方及び、実際に数値的に求めるところまでを記述する。

原理について考察

一般的な解釈

グリコゲームでは、前述の通りグーで勝てば3歩、チョキ、パーなら6歩進める。
一般的な均衡解を求める方法は、じゃんけんに勝った場合は自分が進める歩数分だけ＋の利得とし、負けた場合は相手が進んだ歩数分だけ－の利得とするやり方である。例えば自分がグー、相手がチョキを出した場合は自分がグーで勝ち3歩進めるので、(自分の利得, 相手の利得) = (3, -3)というように利得が算出される。このやり方を用いると、グー：チョキ：パー＝2:2:1の割合で出すことがナッシュ均衡解であることが求められる。

一般的な解釈の問題点

しかしこのように解を求める方法はあまり実践的とは言えない。例えば自分と相手が階段の頂上のあと一歩手前、つまり両者ともじゃんけんに勝ちさえすれば勝利という場面では、前述の解釈が適用できるとは思えない。普通にじゃんけんをするときのように、グー：チョキ：パー＝1:1:1の割合で出すことがナッシュ均衡解となるはずである。そうでなかったとしても、自分だけが相手よりも先に進んでいた場合、逆に自分が相手よりも後ろにいる場合などは戦略が変わってくるはずである。このように、一般的な解釈を安易に適用することができないことがわかる。

つまり、自分や相手の位置が変わるごとに変化するような解を求めたい。しかし構造はより複雑になる。どのような漸化式を立てれば良いのだろうか。

実装の具体的方法

グリコ・チョコレート・パイナップルゲームのゲーム理論による解で既にわかりやすい解説とともに検証されていた。

というわけで、上の記事の内容を再現するという形でこのゲームを解いていく。途中で非線形連立方程式がでてくるので、Pythonのscipy.optimize.rootというモジュールを使って数値的に解くための手順を記していこうと思う。

具体的な計算式

グリコゲームの漸化式

グリコ・チョコレート・パイナップルゲームのゲーム理論による解の記事を参考にした結果、このような漸化式を立てた。
プレイヤー1,2はそれぞれS={G, C, P}の行動をもつ。
プレイヤー1が$n$、プレイヤー2が$m$の位置にいるときのプレイヤー1の利得を$v_{n,m}$とすると、プレイヤー同士が行動した後の利得は以下の表となる。(縦はプレイヤー1、横はプレイヤー2の行動)

	$G$	$C$	$P$
$G$	$v_{n, m}$	$v_{n-3, m}$	$v_{n, m-6}$
$C$	$v_{n, m-3}$	$v_{n, m}$	$v_{n-6, m}$
$P$	$v_{n-6, m}$	$v_{n, m-6}$	$v_{n, m}$

さらにプレイヤー2がG,C,Pを出す確率を$q_G, q_C, q_P$とし、プレイヤー1がG,C,Pを出すときの期待利得がそれぞれ$v_{n,m}$となり一致することから、各$v_{n,m}$に対して以下の４式が成り立つ。

\begin{align}
v_{n,m} &= q_Gv_{n,m}+q_Cv_{n-3, m}+q_Pv_{n, m-6} \\
v_{n,m} &= q_Gv_{n, m-3}+q_Cv_{n,m}+q_Pv_{n-6, m} \\
v_{n,m} &= q_Gv_{n-6, m}+q_Cv_{n, m-6}+q_Pv_{n,m} \\
1 &= q_G+q_C+q_P
\end{align}

また、$v_{n,m}$について、$n<0$のとき自身は既にゴールしているので$v_{n,m}=1$となり、反対に$m<0$のとき相手は既にゴールしているので$v_{n,m}=-1$となる。またこの2つが同時に起こることはないが、

以上の漸化式を各$n,m$について立て、階段の段数を$N$として$4N^2$個の式から各$n,m$の期待値、グーチョキパーを出す割合について求めれば、基本的に解が求まるということになる。

工夫

計算を単純にするため、3歩=1歩と考える。
式を$3nm$個に減らすため、$q_P=1-q_G-g_C$とおく。

非線形連立方程式の解法

今回非線形連立方程式を数値的に解くにあたって、Pythonのscipy.optimize.rootというモジュールを使用した。モジュールの使い方についてはこちらの記事を参考にした。

optimize.rootは、第一引数に関数、第二引数に初期値となる変数のリスト(スカラー値ベクトル)をとる。第一引数にはどのような関数を設定すれば良いかというと、変数のリストを引数とし、変数のリストを求めたい連立方程式に代入した結果の数値リストを戻り値とすることが求められる。そしてoptimize.rootは、このときの結果の数値リストをなるべく0に近づけるような変数のリストを計算してくれる。

結果

ゴールまでの歩数と期待値について3Dプロットした結果を以下に示す。

プロットについてはこちらのサイトを参考にした。

期待利得はこのゲームにおいてナッシュ均衡となる混合戦略をとったとき、勝てるor負ける可能性について示している。期待利得$E$と勝つ可能性$p$の関係式は以下で示される。

$$p = \frac{1}{2}(1+E)$$

期待利得が0.5であれば75%の確率で勝つことができ、逆に-0.8であれば90%の確率で負けることを示している。期待利得が0のときは勝つ確率も負ける確率も同じ(=50%)ということである。

まず結果の妥当性について議論する。このゲームにおける歩数と期待値との関係のうち、自明なものがある。

自分と相手の残り歩数が同じとき期待利得は0
残り歩数が自分の方が多いとき期待利得は負、逆に相手の方が多いときは正
自分の残り歩数が相手に比べて遥かに多いとき、ほぼ勝ち目がない(期待利得は-1に近づく)

3つ挙げたが、実際に求めた結果を見る限りその通りになっている。だから確実に大丈夫ってわけでもないが、多分ちゃんとできてそうだということがわかる。

より詳細な分析

出す手の優先度によって色付け

期待利得だけ知ることができても、どの手を優先して出せば良いかがわからなければ実践では使えない。そこで、先程の棒グラフに出すべき手の優先度の高さによって色付けしてみた。進化したグラフを以下に示す。

赤、緑、青はそれぞれグー、チョキ、パーを示す。
例えば残り歩数が自分=1、相手=2のときは緑が強調されている＝チョキを優先して出すのが最適戦略になるということである。これは多分、このとき相手にチョキかパーを出されて負けると一気に二歩分進まれて負けてしまうため、グーでしか勝てないチョキの優先度が高いのだと説明できる。

全体的に負けてる時ほどグー、勝っているときほどチョキの優先度が高いように見える。

求解の高速化

連立方程式の求解は解く方程式の数が多くなるほど時間がかかり、精度が悪くなる。そこで、連立方程式を少数ずつのブロックに分け解くことで効率化を図る。

$v_{n,m}$、$q_G(n,m)$、$q_C(n,m)$を求めるための3つの方程式

\begin{align}
v_{n,m} &= q_Gv_{n,m}+q_Cv_{n-1, m}+(1-q_G-q_C)v_{n, m-2} \\
v_{n,m} &= q_Gv_{n, m-1}+q_Cv_{n,m}+(1-q_G-q_C)v_{n-2, m} \\
v_{n,m} &= q_Gv_{n-2, m}+q_Cv_{n, m-2}+(1-q_G-q_C)v_{n,m}
\end{align}

を一纏めのブロックとし、「$v_{n,m}$のブロック」と呼ぶことにする。

$v_{n,m}$のブロックは、$v_{n,m}$より添字の小さな$v$($v_{n-1,m}$や$v_{n,m-1}$など)が既に求められていた場合数値解を求めることが可能である。例えば$v_{1,1}$は、$v_{0, 1}=1$、$v_{-1,1}=1$、$v_{1,0}=-1$、$v_{1,-1}=-1$なので、他の$v_{n,m}$を求めることなく数値解を求めることができる。

このような方法で$N=100$として求めた結果を以下に示す。