Answers.Body: <p>I hit a similar issue when generating my magic bitboards. It seemed that my level of shifting was too aggressive and setting it to 50 resolved the problem.</p>
  <p>I haven't followed your code all the way through so you may already be doing this, but the other thing to keep in mind is that collisions are okay IF they result in the same set of moves being generated.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-09-01T14:11:56.877Z
Answers.LastActivityDate: 2024-09-01T18:38:33.363Z
Answers.LastEditDate: 2024-09-01T18:38:33.363Z
Answers.UserDisplayName: KrazyKattapilla
Body: <p>I am currently working on making a Chess Engine in Java and have tried to implement a Magic Number Generator. However, the generator always seems to get stuck on a certain index and can't get past it. I suspect this is because of an error in the indexing but I can't seem to find anything wrong with the indexing. Any help will be much appreciated. Everything other than the generator seems to be working. The generator is at the bottom of the post if you want to skip past the rest.</p>
  <p>The code to initialise the relevant occupancy lookup tables for bishops and rooks is as follows:</p>
  <pre><code>static void initBishopRelevantOccupancy() {
    for (int rankIndex = 1; rankIndex &lt;= 8; rankIndex++) {
      for (int fileIndex = A; fileIndex &lt;= H; fileIndex++) {
        int squareIndex = ((rankIndex - 1) * 8) + (fileIndex - 1);
        bishopRelevantOccupancy[squareIndex] =
            ((DIAGONAL[8 + (rankIndex - 1) - (fileIndex - 1)])
                    ^ (ANTIDIAGONAL[1 + (rankIndex - 1) + (fileIndex - 1)]))
                &amp; ~(RANK[8] | FILE[H] | RANK[1] | FILE[A]);
      }
    }
  }
  
  
  static void initRookRelevantOccupancy() {
    for (int rankIndex = 1; rankIndex &lt;= 8; rankIndex++) {
      for (int fileIndex = A; fileIndex &lt;= H; fileIndex++) {
        int squareIndex = ((rankIndex - 1) * 8) + (fileIndex - 1);
        rookRelevantOccupancy[squareIndex] =
            ~getSquare(squareIndex)
                &amp; ((RANK[rankIndex] &amp; ~(FILE[A] | FILE[H]))
                    ^ (FILE[fileIndex] &amp; ~(RANK[1] | RANK[8])));
      }
    }
  }
  </code></pre>
  <p>(PS: The indexing for the lookup tables for the RANKS, FILES, DIAGONALS, and ANTIDIAGONALS start at 1 since the the first rank is rank 1. This is done for the sake of readability and has no impact on the program besides the fact that i have to subtract 1 from the indexes to calculate the square index.)</p>
  <p>The code for shifting the index key into the relevant occupancies is as follows:</p>
  <pre><code>static long getLS1B(long bitboard) {
    return bitboard &amp; -bitboard;
  }
  
  static long getOccupancy(long relevantOccupancy, int index) {
    long  occupancy   = 0;
    int   cardinality = getPopulationCount(relevantOccupancy);
  
    for (int bit = 0; bit &lt; cardinality; bit++) {
      long square = getLS1B(relevantOccupancy);
  
      relevantOccupancy ^= square;
  
      if ((index &amp; (1 &lt;&lt; bit)) != 0) {
        occupancy |= square;
      }
    }
  
    return occupancy;
  }
  </code></pre>
  <p>The code to get the shift values to get the magic index is as follows:</p>
  <pre><code>static int[] getShifts(long[] relevantOccupancy) {
    int[] shifts = new int[64];
  
    for (int squareIndex = 0; squareIndex &lt; 64; squareIndex++) {
      int numberOfBits =
          getPopulationCount(
              relevantOccupancy[squareIndex]);
      shifts[squareIndex] = 64 - numberOfBits;
    }
  
    return shifts;
  }
  </code></pre>
  <p>The code to get the ray attacks is as follows:</p>
  <pre><code>/*
   *     Compass Rose
   *
   *     NW    N    NE
   *      +7  +8  +9
   *        \  |  /
   *   W -1 -- 0 -- +1 E
   *        /  |  \
   *      -9  -8  -7
   *     SW    S    SE
   *
   */
  
  // Ray Directions
  static final int
      NORTH = +8,
      EAST  = +1,
      SOUTH = -8,
      WEST  = -1,
  
      NORTH_EAST = NORTH + EAST,
      SOUTH_EAST = SOUTH + EAST,
      SOUTH_WEST = SOUTH + WEST,
      NORTH_WEST = NORTH + WEST;
  
  static long getRayAttack(int squareIndex, int DIRECTION, long mask, long occupancy) {
    long ray = 0;
    int raySquareIndex = squareIndex;
  
    while ((getSquare(raySquareIndex) &amp; mask) == 0) {
      if ((getSquare(raySquareIndex) &amp; occupancy) == 0) {
        ray |= getSquare(raySquareIndex);
      } else {
        break;
      }
      raySquareIndex += DIRECTION;
    }
  
    ray |= getSquare(raySquareIndex);
    ray ^= getSquare(squareIndex);
  
    return ray;
  }
  </code></pre>
  <p>The code to initialise the move lookup tables or attack sets for bishops and rooks is as follows:</p>
  <pre><code>static void initBishopMoveLookupTable() {
      initBishopRelevantOccupancy();
      initBishopShifts();
  
      for (int index = 0; index &lt; 512; index++) {
        for (int squareIndex = 0; squareIndex &lt; 64; squareIndex++) {
          int fileIndex = (squareIndex % 8) + 1;
          int rankIndex = (squareIndex / 8) + 1;
          int diagonalIndex = 8 + (rankIndex - 1) - (fileIndex - 1);
          int antiDiagonalIndex = 1 + (rankIndex - 1) + (fileIndex - 1);
  
          long occupancy = getOccupancy(bishopRelevantOccupancy[squareIndex], index);
  
          long northEastRayAttack = getRayAttack(squareIndex, NORTH_EAST, (RANK[8] | FILE[H]), occupancy);
          long southEastRayAttack = getRayAttack(squareIndex, SOUTH_EAST, (RANK[1] | FILE[H]), occupancy);
          long southWestRayAttack = getRayAttack(squareIndex, SOUTH_WEST, (RANK[1] | FILE[A]), occupancy);
          long northWestRayAttack = getRayAttack(squareIndex, NORTH_WEST, (RANK[8] | FILE[A]), occupancy);
  
          bishopMoveLookupTable[squareIndex][index] =
              northEastRayAttack | southEastRayAttack | southWestRayAttack | northWestRayAttack;
        }
      }
    }
  
  static void initRookMoveLookupTable() {
    for (int squareIndex = 0; squareIndex &lt; 64; squareIndex++) {
      for (int index = 0; index &lt; 4096; index++) {
        int fileIndex = (squareIndex % 8) + 1;
        int rankIndex = (squareIndex / 8) + 1;
        long occupancy = getOccupancy(rookRelevantOccupancy[squareIndex], index);
  
        long northRayAttack = getRayAttack(squareIndex, NORTH, RANK[8], occupancy);
        long eastRayAttack = getRayAttack(squareIndex, EAST, FILE[H], occupancy);
        long southRayAttack = getRayAttack(squareIndex, SOUTH, RANK[1], occupancy);
        long westRayAttack = getRayAttack(squareIndex, WEST, FILE[A], occupancy);
  
        rookMoveLookupTable[squareIndex][index] =
            northRayAttack | eastRayAttack | southRayAttack | westRayAttack;
      }
    }
  }
  </code></pre>
  <p>The code to get the population count or cardinality of a bitboard using byte lookup is as follows:</p>
  <pre><code>static void initPopulationCount() {
    populationCount[0] = 0;
  
    for (int index = 1; index &lt; 256; index++) {
      populationCount[index] = populationCount[index / 2] + (index &amp; 1);
    }
  }
  
  static int getPopulationCount(long bitboard) {
    return  populationCount[(int) ((bitboard &gt;&gt;&gt;  0) &amp; RANK[1])]
          + populationCount[(int) ((bitboard &gt;&gt;&gt;  8) &amp; RANK[1])]
          + populationCount[(int) ((bitboard &gt;&gt;&gt; 16) &amp; RANK[1])]
          + populationCount[(int) ((bitboard &gt;&gt;&gt; 24) &amp; RANK[1])]
          + populationCount[(int) ((bitboard &gt;&gt;&gt; 32) &amp; RANK[1])]
          + populationCount[(int) ((bitboard &gt;&gt;&gt; 40) &amp; RANK[1])]
          + populationCount[(int) ((bitboard &gt;&gt;&gt; 48) &amp; RANK[1])]
          + populationCount[(int) ((bitboard &gt;&gt;&gt; 56) &amp; RANK[1])];
  }
  </code></pre>
  <p>The code for the random number generator to generate magic candidates is as follows:</p>
  <pre><code>static long generateRandomLong() {
    Random random = new Random();
  
    long random0 = random.nextLong() &amp; 0xFFFF;
    long random1 = random.nextLong() &amp; 0xFFFF;
    long random2 = random.nextLong() &amp; 0xFFFF;
    long random3 = random.nextLong() &amp; 0xFFFF;
  
    return (random0 &lt;&lt; 0) | (random1 &lt;&lt; 16) | (random2 &lt;&lt; 32) | (random3 &lt;&lt; 48);
  }
  
  static long getMagicCandidate() {
    return generateRandomLong() &amp; generateRandomLong() &amp; generateRandomLong();
  }
  </code></pre>
  <p>The code to get the magic index is as follows:</p>
  <pre><code>static int getMagicIndex(long maskedOccupancy, long magicNumber, int shift) {
    return (int) ((maskedOccupancy * magicNumber) &gt;&gt;&gt; shift);
  }
  </code></pre>
  <p>The code to get the magic numbers is as follows:</p>
  <pre><code>static long getMagicNumber(long[] moveLookupTable, long relevantOccupancy, int shift) {
    boolean found         = false;
    int     numberOfBits  = getPopulationCount(relevantOccupancy);
  
    long[]  occupancies   = new long[1 &lt;&lt; numberOfBits];
    long[]  tempMLT       = new long[1 &lt;&lt; numberOfBits];
  
    for (int index = 0; index &lt; (1 &lt;&lt; numberOfBits); index++) {
      occupancies[index] = getOccupancy(relevantOccupancy, index);
    }
  
    while (!found) {
      long magicNumber = getMagicCandidate();
  
      if (getPopulationCount((relevantOccupancy * magicNumber) &amp; 0xFF00000000000000L) &lt; 6) {
        continue;
      }
  
      for (int i = 0; i &lt; (1 &gt;&gt; numberOfBits); i++) {
        tempMLT[i] = 0;
      }
  
      boolean fail = false;
  
      for (int index = 0; !fail &amp;&amp; index &lt; (1 &lt;&lt; numberOfBits); index++) {
        int  magicIndex = getMagicIndex(occupancies[index], magicNumber, shift);
  
          if (tempMLT[magicIndex] == 0) {
            tempMLT[magicIndex] = moveLookupTable[index];
          } else if (tempMLT[magicIndex] != moveLookupTable[index]) {
            fail = true;
          }
        }
        if (!fail) {
          return magicNumber;
        }
      }
      System.out.println(&quot;FAIL&quot;);
      return 0;
    }
  </code></pre>
  <p>Everything except the magic number generator seems to be working. The generator gets stuck on some indexes and doesn't go any further than them. What I've noticed is that it seems to be getting stuck on indexes that are powers of two or in other words, indexes who only have one bit when converted to binary.</p>
  <p>The mapping I use is the standard Little Endian File Rank Mapping.</p>
  
