TadaoYamaokaの日記

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

【囲碁プログラム】 tree policyの学習

AlphaGoの論文にあるtree policyをプロの棋譜から学習を行った。

rollout plicyから追加される特徴は以下の3つ。

  • Self-atari … 次に取られる手
  • Last move distance … 直前の2手からのマンハッタン距離
  • Non-response patter … 12point diamondパターン

Last move distanceの特徴数は34となっていたので、直前の2手のそれぞれで17ずつとして、マンハッタン距離が17以上の場合は17と同じと見做した。

Self-atariは、悪い手と考えられるので、マイナスの特徴量が付くはずである。
はじめ、特徴量の初期値をマイナスにしても0に収束してしまうので、何かがおかしいと思って、勾配法の式を見直したら、

\delta w_j = (y_i - d_i) w_j

としていた。正しくは、

\delta w_j = (y_i - d_i) z_j

z_jは、前の層の出力で、rollout/tree policyは1層のlinear-softmaxなので、つまり特徴に一致の場合1で、不一致の場合0となる。

修正して学習しなおしたら、ちゃんと負の値が付いた。

5万局の棋譜を学習したら、損失関数は序盤の数100局で下がった後、ほぼ横ばいになってしまう。

学習係数と正則化係数は適当な固定値を使っているのが原因かもしれない。
AlphaGoの論文には、rollout policyの一致率は、24.2%と書かれているので、こんなものなのかもしれない。


まだ十分に検証できていないが、GnuGoとの対戦ではアタリを助けるだけのランダムプレイアウトと比べて、勝率は明らかに上がった。
20戦で30%の勝率だったので、まだ5割には達していない感じである。

AlphaGoの論文では、tree policyとrollout policyのみを使った場合のElo ratingは1457となっているので、妥当な強さかもしれない。


実行速度がだいぶ落ちてしまったので、

  • パターン値の差分計算
  • パターン特徴量の検索をmapを使っていたのをゾブリストハッシュに変更
  • パターンの回転形を事前にハッシュに登録

ということを行って、19路1手目、10000プレイアウトで、

アタリを助けるだけのプレイアウト 1047 ms
rollout/tree policy適用 3750 ms

まで改善することができた。


AlphaGoで特徴になっているナカデがまだ実装できていないので、処理方法を検討しているが、実行速度を犠牲にしないでナカデの処理をどう実装すればよいかいい方法が思いついていない。