Move generation for sliding pieces and Hyperbola Quintessence

Question

I'm working on a bitboard-based chess engine at the moment and I have managed to generate pseudo-legal moves for knights, kings and pawns. However, I'm still trying to wrap my head around sliding pieces (bishops, rooks, queens). I have come across this algorithm which approaches the problem, with the "o^(o - 2r) trick", but I found it overall quite confusing. I have tried implementing it for files in the following function but it doesn't seem to work:

uint64_t compute_pseudo_file(uint64_t pieceBB[], uint64_t sliderBB, uint64_t own_side) {
  // o^(o - 2r) 
  int sq = get_square(sliderBB);

  uint64_t occ = get_all_pieces(pieceBB) & get_file_mask(sq);

  uint64_t normal = occ - 2 * sliderBB;
  uint64_t reverse = _byteswap_uint64(occ) - 2 * _byteswap_uint64(sliderBB);

  return normal ^ reverse;
}

In this case, the sliderBB is:

0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0

And the occ is:

0 0 0 1 0 0 0 0
0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0
0 0 0 1 0 0 0 0

And the function compute_pseudo_files() returns this:

0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
1 1 1 1 0 0 0 0
0 0 0 0 1 1 1 1
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0

When I'm expecting this:

0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0
0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0

I'm just getting into bitboards and bitwise manipulation now, so I'm clearly unfamiliar with a lot of stuff. I would appreciate any advice from anyone who has experience with these implementations and specifically on how to implement this algorithm for generating pseudo-legal moves for sliding pieces. I also think that this post would be helpful for others who are getting into chess engines and bitboards.

Nihar Karve · Accepted Answer · 2021-11-10T04:53:41.010

Your implementation looks incorrect to me. Here's the correct hyperbola quintessence implementation:

Bitboard hyp_quint(Square square, Bitboard occ, Bitboard mask) {
    return (((mask & occ) - SQUARE_BB[square] * 2) ^
        reverse(reverse(mask & occ) - reverse(SQUARE_BB[square]) * 2)) & mask;
}

mask is the file/rank/NW-SE diagonal/NE-SW diagonal mask, depending on the sliding piece
occ is the unmasked occupied bitboard, equivalent to get_all_pieces(pieceBB) in the OP
SQUARE_BB[square] is a bitboard with a single set bit at the position of the sliding piece, equivalent to sliderBB in the OP
The reverse function can be implemented as follows:

Bitboard reverse(Bitboard b) {
    b = (b & 0x5555555555555555) << 1 | ((b >> 1) & 0x5555555555555555);
    b = (b & 0x3333333333333333) << 2 | ((b >> 2) & 0x3333333333333333);
    b = (b & 0x0f0f0f0f0f0f0f0f) << 4 | ((b >> 4) & 0x0f0f0f0f0f0f0f0f);
    b = (b & 0x00ff00ff00ff00ff) << 8 | ((b >> 8) & 0x00ff00ff00ff00ff);

    return (b << 48) | ((b & 0xffff0000) << 16) | ((b >> 16) & 0xffff0000) | (b >> 48);
}

So now if you want to generate sliding moves for a rook, you must call

Bitboard get_rook_attacks(Square square, Bitboard occ) {
    return hyp_quint(square, occ, MASK_FILE[file_of(square)]) |
           hyp_quint(square, occ, MASK_RANK[rank_of(square)]);
}

Move generation for sliding pieces and Hyperbola Quintessence

1 Answers1