開発メモ : Magic Bitboardsは使わないことに - Bonanzaソース完全解析ブログ

※ 開発メモと書いてあるのは、自分用のメモです。意味不明なところが多々あるかも知れませんが、あとで、こんなことをこの時期に考えていたと思い返すために残しておきます。

Magic Bitboardsが本当に速いのか検討した結果、コンピュータ将棋には向かないと判断。

[理由] 現状、BonanzaやGPS将棋などでは評価関数用で使うパラメータは局所的にしかアクセスしていないため、L2/L3 cache(12MB程度)には完全に収まっている。収まっていないのは置換表だけだが、新規局面以外は一度書き込んでいるわけであり、これもある程度の確率でL2/L3 cacheに収まっている。

ところが、Magic Bitboardを使うと、14-bitのoccupied bit patternに対するbitboardテーブルが必要になる。飛・龍・角・馬で4種類×2**14×sizeof(bitboard)×81 = 60.75MB。大きすぎる。

このテーブルのアクセスする場所にはある程度局所性があるだろうが、私は差分指し手生成を採用しているのでこのテーブルにアクセスするのは、盤面上の状態が変わったときであり、そのときのデータがL2/L3 cacheに乗っていない確率は差分指し手生成を用いないときの確率より少し低いと思う。

そこで、Magic Bitboardsは用いないことにする。

Magic Bitboardsを使わないが、盤面をrl90(90度回転させたbitboard),diag1,2(45度回転させたbitboard)はそれぞれu64に収まっており、かつ、occupiedなbit pattern(7bit)をシフトで得たあとのmaskは0xffなので、実際のコードではmaskする部分のコードは省略される。

また、Bonanzaでは香は (飛車の利き & minus_ray )などとしてあったが、香用のテーブルも用意。馬も (diag1 | diag2 | 王の利き) となっていたが同様に( diag1 | 王の利き) のテーブルを事前に用意しておいて合成回数を減らす。

以下が実際に利きを計算する部分のコード。bitboardではなくDBBになっているので盤面の特定の範囲の利きを求めるにはたいていu64に1回アクセスするだけで済む。例えば王の8近傍は、必ず、DBBのp64[0]かp64[2]かのどちらかに包含される。

// スライドテーブル
// スライドテーブル。飛角の利きを求めるときに使う。
// adbb_file_attacksなどで使うためのテーブル。
// 詳しい意味は、ini.cppのini_attack_tablesを参照のこと。
extern slide_tbl aslide[ nsquare ];

// --- 飛車の利き、ここから

// sqの飛車の地点の横の利き。左右の端が駒にぶつかるまで。
// BoardPos sq, DBB occupied
#define AttackRank(sq)  (adbb_rank_attacks[sq]				\
                         [(ptree->posi.occupied.p32[aslide[sq].ir0]	\
                            >> aslide[sq].sr0) & 0xff ])

// ↑の関数版
inline DBB AttackRankFunc(BoardPos sq,const DBB& occupied)
{
	return adbb_rank_attacks[sq][(occupied.p32[aslide[sq].ir0] >> aslide[sq].sr0) & 0xff ];
}

// sqの飛車の地点の縦の利き。上下の端が駒にぶつかるまで。
// BoardPos sq, u64 occupied_rr90
#define AttackFile(sq)  (adbb_file_attacks[sq]				\
                         [(ptree->posi.occupied_rr90 >> aslide[sq].srr90) & 0xff ])

// ↑の関数版
inline DBB AttackFileFunc(BoardPos sq,u64 occupied_rr90)
{
	return adbb_file_attacks[sq][(occupied_rr90 >> aslide[sq].srr90) & 0xff ];
}

// AttackFile + Kingの利き(龍の利きを求めるのに便利)
#define AttackFileKing(sq) (adbb_file_king_attacks[sq]				\
                         [(ptree->posi.occupied_rr90 >> aslide[sq].srr90) & 0xff ])

// 飛車の利き
#define AttackRook(sq)			(AttackFile(sq) | AttackRank(sq) )

// 龍の利き
#define AttackDragon(sq)    (AttackFileKing(sq) | AttackRank(sq) )

// --- 飛車の利きここまで

// 同じく、香の利きを求めるためのテーブル。
extern DBB adbb_file_plus_attacks[nsquare][256];		// 後手の香の利きを求めるのに使う
extern DBB adbb_file_minus_attacks[nsquare][256];		// 先手の香の利きを求めるのに使う

// 香の利き(先手)
#define AttackBLance(sq)  (adbb_file_minus_attacks[sq]				\
                         [(ptree->posi.occupied_rr90 >> aslide[sq].srr90) & 0xff ])

// 香の利き(後手)
#define AttackWLance(sq)  (adbb_file_plus_attacks[sq]				\
                         [(ptree->posi.occupied_rr90 >> aslide[sq].srr90) & 0xff ])

// --- 角の利きここから

extern DBB adbb_diag1_attacks[nsquare][256];
extern DBB adbb_diag1_king_attacks[nsquare][256];
extern DBB adbb_diag2_attacks[nsquare][256];

#define AttackDiag1(sq)  (adbb_diag1_attacks[sq]				\
                         [(ptree->posi.occupied_rr45 >> aslide[sq].srr45) & 0xff ])

#define AttackDiag2(sq)  (adbb_diag2_attacks[sq]				\
                         [(ptree->posi.occupied_rl45 >> aslide[sq].srl45) & 0xff ])

#define AttackDiag1King(sq)  (adbb_diag1_king_attacks[sq]				\
                         [(ptree->posi.occupied_rr45 >> aslide[sq].srr45) & 0xff ])

// 角の利き
#define AttackBishop(sq)	(AttackDiag1(sq) | AttackDiag2(sq) )

// 龍の利き
#define AttackHorse(sq)   (AttackDiag1King(sq) | AttackDiag2(sq) )