git.sesse.net Git - stockfish/blob - src/bitbase.cpp

   1 /*
   2   Stockfish, a UCI chess playing engine derived from Glaurung 2.1
   3   Copyright (C) 2004-2008 Tord Romstad (Glaurung author)
   4   Copyright (C) 2008-2010 Marco Costalba, Joona Kiiski, Tord Romstad
   5
   6   Stockfish is free software: you can redistribute it and/or modify
   7   it under the terms of the GNU General Public License as published by
   8   the Free Software Foundation, either version 3 of the License, or
   9   (at your option) any later version.
  10
  11   Stockfish is distributed in the hope that it will be useful,
  12   but WITHOUT ANY WARRANTY; without even the implied warranty of
  13   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14   GNU General Public License for more details.
  15
  16   You should have received a copy of the GNU General Public License
  17   along with this program.  If not, see <http://www.gnu.org/licenses/>.
  18 */
  19
  20 #include <cassert>
  21
  22 #include "bitboard.h"
  23 #include "types.h"
  24
  25 namespace {
  26
  27   enum Result {
  28     RESULT_UNKNOWN,
  29     RESULT_INVALID,
  30     RESULT_WIN,
  31     RESULT_DRAW
  32   };
  33
  34   struct KPKPosition {
  35     Result classify_knowns(int index);
  36     Result classify(int index, Result db[]);
  37
  38   private:
  39     void from_index(int index);
  40     Result classify_white(const Result db[]);
  41     Result classify_black(const Result db[]);
  42     Bitboard wk_attacks()   const { return StepAttacksBB[WK][whiteKingSquare]; }
  43     Bitboard bk_attacks()   const { return StepAttacksBB[BK][blackKingSquare]; }
  44     Bitboard pawn_attacks() const { return StepAttacksBB[WP][pawnSquare]; }
  45
  46     Square whiteKingSquare, blackKingSquare, pawnSquare;
  47     Color sideToMove;
  48   };
  49
  50   // The possible pawns squares are 24, the first 4 files and ranks from 2 to 7
  51   const int IndexMax = 2 * 24 * 64 * 64; // color * wp_sq * wk_sq * bk_sq = 196608
  52
  53   // Each uint32_t stores results of 32 positions, one per bit
  54   uint32_t KPKBitbase[IndexMax / 32];
  55
  56   int compute_index(Square wksq, Square bksq, Square wpsq, Color stm);
  57 }
  58
  59
  60 uint32_t probe_kpk_bitbase(Square wksq, Square wpsq, Square bksq, Color stm) {
  61
  62   int index = compute_index(wksq, bksq, wpsq, stm);
  63
  64   return KPKBitbase[index / 32] & (1 << (index & 31));
  65 }
  66
  67
  68 void kpk_bitbase_init() {
  69
  70   Result db[IndexMax];
  71   KPKPosition pos;
  72   int index, bit, repeat = 1;
  73
  74   // Initialize table
  75   for (index = 0; index < IndexMax; index++)
  76       db[index] = pos.classify_knowns(index);
  77
  78   // Iterate until all positions are classified (30 cycles needed)
  79   while (repeat)
  80       for (repeat = index = 0; index < IndexMax; index++)
  81           if (   db[index] == RESULT_UNKNOWN
  82               && pos.classify(index, db) != RESULT_UNKNOWN)
  83               repeat = 1;
  84
  85   // Map 32 position results into one KPKBitbase[] entry
  86   for (index = 0; index < IndexMax / 32; index++)
  87       for (bit = 0; bit < 32; bit++)
  88           if (db[32 * index + bit] == RESULT_WIN)
  89               KPKBitbase[index] |= (1 << bit);
  90 }
  91
  92
  93 namespace {
  94
  95   // A KPK bitbase index is an integer in [0, IndexMax] range
  96   //
  97   // Information is mapped in this way
  98   //
  99   // bit     0: side to move (WHITE or BLACK)
 100   // bit  1- 6: black king square (from SQ_A1 to SQ_H8)
 101   // bit  7-12: white king square (from SQ_A1 to SQ_H8)
 102   // bit 13-14: white pawn file (from FILE_A to FILE_D)
 103   // bit 15-17: white pawn rank - 1 (from RANK_2 - 1 to RANK_7 - 1)
 104
 105   int compute_index(Square wksq, Square bksq, Square wpsq, Color stm) {
 106
 107     assert(square_file(wpsq) <= FILE_D);
 108
 109     int p = square_file(wpsq) + 4 * (square_rank(wpsq) - 1);
 110     int r = stm + 2 * bksq + 128 * wksq + 8192 * p;
 111
 112     assert(r >= 0 && r < IndexMax);
 113
 114     return r;
 115   }
 116
 117   void KPKPosition::from_index(int index) {
 118
 119     int s = index >> 13;
 120     sideToMove = Color(index & 1);
 121     blackKingSquare = Square((index >> 1) & 63);
 122     whiteKingSquare = Square((index >> 7) & 63);
 123     pawnSquare = make_square(File(s & 3), Rank((s >> 2) + 1));
 124   }
 125
 126   Result KPKPosition::classify_knowns(int index) {
 127
 128     from_index(index);
 129
 130     // Check if two pieces are on the same square
 131     if (   whiteKingSquare == pawnSquare
 132         || whiteKingSquare == blackKingSquare
 133         || blackKingSquare == pawnSquare)
 134         return RESULT_INVALID;
 135
 136     // Check if a king can be captured
 137     if (    bit_is_set(wk_attacks(), blackKingSquare)
 138         || (bit_is_set(pawn_attacks(), blackKingSquare) && sideToMove == WHITE))
 139         return RESULT_INVALID;
 140
 141     // The position is an immediate win if it is white to move and the
 142     // white pawn can be promoted without getting captured.
 143     if (   square_rank(pawnSquare) == RANK_7
 144         && sideToMove == WHITE
 145         && whiteKingSquare != pawnSquare + DELTA_N
 146         && (   square_distance(blackKingSquare, pawnSquare + DELTA_N) > 1
 147             || bit_is_set(wk_attacks(), pawnSquare + DELTA_N)))
 148         return RESULT_WIN;
 149
 150     // Check for known draw positions
 151     //
 152     // Case 1: Stalemate
 153     if (   sideToMove == BLACK
 154         && (bk_attacks() & ~(wk_attacks() | pawn_attacks())) == EmptyBoardBB)
 155         return RESULT_DRAW;
 156
 157     // Case 2: King can capture pawn
 158     if (   sideToMove == BLACK
 159         && bit_is_set(bk_attacks(), pawnSquare) && !bit_is_set(wk_attacks(), pawnSquare))
 160         return RESULT_DRAW;
 161
 162     // Case 3: Black king in front of white pawn
 163     if (   blackKingSquare == pawnSquare + DELTA_N
 164         && square_rank(pawnSquare) < RANK_7)
 165         return RESULT_DRAW;
 166
 167     //  Case 4: White king in front of pawn and black has opposition
 168     if (   whiteKingSquare == pawnSquare + DELTA_N
 169         && blackKingSquare == pawnSquare + DELTA_N + DELTA_N + DELTA_N
 170         && square_rank(pawnSquare) < RANK_5
 171         && sideToMove == WHITE)
 172         return RESULT_DRAW;
 173
 174     // Case 5: Stalemate with rook pawn
 175     if (   blackKingSquare == SQ_A8
 176         && square_file(pawnSquare) == FILE_A)
 177         return RESULT_DRAW;
 178
 179     return RESULT_UNKNOWN;
 180   }
 181
 182   Result KPKPosition::classify(int index, Result db[]) {
 183
 184     from_index(index);
 185     db[index] = (sideToMove == WHITE ? classify_white(db) : classify_black(db));
 186     return db[index];
 187   }
 188
 189   Result KPKPosition::classify_white(const Result db[]) {
 190
 191     // If one move leads to a position classified as RESULT_WIN, the result
 192     // of the current position is RESULT_WIN. If all moves lead to positions
 193     // classified as RESULT_DRAW, the current position is classified RESULT_DRAW
 194     // otherwise the current position is classified as RESULT_UNKNOWN.
 195
 196     bool unknownFound = false;
 197     Bitboard b;
 198     Square s;
 199     Result r;
 200
 201     // King moves
 202     b = wk_attacks();
 203     while (b)
 204     {
 205         s = pop_1st_bit(&b);
 206         r = db[compute_index(s, blackKingSquare, pawnSquare, BLACK)];
 207
 208         if (r == RESULT_WIN)
 209             return RESULT_WIN;
 210
 211         if (r == RESULT_UNKNOWN)
 212             unknownFound = true;
 213     }
 214
 215     // Pawn moves
 216     if (square_rank(pawnSquare) < RANK_7)
 217     {
 218         s = pawnSquare + DELTA_N;
 219         r = db[compute_index(whiteKingSquare, blackKingSquare, s, BLACK)];
 220
 221         if (r == RESULT_WIN)
 222             return RESULT_WIN;
 223
 224         if (r == RESULT_UNKNOWN)
 225             unknownFound = true;
 226
 227         // Double pawn push
 228         if (square_rank(s) == RANK_3 && r != RESULT_INVALID)
 229         {
 230             s += DELTA_N;
 231             r = db[compute_index(whiteKingSquare, blackKingSquare, s, BLACK)];
 232
 233             if (r == RESULT_WIN)
 234                 return RESULT_WIN;
 235
 236             if (r == RESULT_UNKNOWN)
 237                 unknownFound = true;
 238         }
 239     }
 240     return unknownFound ? RESULT_UNKNOWN : RESULT_DRAW;
 241   }
 242
 243   Result KPKPosition::classify_black(const Result db[]) {
 244
 245     // If one move leads to a position classified as RESULT_DRAW, the result
 246     // of the current position is RESULT_DRAW. If all moves lead to positions
 247     // classified as RESULT_WIN, the position is classified as RESULT_WIN.
 248     // Otherwise, the current position is classified as RESULT_UNKNOWN.
 249
 250     bool unknownFound = false;
 251     Bitboard b;
 252     Square s;
 253     Result r;
 254
 255     // King moves
 256     b = bk_attacks();
 257     while (b)
 258     {
 259         s = pop_1st_bit(&b);
 260         r = db[compute_index(whiteKingSquare, s, pawnSquare, WHITE)];
 261
 262         if (r == RESULT_DRAW)
 263             return RESULT_DRAW;
 264
 265         if (r == RESULT_UNKNOWN)
 266             unknownFound = true;
 267     }
 268     return unknownFound ? RESULT_UNKNOWN : RESULT_WIN;
 269   }
 270
 271 }