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-2010 Marco Costalba, Joona Kiiski, Tord Romstad
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.
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.
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/>.
36 void from_index(int index);
37 bool is_legal() const;
38 bool is_immediate_draw() const;
39 bool is_immediate_win() const;
40 Bitboard wk_attacks() const { return StepAttacksBB[WK][whiteKingSquare]; }
41 Bitboard bk_attacks() const { return StepAttacksBB[BK][blackKingSquare]; }
42 Bitboard pawn_attacks() const { return StepAttacksBB[WP][pawnSquare]; }
44 Square whiteKingSquare, blackKingSquare, pawnSquare;
48 // The possible pawns squares are 24, the first 4 files and ranks from 2 to 7
49 const int IndexMax = 2 * 24 * 64 * 64; // color * wp_sq * wk_sq * bk_sq
51 // Each uint32_t stores results of 32 positions, one per bit
52 uint32_t KPKBitbase[IndexMax / 32];
54 Result classify_wtm(const KPKPosition& pos, const Result bb[]);
55 Result classify_btm(const KPKPosition& pos, const Result bb[]);
56 int compute_index(Square wksq, Square bksq, Square wpsq, Color stm);
60 uint32_t probe_kpk_bitbase(Square wksq, Square wpsq, Square bksq, Color stm) {
62 int index = compute_index(wksq, bksq, wpsq, stm);
64 return KPKBitbase[index / 32] & (1 << (index & 31));
68 void init_kpk_bitbase() {
75 for (int i = 0; i < IndexMax; i++)
78 bb[i] = !pos.is_legal() ? RESULT_INVALID
79 : pos.is_immediate_draw() ? RESULT_DRAW
80 : pos.is_immediate_win() ? RESULT_WIN : RESULT_UNKNOWN;
83 // Iterate until all positions are classified (30 cycles needed)
87 for (int i = 0; i < IndexMax; i++)
88 if (bb[i] == RESULT_UNKNOWN)
92 bb[i] = (pos.sideToMove == WHITE) ? classify_wtm(pos, bb)
93 : classify_btm(pos, bb);
94 if (bb[i] != RESULT_UNKNOWN)
100 // Map 32 position results into one KPKBitbase[] entry
101 for (int i = 0; i < IndexMax / 32; i++)
102 for (int j = 0; j < 32; j++)
103 if (bb[32 * i + j] == RESULT_WIN || bb[32 * i + j] == RESULT_LOSS)
104 KPKBitbase[i] |= (1 << j);
110 // A KPK bitbase index is an integer in [0, IndexMax] range
112 // Information is mapped in this way
114 // bit 0: side to move (WHITE or BLACK)
115 // bit 1- 6: black king square (from SQ_A1 to SQ_H8)
116 // bit 7-12: white king square (from SQ_A1 to SQ_H8)
117 // bit 13-14: white pawn file (from FILE_A to FILE_D)
118 // bit 15-17: white pawn rank - 1 (from RANK_2 - 1 to RANK_7 - 1)
120 int compute_index(Square wksq, Square bksq, Square wpsq, Color stm) {
122 assert(square_file(wpsq) <= FILE_D);
124 int p = int(square_file(wpsq)) + 4 * int(square_rank(wpsq) - 1);
125 int r = int(stm) + 2 * int(bksq) + 128 * int(wksq) + 8192 * p;
127 assert(r >= 0 && r < IndexMax);
132 void KPKPosition::from_index(int index) {
134 int s = (index / 8192) % 24;
136 sideToMove = Color(index % 2);
137 blackKingSquare = Square((index / 2) % 64);
138 whiteKingSquare = Square((index / 128) % 64);
139 pawnSquare = make_square(File(s % 4), Rank(s / 4 + 1));
142 bool KPKPosition::is_legal() const {
144 if ( whiteKingSquare == pawnSquare
145 || whiteKingSquare == blackKingSquare
146 || blackKingSquare == pawnSquare)
149 if (sideToMove == WHITE)
151 if ( bit_is_set(wk_attacks(), blackKingSquare)
152 || bit_is_set(pawn_attacks(), blackKingSquare))
155 else if (bit_is_set(bk_attacks(), whiteKingSquare))
161 bool KPKPosition::is_immediate_draw() const {
163 if (sideToMove == BLACK)
165 Bitboard wka = wk_attacks();
166 Bitboard bka = bk_attacks();
169 if ((bka & ~(wka | pawn_attacks())) == EmptyBoardBB)
172 // Case 2: King can capture pawn
173 if (bit_is_set(bka, pawnSquare) && !bit_is_set(wka, pawnSquare))
178 // Case 1: Stalemate (possible pawn files are only from A to D)
179 if ( whiteKingSquare == SQ_A8
180 && pawnSquare == SQ_A7
181 && (blackKingSquare == SQ_C7 || blackKingSquare == SQ_C8))
187 bool KPKPosition::is_immediate_win() const {
189 // The position is an immediate win if it is white to move and the
190 // white pawn can be promoted without getting captured.
191 return sideToMove == WHITE
192 && square_rank(pawnSquare) == RANK_7
193 && whiteKingSquare != pawnSquare + DELTA_N
194 && ( square_distance(blackKingSquare, pawnSquare + DELTA_N) > 1
195 || bit_is_set(wk_attacks(), pawnSquare + DELTA_N));
198 Result classify_wtm(const KPKPosition& pos, const Result bb[]) {
200 // If one move leads to a position classified as RESULT_LOSS, the result
201 // of the current position is RESULT_WIN. If all moves lead to positions
202 // classified as RESULT_DRAW, the current position is classified RESULT_DRAW
203 // otherwise the current position is classified as RESULT_UNKNOWN.
205 bool unknownFound = false;
211 b = pos.wk_attacks();
215 r = bb[compute_index(s, pos.blackKingSquare, pos.pawnSquare, BLACK)];
217 if (r == RESULT_LOSS)
220 if (r == RESULT_UNKNOWN)
225 if (square_rank(pos.pawnSquare) < RANK_7)
227 s = pos.pawnSquare + DELTA_N;
228 r = bb[compute_index(pos.whiteKingSquare, pos.blackKingSquare, s, BLACK)];
230 if (r == RESULT_LOSS)
233 if (r == RESULT_UNKNOWN)
237 if ( square_rank(s) == RANK_3
238 && s != pos.whiteKingSquare
239 && s != pos.blackKingSquare)
242 r = bb[compute_index(pos.whiteKingSquare, pos.blackKingSquare, s, BLACK)];
244 if (r == RESULT_LOSS)
247 if (r == RESULT_UNKNOWN)
251 return unknownFound ? RESULT_UNKNOWN : RESULT_DRAW;
255 Result classify_btm(const KPKPosition& pos, const Result bb[]) {
257 // If one move leads to a position classified as RESULT_DRAW, the result
258 // of the current position is RESULT_DRAW. If all moves lead to positions
259 // classified as RESULT_WIN, the current position is classified as
260 // RESULT_LOSS. Otherwise, the current position is classified as
263 bool unknownFound = false;
269 b = pos.bk_attacks();
273 r = bb[compute_index(pos.whiteKingSquare, s, pos.pawnSquare, WHITE)];
275 if (r == RESULT_DRAW)
278 if (r == RESULT_UNKNOWN)
281 return unknownFound ? RESULT_UNKNOWN : RESULT_LOSS;