Answers.Body: <p>Basically, what you're missing is that while there may only be 64*2<sup>12</sup> possible different blocker values to consider, those values are spread out across almost the entire 64-bit number range, which is far too large to use as an index into an array (as that would require the array to have a capacity of 2<sup>64</sup> slots). So those blocker bitboards need to be transformed into some other number that can be used to index into a reasonably sized array.</p>
  <p>A traditional, general purpose hashmap could do this, but the algorithms used by them are built to spread similar values far apart in order to minimize collisions. However, in the case of magic bitboards, we know that there are many different blocker boards that will map into the same attack board, and our ideal state would be that the hashing algorithm will map all of the blockers that yield the same attacks into the same index in the table.</p>
  <p>The magic numbers involved with magic bitboards are meant to push all of the relevant bits from the blocker board into the same few bits so that we can then use just those bits from the result as the key into our table of attack boards. In the ideal state for rook moves, we would only need 12 bits, which would reduce the total size of the array from 2<sup>64</sup> down to 2<sup>12</sup> possible indexes.</p>
  <p>Essentially, the blocker board values need to be hashed in some way in order to be useable as a key into a dictionary. Given that fact, we may as well use a purpose-built hashing algorithm that is able to make efficient use of our resources.</p>
  <p><a href="https://analog-hors.github.io/site/magic-bitboards/" rel="nofollow noreferrer">This site's explanation is what made this click with me.</a></p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-07-14T16:55:23.340Z
Answers.Text: Thank you for the detailed explanation @Nelson. Totally agree with your first paragraph and this has led to me to using dictionaries rather than arrays. The point about hashing is interesting in that we want to embrace collisions under certain circumstances - I suspect I may end up revisiting this again at some point.
Answers.UserDisplayName: KrazyKattapilla
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-07-14T00:58:47.730Z
Answers.LastActivityDate: 2024-07-26T20:07:31.430Z
Answers.LastEditDate: 2024-07-26T20:07:31.430Z
Answers.UserDisplayName: Nelson O
Answers.Body: <p>I tested both approaches.</p>
  <p>Using the dictionary as detailed above does work and is conceptually easy to understand.</p>
  <p>Using magic number also works and seems to be much faster - for example, on my test machine it completes Perft tests between 30% and 50% quicker than the dictionary approach. It is however more complex in its approach and requires some initialisation code to set up the magic numbers.</p>
  <p>This means that, as with many things, it is a trade-off between simplicity and speed.</p>
  <p>As far as I can tell, the reason for the difference is that the dictionary approach hashes my 64 bit key to a 32 bit hash behind the scenes. I believe that this hashing is much more CPU intensive than the multiplication, two list look ups and  one bitwise shift needed when using magic numbers.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-07-26T19:28:43.880Z
Answers.LastActivityDate: 2024-07-26T19:28:43.880Z
Answers.UserDisplayName: KrazyKattapilla
Body: <p>I am modifying my chess engine to use a bitboard based approach to board representation instead of the current mailbox approach.</p>
  <p>I've read much about using magic bitboards to retrieve bitboards of legal moves.</p>
  <p>The approach is summed up in this Chess SE post (<a href="https://chess.stackexchange.com/q/15070/39493">Understanding magic bitboard</a>) with the following pseudocode</p>
  <pre><code>bbBlockers = bbAllPieces &amp; occupancyMaskRook[C3]
  
  databaseIndex = (int)((bbBlockers * magicNumberRook[C3]) &gt;&gt; rookMagicShifts[C3])
  
  bbMoveSquares = magicMovesRook[C3][databaseIndex] &amp; ~bbFriendlyPieces
  </code></pre>
  <p>I am comfortable with how this works. However, I am not sure why we bother with the magic numbers. Essentially, multiplying the blocker bitboard by the magic number for a given square gives us a key which we then use to look up the moves bitboard.</p>
  <p>Why can't we just use the integer value of the blockers bitboard as the key instead since it is just a 64 bit value?</p>
  <p>Going back to the pseudo-code above it would be as follows:</p>
  <pre><code>bbBlockers = bbAllPieces &amp; occupancyMaskRook[C3]
        
  bbMoveSquares = rookMoves[C3][bbBlockers] &amp; ~bbFriendlyPieces
  </code></pre>
  <p>Which indicates that removing magic numbers would reduce the number of operations needed.</p>
  <p>Also, looking at the numbers involved for rooks we have 64 possible squares and a maximum of 4096 (2<sup>12</sup>) which gives us 262,144 dictionary entries. Each entry is 16 bytes (8 for the key and 8 for the payload) so we only need to store 4,194,304 bytes (roughly 4MiB) so the storage requirements aren't huge. The values for bishops will be less so I'm not sure that this is a justification for avoiding the approach.</p>
  <p>I could just be missing a key point so I hope someone can help clarify things for me.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2024-07-13T10:23:21.980Z
