メカ女子将棋、評価関数を機械学習することにしました。
ただ、とりあえず大雑把にやってみたところ、失敗こきました(T_T)
ただ、学習のiterationをまだ一回廻しただけなので、まだまだ成功する
可能性は少しあります(^^)
ここにやり方を一通り書きますので、もしよろしければ、識者の方の意見を
賜りたいと思います（たしかコメント可能になっていると思います）
1. liblinearを準備する
liblinearについてはlibsvmの親戚で速いやつ、くらいに思っていただければ
いいと思います。今回はclassify（二値分類）ではなく、regression（回帰）
を使ってみることにしました。これは二値分類の場合に0か1が答えとして出てくる
代わりに、関数値がdouble型で返ってきます。この学習の種類は、trainのsパラメータとして
-s 11を使用した場合に相当します（L2-regularized L2-loss support vector regression (primal)）。
今回はtrainとpredictを使うほか、評価関数内でライブラリとしてliblinearの
内部の関数を利用します。
学習のためのファイルは次のようなレコードの並びです。
regressionの場合、１か0ではなく、関数値を与えます。
関数値 素性インデックス１:素性値１ 素性インデックス２：素性値２.............
この構造はlibsvmで使われるファイルと同一のものです。
2. 棋譜
色々やってみたのですが、trainで学習できる棋譜の数はon memoryでいける
最大値が大体300局くらいでした。CSA形式に準じた形の棋譜を準備します。
3. 素性抽出
まず、棋譜のすべての局面において、すべての可能手を列挙するプログラムを
書きます。そして、各局面のすべての可能手によって生じる可能性のある兄弟
局面を求めます。
その兄弟局面において、まず深さ1で探索して探索の値を求めます。
棋譜にあった局面は、歩１つぶん（100くらい）を加算します。
棋譜にあった局面よりも大きい値を持つ兄弟局面については、棋譜にあった局面
から100を引いた値を設定します。
これで、棋譜にあった局面が突出している状態になります。
次に素性を求めます。すべての兄弟局面について、素性ベクトルを求め、先ほど求めた
探索値を付与します。
今回は2駒の関係を用いました。具体的には駒の位置(100通り)と駒の種類（16通り）の
二乗になりますので、 2560000種類の素性インデックスが可能性としてあることになります。
この各素性インデックスに大して、素性値を求めます。すべての２駒の関係について、
王手を含む効きの種類が細かく分類して10通りくらいあるのですが、それを1--10で
数値化します。効きがある関係だけ素性を用意します。
こうして、１局面について、可能手の数だけレコードができます。
これをファイルに落としていきます。１局を１ファイルとしました。
4.学習
3.で作ったファイルのうち、300局をcatで固めます（kifu300.txtとします）。
その結果から、学習を行います。
$ ./train -s 11 kifu300.txt kifu300.model
膨大なメモリを使い、10分くらいでkifu300.modelファイルが出来上がります。
5. 利用
liblinearをメカ女子将棋に組み込みます。
面倒だったので、blasのライブラリと一緒に.aファイルをリンクして
しまいました。
諸般の事情で、メカ女子将棋のエンジンはshared libraryなので、
このshared libraryに対してblasとliblinearを結合します。
インクルードファイルはlinear.hになります。
まず、対局開始時にmodelファイルを読み込むように改良します。
そして評価関数をpredict関数の出力値に置き換えます。
関数出力（predict）の結果は、いい忘れましたが、-10000から10000
にクランプした上で、
-1から+1にスケールしてありますので、predictの結果に10000.0を
掛けて乱数を載せて評価関数の値として返します。
6. 結果
predictの時間が長くかかれば成り立たないなと危惧していたのですが、
大丈夫でした、predict自体の時間は短いようです。ただ、素性ベクトルを
局面に対して求めるのに時間が掛かっているようです。
結果としては、大変弱い評価関数が出来上がりました。
ただ、出来たmodelファイルからさらに、2から5を繰り替えしていけば、
強化学習ができるのではないかと思っています。
すみません、長くなりました。以上です。
liblinear というライブラリがあるのですね．
返信削除よいことを知りましたありがとうございます．
棋譜というか，局面図がないので，
何をどう推定しようとして期待どおりにならなかったのか
私には読み取れませんでしたが，
推定しようとしている事柄（正解値）は，
線形予測で十分な正解値が用意してあるのでしょうか？
つまり，「完璧に推定できたときにどうなるか」
という正解情報と，現状での推定結果とを比較しないと，
学習が失敗したのかどうかわからないような気がしました．
線形の正解情報を特には用意していない場合は，
課題自体が線形平面で切り分けられる課題なのか，
ぐにょぐにょの曲面でないと切り分けられない課題
なのかどうかを見極めておく必要があると思います．
課題がどういう性質であるのか想像がつかない場合は，
特段の理由がない限りは SVN で切り分けたほうがよいと
思います．
libSVNは，結構，速いと思います．
↑すっごくシンプルな表現を思いつきました(^^;)．
返信削除教師値に対して回帰直線（回帰平面）を引いたときの正解率に比べて，
学習結果で推定したときの正解率はどれくらい落ちるかを評価すると
よいのではないか，と思いました．
たいていの課題は回帰直線（回帰平面）には乗らないので... ．
何を推定しようとしているのか，ようやく理解できました！
返信削除> これで、棋譜にあった局面が突出している状態になります。
↑この仮定は確認できていますか？
値の分布がわからないのですが，
+100したり -100 したりしても，「棋譜にあった局面」が
「棋譜にない局面」に埋もれてしまっていると，
判別面より上には行かないので，
線形予測では推定できません．
回答ありがとうございます。正解かどうかは対戦させてみての勝率になるでしょうか。
返信削除いま学習を行っているのですが、数時間掛けてもliblinearで収束しません。多分libsvm
だとさらに数倍かかると思います。
学習がうまくいっているかどうかを調べるのに，
返信削除対戦して勝った負けたではも何もわかりません．
Twitter @kimrin のほうに書いたけれど，
学習させた棋譜中の局面に対する「次の一手」が
学習させた棋譜どおりになるかどうかでわかります．
> 数時間掛けても liblinearで収束しません。多分libsvm
> だとさらに数倍かかると思います。
必ずしも liblinear < libsvm ではない気がします．
線形分離不可能な課題の場合は，
liblinear だとなかなか収束しないんじゃないかな？
> これで、棋譜にあった局面が突出している状態になります。
なってないからかも．
もし，なっていることが確認できているのに収束しないとしたら，
「棋譜に存在する局面」と「棋譜に存在しない局面」とが
与えている素性情報からは線形平面で分離できないからです．
そもそも線形分離可能な課題なのですか？