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