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-2015 Marco Costalba, Joona Kiiski, Tord Romstad
   5   Copyright (C) 2015-2017 Marco Costalba, Joona Kiiski, Gary Linscott, Tord Romstad
   6
   7   Stockfish is free software: you can redistribute it and/or modify
   8   it under the terms of the GNU General Public License as published by
   9   the Free Software Foundation, either version 3 of the License, or
  10   (at your option) any later version.
  11
  12   Stockfish is distributed in the hope that it will be useful,
  13   but WITHOUT ANY WARRANTY; without even the implied warranty of
  14   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15   GNU General Public License for more details.
  16
  17   You should have received a copy of the GNU General Public License
  18   along with this program.  If not, see <http://www.gnu.org/licenses/>.
  19 */
  20
  21 #include <algorithm>
  22 #include <cassert>
  23 #include <numeric>
  24 #include <vector>
  25
  26 #include "bitboard.h"
  27 #include "types.h"
  28
  29 namespace {
  30
  31   // There are 24 possible pawn squares: the first 4 files and ranks from 2 to 7
  32   const unsigned MAX_INDEX = 2*24*64*64; // stm * psq * wksq * bksq = 196608
  33
  34   // Each uint32_t stores results of 32 positions, one per bit
  35   uint32_t KPKBitbase[MAX_INDEX / 32];
  36
  37   // A KPK bitbase index is an integer in [0, IndexMax] range
  38   //
  39   // Information is mapped in a way that minimizes the number of iterations:
  40   //
  41   // bit  0- 5: white king square (from SQ_A1 to SQ_H8)
  42   // bit  6-11: black king square (from SQ_A1 to SQ_H8)
  43   // bit    12: side to move (WHITE or BLACK)
  44   // bit 13-14: white pawn file (from FILE_A to FILE_D)
  45   // bit 15-17: white pawn RANK_7 - rank (from RANK_7 - RANK_7 to RANK_7 - RANK_2)
  46   unsigned index(Color us, Square bksq, Square wksq, Square psq) {
  47     return wksq | (bksq << 6) | (us << 12) | (file_of(psq) << 13) | ((RANK_7 - rank_of(psq)) << 15);
  48   }
  49
  50   enum Result {
  51     INVALID = 0,
  52     UNKNOWN = 1,
  53     DRAW    = 2,
  54     WIN     = 4
  55   };
  56
  57   Result& operator|=(Result& r, Result v) { return r = Result(r | v); }
  58
  59   struct KPKPosition {
  60     KPKPosition() = default;
  61     explicit KPKPosition(unsigned idx);
  62     operator Result() const { return result; }
  63     Result classify(const std::vector<KPKPosition>& db)
  64     { return us == WHITE ? classify<WHITE>(db) : classify<BLACK>(db); }
  65
  66     template<Color Us> Result classify(const std::vector<KPKPosition>& db);
  67
  68     Color us;
  69     Square ksq[COLOR_NB], psq;
  70     Result result;
  71   };
  72
  73 } // namespace
  74
  75
  76 bool Bitbases::probe(Square wksq, Square wpsq, Square bksq, Color us) {
  77
  78   assert(file_of(wpsq) <= FILE_D);
  79
  80   unsigned idx = index(us, bksq, wksq, wpsq);
  81   return KPKBitbase[idx / 32] & (1 << (idx & 0x1F));
  82 }
  83
  84
  85 void Bitbases::init() {
  86
  87   std::vector<KPKPosition> db(MAX_INDEX);
  88   unsigned idx, repeat = 1;
  89
  90   // Initialize db with known win / draw positions
  91   for (idx = 0; idx < MAX_INDEX; ++idx)
  92       db[idx] = KPKPosition(idx);
  93
  94   // Iterate through the positions until none of the unknown positions can be
  95   // changed to either wins or draws (15 cycles needed).
  96   while (repeat)
  97       for (repeat = idx = 0; idx < MAX_INDEX; ++idx)
  98           repeat |= (db[idx] == UNKNOWN && db[idx].classify(db) != UNKNOWN);
  99
 100   // Map 32 results into one KPKBitbase[] entry
 101   for (idx = 0; idx < MAX_INDEX; ++idx)
 102       if (db[idx] == WIN)
 103           KPKBitbase[idx / 32] |= 1 << (idx & 0x1F);
 104 }
 105
 106
 107 namespace {
 108
 109   KPKPosition::KPKPosition(unsigned idx) {
 110
 111     ksq[WHITE] = Square((idx >>  0) & 0x3F);
 112     ksq[BLACK] = Square((idx >>  6) & 0x3F);
 113     us         = Color ((idx >> 12) & 0x01);
 114     psq        = make_square(File((idx >> 13) & 0x3), RANK_7 - Rank((idx >> 15) & 0x7));
 115
 116     // Check if two pieces are on the same square or if a king can be captured
 117     if (   distance(ksq[WHITE], ksq[BLACK]) <= 1
 118         || ksq[WHITE] == psq
 119         || ksq[BLACK] == psq
 120         || (us == WHITE && (StepAttacksBB[PAWN][psq] & ksq[BLACK])))
 121         result = INVALID;
 122
 123     // Immediate win if a pawn can be promoted without getting captured
 124     else if (   us == WHITE
 125              && rank_of(psq) == RANK_7
 126              && ksq[us] != psq + NORTH
 127              && (    distance(ksq[~us], psq + NORTH) > 1
 128                  || (StepAttacksBB[KING][ksq[us]] & (psq + NORTH))))
 129         result = WIN;
 130
 131     // Immediate draw if it is a stalemate or a king captures undefended pawn
 132     else if (   us == BLACK
 133              && (  !(StepAttacksBB[KING][ksq[us]] & ~(StepAttacksBB[KING][ksq[~us]] | StepAttacksBB[PAWN][psq]))
 134                  || (StepAttacksBB[KING][ksq[us]] & psq & ~StepAttacksBB[KING][ksq[~us]])))
 135         result = DRAW;
 136
 137     // Position will be classified later
 138     else
 139         result = UNKNOWN;
 140   }
 141
 142   template<Color Us>
 143   Result KPKPosition::classify(const std::vector<KPKPosition>& db) {
 144
 145     // White to move: If one move leads to a position classified as WIN, the result
 146     // of the current position is WIN. If all moves lead to positions classified
 147     // as DRAW, the current position is classified as DRAW, otherwise the current
 148     // position is classified as UNKNOWN.
 149     //
 150     // Black to move: If one move leads to a position classified as DRAW, the result
 151     // of the current position is DRAW. If all moves lead to positions classified
 152     // as WIN, the position is classified as WIN, otherwise the current position is
 153     // classified as UNKNOWN.
 154
 155     const Color  Them = (Us == WHITE ? BLACK : WHITE);
 156     const Result Good = (Us == WHITE ? WIN   : DRAW);
 157     const Result Bad  = (Us == WHITE ? DRAW  : WIN);
 158
 159     Result r = INVALID;
 160     Bitboard b = StepAttacksBB[KING][ksq[Us]];
 161
 162     while (b)
 163         r |= Us == WHITE ? db[index(Them, ksq[Them]  , pop_lsb(&b), psq)]
 164                          : db[index(Them, pop_lsb(&b), ksq[Them]  , psq)];
 165
 166     if (Us == WHITE)
 167     {
 168         if (rank_of(psq) < RANK_7)      // Single push
 169             r |= db[index(Them, ksq[Them], ksq[Us], psq + NORTH)];
 170
 171         if (   rank_of(psq) == RANK_2   // Double push
 172             && psq + NORTH != ksq[Us]
 173             && psq + NORTH != ksq[Them])
 174             r |= db[index(Them, ksq[Them], ksq[Us], psq + NORTH + NORTH)];
 175     }
 176
 177     return result = r & Good  ? Good  : r & UNKNOWN ? UNKNOWN : Bad;
 178   }
 179
 180 } // namespace