機械学習の知識がないけどゲームAIを作って唐揚げを大量に食べる

世は空前のAIブームである。DeepMind の AlphaGo が囲碁のトッププロを負かしてから5年、そのへんのコンビニでも「AI を利用した」「AI で設計した」という文字があふれるようになった。

自分も以前 TensorFlow のサンプルコードを丸写しして手書き文字認識のプログラムを書いたものだが、原理がよくわからないので「AI を作ってる感」がわかないし、機械を学習させているというより機械に学習させられている感が否めない。できれば複雑なライブラリを使わず、自分でゼロから作れる単純なもので「AI してる」という実感を得たい。

「AI してる」感とは何なのかといえば、おそらくAIの成長過程が見えることだろう。となればゲームAIがわかりやすい。自分の書いたプログラムが成長していくのは見ていて楽しいし、ゲームであればその成長が実感しやすい。

とはいえオセロやブロック崩しのようなものを作るのは手間なので、以下のようなシンプルな数取りゲームを考える。飲み会や家庭で頻繁に発生する心理戦をモデル化したものである。

・大皿に唐揚げが21個乗っている。
・2人のプレイヤーが交互に、唐揚げを1〜4個取って食べる。
・最後の1個を食べると負け。
・敗者は「生意気」「図々しい」「遠慮を知らない」と後ろ指をさされながら残りの人生を日陰で過ごさねばならない。

最低でも1個食べねばならないのがポイントだ。つまり大皿に1個しかない状態で自分の手番が回ってきたら「詰み」となる。逆に、3個残っていればその時点で勝利を確定できる。2個食べて相手に回せばいい。

ゲームをAIに学習させるためには、まずゲーム自体をプログラムしなければならない。ひとまず自分とCPUが対戦するコードを書いてみた。プログラミング入門書の3章くらいでよく出る何ひとつ面白くないゲームである。

唐揚げが21個あります。
何個食べますか？ (1, 2, 3, 4) 
> 3
CPUは2個食べました。残りは16個です。
何個食べますか？ (1, 2, 3, 4)
> 4
CPUは3個食べました。残りは9個です。
何個食べますか？ (1, 2, 3, 4)
> 3
CPUは4個食べました。残りは2個です。
何個食べますか？ (1, 2, 3, 4)
> 1
CPUは1個食べました。残りは0個です。
あなたの勝ちです。

このCPUは何の戦略もなく1〜4の数字をランダムに選ぶだけなので、勝利するのは容易い。

ご存知の方も多いだろうが、このゲームは後手必勝である。先手がn個を食べるたびに、後手は(5-n)個を食べればいい。そうすれば唐揚げは5個ずつ減るので、4ターン後には1個だけ残った状態で先手番になり、先手番の負けが確定する。

今回のテーマは「AI はこの必勝法を発見できるか？」である。

もう少しマトモな言い方をすると、「プログラマが必勝法を直接入力せずとも、プレイ経験をもとに学習し、必勝法を発見するプログラムを作れるか？」である。

この唐揚げゲームにおいては「いま唐揚げは何個残っているか？」によって21通りの状態が存在する。プレイヤーの行動は「何個食べるか？」で各4パターンだ。つまり、21×4 = 84通りの行動が存在する。

そこで、コンピュータ同士の対戦で唐揚げを何皿も食べさせて、84通りの行動のどれが勝利につながるか、どれが敗北につながるか、を学習させることにしよう。最初はランダムに1〜4個から選ばせて、勝った行動パターンは高確率に、負けた行動パターンは低確率にしていく。

たとえば、「残り4個。何個食べるか？」を考えよう。初期状態ではAIはランダムで行動するので、

• 1個 → 25%
• 2個 → 25%
• 3個 → 25%
• 4個 → 25%

となっている。ここでAIが4個食べるとその瞬間に負けるので、「残り4個で4個食べるのは悪手のようだ」と学習し、確率が次のように改められる。

• 1個 → 30%
• 2個 → 30%
• 3個 → 30%
• 4個 → 10%

次のゲームで再び残り4個になった場合、この確率に従って行動が選択される。もしAIが3個を選べば確実に勝利するので、「残り4個なら3個食べるのが好手らしい」と学習し、また確率が変わる。

• 1個 → 25%
• 2個 → 25%
• 3個 → 45%
• 4個 → 5%

これを何度も繰り返せば、いずれ100%の確率で「残り4個なら3個食べる」と行動するようになる。これが1〜21個のすべての状態で起きれば、AI が必勝法を見出したことになるわけだ。

確率変更のアルゴリズムは色々なやり方がありそうだが、今回は単純さを重視して、以下のようにする。

• 負けたら、その行動を選択する確率を半分にする。
• 勝ったら、その行動を選択しない確率を半分にする。
• その後、確率の総和が1になるように正規化する。

というわけで適当にコードを書いて実行する。

