雑記： AlphaGoって何 - クッキーの日記

AlphaGo のニュースでもちきりだけどよくわかっていない自分（囲碁わからない）への自分なりのまとめ。

参考文献（出典）

AlphaGo のすごいところ
- 2015年10月にAIとしてはじめてプロ棋士に勝利した（2段プロ棋士に5連勝した）。
- 2016年3月にAIとしてはじめて9段プロ棋士に3連勝した。4戦目は落とした（2016年3月13日現在、全5局が継続中）。
  - 2016年3月の対局では、64スレッドを1920のCPUと280のGPUで分散実行している。

囲碁の難しいところと対策
- ゲーム木において1ノードからの枝分かれが多い（しらみ潰し探索は枝分かれ数の指数関数で増える）。
  枝分かれ数をゲームの branching factor （枝分かれ要素）とか breath （幅）という。
  - チェス：平均 35（3手先までのしらみ潰し探索パターンが約 35^3 = 42875）
  - 囲碁：平均 250（3手先までのしらみ潰し探索パターンが約 250^3 = 15625000）
    「考慮すべき盤面が宇宙の原子数より多い（DeepMind公式、Google公式ブログ）」
- かつ、囲碁はゲームの深さ（手数）も深い（チェスは約80、囲碁は約150：元論文より）。
- そのためアルファベータ法などの適用が難しい。
  - アルファベータ法：ミニマックス法において意味のない枝の評価を省く。
  - ミニマックス法：何を打つかの判断に4手先 (次の自分の手、その次の相手の手、その次の自分の手、その次の相手の手) まで読む場合、まずある末端ノードについて4手先（相手が打った後）の自分の報酬を評価する。その次に1つノードを戻ってまた別の末端ノードの自分の報酬を評価する。その報酬がさっきより大きかったらこの末端ノードは刈り取って捨てる（4手先は相手の手番なので、自分の報酬がより大きくなる枝は選ばれないとする）。小さかったら最初に評価した末端ノードの方を捨てる。以後繰り返し。自分の手番直後のノードでは自分の報酬がより小さいノードを捨てていく。
- ゲームが複雑すぎるならどうすればいいのか。
  - あるノード以下の評価を打ち切り、そのノードの評価で代用する（チェス等では有効であった）。
  - 全て評価せず、確率的にサンプリングした点のみ評価する（いわゆるモンテカルロ碁）。
    実際の棋譜データを参考に、より確率の高い探索範囲に絞る工夫もなされてきた。
- しかしこれらのアプローチをもってしても囲碁AIはアマチュアレベルに留まっていた。
  「評価関数が入力データの線形結合ベースであったため（元論文）」

AlphaGo アルゴリズムの概要
- 畳込みニューラルネットワーク及びモンテカルロ木探索を使用する。
- 以下の2つのネットワークを使用する。
  - “policy network"：次の手を選択する。
  - “value network”：盤面を評価する。
- ネットワークは12の異なる層と数百万のコネクションを含む。
- トレーニング手順：
  - "policy network" にプロ棋士の3000万の手を学習させる（教師あり学習：これで人間の手を57%予測できる）。ここで、モンテカルロ木探索のための確率分布も学習する。
  - 次に "policy network" を自分自身と数千回戦わせ、より勝てるものにする（強化学習）。
  - 最後にこの policy network" を戦わせることにより、どちらが勝つかの予測を "value network" に学習させる。

たぶんこんな雰囲気。より詳細は論文参照。
この記事を書いている間に Lee Sedol 九段が4戦目を下した。よくわからないけどなんかうれしい。
AIは完勝目指してまた何か盛り込んでくるんだろうか。