WebSVN – Games.Chess Giants – Diff – /engine-stockfish/bitboard.cpp

   Copyright (C) 2008-2015 Marco Costalba, Joona Kiiski, Tord Romstad
-  Copyright (C) 2015-2016 Marco Costalba, Joona Kiiski, Gary Linscott, Tord Romstad
+  Copyright (C) 2015-2018 Marco Costalba, Joona Kiiski, Gary Linscott, Tord Romstad
   Stockfish is free software: you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation, either version 3 of the License, or
   (at your option) any later version.
 #include "bitboard.h"
 #include "misc.h"
 uint8_t PopCnt16[1 << 16];
 int SquareDistance[SQUARE_NB][SQUARE_NB];
-Bitboard  RookMasks  [SQUARE_NB];
-Bitboard  RookMagics [SQUARE_NB];
-Bitboard* RookAttacks[SQUARE_NB];
-unsigned  RookShifts [SQUARE_NB];
-Bitboard  BishopMasks  [SQUARE_NB];
-Bitboard  BishopMagics [SQUARE_NB];
-Bitboard* BishopAttacks[SQUARE_NB];
-unsigned  BishopShifts [SQUARE_NB];
 Bitboard SquareBB[SQUARE_NB];
 Bitboard FileBB[FILE_NB];
 Bitboard RankBB[RANK_NB];
 Bitboard AdjacentFilesBB[FILE_NB];
-Bitboard InFrontBB[COLOR_NB][RANK_NB];
+Bitboard ForwardRanksBB[COLOR_NB][RANK_NB];
-Bitboard StepAttacksBB[PIECE_NB][SQUARE_NB];
 Bitboard BetweenBB[SQUARE_NB][SQUARE_NB];
 Bitboard LineBB[SQUARE_NB][SQUARE_NB];
 Bitboard DistanceRingBB[SQUARE_NB][8];
-Bitboard ForwardBB[COLOR_NB][SQUARE_NB];
+Bitboard ForwardFileBB[COLOR_NB][SQUARE_NB];
 Bitboard PassedPawnMask[COLOR_NB][SQUARE_NB];
 Bitboard PawnAttackSpan[COLOR_NB][SQUARE_NB];
 Bitboard PseudoAttacks[PIECE_TYPE_NB][SQUARE_NB];
