2009-11-23

■　double-sized bitboardの提案

将棋盤は81マスで、bitboardで表現する場合81bit必要です。これは64bitに収まらないので、盤面をbitboardで表現しようとすると64bit + 32bitもしくは64bit×2のようになるのが普通です。

上の組み合わせをメモリの無駄を承知で以下のようにするのもアリなのではと考えてます。
struct Bitboard {
union {
unsigned long long reg64[2];
unsigned int reg32[4]; // 互換性考慮
};
};
http://d.hatena.ne.jp/stonestonestone/20091115#p1

64bit環境で64ビット幅でのアクセスが、8バイト境界をまたぐと速度的にいろいろまずいので、どうしてもpaddingしてsizeof(bitboard)を8の倍数にするしかないというのはもちろんそうです。

それで、問題なのは、このpaddingしてある最後の4バイトが全くの無駄ということです。メモリの無駄だけならば良いのですが、せっかく64bit化しているのに、倍速にはならず、(上のソースで言えば)3つのreg32にアクセスしていたのが、2つのreg64にアクセスすれば良いようになるので、結局、3/2倍にしかなっていないのです。本来64bit化で2倍になるところが3/2倍にしかなっていないのですから、残り33%の伸びしろ(2÷ 3/2 = 4/3)が残っていることになります。

この33%の伸びしろを使い切る唯一の方法が私の提案するdouble-sized bitboardです。

なお、チェスでは、盤面は8*8 = 64なのでちょうど64bitに収まり、この問題は生じません。すなわち、コンピュータチェスにはこの発想は不要で、コンピュータ将棋特有のものです。

■　double-sized bitboardとは何か？

もうここまで説明すればあとは説明する必要はないと思いますが、構造体は次のように定義します。

struct DoubleSizedBitboard
{
  union
  {
    u64 p64[3];
    u32 p32[6];
  };
};

以下、DoubleSizedBitboardをDBBと略記します。意図は明確です。OCCUPIEDなどのbitboardは、このDoubleSizedBitboardで持ち、重複してp64[2]の情報も更新しておきます。具体的には、

	BB_B_OCCUPIED.Xor(sq);
	↓
  BB_B_OCCUPIED.p32[0] ^= abb_mask[sq].p32[0];
  BB_B_OCCUPIED.p32[1] ^= abb_mask[sq].p32[1];
  BB_B_OCCUPIED.p32[2] ^= abb_mask[sq].p32[2];

こうやっていたものを

	DBB_B_OCCUPIED.Xor(sq);
	↓
  DBB_B_OCCUPIED.p64[0] ^= adbb_mask[sq].p64[0];
  DBB_B_OCCUPIED.p64[1] ^= adbb_mask[sq].p64[1];
  DBB_B_OCCUPIED.p64[2] ^= adbb_mask[sq].p64[2];
	// DBB = double-sized bitboard

こうやります。本来64bit環境では2回の演算で終わるところ3回やっているので1回ぶん無駄ではあります。ところが、こうやっておけば、BB_B_SILVER + BB_B_KNIGHTのDBBとbitwise andをとるときに1回分得をしたり、bsf/bsrか条件分岐が1回省略できたりしておいしいのです。よって上で損したぶんの元はすぐに取り返せるのです。

敵陣以外にある自駒 → DBB_B_OCCUPIED.p64[2] , 自陣以外にある自駒→DBB_B_OCCUPIED.p64[0]も、うまく使えば指し手生成が高速化できます。

あとは、角の利きの計算のために使っているOCCUPIED_DIAG1,2にしても、DBBを使えば上のように3回の64ビット幅のbitwise xorで済みます。

	OCCUPIED_DIAG1.XorDiag1( sq_drop );
	OCCUPIED_DIAG2.XorDiag2( sq_drop );
　↓
	DBB_OCCUPIED_DIAG.XorDiag( sq_drop );

まあ、OCCUPIED_DIAG1,2に限って言えば7*7 = 49bitに収まるので1つに収めてMagicBitboardを使うほうが速いのかも知れませんが。

あとは、静止探索が結構の時間を占めており、そのためにはgen_capを高速化する必要があるのですが、gen_capを高速化するためには、このDBBが大活躍します。詳しいことはまたの機会に。

その他、いろいろ使い道があるのですが、今回はこのへんで。DBBの意外な使い道が思いついたら、この記事にトラックバックやコメントなどをください。

■　おまけ

DBBは2つのbitboardを1つにpackしたものと捉えることが出来ますが、このp64[0]とp64[2]には、盤面の上2/3(64マス分)を収めたほうが、bsrしたときにその値から盤上の座標(BoardPos)への変換が不要になるので良いですね。

またpackされた2つのbitboard同士のbitwise orをとりたいようなときにも、p64[0] |= p64[2]; p32[2]|=p32[3]; と最悪でも2回のbitwise orで済みますしね。

この場合、DBB_B_OCCUPIEDのp64[0] == p64[2]なのでp64[2]のほうは実際は使う必要がなくて、↓のようなコードだけで済むので追加コストは無しだと考えられます。

	DBB_B_OCCUPIED.Xor(sq);
	↓
  DBB_B_OCCUPIED.p64[0] ^= adbb_mask[sq].p64[0];
  DBB_B_OCCUPIED.p64[1] ^= adbb_mask[sq].p64[1];
	// DBB = double-sized bitboard