AlphaGo Zeroについての覚書

AlphaGoシリーズの概要

ClaudeがまとめたAlphaGoシリーズの系譜は以下の通り：

AlphaGo (2015–2016)

方策ネットワーク（次の一手の確率分布）と価値ネットワーク（局面の勝率）を、モンテカルロ木探索（MCTS）に組み込んだ構成。学習はまず人間の棋譜からの教師あり学習、その後に自己対戦による強化学習という二段構え。2015年10月に欧州王者のファン・フイに5-0、2016年3月にイ・セドルに4-1で勝利しました。2017年には「Master」名義でオンライン対局60連勝、柯潔にも勝利しています。

AlphaGo Zero (2017)

人間の棋譜を一切使わず、ルールのみを与えてゼロから自己対戦で学習。方策と価値を一つのネットワークに統合し、ロールアウト（ランダムプレイアウト）も廃してMCTSの探索結果そのものを教師信号にするという、かなりすっきりした定式化になりました。数日の学習で従来版を100-0で圧倒。

AlphaZero (2017–2018)

同じアルゴリズムを囲碁・チェス・将棋に適用し、汎用性を示したもの。各ゲーム固有の工夫（チェスの評価関数など）を持たずに、Stockfish、elmo、AlphaGo Zeroを破りました。

MuZero (2019–2020)

ルールすら与えられず、環境のダイナミクスを潜在空間で学習したモデルを使って計画する。囲碁・チェス・将棋に加えてAtariでも最高水準を達成し、「探索＋学習」の枠組みがボードゲームを超えて一般化しうることを示しました。

この中から今回はAlphaGo Zeroに注目する。

AlphaGo Zeroの仕組み

膨大なパラメータ$\theta$によって特徴づけられる関数$f_\theta$がメインとなる。この関数は局面$s$を入力されると、その局面において可能な着手の「有望度」を$p$として与え、また、その局面における手番プレイヤーからみた予想勝敗を$v$で与える。

AlphaGo Zeroの学習とは、パラメータ$\theta$を調整し、人間に勝てるようにすることに他ならない。

では、具体的に学習はどうやって行うのか。そのためには、関数$f_\theta$から実際に手を選択する仕組みを考える必要がある。最も素朴には、有望度$p$が最大の手を選択すれば良いのだが、実際には「先読み」を行うことでより有望度の精度を上げる手法が採られる。そこで用いられるのがMCTSである。

有望度というのは、先読みをした結果なのだから、先読みをしても有望度は改善されないのではないかと思われるが、それは$f_\theta$が完璧な場合の話である。実際は不完全であり、一般には先読みを行った後の方が有望度の精度が高くなると期待される。

しかし、先読みを行うには膨大に存在する手の可能性を検討する必要があるわけで、無限の計算能力を持つわけではない我々は、あらゆる可能性の中から「有望そうな」ものを選ばねばならない。MCTSはこの可能性の選択に対して$f_\theta$を利用する。

MCTS をダンジョン攻略で理解する

ダンジョンを攻略する冒険者の立場になって考えよう。彼の目的は、ダンジョン内の宝物庫に到達することである。

彼は今、ダンジョン内のある拠点$s_0$にいる。ダンジョンは非常に複雑なので、出来るだけ効率的に探索を行いたい。どうすればいいだろうか？

$s_0$から枝分かれしている道のそれぞれについて、冒険者の勘（$f_\theta$に相当する）から、それぞれの道がどのくらいの有望度であるかを知ることが出来る。当然、まずは最も有望度$p$の高い道を選ぶだろう。そうして進んでみると、新しい部屋にたどり着く。この部屋を隈なく調べてみると、彼は$s_0$で感じていたのと、別の気配を感じ取る。有望そうだと思って道を選んだが、どうもこの部屋は望み$v$が薄そうだと思うこともあるだろうし、逆に、思ったよりずっと宝物庫に近そうだと感じることもあるだろう。

しかし、どちらにせよ、彼は一歩進んで新しい知識を得たのだから、それによってさっきまで持っていたこの道についての評価を更新するべきだろう。彼は新しい部屋を手元のマップに追記して、拠点へ帰る。この時、選んだ道の探索回数$N$に1を加算し、さらに累積有望度$W$に$v$を加算する。そして道の平均有望度$Q=W/N$を計算する。

累積有望度はこれまでのその道を選んだ時に得られた有望度の累積。平均有望度は文字通りその平均である。つまり、平均有望度$Q$は探索の結果が徐々に反映されてゆくことになる。イメージとしてはその道を選んだ結果得られると期待される有望度である。

$N$回目の探索が終わって、$N+1$回目の探索を行う場面を考えるのが分かりやすい。

$s_0$からスタートする。このステップでは、枝分かれしている各道について以下の選択スコアを計算する：

$$U_i = Q_i + c\, p_i \frac{\sqrt{\sum_j N_j}}{1 + N_i}$$

ここで$i$は拠点$s_0$から枝分かれしている道につけた番号である。$Q_i$は道$i$の平均有望度、$p_i$は冒険者の勘（$f_\theta$）が最初に与えた道$i$の有望度、$N_i$は道$i$をこれまでに探索した回数であり、$\sum_j N_j$はこの拠点から出発した探索の総回数、すなわち$N$に等しい。$c$は定数で、第二項をどれだけ重く見るかを決める。

第一項$Q_i$は、これまでの探索で実際に確かめられた評価である。実際に道$i$を選んだ探索によって得られた有望度の平均値であった。これがスコア$U$に加算されている意味は、これまでの探索で良いと分かっている道を選べという要求である。

第二項のメインは$p_i$である。これは探索前に冒険者が持っている勘による値であった。$c$や分数はそれに対する重みづけを行っているにすぎないが、特にこの分数の意味を考えるのが重要である。

分母は道$i$を選んだ回数である。一方で分子は、探索の総回数である。つまり、探索の初期には分数自体は大きな値となるはずである。しかし、探索の後半では分子は平方根でしか伸びない一方で、分母はそのままスケールする。すると、分数全体は小さくなってゆくことが期待される。

したがって、この項は第一項とは逆に、まだ試していない道を選べという要求である。$N_i$が小さいうちは分母が小さいので第二項は大きく、その道を繰り返し選ぶにつれて小さくなっていく。また勘の良い道ほど$p_i$が大きいから、どれも未探索のうちは勘の順に試されることになる。冒険者はこの二つの要求の釣り合いを取りながら、スコア$U_i$が最大の道を選ぶのである。

こうして次の部屋に到達する。その部屋がマップに記載があればまたスコアを計算して先へ進む。マップにまだ記載のない部屋であれば一旦探索を打ち切って拠点へ引き返す。

この時、それまで辿ってきた道を引き返すわけだが、この時道の記録を既に述べた方法で更新する。

この探索方法であれば、冒険者の勘に加えて、実際に探索を行った結果も加味される。最初は勘に従って道を選ぶが、探索が進んでデータが揃えば、勘よりもそのデータ（つまり平均有望度$Q$）を利用して道を選ぶことになる。

メモ

• この探索方法は、時間をかければ全ての道が選択される。実際、未探索の道はスコア第2項の分子が増加するのでいつかは大きなスコアとなって選ばれる。
• 道には$N,W,Q$の他に$p_i$も保持させる。こうすることで毎回$p_i$をネットワークに計算させる必要がなくなる。

参考

スッキリわかるAlphaZero

「その他」に戻る ・ メニューに戻る