AlphaZero

イントロ

2018年12月にDeepMindからA general reinforcement learning algorithm that masters chess, shogi, and Go through self-playという論文が発表されました。超要約すると、**ドメイン知識なしで、同じ方法で、人間より強い囲碁AI、将棋AI、チェスAIを作りました！**というもの。これについて、まとめようと思います。こちら(興味があったら見てください)はAlphaZeroの将棋の棋譜です。玉がふわふわしてて、僕のような雑魚が真似ると一瞬で詰みそうです。

前提となる知識はニューラルネットワークとMCTS(Monte Carlo tree search)です。

要点まとめ

1. ベースはAlphaGo Zero(Mastering the game of Go without Human Knowledge)
2. AlphaGo Zeroは勝つ確率を推定しているが、AlphaZeroは期待報酬（expected outcome）を推定している。
3. 完全にドメイン知識なし（AlphaGo Zeroは2箇所にドメイン知識を使っている）。
4. 学習の仕方がシンプルになった。

ベースはAlphaGo Zero

2017年に発表されたAlphaGo Zeroは人間が指したデータなしで、人間が指したデータを使って学習した囲碁プログラム（AlphaGo）をぶっ倒しています。ちなみにAlphaGo(Mastering the game of Go with Deep Neural Networks & Tree Search)は初めてプロに勝った囲碁プログラムです。AlphaGo Zeroはだいたい下記のようなプログラムです。説明はA Simple Alpha(Go) Zero Tutorialを参考にさせて頂きました。AlphaGoとの比較で説明しようかとも思ったのですが、AlphaGoは結構複雑であり、AlphaGo自体の説明が必要になってしまいますのでやめました。

ニューラルネット

ニューラルネットワーク$f _{θ}$は$θ$をパラメータとして、インプットはボードの状態です。そして、二つのアウトプットを持ちます。１つ目は、指し手の確率分布$\boldsymbol{p}$、2つ目はそのポジションから勝つ確率$v$です。つまり、
$$f _{θ} = (\boldsymbol{p}, v)$$
ということです。学習に用いるデータは($s _{t}$, $\boldsymbol{π _{t}}$, $z _{t}$)という形をしています。ここで、$\boldsymbol{π _{t}}$はボードの状態が$s _{t}$の時にMCTSを使って、得られる確率分布です。$z _{t}$はそのポジションを指しているプレイヤーから見た最終的なoutcomeです。もし勝てば $z _{t} = 1$ で、負ければ $z _{t} = -1$ です。そして、損失$l$は以下のように定義されます。
$$l = (z - v)^2 - \boldsymbol{π}^{T}log\boldsymbol{p} + c||θ||^2$$
つまり、このニューラルネットワークは勝ち負けを推定するだけでなく、MCTSが出力する確率分布$\boldsymbol{π _{t}}$と類似の確率分布$\boldsymbol{p}$を出力するようになる、ということです。

MCTS

上の説明でもありましたが、MCTSは最終的に確率分布$\boldsymbol{π _{t}}$を出力します。AlphaGo Zeroではゲーム木を次のように構成します。状態$s _{t}$が一つのノードを表し、$a _{t}$を指し手として、($s _{t}$, $a _{t}$)はエッジを表します。そして、探索の間、次の量を更新していきます。

• $Q(s, a)$: 状態$s$から、指し手$a$を選択した時の期待報酬。いわゆる$Q$値。
• $N(s, a)$: シミュレーションの間、状態$s$から、指し手$a$を選択した回数。
• $P(a | s)$: ニューラルネットワークによって、計算される指し手の初期分布。状態$s$の時の指し手の確率分布。

これらの量から、次の$X$が定義されます。
$$X\left( s,a\right) =Q\left( s,a\right) +c\cdot P\left( a | s\right)\cdot \dfrac {\sqrt {\sum _{b}N\left( s\cdot b\right) }}{1+N\left( s,a\right) }$$

$c$は探索をコントロールするハイパーパラメータです。ちょっと余談ですが、第二項は信頼上限と呼ばれており、強化学習ではよく出てきます。AlphaGoやAlphaGo Zeroが使っているのはPUCTと呼ばれるアルゴリズムの亜種です。これらのアルゴリズムの基本的な思想は、不確かな時は楽観的に¹、というもので、真に良い行動を見つけるためには探索が必要、ということです。とても成功しているアルゴリズムにUCB1があります。