【第1回戦】
先手は3個食べた。残り18個。
後手は3個食べた。残り15個。
先手は3個食べた。残り12個。
後手は3個食べた。残り9個。
先手は2個食べた。残り7個。
後手は3個食べた。残り4個。
先手は2個食べた。残り2個。
後手は4個食べた。残り-2個。
先手の勝利！
[[0.25       0.25       0.25       0.25      ]
[0.28571429 0.28571429 0.28571429 0.14285714]
[0.25       0.25       0.25       0.25      ]
[0.18181818 0.45454545 0.18181818 0.18181818]
[0.25       0.25       0.25       0.25      ]
[0.25       0.25       0.25       0.25      ]
[0.28571429 0.28571429 0.14285714 0.28571429]
[0.25       0.25       0.25       0.25      ]
[0.18181818 0.45454545 0.18181818 0.18181818]
[0.25       0.25       0.25       0.25      ]
[0.25       0.25       0.25       0.25      ]
[0.28571429 0.28571429 0.14285714 0.28571429]
[0.25       0.25       0.25       0.25      ]
[0.25       0.25       0.25       0.25      ]
[0.18181818 0.18181818 0.45454545 0.18181818]
[0.25       0.25       0.25       0.25      ]
[0.25       0.25       0.25       0.25      ]
[0.28571429 0.28571429 0.14285714 0.28571429]
[0.25       0.25       0.25       0.25      ]
[0.25       0.25       0.25       0.25      ]
[0.18181818 0.18181818 0.45454545 0.18181818]]

【第2回戦】
先手は4個食べた。残り17個。
後手は2個食べた。残り15個。
先手は3個食べた。残り12個。
後手は2個食べた。残り10個。
先手は3個食べた。残り7個。
後手は4個食べた。残り3個。
先手は1個食べた。残り2個。
後手は1個食べた。残り1個。
先手は1個食べた。残り0個。
後手の勝利！
[[0.14285714 0.28571429 0.28571429 0.28571429]
[0.47368421 0.21052632 0.21052632 0.10526316]
[0.14285714 0.28571429 0.28571429 0.28571429]
[0.18181818 0.45454545 0.18181818 0.18181818]
[0.25       0.25       0.25       0.25      ]
[0.25       0.25       0.25       0.25      ]
[0.21052632 0.21052632 0.10526316 0.47368421]
[0.25       0.25       0.25       0.25      ]
[0.18181818 0.45454545 0.18181818 0.18181818]
[0.28571429 0.28571429 0.14285714 0.28571429]
[0.25       0.25       0.25       0.25      ]
[0.21052632 0.47368421 0.10526316 0.21052632]
[0.25       0.25       0.25       0.25      ]
[0.25       0.25       0.25       0.25      ]
[0.23529412 0.23529412 0.29411765 0.23529412]
[0.25       0.25       0.25       0.25      ]
[0.18181818 0.45454545 0.18181818 0.18181818]
[0.28571429 0.28571429 0.14285714 0.28571429]
[0.25       0.25       0.25       0.25      ]
[0.25       0.25       0.25       0.25      ]
[0.2        0.2        0.5        0.1       ]]

【第3回戦】
...

1回戦では先手が初手で3個食べて勝ったので「どうやら21個の状態で3個食べると勝てるらしい」と学習し、確率を25%から45%まで上げた。2回戦初手で今度は初手4個食べたものの敗北し、「やはり初手は3個がいい」と判断したらしく50%まで上がった。一方、後手は「残り2個の状態で1個食べると勝つ」という極めて重要な経験をこの2回戦目にして取得。
（なお先手も後手も同一の戦略を使う）

10回戦が終了した時点での確率を見てみよう。数字だと見づらいのでヒートマップにする。

ゲーム内時間は左から右に進行し、白いマスほど高確率（＝使われやすい選択）である。この時点でまだ全体的な戦略は五里霧中だが、どうやら残り2個になったら1個食えということはほぼ理解（95%）しているらしい。2個時点で2個以上食べたら即負けなので、確率が1個に素早く収束するのは消去法にもとづく必然といえる。

30回戦が終了。どうやら終盤の戦略が固まってきたようで、うっすらと斜めの白いラインが見えつつある。すなわち「5個以下になったら、1個残して相手に回せ」である。10回戦の時点で「2個残したら負ける」がほぼ確実になっていたので、5個残った時点での戦略がそこから導出されたのだろう。

100回戦。ここにきて7〜10個状態にも明確な戦略が出来つつある。この白い斜線が示すのは「6個残して相手に回せ」である。6個を渡されるとたとえ何個食べても30回戦時点で見出した戦略を使われてしまう、ということをAIが理解している。刹那的な電子情報を送りあうシリコンの機械といえども100皿も唐揚げを食べ続ければコレステロールの海から長期的展望を獲得するのだ。

さあ、この先の展開はもう読者のみなさんにも見えているだろう。レモンを絞ってご照覧あれ。

お見事！ ここまで見つけたパターンがどんどん延長され、ついに序盤の行動パターンまで確定した。16個、11個、6個、1個と、5で割って1余る唐揚げを相手に渡せば勝てるのだ。このルールから演繹されることは、ゲームが21個で開始されている時点で先手の敗北は運命づけられていた、ということだ。唐揚げを300皿、すなわち6300個食べて見出した心理である。どうか2人の電脳勇士にあたたかな拍手を。

なお、これほど学習が進めば21個、16個、11個、6個、1個の時点で何をやっても負けが確定しているので、どの行動にもほぼ同じ確率が割り振られている。これはいわば「諦め」の境地と解釈すべきだろう。

さて、今回のような単純なアルゴリズムであっさり必勝法を見いだせたのは、ひとえにこのゲームが非常に単純だからである。なにしろ状態が21個しかないので、全パターンにスコアをつけることが可能なのである。

将棋だと盤面の状態は10の220乗くらいあるので、その全ての良し悪しを判断するのは到底不可能で、特徴量抽出といった作業や強力なマシンパワーが必要になるらしい。自分はそのあたりの知識がないので、科学技術と人間社会の展望を唐揚げ食べてビール飲みながら見守りたい。