shogi686の学習について その1

まず、学習用の棋譜を用意する。今回は、自分が将棋クエストで指した600局強の棋譜を使った(それより極端に多い棋譜を使うことは想定していない)。棋譜の中に"N+merom686"という文字列があればファイル名の先頭に"b"を、"N-merom686"があれば"w"を付加して連番ファイルにリネームする(そういうプログラムを別に書いた)。それを、Blunder.Converterを使ってsfen形式に変換する。更にファイルサイズ等を見て、初手投了などの意味のない棋譜を手動で除く。駒落ち棋譜はそのまま使う。
学習するときは、ファイル名から学習に使う手番を判断する。局面を保持するPosition構造体にその局面で指した手(これが教師)を付加してstd::vectorに突っ込んでいくという安易な実装(開発に時間がかからないことのメリットは大きい)。棋譜が少なければ特に問題ない。王手放置もあるので、その局の最後の指し手は使わない。ソートと重複削除を行い、ついでに定跡を生成する(現れた全局面に対して指し手と出現回数をそのまま記録してるだけ)。
プロセスにIDLE_PRIORITY_CLASSを設定(学習中にTwitterとかするから)し、論理コア数を取得して8並列(使用CPUはCorei7 2670QM)でボナメソを実行する。最初に、各変数を初期化して、元にする評価ベクトルの統計情報を表示する(大抵はゼロから始めるけど)。
600局強の棋譜の20000局面強を使い、ボナンザメソッド。非常に優秀な手法である。並列化はやりやすい。ほとんどの時間を評価ベクトルの勾配を求めるのに費す(というか勾配を求めるために探索してPVを得るのに時間を使う)ので、そこだけ並列化すればよい。
ここから、勾配について説明する。目的は評価ベクトル(shogi686では、kk+kp+pp.binに詰まっている2駒関係を表す数百万個の16bit値が実体)を調整して強くすることだが、これを教師の指し手との一致度を高めることで実現する。具体的には、シグモイド関数を使って「教師の手を指した局面の評価値と他の手を指したときの評価値の差」を変換し「非一致度」として、「非一致度」の全局面・全合法手についての合計を、その勾配を使って下げていく。評価値は、N手+静止探索で探索して求める(Nは1か2でやったが、もっと増やす人も多い)。
例えば評価項目が2個しかなかった場合(つまり評価ベクトルの次元が2)、調理に使うボウルのようなグラフを思い浮かべると、最小値をとるのはボウルの底だ。底以外の場所から底へ向かうにはどうすればいいかというと、その場所の傾き(勾配)を調べて低いほうへ向かえばいい(ボウルが変な形をしているとうまくいかない)。底は平らなので、傾いてない場所に来たらそこで止まる。これを100万次元とかでやる(ただの微分なので難しいコードを書く必要はない(コードを書くのは難しいが探索よりはマシ))。
単に「1手+静止探索の読みで指し手が教師と一致した数」を「一致度」にすると、そもそも微分できる場所は全て平らになってしまう。やるとすれば、教師より評価値がよかった指し手に一定の勾配を与えることになると思う(オンライン学習的?)。しかし、間違ってうんと良く評価した手よりも、あとちょっとで正しく評価できる手で学習したい(評価ベクトルを少しだけ変えることで探索結果が変われば副作用が少なく望ましい)から、やはりシグモイド関数を使うのがよい。シグモイド関数を使うと、ちゃんと教師より悪いと評価できた場合も学習してしまうが、終盤においては強さに寄与するようだ(値が大きく正解が限られるから?よく知らない)。
勾配を求めるには、まず、ある局面に対して教師を含む全合法手を探索し末端局面の特徴(評価ベクトルの数百万の要素の中で当てはまる820個くらい)をそれぞれ得る。教師とそれ以外を比較し、教師の末端にだけあるもの/ないものから評価値の差に応じて勾配を得て(シグモイド関数微分を使う)全合法手について足し合わせる。更にそれを学習対象の全局面に対して足し合わせる(微分は線形なので足せばよい)。
GPS将棋の発表から得たヒントなど: 「うさぴょん」「ねこにゃ」開発日記
末端局面を得るにはTriangular PV-Table(なんか複雑でバグを入れそうなのでshogi686では使ってない)などでPVを保存しておき、最初の局面からそのPVの手順で進めればいい。PVは全局面のぶんを保存しておき、学習の最初の数回では、同じPVで勾配を求めて値を更新するのを何回も繰り返す(やりすぎると変になるけど、PVを求めるコストがあまりに高いので繰り返すコストは無視できる)。
駒割は、Bonanzaのように勾配でソートすると、出現頻度の高い歩ばかり更新されるので、勾配を出現頻度で割ってソートしている。Bonanzaの、駒割の和を一定にするやり方はなかなかよい。
その2へ続く。