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_LOSS,
  32     RESULT_DRAW
  33   };
  34
  35   struct KPKPosition {
  36     void from_index(int index);
  37     bool is_legal() const;
  38     bool is_immediate_draw() const;
  39     bool is_immediate_win() const;
  40     Bitboard wk_attacks()   const { return StepAttacksBB[WK][whiteKingSquare]; }
  41     Bitboard bk_attacks()   const { return StepAttacksBB[BK][blackKingSquare]; }
  42     Bitboard pawn_attacks() const { return StepAttacksBB[WP][pawnSquare]; }
  43
  44     Square whiteKingSquare, blackKingSquare, pawnSquare;
  45     Color sideToMove;
  46   };
  47
  48   // The possible pawns squares are 24, the first 4 files and ranks from 2 to 7
  49   const int IndexMax = 2 * 24 * 64 * 64; // color * wp_sq * wk_sq * bk_sq
  50
  51   // Each uint32_t stores results of 32 positions, one per bit
  52   uint32_t KPKBitbase[IndexMax / 32];
  53
  54   Result classify_wtm(const KPKPosition& pos, const Result bb[]);
  55   Result classify_btm(const KPKPosition& pos, const Result bb[]);
  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 init_kpk_bitbase() {
  69
  70   Result bb[IndexMax];
  71   KPKPosition pos;
  72   bool repeat;
  73
  74   // Initialize table
  75   for (int i = 0; i < IndexMax; i++)
  76   {
  77       pos.from_index(i);
  78       bb[i] = !pos.is_legal()          ? RESULT_INVALID
  79              : pos.is_immediate_draw() ? RESULT_DRAW
  80              : pos.is_immediate_win()  ? RESULT_WIN : RESULT_UNKNOWN;
  81   }
  82
  83   // Iterate until all positions are classified (30 cycles needed)
  84   do {
  85       repeat = false;
  86
  87       for (int i = 0; i < IndexMax; i++)
  88           if (bb[i] == RESULT_UNKNOWN)
  89           {
  90               pos.from_index(i);
  91
  92               bb[i] = (pos.sideToMove == WHITE) ? classify_wtm(pos, bb)
  93                                                 : classify_btm(pos, bb);
  94               if (bb[i] != RESULT_UNKNOWN)
  95                   repeat = true;
  96           }
  97
  98   } while (repeat);
  99
 100   // Map 32 position results into one KPKBitbase[] entry
 101   for (int i = 0; i < IndexMax / 32; i++)
 102       for (int j = 0; j < 32; j++)
 103           if (bb[32 * i + j] == RESULT_WIN || bb[32 * i + j] == RESULT_LOSS)
 104               KPKBitbase[i] |= (1 << j);
 105 }
 106
 107
 108 namespace {
 109
 110  // A KPK bitbase index is an integer in [0, IndexMax] range
 111  //
 112  // Information is mapped in this way
 113  //
 114  // bit     0: side to move (WHITE or BLACK)
 115  // bit  1- 6: black king square (from SQ_A1 to SQ_H8)
 116  // bit  7-12: white king square (from SQ_A1 to SQ_H8)
 117  // bit 13-14: white pawn file (from FILE_A to FILE_D)
 118  // bit 15-17: white pawn rank - 1 (from RANK_2 - 1 to RANK_7 - 1)
 119
 120   int compute_index(Square wksq, Square bksq, Square wpsq, Color stm) {
 121
 122     assert(square_file(wpsq) <= FILE_D);
 123
 124     int p = int(square_file(wpsq)) + 4 * int(square_rank(wpsq) - 1);
 125     int r = int(stm) + 2 * int(bksq) + 128 * int(wksq) + 8192 * p;
 126
 127     assert(r >= 0 && r < IndexMax);
 128
 129     return r;
 130   }
 131
 132   void KPKPosition::from_index(int index) {
 133
 134     int s = (index / 8192) % 24;
 135
 136     sideToMove = Color(index % 2);
 137     blackKingSquare = Square((index / 2) % 64);
 138     whiteKingSquare = Square((index / 128) % 64);
 139     pawnSquare = make_square(File(s % 4), Rank(s / 4 + 1));
 140   }
 141
 142   bool KPKPosition::is_legal() const {
 143
 144     if (   whiteKingSquare == pawnSquare
 145         || whiteKingSquare == blackKingSquare
 146         || blackKingSquare == pawnSquare)
 147         return false;
 148
 149     if (sideToMove == WHITE)
 150     {
 151         if (   bit_is_set(wk_attacks(), blackKingSquare)
 152             || bit_is_set(pawn_attacks(), blackKingSquare))
 153             return false;
 154     }
 155     else if (bit_is_set(bk_attacks(), whiteKingSquare))
 156         return false;
 157
 158     return true;
 159   }
 160
 161   bool KPKPosition::is_immediate_draw() const {
 162
 163     if (sideToMove == BLACK)
 164     {
 165         Bitboard wka = wk_attacks();
 166         Bitboard bka = bk_attacks();
 167
 168         // Case 1: Stalemate
 169         if ((bka & ~(wka | pawn_attacks())) == EmptyBoardBB)
 170             return true;
 171
 172         // Case 2: King can capture pawn
 173         if (bit_is_set(bka, pawnSquare) && !bit_is_set(wka, pawnSquare))
 174             return true;
 175     }
 176     else
 177     {
 178         // Case 1: Stalemate (possible pawn files are only from A to D)
 179         if (   whiteKingSquare == SQ_A8
 180             && pawnSquare == SQ_A7
 181             && (blackKingSquare == SQ_C7 || blackKingSquare == SQ_C8))
 182             return true;
 183     }
 184     return false;
 185   }
 186
 187   bool KPKPosition::is_immediate_win() const {
 188
 189     // The position is an immediate win if it is white to move and the
 190     // white pawn can be promoted without getting captured.
 191     return   sideToMove == WHITE
 192           && square_rank(pawnSquare) == RANK_7
 193           && whiteKingSquare != pawnSquare + DELTA_N
 194           && (   square_distance(blackKingSquare, pawnSquare + DELTA_N) > 1
 195               || bit_is_set(wk_attacks(), pawnSquare + DELTA_N));
 196   }
 197
 198   Result classify_wtm(const KPKPosition& pos, const Result bb[]) {
 199
 200     // If one move leads to a position classified as RESULT_LOSS, the result
 201     // of the current position is RESULT_WIN. If all moves lead to positions
 202     // classified as RESULT_DRAW, the current position is classified RESULT_DRAW
 203     // otherwise the current position is classified as RESULT_UNKNOWN.
 204
 205     bool unknownFound = false;
 206     Bitboard b;
 207     Square s;
 208     Result r;
 209
 210     // King moves
 211     b = pos.wk_attacks();
 212     while (b)
 213     {
 214         s = pop_1st_bit(&b);
 215         r = bb[compute_index(s, pos.blackKingSquare, pos.pawnSquare, BLACK)];
 216
 217         if (r == RESULT_LOSS)
 218             return RESULT_WIN;
 219
 220         if (r == RESULT_UNKNOWN)
 221             unknownFound = true;
 222     }
 223
 224     // Pawn moves
 225     if (square_rank(pos.pawnSquare) < RANK_7)
 226     {
 227         s = pos.pawnSquare + DELTA_N;
 228         r = bb[compute_index(pos.whiteKingSquare, pos.blackKingSquare, s, BLACK)];
 229
 230         if (r == RESULT_LOSS)
 231             return RESULT_WIN;
 232
 233         if (r == RESULT_UNKNOWN)
 234             unknownFound = true;
 235
 236         // Double pawn push
 237         if (   square_rank(s) == RANK_3
 238             && s != pos.whiteKingSquare
 239             && s != pos.blackKingSquare)
 240         {
 241             s += DELTA_N;
 242             r = bb[compute_index(pos.whiteKingSquare, pos.blackKingSquare, s, BLACK)];
 243
 244             if (r == RESULT_LOSS)
 245                 return RESULT_WIN;
 246
 247             if (r == RESULT_UNKNOWN)
 248                 unknownFound = true;
 249         }
 250     }
 251     return unknownFound ? RESULT_UNKNOWN : RESULT_DRAW;
 252   }
 253
 254
 255   Result classify_btm(const KPKPosition& pos, const Result bb[]) {
 256
 257     // If one move leads to a position classified as RESULT_DRAW, the result
 258     // of the current position is RESULT_DRAW. If all moves lead to positions
 259     // classified as RESULT_WIN, the current position is classified as
 260     // RESULT_LOSS. Otherwise, the current position is classified as
 261     // RESULT_UNKNOWN.
 262
 263     bool unknownFound = false;
 264     Bitboard b;
 265     Square s;
 266     Result r;
 267
 268     // King moves
 269     b = pos.bk_attacks();
 270     while (b)
 271     {
 272         s = pop_1st_bit(&b);
 273         r = bb[compute_index(pos.whiteKingSquare, s, pos.pawnSquare, WHITE)];
 274
 275         if (r == RESULT_DRAW)
 276             return RESULT_DRAW;
 277
 278         if (r == RESULT_UNKNOWN)
 279             unknownFound = true;
 280     }
 281     return unknownFound ? RESULT_UNKNOWN : RESULT_LOSS;
 282   }
 283
 284 }