Chaos in learning a simple two-person game - AIエンジニアの探求

じゃんけんを題材にしたゲーム理論の論文 *1。シンプルなルールのゲームにおいて2人のプレイヤーがそれぞれ自分の戦略を良くしようとした結果、カオス的振る舞いが生じてしまうということが示されている。

じゃんけんにはナッシュ均衡*2というお互いのプレイヤーが最適な戦略をとっている状態があって、（グー、チョキ、パー）の出す確率を $\displaystyle \left(\frac{1}{3},\frac{1}{3},\frac{1}{3} \right)$ にしてランダムに出すという戦略がそれにあたる（お互いがこの戦術をとった場合、自分がこの戦略からずらしても勝率を高めることができない。そこでお互いはこの戦術から変えないため、一種の膠着状態的な安定性を持つ）。

実際AとBが戦う場合を考えると、A: $\displaystyle \left(\frac{1}{3},\frac{1}{3},\frac{1}{3} \right)$ 、B: $\displaystyle \left(\frac{1}{3},\frac{1}{3},\frac{1}{3} \right)$ のときに例えばBが $\displaystyle \left(\frac{1}{3}+2\epsilon,\frac{1}{3}-\epsilon,\frac{1}{3}-\epsilon \right)$ と自分の出す手を変えても勝率は

$\displaystyle \frac{1}{3} \times \left(\frac{1}{3}+2\epsilon \right)+ \frac{1}{3} \times \left(\frac{1}{3}-\epsilon \right)+\frac{1}{3} \times \left(\frac{1}{3}-\epsilon \right) = \frac{1}{3}$

となって変わらない。一方、Aが例えば $\displaystyle \left(\frac{1}{4},\frac{1}{4},\frac{1}{2} \right)$ みたいな出し方をしてきた場合Bはチョキばかり出すことで勝率を高められる。

(グー、チョキ、パー)= $\displaystyle \left(\frac{1}{3},\frac{1}{3},\frac{1}{3} \right)$ がナッシュ均衡になっているのはまあ自然だし、実際十分賢いプレイヤー（例：私達）ならこの戦略をとると思う。では、あらかじめ最適戦略を知らないプレイヤー同士が戦う場合はどうか？果たしてナッシュ均衡に到達することはできるのか？という問いが出てくる。

上記の問いを考えるために、ここでは強化学習的な戦術の学習を導入している。(グー、チョキ、パー)のうち出してみてうまく行った手（勝ちやすい手）はより出しやすくして、うまく行かなかった手（負けやすい手）は出す確率を減らす、みたいな感じのシンプルなルールを適用していく。

これを定式化したのが次の式。

$\dot{\textbf{x}}_i = x_i [(A\textbf{y})_i - \textbf{x}A\textbf{y}$ ] (1)

$\dot{\textbf{y}}_i = y_i[(B\textbf{x})_i - \textbf{y}B\textbf{x}$ ] (2)

ここで、 $\textbf{x}=(x_1,x_2,x_3),\textbf{y}=(y_1,y_2,y_3)$ はそれぞれプレイヤー2人の出す手の確率、A,Bはpayoff matrix（利得行列）を表している。

payoff matrixは対戦表みたいなもので、自分と相手の出す手の組み合わせによって得られる利得がいくらかを記したもの（勝ちは1,負けは-1)。

f:id:tripdancer0916:20171219075924p:plain

ここで、 $\epsilon$ は引き分けの時の報酬で、普通のじゃんけんだと0になる。

$(A\textbf{y})_i$ は相手が $\textbf{y}$ という戦術で来た時の戦略iの利得の平均、そして $\textbf{x}A\textbf{y}$ は相手が $\textbf{y}$ という戦術できたとき、自分が $\textbf{x}$ という戦術をとったときの平均を表している。

初期値 $\textbf{x}_0,\textbf{y}_0$ をいくつか定めて(1),(2)によってその後の出す目の確率の軌道を計算し、超平面 $x_2 - x_1 + y_2 - y_1 = 0$ を通る時のポアンカレ写像は次のようになる。

f:id:tripdancer0916:20171219205559p:plain

（Yuzuru Sato et al.(2002)より引用）

ナッシュ均衡に落ちることができないのは、この力学系がハミルトン系だから（論文のNoteに詳しく書いてある）で、軌道はトーラスを描く。

そして本題はここからで、 $\epsilon$ を変えてみる。このときゲームのゼロ和性を保つために $\displaystyle \epsilon_x = - \epsilon_y = \epsilon$ にする。

この片方が有利になるようなルールに変えた時、 $\textbf{x},\textbf{y}$ の軌道はカオス的になるという。

ポアンカレ写像は次のようになる( $\epsilon=0.5$ )。残っているトーラスもあるけど、いくつかは崩壊してめちゃくちゃに散らばっている。

f:id:tripdancer0916:20171219210100p:plain

（Yuzuru Sato et al.(2002)より引用）

この場合もハミルトン系なのは変わらないため、アトラクターは存在しない（から散逸系のカオスよりも軌道は複雑になる）。論文ではリアプノフ指数も計算していて、実際にこれがカオスであることが示されている。

単純なルールのゲームで、単純なルールの（しかも少数自由度の）力学系でこのような複雑な振る舞いをするのはやっぱり面白い。

*1:Sato Y, Akiyama E. & Farmer JD. Chaos in learning a simple two-person game. Proc. Nat. Acad. Sci. 2002 99(7): 4748–4751. https://doi.org/10.1073/pnas.032086299 PMID: 11930020

*2:Nash, J. F. (1950). Equilibrium points in n-person games. Proceedings of the National Academy of Sciences, 36(1), 48–49. https://doi.org/10.1073/pnas.36.1.48