読者です 読者をやめる 読者になる 読者になる

雑記: 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は完勝目指してまた何か盛り込んでくるんだろうか。