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