# AlphaGo ## 概要 AlphaGo は [[DeepMind]] が開発したコンピュータ囲碁システムであり、2015年10月に囲碁の欧州チャンピオン Fan Hui(ファン・フイ)を破り、その半年後の2016年に世界トップ棋士の一人 Lee Sedol(イ・セドル)を5戦中4勝1敗で破った。当時、人とコンピュータ囲碁の実力差は数年〜10年はかかると考えられていたため、この勝利は業界に大きな衝撃を与えた。囲碁は候補手数の平均が250・深さの平均数が150と他のゲームに比べ盤面数が桁違いに多く(チェス $10^{120}$・将棋 $10^{200}$ に対し囲碁は $10^{300}$ 程度)、盤面評価の特徴設計も難しかったため、当時最もコンピュータが勝つのが難しいゲームの一つとされていた。(Source: [[@2022__Gihyo__ディープラーニングを支える技術〈2〉 - Chapter 4 深層強化学習]] §4.14, D. Silver and et al., "Mastering the game of Go with deep neural networks and tree search", Nature, 2016) ## AlphaGo の学習パイプライン AlphaGo は状態価値・行動価値・方策をニューラルネットワークでモデル化し、教師あり学習と強化学習を組み合わせた複数段階の学習を行う。各ネットワークは盤面(19×19のサイズの画像)を入力とし、CNNで特徴ベクトルに変換する。 1. **方策ネットワーク $\pi(a|s;\sigma)$ の教師あり学習**: オンライン囲碁 KGS の強いプレイヤーの対戦記録(16万局・3000万手)を使い、強い棋士の次の手を予測するように学習する。13層のネットワークで57%の精度を達成した。 2. **強化学習による方策の強化 $\pi_\rho(a|s;\rho)$**: 教師あり学習の方策で初期化した後、[[方策勾配法]]のREINFORCEで自己対戦させ、勝敗($z=\pm1$)を収益として学習する。人の棋譜を真似るだけでは元の棋士以上には強くなれないが、この強化学習のステップによって学習に使った手よりも強くなれる。 3. **状態価値ネットワーク $V(s;\theta)$ の学習**: 強化学習で得た方策 $\pi_\rho$ どうしを対戦させたときの盤面評価を、期待収益 $z$ との二乗誤差を最小化するように学習する。従来のモンテカルロロールアウトによる盤面評価と比べ、同じ精度で15000倍の高速化を達成したと報告されている。 4. **モンテカルロ木探索による実行時の再評価**: 学習した価値・方策をそのまま使うのではなく、実際の対局時に[[モンテカルロ木探索]]で先読みし評価し直すことで、より強い手を選ぶ。事前確率には $\pi(a|s;\sigma)$(手の多様性があるため)を使い、葉の評価には状態価値 $V(s_L;\theta)$ とロールアウトの期待収益を線形結合する。 (Source: [[@2022__Gihyo__ディープラーニングを支える技術〈2〉 - Chapter 4 深層強化学習]] §4.14) ## 後継システムの系譜 図4.21(コンピュータ囲碁の発展の歴史)がまとめるとおり、AlphaGo は以下のように発展した。 - **AlphaGo Zero(2017年)**: 人の棋譜を一切使わず、ゼロから自己対戦のみで学習する。今の自分より少し強いプレイヤー(モンテカルロ木探索でより深く先読みして選んだ手)を目標として学習する自己改善ループを採用した。方策ネットワークと価値ネットワークを1つのネットワーク $f(s;\theta)$ に統合し(出力は事前確率ベクトル $p$ と状態価値 $v$ のペア)、ResNet(residual network)を採用した。学習開始から数日で既知の定石を発見するとともに未知の定石も発見し、AlphaGo をさらに強くした「AlphaGo Master」(2016年12月、トップ棋士に60連勝)に100戦89勝するまでに強くなったと報告されている。(D. Silver and et al., "Mastering the game of go without human knowledge", Nature, 2017) - **AlphaZero(2018年)**: AlphaGo Zero の学習手法に、引き分けへの対応、盤面の対称性を考慮したデータオーグメンテーション(反転・回転)、常に1つのネットワークを継続更新する設計を加え、囲碁以外のチェス・将棋にも同じ手法で対応できるように拡張した。2時間で将棋・4時間でチェスの最強プログラムに勝利し、8時間でAlphaGo Zeroを上回ったと報告されている。(D. Silver and et al., "A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play", Science, 2018) - **MuZero(2020年)**: AlphaGo・AlphaZero が環境の完璧なシミュレータ(ゲームルール)の存在を前提としていたのに対し、MuZero はゲームルールの事前知識なしに、将来の報酬・価値・方策を予測できる必要最小限の世界モデルをデータから学習し、そのモデル上でモンテカルロ木探索を行う。囲碁・将棋などのボードゲームに加え、従来モデルベース強化学習が成功していなかった Atari のゲームでも従来手法を上回る性能を達成した。YouTube のビットレート制御という現実世界の問題にも適用され、人が設計したモデルを超える性能を達成したと報告されている。(J. Schrittwieser and et al., "Mastering Atari, Go, chess and shogi by planning with a learned model", Nature, 2020) (Source: [[@2022__Gihyo__ディープラーニングを支える技術〈2〉 - Chapter 4 深層強化学習]] §4.14) ## AlphaGo が強さを実現した3つの要素 第4章は、AlphaGo が世界トップ棋士に勝てるほど強くなれた理由を次の3つの組合せに整理する: (1) 強化学習を使って最適な方策・価値を推定したこと、(2) ニューラルネットワークを使って盤面評価したこと、(3) 従来から使われていたモンテカルロ木探索を組み合わせたこと。(Source: [[@2022__Gihyo__ディープラーニングを支える技術〈2〉 - Chapter 4 深層強化学習]] §4.14) ## 2018年時点の同時代的な紹介(『SREの探求』第18章) 『SREの探求』第18章(2018年執筆、日本語版2021年)は、AlphaGoの技術的パイプラインには立ち入らず、2015年10月の対局(囲碁の欧州チャンピオン樊麾（ファン・フイ）に勝利)を、探索アルゴリズムを用いたDeep Blueのチェス勝利(1997年)と対比する形で紹介する(表18-1)。同章はAlphaGoが適用したアルゴリズムを「深層強化学習」とだけ述べ、教師あり学習による方策初期化・自己対戦の強化学習・モンテカルロ木探索という段階構成には触れていない。SRE実務者向けの当時の一般向け紹介が、AI研究の専門的な解説(本ページ上部、『ディープラーニングを支える技術〈2〉』第4章)とは異なる粒度で同じ出来事を語っていたことを示す一例である。(Source: [[@2021__OReillyJapan__SREの探求 - Chapter 18 SREのための機械学習入門]] §18.4.2 表18-1) ## 関連 - 組織: [[DeepMind]] - 概念: [[強化学習]] / [[方策勾配法]] / [[モンテカルロ木探索]] / [[DQN]] - ソース: [[@2022__Gihyo__ディープラーニングを支える技術〈2〉 - Chapter 4 深層強化学習]] / [[@2021__OReillyJapan__SREの探求 - Chapter 18 SREのための機械学習入門]] ## 出典 - 岡野原大輔, 『ディープラーニングを支える技術〈2〉』, 技術評論社, 2022, 第4章, §4.14. - [[@2021__OReillyJapan__SREの探求 - Chapter 18 SREのための機械学習入門]] §18.4.2. - D. Silver and et al., "Mastering the game of Go with deep neural networks and tree search", Nature, 2016.(章内で引用される原論文) - D. Silver and et al., "Mastering the game of go without human knowledge", Nature, 2017.(章内で引用される原論文) - D. Silver and et al., "A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play", Science, 2018.(章内で引用される原論文) - J. Schrittwieser and et al., "Mastering Atari, Go, chess and shogi by planning with a learned model", Nature, 2020.(章内で引用される原論文)