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<M> mBishopAttacks[64][512]; // 256 K
  bitset<M> mRookAttacks[64][4096]; // 2048K
  
  bitset<M> bishopAttacks(bitset<M> 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](https://github.com/nkarve/surge/blob/master/src/tables.cpp).
  
  ```
  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**: @username_3 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?  
  
  ---
  
  