戻ります。1回のシミュレーションは次のように行われます。今状態$s$にいるとします。

1. $argmax _{a}X(s, a)$となる$a$を選択します。
2. 次の状態$s'$がゲーム木に存在するなら、1に戻ります（つまり$argmax _{a}X(s', a)$となる$a$を選択するということ）。次の状態$s'$がゲーム木に存在しないなら、初期化処理を行ってゲーム木に追加し、1に戻ります。初期化処理は、以下の3つ。
   + $(P(a | s'), V(s')) = f _{θ}(s')$
   + $Q(s', a) = 0 \hspace{5pt}∀a$
   + $N(s', a) = 0 \hspace{5pt}∀a$
3. シミュレーション終了時に、$Q(s, a)$や$N(s, a)$を更新する。$N(s, a)$は普通にインクリメントしていけば良いだけですが、$Q(s, a)$は以下の式で更新します。ただし、$s''$は状態$s$から指し手$a$を選択した後に、シミュレーションして出現した状態です。
   + $Q(s, a) = \dfrac {1}{N\left( s,a\right) }\sum _{s''}V( s'')$

　以上が1回のシミュレーションで行われる処理です。何度もシミュレーションを繰り返していくと$N(s, a)$の値は指し手を選択するための良い指標になっていると考えられます。これに基づいて、MCTSが出力する$\boldsymbol{π}(a|s)$は、$∀a$, $π _{a}$ ∝ $N(s, a)^{τ}$を満たします。ただし、$τ$は温度パラメータです。$\boldsymbol{π}$は$\boldsymbol{p}$よりもずっと強い手を選んでいます。考えてみれば、人間もこの手を指したら、どうなるかというシミュレーションを行っています。そして、シミュレーションがあった方が良い手を指せるので、この事実は直感に合っています。
下図は論文中の図です。

Selectでは、$X(s, a)$の値を見て、指し手を選んでいます。そして、次の状態$s'$が存在しない時には、Expand and evaluateが行われ、新たなノードをゲーム木に追加し、$V(s')$を計算します。そして、1回のシミュレーションが終了すると、Backupで、$Q(s, a)$や$N(s, a)$を更新します。さらに、シミュレーションを繰り返し、最終的な確率分布$π$を出力します（Play）。

self-playを使った学習

AlphaGo Zeroのすごいところの1つはhuman knowledgeなしで、学習した点にあります。これについて説明します。まず、ニューラルネットワークをランダムに初期化します。そして、その後、各局面においてMCTSを実行しながら、自分自身と対局します。これにより($s _{t}$, $\boldsymbol{π _{t}}$, _)が得られます。3番目の報酬はゲームが終了した時に埋められます。もしプレイヤーがゲームに勝てば1、負ければ-1です。こうして得られたデータに対し、ニューラルネットワークを学習していきます。

ただ、より厳密に言えば、学習データを生成するニューラルネットワークのパラメータ$θ$はこれまでで最も強いパラメータです。AlphaGo Zeroの学習のパイプラインは3つの要素で構成されています。パラメータの最適化、パラメータの評価、self-playデータの生成です。パラメータの最適化はミニバッチ法で行われるのですが、1000traning stepごとに、これまでで最も強いプレイヤーと新たにパラメータを更新していったプレイヤーで対局します。そして、55%以上勝てば、その新しいパラメータが最も強いプレイヤーになります。これがパラメータの評価です。そして、最も強いプレイヤーを用いて、self-playにより対局データを生成していきます。
分かりやすい擬似コードがあるので、載せておきます。

def policyIterSP(game):
    nnet = initNNet()                                       # initialise random neural network
    examples = []    
    for i in range(numIters):
        for e in range(numEps):
            examples += executeEpisode(game, nnet)          # collect examples from this game
        new_nnet = trainNNet(examples)                  
        frac_win = pit(new_nnet, nnet)                      # compare new net with previous net
        if frac_win > threshold: 
            nnet = new_nnet                                 # replace with new net            
    return nnet

def executeEpisode(game, nnet):
    examples = []
    s = game.startState()
    mcts = MCTS()                                           # initialise search tree
        
    while True:
        for _ in range(numMCTSSims):
            mcts.search(s, game, nnet)
        examples.append([s, mcts.pi(s), None])              # rewards can not be determined yet 
        a = random.choice(len(mcts.pi(s)), p=mcts.pi(s))    # sample action from improved policy
        s = game.nextState(s,a)
        if game.gameEnded(s):
            examples = assignRewards(examples, game.gameReward(s)) 
            return examples

以上がAlphaGo Zeroの概略になります。

AlphaZeroは期待報酬（expected outcome）を推定している

AlphaGo Zeroは勝つ確率を推定していたのに対して、AlphaZeroはexpected outcomeを推定している、とあります。なので、僕はAlphaGo Zeroは$v$の値が[0, 1]のレンジなのか？とか思ったのですが、$v$の方の出力層の活性化関数はtanhでした。AlphaZeroも出力層の活性化関数はtanhです。というかネットワークの構造は同一です。なので、これについては何を言いたいのかよく分かりません。もしかすると、ALphaGo Zeroでは$z∈[−1,1]$なのに対して、AlphaZeroでは、$z∈[−1,0,1]$なので（将棋・チェスはドローがある）、それを伝えたかったのかなと思います。

完全にドメイン知識なし

AlphaZeroはルールを除いて、完全にドメイン知識なしです。一方、AlphaGo Zeroは以下の2点でドメイン知識を使っています。

Data Augmentationに###

囲碁はゲームの性質的に、回転・鏡映の操作を行っても、同じ局面と見なせるらしいです。この性質を用いて、AlphaGo Zeroではトレーニングデータを8倍に増やしています。

局面の評価時に

AlphaGo Zeroでは、MCTSを行って状態価値を計算する時に、ランダムに回転・鏡映させています。回転・鏡映のさせ方には、8通りあります。そして、その写像を$d_ {i}$, $i∈[1, 2, .., 8]$とします。インプットを状態$s$とした時に、下のような計算を行います。これにより元の局面と写した先の局面が同じであるということをニューラルネットに教え込むことができます。よって、その性質を学習しやすくなる効果があります。
$$\left( d^{-1}_{i}\left( p\right) ,v\right) = f_{θ}(d_{i}(s))\hspace{5pt}∃i$$

AlphaZeroでは、上の二つのようなドメイン知識は一切用いません。

学習の仕方がシンプルになった

AlphaGo Zeroのトレーニングパイプラインが3つの要素（最適化、評価、self-play）で構成されているのは上で述べた通りです。AlphaGo Zeroは最も強いプレイヤーを使って、データを生成し、そのデータを用いて最適化します。一方で、AlphaZeroは最も強いプレイヤーではなく、最も新しいプレイヤー（つまり単に最新のパラメータを用いて）を使って、データを生成します。つまり、一番強いプレイヤーを決めるフェーズはなくなり、パイプラインはよりシンプルなものになります。

面白かった点

半端じゃないハードウェアリソースを使っている

データの生成に第一世代のTPUを5000個、ニューラルネットワークの最適化に第二世代のTPUを16個使ってるらしいです。

あのシャノンが出てくる

AlphaZeroは秒間60000 positionsを探索するらしいです。一方で、Stockfish(チェスAI)やElmo（将棋AI）はそれぞれ、60000000 positions、25000000 positionsを探索するみたいです。つまり、AlphaZeroの方がポジションに当たりを付けて探索している、ということになります。秒間60000個のポジションを探索するのはさすがコンピュータという感じですが、StockfishやElmoと比べると、人間らしい探索の仕方をしていると言えます。そして、このアプローチはShannonによって、1950年に提案されていたそうです。

今後楽しみな点

チェスはどうか分かりませんが、将棋ではNNUEと呼ばれる非線形な評価関数が提案されています。今まで将棋の状態価値関数は線形なものを使っていたので、このNNUEにより、より強くなったのではないでしょうか。論文の最後には、alpha-beta探索がチェス・将棋の領域でMCTSより優れている、という定説に疑問を投げかけていますが、両者の対決が楽しみです。

1. 速習 強化学習 ―基礎理論とアルゴリズム― p48 ↩