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