Details | Last modification | View Log | RSS feed
| Rev | Author | Line No. | Line |
|---|---|---|---|
| 99 | pmbaty | 1 | /* |
| 2 | Texel - A UCI chess engine. |
||
| 3 | Copyright (C) 2012-2014 Peter Österlund, peterosterlund2@gmail.com |
||
| 4 | |||
| 5 | This program is free software: you can redistribute it and/or modify |
||
| 6 | it under the terms of the GNU General Public License as published by |
||
| 7 | the Free Software Foundation, either version 3 of the License, or |
||
| 8 | (at your option) any later version. |
||
| 9 | |||
| 10 | This program is distributed in the hope that it will be useful, |
||
| 11 | but WITHOUT ANY WARRANTY; without even the implied warranty of |
||
| 12 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
||
| 13 | GNU General Public License for more details. |
||
| 14 | |||
| 15 | You should have received a copy of the GNU General Public License |
||
| 16 | along with this program. If not, see <http://www.gnu.org/licenses/>. |
||
| 17 | */ |
||
| 18 | |||
| 19 | /* |
||
| 20 | * bitBoard.hpp |
||
| 21 | * |
||
| 22 | * Created on: Feb 25, 2012 |
||
| 23 | * Author: petero |
||
| 24 | */ |
||
| 25 | |||
| 26 | #ifndef BITBOARD_HPP_ |
||
| 27 | #define BITBOARD_HPP_ |
||
| 28 | |||
| 29 | #include "util/util.hpp" |
||
| 30 | #include "util/alignedAlloc.hpp" |
||
| 31 | |||
| 32 | enum Square { |
||
| 33 | A1, B1, C1, D1, E1, F1, G1, H1, |
||
| 34 | A2, B2, C2, D2, E2, F2, G2, H2, |
||
| 35 | A3, B3, C3, D3, E3, F3, G3, H3, |
||
| 36 | A4, B4, C4, D4, E4, F4, G4, H4, |
||
| 37 | A5, B5, C5, D5, E5, F5, G5, H5, |
||
| 38 | A6, B6, C6, D6, E6, F6, G6, H6, |
||
| 39 | A7, B7, C7, D7, E7, F7, G7, H7, |
||
| 40 | A8, B8, C8, D8, E8, F8, G8, H8 |
||
| 41 | }; |
||
| 42 | |||
| 43 | class BitBoard { |
||
| 44 | public: |
||
| 45 | /** Squares attacked by a king on a given square. */ |
||
| 46 | static U64 kingAttacks[64]; |
||
| 47 | static U64 knightAttacks[64]; |
||
| 48 | static U64 wPawnAttacks[64], bPawnAttacks[64]; |
||
| 49 | |||
| 50 | // Squares preventing a pawn from being a passed pawn, if occupied by enemy pawn |
||
| 51 | static U64 wPawnBlockerMask[64], bPawnBlockerMask[64]; |
||
| 52 | |||
| 53 | static const U64 maskFileA = 0x0101010101010101ULL; |
||
| 54 | static const U64 maskFileB = 0x0202020202020202ULL; |
||
| 55 | static const U64 maskFileC = 0x0404040404040404ULL; |
||
| 56 | static const U64 maskFileD = 0x0808080808080808ULL; |
||
| 57 | static const U64 maskFileE = 0x1010101010101010ULL; |
||
| 58 | static const U64 maskFileF = 0x2020202020202020ULL; |
||
| 59 | static const U64 maskFileG = 0x4040404040404040ULL; |
||
| 60 | static const U64 maskFileH = 0x8080808080808080ULL; |
||
| 61 | |||
| 62 | static const U64 maskAToGFiles = 0x7F7F7F7F7F7F7F7FULL; |
||
| 63 | static const U64 maskBToHFiles = 0xFEFEFEFEFEFEFEFEULL; |
||
| 64 | static const U64 maskAToFFiles = 0x3F3F3F3F3F3F3F3FULL; |
||
| 65 | static const U64 maskCToHFiles = 0xFCFCFCFCFCFCFCFCULL; |
||
| 66 | |||
| 67 | static const U64 maskAToDFiles = 0x0F0F0F0F0F0F0F0FULL; |
||
| 68 | static const U64 maskEToHFiles = 0xF0F0F0F0F0F0F0F0ULL; |
||
| 69 | |||
| 70 | static const U64 maskFile[8]; |
||
| 71 | |||
| 72 | // Masks for squares where enemy pawn can capture en passant, indexed by file |
||
| 73 | static U64 epMaskW[8], epMaskB[8]; |
||
| 74 | |||
| 75 | static const U64 maskRow1 = 0x00000000000000FFULL; |
||
| 76 | static const U64 maskRow2 = 0x000000000000FF00ULL; |
||
| 77 | static const U64 maskRow3 = 0x0000000000FF0000ULL; |
||
| 78 | static const U64 maskRow4 = 0x00000000FF000000ULL; |
||
| 79 | static const U64 maskRow5 = 0x000000FF00000000ULL; |
||
| 80 | static const U64 maskRow6 = 0x0000FF0000000000ULL; |
||
| 81 | static const U64 maskRow7 = 0x00FF000000000000ULL; |
||
| 82 | static const U64 maskRow8 = 0xFF00000000000000ULL; |
||
| 83 | static const U64 maskRow1Row8 = 0xFF000000000000FFULL; |
||
| 84 | |||
| 85 | static const U64 maskDarkSq = 0xAA55AA55AA55AA55ULL; |
||
| 86 | static const U64 maskLightSq = 0x55AA55AA55AA55AAULL; |
||
| 87 | |||
| 88 | static const U64 maskCorners = 0x8100000000000081ULL; |
||
| 89 | |||
| 90 | /** Convert one or more squares to a bitmask. */ |
||
| 91 | static U64 sqMask(Square sq) { return 1ULL << sq; } |
||
| 92 | template <typename Sq0, typename... Squares> static U64 sqMask(Sq0 sq0, Squares... squares) { |
||
| 93 | return sqMask(sq0) | sqMask(squares...); |
||
| 94 | } |
||
| 95 | |||
| 96 | /** Mirror a bitmask in the X or Y direction. |
||
| 97 | * This implementation is slow. Use only in initialization code. */ |
||
| 98 | static U64 mirrorX(U64 mask); |
||
| 99 | static U64 mirrorY(U64 mask); |
||
| 100 | |||
| 101 | |||
| 102 | static U64 bishopAttacks(int sq, U64 occupied) { |
||
| 103 | return bTables[sq][(int)(((occupied & bMasks[sq]) * bMagics[sq]) >> (64 - bBits[sq]))]; |
||
| 104 | } |
||
| 105 | |||
| 106 | static U64 rookAttacks(int sq, U64 occupied) { |
||
| 107 | return rTables[sq][(int)(((occupied & rMasks[sq]) * rMagics[sq]) >> (64 - rBits[sq]))]; |
||
| 108 | } |
||
| 109 | |||
| 110 | static U64 squaresBetween[64][64]; |
||
| 111 | |||
| 112 | static int getDirection(int from, int to) { |
||
| 113 | int offs = to + (to|7) - from - (from|7) + 0x77; |
||
| 114 | return dirTable[offs]; |
||
| 115 | } |
||
| 116 | |||
| 117 | static int getKingDistance(int from, int to) { |
||
| 118 | int offs = to + (to|7) - from - (from|7) + 0x77; |
||
| 119 | return kingDistTable[offs]; |
||
| 120 | } |
||
| 121 | |||
| 122 | static int getTaxiDistance(int from, int to) { |
||
| 123 | int offs = to + (to|7) - from - (from|7) + 0x77; |
||
| 124 | return taxiDistTable[offs]; |
||
| 125 | } |
||
| 126 | |||
| 127 | static U64 southFill(U64 mask) { |
||
| 128 | mask |= (mask >> 8); |
||
| 129 | mask |= (mask >> 16); |
||
| 130 | mask |= (mask >> 32); |
||
| 131 | return mask; |
||
| 132 | } |
||
| 133 | |||
| 134 | static U64 northFill(U64 mask) { |
||
| 135 | mask |= (mask << 8); |
||
| 136 | mask |= (mask << 16); |
||
| 137 | mask |= (mask << 32); |
||
| 138 | return mask; |
||
| 139 | } |
||
| 140 | |||
| 141 | static int numberOfTrailingZeros(U64 mask) { |
||
| 142 | #ifdef HAS_CTZ |
||
| 143 | if (sizeof(U64) == sizeof(long)) |
||
| 144 | return __builtin_ctzl(mask); |
||
| 145 | else if (sizeof(U64) == sizeof(long long)) |
||
| 146 | return __builtin_ctzll(mask); |
||
| 147 | #endif |
||
| 148 | return trailingZ[(int)(((mask & (0-mask)) * 0x07EDD5E59A4E28C2ULL) >> 58)]; // Pierre-Marie Baty -- signedness fix |
||
| 149 | } |
||
| 150 | |||
| 151 | /** Get the lowest square from mask and remove the corresponding bit in mask. */ |
||
| 152 | static int extractSquare(U64& mask) { |
||
| 153 | int ret = numberOfTrailingZeros(mask); |
||
| 154 | mask &= mask - 1; |
||
| 155 | return ret; |
||
| 156 | } |
||
| 157 | |||
| 158 | /** Return number of 1 bits in mask. */ |
||
| 159 | static int bitCount(U64 mask) { |
||
| 160 | #ifdef HAS_POPCNT |
||
| 161 | if (sizeof(U64) == sizeof(long)) |
||
| 162 | return __builtin_popcountl(mask); |
||
| 163 | else if (sizeof(U64) == sizeof(long long)) |
||
| 164 | return __builtin_popcountl(mask >> 32) + |
||
| 165 | __builtin_popcountl(mask & 0xffffffffULL); |
||
| 166 | #endif |
||
| 167 | const U64 k1 = 0x5555555555555555ULL; |
||
| 168 | const U64 k2 = 0x3333333333333333ULL; |
||
| 169 | const U64 k4 = 0x0f0f0f0f0f0f0f0fULL; |
||
| 170 | const U64 kf = 0x0101010101010101ULL; |
||
| 171 | U64 t = mask; |
||
| 172 | t -= (t >> 1) & k1; |
||
| 173 | t = (t & k2) + ((t >> 2) & k2); |
||
| 174 | t = (t + (t >> 4)) & k4; |
||
| 175 | t = (t * kf) >> 56; |
||
| 176 | return (int)t; |
||
| 177 | } |
||
| 178 | |||
| 179 | /** Initialize static data. */ |
||
| 180 | static void staticInitialize(); |
||
| 181 | |||
| 182 | private: |
||
| 183 | static U64* rTables[64]; |
||
| 184 | static U64 rMasks[64]; |
||
| 185 | static int rBits[64]; |
||
| 186 | static const U64 rMagics[64]; |
||
| 187 | |||
| 188 | static U64* bTables[64]; |
||
| 189 | static U64 bMasks[64]; |
||
| 190 | static const int bBits[64]; |
||
| 191 | static const U64 bMagics[64]; |
||
| 192 | |||
| 193 | static vector_aligned<U64> tableData; |
||
| 194 | |||
| 195 | static const S8 dirTable[]; |
||
| 196 | static const S8 kingDistTable[]; |
||
| 197 | static const S8 taxiDistTable[]; |
||
| 198 | static const int trailingZ[64]; |
||
| 199 | }; |
||
| 200 | |||
| 201 | |||
| 202 | #endif /* BITBOARD_HPP_ */ |