AlphaGo Zeroの仕組みと論文の意義

  • 15
    Like
  • 0
    Comment

こんにちは。うえのんです。
今回は、AlphaGo Zeroについて自分の見解を勝手にまとめたいと思います。

まず、今回の論文が「mastering the game of go with deep neural networks and tree search」と異なる点はモデルがシンプルになり、Value NetworkとPolicy Networkが一つのモデルで済むようになった点です。

また、それより後に出てきたDeepMind社の「AlphaGo Master」と異なる点は学習や対局に使用したTPUが約50基から4基に減ったことです。学習に以前と比べてどの程度の時間をかけているかはわかりませんが、計算リソースが少なくても以前よりeloレーティング(強さ)が向上したとのことです。

この論文の意義としましては、人間が打った棋譜を使用しなくても強化学習のみで強くなれたという点と、今までPolicy,Valueと二つのネットワークをそれぞれ用意する必要があったのが、一つのネットワークに集約でき、少ない計算リソースでも計算できるようになった点です。学習時はモンテカルロ法を使用しますが、実際に対局する際はモンテカルロ法を使用せずにニューラルネットの出力のみで判断するので、探索する必要がなく計算速度が向上しました。

アルゴリズムのフロートしましては、
①まずニューラルネットワークをランダムに初期化
②自己対戦によりPolicy Networkの代わりとなる出力を、モンテカルロ法(モンテカルロシミュレーション)を使用して求めた着手可能なそれぞれの手に対する評価値(仮にそこに着手した場合の勝率を確率で出力する)で近似します。それとほぼ同時に、自己対戦の終局図から勝敗を判定し、Value Networkの教師として近似する。

といった感じです。②に関しては、専門家の方からご指摘がありました。同時に行わないと、最後に行った方が優先されてしまうからだそうです。(最後に行った方にフィッテイングしてしまう)

ネットワークの誤差関数は

l=\left( z-v\right) ^{2}-\pi \log P+C\left\| \theta \right\| ^{2}

となっており、ある局面からの勝敗の予測と実際の勝敗(と言ってもあるノードからの複数あるシミュレーション結果の勝敗の平均を取っている)の誤差と、Policy Network(19*19の盤面に対して、どこに打てば良いかを出力)の出力とモンテカルロ法で求めた着手可能な箇所ごとの尤度の誤差を足し合わせています。さらに、過学習を防ぐために重み(パラメータ)の値を全て二乗して足し合わせています。

ちなみに、zはシミュレーションで求めた勝敗、vはValue Networkに当たる出力で求めた勝敗、πはMCTS(多分Montecarlo Tree Searchの略)で求めた次にどこに打つべきかの出力、pはPolicy Networkの役割を果たす出力ノードの確率分布です。

モンテカルロ法で求めた勝率(確率分布)を教師としてニューラルネットワークに学習させているとしたら、そのために探索の手間が省かれて計算速度が速くなったのか?などと考えておりますが、詳しく論文を読んでいないので責任は負いかねます。

PUCTと呼ばれるアルゴリズムを使用している

モンテカルロ法で探索していく過程で、枝(branch)を展開していき、探索範囲を広げていきます。通常のコンピュータ囲碁プログラムはUCTと呼ばれる、確率論をベースにしたアルゴリズムを使用しています。今回発表されたAlphaGo Zeroも、モンテカルロ法は使用していますが、PUCTと呼ばれる独自のものを使用しています。

c(u,s)=c_{puct} p(s,a) \frac{\sqrt{\sum_{b}Nr(s,a)}}{1+Nr(s,a)}

p(s,a)はPolicy Networkの出力の次の一手のオススメ度(確率分布)、分数の分母は探索途中に出てくるある盤面(ノード)以降にシミュレーションされた全体の分岐の数、分子は同じある盤面(ノード)から一手打ってみて、その着手以降にシミュレーションされた数です。これが何を意味しているかと申しますと、シミュレーション途中にある考えられる着手が少ない回数でしかシミュレートされていなかった場合、確率的に信用できないので、より多くシミュレートしようということです。逆に、多くの回数ある着手に対してシミュレートされていたら、ある程度確率的に信用できるので、他の信用度が弱い着手をより多く検証した方が全体として良いということです。

初期の頃のAlphaGoの論文の解説は下のリンク先のpdfがわかりやすいです。勝手にシェアさせていただきます。
https://www.slideshare.net/yuk1yoshida/alphago-61311712

また、この記事を読んでもやっときた方のために、以下のサイトを紹介しておきます。とてもわかりやすいです。
http://blog.livedoor.jp/yuno_miyako/archives/1068350228.html
http://tadaoyamaoka.hatenablog.com/entry/2017/10/21/174532