4

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.

0

1 Answer 1

2

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)]);
}

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.