Bonanzaの学習法
CSAの例会のコメントを見ると、柿木さんは「Bonanzaに習って私も学習してみました」と書かれてました、
このような集められる情報を、それこそ目を皿のようにして読みました。
TD法も勉強しました。最急降下法も勉強しました。ロジステロの学習法も学びました。
はじめは、ロジステロのように学習しようと思いましたが、
「正確な評価値？」分かりません＿|￣|○
終盤ではなく、序盤・中盤で、正確な値は分からない。
Bonanzaがやっている学習は、正確な評価値を出すように評価関数を最適化しているのではなくて、
棋譜の手とよく一致するように評価関数を最適化しているのでした。
では、TD法とどう違うのか？
TD法による学習は、棋譜ではなく、相手と対局して、状況の変化を利用していました。
オセロは将棋のように静止探索をしないでいいので、ある局面の評価＝その局面の評価で済むのです。
将棋は違います。
それを可能にしたBonanzaの学習法のすごさと思います。
GPS将棋チームの駒の位置関係の学習は、駒同士がぶつかってない局面だけで学習してました。
取り合い探索をしないでもいい状況での学習と思います。
Bonanzaの論文をおさらいすると、
ある局面で、合法手について集計して
L=Σシグモイド(EV自分-EV棋譜)
この数値は、
EV自分＝EV棋譜 なら、シグモイドは0.5になります。
EV自分がEV棋譜より大きければ１に近づく。
EV自分がEV棋譜より小さければ０に近く付く。
EV自分-EV棋譜がマイナスなものは、EV自分＝EV棋譜な手よりオーダリングが後ろですので問題ないですが、
問題は、
EV自分-EV棋譜がプラスです。棋譜の手より評価が高いと誤解した手は先に探索されます。
要するに、
L=Σシグモイド(EV自分-EV棋譜)
とは、棋譜の手よりより良いと誤解した手の総数になります。
これを初手から投了まで集計して
J=ΣLとすると、
Jを最小化することがBonanzaの目的となります。
理想の状態では、１３０手までで終了した棋譜に関してはJ<=130になります。
これなら探索をしまいでも、オーダリングの初手を打つだけで、棋譜が再現できます。
ではJを最小化するには、Jの偏微分を計算して最適化すればいいのです。
∂J/∂w = ∂J/∂w・ΣΣT(EV-EV棋譜)
= ΣΣ∂T(x)/∂x・(EV-EV棋譜)∂/∂w
T(x)はシグモイド関数ですので、∂T(x)/∂x=T(1-T)になります。
w未来 = w現在 - α・ΣΣ∂T(x)/∂x・(EV-EV棋譜)∂/∂w
を繰り返せば、wはJを最小化するべく最適化できるはずです。
「 (EV-EV棋譜)∂/∂w 」が意味するのは、
評価関数を計算した局面で、現れている特徴の差です。
上記のTD法の学習と同じく、
金の価値の特徴は、金の枚数の差です。
自力で探索した局面では金が+1(=3-2)で、棋譜の手を指して探索した局面では金が+0(=2-2)なら、
金に関しては、
(EV-EV棋譜)∂/∂wは 「+1 - +0」＝+1
金の価値を減らせばいいのです。
w金の価値未来 = w金の価値現在 - 若干数
金の価値を減らせば、金をとりにくくなるので、棋譜では金をとってないのに、自力ではとってしまった誤解が是正される。
これをほかの特徴でもやれば良いわけです
保木さんの論文にそう書いてあるのですが、読み取るのに半年かかりました＿|￣|○
まだ１００局面ぐらいでしか学習してませんが、
ある位置の王とある位置の駒の価値
この場合は、先手の８八王に対しての後手の金・と金の位置に対する得点の表です。
後手金 -12 -26 -52 -6 -22 +1 -26 -20 -15 -56 -38 -20 +7 -26 -22 -26 -22 -74 -62 -48 -26 -15 -26 -26 -26 -5 -40 -45 -49 -26 -1 -26 +17 -26 -10 -88 -70 -60 -9 -11 -16 +1 -15 -91 -52 -60 -83 -26 -18 -26 -26 -26 -95 +8 +20 +5 -26 -26 -26 -18 +23 -26 -17 -49 王 +14 +3 +4 -26 -26 -85 -108 -21 +291 -108 +8 -26 -26 -108 -121 -32
王の周りはプラス。他はマイナスになりました。右下のマイナスが大きいですね。
Bonanzaの論文では王の右上のプラスなのですが、マイナスになってます＿|￣|○
上部の左右は、実際は後手王が右にいる場合と左にいる場合が混合されてますので、
評価が正しく出ません。
保木さんも論文で指摘されてましたが、「王と王と他の駒」のように三駒評価にするか、
多項式で連動させるなどの工夫がいると思います。
他にも隣接する駒同士の得点も学習してますが、あまり結果が芳しくないです＿|￣|○
先手金 +0 -10 -10 -12 -11 -9 -9 -1 -1 -10 +9 -5 +1 -13 -3 +6 -1 -9 +0 -6 -8 -26 -11 -15 -2 -1 +0 -6 -9 -2 +20 +9 -8 -2 -9 -9 -6 -2 -4 -7 -3 -2 +0 +0 -5 -2 -1 -2 +7 +8 -2 +0 +0 -3 -2 +5 -12 -16 +8 -5 -6 +0 -1 -7 -4 -4 -12 -25 -5 -8 -5 -7 王 +0 +9 -19 -10 -6 -7 -6 -2
穴熊はサンプルが少なくてあまり学習できてません。これは先手の金です。
穴熊を攻める桂馬の使い方とかも学習できたら素晴らしい！
要するに、落とし穴の表を自動生成しているようなもんと思います。
自分的にbonanza論文の最大の謎は、
11thGPWの論文集のP80の
Vnew(l) = Vold(l) - h・sign[ ∂J/∂V(l) ]
の求め方です。
論文にも、目的関数がなめらかではなく、共役勾配法もうまく働かないので、
∂J/∂V(l)がプラスならVを減少、マイナスなら増加すると書いてあります
（柿木さんがCSA例会で、偏微分は弱いので全微分でやれないか？とか言われてたようです。メモメモ）
しかし、
∂J/∂V(l) = ΣΣ∂T(x)/∂x・(EV-EV棋譜)∂/∂V(l)
って、∂T(x)/∂xってインパルス関数なので、常にプラスになると思うんです。
∂T(x)/∂x = T(x)[ 1 - T(x) ]
T[x]はシグモイド関数で、0〜1に値しかとらない。
なので、∂J/∂V(l)ってマイナスになるでしょうか？
Jは、棋譜より高評価の合法手の集計なので単調増加と思います。
ま、しかし、かなりインチキな手法を考えて、なんとか学習はできました……
インチキなこともあってかなり高速に学習できます。
さらに模索しようと思います(ﾟДﾟ )
柿木さんや棚瀬さんは学習に成功された模様です。
興味深いのはCSA例会の話で、評価値の表を左右対称にしても棚瀬さんが学習が成功されたようです。
王とある駒の評価だと
81x81x駒の種類の数
という膨大な表がいるので、左右対称で学習すれば大きさが小さくなるので、三駒の関係もやれるかもしれないと思います。
ちなみに将棋自体はちっとも強くなってないです。深く読めないと意味ないです(´･ω･`)ｼｮﾎﾞｰﾝ
おまけで、棋譜データベース本のCD-ROMの棋譜を利用するためのソースを公開。
棋泉のデータフォーマットが検索しても分からないので、迷いました。バイナリだし。
分かると簡単でしたが、持ち駒の表現が迷いました。
バイナリで、移動先＝１バイト、移動元＝１バイトの順に並んでます。
１対局で512Bです。よって256手までしか記述できないはず。
移動先が100以上なら成ってます。移動元が100以上なら打です。
fopen_s( &fp, "kisen.kif" ,"rb");
if(fp==NULL)
{
printf("ファイルオープンエラー");
exit(1);
}
unsigned char buf[512];
for(c=1;;c++)
{
if( fread(buf,1,512,fp) <= 0) break;//棋譜終了
for(int i=0;i<=255;i+=2)
{
if( buf[i]==0 ) break;//次の棋譜へ
int x,y,x2,y2;
int c1=buf[i];
int c2=buf[i+1];
if(c1>=100) c1-=100;
x=(c1-1)%9+1;
y=(c1-1)/9+1;
if(c2>=100) c2-=100;
x2=(c2-1)%9+1;
y2=(c2-1)/9+1;
printf("\n#%d-%d %d%d",c,i/2+1,x,y );
if(buf[i]>=100)
{
printf("成←%d%d",x2,y2 );
}
else
{
if(buf[i+1]>=100)
{
printf("打(%d)",c2);
}
else
{
printf("←%d%d",x2,y2 );
}
}
printf("(%d %d)",buf[i],buf[i+1] );
}
}
fclose(fp);
}
