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   const int IndexMax = 2 * 24 * 64 * 64;
  49
  50   uint8_t KPKBitbase[IndexMax / 8];
  51
  52   Result classify_wtm(const KPKPosition& pos, const Result bb[]);
  53   Result classify_btm(const KPKPosition& pos, const Result bb[]);
  54   int compute_index(Square wksq, Square bksq, Square wpsq, Color stm);
  55 }
  56
  57
  58 int probe_kpk_bitbase(Square wksq, Square wpsq, Square bksq, Color stm) {
  59
  60   int index = compute_index(wksq, bksq, wpsq, stm);
  61
  62   return KPKBitbase[index / 8] & (1 << (index & 7));
  63 }
  64
  65
  66 void init_kpk_bitbase() {
  67
  68   bool repeat;
  69   int i, j, b;
  70   KPKPosition pos;
  71   Result bb[IndexMax];
  72
  73   // Initialize table
  74   for (i = 0; i < IndexMax; i++)
  75   {
  76       pos.from_index(i);
  77       bb[i] = !pos.is_legal()          ? RESULT_INVALID
  78              : pos.is_immediate_draw() ? RESULT_DRAW
  79              : pos.is_immediate_win()  ? RESULT_WIN : RESULT_UNKNOWN;
  80   }
  81
  82   // Iterate until all positions are classified (30 cycles needed)
  83   do {
  84       repeat = false;
  85
  86       for (i = 0; i < IndexMax; i++)
  87           if (bb[i] == RESULT_UNKNOWN)
  88           {
  89               pos.from_index(i);
  90
  91               bb[i] = (pos.sideToMove == WHITE) ? classify_wtm(pos, bb)
  92                                                 : classify_btm(pos, bb);
  93               if (bb[i] != RESULT_UNKNOWN)
  94                   repeat = true;
  95           }
  96
  97   } while (repeat);
  98
  99   // Compress result and map into KPKBitbase[]
 100   for (i = 0; i < 24576; i++)
 101   {
 102       b = 0;
 103       for (j = 0; j < 8; j++)
 104           if (bb[8*i+j] == RESULT_WIN || bb[8*i+j] == RESULT_LOSS)
 105               b |= (1 << j);
 106
 107       KPKBitbase[i] = (uint8_t)b;
 108   }
 109 }
 110
 111
 112 namespace {
 113
 114   int compute_index(Square wksq, Square bksq, Square wpsq, Color stm) {
 115
 116       int p = int(square_file(wpsq)) + (int(square_rank(wpsq)) - 1) * 4;
 117       int r = int(stm) + 2 * int(bksq) + 128 * int(wksq) + 8192 * p;
 118
 119       assert(r >= 0 && r < IndexMax);
 120
 121       return r;
 122   }
 123
 124   void KPKPosition::from_index(int index) {
 125
 126     int s = (index / 8192) % 24;
 127
 128     sideToMove = Color(index % 2);
 129     blackKingSquare = Square((index / 2) % 64);
 130     whiteKingSquare = Square((index / 128) % 64);
 131     pawnSquare = make_square(File(s % 4), Rank(s / 4 + 1));
 132   }
 133
 134   bool KPKPosition::is_legal() const {
 135
 136     if (   whiteKingSquare == pawnSquare
 137         || whiteKingSquare == blackKingSquare
 138         || pawnSquare == blackKingSquare)
 139         return false;
 140
 141     if (sideToMove == WHITE)
 142     {
 143         if (   bit_is_set(wk_attacks(), blackKingSquare)
 144             || bit_is_set(pawn_attacks(), blackKingSquare))
 145             return false;
 146     }
 147     else if (bit_is_set(bk_attacks(), whiteKingSquare))
 148         return false;
 149
 150     return true;
 151   }
 152
 153   bool KPKPosition::is_immediate_draw() const {
 154
 155     if (sideToMove == BLACK)
 156     {
 157         Bitboard wka = wk_attacks();
 158         Bitboard bka = bk_attacks();
 159
 160         // Case 1: Stalemate
 161         if ((bka & ~(wka | pawn_attacks())) == EmptyBoardBB)
 162             return true;
 163
 164         // Case 2: King can capture pawn
 165         if (bit_is_set(bka, pawnSquare) && !bit_is_set(wka, pawnSquare))
 166             return true;
 167     }
 168     else
 169     {
 170         // Case 1: Stalemate
 171         if (   whiteKingSquare == SQ_A8
 172             && pawnSquare == SQ_A7
 173             && (blackKingSquare == SQ_C7 || blackKingSquare == SQ_C8))
 174             return true;
 175
 176         if (   whiteKingSquare == SQ_H8
 177             && pawnSquare == SQ_H7
 178             && (blackKingSquare == SQ_F7 || blackKingSquare == SQ_F8))
 179             return true;
 180     }
 181     return false;
 182   }
 183
 184   bool KPKPosition::is_immediate_win() const {
 185
 186     // The position is an immediate win if it is white to move and the
 187     // white pawn can be promoted without getting captured.
 188     return   sideToMove == WHITE
 189           && square_rank(pawnSquare) == RANK_7
 190           && whiteKingSquare != pawnSquare + DELTA_N
 191           && (   square_distance(blackKingSquare, pawnSquare + DELTA_N) > 1
 192               || bit_is_set(wk_attacks(), pawnSquare + DELTA_N));
 193   }
 194
 195   Result classify_wtm(const KPKPosition& pos, const Result bb[]) {
 196
 197     // If one move leads to a position classified as RESULT_LOSS, the result
 198     // of the current position is RESULT_WIN. If all moves lead to positions
 199     // classified as RESULT_DRAW, the current position is classified RESULT_DRAW
 200     // otherwise the current position is classified as RESULT_UNKNOWN.
 201
 202     bool unknownFound = false;
 203     Bitboard b;
 204     Square s;
 205     int idx;
 206
 207     // King moves
 208     b = pos.wk_attacks();
 209     while (b)
 210     {
 211         s = pop_1st_bit(&b);
 212         idx = compute_index(s, pos.blackKingSquare, pos.pawnSquare, BLACK);
 213
 214         switch (bb[idx]) {
 215
 216         case RESULT_LOSS:
 217             return RESULT_WIN;
 218
 219         case RESULT_UNKNOWN:
 220             unknownFound = true;
 221
 222         case RESULT_DRAW:
 223         case RESULT_INVALID:
 224              break;
 225
 226          default:
 227              assert(false);
 228         }
 229     }
 230
 231     // Pawn moves
 232     if (square_rank(pos.pawnSquare) < RANK_7)
 233     {
 234         s = pos.pawnSquare + DELTA_N;
 235         idx = compute_index(pos.whiteKingSquare, pos.blackKingSquare, s, BLACK);
 236
 237         switch (bb[idx]) {
 238
 239         case RESULT_LOSS:
 240             return RESULT_WIN;
 241
 242         case RESULT_UNKNOWN:
 243             unknownFound = true;
 244
 245         case RESULT_DRAW:
 246         case RESULT_INVALID:
 247             break;
 248
 249         default:
 250             assert(false);
 251         }
 252
 253         // Double pawn push
 254         if (   square_rank(s) == RANK_3
 255             && s != pos.whiteKingSquare
 256             && s != pos.blackKingSquare)
 257         {
 258             s += DELTA_N;
 259             idx = compute_index(pos.whiteKingSquare, pos.blackKingSquare, s, BLACK);
 260
 261             switch (bb[idx]) {
 262
 263             case RESULT_LOSS:
 264                 return RESULT_WIN;
 265
 266             case RESULT_UNKNOWN:
 267                 unknownFound = true;
 268
 269             case RESULT_DRAW:
 270             case RESULT_INVALID:
 271                 break;
 272
 273             default:
 274                 assert(false);
 275             }
 276         }
 277     }
 278     return unknownFound ? RESULT_UNKNOWN : RESULT_DRAW;
 279   }
 280
 281
 282   Result classify_btm(const KPKPosition& pos, const Result bb[]) {
 283
 284     // If one move leads to a position classified as RESULT_DRAW, the result
 285     // of the current position is RESULT_DRAW. If all moves lead to positions
 286     // classified as RESULT_WIN, the current position is classified as
 287     // RESULT_LOSS. Otherwise, the current position is classified as
 288     // RESULT_UNKNOWN.
 289
 290     bool unknownFound = false;
 291     Bitboard b;
 292     Square s;
 293     int idx;
 294
 295     // King moves
 296     b = pos.bk_attacks();
 297     while (b)
 298     {
 299         s = pop_1st_bit(&b);
 300         idx = compute_index(pos.whiteKingSquare, s, pos.pawnSquare, WHITE);
 301
 302         switch (bb[idx]) {
 303
 304         case RESULT_DRAW:
 305             return RESULT_DRAW;
 306
 307         case RESULT_UNKNOWN:
 308             unknownFound = true;
 309
 310         case RESULT_WIN:
 311         case RESULT_INVALID:
 312             break;
 313
 314         default:
 315             assert(false);
 316         }
 317     }
 318     return unknownFound ? RESULT_UNKNOWN : RESULT_LOSS;
 319   }
 320
 321 }