Answers.Body: <p>It is probably most efficient if I paste my code from my <a href="https://github.com/nkarve/surge/blob/master/src/tables.cpp" rel="nofollow noreferrer">chess move generator on GitHub</a>.</p>
  <pre><code>int ROOK_ATTACK_SHIFTS[64];
  Bitboard ROOK_ATTACK_MASKS[64];
  Bitboard ROOK_ATTACKS[64][4096];
  
  void initialise_rook_attacks() {
      Bitboard edges, subset, index;
  
      for (Square sq = a1; sq &lt;= h8; ++sq) {
          edges = ((MASK_RANK[AFILE] | MASK_RANK[HFILE]) &amp; ~MASK_RANK[rank_of(sq)]) |
              ((MASK_FILE[AFILE] | MASK_FILE[HFILE]) &amp; ~MASK_FILE[file_of(sq)]);
  
          ROOK_ATTACK_MASKS[sq] = (MASK_RANK[rank_of(sq)]
              ^ MASK_FILE[file_of(sq)]) &amp; ~edges;
  
          ROOK_ATTACK_SHIFTS[sq] = 64 - pop_count(ROOK_ATTACK_MASKS[sq]);
  
          subset = 0;
          do {
              index = subset;
              index = index * ROOK_MAGICS[sq];
              index = index &gt;&gt; ROOK_ATTACK_SHIFTS[sq];
              ROOK_ATTACKS[sq][index] = get_rook_attacks_for_init(sq, subset);
              subset = (subset - ROOK_ATTACK_MASKS[sq]) &amp; ROOK_ATTACK_MASKS[sq];
          } while (subset);
      }
  }
  </code></pre>
  <p>Some comments:</p>
  <ul>
  <li><p>For each square, the bitboard stored in the attacks table is determined by a complicated cycling algorithm. You start with an empty bitboard <code>subset</code>, then manipulate it using the magics and the masks generated previously. This gives you an index. You then initialise the attacks table at <code>ROOK_ATTACKS[sq][index]</code> as the bitboard of slider moves from that square, using the initial value of <code>subset</code> as the occupation bitboard. <code>subset</code> is then updated using the masks, and the loop continues. The nature of the magic numbers is that, starting with <code>subset=0</code>, you will cycle through all 4096 indices (not in order), and <code>subset</code> will turn into the correct &quot;representative&quot; occupation bitboard for all 4096 of these.</p>
  </li>
  <li><p>The value of &quot;9&quot; while bitshifting to calculate the index should <em>not</em> be hardcoded. Instead, it should depend on whether the piece is in the centre, on an edge or in a corner, which is what <code>ROOK_ATTACK_MASKS</code> and <code>ROOK_ATTACK_SHIFTS</code> are for. I believe excluding these is a little-known bug</p>
  </li>
  <li><p>Once you have generated the occupation/blockers bitboard for a particular index (running from 0 to 4095 for rooks), you can generate the sliding moves to initialise the attacks matrix in any way you want. I personally used hyperbola quintessence, but using a simple flood fill poses no problems, it's all pregenerated anyway</p>
  </li>
  </ul>
  <p>Unfortunately the chess programming wiki does not seem to be very useful on these matters; you are best off reading the original works and talkchess posts by Pradyumna Kannan et al.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-12-20T17:44:27.227Z
Answers.Text: I am confused about this `subset = (subset - ROOK_ATTACK_MASKS[sq]) & ROOK_ATTACK_MASKS[sq];` line. How exactly is it supposed to work, because it doesn't for me?
Answers.UserDisplayName: Tom Gebel
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-12-29T09:20:20.820Z
Answers.Text: @TomGebel could you elaborate on what the issue is? Which programming language are you using?
Answers.UserDisplayName: Nihar Karve
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-12-30T17:23:26.457Z
Answers.Text: I am using C++. You claim that `subset` should turn into all possible permutations of the attack mask, but it does not when I try to replicate your example. The attack mask generation is definitely working correctly, I don't see where I could have made a mistake. No matter what square I am indexing, `subset` always turns to `1` and then to `0`. Any ideas?
Answers.UserDisplayName: Tom Gebel
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-06-17T05:06:33.450Z
Answers.LastActivityDate: 2021-06-17T05:06:33.450Z
Answers.UserDisplayName: Nihar Karve
Body: <p>I'm currently coding a chess engine in C++, and have run into a bit of trouble with my magic bitboard implementation.</p>
  <p>So far, I have a function that calculates blockerBoards (all the possible pieces that can block the rook or the bishop).</p>
  <p>From there, I have the following code to take these blockerBoards and convert them into attack tables:</p>
  <pre><code>bitset&lt;M&gt; mBishopAttacks[64][512]; // 256 K
  bitset&lt;M&gt; mRookAttacks[64][4096]; // 2048K
  
  bitset&lt;M&gt; bishopAttacks(bitset&lt;M&gt; blockerBoard, int sq) {
      unsigned long long index = blockerBoard.to_ullong();
      index *= bishopMagics[sq];
      index &gt;&gt;= 64-9
      return mBishopAttacks[sq][index]; //outputs corresponding attack board
  }
  </code></pre>
  <p>Note that I got the array of magic numbers, bishopMagics[64], from somewhere on the web.</p>
  <p>How do I initialize these attack tables, mBishopAttacks and mRookAttacks? Currently, they are empty. Do I simply have to calculate the attack tables for each possible permutation of blockers?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-03-12T18:26:38.387Z
