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