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