じゃんけんのナッシュ均衡は1/3ずつと決まっている。学習させたら均衡から3,050倍遠ざかり、最後は手が完全に読めるようになった
ゲーム理論を習うと、必ずナッシュ均衡が出てくる。誰も自分だけ手を変える理由がない状態で、じゃんけんなら「グー・チョキ・パーを1/3ずつ」がそれにあたる。
そして、たいていこう説明される。
合理的なプレイヤーが互いに学習していけば、やがてナッシュ均衡に落ち着く。
均衡が「行き着く先」として語られている。ナッシュの定理が保証しているのは存在だけなのに、いつのまにか到達の話にすり替わっている。
では、実際に学習させたらどこへ行くのか。じゃんけんで200,000手ぶん回したら、均衡から3,050倍遠ざかった。実験に使ったコードの全文はGitHubに置いています。
じゃんけんの均衡は、確かに1/3ずつしかない
まず前提のほうを固めておく。
じゃんけんに「これを出しておけば損しない」という一手はない。グーを出すと決めた瞬間、相手はパーを出せばいい。パーに決めれば、相手はチョキ。どの一手も、必ずそれを狩る手がある。
なので均衡があるとすれば、手を確率で混ぜるしかない。相手がグー・チョキ・パーを1/3ずつで出してくるなら、こちらが何を出しても勝率は等しく、有利な手が存在しない。だから自分も1/3ずつでいい。これがじゃんけんの唯一のナッシュ均衡で、1/3という数字は計算するまでもなく対称性から出る。
ここまでは疑いようがない。問題は、学習でそこに行けるのかのほう。
測り方
2人のプレイヤーに、それぞれ3つの手の確率を持たせる。毎手このように更新する。
- 相手の現在の確率に対して、自分の各手の期待利得を計算する
- 期待利得の高い手ほど、確率を指数的に大きくする
- 3つの確率の合計が1になるよう正規化する
いわゆる指数重み更新(multiplicative weights)で、「勝てた手を、勝てた分だけ多めに出すようになる」を素直に式にしたものだ。刻み幅という1つのパラメータで、1手ぶんの反応の強さを決める。刻み幅が大きいほど、直前の結果に強く反応する。
この更新則を選んだ理由は2つある。オンライン学習の標準的な手法であることと、刻み幅を0に近づけた極限がレプリケータ方程式(生物の進化ダイナミクスで使う連続時間の式)になるので、同じコードで離散と連続の両方を見られること。
出発点は毎回同じ (0.40, 0.35, 0.25) と (0.30, 0.40, 0.30)。均衡の近くではあるが均衡そのものではない、という位置に置いた。ここから刻み幅だけを変えて200,000手ずつ回す。
均衡に近づかない。遠ざかる
3つの手の確率は合計1なので、状態は三角形の1点で表せる。真ん中がナッシュ均衡だ。
刻み幅を変えただけで、行き先がまったく違う。どれ一つとして中央の星に向かっていない。
均衡からどれだけ離れているかを数字にすると、こうなる。
| 刻み幅 | 開始時の隔たり | 200,000手後 | 倍率 | 最後に最も高かった手の確率 |
|---|---|---|---|---|
| 0.2 | 0.0528 | 160.92 | 3,050倍 | 1.0000 |
| 0.05 | 0.0296 | 38.04 | 1,287倍 | 1.0000 |
| 0.01 | 0.0284 | 2.554 | 90倍 | 0.8803 |
| 0.002 | 0.0283 | 0.037 | 1.3倍 | 0.3817 |
隔たりは均衡との KL ダイバージェンスで測っている。刻み幅0.2では確率1.0000、つまり混ぜるのをやめて一手を出し切るところまで行った。じゃんけんで手が固定されるというのは、最悪の状態だ。
動かすと何が起きているのかがはっきりする。
赤い点は外へ広がって、最後は三角形の辺の上を移動している。辺の上にいるということは、3つのうち1つの手の確率がほぼ0ということだ。グー、パー、チョキ、と順番に出すだけの機械になっている。
学習した結果として、じゃんけんで最もやってはいけない状態に到達した。
「いま出す手」は読まれる。読まれないのは平均だけ
ところが、青い点は星から動かない。ここまでに出した手の平均を取ると、均衡にぴたりと乗っている。
| 刻み幅 | 200,000手の平均 (グー, パー, チョキ) |
|---|---|
| 0.2 | (0.3320, 0.3344, 0.3336) |
| 0.05 | (0.3335, 0.3320, 0.3345) |
| 0.01 | (0.3339, 0.3335, 0.3326) |
| 0.002 | (0.3335, 0.3333, 0.3332) |
どれも1/3ずつだ。軌道は均衡から3,050倍遠ざかりながら、その平均は均衡に収束している。
これがどれくらい違うのかを、実利で測ってみる。手の内が相手に完全に読まれたとき、どれだけ搾取されるか(exploitability)を計算する。ナッシュ均衡なら0で、じゃんけんで一手に決め打ちしていると2.0が最大値になる。
刻み幅0.05では、いま出している手の読まれやすさは2.000。理論上の最大値で、読まれたら必ず負ける。同じ試行の時間平均は0.00406で、ほぼ無敵だ。
つまりこの学習は、「均衡を見つける」ことには成功していて、「均衡を打つ」ことには失敗している。見つけた答えは記録の中にしかなく、プレイヤー自身は一度もその答えを打っていない。
刻み幅を小さくすれば直る、わけではない
表を見ると、刻み幅を小さくするほど離れ方が緩やかになっている。ならば0に近づければ均衡に落ち着くのでは、と考えたくなる。
刻み幅0.0005で400,000手回してみた。この更新則は刻み幅を0に近づけるとレプリケータ方程式に一致するので、実質的に連続時間の挙動になる。
結果は、均衡へ寄りもしなければ離れもしなかった。3つの確率の積(この系の保存量)は 0.03500 から 0.03617 へ 3.4% ずれただけで、これは数値誤差の範囲だ。確率は0.234から0.440の間を往復し続け、読まれやすさは0.137から0.258を行ったり来たりして、平均0.207。一度も0に触れていない。
閉じた輪をひたすら回っているだけで、均衡は輪の中心にあり、通り過ぎることすらない。
刻み幅を大きくすると外へ広がり、0に近づけると同じ場所を回る。離れないようにはできても、近づけることはできない。
外へ広がるほど、一周が遅くなる
螺旋のもう一つの性質として、周期が伸びていく。「最も確率の高い手」が3回入れ替わるのを1周と数えて、周ごとに何手かかったかを測った。
刻み幅0.2では1周56手から2,902手へ、51.8倍に伸びた。外側の輪ほど大きいので当然にも見えるが、これは「そのうち落ち着く」の逆を意味している。回るのが遅くなるだけで、回るのはやめない。
刻み幅0.002の緑の線だけが水平なのが、前の節の閉じた輪に対応している。5,535手から5,560手、35周してほとんど変わらない。
刻み幅を自分で切り替えて、最初の20周ぶんの軌道を見比べられるようにした。拡大すると内側から外側へ順に巻いているのが見えるし、線にカーソルを合わせれば何手目かが出る。
同じ学習則でも、辿り着くゲームはある
ここまでだと「学習は均衡に着かない」という一般論に見えるが、それは言いすぎだ。同じコード、同じ更新則のまま、ゲームだけ差し替えてみる。
囚人のジレンマでは、裏切り確率0.1から始めて107手で99%に達し、そのまま(裏切り, 裏切り)の均衡に張りついた。振動も逆戻りもない。
協調ゲーム(2人が同じ方を選べば得、選ぶ先が2つある)では、初期値121×121通りを全部回して、どちらの均衡に落ちるかを地図にした。73.3%が利得2の均衡へ、26.7%が利得1の均衡へ。どちらも均衡には辿り着く。ただしどちらに着くかは出発点で決まるので、「学習の結果、良いほうが選ばれる」わけではない。
3つのうち2つは均衡に着いた。着かなかったのはじゃんけんだけだ。
違いは利害の構造にある。囚人のジレンマも協調ゲームも、相手の手が分かれば自分の最善手が固定される。じゃんけんだけは、相手に合わせて手を変えると相手もそれに合わせて変えてくるので、追いかけっこが閉じない。ゼロ和で、勝ちが循環しているゲームでだけ起きる現象だ。
これはGANを一から実装したときに見たものと同じ構造でもある。あのときは損失が理論値に収束したのに生成分布が最後まで揃わなかった。生成器と識別器も、勝ちが循環する2人ゲームだ。
この実験で言えないこと
3つほど、正直に線を引いておきたい。
時間平均が均衡に収束すること自体は、既知の結果だ。ゼロ和ゲームでは学習の経験分布が均衡に近づくことが1950年代から知られている。この記事がやったのはその実測と、同時に軌道のほうは離れていくという対比を1枚の絵にしたところまで。
周期の測り方は粗い。「最も確率の高い手が3回入れ替わったら1周」という数え方なので、図3の細かいギザギザは実際の物理量ではなく数え方のブレを含んでいる。傾きの向きは信用してよいが、個々の値を精密なものとして読まないでほしい。
現実の人間はこの更新則で学習していない。指数重み更新は数学的に扱いやすい理想化で、記憶の減衰も、相手の癖の読みも、飽きも入っていない。ここで示せたのは「素直な学習則ではこうなる」までで、人間のじゃんけんがこうだという話ではない。
均衡は、行き先ではなく重心だった
この実験でいちばん意外だったのは、200,000手ぶんの手が最悪(読まれたら必ず負ける)なのに、その平均は最善(誰にも付け込まれない)だった、という食い違いだ。
均衡は行き着く先ではなく、回り続けたときの重心として現れていた。存在は保証されているが、そこに立てるとは誰も言っていない。ゲーム理論の教科書が「均衡が存在する」で止めているのは、たぶん正確さのためだったのだと思う。
ついでに言えば、この螺旋は「相手の直前の出方に強く反応するほど大きくなる」。刻み幅0.2は3,050倍離れ、0.002は1.3倍で済んだ。素早く適応することが、そのまま読まれやすさに変わっていた。相手の出方に合わせて自分を変えるのが速い人ほど、次に何をするか予測しやすくなる——というのは、じゃんけんの外でも心当たりがなくもない。
関連記事
このブログでは、機械学習の仕組みを実際にコードで実装して確かめた実験をテーマ別に整理しています（拡散モデル・Transformer・強化学習・多様体学習・過学習など）。