Subversion Repositories Games.Chess Giants

Rev

Rev 169 | Show entire file | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed

Rev 169 Rev 185
Line 4... Line 4...
4 
  Copyright (C) 2008-2015 Marco Costalba, Joona Kiiski, Tord Romstad
 4 
  Copyright (C) 2008-2015 Marco Costalba, Joona Kiiski, Tord Romstad
5 
  Copyright (C) 2015-2018 Marco Costalba, Joona Kiiski, Gary Linscott, Tord Romstad
 5 
  Copyright (C) 2015-2019 Marco Costalba, Joona Kiiski, Gary Linscott, Tord Romstad
6 
 
 6 
 
7 
  Stockfish is free software: you can redistribute it and/or modify
 7 
  Stockfish is free software: you can redistribute it and/or modify
8 
  it under the terms of the GNU General Public License as published by
 8 
  it under the terms of the GNU General Public License as published by
9 
  the Free Software Foundation, either version 3 of the License, or
 9 
  the Free Software Foundation, either version 3 of the License, or
10 
  (at your option) any later version.
 10 
  (at your option) any later version.
Line 43... Line 43...
43 
Magic RookMagics[SQUARE_NB];
 43 
Magic RookMagics[SQUARE_NB];
44 
Magic BishopMagics[SQUARE_NB];
 44 
Magic BishopMagics[SQUARE_NB];
45 
 
 45 
 
46 
namespace {
 46 
namespace {
47 
 
 47 
 
48 
  // De Bruijn sequences. See chessprogramming.wikispaces.com/BitScan
 - 
 
49 
  const uint64_t DeBruijn64 = 0x3F79D71B4CB0A89ULL;
 - 
 
50 
  const uint32_t DeBruijn32 = 0x783A9B23;
 - 
 
51 
 
 - 
 
52 
  int MSBTable[256];            // To implement software msb()
 - 
 
53 
  Square BSFTable[SQUARE_NB];   // To implement software bitscan
 - 
 
54 
  Bitboard RookTable[0x19000];  // To store rook attacks
 48 
  Bitboard RookTable[0x19000];  // To store rook attacks
55 
  Bitboard BishopTable[0x1480]; // To store bishop attacks
 49 
  Bitboard BishopTable[0x1480]; // To store bishop attacks
56 
 
 50 
 
57 
  void init_magics(Bitboard table[], Magic magics[], Direction directions[]);
 51 
  void init_magics(Bitboard table[], Magic magics[], Direction directions[]);
58 
 
 - 
 
59 
  // bsf_index() returns the index into BSFTable[] to look up the bitscan. Uses
 - 
 
60 
  // Matt Taylor's folding for 32 bit case, extended to 64 bit by Kim Walisch.
 - 
 
61 
 
 - 
 
62 
  unsigned bsf_index(Bitboard b) {
 - 
 
63 
    b ^= b - 1;
 - 
 
64 
    return Is64Bit ? (b * DeBruijn64) >> 58
 - 
 
65 
                   : ((unsigned(b) ^ unsigned(b >> 32)) * DeBruijn32) >> 26;
 - 
 
66 
  }
 - 
 
67 
 
 - 
 
68 
 
 52 
 
69 
  // popcount16() counts the non-zero bits using SWAR-Popcount algorithm
 53 
  // popcount16() counts the non-zero bits using SWAR-Popcount algorithm
70 
 
 54 
 
71 
  unsigned popcount16(unsigned u) {
 55 
  unsigned popcount16(unsigned u) {
72 
    u -= (u >> 1) & 0x5555U;
 56 
    u -= (u >> 1) & 0x5555U;
73 
    u = ((u >> 2) & 0x3333U) + (u & 0x3333U);
 57 
    u = ((u >> 2) & 0x3333U) + (u & 0x3333U);
74 
    u = ((u >> 4) + u) & 0x0F0FU;
 58 
    u = ((u >> 4) + u) & 0x0F0FU;
75 
    return (u * 0x0101U) >> 8;
 59 
    return (u * 0x0101U) >> 8;
76 
  }
 60 
  }
77 
}
 61 
}
78 
 
 - 
 
79 
#ifdef NO_BSF
 - 
 
80 
 
 - 
 
81 
/// Software fall-back of lsb() and msb() for CPU lacking hardware support
 - 
 
82 
 
 - 
 
83 
Square lsb(Bitboard b) {
 - 
 
84 
  assert(b);
 - 
 
85 
  return BSFTable[bsf_index(b)];
 - 
 
86 
}
 - 
 
87 
 
 - 
 
88 
Square msb(Bitboard b) {
 - 
 
89 
 
 - 
 
90 
  assert(b);
 - 
 
91 
  unsigned b32;
 - 
 
92 
  int result = 0;
 - 
 
93 
 
 - 
 
94 
  if (b > 0xFFFFFFFF)
 - 
 
95 
  {
 - 
 
96 
      b >>= 32;
 - 
 
97 
      result = 32;
 - 
 
98 
  }
 - 
 
99 
 
 - 
 
100 
  b32 = unsigned(b);
 - 
 
101 
 
 - 
 
102 
  if (b32 > 0xFFFF)
 - 
 
103 
  {
 - 
 
104 
      b32 >>= 16;
 - 
 
105 
      result += 16;
 - 
 
106 
  }
 - 
 
107 
 
 - 
 
108 
  if (b32 > 0xFF)
 - 
 
109 
  {
 - 
 
110 
      b32 >>= 8;
 - 
 
111 
      result += 8;
 - 
 
112 
  }
 - 
 
113 
 
 - 
 
114 
  return Square(result + MSBTable[b32]);
 - 
 
115 
}
 - 
 
