Bonanzaの評価関数はどのようなものか？【KPP編】
■ Bonanzaの評価関数はどのようなものか？【KPP編】
駒割、KKPに続いて、今回はKPPを見ていく。
以上でBonanzaの評価関数はすべて終了。
■ KKP
KPPには、プロファイラによるとCPU時間の70%を要している。make_listは5%なので、これと併せると実に全体の75%を占めることがわかる。KKPはevaluate.cのevaluate関数で行なわれている。
score = 0;
nlist = make_list( ptree, &score, list0, list1 );
sq_bk = SQ_BKING;
sq_wk = Inv( SQ_WKING );
sum = 0;
for ( i = 0; i < nlist; i++ )
{
k0 = list0[i];
k1 = list1[i];
for ( j = 0; j <= i; j++ )
{
l0 = list0[j];
l1 = list1[j];
assert( k0 >= l0 && k1 >= l1 );
sum += PcPcOnSq( sq_bk, k0, l0 );
sum -= PcPcOnSq( sq_wk, k1, l1 );
}
}
score += sum;
score /= FV_SCALE; // 32で割って正規化
// 駒の価値の加算
score += MATERIAL;見ての通り、sq_bkは先手玉の盤上の座標。sq_wkは後手玉を盤上で180度回転させた位置に持っていったときの座標。Invは、この盤面を180度回転させるという処理をするマクロ。
評価関数のテーブルは先手用なので後手側は180度回転させてから評価する必要があるのだ。
make_listで駒の位置を配列に格納して、その駒の位置に従って、PcPcOnSq(これがKPPテーブル)をlookupしているだけなのでわかりやすいだろう。
ただし、KPPのPPは王以外の2駒だが、同一の駒でも良い。すなわち、KP(King-Piece)という2駒相対関係の評価もこれに含まれることになる。
また、evaluate.cにあるmake_listは、盤上の駒の位置を配列に格納していく関数である。
このmake_listのなかでKKPを(ついでに)評価する。このことは前回説明した。
KKP自体は、実は差分評価が容易であり、うまく工夫すればmake_list自体を省略できる。
■ make_listの引数
make_listで用意するデータは次のものである。
// 52は盤駒38+手駒14
static int
make_list( const tree_t * restrict ptree, int * restrict pscore,
int list0[52], int list1[52] )make_listでは、この引数で渡しているlist0,list1の配列にデータをセットして、list0,list1をどこまで埋めたのかを表わす値をリターンする。
ここでlist0,list1にセットする値は、KPPで用いる。つまり、王を除く、それぞれの駒の位置である。ただし、手駒の枚数もこのときに「駒」であるかのように扱う。
すなわち、先手の手駒の歩が5枚、香が1枚、後手の手駒の銀が2枚、金が3枚という局面であれば、この、「先手持駒 : 歩5」,「先手持駒 : 香1」,「後手持駒 : 銀2」,「後手持駒 : 金3」というのもそれぞれひとつの駒であるかのように扱う。
また、持っていない種類の手駒もひとつの駒であるかのように扱う。すなわち、「先手持駒 : 桂0 」「先手持駒 : 銀0」というのもそれぞれひとつの駒であるかのように扱う。
list0は先手の玉から見た駒位置、list1は後手の駒から見た(Invマクロを通した)駒位置を格納する。
また、駒の位置を格納するときに、駒の種類の情報も格納したいので、実際は、盤上の歩の位置を格納するのであれば、f_pawn(評価関数用のテーブルの歩に関する開始オフセット。f_pawnはfirst of pawnの略か？)という定数を加算して、次のように格納してある。
list0[nlist] = f_pawn + sq;
sqは、おそらくsquareの略で、盤上の位置が入っている。その値が盤面上のどこを意味しているのかについてはこちら(→ http://d.hatena.ne.jp/LS3600/20090921 )をご覧いただきたい。
よって、、このlist0,list1の最大要素数は、王を除く盤上の駒の最大数 38 + 手駒の種類7×2 = 52であるから、この配列はint[52]として確保されている。
list0,list1の[0]〜[13]までは、先後×手駒7種類 = 14が入る。
list0[ 0] = f_hand_pawn + I2HandPawn(HAND_B); list0[ 1] = e_hand_pawn + I2HandPawn(HAND_W); … list1[ 0] = f_hand_pawn + I2HandPawn(HAND_W); list1[ 1] = e_hand_pawn + I2HandPawn(HAND_B); … list1[12] = f_hand_rook + I2HandRook(HAND_W); list1[13] = e_hand_rook + I2HandRook(HAND_B);
■ PcPcOnSqで用いるテーブルの内訳
PcPcOnSqで用いているテーブルの内訳は以下のようになっている。このenumはshogi.hでdefineされている。マジックナンバーっぽくて謎に包まれていたが私がコメントを追加したのでこれで意味はわかると思う。
// --- 評価値計算用
enum {
// pc_on_sqで使うためのテーブル
// f_XXX : first , e_XXX : end
// 持ち駒の部分は、最大持ち駒数＋１（ 持ち駒無しの場合があるので ）
f_hand_pawn = 0, // 0
e_hand_pawn = 19, // = ↑+18+1
f_hand_lance = 38, // = ↑+18+1
e_hand_lance = 43, // = ↑+ 4+1
f_hand_knight = 48, // = ↑+ 4+1
e_hand_knight = 53, // = ↑+ 4+1
f_hand_silver = 58, // = ↑+ 4+1
e_hand_silver = 63, // = ↑+ 4+1
f_hand_gold = 68, // = ↑+ 4+1
e_hand_gold = 73, // = ↑+ 4+1
f_hand_bishop = 78, // = ↑+ 4+1
e_hand_bishop = 81, // = ↑+ 2+1
f_hand_rook = 84, // = ↑+ 2+1
e_hand_rook = 87, // = ↑+ 2+1
fe_hand_end = 90, // = ↑+ 2+1 , 手駒の終端
// pc_on_sqで使うためのテーブル
f_pawn = 81, // = ↑ - 9 (歩は1段目には存在しないのでそれを除外してある)
e_pawn = 162, // = ↑+9*9 (ここ、8*9までしか使用していない)
f_lance = 225, // = ↑+7*9 (香も1段目には存在しないのでそれを除外してある)
e_lance = 306, // = ↑+9*9 (ここ、8*9までしか使用していない)
f_knight = 360, // = ↑+9*6 (桂は、1,2段目に存在しないのでそれを除外)
e_knight = 441, // = ↑+9*9 (ここも、7*9までしか使用していない)
f_silver = 504, // = ↑+9*6
e_silver = 585, // = ↑+9*9
f_gold = 666, // = ↑+9*9
e_gold = 747, // 以下、+9*9ずつ増える。
f_bishop = 828,
e_bishop = 909,
f_horse = 990,
e_horse = 1071,
f_rook = 1152,
e_rook = 1233,
f_dragon = 1314,
e_dragon = 1395,
fe_end = 1476, // これが最後のデータ
// 持ち駒の部分は、最大持ち駒数＋１（ 持ち駒無しの場合があるので ）
kkp_hand_pawn = 0, // 0
kkp_hand_lance = 19, // +18+1 = 19
kkp_hand_knight = 24, // + 4+1 = 24
kkp_hand_silver = 29, // + 4+1 = ..
kkp_hand_gold = 34, // + 4+1
kkp_hand_bishop = 39, // + 4+1
kkp_hand_rook = 42, // + 2+1
kkp_hand_end = 45, // + 2+1
/*
盤上の駒の部分は、先手の歩は１段目には存在し得ない、
先手の桂香は１段目、２段目には存在しない
（香車は２段目に行ったら必ず成ることにしているため）
ので、歩、香、桂馬の部分は + 9*9 とはなっていない
*/
kkp_pawn = 36, // kkp_hand_end - 9
kkp_lance = 108, // + 8*9 = 108
kkp_knight = 171, // + 7*9 = 171
kkp_silver = 252, // + 7*9 = ...
kkp_gold = 333, // + 9*9
kkp_bishop = 414, // + 9*9
kkp_horse = 495, // + 9*9
kkp_rook = 576, // + 9*9
kkp_dragon = 657, // + 9*9
kkp_end = 738 // + 9*9
};
enum { pos_n = fe_end * ( fe_end + 1 ) / 2 };余談ではあるが、このようなマジックナンバーを直接ソースに埋め込むのは感心しない。まず、こう書かれるととても理解しにくいし、同時に、5×5将棋のような他のルールに変更するときにとても苦労する。
私は、kkp_hand_lanceなら、const int kkp_hand_lance = kkp_hand_pawn + pawn_max + 1;のようにひとつ上で定義している定数を使って書いていくほうが変更に対して柔軟だし、そちらをお勧めする。
■ PcPcOnSqの定義
PcPcOnSqはshogi.hで次のように定義されている。
// 3駒関係評価テーブル // これ、k = kingの位置 , i,jは他の2駒の位置。 // 3角テーブルなので、Σi = i*(i+1)/2になる #define PcPcOnSq(k,i,j) pc_on_sq[k][(i)*((i)+1)/2+(j)]
PcPcOnSq(k,i,j)のkはking(王)の位置。i,jは二つの駒。(i==jもありうる) このi,jの値が何を意味するかは上で解説した「pc_on_sqで使うためのテーブル」のenumを見ればわかる。
ところで、i>=jという大小関係を仮定できるなら、三角テーブル(普通の矩形のテーブルのおおよそ半分のサイズ)で済むことがわかる。
しかし、このi>=jという大小関係を守るためには、make_listで駒ごとに座標を列挙したとき、後手側は逆順で格納する必要が出てくる。これが、make_listで後手だけまずlist2というテンポラリ配列に格納し、そのあとlist1にコピーしている理由であり、この三角テーブルをやめて普通の矩形配列にすれば、このコピーのオーバーヘッドがなくなるので全体は1.6%ほど高速化される。
このように普通の矩形配列にした場合、テーブルサイズはおおよそ2倍になるのだが、私がCore 2 Duoで測定した限りは速度低下は一切見受けられなかった。おそらく、アクセスする部分は局所には変わりなくて、cache効率の低下はほとんど存在しないのだろう。Corei7やXeonでどう変わってくるのかは今後追試したい。
また、PcPcOnSqマクロでは、普通の矩形配列でよければi*iの掛け算が定数のかけ算で済む。iMulの、latencyはCore 2 Duoで3だったと思うのでここが i*ke_end+j になれば定数の掛け算で済み、いくらか最適化の余地がうまれる。
さきほどのKPPのループを再掲する。
for ( i = 0; i < nlist; i++ )
{
k0 = list0[i];
k1 = list1[i];
for ( j = 0; j <= i; j++ )
{
l0 = list0[j];
l1 = list1[j];
assert( k0 >= l0 && k1 >= l1 );
sum += PcPcOnSq( sq_bk, k0, l0 );
sum -= PcPcOnSq( sq_wk, k1, l1 );
}
}さきほどの掛け算は、定数畳み込みにより、最内ループの外で行なわれているはずではあるが、ともかく、i*ke_end * jのように変更するだけで1%程度の高速化が出来た。
ただ定数であっても掛け算自体は気持ち悪く、fe_endは1476であるから、これを1536 = 3*512に変更して、次のように書くほうを勧める。
#define PcPcOnSq2(k,i,j) pc_on_sq2[k][((i+i+i)<<9) /*i*fe_end*/ + j] // 1536 = 3*512 = (i+i+i) << 9
これによりCore2Duoではさらに1%程度高速化した。ただしCorei7/XeonなどでiMul自体のlatencyが低い場合は、むしろこのように書き換えることで遅くなるので注意が必要。
■ evaluateのinline化
evaluateは気軽に呼び出されるわりには、その半分ぐらいはstand_patとehash_probeでreturnすることがわかっているので、次のようにstand_patとehash_probeの判定部分だけでもinline化する。これにより1%ほど高速化できる。
static /*inline*/ int ehash_probe( uint64_t current_key, unsigned int hand_b,
int *pscore )
{
uint64_t hash_word, hash_key;
hash_word = ehash_tbl[ (unsigned int)current_key & EHASH_MASK ];
current_key ^= (uint64_t)hand_b << 16;
current_key &= ~(uint64_t)0xffffU;
hash_key = hash_word;
hash_key &= ~(uint64_t)0xffffU;
if ( hash_key != current_key ) { return 0; }
// 32768は、スコアにマイナスがあるので下駄履きさせてあったoffset
*pscore = (int)( (unsigned int)hash_word & 0xffffU ) - 32768;
return 1;
}
int evaluate_body( tree_t * restrict ptree, int ply, int turn );
// evaluateの半分ぐらいはstand_patとehash_probeでreturnするので、
// 関数呼び出しのオーバーヘッドがもったいない。
static /*inline*/ int evaluate( tree_t * restrict ptree, int ply, int turn )
{
int score;
ptree->neval_called++;
// ptree->debug_out1++;
if ( ptree->stand_pat[ply] != score_bound )
{
return (int)ptree->stand_pat[ply];
}
// ptree->debug_out2++;
// hashにそのkeyが存在するのか？
if ( ehash_probe( HASH_KEY, HAND_B, &score ) )
{
// そのスコアを返す。手番が後手番(1)ならば、マイナスの値として返す。
score = turn ? -score : score;
ptree->stand_pat[ply] = (short)score;
return score;
}
return evaluate_body(ptree,ply,turn);
}
■ まとめ
今回はKPPと、それに付随するチューニングどころをざっと解説した。
ちょっと駆け足で解説したので解説が不十分なところがあるかも知れない。
KPPについての説明は以下の記事もご覧いただきたい。
http://d.hatena.ne.jp/kkos/20090315#1237092027
http://d.hatena.ne.jp/kkos/20090527#1243418980
次回以降は、make_listを省略する方法とKPPの差分評価について解説していく。
