attack.c (12189B)
1 #include "string.h" 2 3 #include "attack.h" 4 #include "utils.h" 5 6 #define UNUSED(x) (void)(x) 7 8 // Magic constants 9 10 // clang-format off 11 const int bishop_relevant_bits[64] = { 12 6, 5, 5, 5, 5, 5, 5, 6, 13 5, 5, 5, 5, 5, 5, 5, 5, 14 5, 5, 7, 7, 7, 7, 5, 5, 15 5, 5, 7, 9, 9, 7, 5, 5, 16 5, 5, 7, 9, 9, 7, 5, 5, 17 5, 5, 7, 7, 7, 7, 5, 5, 18 5, 5, 5, 5, 5, 5, 5, 5, 19 6, 5, 5, 5, 5, 5, 5, 6, 20 }; 21 22 const U64 bishop_magic_numbers[64] = { 23 C64(0x40040844404084), C64(0x2004208a004208), C64(0x10190041080202), 24 C64(0x108060845042010), C64(0x581104180800210), C64(0x2112080446200010), 25 C64(0x1080820820060210), C64(0x3c0808410220200), C64(0x4050404440404), 26 C64(0x21001420088), C64(0x24d0080801082102), C64(0x1020a0a020400), 27 C64(0x40308200402), C64(0x4011002100800), C64(0x401484104104005), 28 C64(0x801010402020200), C64(0x400210c3880100), C64(0x404022024108200), 29 C64(0x810018200204102), C64(0x4002801a02003), C64(0x85040820080400), 30 C64(0x810102c808880400), C64(0xe900410884800), C64(0x8002020480840102), 31 C64(0x220200865090201), C64(0x2010100a02021202), C64(0x152048408022401), 32 C64(0x20080002081110), C64(0x4001001021004000), C64(0x800040400a011002), 33 C64(0xe4004081011002), C64(0x1c004001012080), C64(0x8004200962a00220), 34 C64(0x8422100208500202), C64(0x2000402200300c08), C64(0x8646020080080080), 35 C64(0x80020a0200100808), C64(0x2010004880111000), C64(0x623000a080011400), 36 C64(0x42008c0340209202), C64(0x209188240001000), C64(0x400408a884001800), 37 C64(0x110400a6080400), C64(0x1840060a44020800), C64(0x90080104000041), 38 C64(0x201011000808101), C64(0x1a2208080504f080), C64(0x8012020600211212), 39 C64(0x500861011240000), C64(0x180806108200800), C64(0x4000020e01040044), 40 C64(0x300000261044000a), C64(0x802241102020002), C64(0x20906061210001), 41 C64(0x5a84841004010310), C64(0x4010801011c04), C64(0xa010109502200), 42 C64(0x4a02012000), C64(0x500201010098b028), C64(0x8040002811040900), 43 C64(0x28000010020204), C64(0x6000020202d0240), C64(0x8918844842082200), 44 C64(0x4010011029020020), 45 }; 46 47 const int rook_relevant_bits[64] = { 48 12, 11, 11, 11, 11, 11, 11, 12, 49 11, 10, 10, 10, 10, 10, 10, 11, 50 11, 10, 10, 10, 10, 10, 10, 11, 51 11, 10, 10, 10, 10, 10, 10, 11, 52 11, 10, 10, 10, 10, 10, 10, 11, 53 11, 10, 10, 10, 10, 10, 10, 11, 54 11, 10, 10, 10, 10, 10, 10, 11, 55 12, 11, 11, 11, 11, 11, 11, 12, 56 }; 57 58 const U64 rook_magic_numbers[64] = { 59 C64(0x8a80104000800020), C64(0x140002000100040), C64(0x2801880a0017001), 60 C64(0x100081001000420), C64(0x200020010080420), C64(0x3001c0002010008), 61 C64(0x8480008002000100), C64(0x2080088004402900), C64(0x800098204000), 62 C64(0x2024401000200040), C64(0x100802000801000), C64(0x120800800801000), 63 C64(0x208808088000400), C64(0x2802200800400), C64(0x2200800100020080), 64 C64(0x801000060821100), C64(0x80044006422000), C64(0x100808020004000), 65 C64(0x12108a0010204200), C64(0x140848010000802), C64(0x481828014002800), 66 C64(0x8094004002004100), C64(0x4010040010010802), C64(0x20008806104), 67 C64(0x100400080208000), C64(0x2040002120081000), C64(0x21200680100081), 68 C64(0x20100080080080), C64(0x2000a00200410), C64(0x20080800400), 69 C64(0x80088400100102), C64(0x80004600042881), C64(0x4040008040800020), 70 C64(0x440003000200801), C64(0x4200011004500), C64(0x188020010100100), 71 C64(0x14800401802800), C64(0x2080040080800200), C64(0x124080204001001), 72 C64(0x200046502000484), C64(0x480400080088020), C64(0x1000422010034000), 73 C64(0x30200100110040), C64(0x100021010009), C64(0x2002080100110004), 74 C64(0x202008004008002), C64(0x20020004010100), C64(0x2048440040820001), 75 C64(0x101002200408200), C64(0x40802000401080), C64(0x4008142004410100), 76 C64(0x2060820c0120200), C64(0x1001004080100), C64(0x20c020080040080), 77 C64(0x2935610830022400), C64(0x44440041009200), C64(0x280001040802101), 78 C64(0x2100190040002085), C64(0x80c0084100102001), C64(0x4024081001000421), 79 C64(0x20030a0244872), C64(0x12001008414402), C64(0x2006104900a0804), 80 C64(0x1004081002402), 81 }; 82 83 84 // Utility functions 85 86 int hash(U64 key, U64 magic, int relevant_bits) { 87 return (key * magic) >> (64 - relevant_bits); 88 } 89 90 // pseudo random numbers 91 92 U32 state = C32(1804289383); 93 94 U32 get_random_U32_number() { 95 U32 number = state; 96 97 number ^= number << 13; 98 number ^= number >> 17; 99 number ^= number << 5; 100 101 return state = number; 102 } 103 104 U64 get_random_U64_number() { 105 U64 n1, n2, n3, n4; 106 107 n1 = (U64)(get_random_U32_number()) & C64(0xFFFF); 108 n2 = (U64)(get_random_U32_number()) & C64(0xFFFF); 109 n3 = (U64)(get_random_U32_number()) & C64(0xFFFF); 110 n4 = (U64)(get_random_U32_number()) & C64(0xFFFF); 111 112 return n1 | (n2 << 16) | (n3 << 32) | (n4 << 48); 113 } 114 115 // pawn attack table [side][square] 116 U64 pawn_attacks[2][64]; 117 118 // knight attack table [square] 119 U64 knight_attacks[64]; 120 121 // king attack table [square] 122 U64 king_attacks[64]; 123 124 // bishop attack mask 125 U64 bishop_masks[64]; 126 127 // rook attack mask 128 U64 rook_masks[64]; 129 130 // bishop attack table [square][occupancies] 131 U64 bishop_attacks[64][512]; // 256 K 132 133 // rook attack table [square][occupancies] 134 U64 rook_attacks[64][4096]; // 2048K 135 136 U64 get_wpawn_attacks(Square square, U64 occupancy){ 137 UNUSED(occupancy); 138 return pawn_attacks[WHITE][square]; 139 } 140 141 U64 get_bpawn_attacks(Square square, U64 occupancy){ 142 UNUSED(occupancy); 143 return pawn_attacks[BLACK][square]; 144 } 145 146 U64 get_knight_attacks(Square square, U64 occupancy){ 147 UNUSED(occupancy); 148 return knight_attacks[square]; 149 } 150 151 U64 get_king_attacks(Square square, U64 occupancy){ 152 UNUSED(occupancy); 153 return king_attacks[square]; 154 } 155 156 U64 get_bishop_attacks(Square square, U64 occupancy){ 157 occupancy &= bishop_masks[square]; 158 occupancy = hash(occupancy, bishop_magic_numbers[square], 159 bishop_relevant_bits[square]); 160 return bishop_attacks[square][occupancy]; 161 } 162 163 U64 get_rook_attacks(Square square, U64 occupancy){ 164 occupancy &= rook_masks[square]; 165 occupancy = 166 hash(occupancy, rook_magic_numbers[square], rook_relevant_bits[square]); 167 return rook_attacks[square][occupancy]; 168 } 169 170 U64 get_queen_attacks(Square square, U64 occupancy){ 171 return (get_bishop_attacks(square, occupancy) | 172 get_rook_attacks(square, occupancy)); 173 } 174 175 176 // generate pawn attack 177 U64 mask_pawn_attacks(int side, Square square) { 178 U64 bitboard = C64(0); 179 180 bit_set(bitboard, square); 181 if (side == WHITE) 182 return noWeOne(bitboard) | noEaOne(bitboard); 183 else 184 return soWeOne(bitboard) | soEaOne(bitboard); 185 } 186 187 U64 mask_knight_attacks(Square square) { 188 U64 bitboard = C64(0), attacks = C64(0), tmp; 189 190 bit_set(bitboard, square); 191 tmp = nortOne(nortOne(bitboard)); 192 attacks |= westOne(tmp) | eastOne(tmp); 193 tmp = soutOne(soutOne(bitboard)); 194 attacks |= westOne(tmp) | eastOne(tmp); 195 tmp = westOne(westOne(bitboard)); 196 attacks |= soutOne(tmp) | nortOne(tmp); 197 tmp = eastOne(eastOne(bitboard)); 198 attacks |= soutOne(tmp) | nortOne(tmp); 199 200 return attacks; 201 } 202 203 U64 mask_king_attacks(Square square) { 204 U64 bitboard = C64(0), attacks = C64(0); 205 206 bit_set(bitboard, square); 207 attacks |= westOne(bitboard) | eastOne(bitboard); 208 attacks |= soutOne(bitboard) | nortOne(bitboard); 209 attacks |= soutOne(bitboard) | nortOne(bitboard); 210 attacks |= soEaOne(bitboard) | noEaOne(bitboard); 211 attacks |= soWeOne(bitboard) | noWeOne(bitboard); 212 213 return attacks; 214 } 215 216 U64 mask_slide_attacks(Square square, U64 block, const direction_f dir[4], 217 int len[4]) { 218 U64 bitboard = C64(0), attacks = C64(0), tmp; 219 int i, j; 220 221 bit_set(bitboard, square); 222 for (i = 0; i < 4; i++) { 223 for (j = 0, tmp = bitboard; j < len[i]; j++) { 224 attacks |= tmp = (dir[i])(tmp); 225 if (tmp & block) 226 break; 227 } 228 } 229 return attacks; 230 } 231 232 const direction_f bishop_direction[4] = {noEaOne, noWeOne, soEaOne, soWeOne}; 233 const direction_f rook_direction[4] = {westOne, soutOne, eastOne, nortOne}; 234 235 U64 mask_bishop_attacks(Square square) { 236 int tr = square / 8, tf = square % 8; 237 int len[4] = {MIN(7 - tf, 7 - tr) - 1, MIN(tf, 7 - tr) - 1, 238 MIN(7 - tf, tr) - 1, MIN(tf, tr) - 1}; 239 return mask_slide_attacks(square, C64(0), bishop_direction, len); 240 } 241 242 U64 mask_rook_attacks(Square square) { 243 int tr = square / 8, tf = square % 8; 244 int len[4] = {tf - 1, tr - 1, 6 - tf, 6 - tr}; 245 246 return mask_slide_attacks(square, C64(0), rook_direction, len); 247 } 248 249 U64 bishop_attacks_on_the_fly(Square square, U64 block) { 250 int tr = square / 8, tf = square % 8; 251 int len[4] = {MIN(7 - tf, 7 - tr), MIN(tf, 7 - tr), MIN(7 - tf, tr), 252 MIN(tf, tr)}; 253 254 return mask_slide_attacks(square, block, bishop_direction, len); 255 } 256 257 U64 rook_attacks_on_the_fly(Square square, U64 block) { 258 int tr = square / 8, tf = square % 8; 259 int len[4] = {tf, tr, 7 - tf, 7 - tr}; 260 261 return mask_slide_attacks(square, block, rook_direction, len); 262 } 263 264 void init_leapers_attacks(void) { 265 for (Square square = 0; square < 64; square++) { 266 pawn_attacks[WHITE][square] = mask_pawn_attacks(WHITE, square); 267 pawn_attacks[BLACK][square] = mask_pawn_attacks(BLACK, square); 268 knight_attacks[square] = mask_knight_attacks(square); 269 king_attacks[square] = mask_king_attacks(square); 270 } 271 } 272 273 U64 set_occupancy(int index, int bits_in_mask, U64 attack_mask) { 274 U64 occupancy = C64(0); 275 276 for (int count = 0; count < bits_in_mask; count++) { 277 Square square = bit_lsb_index(attack_mask); 278 bit_pop(attack_mask, square); 279 280 if (index & (1 << count)) 281 bit_set(occupancy, square); 282 } 283 284 return occupancy; 285 } 286 287 void init_sliders_attacks_internal(int bishop) { 288 for (Square square = 0; square < 64; square++) { 289 U64 attack_mask; 290 291 if (bishop) { 292 bishop_masks[square] = mask_bishop_attacks(square); 293 attack_mask = bishop_masks[square]; 294 } else { 295 rook_masks[square] = mask_rook_attacks(square); 296 attack_mask = rook_masks[square]; 297 } 298 299 int relevant_bits = bit_count(attack_mask); 300 int occupancy_indicies = 1 << relevant_bits; 301 302 for (int index = 0; index < occupancy_indicies; index++) { 303 U64 occupancy = set_occupancy(index, relevant_bits, attack_mask); 304 if (bishop) { 305 int magic_index = (occupancy * bishop_magic_numbers[square]) >> 306 (64 - bishop_relevant_bits[square]); 307 bishop_attacks[square][magic_index] = 308 bishop_attacks_on_the_fly(square, occupancy); 309 } else { 310 int magic_index = hash(occupancy, rook_magic_numbers[square], 311 rook_relevant_bits[square]); 312 rook_attacks[square][magic_index] = 313 rook_attacks_on_the_fly(square, occupancy); 314 } 315 } 316 } 317 } 318 319 void init_sliders_attacks(void) { 320 init_sliders_attacks_internal(0); 321 init_sliders_attacks_internal(1); 322 } 323 324 // magic numbers 325 326 U64 generate_magic_number() { 327 return get_random_U64_number() & get_random_U64_number() & 328 get_random_U64_number(); 329 } 330 331 U64 find_magic_number(Square square, int relevant_bits, int bishop) { 332 U64 occupancies[4096], attacks[4096], used_attacks[4096]; 333 U64 attack_mask = 334 bishop ? mask_bishop_attacks(square) : mask_rook_attacks(square); 335 int occupancy_indicies = 1 << relevant_bits; 336 337 for (int index = 0; index < occupancy_indicies; index++) { 338 occupancies[index] = set_occupancy(index, relevant_bits, attack_mask); 339 attacks[index] = bishop 340 ? bishop_attacks_on_the_fly(square, occupancies[index]) 341 : rook_attacks_on_the_fly(square, occupancies[index]); 342 } 343 344 for (int random_count = 0; random_count < 100000000; random_count++) { 345 U64 magic_number = generate_magic_number(); 346 if (bit_count((attack_mask * magic_number) & C64(0xFF00000000000000)) < 6) 347 continue; 348 349 memset(used_attacks, C64(0), sizeof(used_attacks)); 350 int index, fail; 351 352 for (index = 0, fail = 0; !fail && index < occupancy_indicies; index++) { 353 int magic_index = hash(occupancies[index], magic_number, relevant_bits); 354 355 if (used_attacks[magic_index] == C64(0)) 356 used_attacks[magic_index] = attacks[index]; 357 else if (used_attacks[magic_index] != attacks[index]) 358 fail = 1; 359 } 360 361 if (!fail) 362 return magic_number; 363 } 364 365 return C64(0); 366 }