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