Answers.Body: <p>Your implementation looks incorrect to me. Here's the correct hyperbola quintessence implementation:</p>
  <pre><code>Bitboard hyp_quint(Square square, Bitboard occ, Bitboard mask) {
      return (((mask &amp; occ) - SQUARE_BB[square] * 2) ^
          reverse(reverse(mask &amp; occ) - reverse(SQUARE_BB[square]) * 2)) &amp; mask;
  }
  </code></pre>
  <ul>
  <li><code>mask</code> is the file/rank/NW-SE diagonal/NE-SW diagonal mask, depending on the sliding piece</li>
  <li><code>occ</code> is the <em>unmasked</em> occupied bitboard, equivalent to <code>get_all_pieces(pieceBB)</code> in the OP</li>
  <li><code>SQUARE_BB[square]</code> is a bitboard with a single set bit at the position of the sliding piece, equivalent to <code>sliderBB</code> in the OP</li>
  <li>The <code>reverse</code> function can be implemented as follows:</li>
  </ul>
  <pre><code>Bitboard reverse(Bitboard b) {
      b = (b &amp; 0x5555555555555555) &lt;&lt; 1 | ((b &gt;&gt; 1) &amp; 0x5555555555555555);
      b = (b &amp; 0x3333333333333333) &lt;&lt; 2 | ((b &gt;&gt; 2) &amp; 0x3333333333333333);
      b = (b &amp; 0x0f0f0f0f0f0f0f0f) &lt;&lt; 4 | ((b &gt;&gt; 4) &amp; 0x0f0f0f0f0f0f0f0f);
      b = (b &amp; 0x00ff00ff00ff00ff) &lt;&lt; 8 | ((b &gt;&gt; 8) &amp; 0x00ff00ff00ff00ff);
  
      return (b &lt;&lt; 48) | ((b &amp; 0xffff0000) &lt;&lt; 16) | ((b &gt;&gt; 16) &amp; 0xffff0000) | (b &gt;&gt; 48);
  }
  </code></pre>
  <p>So now if you want to generate sliding moves for a rook, you must call</p>
  <pre><code>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)]);
  }
  </code></pre>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-11-10T04:02:04.300Z
Answers.LastActivityDate: 2021-11-10T04:53:41.010Z
Answers.LastEditDate: 2021-11-10T04:53:41.010Z
Answers.UserDisplayName: Nihar Karve
Body: <p>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 <a href="https://www.chessprogramming.org/Hyperbola_Quintessence" rel="nofollow noreferrer">this algorithm</a> which approaches the problem, with the &quot;o^(o - 2r) trick&quot;, 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:</p>
  <pre><code>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) &amp; get_file_mask(sq);
  
    uint64_t normal = occ - 2 * sliderBB;
    uint64_t reverse = _byteswap_uint64(occ) - 2 * _byteswap_uint64(sliderBB);
  
    return normal ^ reverse;
  }
  </code></pre>
  <p>In this case, the <code>sliderBB</code> is:</p>
  <pre><code>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 
  </code></pre>
  <p>And the <code>occ</code> is:</p>
  <pre><code>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
  </code></pre>
  <p>And the function <code>compute_pseudo_files()</code> returns this:</p>
  <pre><code>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 
  </code></pre>
  <p>When I'm expecting this:</p>
  <pre><code>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
  </code></pre>
  <p>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.</p>
  
Tags: <engines><computer-chess><bitboard>
Title: Move generation for sliding pieces and Hyperbola Quintessence
ThreadText: # Move generation for sliding pieces and Hyperbola Quintessence
  
  (Asked by: username_0 on 2021-11-04)
  
  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](https://www.chessprogramming.org/Hyperbola_Quintessence) 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.
  
  **Tags:** engines, computer-chess, bitboard
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2021-11-10. Score: 2 | Accepted answer
  
  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)]);
  }
  
  ```
  
  
  ---
  
  