論文で理解するAlphaZeroの概要｜論文で理解する深層強化学習の研究トレンド #5
連載の詳細の経緯は#1に記しましたが、深層強化学習の研究トレンドを論文を元に把握していくシリーズとしています。
#1ではApe-X[2018]について、#2ではR2D2[2019]について、#3ではR2D3について、#4ではMuZeroについてご紹介しました。
論文で理解するApe-Xの概要｜論文で理解する深層強化学習の研究トレンド #1 - lib-arts’s diary
論文で理解するR2D2の概要｜論文で理解する深層強化学習の研究トレンド #2 - lib-arts’s diary
論文で理解するR2D3の概要｜論文で理解する深層強化学習の研究トレンド #3 - lib-arts’s diary
論文で理解するMuZeroの概要｜論文で理解する深層強化学習の研究トレンド #4 - lib-arts’s diary
#5では#4で取り扱ったMuZeroのベースになったAlphaZeroの論文(A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play)について取り扱います。AlphaZeroはAlphaGo Zeroのアプローチをチェスや将棋にも拡張した研究になります。
以下、目次になります。
1. AlphaZeroの概要（Abstractの確認）
2. 重要部分の抜粋
3. まとめ
1. AlphaZeroの概要（Abstractの確認）
1節ではAbstractの内容を確認しながら概要について把握します。以下各文の和訳とともに解説を行います。
The game of chess is the longest-studied domain in the history of artificial intelligence.
和訳：『チェスゲームは人工知能の歴史において最も長く研究されてきたドメインである。』
人工知能の用語が出てきたのは、ジョン・マッカーシーが1956年のダートマス会議のために出した提案書の中が初だとされていますが、チェスを機械に行わせる話自体は1840年代のチャールズ・バベッジや現在のノイマン型コンピュータの基礎を作った(1940年代)ノイマンが1928年に書いた『社会的ゲームの理論について』の中でも言及されており、むしろ人工知能やコンピュータの出現よりも前からアルゴリズム自体は研究されてきています。
The strongest programs are based on a combination of sophisticated search techniques, domain-specific adaptations, and handcrafted evaluation functions that have been refined by human experts over several decades.
和訳：『(チェスなどのゲームの分野における)最も強いプログラムは洗練された探索技術、ドメイン特化の適応、人間の熟練者によって何十年もかけて作り込まれてきた評価関数の組み合わせに基づいている。』
コンピュータを用いたチェスやオセロなどの長年の研究にあたっては、MiniMaxをベースとして問題を定義し、アルファ・ベータ法(alpha-beta pruning)によって探索範囲を枝狩りしたり、モンテカルロ木探索(MCTS; Monte Carlo Tree Search)によってシミュレーション的に解いたりなど様々なアルゴリズムが考案されてきています。また、人間の熟練者の棋譜を参考にアルゴリズムを組んだりもされてきています。
By contrast, the AlphaGo Zero program recently achieved superhuman performance in the game of Go by reinforcement learning from self-play.
和訳：『対照的に、近年のAlphaGo Zeroのプログラムにおいては、プログラム自身のゲームプレイングを用いた強化学習によって囲碁ゲームにおいて人間を上回るパフォーマンスを実現した。』
一方で、AlphaZeroの元になっているAlphaGo Zeroのプログラムでは、人間の熟練者の棋譜を用いず、囲碁において人間を上回るパフォーマンスを実現し、話題になりました。これにより、複雑なドメイン特化も組み合わせながら取り組まれてきた問題に、汎用化についての可能性が見えるようになりました。
In this paper, we generalize this approach into a single AlphaZero algorithm that can achieve superhuman performance in many challenging games. Starting from random play and given no domain knowledge except the game rules, AlphaZero convincingly defeated a world champion program in the games of chess and shogi (Japanese chess), as well as Go.
和訳：『この論文では、我々は(AlphaGo Zeroの)アプローチをAlphaZeroのアルゴリズムに導入し、多くのゲームにおける人間を超えたパフォーマンスを獲得できるようにした。ランダムのプレイングとゲームのルール以外のドメイン知識を与えないところから、AlphaZeroは囲碁と同様にチェスや将棋においても世界一のプログラムを上回った。』
AlphaZeroの論文では、AlphaGo Zeroの論文の汎用化への可能性を元に、他のゲームへの応用についても取り組まれています。ルール以外の事前知識を与えないで、AlphaZeroでは囲碁と同様にチェスや将棋においても世界一のプログラムを上回ったとされています。
2. 重要部分の抜粋
2節では本文の重要と思われる部分についての抜粋と簡単な解説を行なっていきます。
冒頭部では、話の導入としてAbstractの内容をなぞっているような内容になっています。コンピュータチェスにおける従来の研究について確認し、ドメイン特化の傾向が強く、なかなか他のゲームへの適用が難しい点について指摘されています。
続いて上記では、ドメイン特化の傾向が強かった従来研究とは対照的に、AlphaGo Zeroの研究では畳み込みニューラルネットワークを用いた強化学習によって、自己プレイングに基づいてのみ学習することができたとされています。それを受けて、この論文ではAlphaGo Zeroのアプローチを汎用化してAlphaZeroとし、囲碁、将棋、チェスのそれぞれにおいて同じニューラルネットワークの構造を用いて学習させたと記述されています。
その他の前置き部分は飛ばして具体的なアルゴリズムの話に入りますが、によって遷移確率(move probability)と価値関数の推定値(value estimates)を計算するとされています。ここで用いられるニューラルネットワークは、Deep Q-Network系のアプローチで用いられているModel-freeのアプローチと基本的には同様なネットワークと考えて良さそうです。このように定義したネットワークをAlphaZeroはself-playに基づいて学習するとなっています。
ここでModel-basedのアプローチにおいてよく用いられるドメイン知識に基づくalpha-bata searchの代わりに、AlphaZeroでは前述のニューラルネットワークを用いて汎用化したモンテカルロ木探索(Monte Carlo tree search)アルゴリズムを用いたとされています。モンテカルロ木探索においては価値関数の高い低いだけでなく、行なったことのない行動を選択しやすいように組まれているのですが、この時の行動によって推移する先のノードの選択にあたって畳み込みニューラルネットワークのを考慮するとなっています。
ニューラルネットワークの学習にあたっては、(1)で定義した交差エントロピー誤差関数(cross-entropy losses)を用いて学習するとなっています。数式のと
が
のアウトプットとなっています。
アルゴリズムの大枠については一通り取り扱えたので、以下ではAlphaZeroのパフォーマンス面について確認していきます。
まずは学習の収束について取り扱っているFigure1を確認していきます。A〜Cはそれぞれチェスと将棋と囲碁のゲームにおいて他のプログラムのパフォーマンスを上回るまでにどのくらいの学習ステップを必要としたかについて図式化されています。ここで縦軸はレート(パフォーマンスに相当)、横軸は学習ステップ(学習時間に相当)を意味しています。
Figure2では他のプログラムとの対戦結果についてまとめられています。上記よりAlphaZeroが他のプログラムに対して勝ち越しているというのが読み取れます。
3. まとめ
#5では#4で取り扱ったMuZeroのベースになったAlphaZeroの論文(A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play)について取り扱いました。これらのゲームAIは元々ドメイン特化として研究されてきましたが、AlphaGo Zeroの成功から汎用的なアプローチに舵が切られてきており、これがMuZeroでAtariのゲームに対してもModel-basedなアプローチに基づいて取り組むにあたってのBackgroundとなっています。
