-
Notifications
You must be signed in to change notification settings - Fork 472
/
bitboard.cpp
341 lines (255 loc) · 10.6 KB
/
bitboard.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
/*
Stockfish, a UCI chess playing engine derived from Glaurung 2.1
Copyright (C) 2004-2008 Tord Romstad (Glaurung author)
Copyright (C) 2008-2013 Marco Costalba, Joona Kiiski, 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.
Stockfish is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
#include <algorithm>
#include <cstring>
#include <iostream>
#include "bitboard.h"
#include "bitcount.h"
#include "misc.h"
#include "rkiss.h"
CACHE_LINE_ALIGNMENT
Bitboard RMasks[SQUARE_NB];
Bitboard RMagics[SQUARE_NB];
Bitboard* RAttacks[SQUARE_NB];
unsigned RShifts[SQUARE_NB];
Bitboard BMasks[SQUARE_NB];
Bitboard BMagics[SQUARE_NB];
Bitboard* BAttacks[SQUARE_NB];
unsigned BShifts[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 StepAttacksBB[PIECE_NB][SQUARE_NB];
Bitboard BetweenBB[SQUARE_NB][SQUARE_NB];
Bitboard DistanceRingsBB[SQUARE_NB][8];
Bitboard ForwardBB[COLOR_NB][SQUARE_NB];
Bitboard PassedPawnMask[COLOR_NB][SQUARE_NB];
Bitboard PawnAttackSpan[COLOR_NB][SQUARE_NB];
Bitboard PseudoAttacks[PIECE_TYPE_NB][SQUARE_NB];
int SquareDistance[SQUARE_NB][SQUARE_NB];
namespace {
// De Bruijn sequences. See chessprogramming.wikispaces.com/BitScan
const uint64_t DeBruijn_64 = 0x3F79D71B4CB0A89ULL;
const uint32_t DeBruijn_32 = 0x783A9B23;
CACHE_LINE_ALIGNMENT
int MS1BTable[256];
Square BSFTable[SQUARE_NB];
Bitboard RTable[0x19000]; // Storage space for rook attacks
Bitboard BTable[0x1480]; // Storage space for bishop attacks
typedef unsigned (Fn)(Square, Bitboard);
void init_magics(Bitboard table[], Bitboard* attacks[], Bitboard magics[],
Bitboard masks[], unsigned shifts[], Square deltas[], Fn index);
FORCE_INLINE unsigned bsf_index(Bitboard b) {
// Matt Taylor's folding for 32 bit systems, extended to 64 bits by Kim Walisch
b ^= (b - 1);
return Is64Bit ? (b * DeBruijn_64) >> 58
: ((unsigned(b) ^ unsigned(b >> 32)) * DeBruijn_32) >> 26;
}
}
/// lsb()/msb() finds the least/most significant bit in a nonzero bitboard.
/// pop_lsb() finds and clears the least significant bit in a nonzero bitboard.
#if !defined(USE_BSFQ)
Square lsb(Bitboard b) { return BSFTable[bsf_index(b)]; }
Square pop_lsb(Bitboard* b) {
Bitboard bb = *b;
*b = bb & (bb - 1);
return BSFTable[bsf_index(bb)];
}
Square msb(Bitboard b) {
unsigned b32;
int result = 0;
if (b > 0xFFFFFFFF)
{
b >>= 32;
result = 32;
}
b32 = unsigned(b);
if (b32 > 0xFFFF)
{
b32 >>= 16;
result += 16;
}
if (b32 > 0xFF)
{
b32 >>= 8;
result += 8;
}
return (Square)(result + MS1BTable[b32]);
}
#endif // !defined(USE_BSFQ)
/// Bitboards::print() prints a bitboard in an easily readable format to the
/// standard output. This is sometimes useful for debugging.
void Bitboards::print(Bitboard b) {
sync_cout;
for (Rank rank = RANK_8; rank >= RANK_1; rank--)
{
std::cout << "+---+---+---+---+---+---+---+---+" << '\n';
for (File file = FILE_A; file <= FILE_H; file++)
std::cout << "| " << (b & (file | rank) ? "X " : " ");
std::cout << "|\n";
}
std::cout << "+---+---+---+---+---+---+---+---+" << sync_endl;
}
/// Bitboards::init() initializes various bitboard arrays. It is called during
/// program initialization.
void Bitboards::init() {
for (int k = 0, i = 0; i < 8; i++)
while (k < (2 << i))
MS1BTable[k++] = i;
for (int i = 0; i < 64; i++)
BSFTable[bsf_index(1ULL << i)] = Square(i);
for (Square s = SQ_A1; s <= SQ_H8; s++)
SquareBB[s] = 1ULL << s;
FileBB[FILE_A] = FileABB;
RankBB[RANK_1] = Rank1BB;
for (int i = 1; i < 8; i++)
{
FileBB[i] = FileBB[i - 1] << 1;
RankBB[i] = RankBB[i - 1] << 8;
}
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]);
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)];
PawnAttackSpan[c][s] = InFrontBB[c][rank_of(s)] & AdjacentFilesBB[file_of(s)];
PassedPawnMask[c][s] = ForwardBB[c][s] | PawnAttackSpan[c][s];
}
for (Square s1 = SQ_A1; s1 <= SQ_H8; s1++)
for (Square s2 = SQ_A1; s2 <= SQ_H8; s2++)
SquareDistance[s1][s2] = std::max(file_distance(s1, s2), rank_distance(s1, s2));
for (Square s1 = SQ_A1; s1 <= SQ_H8; s1++)
for (int d = 1; d < 8; d++)
for (Square s2 = SQ_A1; s2 <= SQ_H8; s2++)
if (SquareDistance[s1][s2] == d)
DistanceRingsBB[s1][d - 1] |= s2;
int steps[][9] = { {}, { 7, 9 }, { 17, 15, 10, 6, -6, -10, -15, -17 },
{}, {}, {}, { 9, 7, -7, -9, 8, 1, -1, -8 } };
for (Color c = WHITE; c <= BLACK; c++)
for (PieceType pt = PAWN; pt <= KING; pt++)
for (Square s = SQ_A1; s <= SQ_H8; s++)
for (int k = 0; steps[pt][k]; k++)
{
Square to = s + Square(c == WHITE ? steps[pt][k] : -steps[pt][k]);
if (is_ok(to) && square_distance(s, to) < 3)
StepAttacksBB[make_piece(c, pt)][s] |= to;
}
Square RDeltas[] = { DELTA_N, DELTA_E, DELTA_S, DELTA_W };
Square BDeltas[] = { DELTA_NE, DELTA_SE, DELTA_SW, DELTA_NW };
init_magics(RTable, RAttacks, RMagics, RMasks, RShifts, RDeltas, magic_index<ROOK>);
init_magics(BTable, BAttacks, BMagics, BMasks, BShifts, BDeltas, magic_index<BISHOP>);
for (Square s = SQ_A1; s <= SQ_H8; s++)
{
PseudoAttacks[QUEEN][s] = PseudoAttacks[BISHOP][s] = attacks_bb<BISHOP>(s, 0);
PseudoAttacks[QUEEN][s] |= PseudoAttacks[ ROOK][s] = attacks_bb< ROOK>(s, 0);
}
for (Square s1 = SQ_A1; s1 <= SQ_H8; s1++)
for (Square s2 = SQ_A1; s2 <= SQ_H8; s2++)
if (PseudoAttacks[QUEEN][s1] & s2)
{
Square delta = (s2 - s1) / square_distance(s1, s2);
for (Square s = s1 + delta; s != s2; s += delta)
BetweenBB[s1][s2] |= s;
}
}
namespace {
Bitboard sliding_attack(Square deltas[], Square sq, Bitboard occupied) {
Bitboard attack = 0;
for (int i = 0; i < 4; i++)
for (Square s = sq + deltas[i];
is_ok(s) && square_distance(s, s - deltas[i]) == 1;
s += deltas[i])
{
attack |= s;
if (occupied & s)
break;
}
return attack;
}
Bitboard pick_random(RKISS& rk, int booster) {
// Values s1 and s2 are used to rotate the candidate magic of a
// quantity known to be the optimal to quickly find the magics.
int s1 = booster & 63, s2 = (booster >> 6) & 63;
Bitboard m = rk.rand<Bitboard>();
m = (m >> s1) | (m << (64 - s1));
m &= rk.rand<Bitboard>();
m = (m >> s2) | (m << (64 - s2));
return m & rk.rand<Bitboard>();
}
// 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[],
Bitboard masks[], unsigned shifts[], Square deltas[], Fn index) {
int MagicBoosters[][8] = { { 3191, 2184, 1310, 3618, 2091, 1308, 2452, 3996 },
{ 1059, 3608, 605, 3234, 3326, 38, 2029, 3043 } };
RKISS rk;
Bitboard occupancy[4096], reference[4096], edges, b;
int i, size, booster;
// 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.
masks[s] = sliding_attack(deltas, s, 0) & ~edges;
shifts[s] = (Is64Bit ? 64 : 32) - popcount<Max15>(masks[s]);
// 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);
b = (b - masks[s]) & masks[s];
} 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;
booster = MagicBoosters[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 {
do magics[s] = pick_random(rk, booster);
while (popcount<Max15>((magics[s] * masks[s]) >> 56) < 6);
memset(attacks[s], 0, size * sizeof(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.
for (i = 0; i < size; i++)
{
Bitboard& attack = attacks[s][index(s, occupancy[i])];
if (attack && attack != reference[i])
break;
assert(reference[i] != 0);
attack = reference[i];
}
} while (i != size);
}
}
}