TadaoYamaokaの日記

山岡忠夫Homeで公開しているプログラムの開発ネタを中心に書いていきます。

AlphaZero Chess/Shogiの論文を読む その3

前回までに個人的に気になった点はだいたい書いたので、今回は残った部分で気になったところを拾って書きます。

スケーラビリティ

思考時間を増やした場合、αβ探索よりもレーティングの伸びが良い。
これはAlphaZeroのMCTSがαβ探索より思考時間を短縮できるということを示しており、αβ探索の方がこの分野で優れているという信念が疑問視された。

引用されていた文献には、チェスにおけるMCTSの欠点として、トラップを発見するためにより長い試行時間が必要ということが挙げられていました。
ただし、十分に正確なシミュレーション戦略が見つかれば対処できるとも書かれていたので、今回それが精度の高いPolicyによって実現されたということでしょう。

先行研究

チェスの研究はたくさん上げられていますが、将棋の先行研究としては、ボナンザによる機械学習が取り上げられていました。

なぜうまく動くか

ニューラルネットワークによる非線形関数近似で局面評価をすると、強い表現力があるが疑わしい近似誤差を起こすことがある。
MCTSは、これらの近似誤差を平均するため相殺する傾向がある。
対照的に、αβ探索は近似誤差をルートに伝播させる。
MCTSによって、ニューラルネットワークを効果的に適用できるようになる。

ドメイン知識

使用したドメイン知識は以下の通り。

  1. 入力特徴と出力特徴を表現するために、盤がグリッド構造であることを使用
  2. シミュレーション、ゲーム終了のために、ゲームのルールを使用
  3. 千日手、移動、成り、持ち駒からの打ち手のルールを入力特徴と出力特徴に使用
  4. 上限手数で引き分けとする

以上のドメイン知識以外は使用していない。

考察

スケーラビリティ

将棋はチェス以上に浅いトラップを持つゲームであることが知られています。
将棋におけるモンテカルロ木探索の特性の解明
浅いトラップの存在がMCTSがMini-Max探索よりも弱い原因の一つとされていました。
AlphaZeroの手法でこの欠点が克服できることが示されたと思います。

先行研究

コンピュータ将棋でブレイクスルーとなったボナンザはしっかり取り上げられてますね。

なぜうまく動くか

非線形関数はMCTSと組み合わせることでうまく動くということです。
Ponanza方式のαβ探索とディープラーニングの組み合わせはこれとは異なるアプローチですが、近似誤差の平均化という点では狙いは同じだと思います。
AlphaZero方式はドメイン知識を用いない汎用性のある方法という主張もあるので目指すベクトルは異なりますが、将棋を強くするという目的であれば他にもアプローチはあると思います。

ドメイン知識

千日手を入力特徴に加えていますが、囲碁のコウと異なり、千日手が絡む手はそれほど重要ではないため、私は千日手は探索中にチェックしてもよいと思っていますが、ニューラルネットワークに学習させたかったようです。
AlphaGoZeroの論文の記事でも書きましたが、将棋を強くするという目的であれば効果的なドメイン知識は使って学習を効率化させたいところです。

今回で終了します。