Comments.Text: Presumably you’ve read https://www.chessprogramming.org/Magic_Bitboards but I will give the link here
Comments.UserDisplayName: Laska
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2024-07-13T20:09:31.967Z
Comments.Text: Thank you @Laska. This is one of many pages I have read. Interestingly it does mention CPU caching although I’m not sure if this is still such an issue due to CPU improvements since that page was last updated (3 years ago). Nevertheless, it the page is a useful resource and may be helpful to others reading this question.
Comments.UserDisplayName: KrazyKattapilla
Tags: <engines><programming>
Title: Why calculate magic numbers for bitboards rather than using the blocker bitboard as a key?
ThreadText: # Why calculate magic numbers for bitboards rather than using the blocker bitboard as a key?
  
  (Asked by: username_0 on 2024-07-12)
  
  I am modifying my chess engine to use a bitboard based approach to board representation instead of the current mailbox approach.
  
  I've read much about using magic bitboards to retrieve bitboards of legal moves.
  
  The approach is summed up in this Chess SE post ([Understanding magic bitboard](https://chess.stackexchange.com/q/15070/39493)) with the following pseudocode
  
  ```
  bbBlockers = bbAllPieces & occupancyMaskRook[C3]
  
  databaseIndex = (int)((bbBlockers * magicNumberRook[C3]) >> rookMagicShifts[C3])
  
  bbMoveSquares = magicMovesRook[C3][databaseIndex] & ~bbFriendlyPieces
  
  ```
  
  I am comfortable with how this works. However, I am not sure why we bother with the magic numbers. Essentially, multiplying the blocker bitboard by the magic number for a given square gives us a key which we then use to look up the moves bitboard.
  
  Why can't we just use the integer value of the blockers bitboard as the key instead since it is just a 64 bit value?
  
  Going back to the pseudo-code above it would be as follows:
  
  ```
  bbBlockers = bbAllPieces & occupancyMaskRook[C3]
        
  bbMoveSquares = rookMoves[C3][bbBlockers] & ~bbFriendlyPieces
  
  ```
  
  Which indicates that removing magic numbers would reduce the number of operations needed.
  
  Also, looking at the numbers involved for rooks we have 64 possible squares and a maximum of 4096 (212) which gives us 262,144 dictionary entries. Each entry is 16 bytes (8 for the key and 8 for the payload) so we only need to store 4,194,304 bytes (roughly 4MiB) so the storage requirements aren't huge. The values for bishops will be less so I'm not sure that this is a justification for avoiding the approach.
  
  I could just be missing a key point so I hope someone can help clarify things for me.
  
  **Tags:** engines, programming
  
  > **Comments:**
  > **username_1**: Presumably you’ve read https://www.chessprogramming.org/Magic_Bitboards but I will give the link here  
  > **username_0**: Thank you @username_1. This is one of many pages I have read. Interestingly it does mention CPU caching although I’m not sure if this is still such an issue due to CPU improvements since that page was last updated (3 years ago). Nevertheless, it the page is a useful resource and may be helpful to others reading this question.  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_2 on 2024-07-14. Score: 2 | Accepted answer
  
  Basically, what you're missing is that while there may only be 64\*212 possible different blocker values to consider, those values are spread out across almost the entire 64-bit number range, which is far too large to use as an index into an array (as that would require the array to have a capacity of 264 slots). So those blocker bitboards need to be transformed into some other number that can be used to index into a reasonably sized array.
  
  A traditional, general purpose hashmap could do this, but the algorithms used by them are built to spread similar values far apart in order to minimize collisions. However, in the case of magic bitboards, we know that there are many different blocker boards that will map into the same attack board, and our ideal state would be that the hashing algorithm will map all of the blockers that yield the same attacks into the same index in the table.
  
  The magic numbers involved with magic bitboards are meant to push all of the relevant bits from the blocker board into the same few bits so that we can then use just those bits from the result as the key into our table of attack boards. In the ideal state for rook moves, we would only need 12 bits, which would reduce the total size of the array from 264 down to 212 possible indexes.
  
  Essentially, the blocker board values need to be hashed in some way in order to be useable as a key into a dictionary. Given that fact, we may as well use a purpose-built hashing algorithm that is able to make efficient use of our resources.
  
  [This site's explanation is what made this click with me.](https://analog-hors.github.io/site/magic-bitboards/)
  
  > **Comments:**
  > **username_0**: Thank you for the detailed explanation @username_2. Totally agree with your first paragraph and this has led to me to using dictionaries rather than arrays. The point about hashing is interesting in that we want to embrace collisions under certain circumstances - I suspect I may end up revisiting this again at some point.  
  
  ---
  
  ### Answer by username_0 on 2024-07-26. Score: 1
  
  I tested both approaches.
  
  Using the dictionary as detailed above does work and is conceptually easy to understand.
  
  Using magic number also works and seems to be much faster - for example, on my test machine it completes Perft tests between 30% and 50% quicker than the dictionary approach. It is however more complex in its approach and requires some initialisation code to set up the magic numbers.
  
  This means that, as with many things, it is a trade-off between simplicity and speed.
  
  As far as I can tell, the reason for the difference is that the dictionary approach hashes my 64 bit key to a 32 bit hash behind the scenes. I believe that this hashing is much more CPU intensive than the multiplication, two list look ups and one bitwise shift needed when using magic numbers.
  
  
  ---
  
  