What's?
- 2016年に開発された囲碁のAI
- DeepMind社と言う現在はGoogleが買収した企業が作った
- 当時プロ棋士に勝ったと言うことで有名に
- 将棋じゃないよ、AWAKEじゃないよ
- 深層強化学習で作られている
- 強化学習の方策や次の行動をNNで探索（学習）すること
- モンテカルロ木探索（MCTS）と言うアルゴリズムが元になっている
- 複数のNNを組み合わせて学習する
Policy NetworkValue Network
モンテカルロ木探索（MCTS）
ゲーム木の考え方を元に改善を図る。
ゲーム木
- あるゲームの行動パターンを木構造で表していくこと
- マルバツゲームとかなら全パターンは網羅できる
- 囲碁とかはパターンが多すぎて実質無理ゲー
MCTS
- 囲碁は現状が勝っているか負けているかの判断が人間でも難しい
- 専門の人はわかるけどトーシロにはわかんない
- 将棋やチェスは駒の強弱で分かりやすい
- わからないからランダムゲームセットまでいったろ
- それで勝率測ってこ。がMCTS
- 木構造のノードに「勝利数/プレイ数」を並べていく（囲碁なら、黒白それぞれのノードが交互に存在）
- まずはどこのノードに着目するか（Selection）
- そのノードから次のノードを「0/0」として増やす（Expantion）
- ランダムに最後までプレイし増やしたノードの「勝利数/プレイ数」を更新（Simulation）
- 更新したノードから先頭のノードまで結果を伝え、各ノードも更新する（Backpropagation）
Backpropagationは勾配更新とは完全に別物、たまたまネーミングが同じだけ
Alphagoのアルゴリズム
- MCTSでランダムにやり続けるのは明らかに効率が悪い
- どう考えても悪手なものは試したくない
- ディープラーニングを使おう!
- 現在の状態（盤面）から最も良い手を推論する
- Policy Network
- 現在の状態（盤面）を入力して、打つべき手の確率を出力
- ゲーム木の幅を削ることとと同等の効果
- 現在の状態（盤面）から勝率を計算する
- Value Network
- 現在の状態（盤面）を入力して、勝敗(+1:勝ち ~ -1:負け)を出力
- ゲーム木の深さを削ることと同等の効果
- 様々なNNの基本的な施策が導入されている
- BatchNorm
- ResNet
学習方法
1. 教師あり学習でPolicy Networkを学習する
- SL Policy Network
- 教師データは過去の棋譜(16万局、3000万の盤面)
- これだけでも57%くらいの精度で次の手の予測を行うことができる
- 高速Policy Network (Rollout Policy Network)
- こいつも学習する
- 精度は24%くらい
- 1000倍くらい早く学習できる
2. 強化学習でPolicy Networkを学習する（強くする）
- RL Policy Network
- Policy Network同士で対戦する
- 勝ったら+1, 負けたら-1の報酬を与える
- SL Policy Networkのみの場合と戦うと、勝率は8割くらいになる
3. 教師あり学習でValue Networkを学習する
- 現在の状態（盤面）を入力し、勝率を予測する
- 実際の勝敗（ラベル）はRL Policy Networkで戦わせた結果を使う
- 仮に2のRL Policy Networkで勝率を計算すると仮定するとそれより同等の精度で1.5万倍高速に推論できる
- Policy Networkは最後まで勝敗が分からないがValue Networkはその盤面だけでわかる
最終的な動作
- モンテカルロ木探索（MCTS）に従い、4つの動作をするのは同じ
- Selection
- Expantion
- Simulation
- Backpropagation
- Selection
- 評価値の高いものを優先して選択する
- Expantion & Simulation
- SL Policy Networkで勝率計算
- 勝率が高そうなら探索、低そうなら終了
- Backpropagation
- Value Networkと高速Policy Networkの両方で評価
RL Policy Networkは登場しない！！（Value Networkの学習に使ってるだけ）