Stockfishのbitboardは、チェスなので盤面が8×8 = 64升であり、64bit変数に収まります。(将棋の場合、81升なので128bit変数もしくは、64bit変数が2つ必要になります。)
あと、magic bitboardと言う仕組みが使われています。これは斜めに利く駒の利きのbitboardに対して掛け算を使って連続するビットに移動させるテクニックです。→ Magic Bitboard – Chess Programming Wiki
Haswell以降であればBMIを使うべきでしょう。→ BMI使ってますか？
|
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 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 |
/* 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 */ #ifndef BITBOARD_H_INCLUDED #define BITBOARD_H_INCLUDED #include "types.h" namespace Bitboards { // Bitboard関連の定数・テーブルを初期化する。 void init(); // Bitboards::print()は容易に読みやすいフォーマットで標準出力にビットボードを表示する。 // これは、デバッグにおいてときどき有用である。 void print(Bitboard b); } namespace Bitbases { void init_kpk(); bool probe_kpk(Square wksq, Square wpsq, Square bksq, Color us); } // 各筋を意味するbitboard const Bitboard FileABB = 0x0101010101010101ULL; const Bitboard FileBBB = FileABB << 1; const Bitboard FileCBB = FileABB << 2; const Bitboard FileDBB = FileABB << 3; const Bitboard FileEBB = FileABB << 4; const Bitboard FileFBB = FileABB << 5; const Bitboard FileGBB = FileABB << 6; const Bitboard FileHBB = FileABB << 7; // 各段を意味するbitboard const Bitboard Rank1BB = 0xFF; const Bitboard Rank2BB = Rank1BB << (8 * 1); const Bitboard Rank3BB = Rank1BB << (8 * 2); const Bitboard Rank4BB = Rank1BB << (8 * 3); const Bitboard Rank5BB = Rank1BB << (8 * 4); const Bitboard Rank6BB = Rank1BB << (8 * 5); const Bitboard Rank7BB = Rank1BB << (8 * 6); const Bitboard Rank8BB = Rank1BB << (8 * 7); CACHE_LINE_ALIGNMENT extern Bitboard RMasks[SQUARE_NB]; extern Bitboard RMagics[SQUARE_NB]; extern Bitboard* RAttacks[SQUARE_NB]; extern unsigned RShifts[SQUARE_NB]; extern Bitboard BMasks[SQUARE_NB]; extern Bitboard BMagics[SQUARE_NB]; extern Bitboard* BAttacks[SQUARE_NB]; extern unsigned BShifts[SQUARE_NB]; // 盤面でSquareの場所が1であるBitboard extern Bitboard SquareBB[SQUARE_NB]; // 各筋 extern Bitboard FileBB[FILE_NB]; // 各段 extern Bitboard RankBB[RANK_NB]; extern Bitboard AdjacentFilesBB[FILE_NB]; extern Bitboard InFrontBB[COLOR_NB][RANK_NB]; // 小駒による利きのテーブル。 // StepAttacksBB[駒種(先後区別あり)][その駒の存在する升] extern Bitboard StepAttacksBB[PIECE_NB][SQUARE_NB]; // 2升(縦横斜の関係)に挟まれている升を返すためのテーブル extern Bitboard BetweenBB[SQUARE_NB][SQUARE_NB]; // 2枚が直線上(縦横斜の関係)にあるとき、その直線上が1であるbitboardを返すためのテーブル // (その線分ではなく直線なので端まで1) extern Bitboard LineBB[SQUARE_NB][SQUARE_NB]; extern Bitboard DistanceRingsBB[SQUARE_NB][8]; extern Bitboard ForwardBB[COLOR_NB][SQUARE_NB]; extern Bitboard PassedPawnMask[COLOR_NB][SQUARE_NB]; extern Bitboard PawnAttackSpan[COLOR_NB][SQUARE_NB]; // ある駒による利きの範囲(遮断される駒は考慮に入っていない、静的なテーブル) extern Bitboard PseudoAttacks[PIECE_TYPE_NB][SQUARE_NB]; // 筋の差か段の差かで大きいほうの値 // ※ s1,s2が縦横斜の関係にあるときは、s1から王を最短で何回の移動でs2に持っていけるかという値であるので // テーブル初期化に使える extern int SquareDistance[SQUARE_NB][SQUARE_NB]; const Bitboard DarkSquares = 0xAA55AA55AA55AA55ULL; /// Overloads of bitwise operators between a Bitboard and a Square for testing /// whether a given bit is set in a bitboard, and for setting and clearing bits. // BitboardとSquareとの間のbit演算子のオーバーロードで、これは与えられたビットが // ビットボードのなかでセットされているかをテストしたり、ビットを設定したりクリアしたりする。 // Bitboard盤面と、升sだけが1であるbitboardとをandをとってかえす // 結果として、升sが1であれば非0が返る。 // ToDo : 他のoperator、Bitboard&をとっているのに、これはなぜBitboardをとるのか？ inline Bitboard operator&(Bitboard b, Square s) { return b & SquareBB[s]; } inline Bitboard& operator|=(Bitboard& b, Square s) { return b |= SquareBB[s]; } inline Bitboard& operator^=(Bitboard& b, Square s) { return b ^= SquareBB[s]; } inline Bitboard operator|(Bitboard b, Square s) { return b | SquareBB[s]; } inline Bitboard operator^(Bitboard b, Square s) { return b ^ SquareBB[s]; } // 与えられたbitboardに駒が2駒以上あるのか。 inline bool more_than_one(Bitboard b) { return b & (b - 1); } // 筋の差か段の差かで大きいほうの値 // ※ s1,s2が縦横斜の関係にあるときは、s1から王を最短で何回の移動でs2に持っていけるかという値であるので // テーブル初期化に使える inline int square_distance(Square s1, Square s2) { return SquareDistance[s1][s2]; } // 筋の差(横方向の距離) inline int file_distance(Square s1, Square s2) { return abs(file_of(s1) - file_of(s2)); } // 段の差(縦方向の距離) inline int rank_distance(Square s1, Square s2) { return abs(rank_of(s1) - rank_of(s2)); } /// shift_bb() moves bitboard one step along direction Delta. Mainly for pawns. template inline Bitboard shift_bb(Bitboard b) { return Delta == DELTA_N ? b << 8 : Delta == DELTA_S ? b >> 8 : Delta == DELTA_NE ? (b & ~FileHBB) << 9 : Delta == DELTA_SE ? (b & ~FileHBB) >> 7 : Delta == DELTA_NW ? (b & ~FileABB) << 7 : Delta == DELTA_SW ? (b & ~FileABB) >> 9 : 0; } /// rank_bb() and file_bb() take a file or a square as input and return /// a bitboard representing all squares on the given file or rank. inline Bitboard rank_bb(Rank r) { return RankBB[r]; } inline Bitboard rank_bb(Square s) { return RankBB[rank_of(s)]; } inline Bitboard file_bb(File f) { return FileBB[f]; } inline Bitboard file_bb(Square s) { return FileBB[file_of(s)]; } /// adjacent_files_bb() takes a file as input and returns a bitboard representing /// all squares on the adjacent files. inline Bitboard adjacent_files_bb(File f) { return AdjacentFilesBB[f]; } /// in_front_bb() takes a color and a rank as input, and returns a bitboard /// representing all the squares on all ranks in front of the rank, from the /// given color's point of view. For instance, in_front_bb(BLACK, RANK_3) will /// give all squares on ranks 1 and 2. inline Bitboard in_front_bb(Color c, Rank r) { return InFrontBB[c][r]; } /// between_bb() returns a bitboard representing all squares between two squares. /// For instance, between_bb(SQ_C4, SQ_F7) returns a bitboard with the bits for /// square d5 and e6 set. If s1 and s2 are not on the same line, file or diagonal, /// 0 is returned. // s1からs2までの地点に挟まれた升を列挙する。縦横斜の関係にない場合は、挟まれた升はなし(0を返す)として扱う。 inline Bitboard between_bb(Square s1, Square s2) { return BetweenBB[s1][s2]; } /// forward_bb() takes a color and a square as input, and returns a bitboard /// representing all squares along the line in front of the square, from the /// point of view of the given color. Definition of the table is: /// ForwardBB[c][s] = in_front_bb(c, s) & file_bb(s) inline Bitboard forward_bb(Color c, Square s) { return ForwardBB[c][s]; } /// pawn_attack_span() takes a color and a square as input, and returns a bitboard /// representing all squares that can be attacked by a pawn of the given color /// when it moves along its file starting from the given square. Definition is: /// PawnAttackSpan[c][s] = in_front_bb(c, s) & adjacent_files_bb(s); inline Bitboard pawn_attack_span(Color c, Square s) { return PawnAttackSpan[c][s]; } /// passed_pawn_mask() takes a color and a square as input, and returns a /// bitboard mask which can be used to test if a pawn of the given color on /// the given square is a passed pawn. Definition of the table is: /// PassedPawnMask[c][s] = pawn_attack_span(c, s) | forward_bb(c, s) inline Bitboard passed_pawn_mask(Color c, Square s) { return PassedPawnMask[c][s]; } /// squares_of_color() returns a bitboard representing all squares with the same /// color of the given square. inline Bitboard squares_of_color(Square s) { return DarkSquares & s ? DarkSquares : ~DarkSquares; } /// aligned() returns true if the squares s1, s2 and s3 are aligned /// either on a straight or on a diagonal line. // s1,s2,s3が一直線上(縦横斜)にあればtrue。 // pinされている駒を移動させるときに、王と直線上への移動であれば開き王手にならないので // それを判定するために使う。 inline bool aligned(Square s1, Square s2, Square s3) { return LineBB[s1][s2] & s3; } /// Functions for computing sliding attack bitboards. Function attacks_bb() takes /// a square and a bitboard of occupied squares as input, and returns a bitboard /// representing all squares attacked by Pt (bishop or rook) on the given square. // 大駒による利きを計算するための関数。attacks_bbから呼び出される。 // occ = 盤面上の駒のbitboard(これらの駒で利きが遮断されるものとする) // この関数の返す利きは、大駒の移動可能場所であり、駒が存在する場所は含まない。 template FORCE_INLINE unsigned magic_index(Square s, Bitboard occ) { // マスク Bitboard* const Masks = Pt == ROOK ? RMasks : BMasks; // マジックテーブル Bitboard* const Magics = Pt == ROOK ? RMagics : BMagics; // マジックテーブルのシフト回数 unsigned* const Shifts = Pt == ROOK ? RShifts : BShifts; if (Is64Bit) return unsigned(((occ & Masks[s]) * Magics[s]) >> Shifts[s]); unsigned lo = unsigned(occ) & unsigned(Masks[s]); unsigned hi = unsigned(occ >> 32) & unsigned(Masks[s] >> 32); return (lo * unsigned(Magics[s]) ^ hi * unsigned(Magics[s] >> 32)) >> Shifts[s]; } // 駒種Ptによる利きのbitboardを生成。盤上に置かれた駒occをきちんと考慮する。 // (捕獲する升への利きも生成している) // PtはROOKかBISHOPのいずれか。大駒用。 // 小駒は StepAttacksBB[p][s]で済む。 template inline Bitboard attacks_bb(Square s, Bitboard occ) { // PtがROOKでなければBISHOP。 return (Pt == ROOK ? RAttacks : BAttacks)[s][magic_index } /// 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. // lsb()/msb()は0でないbitboardにおいて、最下位、最上位の1であるbitを見つける。 // pop_lsb()は0でないbitboardにおいて、1であるbitを見つけてそのbitをクリアする。 #ifdef USE_BSFQ # if defined(_MSC_VER) && !defined(__INTEL_COMPILER) FORCE_INLINE Square lsb(Bitboard b) { unsigned long index; _BitScanForward64(&index, b); return (Square) index; } FORCE_INLINE Square msb(Bitboard b) { unsigned long index; _BitScanReverse64(&index, b); return (Square) index; } # elif defined(__arm__) FORCE_INLINE int lsb32(uint32_t v) { __asm__("rbit %0, %1" : "=r"(v) : "r"(v)); return __builtin_clz(v); } FORCE_INLINE Square msb(Bitboard b) { return (Square) (63 - __builtin_clzll(b)); } FORCE_INLINE Square lsb(Bitboard b) { return (Square) (uint32_t(b) ? lsb32(uint32_t(b)) : 32 + lsb32(uint32_t(b >> 32))); } # else FORCE_INLINE Square lsb(Bitboard b) { // Assembly code by Heinz van Saanen Bitboard index; __asm__("bsfq %1, %0": "=r"(index): "rm"(b) ); return (Square) index; } FORCE_INLINE Square msb(Bitboard b) { Bitboard index; __asm__("bsrq %1, %0": "=r"(index): "rm"(b) ); return (Square) index; } # endif FORCE_INLINE Square pop_lsb(Bitboard* b) { const Square s = lsb(*b); *b &= *b - 1; return s; } #else // if defined(USE_BSFQ) extern Square msb(Bitboard b); extern Square lsb(Bitboard b); extern Square pop_lsb(Bitboard* b); #endif /// frontmost_sq() and backmost_sq() find the square corresponding to the /// most/least advanced bit relative to the given color. inline Square frontmost_sq(Color c, Bitboard b) { return c == WHITE ? msb(b) : lsb(b); } inline Square backmost_sq(Color c, Bitboard b) { return c == WHITE ? lsb(b) : msb(b); } #endif // #ifndef BITBOARD_H_INCLUDED |
|
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 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 |
/* 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 */ #include #include #include #include "bitboard.h" #include "bitcount.h" #include "misc.h" #include "rkiss.h" CACHE_LINE_ALIGNMENT // Rook用のmagic table(マスクとマジックテーブルとシフト回数) Bitboard RMasks[SQUARE_NB]; Bitboard RMagics[SQUARE_NB]; Bitboard* RAttacks[SQUARE_NB]; // Rook用の利きのテーブル(magic table)へのポインタ。 unsigned RShifts[SQUARE_NB]; // Bishop用のmagic table(マスクとマジックテーブルとシフト回数) Bitboard BMasks[SQUARE_NB]; Bitboard BMagics[SQUARE_NB]; Bitboard* BAttacks[SQUARE_NB]; // Bishop用の利きのテーブルへのポインタ。 unsigned BShifts[SQUARE_NB]; // 盤面のうち、Squareの場所のみ1であるBitboardを返す Bitboard SquareBB[SQUARE_NB]; // 各筋 Bitboard FileBB[FILE_NB]; // 各段 Bitboard RankBB[RANK_NB]; Bitboard AdjacentFilesBB[FILE_NB]; Bitboard InFrontBB[COLOR_NB][RANK_NB]; // 小駒による利きのテーブル。 // StepAttacksBB[駒種(先後区別あり)][その駒の存在する升] Bitboard StepAttacksBB[PIECE_NB][SQUARE_NB]; // 2升に挟まれている升を返すためのテーブル Bitboard BetweenBB[SQUARE_NB][SQUARE_NB]; // 2枚が直線上(縦横斜の関係)にあるとき、その直線上が1であるbitboardを返すためのテーブル // (その線分ではなく直線なので端まで1) Bitboard LineBB[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]; // 筋の差か段の差かで大きいほうの値 // ※ s1,s2が縦横斜の関係にあるときは、s1から王を最短で何回の移動でs2に持っていけるかという値であるので // テーブル初期化に使える int SquareDistance[SQUARE_NB][SQUARE_NB]; namespace { // De Bruijn sequences. See chessprogramming.wikispaces.com/BitScan // bitscanforwardを掛け算とシフトで行うための定数。 // http://chessprogramming.wikispaces.com/BitScan const uint64_t DeBruijn_64 = 0x3F79D71B4CB0A89ULL; const uint32_t DeBruijn_32 = 0x783A9B23; CACHE_LINE_ALIGNMENT // 1である最上位ビットのビット位置を返すためのテーブル 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 // bitscanforwardを掛け算とシフト演算でこなすためのテクニック。 // 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. #ifndef USE_BSFQ Square lsb(Bitboard b) { return BSFTable[bsf_index(b)]; } // bitboardから下位の1bitを取り出し、それに対応する盤上の位置を返す Square pop_lsb(Bitboard* b) { Bitboard bb = *b; *b = bb & (bb - 1); // return BSFTable[bsf_index(bb)]; } // 1になっている最上位のビットが下から数えて何bit目であるかを返す。 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 // ifndef USE_BSFQ /// Bitboards::print() prints a bitboard in an easily readable format to the /// standard output. This is sometimes useful for debugging. // Bitboards::print()は容易に読みやすいフォーマットで標準出力にビットボードを表示する。 // これは、デバッグにおいてときどき有用である。 void Bitboards::print(Bitboard b) { // ※ ここ、なぜnamespaceで書かないのか…。 // これは#defineで書かれているのでこう書くだけでio_lockが呼び出される。最後にsync_endlを出力しておけばそこでunlockされる。 sync_cout; // チェスでは段数は一番上がRANK 8で一番下がRANK 1なので逆順でループを回すことになる。 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. // Bitboards::init()は、bitboard関連の配列を初期化する。これは、プログラムの初期化中に呼び出される。 // ※ main()のなかから呼び出される。 void Bitboards::init() { // 1である最上位ビットのビット位置を返すためのテーブルの初期化 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); // Squareの升sのみが1であるBitboardであるSquareBB[]を初期化 for (Square s = SQ_A1; s <= SQ_H8; ++s) SquareBB[s] = 1ULL << s; // 筋・段を表すBitboardの初期化 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]; } // SquareDistanceとDistanceRingsBBの初期化 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)); if (s1 != s2) DistanceRingsBB[s1][SquareDistance[s1][s2] - 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 init_magics(BTable, BAttacks, BMagics, BMasks, BShifts, BDeltas, magic_index for (Square s = SQ_A1; s <= SQ_H8; ++s) { PseudoAttacks[QUEEN][s] = PseudoAttacks[BISHOP][s] = attacks_bb 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) // s1から8方向上にs2があるのであれば if (PseudoAttacks[QUEEN][s1] & s2) { // square_distanceは筋の差か段の差かで大きいほうの値 // ※ s1,s2が縦横斜の関係にあるときは、s1から王を最短で何回の移動でs2に持っていけるかという値であるので // テーブル初期化に使える Square delta = (s2 - s1) / square_distance(s1, s2); // 間に挟まれた升を1に for (Square s = s1 + delta; s != s2; s += delta) BetweenBB[s1][s2] |= s; // s1とs2の位置関係が斜めか十字かを確定させる PieceType pt = (PseudoAttacks[BISHOP][s1] & s2) ? BISHOP : ROOK; // 十字の位置関係にあるならs1,s2に飛車を置いたときの利きの共通部がs1,s2を通る直線。 // ただし、利きだとs1,s2が除外されてしまうのでこれを最後に足し合わせる。 // 斜めの位置関係にあるときも同様。 LineBB[s1][s2] = (PseudoAttacks[pt][s1] & PseudoAttacks[pt][s2]) | s1 | s2; } } 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 m = (m >> s1) | (m << (64 - s1)); m &= rk.rand m = (m >> s2) | (m << (64 - s2)); return m & rk.rand } // 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 // 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 std::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); } } } |
BMI2使って、3%速くなったって事例がありますね。
https://groups.google.com/forum/m/#!topic/fishcooking/5w7WHgzqdiY
マジですか…。速度アップで3%はでかいですねぇ…。情報ありがとうございます。お正月に頑張ってみます。
将棋所で動かすと、局面はposition・・・形式で与えられますが、position・・・からbitboardへの変換はどうやっていますか？(初期局面から指し進めていく感じでしょうか？)
局面を表現するのはPositionクラスですが、Bitboardは内部的に使用しているだけですので、Positionクラスの外部からは普通はBitboardの操作はせずに、初期局面からdo_move()で一手ずつ進めるだとか、Position::set()でsfen文字列を渡すかの二択ですね。以下は”position…moves…”の指し手文字列に従い一手進める箇所です。
https://github.com/yaneurao/YaneuraOu/blob/8e1baf5b95a09b560e1c64488750495cf2f1d847/source/usi.cpp#L395