64bit環境向けBitboard、RBBの提案 - Bonanzaソース完全解析ブログ

■　64bit環境に適したBitboard、RBBが何故必要なのか？

将棋盤は81マスあり、Bitboardでこれを表現しようと思うと81bit必要です。64bit環境であれば、64bitレジスタが使用できるのですが、81bitは64bitレジスタ1つには収まりません。そこで、64bit変数1つと32bit変数を1つのようにBitboard構造体を構成するのが普通です。

struct Bitboard
{
　u64 p1;
　u32 p2;
};

Bonanzaのように3段ごとに32bit変数1つに入れないと、自陣にある駒だけを対象にforeachしたいときに、困ります。

しかし、x64環境では、bsf自体が1命令で出来るので、p1には、64マス分を詰め込みたいのです。そうするとp2は、残り81-64=17マスのみになります。これでは自陣にある駒を列挙しようとするときに、p1とp2にまたがるため、二回にわけてbsrする必要があり、非常に損をします。

また、p1を、3段(27bit) + padding(5bit) + 3段(27bit) + padding(5bit)のような変則的な構成にすると、このときの座標変換がやっかいになり、bsrが1回で済んでもかえって遅くなります。

つまり、理想的には、
・p1には64マス分を詰め込んであること
・p1のbsfしたbit位置をBoardPos(盤面座標)に変換するときに引き算とか足し算が不要であること
・自陣(7〜9段目)に対するforeachを2回にわけずに行なえること
であって欲しいのです。

これを可能にするのが私の提唱するRBB(Redundant Bitboards)です。

■　RBBのフォーマット

struct Bitboard
{
　u64 p[2];
};

簡単ですね。p[0]には盤面を上から64マスぶん格納してあります。p[1]には盤面を下から64マスぶん格納してあります。つまり、冗長部分が 128-81=47bitあります。これがRBBのredundantたるゆえんです。

■　RBBの具体的なメリット

RBBを導入すると何がお得なのかと言うと、自陣に対してforeachしたければに、(p[1] & HIGH_MASK27)として自陣の27bitを簡単に取り出せます。
自陣どころか、先手/後手から見た非敵陣の6段分(6*9=54bit)だろうと、7段分(6*9=63bit)だろうと一気に取り出せます。凄いですね。

そして先手/後手で対称性があるので、先手用のコードから後手用のコードを生成するのは単純な文字置換で済みます。要するにYaneLispのようなプリプロセッサ的なものが使えるということですね。便利ですね。

また、このp[0]をLow盤面、p[1]をHigh盤面だと呼ぶとします。いま、玉が1〜5段にいる場合は、Low関数、6〜9段にいる場合は、High関数を呼び出すとします。

このとき、Low関数では、近接駒(歩、桂、銀、金と、馬龍の8近傍)による王手は、Low盤面のみを調べれば良いとわかります。(何故なら5段目にいる玉に王手をしている盤面の一番下にある桂馬は7段目であり、7段目まではLow盤面に収まっていることが保証されているからです。)
同じくHigh関数ではHigh盤面のみを調べれば良いです。これにより、30%ぐらい高速に判定することが出来ます。

また、gen_nocap(駒をとらない指し手の生成)のために非敵陣(High盤面)にある銀に対して、移動先を調べるためにOccupied Bitboard(駒がある場所が1であるBitboard)と銀の利きをマスクするときも、移動先はHigh盤面(3〜9段目まではHigh盤面におさまっている！)なので、次のようにHigh盤面同士のbitwise andをすれば事足ります。

　desti.p[1] = silver_attacks[sq].p[1] & movable.p[1];

この技法を使えばgen_cap(駒をとる指し手の生成)は次のようにして高速化できます。

　bb.p[0] &= LOW45_MASK; // 1〜5段目
　foreach_Low盤面( bb.p[0] , from , {
　　desti.p[0] = silver_attacks[from].p[0] & movable.p[0];
　　foreach_Low盤面(desti.p[0] , to , {
　　　// fromからtoへ駒をとりながら移動させる指し手を生成
　　});
　});
　bb.p[1] &= HIGH36_MASK; // 6〜9段目
　foreach_High盤面( bb.p[1] , from , {
　　desti.p[1] = silver_attacks[from].p[1] & movable.p[1];
　　foreach_High盤面(desti.p[1] , to , {
　　　// fromからtoへ駒をとりながら移動させる指し手を生成
　　});
　});

このようにunrollすることによりgen_capはRBBを使わない場合に比べ、30%以上高速化できます。

■　まとめ

64bit環境に適したBitboard、RBBを提案しました。
また、RBBを使うことで、Bonanzaのgen_capは倍速以上に高速化できました。
他にもいろいろ使い所があるので考えてみてください。

私が思うに64bit環境で、将棋用のBitboardを扱うなら、これが最適なデータ構造です。
是非使ってみてその速さを実感してみてください。