Quad-Bitboards are simply a vector of four bitboards for various purposes. Those vectors are suited for SIMD-instruction sets like SSE2 and may kept for instance in two 128-bit XMM-registers, or AVX2 with one 256-bit YMM-register.
The idea is during make/unmake move to xor the quad-bitboard by from- and to-aspects similar to the hashkey. This implies the information of the moving and possibly captured piece is coded inside the move structure, as well as special moves like double push (triggering ep), castling, en passant and promotions.
Another application is to perform parallel prefixKogge-Stone algorithms with quad-bitboards. That allows to propagate four or up to 15 bitboards with one direction fill.
qbb.bb[0]= white rooks or queens
qbb.bb[1]= black rooks or queens
qbb.bb[2]= black king
qbb.bb[3]= white king
Using an appropriate C++ QBB-class with overloaded operators using SSE2-intrinsics, allows to write it in usual syntax...
void nortOccl(QBB &gen /* in, out */, U64 pro64){
QBB pro(pro64);
gen |= pro &(gen <<8);
pro = pro &(pro <<8);
gen |= pro &(gen <<16);
pro = pro &(pro <<16);
gen |= pro &(gen <<32);}
A quad-bitboard is simply a dense board-structure, where arbitrary piece-code-nibbles reside vertically in four bitboards. Together with hashkeys (normal and pawnhash), ep and castle states, movecount, reversable movecount, and some more the whole board structure takes 64-bytes - and make/unmake is almost one simdwise "xor/add/and" instruction with delta[moveNr] on that board-structure.
Quad-bitboards with up to 15 arbitrary codes may be used in fill-algorithms, to generate the multiplexed quad-bitboard in one run with one common empty square propagator. But multiplexing and demultiplexing makes it rather hard to use efficiently.
One simpler coding scheme, where each bitboard is a disjoint set, is following:
bb0: white rooks or queens
bb1: white king
bb2: black king
bb3: black rooks or queens
Now we can fill this quad-bitboard left and right wise (and for the other directions as well). We can aggregate the real sliding attacks for the taboo sets of the opponent king. We can do simdwise leftFill(bb1:bb0) & rightFill(bb3:bb2) and rightFill(bb1:bb0) & leftFill(bb3:bb2) to get inbetween sets of sliders with opponent king. In case of a sliding check (no piece inbetween) we can use this set as possible target set of check-breaking moves. Otherwise we can intersect it with own pieces to get pinned pieces (in total and by direction) or with opposite pieces to get discovered checkers...
Table of Contents
Quad-Bitboards are simply a vector of four bitboards for various purposes. Those vectors are suited for SIMD-instruction sets like SSE2 and may kept for instance in two 128-bit XMM-registers, or AVX2 with one 256-bit YMM-register.
As Board-Definition
One application is to keep one quad-bitboard as compact board-definition with vertical nibbles as piece or empty square codes:To get the disjoint bitboards similar to the bitboard board-definition is about some bitwise operations:
The idea is during make/unmake move to xor the quad-bitboard by from- and to-aspects similar to the hashkey. This implies the information of the moving and possibly captured piece is coded inside the move structure, as well as special moves like double push (triggering ep), castling, en passant and promotions.
SSE2 Conversions
To Hex Bitboards
A conversion of a quad-bitboard to 16 disjoint bitboards can be done quite efficiently with SSE2 instructions:To Mailbox
Converting the 64 vertical nibbles to a 8x8 board is more expensive and should be avoided on the fly, let say once per node.As Sliding Piece Generators
Another application is to perform parallel prefix Kogge-Stone algorithms with quad-bitboards. That allows to propagate four or up to 15 bitboards with one direction fill.Using an appropriate C++ QBB-class with overloaded operators using SSE2-intrinsics, allows to write it in usual syntax...
Quotes
Quote by Gerd Isenberg [1]Quad-bitboards with up to 15 arbitrary codes may be used in fill-algorithms, to generate the multiplexed quad-bitboard in one run with one common empty square propagator. But multiplexing and demultiplexing makes it rather hard to use efficiently.
One simpler coding scheme, where each bitboard is a disjoint set, is following:
bb0: white rooks or queens
bb1: white king
bb2: black king
bb3: black rooks or queens
Now we can fill this quad-bitboard left and right wise (and for the other directions as well). We can aggregate the real sliding attacks for the taboo sets of the opponent king. We can do simdwise leftFill(bb1:bb0) & rightFill(bb3:bb2) and rightFill(bb1:bb0) & leftFill(bb3:bb2) to get inbetween sets of sliders with opponent king. In case of a sliding check (no piece inbetween) we can use this set as possible target set of check-breaking moves. Otherwise we can intersect it with own pieces to get pinned pieces (in total and by direction) or with opposite pieces to get discovered checkers...
See also
Forum Posts
References
What links here?
Up one Level