Answers.Body: <p>I think you're misunderstanding something here based on the way you formulated your question.  Multiplying the blockers by the magic and the shifting does <strong>not</strong> give you the attack set.  What it gives you is an index by which you can lookup the attack set in a pre-computed array.  The shifted product is a key, not a bitboard as you displayed it</p>
  <p>It is possible (and desireable) for multiple blocker sets to result in the same index and therefore have the same attack map.  Consider a rook on A1.  The attack set will be the same if there is a blocker on B1, blockers on B1 and C1, blockers on B1 and C1 and D1.</p>
  <p>As for how long it takes to generate the magics themselves, that depends on your hardware and on the speed of your algorithm.  I would say that only being able to test a thousand in a few seconds indicates a serious performance issue in your code.  I feel like stockfish claims to be able to generate them <em>all</em> in a second or so.</p>
  <p>Finally, the benefit of findind a &quot;better&quot; magic is what you said.  It reduces the size of the pre-computed array.  Lowering the memory footprint of an engine makes it more efficient in terms of cpu cache hits vs memory lookups.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-06-26T17:03:58.993Z
Answers.LastActivityDate: 2020-06-26T17:03:58.993Z
Answers.UserDisplayName: Jeff Wilson
Body: <p>I am working on my chess engine and wanted to finally implement magic bitboards to get a huge increase in performance.</p>
  
  <p>Basically I was writing a method to check if a number can be used as a magic for a given attack mask. I took a look at this table: <a href="https://www.chessprogramming.org/Best_Magics_so_far" rel="nofollow noreferrer">best magics</a> and tried to verify if these can actually be used.</p>
  
  <p>I tested it with the index 48 (rook on a7). I should probably say that I am working in Java and there are no unsigned values but this is not a problem because all shift-operations still work the same and the given magic for a7 is positive anyway.</p>
  
  <p>So I took the mask and populated it with some random blockers.</p>
  
  <pre><code>mask:                     random blockers:
  
  00000000                  00000000
  01111110                  00110010
  10000000                  10000000
  10000000                  10000000
  10000000                  10000000
  10000000                  00000000
  10000000                  00000000
  00000000                  00000000
  </code></pre>
  
  <p>I then took the magic number (0x48FFFE99FECFAA00) and took the random blockers bitboard and multiplied them. the result and the shifted result looks like this:</p>
  
  <pre><code>result                    shifted
  
  00000111                  00000000                           
  00011110                  00000000
  10011110                  00000000
  01010101                  00000000
  00000000                  00000000
  00000000                  00000000
  00000000                  11100000
  00000000                  11000000
  </code></pre>
  
  <p>The problem here is that the amount of bits does not equal the one of the random blockers which is a problem because the bits in shifted result must be the same as the amount of bits in the random blockers bitboard. Also different random blockers inputs resulted in the same output.</p>
  
  <blockquote>
    <p>Can somebody verify this? Where did I go wrong?</p>
  </blockquote>
  
  <hr>
  
  <blockquote>
    <p>Also I was wondering how long it takes to generate the magic numbers.
    My code was running for a few seconds and did not find a single one (I
    checked about one thousand). What is the density of valid magics?
    1/1000 ? 1/10000000?</p>
  </blockquote>
  
  <hr>
  
  <blockquote>
    <p>My last question is: Why are people trying to reduce their tables sizes of magics? I keep seeing this and people seem to have a real battle about who can go below x kByte. Is there a specific reason for this?</p>
  </blockquote>
  
  <p>EDIT:</p>
  
  <p>I found the problem with the magics. I compared the shifted result and they were the same for some blockers. but these had the same actual attack set.
  I am very happy for any kind of help!</p>
  
Tags: <engines><programming><bitboard>
Title: Are these magics wrong?
ThreadText: # Are these magics wrong?
  
  (Asked by: username_0 on 2020-01-26)
  
  I am working on my chess engine and wanted to finally implement magic bitboards to get a huge increase in performance.
  
  Basically I was writing a method to check if a number can be used as a magic for a given attack mask. I took a look at this table: [best magics](https://www.chessprogramming.org/Best_Magics_so_far) and tried to verify if these can actually be used.
  
  I tested it with the index 48 (rook on a7). I should probably say that I am working in Java and there are no unsigned values but this is not a problem because all shift-operations still work the same and the given magic for a7 is positive anyway.
  
  So I took the mask and populated it with some random blockers.
  
  ```
  mask:                     random blockers:
  
  00000000                  00000000
  01111110                  00110010
  10000000                  10000000
  10000000                  10000000
  10000000                  10000000
  10000000                  00000000
  10000000                  00000000
  00000000                  00000000
  
  ```
  
  I then took the magic number (0x48FFFE99FECFAA00) and took the random blockers bitboard and multiplied them. the result and the shifted result looks like this:
  
  ```
  result                    shifted
  
  00000111                  00000000                           
  00011110                  00000000
  10011110                  00000000
  01010101                  00000000
  00000000                  00000000
  00000000                  00000000
  00000000                  11100000
  00000000                  11000000
  
  ```
  
  The problem here is that the amount of bits does not equal the one of the random blockers which is a problem because the bits in shifted result must be the same as the amount of bits in the random blockers bitboard. Also different random blockers inputs resulted in the same output.
  
  > Can somebody verify this? Where did I go wrong?
  
  ---
  
  > Also I was wondering how long it takes to generate the magic numbers.
  > My code was running for a few seconds and did not find a single one (I
  > checked about one thousand). What is the density of valid magics?
  > 1/1000 ? 1/10000000?
  
  ---
  
  > My last question is: Why are people trying to reduce their tables sizes of magics? I keep seeing this and people seem to have a real battle about who can go below x kByte. Is there a specific reason for this?
  
  EDIT:
  
  I found the problem with the magics. I compared the shifted result and they were the same for some blockers. but these had the same actual attack set.
  I am very happy for any kind of help!
  
  **Tags:** engines, programming, bitboard
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2020-06-26. Score: 3 | Accepted answer
  
  I think you're misunderstanding something here based on the way you formulated your question. Multiplying the blockers by the magic and the shifting does **not** give you the attack set. What it gives you is an index by which you can lookup the attack set in a pre-computed array. The shifted product is a key, not a bitboard as you displayed it
  
  It is possible (and desireable) for multiple blocker sets to result in the same index and therefore have the same attack map. Consider a rook on A1. The attack set will be the same if there is a blocker on B1, blockers on B1 and C1, blockers on B1 and C1 and D1.
  
  As for how long it takes to generate the magics themselves, that depends on your hardware and on the speed of your algorithm. I would say that only being able to test a thousand in a few seconds indicates a serious performance issue in your code. I feel like stockfish claims to be able to generate them *all* in a second or so.
  
  Finally, the benefit of findind a "better" magic is what you said. It reduces the size of the pre-computed array. Lowering the memory footprint of an engine makes it more efficient in terms of cpu cache hits vs memory lookups.
  
  
  ---
  
  