X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fbitboard.cpp;h=0c38e182ba3633f5c6040f3f810d34de74657a6f;hp=0bbd155b10e0d71a1f3d52d83f25a95da72a86ec;hb=5bed82cd4e34c329bd08c57963ccc93c15ca0f05;hpb=bb751d6c890f5c50c642366d601740366cfae8d0 diff --git a/src/bitboard.cpp b/src/bitboard.cpp index 0bbd155b..0c38e182 100644 --- a/src/bitboard.cpp +++ b/src/bitboard.cpp @@ -1,17 +1,18 @@ /* - Glaurung, a UCI chess playing engine. - Copyright (C) 2004-2008 Tord Romstad + Stockfish, a UCI chess playing engine derived from Glaurung 2.1 + Copyright (C) 2004-2008 Tord Romstad (Glaurung author) + Copyright (C) 2008-2010 Marco Costalba, Joona Kiiski, Tord Romstad - Glaurung is free software: you can redistribute it and/or modify + 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. - - Glaurung is distributed in the hope that it will be useful, + + 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 . */ @@ -24,72 +25,102 @@ #include #include "bitboard.h" +#include "bitcount.h" #include "direction.h" -//// -//// Constants and variables -//// - -const Bitboard SquaresByColorBB[2] = {BlackSquaresBB, WhiteSquaresBB}; - -const Bitboard FileBB[8] = { - FileABB, FileBBB, FileCBB, FileDBB, FileEBB, FileFBB, FileGBB, FileHBB -}; +#if defined(IS_64BIT) -const Bitboard NeighboringFilesBB[8] = { - FileBBB, FileABB|FileCBB, FileBBB|FileDBB, FileCBB|FileEBB, - FileDBB|FileFBB, FileEBB|FileGBB, FileFBB|FileHBB, FileGBB +const uint64_t BMult[64] = { + 0x440049104032280ULL, 0x1021023c82008040ULL, 0x404040082000048ULL, + 0x48c4440084048090ULL, 0x2801104026490000ULL, 0x4100880442040800ULL, + 0x181011002e06040ULL, 0x9101004104200e00ULL, 0x1240848848310401ULL, + 0x2000142828050024ULL, 0x1004024d5000ULL, 0x102044400800200ULL, + 0x8108108820112000ULL, 0xa880818210c00046ULL, 0x4008008801082000ULL, + 0x60882404049400ULL, 0x104402004240810ULL, 0xa002084250200ULL, + 0x100b0880801100ULL, 0x4080201220101ULL, 0x44008080a00000ULL, + 0x202200842000ULL, 0x5006004882d00808ULL, 0x200045080802ULL, + 0x86100020200601ULL, 0xa802080a20112c02ULL, 0x80411218080900ULL, + 0x200a0880080a0ULL, 0x9a01010000104000ULL, 0x28008003100080ULL, + 0x211021004480417ULL, 0x401004188220806ULL, 0x825051400c2006ULL, + 0x140c0210943000ULL, 0x242800300080ULL, 0xc2208120080200ULL, + 0x2430008200002200ULL, 0x1010100112008040ULL, 0x8141050100020842ULL, + 0x822081014405ULL, 0x800c049e40400804ULL, 0x4a0404028a000820ULL, + 0x22060201041200ULL, 0x360904200840801ULL, 0x881a08208800400ULL, + 0x60202c00400420ULL, 0x1204440086061400ULL, 0x8184042804040ULL, + 0x64040315300400ULL, 0xc01008801090a00ULL, 0x808010401140c00ULL, + 0x4004830c2020040ULL, 0x80005002020054ULL, 0x40000c14481a0490ULL, + 0x10500101042048ULL, 0x1010100200424000ULL, 0x640901901040ULL, + 0xa0201014840ULL, 0x840082aa011002ULL, 0x10010840084240aULL, + 0x420400810420608ULL, 0x8d40230408102100ULL, 0x4a00200612222409ULL, + 0xa08520292120600ULL }; -const Bitboard ThisAndNeighboringFilesBB[8] = { - FileABB|FileBBB, FileABB|FileBBB|FileCBB, - FileBBB|FileCBB|FileDBB, FileCBB|FileDBB|FileEBB, - FileDBB|FileEBB|FileFBB, FileEBB|FileFBB|FileGBB, - FileFBB|FileGBB|FileHBB, FileGBB|FileHBB -}; - -const Bitboard RankBB[8] = { - Rank1BB, Rank2BB, Rank3BB, Rank4BB, Rank5BB, Rank6BB, Rank7BB, Rank8BB +const uint64_t RMult[64] = { + 0xa8002c000108020ULL, 0x4440200140003000ULL, 0x8080200010011880ULL, + 0x380180080141000ULL, 0x1a00060008211044ULL, 0x410001000a0c0008ULL, + 0x9500060004008100ULL, 0x100024284a20700ULL, 0x802140008000ULL, + 0x80c01002a00840ULL, 0x402004282011020ULL, 0x9862000820420050ULL, + 0x1001448011100ULL, 0x6432800200800400ULL, 0x40100010002000cULL, + 0x2800d0010c080ULL, 0x90c0008000803042ULL, 0x4010004000200041ULL, + 0x3010010200040ULL, 0xa40828028001000ULL, 0x123010008000430ULL, + 0x24008004020080ULL, 0x60040001104802ULL, 0x582200028400d1ULL, + 0x4000802080044000ULL, 0x408208200420308ULL, 0x610038080102000ULL, + 0x3601000900100020ULL, 0x80080040180ULL, 0xc2020080040080ULL, + 0x80084400100102ULL, 0x4022408200014401ULL, 0x40052040800082ULL, + 0xb08200280804000ULL, 0x8a80a008801000ULL, 0x4000480080801000ULL, + 0x911808800801401ULL, 0x822a003002001894ULL, 0x401068091400108aULL, + 0x4a10a00004cULL, 0x2000800640008024ULL, 0x1486408102020020ULL, + 0x100a000d50041ULL, 0x810050020b0020ULL, 0x204000800808004ULL, + 0x20048100a000cULL, 0x112000831020004ULL, 0x9000040810002ULL, + 0x440490200208200ULL, 0x8910401000200040ULL, 0x6404200050008480ULL, + 0x4b824a2010010100ULL, 0x4080801810c0080ULL, 0x400802a0080ULL, + 0x8224080110026400ULL, 0x40002c4104088200ULL, 0x1002100104a0282ULL, + 0x1208400811048021ULL, 0x3201014a40d02001ULL, 0x5100019200501ULL, + 0x101000208001005ULL, 0x2008450080702ULL, 0x1002080301d00cULL, + 0x410201ce5c030092ULL }; -const Bitboard RelativeRankBB[2][8] = { - { - Rank1BB, Rank2BB, Rank3BB, Rank4BB, Rank5BB, Rank6BB, Rank7BB, Rank8BB - }, - { - Rank8BB, Rank7BB, Rank6BB, Rank5BB, Rank4BB, Rank3BB, Rank2BB, Rank1BB - } +const int BShift[64] = { + 58, 59, 59, 59, 59, 59, 59, 58, 59, 59, 59, 59, 59, 59, 59, 59, + 59, 59, 57, 57, 57, 57, 59, 59, 59, 59, 57, 55, 55, 57, 59, 59, + 59, 59, 57, 55, 55, 57, 59, 59, 59, 59, 57, 57, 57, 57, 59, 59, + 59, 59, 59, 59, 59, 59, 59, 59, 58, 59, 59, 59, 59, 59, 59, 58 }; -const Bitboard InFrontBB[2][8] = { - { - Rank2BB | Rank3BB | Rank4BB | Rank5BB | Rank6BB | Rank7BB | Rank8BB, - Rank3BB | Rank4BB | Rank5BB | Rank6BB | Rank7BB | Rank8BB, - Rank4BB | Rank5BB | Rank6BB | Rank7BB | Rank8BB, - Rank5BB | Rank6BB | Rank7BB | Rank8BB, - Rank6BB | Rank7BB | Rank8BB, - Rank7BB | Rank8BB, - Rank8BB, - EmptyBoardBB - }, - { - EmptyBoardBB, - Rank1BB, - Rank2BB | Rank1BB, - Rank3BB | Rank2BB | Rank1BB, - Rank4BB | Rank3BB | Rank2BB | Rank1BB, - Rank5BB | Rank4BB | Rank3BB | Rank2BB | Rank1BB, - Rank6BB | Rank5BB | Rank4BB | Rank3BB | Rank2BB | Rank1BB, - Rank7BB | Rank6BB | Rank5BB | Rank4BB | Rank3BB | Rank2BB | Rank1BB - } +const int RShift[64] = { + 52, 53, 53, 53, 53, 53, 53, 52, 53, 54, 54, 54, 54, 54, 54, 53, + 53, 54, 54, 54, 54, 54, 54, 53, 53, 54, 54, 54, 54, 54, 54, 53, + 53, 54, 54, 54, 54, 54, 54, 53, 53, 54, 54, 54, 54, 54, 54, 53, + 53, 54, 54, 54, 54, 54, 54, 53, 52, 53, 53, 53, 53, 53, 53, 52 }; -#if defined(USE_COMPACT_ROOK_ATTACKS) - -Bitboard RankAttacks[8][64], FileAttacks[8][64]; +#else // if !defined(IS_64BIT) -#elif defined(USE_32BIT_ATTACKS) +const uint64_t BMult[64] = { + 0x54142844c6a22981ULL, 0x710358a6ea25c19eULL, 0x704f746d63a4a8dcULL, + 0xbfed1a0b80f838c5ULL, 0x90561d5631e62110ULL, 0x2804260376e60944ULL, + 0x84a656409aa76871ULL, 0xf0267f64c28b6197ULL, 0x70764ebb762f0585ULL, + 0x92aa09e0cfe161deULL, 0x41ee1f6bb266f60eULL, 0xddcbf04f6039c444ULL, + 0x5a3fab7bac0d988aULL, 0xd3727877fa4eaa03ULL, 0xd988402d868ddaaeULL, + 0x812b291afa075c7cULL, 0x94faf987b685a932ULL, 0x3ed867d8470d08dbULL, + 0x92517660b8901de8ULL, 0x2d97e43e058814b4ULL, 0x880a10c220b25582ULL, + 0xc7c6520d1f1a0477ULL, 0xdbfc7fbcd7656aa6ULL, 0x78b1b9bfb1a2b84fULL, + 0x2f20037f112a0bc1ULL, 0x657171ea2269a916ULL, 0xc08302b07142210eULL, + 0x880a4403064080bULL, 0x3602420842208c00ULL, 0x852800dc7e0b6602ULL, + 0x595a3fbbaa0f03b2ULL, 0x9f01411558159d5eULL, 0x2b4a4a5f88b394f2ULL, + 0x4afcbffc292dd03aULL, 0x4a4094a3b3f10522ULL, 0xb06f00b491f30048ULL, + 0xd5b3820280d77004ULL, 0x8b2e01e7c8e57a75ULL, 0x2d342794e886c2e6ULL, + 0xc302c410cde21461ULL, 0x111f426f1379c274ULL, 0xe0569220abb31588ULL, + 0x5026d3064d453324ULL, 0xe2076040c343cd8aULL, 0x93efd1e1738021eeULL, + 0xb680804bed143132ULL, 0x44e361b21986944cULL, 0x44c60170ef5c598cULL, + 0xf4da475c195c9c94ULL, 0xa3afbb5f72060b1dULL, 0xbc75f410e41c4ffcULL, + 0xb51c099390520922ULL, 0x902c011f8f8ec368ULL, 0x950b56b3d6f5490aULL, + 0x3909e0635bf202d0ULL, 0x5744f90206ec10ccULL, 0xdc59fd76317abbc1ULL, + 0x881c7c67fcbfc4f6ULL, 0x47ca41e7e440d423ULL, 0xeb0c88112048d004ULL, + 0x51c60e04359aef1aULL, 0x1aa1fe0e957a5554ULL, 0xdd9448db4f5e3104ULL, + 0xdc01f6dca4bebbdcULL, +}; const uint64_t RMult[64] = { 0xd7445cdec88002c0ULL, 0xd0a505c1f2001722ULL, 0xe065d1c896002182ULL, @@ -116,6 +147,13 @@ const uint64_t RMult[64] = { 0x5ac08a4735370479ULL, }; +const int BShift[64] = { + 26, 27, 27, 27, 27, 27, 27, 26, 27, 27, 27, 27, 27, 27, 27, 27, + 27, 27, 25, 25, 25, 25, 27, 27, 27, 27, 25, 23, 23, 25, 27, 27, + 27, 27, 25, 23, 23, 25, 27, 27, 27, 27, 25, 25, 25, 25, 27, 27, + 27, 27, 27, 27, 27, 27, 27, 27, 26, 27, 27, 27, 27, 27, 27, 26 +}; + const int RShift[64] = { 20, 21, 21, 21, 21, 21, 21, 20, 21, 22, 22, 22, 22, 22, 22, 21, 21, 22, 22, 22, 22, 22, 22, 21, 21, 22, 22, 22, 22, 22, 22, 21, @@ -123,158 +161,102 @@ const int RShift[64] = { 21, 22, 22, 22, 22, 22, 22, 21, 20, 21, 21, 21, 21, 21, 21, 20 }; -#else // if defined(USE_32BIT_ATTACKS) +#endif // defined(IS_64BIT) -const uint64_t RMult[64] = { - 0xa8002c000108020ULL, 0x4440200140003000ULL, 0x8080200010011880ULL, - 0x380180080141000ULL, 0x1a00060008211044ULL, 0x410001000a0c0008ULL, - 0x9500060004008100ULL, 0x100024284a20700ULL, 0x802140008000ULL, - 0x80c01002a00840ULL, 0x402004282011020ULL, 0x9862000820420050ULL, - 0x1001448011100ULL, 0x6432800200800400ULL, 0x40100010002000cULL, - 0x2800d0010c080ULL, 0x90c0008000803042ULL, 0x4010004000200041ULL, - 0x3010010200040ULL, 0xa40828028001000ULL, 0x123010008000430ULL, - 0x24008004020080ULL, 0x60040001104802ULL, 0x582200028400d1ULL, - 0x4000802080044000ULL, 0x408208200420308ULL, 0x610038080102000ULL, - 0x3601000900100020ULL, 0x80080040180ULL, 0xc2020080040080ULL, - 0x80084400100102ULL, 0x4022408200014401ULL, 0x40052040800082ULL, - 0xb08200280804000ULL, 0x8a80a008801000ULL, 0x4000480080801000ULL, - 0x911808800801401ULL, 0x822a003002001894ULL, 0x401068091400108aULL, - 0x4a10a00004cULL, 0x2000800640008024ULL, 0x1486408102020020ULL, - 0x100a000d50041ULL, 0x810050020b0020ULL, 0x204000800808004ULL, - 0x20048100a000cULL, 0x112000831020004ULL, 0x9000040810002ULL, - 0x440490200208200ULL, 0x8910401000200040ULL, 0x6404200050008480ULL, - 0x4b824a2010010100ULL, 0x4080801810c0080ULL, 0x400802a0080ULL, - 0x8224080110026400ULL, 0x40002c4104088200ULL, 0x1002100104a0282ULL, - 0x1208400811048021ULL, 0x3201014a40d02001ULL, 0x5100019200501ULL, - 0x101000208001005ULL, 0x2008450080702ULL, 0x1002080301d00cULL, - 0x410201ce5c030092ULL -}; +const Bitboard LightSquaresBB = 0x55AA55AA55AA55AAULL; +const Bitboard DarkSquaresBB = 0xAA55AA55AA55AA55ULL; -const int RShift[64] = { - 52, 53, 53, 53, 53, 53, 53, 52, 53, 54, 54, 54, 54, 54, 54, 53, - 53, 54, 54, 54, 54, 54, 54, 53, 53, 54, 54, 54, 54, 54, 54, 53, - 53, 54, 54, 54, 54, 54, 54, 53, 53, 54, 54, 54, 54, 54, 54, 53, - 53, 54, 54, 54, 54, 54, 54, 53, 52, 53, 53, 53, 53, 53, 53, 52 -}; - -#endif // defined(USE_32BIT_ATTACKS) - -#if !defined(USE_COMPACT_ROOK_ATTACKS) -Bitboard RMask[64]; -int RAttackIndex[64]; -Bitboard RAttacks[0x19000]; -#endif +const Bitboard SquaresByColorBB[2] = { DarkSquaresBB, LightSquaresBB }; -#if defined(USE_32BIT_ATTACKS) +const Bitboard FileBB[8] = { + FileABB, FileBBB, FileCBB, FileDBB, FileEBB, FileFBB, FileGBB, FileHBB +}; -const uint64_t BMult[64] = { - 0x54142844c6a22981ULL, 0x710358a6ea25c19eULL, 0x704f746d63a4a8dcULL, - 0xbfed1a0b80f838c5ULL, 0x90561d5631e62110ULL, 0x2804260376e60944ULL, - 0x84a656409aa76871ULL, 0xf0267f64c28b6197ULL, 0x70764ebb762f0585ULL, - 0x92aa09e0cfe161deULL, 0x41ee1f6bb266f60eULL, 0xddcbf04f6039c444ULL, - 0x5a3fab7bac0d988aULL, 0xd3727877fa4eaa03ULL, 0xd988402d868ddaaeULL, - 0x812b291afa075c7cULL, 0x94faf987b685a932ULL, 0x3ed867d8470d08dbULL, - 0x92517660b8901de8ULL, 0x2d97e43e058814b4ULL, 0x880a10c220b25582ULL, - 0xc7c6520d1f1a0477ULL, 0xdbfc7fbcd7656aa6ULL, 0x78b1b9bfb1a2b84fULL, - 0x2f20037f112a0bc1ULL, 0x657171ea2269a916ULL, 0xc08302b07142210eULL, - 0x880a4403064080bULL, 0x3602420842208c00ULL, 0x852800dc7e0b6602ULL, - 0x595a3fbbaa0f03b2ULL, 0x9f01411558159d5eULL, 0x2b4a4a5f88b394f2ULL, - 0x4afcbffc292dd03aULL, 0x4a4094a3b3f10522ULL, 0xb06f00b491f30048ULL, - 0xd5b3820280d77004ULL, 0x8b2e01e7c8e57a75ULL, 0x2d342794e886c2e6ULL, - 0xc302c410cde21461ULL, 0x111f426f1379c274ULL, 0xe0569220abb31588ULL, - 0x5026d3064d453324ULL, 0xe2076040c343cd8aULL, 0x93efd1e1738021eeULL, - 0xb680804bed143132ULL, 0x44e361b21986944cULL, 0x44c60170ef5c598cULL, - 0xf4da475c195c9c94ULL, 0xa3afbb5f72060b1dULL, 0xbc75f410e41c4ffcULL, - 0xb51c099390520922ULL, 0x902c011f8f8ec368ULL, 0x950b56b3d6f5490aULL, - 0x3909e0635bf202d0ULL, 0x5744f90206ec10ccULL, 0xdc59fd76317abbc1ULL, - 0x881c7c67fcbfc4f6ULL, 0x47ca41e7e440d423ULL, 0xeb0c88112048d004ULL, - 0x51c60e04359aef1aULL, 0x1aa1fe0e957a5554ULL, 0xdd9448db4f5e3104ULL, - 0xdc01f6dca4bebbdcULL, -}; +const Bitboard NeighboringFilesBB[8] = { + FileBBB, FileABB|FileCBB, FileBBB|FileDBB, FileCBB|FileEBB, + FileDBB|FileFBB, FileEBB|FileGBB, FileFBB|FileHBB, FileGBB +}; -const int BShift[64] = { - 26, 27, 27, 27, 27, 27, 27, 26, 27, 27, 27, 27, 27, 27, 27, 27, - 27, 27, 25, 25, 25, 25, 27, 27, 27, 27, 25, 23, 23, 25, 27, 27, - 27, 27, 25, 23, 23, 25, 27, 27, 27, 27, 25, 25, 25, 25, 27, 27, - 27, 27, 27, 27, 27, 27, 27, 27, 26, 27, 27, 27, 27, 27, 27, 26 +const Bitboard ThisAndNeighboringFilesBB[8] = { + FileABB|FileBBB, FileABB|FileBBB|FileCBB, + FileBBB|FileCBB|FileDBB, FileCBB|FileDBB|FileEBB, + FileDBB|FileEBB|FileFBB, FileEBB|FileFBB|FileGBB, + FileFBB|FileGBB|FileHBB, FileGBB|FileHBB }; -#else // if defined(USE_32BIT_ATTACKS) +const Bitboard RankBB[8] = { + Rank1BB, Rank2BB, Rank3BB, Rank4BB, Rank5BB, Rank6BB, Rank7BB, Rank8BB +}; -const uint64_t BMult[64] = { - 0x440049104032280ULL, 0x1021023c82008040ULL, 0x404040082000048ULL, - 0x48c4440084048090ULL, 0x2801104026490000ULL, 0x4100880442040800ULL, - 0x181011002e06040ULL, 0x9101004104200e00ULL, 0x1240848848310401ULL, - 0x2000142828050024ULL, 0x1004024d5000ULL, 0x102044400800200ULL, - 0x8108108820112000ULL, 0xa880818210c00046ULL, 0x4008008801082000ULL, - 0x60882404049400ULL, 0x104402004240810ULL, 0xa002084250200ULL, - 0x100b0880801100ULL, 0x4080201220101ULL, 0x44008080a00000ULL, - 0x202200842000ULL, 0x5006004882d00808ULL, 0x200045080802ULL, - 0x86100020200601ULL, 0xa802080a20112c02ULL, 0x80411218080900ULL, - 0x200a0880080a0ULL, 0x9a01010000104000ULL, 0x28008003100080ULL, - 0x211021004480417ULL, 0x401004188220806ULL, 0x825051400c2006ULL, - 0x140c0210943000ULL, 0x242800300080ULL, 0xc2208120080200ULL, - 0x2430008200002200ULL, 0x1010100112008040ULL, 0x8141050100020842ULL, - 0x822081014405ULL, 0x800c049e40400804ULL, 0x4a0404028a000820ULL, - 0x22060201041200ULL, 0x360904200840801ULL, 0x881a08208800400ULL, - 0x60202c00400420ULL, 0x1204440086061400ULL, 0x8184042804040ULL, - 0x64040315300400ULL, 0xc01008801090a00ULL, 0x808010401140c00ULL, - 0x4004830c2020040ULL, 0x80005002020054ULL, 0x40000c14481a0490ULL, - 0x10500101042048ULL, 0x1010100200424000ULL, 0x640901901040ULL, - 0xa0201014840ULL, 0x840082aa011002ULL, 0x10010840084240aULL, - 0x420400810420608ULL, 0x8d40230408102100ULL, 0x4a00200612222409ULL, - 0xa08520292120600ULL +const Bitboard RelativeRankBB[2][8] = { + { Rank1BB, Rank2BB, Rank3BB, Rank4BB, Rank5BB, Rank6BB, Rank7BB, Rank8BB }, + { Rank8BB, Rank7BB, Rank6BB, Rank5BB, Rank4BB, Rank3BB, Rank2BB, Rank1BB } }; -const int BShift[64] = { - 58, 59, 59, 59, 59, 59, 59, 58, 59, 59, 59, 59, 59, 59, 59, 59, - 59, 59, 57, 57, 57, 57, 59, 59, 59, 59, 57, 55, 55, 57, 59, 59, - 59, 59, 57, 55, 55, 57, 59, 59, 59, 59, 57, 57, 57, 57, 59, 59, - 59, 59, 59, 59, 59, 59, 59, 59, 58, 59, 59, 59, 59, 59, 59, 58 +const Bitboard InFrontBB[2][8] = { + { Rank2BB | Rank3BB | Rank4BB | Rank5BB | Rank6BB | Rank7BB | Rank8BB, + Rank3BB | Rank4BB | Rank5BB | Rank6BB | Rank7BB | Rank8BB, + Rank4BB | Rank5BB | Rank6BB | Rank7BB | Rank8BB, + Rank5BB | Rank6BB | Rank7BB | Rank8BB, + Rank6BB | Rank7BB | Rank8BB, + Rank7BB | Rank8BB, + Rank8BB, + EmptyBoardBB + }, + { EmptyBoardBB, + Rank1BB, + Rank2BB | Rank1BB, + Rank3BB | Rank2BB | Rank1BB, + Rank4BB | Rank3BB | Rank2BB | Rank1BB, + Rank5BB | Rank4BB | Rank3BB | Rank2BB | Rank1BB, + Rank6BB | Rank5BB | Rank4BB | Rank3BB | Rank2BB | Rank1BB, + Rank7BB | Rank6BB | Rank5BB | Rank4BB | Rank3BB | Rank2BB | Rank1BB + } }; -#endif // defined(USE_32BIT_ATTACKS) +Bitboard RMask[64]; +int RAttackIndex[64]; +Bitboard RAttacks[0x19000]; Bitboard BMask[64]; int BAttackIndex[64]; Bitboard BAttacks[0x1480]; -Bitboard SetMaskBB[64]; -Bitboard ClearMaskBB[64]; +Bitboard SetMaskBB[65]; +Bitboard ClearMaskBB[65]; Bitboard StepAttackBB[16][64]; Bitboard RayBB[64][8]; Bitboard BetweenBB[64][64]; +Bitboard SquaresInFrontMask[2][64]; Bitboard PassedPawnMask[2][64]; -Bitboard OutpostMask[2][64]; +Bitboard AttackSpanMask[2][64]; Bitboard BishopPseudoAttacks[64]; Bitboard RookPseudoAttacks[64]; Bitboard QueenPseudoAttacks[64]; +uint8_t BitCount8Bit[256]; + //// //// Local definitions //// namespace { + void init_masks(); void init_ray_bitboards(); void init_attacks(); void init_between_bitboards(); + void init_pseudo_attacks(); + Bitboard index_to_bitboard(int index, Bitboard mask); Bitboard sliding_attacks(int sq, Bitboard block, int dirs, int deltas[][2], int fmin, int fmax, int rmin, int rmax); - Bitboard index_to_bitboard(int index, Bitboard mask); - void init_sliding_attacks(Bitboard attacks[], - int attackIndex[], Bitboard mask[], - const int shift[2], const Bitboard mult[], - int deltas[][2]); - void init_pseudo_attacks(); -#if defined(USE_COMPACT_ROOK_ATTACKS) - void init_file_and_rank_attacks(); -#endif -}; + void init_sliding_attacks(Bitboard attacks[], int attackIndex[], Bitboard mask[], + const int shift[], const Bitboard mult[], int deltas[][2]); +} //// @@ -285,11 +267,14 @@ namespace { /// standard output. This is sometimes useful for debugging. void print_bitboard(Bitboard b) { - for(Rank r = RANK_8; r >= RANK_1; r--) { - std::cout << "+---+---+---+---+---+---+---+---+" << std::endl; - for(File f = FILE_A; f <= FILE_H; f++) - std::cout << "| " << (bit_is_set(b, make_square(f, r))? 'X' : ' ') << ' '; - std::cout << "|" << std::endl; + + for (Rank r = RANK_8; r >= RANK_1; r--) + { + std::cout << "+---+---+---+---+---+---+---+---+" << std::endl; + for (File f = FILE_A; f <= FILE_H; f++) + std::cout << "| " << (bit_is_set(b, make_square(f, r))? 'X' : ' ') << ' '; + + std::cout << "|" << std::endl; } std::cout << "+---+---+---+---+---+---+---+---+" << std::endl; } @@ -299,80 +284,97 @@ void print_bitboard(Bitboard b) { /// program initialization. void init_bitboards() { + int rookDeltas[4][2] = {{0,1},{0,-1},{1,0},{-1,0}}; int bishopDeltas[4][2] = {{1,1},{-1,1},{1,-1},{-1,-1}}; + init_masks(); init_ray_bitboards(); init_attacks(); init_between_bitboards(); -#if defined(USE_COMPACT_ROOK_ATTACKS) - init_file_and_rank_attacks(); -#else - init_sliding_attacks(RAttacks, RAttackIndex, RMask, RShift, - RMult, rookDeltas); -#endif - init_sliding_attacks(BAttacks, BAttackIndex, BMask, BShift, - BMult, bishopDeltas); + init_sliding_attacks(RAttacks, RAttackIndex, RMask, RShift, RMult, rookDeltas); + init_sliding_attacks(BAttacks, BAttackIndex, BMask, BShift, BMult, bishopDeltas); init_pseudo_attacks(); } -#if defined(USE_FOLDED_BITSCAN) - -static const int BitTable[64] = { - 63, 30, 3, 32, 25, 41, 22, 33, 15, 50, 42, 13, 11, 53, 19, 34, 61, 29, 2, - 51, 21, 43, 45, 10, 18, 47, 1, 54, 9, 57, 0, 35, 62, 31, 40, 4, 49, 5, 52, - 26, 60, 6, 23, 44, 46, 27, 56, 16, 7, 39, 48, 24, 59, 14, 12, 55, 38, 28, - 58, 20, 37, 17, 36, 8 -}; - - /// first_1() finds the least significant nonzero bit in a nonzero bitboard. - -Square first_1(Bitboard b) { - b ^= (b - 1); - uint32_t fold = int(b) ^ int(b >> 32); - return Square(BitTable[(fold * 0x783a9b23) >> 26]); -} - - /// pop_1st_bit() finds and clears the least significant nonzero bit in a /// nonzero bitboard. -Square pop_1st_bit(Bitboard *b) { - Bitboard bb = *b ^ (*b - 1); - uint32_t fold = int(bb) ^ int(bb >> 32); - *b &= (*b - 1); - return Square(BitTable[(fold * 0x783a9b23) >> 26]); -} - -#else +#if defined(IS_64BIT) && !defined(USE_BSFQ) -static const int BitTable[64] = { +static CACHE_LINE_ALIGNMENT +const int BitTable[64] = { 0, 1, 2, 7, 3, 13, 8, 19, 4, 25, 14, 28, 9, 34, 20, 40, 5, 17, 26, 38, 15, 46, 29, 48, 10, 31, 35, 54, 21, 50, 41, 57, 63, 6, 12, 18, 24, 27, 33, 39, 16, 37, 45, 47, 30, 53, 49, 56, 62, 11, 23, 32, 36, 44, 52, 55, 61, 22, 43, 51, 60, 42, 59, 58 }; +Square first_1(Bitboard b) { + return Square(BitTable[((b & -b) * 0x218a392cd3d5dbfULL) >> 58]); +} -/// first_1() finds the least significant nonzero bit in a nonzero bitboard. +Square pop_1st_bit(Bitboard* b) { + Bitboard bb = *b; + *b &= (*b - 1); + return Square(BitTable[((bb & -bb) * 0x218a392cd3d5dbfULL) >> 58]); +} + +#elif !defined(USE_BSFQ) + +static CACHE_LINE_ALIGNMENT +const int BitTable[64] = { + 63, 30, 3, 32, 25, 41, 22, 33, 15, 50, 42, 13, 11, 53, 19, 34, 61, 29, 2, + 51, 21, 43, 45, 10, 18, 47, 1, 54, 9, 57, 0, 35, 62, 31, 40, 4, 49, 5, 52, + 26, 60, 6, 23, 44, 46, 27, 56, 16, 7, 39, 48, 24, 59, 14, 12, 55, 38, 28, + 58, 20, 37, 17, 36, 8 +}; Square first_1(Bitboard b) { - return Square(BitTable[((b & -b) * 0x218a392cd3d5dbfULL) >> 58]); + + b ^= (b - 1); + uint32_t fold = int(b) ^ int(b >> 32); + return Square(BitTable[(fold * 0x783a9b23) >> 26]); } +// Use type-punning +union b_union { -/// pop_1st_bit() finds and clears the least significant nonzero bit in a -/// nonzero bitboard. + Bitboard b; + struct { +#if defined (BIGENDIAN) + uint32_t h; + uint32_t l; +#else + uint32_t l; + uint32_t h; +#endif + } dw; +}; -Square pop_1st_bit(Bitboard *b) { - Bitboard bb = *b; - *b &= (*b - 1); - return Square(BitTable[((bb & -bb) * 0x218a392cd3d5dbfULL) >> 58]); +Square pop_1st_bit(Bitboard* bb) { + + b_union u; + Square ret; + + u.b = *bb; + + if (u.dw.l) + { + ret = Square(BitTable[((u.dw.l ^ (u.dw.l - 1)) * 0x783a9b23) >> 26]); + u.dw.l &= (u.dw.l - 1); + *bb = u.b; + return ret; + } + ret = Square(BitTable[((~(u.dw.h ^ (u.dw.h - 1))) * 0x783a9b23) >> 26]); + u.dw.h &= (u.dw.h - 1); + *bb = u.b; + return ret; } -#endif // defined(USE_FOLDED_BITSCAN) +#endif namespace { @@ -383,159 +385,163 @@ namespace { // be necessary to touch any of them. void init_masks() { - for(Square s = SQ_A1; s <= SQ_H8; s++) { - SetMaskBB[s] = (1ULL << s); - ClearMaskBB[s] = ~SetMaskBB[s]; + + SetMaskBB[SQ_NONE] = 0ULL; + ClearMaskBB[SQ_NONE] = ~SetMaskBB[SQ_NONE]; + + for (Square s = SQ_A1; s <= SQ_H8; s++) + { + SetMaskBB[s] = (1ULL << s); + ClearMaskBB[s] = ~SetMaskBB[s]; } - for(Color c = WHITE; c <= BLACK; c++) - for(Square s = SQ_A1; s <= SQ_H8; s++) { - PassedPawnMask[c][s] = - in_front_bb(c, s) & this_and_neighboring_files_bb(s); - OutpostMask[c][s] = in_front_bb(c, s) & neighboring_files_bb(s); - } + + for (Color c = WHITE; c <= BLACK; c++) + for (Square s = SQ_A1; s <= SQ_H8; s++) + { + SquaresInFrontMask[c][s] = in_front_bb(c, s) & file_bb(s); + PassedPawnMask[c][s] = in_front_bb(c, s) & this_and_neighboring_files_bb(s); + AttackSpanMask[c][s] = in_front_bb(c, s) & neighboring_files_bb(s); + } + + for (Bitboard b = 0ULL; b < 256ULL; b++) + BitCount8Bit[b] = (uint8_t)count_1s(b); } + int remove_bit_8(int i) { return ((i & ~15) >> 1) | (i & 7); } void init_ray_bitboards() { + int d[8] = {1, -1, 16, -16, 17, -17, 15, -15}; - for(int i = 0; i < 128; i = i + 9 & ~8) { - for(int j = 0; j < 8; j++) { - RayBB[(i&7)|((i>>4)<<3)][j] = EmptyBoardBB; - for(int k = i + d[j]; (k & 0x88) == 0; k += d[j]) - set_bit(&(RayBB[(i&7)|((i>>4)<<3)][j]), Square((k&7)|((k>>4)<<3))); - } - } - } + for (int i = 0; i < 128; i = (i + 9) & ~8) + for (int j = 0; j < 8; j++) + { + RayBB[remove_bit_8(i)][j] = EmptyBoardBB; + for (int k = i + d[j]; (k & 0x88) == 0; k += d[j]) + set_bit(&(RayBB[remove_bit_8(i)][j]), Square(remove_bit_8(k))); + } + } void init_attacks() { - int i, j, k, l; - int step[16][8] = { + + const int step[16][8] = { {0}, {7,9,0}, {17,15,10,6,-6,-10,-15,-17}, {9,7,-7,-9,0}, {8,1,-1,-8,0}, {9,7,-7,-9,8,1,-1,-8}, {9,7,-7,-9,8,1,-1,-8}, {0}, {0}, {-7,-9,0}, {17,15,10,6,-6,-10,-15,-17}, {9,7,-7,-9,0}, {8,1,-1,-8,0}, {9,7,-7,-9,8,1,-1,-8}, {9,7,-7,-9,8,1,-1,-8} }; - - for(i = 0; i < 64; i++) { - for(j = 0; j <= int(BK); j++) { - StepAttackBB[j][i] = EmptyBoardBB; - for(k = 0; k < 8 && step[j][k] != 0; k++) { - l = i + step[j][k]; - if(l >= 0 && l < 64 && abs((i&7) - (l&7)) < 3) - StepAttackBB[j][i] |= (1ULL << l); + + for (int i = 0; i < 64; i++) + for (int j = 0; j <= int(BK); j++) + { + StepAttackBB[j][i] = EmptyBoardBB; + for (int k = 0; k < 8 && step[j][k] != 0; k++) + { + int l = i + step[j][k]; + if (l >= 0 && l < 64 && abs((i & 7) - (l & 7)) < 3) + StepAttackBB[j][i] |= (1ULL << l); + } } - } - } } - Bitboard sliding_attacks(int sq, Bitboard block, int dirs, int deltas[][2], int fmin=0, int fmax=7, int rmin=0, int rmax=7) { Bitboard result = 0ULL; - int rk = sq / 8, fl = sq % 8, r, f, i; - for(i = 0; i < dirs; i++) { - int dx = deltas[i][0], dy = deltas[i][1]; - for(f = fl+dx, r = rk+dy; - (dx==0 || (f>=fmin && f<=fmax)) && (dy==0 || (r>=rmin && r<=rmax)); - f += dx, r += dy) { - result |= (1ULL << (f + r*8)); - if(block & (1ULL << (f + r*8))) break; - } + int rk = sq / 8; + int fl = sq % 8; + + for (int i = 0; i < dirs; i++) + { + int dx = deltas[i][0]; + int dy = deltas[i][1]; + int f = fl + dx; + int r = rk + dy; + + while ( (dx == 0 || (f >= fmin && f <= fmax)) + && (dy == 0 || (r >= rmin && r <= rmax))) + { + result |= (1ULL << (f + r*8)); + if (block & (1ULL << (f + r*8))) + break; + + f += dx; + r += dy; + } } return result; } - void init_between_bitboards() { - SquareDelta step[8] = { - DELTA_E, DELTA_W, DELTA_N, DELTA_S, DELTA_NE, DELTA_SW, DELTA_NW, DELTA_SE - }; - SignedDirection d; - for(Square s1 = SQ_A1; s1 <= SQ_H8; s1++) - for(Square s2 = SQ_A1; s2 <= SQ_H8; s2++) { - BetweenBB[s1][s2] = EmptyBoardBB; - d = signed_direction_between_squares(s1, s2); - if(d != SIGNED_DIR_NONE) - for(Square s3 = s1 + step[d]; s3 != s2; s3 += step[d]) - set_bit(&(BetweenBB[s1][s2]), s3); + + const SquareDelta step[8] = { DELTA_E, DELTA_W, DELTA_N, DELTA_S, + DELTA_NE, DELTA_SW, DELTA_NW, DELTA_SE }; + + for (Square s1 = SQ_A1; s1 <= SQ_H8; s1++) + for (Square s2 = SQ_A1; s2 <= SQ_H8; s2++) + { + BetweenBB[s1][s2] = EmptyBoardBB; + SignedDirection d = signed_direction_between_squares(s1, s2); + + if (d != SIGNED_DIR_NONE) + { + for (Square s3 = s1 + step[d]; s3 != s2; s3 += step[d]) + set_bit(&(BetweenBB[s1][s2]), s3); + } } } - Bitboard index_to_bitboard(int index, Bitboard mask) { - int i, j, bits = count_1s(mask); + Bitboard result = 0ULL; - for(i = 0; i < bits; i++) { - j = pop_1st_bit(&mask); - if(index & (1 << i)) result |= (1ULL << j); + int bits = count_1s(mask); + + for (int i = 0; i < bits; i++) + { + int j = pop_1st_bit(&mask); + if (index & (1 << i)) + result |= (1ULL << j); } return result; } + void init_sliding_attacks(Bitboard attacks[], int attackIndex[], Bitboard mask[], + const int shift[], const Bitboard mult[], int deltas[][2]) { - void init_sliding_attacks(Bitboard attacks[], - int attackIndex[], Bitboard mask[], - const int shift[2], const Bitboard mult[], - int deltas[][2]) { - int i, j, k, index = 0; - Bitboard b; - for(i = 0; i < 64; i++) { - attackIndex[i] = index; - mask[i] = sliding_attacks(i, 0ULL, 4, deltas, 1, 6, 1, 6); - j = (1 << (64 - shift[i])); - for(k = 0; k < j; k++) { -#if defined(USE_32BIT_ATTACKS) - b = index_to_bitboard(k, mask[i]); - attacks[index + - (unsigned(int(b) * int(mult[i]) ^ - int(b >> 32) * int(mult[i] >> 32)) - >> shift[i])] = - sliding_attacks(i, b, 4, deltas); + for (int i = 0, index = 0; i < 64; i++) + { + attackIndex[i] = index; + mask[i] = sliding_attacks(i, 0ULL, 4, deltas, 1, 6, 1, 6); + +#if defined(IS_64BIT) + int j = (1 << (64 - shift[i])); #else - b = index_to_bitboard(k, mask[i]); - attacks[index + ((b * mult[i]) >> shift[i])] = - sliding_attacks(i, b, 4, deltas); + int j = (1 << (32 - shift[i])); #endif - } - index += j; + + for (int k = 0; k < j; k++) + { +#if defined(IS_64BIT) + Bitboard b = index_to_bitboard(k, mask[i]); + attacks[index + ((b * mult[i]) >> shift[i])] = sliding_attacks(i, b, 4, deltas); +#else + Bitboard b = index_to_bitboard(k, mask[i]); + unsigned v = int(b) * int(mult[i]) ^ int(b >> 32) * int(mult[i] >> 32); + attacks[index + (v >> shift[i])] = sliding_attacks(i, b, 4, deltas); +#endif + } + index += j; } } - void init_pseudo_attacks() { - Square s; - for(s = SQ_A1; s <= SQ_H8; s++) { - BishopPseudoAttacks[s] = bishop_attacks_bb(s, EmptyBoardBB); - RookPseudoAttacks[s] = rook_attacks_bb(s, EmptyBoardBB); - QueenPseudoAttacks[s] = queen_attacks_bb(s, EmptyBoardBB); - } - } -#if defined(USE_COMPACT_ROOK_ATTACKS) - void init_file_and_rank_attacks() { - int i, j, k, l, m, s; - Bitboard b1, b2; - for(i = 0; i < 64; i++) { - - for(m = 0; m <= 1; m++) { - b1 = 0ULL; - for(j = 0; j < 6; j++) if(i & (1<= 0 && l <= 7; l += s) { - b2 |= (m? RankBB[l] : FileBB[l]); - if(b1 & (1ULL << (l*(1+m*7)))) break; - } - } - if(m) FileAttacks[j][(b1*0xd6e8802041d0c441ULL) >> 58] = b2; - else RankAttacks[j][i] = b2; - } - } + for (Square s = SQ_A1; s <= SQ_H8; s++) + { + BishopPseudoAttacks[s] = bishop_attacks_bb(s, EmptyBoardBB); + RookPseudoAttacks[s] = rook_attacks_bb(s, EmptyBoardBB); + QueenPseudoAttacks[s] = queen_attacks_bb(s, EmptyBoardBB); } } -#endif // defined(USE_COMPACT_ROOK_ATTACKS) - + }