TadaoYamaokaの日記

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

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

インターネット上から入手した5万局くらいのプロの棋譜から、プレイアウトの特徴量を学習させてみた。
勝ったほうの手のみを学習することにしたので、勝敗データがない棋譜は除外した。

特徴量は、AlphaGoの論文にあったrollout policyの特徴量とした。
ただし、中手はまだロジックができていないので除外。

各局面の各合法手について、以下の特徴の特徴量の線形和をsoftmaxに入力して着手確率を出力する。

  • Response … 応答パターンにマッチするか
  • Save atari … アタリを助ける手か
  • Neighbour … 直前の手の隣の8目か
  • Nakade … 中手のパターンにマッチするか(今回は除外)
  • Response pattern … 直前の手付近12目のパターンにマッチするか
  • Non-response pattern … 着手する場所が3×3のパターンにマッチするか

AlphaGoのrollout policyはMCTSのツリーの初期値としても使用されており、その際はさらに3つ特徴(アタリになる手、直前の手からの距離、着手する場所の12-pointsパターン)が加わるが今回は除外した。


Response patternは、「12-point diamon-shaped pattern」と書かれているが、図で説明がないので推測するしかない。
以下のようなものであると仮定した。

    ×    
   
   
       

◎が直前の手、×が着手した場所

Response patternとNon-response patternは、石の色の他、呼吸点の数(1,2,≧3)も特徴量になっている。

3×3パターンの場合は、石の色(空白、白、黒)で2bit、呼吸点の数で2bit、中央を除く8目分で、
(2+2)×8 = 32bit
の値となる。

回転と対称形を考慮して、パターンの値が一番小さいものをパターンを表す値とした。

パターンを表す値には、ゾブリストハッシュが一般的に使われるようであるが、ハッシュ値を24bitくらい確保しても少数だがハッシュ値の衝突が起きるので、パターンの値そのものを2分木(C++のmap)で持つことにする。
Pachiのソースを見ると、ゾブリストハッシュに使っている値をランダムではなく、よくわからない式(シード値0x35373cに16803とかを掛けて7を引くなど)で計算していて、理論的な背景が理解できなかった。
衝突を防ぐうまい手があるのだろうか・・・。

パターンのサイズがそれほど大きくなく、棋譜で出現頻度の低いパターンを削れば2分木でも実用的な速度になると見込んでいる。
Response patternでも(2+2)×12 + 4(着手位置) = 52bitで表せるので、64bit整数を2分木のキーにできる。

この論文によると、ハッシュが80%衝突しても精度をある程度維持できるようなので、少しくらいの衝突についてはそれほど気にしなくてもよいかもしれない。そのうち評価してみたい。



棋譜データからの学習は、損失関数を交差エントロピーとして、確率的勾配降下法を使用した。

特徴量が発散しないように、どの局面でもほぼ表れる空白のNon-response patternの特徴量が常に1.0であるという制約条件を置いた。
学習係数は、0.1→0.01→0.001と適当に小さくして、同じ学習データで複数回学習させた。


以上のように学習した結果、特徴量が最も大きくなったパターンは以下のものであった。

<Response pattern>

         
    ×    
●3 ●3 ●3  
  ○3 ○3 ●3  
    ●3    

◎が直前の白の手、×が黒の着手、数値は呼吸点の数(3は3以上)

<Non-response pattern>

●2 ○2 ●2
  ×  
  ●2 ○3

×が黒の着手、数値は呼吸点の数(3は3以上)


Response patternが一致する棋譜は、例えばこの対局の204手目である。

f:id:TadaoYamaoka:20160505090746p:plain

白黒が逆で180度回転しているが、パターンに一致している。
プレイアウト中にこのパターンが局面に表れた場合は、Aの位置に打つ確率が上がる。


とりあえず学習できたので、これを前回のプログラムのプレイアウトに組み込んでどれくらい勝率が上がるか試してみるつもり。

github.com