最終講はケーススタディだ。強化学習がチェッカー、チェス、オセロ、バックギャモン、囲碁、ポーカーといった古典的ゲームでどのように人間を超えたかを見ていく。ゲームはルールが単純なのに概念は深く、何百年何千年と磨かれてきて、知能の意味ある試金石になる。シルバーの表現では人工知能のショウジョウバエ（drosophila）だ。ショウジョウバエが遺伝学の標準的な実験動物であるように、ゲームは現実の問題を小さく圧縮した実験室になる。そして何より、ゲームは面白い。
講義スライド: PDF
ここまで到達した水準
講義の冒頭は現状ボードだ。チェッカーは完全（perfect）水準で解かれ、チェス・オセロ・バックギャモン・スクラブル・ポーカーは超人（superhuman）水準、囲碁は（この講義時点で）グランドマスター水準だった。各頂点を打ち立てたプログラムがChinook（チェッカー）、ディープブルー（チェス）、Logistello（オセロ）、TD-Gammon（バックギャモン）、Maven（スクラブル）、MoGo・Crazy Stone・Zen（囲碁）、Polaris（ポーカー）だ。
興味深いのはその隣に並ぶ二つ目の表だ。「この頂点を強化学習で成し遂げたプログラムは何か」を別に抜き出すと、リストが少し変わる。チェスではディープブルーの代わりにKnightCap・Meepが、ポーカーではPolarisの代わりにSmooCTが入ってくる。強化学習だけで最高水準に上ったチェスプログラムはまだインターナショナルマスター程度で、その他はほとんど強化学習が頂点を占めた。この講義はまさにその強化学習の系譜をたどる。
ゲーム理論：最適応答とナッシュ均衡
複数人で競うゲームで「最適方策」とは何だろうか。自分一人の問題ではなく相手がいるので、最適は相手が何をするかにかかっている。
核心となる観察はこうだ。他のすべての参加者が自分の方策 $\pi^{-i}$ を固定してしまえば、その瞬間、相手はもはや知的な敵ではなく単なる環境の一部になる。相手が決まったルールどおりにしか動かない壁なら、残るのは自分一人でその壁を相手に報酬を最大化する問題だ。つまりゲームが一つのMDPに縮約される。このとき自分の最適応答（best response）$\pi^{i}_*(\pi^{-i})$ とは、まさにそのMDPの最適方策だ。多人数ゲームが単一エージェント強化学習問題へと畳み込まれるわけだ。
さて、全員が同時に最善を尽くすなら、どんな状態に至るだろうか。すべての参加者の方策を一つにまとめた結合方策 $\pi$ があり、
$$\pi^{i} = \pi^{i}_*(\pi^{-i}) \quad \text{すべての } i \text{ について}$$つまり各自の方策が残り全員に対する最適応答になれば、誰も一人で変えて得をすることはできない。この状態がナッシュ均衡（Nash equilibrium）だ。
ここで講義の一つ目の大きな絵が現れる。ナッシュ均衡は自己対戦（self-play）強化学習の不動点だ。複数のエージェントが互いに対戦しながら経験を積み（$a^1 \sim \pi^1$, $a^2 \sim \pi^2$, …）、各自が相手に対する最適応答を学ぶ。ところが一人の方策がすなわち他者の環境を決めるので、全員が同時に互いに合わせて適応していく。この鬼ごっこが止まる地点、つまり誰ももう変えるものがないその不動点こそがナッシュ均衡だ。
この講義はその中でも特殊な部類、二人ゼロサムゲームに集中する。二人が交互に打ち（白と黒と呼ぼう）、黒と白の報酬がちょうど反対で $R^1 + R^2 = 0$ だ。自分が勝つ分だけ相手が負ける。このゲームでナッシュ均衡を見つける二つの道がゲーム木探索（プランニング）と自己対戦強化学習であり、この講義の骨格がその二つだ。
もう一つの軸がある。盤がすべて見えれば完全情報（マルコフ）ゲームだ（チェス、チェッカー、オセロ、バックギャモン、囲碁）。相手の手札が隠されていれば不完全情報ゲームだ（スクラブル、ポーカー）。まず完全情報ゲームから見る。
ミニマックス探索
二人ゼロサムゲームの古典的解法はミニマックスだ。結合方策 $\pi = (\pi^1, \pi^2)$ が与えられれば価値関数はいつもどおり $v_\pi(s) = \mathbb{E}_\pi[G_t \mid S_t = s]$ だ。ミニマックス価値関数は白の期待リターンを最大化すると同時に黒の期待リターンを最小化する。
$$v_*(s) = \max_{\pi^1} \min_{\pi^2} v_\pi(s)$$この値を達成する結合方策がミニマックス方策だ。そして講義が指し示す二つ目の橋がここにある。ミニマックス方策はナッシュ均衡だ。先のゲーム理論とここの探索が同じ地点を指すという意味だ。ミニマックス価値関数は一意だ。
ミニマックス値は深さ優先ゲーム木探索で求める。自分の番では値を最大に、相手の番では最小に選び、リーフから根へ値を引き上げる。歴史的にこのアイデアはクロード・シャノンが1950年の論文「チェスを指すコンピュータのプログラミング」で提示した。コンピュータがなく、紙の上で回した。
問題は木が指数的に爆発することだ。最後まで読むのは現実的に不可能だ。そこで一定の深さまでだけ読み、その下のリーフノードの値は価値関数近似器 $v(s, \mathbf{w}) \approx v_*(s)$ で概算する。これを評価関数またはヒューリスティック関数と呼ぶ。ミニマックス探索は固定された深さまで降りたあと、リーフの近似値を基準に上へ値を上げる。
二値線形価値関数
リーフの値を付ける最も単純でありながら強力な形が二値線形価値関数だ。講義の結論レシピが結局この一行に収束するので、ここがこの講義の骨格だ。
駒一つごとに特徴一つを置いた二値特徴ベクトル $\mathbf{x}(s)$ を作る（例：「このマスにこの駒があるか」を0か1で）。重みベクトル $\mathbf{w}$ の各成分はその駒の価値だ。すると盤の評価値は、点いている（active）特徴の重みを足したものだ。
$$v(s, \mathbf{w}) = \mathbf{x}(s) \cdot \mathbf{w}$$チェスでいえば自分のポーンが一つあれば $+1$、相手のナイトが一つあれば $-3$ のように、点いた特徴の重みを次々に足して一つのスコアにする。人が手で「駒の価値」を付けていた古い直観が、まさに一つの線形関数として表現されるのだ。この単純な枠が講義全体を貫く。
ディープブルー
ディープブルーはこの枠を人の手先で極限まで押し進めた事例だ。
- 知識：約8000個の手作りチェス特徴を持つ二値線形価値関数。重みの大部分を人間の専門家がチューニングした。
- 探索：高性能な並列アルファベータ探索。チェス専用VLSIチップ480個で毎秒2億局面を読み、16から40プライ先を見通した。
- 結果：1997年、世界チャンピオンのガルリ・カスパロフを4対2で破った。当時インターネット史上最も多く視聴されたイベントだった。
ディープブルーには強化学習がない。人が組んだ評価関数に圧倒的な探索を乗せた、手工の頂点だ。
Chinook
チェッカーのChinookも最初は手チューニング系だった。
- 知識：二値線形価値関数。21個の知識ベース特徴（位置、機動性など）をゲームの4段階（phase）別に分けて使った。
- 探索：高性能なアルファベータ探索。そこに後退解析（retrograde analysis）を乗せた。勝った局面から逆向きに探索し、勝つすべての局面を照会テーブルに保存する。すると駒が数個残る終盤は完璧に指す。
- 結果：1994年、世界チャンピオンのマリオン・ティンズリーとの対決で2局を勝ち、ティンズリーが健康問題で棄権した。
そして2007年、Chinookはチェッカーを完全に解いた。神を相手にしても負けない完全対局だ。ここで注意すべき点が一つ。この完全解決版Chinookの核心は手チューニング重みと後退解析によるエンドゲームデータベースであって、後で出てくるTDリーフ学習ではない。TDリーフは後から付いた後期バージョンの話だ（後の節で再び出てくる）。
自己対戦強化学習
さて、人が評価関数を組んでやる代わりに、強化学習で学ばせよう。自分自身と対戦して得た経験で価値関数 $v(s, \mathbf{w})$ を更新する。第4講で見た予測アルゴリズムがそのまま使われる。
- MC：リターン $G_t$ に向けて更新する。$\Delta\mathbf{w} = \alpha(G_t - v(S_t, \mathbf{w}))\nabla_\mathbf{w} v(S_t, \mathbf{w})$
- TD(0)：次状態の値 $v(S_{t+1})$ に向けて更新する。$\Delta\mathbf{w} = \alpha(v(S_{t+1}, \mathbf{w}) - v(S_t, \mathbf{w}))\nabla_\mathbf{w} v(S_t, \mathbf{w})$
- TD(λ)：λリターン $G_t^\lambda$ に向けて更新する。$\Delta\mathbf{w} = \alpha(G_t^\lambda - v(S_t, \mathbf{w}))\nabla_\mathbf{w} v(S_t, \mathbf{w})$
自己対戦が魅力的な理由は、カリキュラムがひとりでに回るからだ。相手がすなわち自分自身なので、自分の実力が上がれば相手も一緒に強くなる。果てしなく難しくなる難易度を人が設計してやる必要がない。
アフターステートで方策を改善する
ここにゲーム特有の近道が一つある。決定論的ゲームでは $v_*(s)$ だけ学べば十分だ。状態行動価値 $q_*(s, a)$ を別途学ぶ必要がない。
理由はアフターステート（afterstate）にある。ゲームのルールがすでに後続状態 $\text{succ}(s, a)$ を決めてくれるので、行動 $a$ の価値はその行動が作る盤の価値と等しい。
$$q_*(s, a) = v_*(\text{succ}(s, a))$$自分がある手を打つと盤がどうなるかはルールさえ知っていれば即座に分かるので、「手の価値」を学ぶ必要なく「盤の価値」だけ学べばよい。だから行動はアフターステート値を最大化（または相手なら最小化）して選ぶ。
$$A_t = \arg\max_a v_*(\text{succ}(S_t, a)) \quad (\text{白}), \qquad A_t = \arg\min_a v_*(\text{succ}(S_t, a)) \quad (\text{黒})$$この一度の選択が白と黒の両方の結合方策を同時に改善する。
オセロのLogistello
Logistelloが印象的なのは特徴を自分で作ったという点だ。「C1に黒石があるか」のような生の入力特徴から出発し、それらを論理積・論理和で織り合わせて新しい特徴を作り出した。そうして異なる構成で150万個に及ぶ特徴を作り、その上に二値線形価値関数を乗せた。
学習は一般化方策反復だった。現在の方策で自己対戦を一束作り、その結果（勝敗）でモンテカルロ回帰して方策を評価したあと、貪欲改善で新しいプレイヤーを作る。結果は世界チャンピオンの村上健を6対0で破った。
バックギャモンのTD-Gammon
TD-Gammonはこの講義で最も有名な里程標だ。ここでは線形関数の代わりに非線形ニューラルネットワークが盤を評価した。
- ランダムな重みで初期化する（事前知識0）。
- 自己対戦で学習する。
- 非線形時間差学習を使う。$\delta_t = v(S_{t+1}, \mathbf{w}) - v(S_t, \mathbf{w})$, $\Delta\mathbf{w} = \alpha\delta_t \nabla_\mathbf{w} v(S_t, \mathbf{w})$。
- 貪欲な方策改善だけをした（探索なし）。
ここに特異な箇所が一つある。探索の仕掛けなしに純粋な貪欲で学習したのに、実際にいつも収束した。理論的には探索があるべきに思えるが、バックギャモンでは大丈夫だった。理由はサイコロだ。毎手ごとにサイコロがランダム性を撒いてくれるので、アルゴリズムが探索を別途しなくても盤がひとりでに多様に散らばったのだ。講義も「他のゲームではこうではなかった」と指摘する。
結果は一つの知識のはしごに要約される。
- 専門家知識0 $\Rightarrow$ 中級の実力
- 手作り特徴を追加 $\Rightarrow$ 上級の実力 (1991)
- 2プライ探索 $\Rightarrow$ 強いマスター級 (1993)
- 3プライ探索 $\Rightarrow$ 超人の実力 (1998)
そして1992年、世界チャンピオンのルイジ・ヴィラを7対1で破った。何の知識もなく自分自身とだけ打って上りつめたはしごだ。
強化学習とミニマックス探索を織り合わせる
TD-Gammonでは学習中に単純な貪欲行動選択で十分だった。ところが残念ながらこれがどこでも通じたわけではない。代表的にチェスがそうだ。
前節の方式、つまり単純TD（次状態の値で現在の値を更新すること）をゲームごとに回してみると成否が分かれた。オセロ（Logistello）とバックギャモン（TD-Gammon）では超人水準が出たのに、チェスとチェッカーでは成績が悪かった。
なぜか。チェスは戦術があってこそ盤から信号を見つけられるからだ。例えばチェックメイトは探索なしにただ盤を見るだけではなかなか気づきにくい。良い位置にあるように見える盤が数手後に詰みで崩れるのに、静的な評価関数はそれを見られない。結論はこうだ。次状態の値ではなく、探索で得た値で学ぶべきだ。
ここで三兄弟が登場する。三つを見分ける鍵はただ一つ、「何を何で更新するか」だ。
TDルート
TDルートは次状態の探索値で現在状態の値を更新する。根の位置 $S_t$ で探索値を計算する。
$$v_+(S_t, \mathbf{w}) = \min\max_{s \in \text{leaves}(S_t)} v(s, \mathbf{w})$$そして次状態の探索値で現在の値を引き寄せる。$v(S_t, \mathbf{w}) \leftarrow v_+(S_{t+1}, \mathbf{w}) = v(l_+(S_{t+1}), \mathbf{w})$。ここで $l_+(s)$ は $s$ でミニマックス値を達成するリーフノードだ。
これがサミュエルのチェッカープレイヤー（1959）で、史上初のTD学習アルゴリズムだ。自己対戦で学んでアマチュアの人間を破った。今見ると奇妙な他のアイデアも一緒に使った。
TDリーフ
TDリーフは現在の探索値を次ステップの探索値で更新する。TDルートと違い、今と次、両方で探索値を計算する。
$$v_+(S_t, \mathbf{w}) \leftarrow v_+(S_{t+1}, \mathbf{w}) \quad\Longrightarrow\quad v(l_+(S_t), \mathbf{w}) \leftarrow v(l_+(S_{t+1}), \mathbf{w})$$チェスのKnightCapがこの方式だ。専門家相手に訓練し、標準の駒の値から出発してTDリーフで重みを学んだ。アルファベータ探索に標準的な改善を乗せ、少ない対局でマスター水準に上った。ただし二つの限界があった。自己対戦ではうまくいかず、良い初期重みから出発しないとうまくいかなかった。
先で先送りにした話がここで閉じる。チェッカーのChinookはもともと手チューニング重みを使ったが、後期バージョンは自己対戦で訓練しTDリーフで重みを調整した（駒の値だけは固定したまま）。そうして学んだ自己対戦の重みが手チューニング重み以上の性能、つまり超人水準を出した。先に「完全解決版ChinookはTDリーフではない」と強調した理由がこれだ。TDリーフはこの後期バージョンの話だ。
TreeStrap
TreeStrapは探索値を同じ時点のより深い探索値で更新する。TDルート・リーフが時間をまたいで（次ステップの値で）学んだのと違い、TreeStrapは同じステップ内で木のすべてのノードの値をその場の探索値へ引き寄せる。
$$v(s, \mathbf{w}) \leftarrow v_+(s, \mathbf{w}) \quad\Longrightarrow\quad v(s, \mathbf{w}) \leftarrow v(l_+(s), \mathbf{w}), \quad \forall s \in \text{nodes}(S_t)$$チェスのMeepがこの方式だ。2000個の特徴の二値線形価値関数を、ランダムな初期重みから（事前知識0）出発してTreeStrapで調整した。そしてKnightCapの二つの限界を越えた。自己対戦でも有効で、ランダムな初期重みでも有効だった。結果はインターナショナルマスターたちを相手に13勝15敗、いや13/15勝だ。
探索をシミュレーションで置き換える
もう一歩進めば、自己対戦強化学習が探索そのものを代わることができる。根の状態 $S_t$ から自己対戦をシミュレーションし、そのシミュレーション経験に強化学習を適用する。モンテカルロ制御をこうして木に乗せたものがモンテカルロ木探索（MCTS）で、最も効果的な変種が各ノードでUCBによって探索と活用を天秤にかけるUCTだ。
ここで第8講とこの講がつながる。自己対戦UCTはミニマックス値へ収束する（完全情報、ゼロサム、二人ゲームで）。MCTSは囲碁（前講）、ヘックス、ラインズ・オブ・アクション、アマゾンなど多くの難しいゲームで最高性能を出した。一方あるゲームでは木を立てない単純モンテカルロ探索だけでも十分だった（スクラブル、バックギャモン）。
スクラブルのMaven：単純モンテカルロ探索
Mavenは不完全情報の代表事例と誤解しやすいが、この講義でMavenはその「単純モンテカルロ探索」の事例として配置される。
- 学習：手を スコア + $v(\text{rack})$ で評価する。ここで $v(\text{rack})$ は手に残ったタイル（rack）の価値を付ける二値線形価値関数で、一文字・二文字・三文字の特徴を使う（Q??????, QU?????, III???? のように）。Logistelloのようにモンテカルロ方策反復で学んだ。
- 探索：自己対戦 $n$ ステップを想像するロールアウトで手を展開してみて、その結果の盤を スコア + $v(\text{rack})$ で評価する。ロールアウト平均評価で各手を採点し、最も高い手を選んで打つ。終盤はB*アルゴリズムで専用探索をする。
結果、Mavenは世界チャンピオンのアダム・ローガンを9対5で破った。ある対局では終盤をMOUTHPARTで締めくくると予測し、分析の結果、対局あたり3点程度の誤差しかなかった。
不完全情報ゲームの強化学習
さて、盤がすべて見えないゲームだ。ポーカーのように相手の手札が隠されると、参加者ごとに知ることが異なり、互いに異なる探索木を持つ。核心的な道具は情報状態（information state）だ。「自分が今まで見たカードは何か」のように、一人の参加者が知ることを要約したノードを情報状態ごとに一つ置く。実際には異なる複数の物理状態が同じ情報状態を共有し、値が似た状態をさらにまとめもする。
この情報状態ゲーム木を解く二つの道がある。
- 反復的前方探索：代表的に反実仮想後悔最小化（CFR, counterfactual regret minimization）だ。ヘッズアップリミットテキサスホールデムを事実上完全に解いた。
- 自己対戦強化学習：代表的にSmooth UCTだ。二人・三人リミットホールデムで銀メダル3個を取り、大規模前方探索エージェントたちを凌駕した。
Smooth UCT
Smooth UCTは情報状態ゲーム木にMCTSを適用したUCT変種で、ゲーム理論の仮想プレイ（fictitious play）から着想を得た。核心は相手の平均行動に反応するということだ。各ノードの行動カウントから平均戦略を取り出す。
$$\pi_{\text{avg}}(a \mid s) = \frac{N(s, a)}{N(s)}$$そして各ノードで確率 $\eta$ ではいつものようにUCTで、確率 $1 - \eta$ ではこの平均戦略 $\pi_{\text{avg}}$ で行動を選ぶ。
$$A \sim \begin{cases} \text{UCT}(S), & \text{確率 } \eta \\ \pi_{\text{avg}}(\cdot \mid S), & \text{確率 } 1 - \eta \end{cases}$$なぜこれが重要か。ポーカー変種では素朴なMCTSは発散した。相手が絶えず変わる標的を追ううちに自分たち同士で振動してしまったのだ。一方Smooth UCTは相手の平均戦略という安定した標的に反応し、ナッシュ均衡へ収束した。ゲーム理論から始まったこの講義が再びゲーム理論の不動点へ戻ってくるわけだ。
貫くもの：一つのレシピ
講義の結論は驚くほど単純だ。成功のレシピがゲームを横断してほとんど同じだったということだ。チェス（Meep）、チェッカー（Chinook）、オセロ（Logistello）、バックギャモン（TD-Gammon）、囲碁（MoGo）、スクラブル（Maven）、リミットホールデム（SmooCT）を一つの表に並べると共通点が際立つ。
- 二値特徴：駒、ポーン、円盤の配置、残った駒の数、石のパターン、ラック上の文字、カード抽象化。対象はゲームごとに違っても形は一様に二値だ。
- 価値関数：ほとんどすべて線形だ（TD-Gammonのニューラルネットワークだけが例外）。
- 自己対戦：学習は大部分が自分自身との対戦でなされた（KnightCapだけが専門家相手を添えた）。
二値特徴 + 線形価値関数 + 自己対戦。異なるゲームで異なる人々が到達した答えがこの一つに集まるというのが、この講義が残す絵だ。そこにミニマックス探索をどう織り合わせるか（アルファベータ、TDリーフ、TreeStrap、MCTS）がゲームごとの個性だったにすぎない。
一つだけ付け加えると、この講義より後に出たAlphaGoとAlphaZeroは、まさにこの系譜、自己対戦とMCTSの直系の後裔だ（シルバー本人が率いたプロジェクトだ）。方策・価値ニューラルネットワークと木探索を自己対戦で織り合わせて囲碁を征服したので、この講義が立てた骨格の上にディープラーニングを乗せたわけだ。ただしこれはスライドの範囲外の後続なので、ここでは一文だけで触れておく。
これでシルバー講義をたどった十講を終える。ここからシリーズは、資料記事で予告したとおり、PPOをはじめとするより新しい手法へ進む。