AlphaGoのお勉強

未分類

http://www.slideshare.net/yuk1yoshida/alphago-61311712
は大変分かりやすいスライドなのですが、AlphaGoがなぜそういう設計になっているのかわからなかったので原文を読んでみました。
(スライド中のvk.comから取っていいのかな・・？）
以下は自分の解釈ですが、上記スライドをかなり参考にしています。

学習しておく関数

a. ポリシー関数

P(a|s) = 盤面sにおいて手aを打つべき確率

a-1. rollout policy(p-pai)

  • 線形softmax、高速
  • 人間による8M盤面より学習
  • rollout時の確率として使用

a-2. tree policy(p-tau)

  • 線形softmax、高速
  • rollout policyより特徴量が多い
  • 人間による8M盤面より学習(?)
  • 木の展開時にpolicy networkが計算されるまでの仮値として使用

a-3. policy network(p-sigma)

  • neural network、高精度
  • 人間による28.4M盤面より学習
  • 木の展開時の事前確率として使用（探索時の優先順位に影響）

b. バリュー関数

V(s) = 盤面sの評価値(-1～1)

b-1. value network(v-theta)

  • neural network
  • 盤面の評価値
  • 生成された30M盤面より学習

memo

  • なぜrollout policyとtree policyを分けるのかは良くわからない。
  • 強化学習においてp-rhoを学習するが、それはvalue networkの学習に用いるだけで対戦には使用しない。 p-paiの方が多様性が高くモンテカルロ探索には良いとのこと。
  • value networkの学習では、同じ局から盤面をとってきてしまうとover fittingしてしまうので、それぞれ別の局から盤面をとってきている。

MCTS（Monte Carlo tree search) のアルゴリズム

ルートノードおよび合法手をエッジとする木から開始する

  • エッジは事前確率・value network計算回数・rollout計算回数・value newwork評価値の積算・rollout結果の積算を保持する
  • 事前確率はpolicy networkをセットする

各スレッドは以下のように探索する

  • 1 ルートノードからQ+uの大きいものを選び木を下ってリーフ（エッジがまだ展開されていないノード）まで到達する
    • Qはvalue networkの値とrollout結果の平均
    • uは事前確率と探索回数による、探索を広く行うための項
  • 2-1 リーフ到達時に、まだ評価されていない場合はvalue networkの評価を依頼する
    • value network終了時に評価を伝播させる
  • 2-2 リーフ到達時に、ロールアウトを行う
    • ロールアウト終了時に評価を伝播させる
    • rollout中は一時的に評価を下げておき、他のスレッドから探索されづらくする
  • 3 あるエッジのrollout回数が閾値(=40)を超えた場合、その直下のリーフを展開する
    • 事前確率はtree policyを仮にセットし、policy networkの計算が終わったら置き換える
    • policy networkの値をsoftmax temperatureで調整し、メリハリを強くしている

最終的に、rollout回数の最も多い手を選択する

  • 評価値の最も高い手より外れ値に頑強

memo

  • CPUのスレッドの他、value network用のGPUのキュー、policy network用のGPUのキューがあり(?) 、非同期に評価が行われる
  • value networkの評価の順序は良くわかりませんが、きっとうまく評価の高そうな順に行うようになっているのでしょう。
  • policy networkの評価が追いつくように、リーフ展開の閾値を動的に調整する
  • 評価の伝播は単純に勝敗・評価値・探索回数をルートノードまでさかのぼって加える。 探索確率はpolicy network/Value Network/rollout結果によるため、評価値はそれなりに良い手の加重平均となる。
    評価値のmaxをとるわけではないのが面白いところで、囲碁を確率論的なものとしてとらえているように思える。
  • 評価が非同期に更新されていくので、良い感じに探索するパスが分散される

感想