src/bitbase.cpp

   1 /*
   2   Glaurung, a UCI chess playing engine.
   3   Copyright (C) 2004-2008 Tord Romstad
   4
   5   Glaurung is free software: you can redistribute it and/or modify
   6   it under the terms of the GNU General Public License as published by
   7   the Free Software Foundation, either version 3 of the License, or
   8   (at your option) any later version.
   9
  10   Glaurung is distributed in the hope that it will be useful,
  11   but WITHOUT ANY WARRANTY; without even the implied warranty of
  12   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13   GNU General Public License for more details.
  14
  15   You should have received a copy of the GNU General Public License
  16   along with this program.  If not, see <http://www.gnu.org/licenses/>.
  17 */
  18
  19
  20 ////
  21 //// Includes
  22 ////
  23
  24 #include <cassert>
  25
  26 #include "bitbase.h"
  27 #include "bitboard.h"
  28 #include "move.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     int to_index() const;
  49     bool is_legal() const;
  50     bool is_immediate_draw() const;
  51     bool is_immediate_win() const;
  52     Bitboard wk_attacks() const;
  53     Bitboard bk_attacks() const;
  54     Bitboard pawn_attacks() const;
  55
  56     Square whiteKingSquare, blackKingSquare, pawnSquare;
  57     Color sideToMove;
  58   };
  59
  60
  61   Result *Bitbase;
  62   const int IndexMax = 2*24*64*64;
  63   int UnknownCount = 0;
  64
  65   void initialize();
  66   bool next_iteration();
  67   Result classify_wtm(const KPKPosition &p);
  68   Result classify_btm(const KPKPosition &p);
  69   int compute_index(Square wksq, Square bksq, Square psq, Color stm);
  70   int compress_result(Result r);
  71
  72 }
  73
  74
  75 ////
  76 //// Functions
  77 ////
  78
  79 void generate_kpk_bitbase(uint8_t bitbase[]) {
  80   // Allocate array and initialize:
  81   Bitbase = new Result[IndexMax];
  82   initialize();
  83
  84   // Iterate until all positions are classified:
  85   while(next_iteration());
  86
  87   // Compress bitbase into the supplied parameter:
  88   int i, j, b;
  89   for(i = 0; i < 24576; i++) {
  90     for(b = 0, j = 0; j < 8; b |= (compress_result(Bitbase[8*i+j]) << j), j++);
  91     bitbase[i] = b;
  92   }
  93
  94   // Release allocated memory:
  95   delete [] Bitbase;
  96 }
  97
  98
  99 namespace {
 100
 101   void KPKPosition::from_index(int index) {
 102     int s;
 103     sideToMove = Color(index % 2);
 104     blackKingSquare = Square((index / 2) % 64);
 105     whiteKingSquare = Square((index / 128) % 64);
 106     s = (index / 8192) % 24;
 107     pawnSquare = make_square(File(s % 4), Rank(s / 4 + 1));
 108   }
 109
 110
 111   int KPKPosition::to_index() const {
 112     return compute_index(whiteKingSquare, blackKingSquare, pawnSquare,
 113                          sideToMove);
 114   }
 115
 116
 117   bool KPKPosition::is_legal() const {
 118     if(whiteKingSquare == pawnSquare || whiteKingSquare == blackKingSquare ||
 119        pawnSquare == blackKingSquare)
 120       return false;
 121     if(sideToMove == WHITE) {
 122       if(bit_is_set(this->wk_attacks(), blackKingSquare))
 123         return false;
 124       if(bit_is_set(this->pawn_attacks(), blackKingSquare))
 125         return false;
 126     }
 127     else {
 128       if(bit_is_set(this->bk_attacks(), whiteKingSquare))
 129         return false;
 130     }
 131     return true;
 132   }
 133
 134
 135   bool KPKPosition::is_immediate_draw() const {
 136     if(sideToMove == BLACK) {
 137       Bitboard wka = this->wk_attacks();
 138       Bitboard bka = this->bk_attacks();
 139
 140       // Case 1: Stalemate
 141       if((bka & ~(wka | this->pawn_attacks())) == EmptyBoardBB)
 142         return true;
 143
 144       // Case 2: King can capture pawn
 145       if(bit_is_set(bka, pawnSquare) && !bit_is_set(wka, pawnSquare))
 146         return true;
 147     }
 148     else {
 149       // Case 1: Stalemate
 150       if(whiteKingSquare == SQ_A8 && pawnSquare == SQ_A7 &&
 151          (blackKingSquare == SQ_C7 || blackKingSquare == SQ_C8))
 152         return true;
 153     }
 154
 155     return false;
 156   }
 157
 158
 159   bool KPKPosition::is_immediate_win() const {
 160     // The position is an immediate win if it is white to move and the white
 161     // pawn can be promoted without getting captured:
 162     return
 163       sideToMove == WHITE &&
 164       square_rank(pawnSquare) == RANK_7 &&
 165       (square_distance(blackKingSquare, pawnSquare+DELTA_N) > 1 ||
 166        bit_is_set(this->wk_attacks(), pawnSquare+DELTA_N));
 167   }
 168
 169
 170   Bitboard KPKPosition::wk_attacks() const {
 171     return StepAttackBB[WK][whiteKingSquare];
 172   }
 173
 174
 175   Bitboard KPKPosition::bk_attacks() const {
 176     return StepAttackBB[BK][blackKingSquare];
 177   }
 178
 179
 180   Bitboard KPKPosition::pawn_attacks() const {
 181     return StepAttackBB[WP][pawnSquare];
 182   }
 183
 184
 185   void initialize() {
 186     KPKPosition p;
 187     for(int i = 0; i < IndexMax; i++) {
 188       p.from_index(i);
 189       if(!p.is_legal())
 190         Bitbase[i] = RESULT_INVALID;
 191       else if(p.is_immediate_draw())
 192         Bitbase[i] = RESULT_DRAW;
 193       else if(p.is_immediate_win())
 194         Bitbase[i] = RESULT_WIN;
 195       else {
 196         Bitbase[i] = RESULT_UNKNOWN;
 197         UnknownCount++;
 198       }
 199     }
 200   }
 201
 202
 203   bool next_iteration() {
 204     KPKPosition p;
 205     int previousUnknownCount = UnknownCount;
 206
 207     for(int i = 0; i < IndexMax; i++)
 208       if(Bitbase[i] == RESULT_UNKNOWN) {
 209         p.from_index(i);
 210
 211         Bitbase[i] = (p.sideToMove == WHITE)? classify_wtm(p) : classify_btm(p);
 212
 213         if(Bitbase[i] == RESULT_WIN || Bitbase[i] == RESULT_LOSS ||
 214            Bitbase[i] == RESULT_DRAW)
 215           UnknownCount--;
 216       }
 217
 218     return UnknownCount != previousUnknownCount;
 219   }
 220
 221
 222   Result classify_wtm(const KPKPosition &p) {
 223
 224     // If one move leads to a position classified as RESULT_LOSS, the result
 225     // of the current position is RESULT_WIN.  If all moves lead to positions
 226     // classified as RESULT_DRAW, the current position is classified as
 227     // RESULT_DRAW.  Otherwise, the current position is classified as
 228     // RESULT_UNKNOWN.
 229
 230     bool unknownFound = false;
 231     Bitboard b;
 232     Square s;
 233
 234     // King moves
 235     b = p.wk_attacks();
 236     while(b) {
 237       s = pop_1st_bit(&b);
 238       switch(Bitbase[compute_index(s, p.blackKingSquare, p.pawnSquare,
 239                                    BLACK)]) {
 240       case RESULT_LOSS:
 241         return RESULT_WIN;
 242
 243       case RESULT_UNKNOWN:
 244         unknownFound = true;
 245         break;
 246
 247       case RESULT_DRAW: case RESULT_INVALID:
 248         break;
 249
 250       default:
 251         assert(false);
 252       }
 253     }
 254
 255     // Pawn moves
 256     if(square_rank(p.pawnSquare) < RANK_7) {
 257       s = p.pawnSquare + DELTA_N;
 258       switch(Bitbase[compute_index(p.whiteKingSquare, p.blackKingSquare, s,
 259                                    BLACK)]) {
 260       case RESULT_LOSS:
 261         return RESULT_WIN;
 262
 263       case RESULT_UNKNOWN:
 264         unknownFound = true;
 265         break;
 266
 267       case RESULT_DRAW: case RESULT_INVALID:
 268         break;
 269
 270       default:
 271         assert(false);
 272       }
 273
 274       if(square_rank(s) == RANK_3 &&
 275          s != p.whiteKingSquare && s != p.blackKingSquare) {
 276         s += DELTA_N;
 277         switch(Bitbase[compute_index(p.whiteKingSquare, p.blackKingSquare, s,
 278                                      BLACK)]) {
 279         case RESULT_LOSS:
 280           return RESULT_WIN;
 281
 282         case RESULT_UNKNOWN:
 283           unknownFound = true;
 284           break;
 285
 286         case RESULT_DRAW: case RESULT_INVALID:
 287           break;
 288
 289         default:
 290           assert(false);
 291         }
 292       }
 293     }
 294
 295     return unknownFound? RESULT_UNKNOWN : RESULT_DRAW;
 296   }
 297
 298
 299   Result classify_btm(const KPKPosition &p) {
 300
 301     // If one move leads to a position classified as RESULT_DRAW, the result
 302     // of the current position is RESULT_DRAW.  If all moves lead to positions
 303     // classified as RESULT_WIN, the current position is classified as
 304     // RESULT_LOSS.  Otherwise, the current position is classified as
 305     // RESULT_UNKNOWN.
 306
 307     bool unknownFound = false;
 308     Bitboard b;
 309     Square s;
 310
 311     // King moves
 312     b = p.bk_attacks();
 313     while(b) {
 314       s = pop_1st_bit(&b);
 315       switch(Bitbase[compute_index(p.whiteKingSquare, s, p.pawnSquare,
 316                                    WHITE)]) {
 317       case RESULT_DRAW:
 318         return RESULT_DRAW;
 319
 320       case RESULT_UNKNOWN:
 321         unknownFound = true;
 322         break;
 323
 324       case RESULT_WIN: case RESULT_INVALID:
 325         break;
 326
 327       default:
 328         assert(false);
 329       }
 330     }
 331
 332     return unknownFound? RESULT_UNKNOWN : RESULT_LOSS;
 333   }
 334
 335
 336   int compute_index(Square wksq, Square bksq, Square psq, Color stm) {
 337     int p = int(square_file(psq)) + (int(square_rank(psq)) - 1) * 4;
 338     int result = int(stm) + 2*int(bksq) + 128*int(wksq) + 8192*p;
 339     assert(result >= 0 && result < IndexMax);
 340     return result;
 341   }
 342
 343
 344   int compress_result(Result r) {
 345     return (r == RESULT_WIN || r == RESULT_LOSS)? 1 : 0;
 346   }
 347
 348 }