2009/09/25
■[Bonanza] 情報処理 No.9
情報処理 No.9のコンピュータ将棋特集を読んだ。
金子知適「最近のコンピュータ将棋の技術背景とGPS将棋」は、コンピュータ将棋全般について大変よくまとめられている記事。
Bonanzaの説明で、
持駒を含める場合は残りの２駒は玉とする等の制限を加えられてはいるが、それでも重み(パラメータ)の数は２億近くに達している。
というのは間違いだろう。
持駒については個々の駒単位ではなく、駒の種類ごとに何枚あるかを位置状態とする点を除いて、盤上の駒と同じように評価される。(03/15で書いている)
あるいは、まだ公開されていないBonanza最新版でそのように変更されているのかもしれないが。
2009/06/11
■[Bonanza] 対称
小宮日記 なぜBona4はdv==0のときに特徴を更新するのか？
恐らく、強さはほとんど変わらないだろうと予想。確認していないので断定はできないけれど。
それではどうして調べたのかというと、単に原因が気になったからというのが一つの理由。
もう一つは、Bonanzaのコード全体を読んで受けた印象が理由。
Bonanzaというのは、プログラムが強ければ良いというだけではなく、真理を探求するという要素も持っている感じがする。評価関数の部分だけを見てもわかるが、将棋固有のヒューリスティックが極力少なくなるように書かれている。その理由には、作者の将棋の棋力が低いということもあるだろうが、それだけとは思えない。
これも強さには大して影響がないかもしれないが、前から気になっていたことを思い出した。
学習で得られた更新量を実際のパラメタに反映する前に、盤の左右反転に対するパラメタの対称性を考慮して、param_sym()という関数を実行している。
この関数は、位置(k0l,il,jl)と、それを反転した位置(k0r,ir,jr)の値を、両者の和の値に置き換える。それは良いのだが、全ての位置が反転しても同じ位置の組み合わせだった場合(k0l==k0r, il==ir, jl==jr、三つの駒が全て五筋にいる、または持駒状態の位置)に、何もしないのは間違いではないだろうか？
通常のケースでは平均ではなく和にしているのだから、k0l==k0r, il==ir, jl==jrの場合には値を二倍に更新しないと過小評価することになってしまう。
param_sym( param_t *p )
{
int q, r, il, ir, ir0, jl, jr, k0l, k0r, k1l, k1r;
for ( k0l = 0; k0l < nsquare; k0l++ ) {
q = k0l / nfile;
r = k0l % nfile;
k0r = q*nfile + nfile-1-r;
if ( k0l > k0r ) { continue; }
for ( il = 0; il < fe_end; il++ ) {
if ( il < fe_hand_end ) { ir0 = il; }
else {
q = ( il- fe_hand_end ) / nfile;
r = ( il- fe_hand_end ) % nfile;
ir0 = q*nfile + nfile-1-r + fe_hand_end;
}
for ( jl = 0; jl <= il; jl++ ) {
if ( jl < fe_hand_end )
{
ir = ir0;
jr = jl;
}
else {
q = ( jl - fe_hand_end ) / nfile;
r = ( jl - fe_hand_end ) % nfile;
jr = q*nfile + nfile-1-r + fe_hand_end;
if ( jr > ir0 )
{
ir = jr;
jr = ir0;
}
else { ir = ir0; }
}
if ( k0l == k0r && il*(il+1)/2+jl >= ir*(ir+1)/2+jr ) { continue; }
p->PcPcOnSq(k0l,il,jl)
= p->PcPcOnSq(k0r,ir,jr)
= p->PcPcOnSq(k0l,il,jl) + p->PcPcOnSq(k0r,ir,jr);
}
}
}
以下略
2009/06/01
■[Bonanza] rparam()
2009/05/22に書いた、０付近の非対称の原因がrparam()にあることを実際に確認した。
Bonanza 4.0.4で、dv==0のときにはistepの更新をしないで、乱数の効果分だけ更新するように書き換える。
static void rparam( short *pv, float dv, int istep ) { int v, r; v = *pv; r = brand() + brand() - 1; if ( v > 0 ) { dv -= (float)FV_PENALTY; } else if ( v < 0 ) { dv += (float)FV_PENALTY; } if (dv == 0.0) { if (r > 0) { if (v <= SHRT_MAX - r) { v += r; } else { warn: out_warning( "A fvcoef parameter is out of bounce.\n" ); } } else if (r < 0) { if (v >= SHRT_MIN - r) { v += r; } else goto warn; } } else { istep += r; if (dv > 0.0) { if (v <= SHRT_MAX - istep ) { v += istep; } else goto warn; } else { if (v >= SHRT_MIN + istep ) { v -= istep; } else goto warn; } } *pv = (short)v; }
初期状態から1回iterationした結果は、以下のようになった。(newが書き換えた側)
やはりrparam()が原因だった。
| value | original | new |
|---|---|---|
| -5 | 0.15% | 0.15% |
| -4 | 0.14% | 0.14% |
| -3 | 0.44% | 0.46% |
| -2 | 4.52% | 4.76% |
| -1 | 18.46% | 22.93% |
| 0 | 32.57% | 37.01% |
| 1 | 26.76% | 22.68% |
| 2 | 9.29% | 4.61% |
| 3 | 0.87% | 0.44% |
| 4 | 0.15% | 0.14% |
| 5 | 0.15% | 0.15% |
| value | original | new |
|---|---|---|
| -5 | 0.17% | 0.16% |
| -4 | 0.16% | 0.16% |
| -3 | 0.46% | 0.48% |
| -2 | 4.52% | 4.85% |
| -1 | 18.70% | 24.61% |
| 0 | 33.18% | 39.11% |
| 1 | 27.45% | 22.06% |
| 2 | 9.63% | 3.37% |
| 3 | 0.91% | 0.35% |
| 4 | 0.16% | 0.16% |
| 5 | 0.17% | 0.17% |
2009/05/27
■[Bonanza] PcPcOnSq
k0, l0に入る値は、駒の位置状態を表す番号。(例：歩が６七にいる)
この番号は、0から1475まである。
二個の駒の位置関係を考えているのだから、0から1475の番号を縦と横それぞれに振った正方形を考えて、その中のある場所が一個の位置関係に対応する。但し、aとbの関係はbとaの関係と同じことなので必要な領域は半分の三角形(対角線は含む)。
左下の三角形を考えて、この三角形の各要素に対して０行目から順番に通し番号を０から振っていくと、第i行目の先頭要素の番号はi*(i+1)/2になる。従って、i >= jである二駒の状態(i, j)の位置関係のインデックスは、i*(i+1)/2 + jとなる。
最終的に、玉位置k, 二駒の位置状態i, jの要素の評価パラメタの取得は以下のようになる。
#define PcPcOnSq(k,i,j) pc_on_sq[k][(i)*((i)+1)/2+(j)]
正方形のままで表現すると、必要な領域が二倍近くになってしまうので、このように表現しているのだと思う。
pc_on_sq[][]というのは、この日記でKPPと呼んでいるパラメタのこと。
2009/05/22
■[Bonanza] 4.1.1の評価パラメタ
自分で学習させたものではなく、Bonanza 4.1.1に入っているfv.binの評価パラメタ値を調べる。(4.0.3の場合については、2009/03/20に書いている。)
KPP 最小値: -11779, 最大値: 8856, 平均値:0.05, 標準偏差: 73.29
KKP 最小値: -3251, 最大値: 4911, 平均値: 0.55, 標準偏差: 11.72
KPPの場合、値の絶対値が229以内に99%, 413以内に99.5%, 1004以内に99.9%が含まれている。
KKPの場合、値の絶対値が159以内に99%, 313以内に99.5%, 741以内に99.9%が含まれている。
この結果から、4.0.3のときよりも値の絶対値が大きい側に全体的に広がっているようだ。この原因は、学習時の探索を深くした(１から２？)ことにあるのだろうが、そのメカニズムまではわからない。
０付近の値の分布率は、以下のようになった。
| value | 4.0.3 ratio | 4.1.1 ratio |
|---|---|---|
| -5 | 0.11% | 0.08% |
| -4 | 0.17% | 0.10% |
| -3 | 0.51% | 0.12% |
| -2 | 5.59% | 3.25% |
| -1 | 21.43% | 18.13% |
| 0 | 34.76% | 35.43% |
| 1 | 26.12% | 29.19% |
| 2 | 8.12% | 8.78% |
| 3 | 0.65% | 0.12% |
| 4 | 0.19% | 0.10% |
| 5 | 0.11% | 0.08% |
4.0.3の場合も同様だが、プラスとマイナスの値の分布の非対称が目立つ。理想的には対称な分布になるべき。
この原因は、関数rparam()にあるのではないか？
v = 0でdv = 0のときには、v += istepを実行するようになっているので、第二フェーズの最後のstepでそうなれば必ずプラスになる。
rparam( short *pv, float dv ) { int v, istep; istep = brand(); istep += brand(); v = *pv; if ( v > 0 ) { dv -= (float)FV_PENALTY; } else if ( v < 0 ) { dv += (float)FV_PENALTY; } if ( dv >= 0.0 && v <= SHRT_MAX - istep ) { v += istep; } else if ( dv <= 0.0 && v >= SHRT_MIN + istep ) { v -= istep; } else { out_warning( "A fvcoef parameter is out of bounce.\n" ); } *pv = (short)v; }