116 
 
 - 
 
117 
#endif // ifdef NO_BSF
 - 
 
118 
 
 62 
 
119 
 
 63 
 
120 
/// Bitboards::pretty() returns an ASCII representation of a bitboard suitable
 64 
/// Bitboards::pretty() returns an ASCII representation of a bitboard suitable
121 
/// to be printed to standard output. Useful for debugging.
 65 
/// to be printed to standard output. Useful for debugging.
122 
 
 66 
 
Line 126... Line 70...
126 
 
 70 
 
127 
  for (Rank r = RANK_8; r >= RANK_1; --r)
 71 
  for (Rank r = RANK_8; r >= RANK_1; --r)
128 
  {
 72 
  {
129 
      for (File f = FILE_A; f <= FILE_H; ++f)
 73 
      for (File f = FILE_A; f <= FILE_H; ++f)
130 
          s += b & make_square(f, r) ? "| X " : "|   ";
 74 
          s += b & make_square(f, r) ? "| X " : "|   ";
131 
 
 75 
 
132 
      s += "|\n+---+---+---+---+---+---+---+---+\n";
 76 
      s += "|\n+---+---+---+---+---+---+---+---+\n";
133 
  }
 77 
  }
134 
 
 78 
 
135 
  return s;
 79 
  return s;
136 
}
 80 
}
Line 143... Line 87...
143 
 
 87 
 
144 
  for (unsigned i = 0; i < (1 << 16); ++i)
 88 
  for (unsigned i = 0; i < (1 << 16); ++i)
145 
      PopCnt16[i] = (uint8_t) popcount16(i);
 89 
      PopCnt16[i] = (uint8_t) popcount16(i);
146 
 
 90 
 
147 
  for (Square s = SQ_A1; s <= SQ_H8; ++s)
 91 
  for (Square s = SQ_A1; s <= SQ_H8; ++s)
148 
  {
 - 
 
149 
      SquareBB[s] = 1ULL << s;
 92 
      SquareBB[s] = (1ULL << s);
150 
      BSFTable[bsf_index(SquareBB[s])] = s;
 - 
 
151 
  }
 - 
 
152 
 
 - 
 
153 
  for (Bitboard b = 2; b < 256; ++b)
 - 
 
154 
      MSBTable[b] = MSBTable[b - 1] + !more_than_one(b);
 - 
 
155 
 
 93 
 
156 
  for (File f = FILE_A; f <= FILE_H; ++f)
 94 
  for (File f = FILE_A; f <= FILE_H; ++f)
157 
      FileBB[f] = f > FILE_A ? FileBB[f - 1] << 1 : FileABB;
 95 
      FileBB[f] = f > FILE_A ? FileBB[f - 1] << 1 : FileABB;
158 
 
 96 
 
159 
  for (Rank r = RANK_1; r <= RANK_8; ++r)
 97 
  for (Rank r = RANK_1; r <= RANK_8; ++r)
Line 176... Line 114...
176 
  for (Square s1 = SQ_A1; s1 <= SQ_H8; ++s1)
 114 
  for (Square s1 = SQ_A1; s1 <= SQ_H8; ++s1)
177 
      for (Square s2 = SQ_A1; s2 <= SQ_H8; ++s2)
 115 
      for (Square s2 = SQ_A1; s2 <= SQ_H8; ++s2)
178 
          if (s1 != s2)
 116 
          if (s1 != s2)
179 
          {
 117 
          {
180 
              SquareDistance[s1][s2] = std::max(distance<File>(s1, s2), distance<Rank>(s1, s2));
 118 
              SquareDistance[s1][s2] = std::max(distance<File>(s1, s2), distance<Rank>(s1, s2));
181 
              DistanceRingBB[s1][SquareDistance[s1][s2] - 1] |= s2;
 119 
              DistanceRingBB[s1][SquareDistance[s1][s2]] |= s2;
182 
          }
 120 
          }
183 
 
 121 
 
184 
  int steps[][5] = { {}, { 7, 9 }, { 6, 10, 15, 17 }, {}, {}, {}, { 1, 7, 8, 9 } };
 122 
  int steps[][5] = { {}, { 7, 9 }, { 6, 10, 15, 17 }, {}, {}, {}, { 1, 7, 8, 9 } };
185 
 
 123 
 
186 
  for (Color c = WHITE; c <= BLACK; ++c)
 124 
  for (Color c = WHITE; c <= BLACK; ++c)
Line 197... Line 135...
197 
                      else
 135 
                      else
198 
                          PseudoAttacks[pt][s] |= to;
 136 
                          PseudoAttacks[pt][s] |= to;
199 
                  }
 137 
                  }
200 
              }
 138 
              }
201 
 
 139 
 
202 
  Direction RookDirections[] = { NORTH,  EAST,  SOUTH,  WEST };
 140 
  Direction RookDirections[] = { NORTH, EAST, SOUTH, WEST };
203 
  Direction BishopDirections[] = { NORTH_EAST, SOUTH_EAST, SOUTH_WEST, NORTH_WEST };
 141 
  Direction BishopDirections[] = { NORTH_EAST, SOUTH_EAST, SOUTH_WEST, NORTH_WEST };
204 
 
 142 
 
205 
  init_magics(RookTable, RookMagics, RookDirections);
 143 
  init_magics(RookTable, RookMagics, RookDirections);
206 
  init_magics(BishopTable, BishopMagics, BishopDirections);
 144 
  init_magics(BishopTable, BishopMagics, BishopDirections);
207 
 
 145