Comments.Text: I assume you know this [wiki](https://www.chessprogramming.org/Bitboards)?
Comments.UserDisplayName: Sleafar
Tags: <engines><programming><bitboard>
Title: How do I complete this implementation of magic bitboards?
ThreadText: # How do I complete this implementation of magic bitboards?
  
  (Asked by: username_0 on 2021-03-10)
  
  I'm currently coding a chess engine in C++, and have run into a bit of trouble with my magic bitboard implementation.
  So far, I have a function that calculates blockerBoards (all the possible pieces that can block the rook or the bishop).
  From there, I have the following code to take these blockerBoards and convert them into attack tables:
  bitset mBishopAttacks[64][512]; // 256 K
  bitset mRookAttacks[64][4096]; // 2048K
  
  bitset bishopAttacks(bitset blockerBoard, int sq) {
      unsigned long long index = blockerBoard.to_ullong();
      index *= bishopMagics[sq];
      index >>= 64-9
      return mBishopAttacks[sq][index]; //outputs corresponding attack board
  }
  
  Note that I got the array of magic numbers, bishopMagics[64], from somewhere on the web.
  How do I initialize these attack tables, mBishopAttacks and mRookAttacks? Currently, they are empty. Do I simply have to calculate the attack tables for each possible permutation of blockers?
  
  **Tags:** engines, programming, bitboard
  
  > **Comments:**
  > **username_1**: I assume you know this [wiki](https://www.chessprogramming.org/Bitboards)?  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2021-06-17. Score: 3 | Accepted answer
  
  It is probably most efficient if I paste my code from my chess move generator on GitHub.
  int ROOK_ATTACK_SHIFTS[64];
  Bitboard ROOK_ATTACK_MASKS[64];
  Bitboard ROOK_ATTACKS[64][4096];
  
  void initialise_rook_attacks() {
      Bitboard edges, subset, index;
  
      for (Square sq = a1; sq <= h8; ++sq) {
          edges = ((MASK_RANK[AFILE] | MASK_RANK[HFILE]) & ~MASK_RANK[rank_of(sq)]) |
              ((MASK_FILE[AFILE] | MASK_FILE[HFILE]) & ~MASK_FILE[file_of(sq)]);
  
          ROOK_ATTACK_MASKS[sq] = (MASK_RANK[rank_of(sq)]
              ^ MASK_FILE[file_of(sq)]) & ~edges;
  
          ROOK_ATTACK_SHIFTS[sq] = 64 - pop_count(ROOK_ATTACK_MASKS[sq]);
  
          subset = 0;
          do {
              index = subset;
              index = index * ROOK_MAGICS[sq];
              index = index >> ROOK_ATTACK_SHIFTS[sq];
              ROOK_ATTACKS[sq][index] = get_rook_attacks_for_init(sq, subset);
              subset = (subset - ROOK_ATTACK_MASKS[sq]) & ROOK_ATTACK_MASKS[sq];
          } while (subset);
      }
  }
  
  Some comments:
  
  For each square, the bitboard stored in the attacks table is determined by a complicated cycling algorithm. You start with an empty bitboard subset, then manipulate it using the magics and the masks generated previously. This gives you an index. You then initialise the attacks table at ROOK_ATTACKS[sq][index] as the bitboard of slider moves from that square, using the initial value of subset as the occupation bitboard. subset is then updated using the masks, and the loop continues. The nature of the magic numbers is that, starting with subset=0, you will cycle through all 4096 indices (not in order), and subset will turn into the correct "representative" occupation bitboard for all 4096 of these.
  
  The value of "9" while bitshifting to calculate the index should not be hardcoded. Instead, it should depend on whether the piece is in the centre, on an edge or in a corner, which is what ROOK_ATTACK_MASKS and ROOK_ATTACK_SHIFTS are for. I believe excluding these is a little-known bug
  
  Once you have generated the occupation/blockers bitboard for a particular index (running from 0 to 4095 for rooks), you can generate the sliding moves to initialise the attacks matrix in any way you want. I personally used hyperbola quintessence, but using a simple flood fill poses no problems, it's all pregenerated anyway
  
  
  Unfortunately the chess programming wiki does not seem to be very useful on these matters; you are best off reading the original works and talkchess posts by Pradyumna Kannan et al.
  
  > **Comments:**
  > **username_3**: I am confused about this `subset = (subset - ROOK_ATTACK_MASKS[sq]) & ROOK_ATTACK_MASKS[sq];` line. How exactly is it supposed to work, because it doesn't for me?  
  > **username_2**: @TomGebel could you elaborate on what the issue is? Which programming language are you using?  
  > **username_3**: I am using C++. You claim that `subset` should turn into all possible permutations of the attack mask, but it does not when I try to replicate your example. The attack mask generation is definitely working correctly, I don't see where I could have made a mistake. No matter what square I am indexing, `subset` always turns to `1` and then to `0`. Any ideas?  
  
  ---
  
  