+Bitboard PawnAttacks[COLOR_NB][SQUARE_NB];
+Magic RookMagics[SQUARE_NB];
+Magic BishopMagics[SQUARE_NB];
 namespace {
   // De Bruijn sequences. See chessprogramming.wikispaces.com/BitScan
   const uint64_t DeBruijn64 = 0x3F79D71B4CB0A89ULL;
   int MSBTable[256];            // To implement software msb()
   Square BSFTable[SQUARE_NB];   // To implement software bitscan
   Bitboard RookTable[0x19000];  // To store rook attacks
   Bitboard BishopTable[0x1480]; // To store bishop attacks
-  typedef unsigned (Fn)(Square, Bitboard);
-  void init_magics(Bitboard table[], Bitboard* attacks[], Bitboard magics[],
+  void init_magics(Bitboard table[], Magic magics[], Direction directions[]);
-                   Bitboard masks[], unsigned shifts[], Square deltas[], Fn index);
   // bsf_index() returns the index into BSFTable[] to look up the bitscan. Uses
   // Matt Taylor's folding for 32 bit case, extended to 64 bit by Kim Walisch.
   unsigned bsf_index(Bitboard b) {
   for (File f = FILE_A; f <= FILE_H; ++f)
       AdjacentFilesBB[f] = (f > FILE_A ? FileBB[f - 1] : 0) | (f < FILE_H ? FileBB[f + 1] : 0);
   for (Rank r = RANK_1; r < RANK_8; ++r)
-      InFrontBB[WHITE][r] = ~(InFrontBB[BLACK][r + 1] = InFrontBB[BLACK][r] | RankBB[r]);
+      ForwardRanksBB[WHITE][r] = ~(ForwardRanksBB[BLACK][r + 1] = ForwardRanksBB[BLACK][r] | RankBB[r]);
   for (Color c = WHITE; c <= BLACK; ++c)
       for (Square s = SQ_A1; s <= SQ_H8; ++s)
+      {
-          ForwardBB[c][s]      = InFrontBB[c][rank_of(s)] & FileBB[file_of(s)];
+          ForwardFileBB [c][s] = ForwardRanksBB[c][rank_of(s)] & FileBB[file_of(s)];
-          PawnAttackSpan[c][s] = InFrontBB[c][rank_of(s)] & AdjacentFilesBB[file_of(s)];
+          PawnAttackSpan[c][s] = ForwardRanksBB[c][rank_of(s)] & AdjacentFilesBB[file_of(s)];
-          PassedPawnMask[c][s] = ForwardBB[c][s] | PawnAttackSpan[c][s];
+          PassedPawnMask[c][s] = ForwardFileBB [c][s] | PawnAttackSpan[c][s];
+      }
   for (Square s1 = SQ_A1; s1 <= SQ_H8; ++s1)
       for (Square s2 = SQ_A1; s2 <= SQ_H8; ++s2)
           if (s1 != s2)
+          {
               SquareDistance[s1][s2] = std::max(distance<File>(s1, s2), distance<Rank>(s1, s2));
               DistanceRingBB[s1][SquareDistance[s1][s2] - 1] |= s2;
+          }
-  int steps[][9] = { {}, { 7, 9 }, { 17, 15, 10, 6, -6, -10, -15, -17 },
+  int steps[][5] = { {}, { 7, 9 }, { 6, 10, 15, 17 }, {}, {}, {}, { 1, 7, 8, 9 } };
-                     {}, {}, {}, { 9, 7, -7, -9, 8, 1, -1, -8 } };
   for (Color c = WHITE; c <= BLACK; ++c)
-      for (PieceType pt = PAWN; pt <= KING; ++pt)
+      for (PieceType pt : { PAWN, KNIGHT, KING })
           for (Square s = SQ_A1; s <= SQ_H8; ++s)
               for (int i = 0; steps[pt][i]; ++i)
+              {
-                  Square to = s + Square(c == WHITE ? steps[pt][i] : -steps[pt][i]);
+                  Square to = s + Direction(c == WHITE ? steps[pt][i] : -steps[pt][i]);
                   if (is_ok(to) && distance(s, to) < 3)
+                  {
+                      if (pt == PAWN)
+                          PawnAttacks[c][s] |= to;
+                      else
-                      StepAttacksBB[make_piece(c, pt)][s] |= to;
+                          PseudoAttacks[pt][s] |= to;
+                  }
+              }
-  Square RookDeltas[] = { NORTH,  EAST,  SOUTH,  WEST  };
+  Direction RookDirections[] = { NORTH,  EAST,  SOUTH,  WEST };
-  Square BishopDeltas[] = { NORTH_EAST, SOUTH_EAST, SOUTH_WEST, NORTH_WEST };
+  Direction BishopDirections[] = { NORTH_EAST, SOUTH_EAST, SOUTH_WEST, NORTH_WEST };
-  init_magics(RookTable, RookAttacks, RookMagics, RookMasks, RookShifts, RookDeltas, magic_index<ROOK>);
+  init_magics(RookTable, RookMagics, RookDirections);
-  init_magics(BishopTable, BishopAttacks, BishopMagics, BishopMasks, BishopShifts, BishopDeltas, magic_index<BISHOP>);
+  init_magics(BishopTable, BishopMagics, BishopDirections);
   for (Square s1 = SQ_A1; s1 <= SQ_H8; ++s1)
+  {
       PseudoAttacks[QUEEN][s1]  = PseudoAttacks[BISHOP][s1] = attacks_bb<BISHOP>(s1, 0);
       PseudoAttacks[QUEEN][s1] |= PseudoAttacks[  ROOK][s1] = attacks_bb<  ROOK>(s1, 0);
-      for (Piece pc = W_BISHOP; pc <= W_ROOK; ++pc)
+      for (PieceType pt : { BISHOP, ROOK })
           for (Square s2 = SQ_A1; s2 <= SQ_H8; ++s2)
+          {
-              if (!(PseudoAttacks[pc][s1] & s2))
+              if (!(PseudoAttacks[pt][s1] & s2))
                   continue;
-              LineBB[s1][s2] = (attacks_bb(pc, s1, 0) & attacks_bb(pc, s2, 0)) | s1 | s2;
+              LineBB[s1][s2] = (attacks_bb(pt, s1, 0) & attacks_bb(pt, s2, 0)) | s1 | s2;
-              BetweenBB[s1][s2] = attacks_bb(pc, s1, SquareBB[s2]) & attacks_bb(pc, s2, SquareBB[s1]);
+              BetweenBB[s1][s2] = attacks_bb(pt, s1, SquareBB[s2]) & attacks_bb(pt, s2, SquareBB[s1]);
+          }
+  }
+}
 namespace {
-  Bitboard sliding_attack(Square deltas[], Square sq, Bitboard occupied) {
+  Bitboard sliding_attack(Direction directions[], Square sq, Bitboard occupied) {
     Bitboard attack = 0;
     for (int i = 0; i < 4; ++i)
-        for (Square s = sq + deltas[i];
+        for (Square s = sq + directions[i];
-             is_ok(s) && distance(s, s - deltas[i]) == 1;
+             is_ok(s) && distance(s, s - directions[i]) == 1;
-             s += deltas[i])
+             s += directions[i])
+        {
             attack |= s;
             if (occupied & s)
                 break;
   // init_magics() computes all rook and bishop attacks at startup. Magic
   // bitboards are used to look up attacks of sliding pieces. As a reference see
   // chessprogramming.wikispaces.com/Magic+Bitboards. In particular, here we
   // use the so called "fancy" approach.
-  void init_magics(Bitboard table[], Bitboard* attacks[], Bitboard magics[],
+  void init_magics(Bitboard table[], Magic magics[], Direction directions[]) {
-                   Bitboard masks[], unsigned shifts[], Square deltas[], Fn index) {
+    // Optimal PRNG seeds to pick the correct magics in the shortest time
     int seeds[][RANK_NB] = { { 8977, 44560, 54343, 38998,  5731, 95205, 104912, 17020 },
                              {  728, 10316, 55013, 32803, 12281, 15100,  16645,   255 } };
     Bitboard occupancy[4096], reference[4096], edges, b;
-    int age[4096] = {0}, current = 0, i, size;
+    int epoch[4096] = {}, cnt = 0, size = 0;
-    // attacks[s] is a pointer to the beginning of the attacks table for square 's'
-    attacks[SQ_A1] = table;
     for (Square s = SQ_A1; s <= SQ_H8; ++s)
+    {
         // Board edges are not considered in the relevant occupancies
         edges = ((Rank1BB | Rank8BB) & ~rank_bb(s)) | ((FileABB | FileHBB) & ~file_bb(s));
         // Given a square 's', the mask is the bitboard of sliding attacks from
         // 's' computed on an empty board. The index must be big enough to contain
         // all the attacks for each possible subset of the mask and so is 2 power
         // the number of 1s of the mask. Hence we deduce the size of the shift to
         // apply to the 64 or 32 bits word to get the index.
+        Magic& m = magics[s];
-        masks[s]  = sliding_attack(deltas, s, 0) & ~edges;
+        m.mask  = sliding_attack(directions, s, 0) & ~edges;
-        shifts[s] = (Is64Bit ? 64 : 32) - popcount(masks[s]);
+        m.shift = (Is64Bit ? 64 : 32) - popcount(m.mask);
+        // Set the offset for the attacks table of the square. We have individual
+        // table sizes for each square with "Fancy Magic Bitboards".
+        m.attacks = s == SQ_A1 ? table : magics[s - 1].attacks + size;
         // Use Carry-Rippler trick to enumerate all subsets of masks[s] and
         // store the corresponding sliding attack bitboard in reference[].
         b = size = 0;
         do {
             occupancy[size] = b;
-            reference[size] = sliding_attack(deltas, s, b);
+            reference[size] = sliding_attack(directions, s, b);
             if (HasPext)
-                attacks[s][pext(b, masks[s])] = reference[size];
+                m.attacks[pext(b, m.mask)] = reference[size];
             size++;
-            b = (b - masks[s]) & masks[s];
+            b = (b - m.mask) & m.mask;
         } while (b);
-        // Set the offset for the table of the next square. We have individual
-        // table sizes for each square with "Fancy Magic Bitboards".
-        if (s < SQ_H8)
-            attacks[s + 1] = attacks[s] + size;
         if (HasPext)
             continue;
         PRNG rng(seeds[Is64Bit][rank_of(s)]);
         // Find a magic for square 's' picking up an (almost) random number
         // until we find the one that passes the verification test.
-        do {
+        for (int i = 0; i < size; )
-            do
+        {
-                magics[s] = rng.sparse_rand<Bitboard>();
+            for (m.magic = 0; popcount((m.magic * m.mask) >> 56) < 6; )
-            while (popcount((magics[s] * masks[s]) >> 56) < 6);
+                m.magic = rng.sparse_rand<Bitboard>();
             // A good magic must map every possible occupancy to an index that
             // looks up the correct sliding attack in the attacks[s] database.
             // Note that we build up the database for square 's' as a side
-            // effect of verifying the magic.
+            // effect of verifying the magic. Keep track of the attempt count
+            // and save it in epoch[], little speed-up trick to avoid resetting
+            // m.attacks[] after every failed attempt.
-            for (++current, i = 0; i < size; ++i)
+            for (++cnt, i = 0; i < size; ++i)
+            {
-                unsigned idx = index(s, occupancy[i]);
+                unsigned idx = m.index(occupancy[i]);
-                if (age[idx] < current)
+                if (epoch[idx] < cnt)
+                {
-                    age[idx] = current;
+                    epoch[idx] = cnt;
-                    attacks[s][idx] = reference[i];
+                    m.attacks[idx] = reference[i];
+                }
-                else if (attacks[s][idx] != reference[i])
+                else if (m.attacks[idx] != reference[i])
                     break;
+            }
-        } while (i < size);
+        }
+    }
+  }
+}

Subversion Repositories Games.Chess Giants

Games.Chess Giants/engine-stockfish/bitboard.cpp – Rev 154 → 169