Tags: <programming><bishops><rooks><bitboard>
Title: How can I implement a Magic Bitboard Generator in Java?
ThreadText: # How can I implement a Magic Bitboard Generator in Java?
  
  (Asked by: username_0 on 2024-05-08)
  
  I am currently working on making a Chess Engine in Java and have tried to implement a Magic Number Generator. However, the generator always seems to get stuck on a certain index and can't get past it. I suspect this is because of an error in the indexing but I can't seem to find anything wrong with the indexing. Any help will be much appreciated. Everything other than the generator seems to be working. The generator is at the bottom of the post if you want to skip past the rest.
  The code to initialise the relevant occupancy lookup tables for bishops and rooks is as follows:
  static void initBishopRelevantOccupancy() {
    for (int rankIndex = 1; rankIndex <= 8; rankIndex++) {
      for (int fileIndex = A; fileIndex <= H; fileIndex++) {
        int squareIndex = ((rankIndex - 1) * 8) + (fileIndex - 1);
        bishopRelevantOccupancy[squareIndex] =
            ((DIAGONAL[8 + (rankIndex - 1) - (fileIndex - 1)])
                    ^ (ANTIDIAGONAL[1 + (rankIndex - 1) + (fileIndex - 1)]))
                & ~(RANK[8] | FILE[H] | RANK[1] | FILE[A]);
      }
    }
  }
  
  
  static void initRookRelevantOccupancy() {
    for (int rankIndex = 1; rankIndex <= 8; rankIndex++) {
      for (int fileIndex = A; fileIndex <= H; fileIndex++) {
        int squareIndex = ((rankIndex - 1) * 8) + (fileIndex - 1);
        rookRelevantOccupancy[squareIndex] =
            ~getSquare(squareIndex)
                & ((RANK[rankIndex] & ~(FILE[A] | FILE[H]))
                    ^ (FILE[fileIndex] & ~(RANK[1] | RANK[8])));
      }
    }
  }
  
  (PS: The indexing for the lookup tables for the RANKS, FILES, DIAGONALS, and ANTIDIAGONALS start at 1 since the the first rank is rank 1. This is done for the sake of readability and has no impact on the program besides the fact that i have to subtract 1 from the indexes to calculate the square index.)
  The code for shifting the index key into the relevant occupancies is as follows:
  static long getLS1B(long bitboard) {
    return bitboard & -bitboard;
  }
  
  static long getOccupancy(long relevantOccupancy, int index) {
    long  occupancy   = 0;
    int   cardinality = getPopulationCount(relevantOccupancy);
  
    for (int bit = 0; bit < cardinality; bit++) {
      long square = getLS1B(relevantOccupancy);
  
      relevantOccupancy ^= square;
  
      if ((index & (1 << bit)) != 0) {
        occupancy |= square;
      }
    }
  
    return occupancy;
  }
  
  The code to get the shift values to get the magic index is as follows:
  static int[] getShifts(long[] relevantOccupancy) {
    int[] shifts = new int[64];
  
    for (int squareIndex = 0; squareIndex < 64; squareIndex++) {
      int numberOfBits =
          getPopulationCount(
              relevantOccupancy[squareIndex]);
      shifts[squareIndex] = 64 - numberOfBits;
    }
  
    return shifts;
  }
  
  The code to get the ray attacks is as follows:
  /*
   *     Compass Rose
   *
   *     NW    N    NE
   *      +7  +8  +9
   *        \  |  /
   *   W -1 -- 0 -- +1 E
   *        /  |  \
   *      -9  -8  -7
   *     SW    S    SE
   *
   */
  
  // Ray Directions
  static final int
      NORTH = +8,
      EAST  = +1,
      SOUTH = -8,
      WEST  = -1,
  
      NORTH_EAST = NORTH + EAST,
      SOUTH_EAST = SOUTH + EAST,
      SOUTH_WEST = SOUTH + WEST,
      NORTH_WEST = NORTH + WEST;
  
  static long getRayAttack(int squareIndex, int DIRECTION, long mask, long occupancy) {
    long ray = 0;
    int raySquareIndex = squareIndex;
  
    while ((getSquare(raySquareIndex) & mask) == 0) {
      if ((getSquare(raySquareIndex) & occupancy) == 0) {
        ray |= getSquare(raySquareIndex);
      } else {
        break;
      }
      raySquareIndex += DIRECTION;
    }
  
    ray |= getSquare(raySquareIndex);
    ray ^= getSquare(squareIndex);
  
    return ray;
  }
  
  The code to initialise the move lookup tables or attack sets for bishops and rooks is as follows:
  static void initBishopMoveLookupTable() {
      initBishopRelevantOccupancy();
      initBishopShifts();
  
      for (int index = 0; index < 512; index++) {
        for (int squareIndex = 0; squareIndex < 64; squareIndex++) {
          int fileIndex = (squareIndex % 8) + 1;
          int rankIndex = (squareIndex / 8) + 1;
          int diagonalIndex = 8 + (rankIndex - 1) - (fileIndex - 1);
          int antiDiagonalIndex = 1 + (rankIndex - 1) + (fileIndex - 1);
  
          long occupancy = getOccupancy(bishopRelevantOccupancy[squareIndex], index);
  
          long northEastRayAttack = getRayAttack(squareIndex, NORTH_EAST, (RANK[8] | FILE[H]), occupancy);
          long southEastRayAttack = getRayAttack(squareIndex, SOUTH_EAST, (RANK[1] | FILE[H]), occupancy);
          long southWestRayAttack = getRayAttack(squareIndex, SOUTH_WEST, (RANK[1] | FILE[A]), occupancy);
          long northWestRayAttack = getRayAttack(squareIndex, NORTH_WEST, (RANK[8] | FILE[A]), occupancy);
  
          bishopMoveLookupTable[squareIndex][index] =
              northEastRayAttack | southEastRayAttack | southWestRayAttack | northWestRayAttack;
        }
      }
    }
  
  static void initRookMoveLookupTable() {
    for (int squareIndex = 0; squareIndex < 64; squareIndex++) {
      for (int index = 0; index < 4096; index++) {
        int fileIndex = (squareIndex % 8) + 1;
        int rankIndex = (squareIndex / 8) + 1;
        long occupancy = getOccupancy(rookRelevantOccupancy[squareIndex], index);
  
        long northRayAttack = getRayAttack(squareIndex, NORTH, RANK[8], occupancy);
        long eastRayAttack = getRayAttack(squareIndex, EAST, FILE[H], occupancy);
        long southRayAttack = getRayAttack(squareIndex, SOUTH, RANK[1], occupancy);
        long westRayAttack = getRayAttack(squareIndex, WEST, FILE[A], occupancy);
  
        rookMoveLookupTable[squareIndex][index] =
            northRayAttack | eastRayAttack | southRayAttack | westRayAttack;
      }
    }
  }
  
  The code to get the population count or cardinality of a bitboard using byte lookup is as follows:
  static void initPopulationCount() {
    populationCount[0] = 0;
  
    for (int index = 1; index < 256; index++) {
      populationCount[index] = populationCount[index / 2] + (index & 1);
    }
  }
  
  static int getPopulationCount(long bitboard) {
    return  populationCount[(int) ((bitboard >>>  0) & RANK[1])]
          + populationCount[(int) ((bitboard >>>  8) & RANK[1])]
          + populationCount[(int) ((bitboard >>> 16) & RANK[1])]
          + populationCount[(int) ((bitboard >>> 24) & RANK[1])]
          + populationCount[(int) ((bitboard >>> 32) & RANK[1])]
          + populationCount[(int) ((bitboard >>> 40) & RANK[1])]
          + populationCount[(int) ((bitboard >>> 48) & RANK[1])]
          + populationCount[(int) ((bitboard >>> 56) & RANK[1])];
  }
  
  The code for the random number generator to generate magic candidates is as follows:
  static long generateRandomLong() {
    Random random = new Random();
  
    long random0 = random.nextLong() & 0xFFFF;
    long random1 = random.nextLong() & 0xFFFF;
    long random2 = random.nextLong() & 0xFFFF;
    long random3 = random.nextLong() & 0xFFFF;
  
    return (random0 << 0) | (random1 << 16) | (random2 << 32) | (random3 << 48);
  }
  
  static long getMagicCandidate() {
    return generateRandomLong() & generateRandomLong() & generateRandomLong();
  }
  
  The code to get the magic index is as follows:
  static int getMagicIndex(long maskedOccupancy, long magicNumber, int shift) {
    return (int) ((maskedOccupancy * magicNumber) >>> shift);
  }
  
  The code to get the magic numbers is as follows:
  static long getMagicNumber(long[] moveLookupTable, long relevantOccupancy, int shift) {
    boolean found         = false;
    int     numberOfBits  = getPopulationCount(relevantOccupancy);
  
    long[]  occupancies   = new long[1 << numberOfBits];
    long[]  tempMLT       = new long[1 << numberOfBits];
  
    for (int index = 0; index < (1 << numberOfBits); index++) {
      occupancies[index] = getOccupancy(relevantOccupancy, index);
    }
  
    while (!found) {
      long magicNumber = getMagicCandidate();
  
      if (getPopulationCount((relevantOccupancy * magicNumber) & 0xFF00000000000000L) < 6) {
        continue;
      }
  
      for (int i = 0; i < (1 >> numberOfBits); i++) {
        tempMLT[i] = 0;
      }
  
      boolean fail = false;
  
      for (int index = 0; !fail && index < (1 << numberOfBits); index++) {
        int  magicIndex = getMagicIndex(occupancies[index], magicNumber, shift);
  
          if (tempMLT[magicIndex] == 0) {
            tempMLT[magicIndex] = moveLookupTable[index];
          } else if (tempMLT[magicIndex] != moveLookupTable[index]) {
            fail = true;
          }
        }
        if (!fail) {
          return magicNumber;
        }
      }
      System.out.println("FAIL");
      return 0;
    }
  
  Everything except the magic number generator seems to be working. The generator gets stuck on some indexes and doesn't go any further than them. What I've noticed is that it seems to be getting stuck on indexes that are powers of two or in other words, indexes who only have one bit when converted to binary.
  The mapping I use is the standard Little Endian File Rank Mapping.
  
  **Tags:** programming, bishops, rooks, bitboard
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2024-09-01. Score: 1
  
  I hit a similar issue when generating my magic bitboards. It seemed that my level of shifting was too aggressive and setting it to 50 resolved the problem.
  
  I haven't followed your code all the way through so you may already be doing this, but the other thing to keep in mind is that collisions are okay IF they result in the same set of moves being generated.
  
  
  ---
  
  