Line data Source code
1 : #include "attack.hpp"
2 :
3 : #include "bitboard.hpp"
4 : #include "logging.hpp"
5 : #include "positionTools.hpp"
6 : #include "timers.hpp"
7 :
8 : #ifndef WITH_MAGIC
9 : namespace {
10 : array1d<int,512> _ranks = {0};
11 : }
12 : #endif
13 :
14 : namespace BBTools {
15 :
16 : array1d<Mask,NbSquare> mask;
17 :
18 : // This initialisation function is taken from Dumb chess engine by Richard Delorme
19 22 : void initMask() {
20 22 : Logging::LogIt(Logging::logInfo) << "Init mask";
21 22 : Logging::LogIt(Logging::logInfo) << "Size of masks : " << sizeof(mask) / 1024 << "Kb";
22 22 : array2d<Square,NbSquare,NbSquare> d = {{0}};
23 1430 : for (Square x = 0; x < NbSquare; ++x) {
24 1408 : mask[x].bbsquare = SquareToBitboard(x);
25 5632 : for (Square i = -1; i <= 1; ++i) {
26 16896 : for (Square j = -1; j <= 1; ++j) {
27 12672 : if (i == 0 && j == 0) continue;
28 : #if !defined(WITH_SMALL_MEMORY)
29 43296 : for (Square r = SQRANK(x) + i, f = SQFILE(x) + j; 0 <= r && r < 8 && 0 <= f && f < 8; r += i, f += j) {
30 32032 : const int y = 8 * r + f;
31 32032 : d[x][y] = 8 * i + j;
32 88704 : for (Square z = x + d[x][y]; z != y; z += d[x][y]) mask[x].between[y] |= SquareToBitboard(z);
33 : }
34 : #endif
35 : const auto r = SQRANK(x);
36 : const auto f = SQFILE(x);
37 11264 : if (0 <= r + i && r + i < 8 && 0 <= f + j && f + j < 8) mask[x].kingZone |= SquareToBitboard((SQRANK(x) + i) * 8 + SQFILE(x) + j);
38 : }
39 : }
40 :
41 4488 : for (Square y = x - 9; y >= 0 && d[x][y] == -9; y -= 9) mask[x].diagonal |= SquareToBitboard(y);
42 4488 : for (Square y = x + 9; y < NbSquare && d[x][y] == 9; y += 9) mask[x].diagonal |= SquareToBitboard(y);
43 :
44 4488 : for (Square y = x - 7; y >= 0 && d[x][y] == -7; y -= 7) mask[x].antidiagonal |= SquareToBitboard(y);
45 4488 : for (Square y = x + 7; y < NbSquare && d[x][y] == 7; y += 7) mask[x].antidiagonal |= SquareToBitboard(y);
46 :
47 6336 : for (Square y = x - 8; y >= 0; y -= 8) mask[x].file |= SquareToBitboard(y);
48 6336 : for (Square y = x + 8; y < NbSquare; y += 8) mask[x].file |= SquareToBitboard(y);
49 :
50 : auto f = SQFILE(x);
51 : auto r = SQRANK(x);
52 4224 : for (Square i = -1, c = 1, dp = 6; i <= 1; i += 2, c = 0, dp = 1) {
53 8448 : for (Square j = -1; j <= 1; j += 2)
54 5632 : if (0 <= r + i && r + i < 8 && 0 <= f + j && f + j < 8) { mask[x].pawnAttack[c] |= SquareToBitboard((r + i) * 8 + (f + j)); }
55 2816 : if (0 <= r + i && r + i < 8) {
56 2464 : mask[x].push[c] = SquareToBitboard((r + i) * 8 + f);
57 2464 : if (r == dp) mask[x].dpush[c] = SquareToBitboard((r + 2 * i) * 8 + f); // double push
58 : }
59 : }
60 : #if !defined(WITH_SMALL_MEMORY)
61 1408 : if (r == 3 || r == 4) {
62 352 : if (f > 0) mask[x].enpassant |= SquareToBitboard(x - 1);
63 352 : if (f < 7) mask[x].enpassant |= SquareToBitboard(x + 1);
64 : }
65 : #endif
66 :
67 12672 : for (Square i = -2; i <= 2; i = (i == -1 ? 1 : i + 1)) {
68 33792 : for (Square j = -2; j <= 2; ++j) {
69 28160 : if (i == j || i == -j || j == 0) continue;
70 11264 : if (0 <= r + i && r + i < 8 && 0 <= f + j && f + j < 8) { mask[x].knight |= SquareToBitboard(8 * (r + i) + (f + j)); }
71 : }
72 : }
73 :
74 5632 : for (Square i = -1; i <= 1; ++i) {
75 16896 : for (Square j = -1; j <= 1; ++j) {
76 12672 : if (i == 0 && j == 0) continue;
77 11264 : if (0 <= r + i && r + i < 8 && 0 <= f + j && f + j < 8) { mask[x].king |= SquareToBitboard(8 * (r + i) + (f + j)); }
78 : }
79 : }
80 :
81 : BitBoard wspan = SquareToBitboardTable(x);
82 1408 : wspan |= wspan << 8;
83 1408 : wspan |= wspan << 16;
84 1408 : wspan |= wspan << 32;
85 : wspan = _shiftNorth(wspan);
86 : BitBoard bspan = SquareToBitboardTable(x);
87 1408 : bspan |= bspan >> 8;
88 1408 : bspan |= bspan >> 16;
89 1408 : bspan |= bspan >> 32;
90 : bspan = _shiftSouth(bspan);
91 :
92 : #if !defined(WITH_SMALL_MEMORY)
93 : ///@todo try to use them in bitboardTools to see if its faster than on the fly computations ...
94 1408 : mask[x].frontSpan[Co_White] = wspan;
95 1408 : mask[x].frontSpan[Co_Black] = bspan;
96 :
97 1408 : mask[x].rearSpan[Co_Black] = wspan;
98 1408 : mask[x].rearSpan[Co_White] = bspan;
99 :
100 : mask[x].passerSpan[Co_White] = wspan;
101 1408 : mask[x].passerSpan[Co_White] |= _shiftWest(wspan);
102 1408 : mask[x].passerSpan[Co_White] |= _shiftEast(wspan);
103 : mask[x].passerSpan[Co_Black] = bspan;
104 1408 : mask[x].passerSpan[Co_Black] |= _shiftWest(bspan);
105 1408 : mask[x].passerSpan[Co_Black] |= _shiftEast(bspan);
106 :
107 : mask[x].attackFrontSpan[Co_White] = _shiftWest(wspan);
108 1408 : mask[x].attackFrontSpan[Co_White] |= _shiftEast(wspan);
109 : mask[x].attackFrontSpan[Co_Black] = _shiftWest(bspan);
110 1408 : mask[x].attackFrontSpan[Co_Black] |= _shiftEast(bspan);
111 : #endif
112 : }
113 :
114 : #ifndef WITH_MAGIC
115 : for (Square o = 0; o < 64; ++o) {
116 : for (Square k = 0; k < 8; ++k) {
117 : int y = 0;
118 : for (Square x = k - 1; x >= 0; --x) {
119 : const BitBoard b = SquareToBitboard(x);
120 : y |= b;
121 : if (((o << 1) & b) == b) break;
122 : }
123 : for (Square x = k + 1; x < 8; ++x) {
124 : const BitBoard b = SquareToBitboard(x);
125 : y |= b;
126 : if (((o << 1) & b) == b) break;
127 : }
128 : _ranks[o * 8 + k] = y;
129 : }
130 : }
131 : #endif
132 22 : }
133 :
134 : #ifndef WITH_MAGIC // then use HQBB
135 :
136 : BitBoard attack(const BitBoard occupancy, const Square s, const BitBoard m) {
137 : assert(isValidSquare(s));
138 : START_TIMER
139 : BitBoard forward = occupancy & m;
140 : BitBoard reverse = swapbits(forward);
141 : forward -= SquareToBitboard(s);
142 : reverse -= SquareToBitboard(s ^ 63);
143 : forward ^= swapbits(reverse);
144 : forward &= m;
145 : STOP_AND_SUM_TIMER(Attack)
146 : return forward;
147 : }
148 :
149 : BitBoard rankAttack(const BitBoard occupancy, const Square s) {
150 : assert(isValidSquare(s));
151 : const int f = SQFILE(s);
152 : const int r = s & 56;
153 : return static_cast<BitBoard>(_ranks[((occupancy >> r) & 126) * 4 + f]) << r;
154 : }
155 :
156 : BitBoard fileAttack(const BitBoard occupancy, const Square s) {
157 : assert(isValidSquare(s));
158 : return attack(occupancy, s, mask[s].file);
159 : }
160 :
161 : BitBoard diagonalAttack(const BitBoard occupancy, const Square s) {
162 : assert(isValidSquare(s));
163 : return attack(occupancy, s, mask[s].diagonal);
164 : }
165 :
166 : BitBoard antidiagonalAttack(const BitBoard occupancy, const Square s) {
167 : assert(isValidSquare(s));
168 : return attack(occupancy, s, mask[s].antidiagonal);
169 : }
170 :
171 : #else // MAGIC
172 :
173 : namespace MagicBB {
174 :
175 : array1d<SMagic,NbSquare> bishopMagic;
176 : array1d<SMagic,NbSquare> rookMagic;
177 :
178 : array2d<BitBoard,NbSquare,1 << BISHOP_INDEX_BITS> bishopAttacks;
179 : array2d<BitBoard,NbSquare,1 << ROOK_INDEX_BITS> rookAttacks;
180 :
181 : constexpr array1d<BitBoard,NbSquare> bishopMagics = {
182 : 0x1002004102008200, 0x1002004102008200, 0x4310002248214800, 0x402010c110014208, 0xa000a06240114001, 0xa000a06240114001, 0x402010c110014208, 0xa000a06240114001,
183 : 0x1002004102008200, 0x1002004102008200, 0x1002004102008200, 0x1002004102008200, 0x100c009840001000, 0x4310002248214800, 0xa000a06240114001, 0x4310002248214800,
184 : 0x4310002248214800, 0x822143005020a148, 0x0001901c00420040, 0x0880504024308060, 0x0100201004200002, 0xa000a06240114001, 0x822143005020a148, 0x1002004102008200,
185 : 0x1002004102008200, 0x1002004102008200, 0x1002004102008200, 0x2008080100820102, 0x1481010004104010, 0x0002052000100024, 0xc880221002060081, 0xc880221002060081,
186 : 0x4310002248214800, 0xc880221002060081, 0x0001901c00420040, 0x8400208020080201, 0x000e008400060020, 0x00449210e3902028, 0x402010c110014208, 0xc880221002060081,
187 : 0x100c009840001000, 0xc880221002060081, 0x1000820800c00060, 0x2803101084008800, 0x2200608200100080, 0x0040900130840090, 0x0024010008800a00, 0x0400110410804810,
188 : 0x402010c110014208, 0xa000a06240114001, 0xa000a06240114001, 0x1002004102008200, 0x1002004102008200, 0x1002004102008200, 0x1002004102008200, 0x1002004102008200,
189 : 0xa000a06240114001, 0x4310002248214800, 0x1002004102008200, 0x1002004102008200, 0x1002004102008200, 0x1002004102008200, 0x1002004102008200, 0x1002004102008200
190 : };
191 :
192 : constexpr array1d<BitBoard,NbSquare> rookMagics = {
193 : 0x8200108041020020, 0x8200108041020020, 0xc880221002060081, 0x0009100804021000, 0x0500010004107800, 0x0024010008800a00, 0x0400110410804810, 0x8300038100004222,
194 : 0x004a800182c00020, 0x0009100804021000, 0x3002200010c40021, 0x0020100104000208, 0x01021001a0080020, 0x0884020010082100, 0x1000820800c00060, 0x8020480110020020,
195 : 0x0002052000100024, 0x0200190040088100, 0x0030802001a00800, 0x8010002004000202, 0x0040010100080010, 0x2200608200100080, 0x0001901c00420040, 0x0001400a24008010,
196 : 0x1400a22008001042, 0x8200108041020020, 0x2004500023002400, 0x8105100028001048, 0x8010024d00014802, 0x8000820028030004, 0x402010c110014208, 0x8300038100004222,
197 : 0x0001804002800124, 0x0084022014041400, 0x0030802001a00800, 0x0110a01001080008, 0x0b10080850081100, 0x000010040049020c, 0x0024010008800a00, 0x014c800040100426,
198 : 0x1100400010208000, 0x0009100804021000, 0x0010024871202002, 0x8014001028c80801, 0x1201082010a00200, 0x0002008004102009, 0x8300038100004222, 0x0000401001a00408,
199 : 0x4520920010210200, 0x0400110410804810, 0x8105100028001048, 0x8105100028001048, 0x0802801009083002, 0x8200108041020020, 0x8200108041020020, 0x4000a12400848110,
200 : 0x2000804026001102, 0x2000804026001102, 0x800040a010040901, 0x80001802002c0422, 0x0010b018200c0122, 0x200204802a080401, 0x8880604201100844, 0x80000cc281092402
201 : };
202 :
203 25952256 : BitBoard computeAttacks(const Square index, const BitBoard occ, const Square delta) {
204 : BitBoard attacks = emptyBitBoard;
205 : BitBoard blocked = emptyBitBoard;
206 113000448 : for (Square shift = index + delta; ISNEIGHBOUR(shift, shift - delta); shift += delta) {
207 125118400 : if (!blocked) attacks |= SquareToBitboard(shift);
208 87048192 : blocked |= ((1ULL << shift) & occ);
209 : }
210 25952256 : return attacks;
211 : }
212 :
213 6488064 : BitBoard occupiedFromIndex(const int j, BitBoard mask) {
214 6488064 : BitBoard occ = emptyBitBoard;
215 6488064 : Square i = 0;
216 71143424 : BB::applyOn(mask, [&](const Square & k){
217 64655360 : if (j & SquareToBitboard(i)) occ |= (1ULL << k);
218 64655360 : ++i;
219 64655360 : });
220 6488064 : return occ;
221 : }
222 :
223 22 : void initMagic() {
224 22 : Logging::LogIt(Logging::logInfo) << "Init magic";
225 1430 : for (Square from = 0; from < 64; from++) {
226 1408 : bishopMagic[from].mask = emptyBitBoard;
227 1408 : rookMagic[from].mask = emptyBitBoard;
228 91520 : for (Square j = 0; j < 64; j++) {
229 90112 : if (from == j) continue;
230 96096 : if (SQRANK(from) == SQRANK(j) && !ISOUTERFILE(j)) rookMagic[from].mask |= SquareToBitboard(j);
231 96096 : if (SQFILE(from) == SQFILE(j) && !PROMOTION_RANK(j)) rookMagic[from].mask |= SquareToBitboard(j);
232 88704 : if (abs(SQRANK(from) - SQRANK(j)) == abs(SQFILE(from) - SQFILE(j)) && !ISOUTERFILE(j) && !PROMOTION_RANK(j))
233 8008 : bishopMagic[from].mask |= SquareToBitboard(j);
234 : }
235 1408 : bishopMagic[from].magic = bishopMagics[from];
236 722304 : for (int j = 0; j < (1 << BISHOP_INDEX_BITS); j++) {
237 720896 : const BitBoard occ = occupiedFromIndex(j, bishopMagic[from].mask);
238 720896 : bishopAttacks[from][MAGICBISHOPINDEX(occ, from)] =
239 720896 : (computeAttacks(from, occ, -7) | computeAttacks(from, occ, 7) | computeAttacks(from, occ, -9) | computeAttacks(from, occ, 9));
240 : }
241 1408 : rookMagic[from].magic = rookMagics[from];
242 5768576 : for (int j = 0; j < (1 << ROOK_INDEX_BITS); j++) {
243 5767168 : const BitBoard occ = occupiedFromIndex(j, rookMagic[from].mask);
244 5767168 : rookAttacks[from][MAGICROOKINDEX(occ, from)] =
245 5767168 : (computeAttacks(from, occ, -1) | computeAttacks(from, occ, 1) | computeAttacks(from, occ, -8) | computeAttacks(from, occ, 8));
246 : }
247 : }
248 22 : }
249 :
250 : } // namespace MagicBB
251 :
252 : #endif // MAGIC
253 :
254 199268068 : bool isAttackedBB(const Position &p, const Square s, const Color c) { ///@todo try to optimize order better ?
255 199268068 : assert(isValidSquare(s));
256 : const BitBoard occupancy = p.occupancy();
257 199268068 : if (c == Co_White)
258 83525669 : return attack<P_wb>(s, p.blackBishop() | p.blackQueen(), occupancy) ||
259 82084711 : attack<P_wr>(s, p.blackRook() | p.blackQueen(), occupancy) ||
260 26719627 : attack<P_wp>(s, p.blackPawn(), occupancy, Co_White) ||
261 76559252 : attack<P_wn>(s, p.blackKnight()) ||
262 : attack<P_wk>(s, p.blackKing());
263 : else
264 312672562 : return attack<P_wb>(s, p.whiteBishop() | p.whiteQueen(), occupancy) ||
265 311159365 : attack<P_wr>(s, p.whiteRook() | p.whiteQueen(), occupancy) ||
266 129728246 : attack<P_wp>(s, p.whitePawn(), occupancy, Co_Black) ||
267 291340606 : attack<P_wn>(s, p.whiteKnight()) ||
268 : attack<P_wk>(s, p.whiteKing());
269 : }
270 :
271 1 : BitBoard allAttackedBB(const Position &p, const Square s, const Color c) {
272 1 : assert(isValidSquare(s));
273 : const BitBoard occupancy = p.occupancy();
274 1 : if (c == Co_White)
275 2 : return attack<P_wb>(s, p.blackBishop() | p.blackQueen(), occupancy) |
276 2 : attack<P_wr>(s, p.blackRook() | p.blackQueen(), occupancy) |
277 1 : attack<P_wn>(s, p.blackKnight()) |
278 : attack<P_wp>(s, p.blackPawn(), occupancy, Co_White) |
279 1 : attack<P_wk>(s, p.blackKing());
280 : else
281 0 : return attack<P_wb>(s, p.whiteBishop() | p.whiteQueen(), occupancy) |
282 0 : attack<P_wr>(s, p.whiteRook() | p.whiteQueen(), occupancy) |
283 0 : attack<P_wn>(s, p.whiteKnight()) |
284 : attack<P_wp>(s, p.whitePawn(), occupancy, Co_Black) |
285 0 : attack<P_wk>(s, p.whiteKing());
286 : }
287 :
288 5790404 : BitBoard allAttackedBB(const Position &p, const Square s) {
289 5790404 : assert(isValidSquare(s));
290 : const BitBoard occupancy = p.occupancy();
291 11580808 : return attack<P_wb>(s, p.allBishop() | p.allQueen(), occupancy) |
292 11580808 : attack<P_wr>(s, p.allRook() | p.allQueen(), occupancy) |
293 5790404 : attack<P_wn>(s, p.allKnight()) |
294 5790404 : attack<P_wp>(s, p.blackPawn(), occupancy, Co_White) |
295 : attack<P_wp>(s, p.whitePawn(), occupancy, Co_Black) |
296 5790404 : attack<P_wk>(s, p.allKing());
297 : }
298 :
299 26925812 : BitBoard between(const Square sq1, const Square sq2){
300 : #if !defined(WITH_SMALL_MEMORY)
301 26925812 : return mask[sq1].between[sq2];
302 : #else
303 : constexpr BitBoard m1 {static_cast<BitBoard>(-1)};
304 : constexpr BitBoard a2a7 {0x0001010101010100};
305 : constexpr BitBoard b2g7 {0x0040201008040200};
306 : constexpr BitBoard h1b7 {0x0002040810204080};
307 : const BitBoard btwn = (m1 << sq1) ^ (m1 << sq2);
308 : const BitBoard file = (sq2 & 7) - (sq1 & 7);
309 : const BitBoard rank = ((sq2 | 7) - sq1) >> 3 ;
310 : BitBoard line = ((file & 7) - 1) & a2a7; /* a2a7 if same file */
311 : line += 2 * (((rank & 7) - 1) >> 58); /* b1g1 if same rank */
312 : line += (((rank - file) & 15) - 1) & b2g7; /* b2g7 if same diagonal */
313 : line += (((rank + file) & 15) - 1) & h1b7; /* h1b7 if same antidiag */
314 : line *= btwn & -btwn; /* mul acts like shift by smaller square */
315 : return line & btwn; /* return the bits on that line in-between */
316 : #endif
317 : }
318 :
319 : } // namespace BBTools
320 :
321 0 : bool isAttacked(const Position &p, const Square s){
322 : //assert(isValidSquare(s)); ///@todo ?
323 : START_TIMER
324 199268068 : const bool b = isValidSquare(s) && BBTools::isAttackedBB(p, s, p.c);
325 : STOP_AND_SUM_TIMER(IsAttacked);
326 0 : return b;
327 : }
328 :
329 198803298 : bool isPosInCheck(const Position& p){
330 : // handles chess variants
331 : ///@todo some chess variant will always return false here, there is no such things as check
332 198803298 : return isAttacked(p, kingSquare(p));
333 : }
334 :
335 162332 : bool isAttacked(const Position &p, BitBoard bb) { // copy ///@todo should be done without iterating over Square !
336 605060 : while (bb)
337 464770 : if (isAttacked(p, BB::popBit(bb))) return true;
338 : return false;
339 : }
|
