Subversion Repositories Games.Chess Giants

Rev

Blame | Last modification | View Log | Download | RSS feed

  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_ */
  203.