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-2012 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/>.
35 Result classify_knowns(int index);
36 Result classify(int index, Result db[]);
39 void from_index(int index);
40 Result classify_white(const Result db[]);
41 Result classify_black(const Result db[]);
42 Bitboard wk_attacks() const { return StepAttacksBB[W_KING][whiteKingSquare]; }
43 Bitboard bk_attacks() const { return StepAttacksBB[B_KING][blackKingSquare]; }
44 Bitboard pawn_attacks() const { return StepAttacksBB[W_PAWN][pawnSquare]; }
46 Square whiteKingSquare, blackKingSquare, pawnSquare;
50 // The possible pawns squares are 24, the first 4 files and ranks from 2 to 7
51 const int IndexMax = 2 * 24 * 64 * 64; // color * wp_sq * wk_sq * bk_sq = 196608
53 // Each uint32_t stores results of 32 positions, one per bit
54 uint32_t KPKBitbase[IndexMax / 32];
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 kpk_bitbase_init() {
72 int index, bit, repeat = 1;
75 for (index = 0; index < IndexMax; index++)
76 db[index] = pos.classify_knowns(index);
78 // Iterate until all positions are classified (30 cycles needed)
80 for (repeat = index = 0; index < IndexMax; index++)
81 if ( db[index] == RESULT_UNKNOWN
82 && pos.classify(index, db) != RESULT_UNKNOWN)
85 // Map 32 position results into one KPKBitbase[] entry
86 for (index = 0; index < IndexMax / 32; index++)
87 for (bit = 0; bit < 32; bit++)
88 if (db[32 * index + bit] == RESULT_WIN)
89 KPKBitbase[index] |= (1 << bit);
95 // A KPK bitbase index is an integer in [0, IndexMax] range
97 // Information is mapped in this way
99 // bit 0: side to move (WHITE or BLACK)
100 // bit 1- 6: black king square (from SQ_A1 to SQ_H8)
101 // bit 7-12: white king square (from SQ_A1 to SQ_H8)
102 // bit 13-14: white pawn file (from FILE_A to FILE_D)
103 // bit 15-17: white pawn rank - 1 (from RANK_2 - 1 to RANK_7 - 1)
105 int compute_index(Square wksq, Square bksq, Square wpsq, Color stm) {
107 assert(file_of(wpsq) <= FILE_D);
109 int p = file_of(wpsq) + 4 * (rank_of(wpsq) - 1);
110 int r = stm + 2 * bksq + 128 * wksq + 8192 * p;
112 assert(r >= 0 && r < IndexMax);
117 void KPKPosition::from_index(int index) {
120 sideToMove = Color(index & 1);
121 blackKingSquare = Square((index >> 1) & 63);
122 whiteKingSquare = Square((index >> 7) & 63);
123 pawnSquare = make_square(File(s & 3), Rank((s >> 2) + 1));
126 Result KPKPosition::classify_knowns(int index) {
130 // Check if two pieces are on the same square
131 if ( whiteKingSquare == pawnSquare
132 || whiteKingSquare == blackKingSquare
133 || blackKingSquare == pawnSquare)
134 return RESULT_INVALID;
136 // Check if a king can be captured
137 if ( bit_is_set(wk_attacks(), blackKingSquare)
138 || (bit_is_set(pawn_attacks(), blackKingSquare) && sideToMove == WHITE))
139 return RESULT_INVALID;
141 // The position is an immediate win if it is white to move and the
142 // white pawn can be promoted without getting captured.
143 if ( rank_of(pawnSquare) == RANK_7
144 && sideToMove == WHITE
145 && whiteKingSquare != pawnSquare + DELTA_N
146 && ( square_distance(blackKingSquare, pawnSquare + DELTA_N) > 1
147 || bit_is_set(wk_attacks(), pawnSquare + DELTA_N)))
150 // Check for known draw positions
153 if ( sideToMove == BLACK
154 && !(bk_attacks() & ~(wk_attacks() | pawn_attacks())))
157 // Case 2: King can capture pawn
158 if ( sideToMove == BLACK
159 && bit_is_set(bk_attacks(), pawnSquare) && !bit_is_set(wk_attacks(), pawnSquare))
162 // Case 3: Black king in front of white pawn
163 if ( blackKingSquare == pawnSquare + DELTA_N
164 && rank_of(pawnSquare) < RANK_7)
167 // Case 4: White king in front of pawn and black has opposition
168 if ( whiteKingSquare == pawnSquare + DELTA_N
169 && blackKingSquare == pawnSquare + DELTA_N + DELTA_N + DELTA_N
170 && rank_of(pawnSquare) < RANK_5
171 && sideToMove == WHITE)
174 // Case 5: Stalemate with rook pawn
175 if ( blackKingSquare == SQ_A8
176 && file_of(pawnSquare) == FILE_A)
179 return RESULT_UNKNOWN;
182 Result KPKPosition::classify(int index, Result db[]) {
185 db[index] = (sideToMove == WHITE ? classify_white(db) : classify_black(db));
189 Result KPKPosition::classify_white(const Result db[]) {
191 // If one move leads to a position classified as RESULT_WIN, the result
192 // of the current position is RESULT_WIN. If all moves lead to positions
193 // classified as RESULT_DRAW, the current position is classified RESULT_DRAW
194 // otherwise the current position is classified as RESULT_UNKNOWN.
196 bool unknownFound = false;
206 r = db[compute_index(s, blackKingSquare, pawnSquare, BLACK)];
211 if (r == RESULT_UNKNOWN)
216 if (rank_of(pawnSquare) < RANK_7)
218 s = pawnSquare + DELTA_N;
219 r = db[compute_index(whiteKingSquare, blackKingSquare, s, BLACK)];
224 if (r == RESULT_UNKNOWN)
228 if (rank_of(s) == RANK_3 && r != RESULT_INVALID)
231 r = db[compute_index(whiteKingSquare, blackKingSquare, s, BLACK)];
236 if (r == RESULT_UNKNOWN)
240 return unknownFound ? RESULT_UNKNOWN : RESULT_DRAW;
243 Result KPKPosition::classify_black(const Result db[]) {
245 // If one move leads to a position classified as RESULT_DRAW, the result
246 // of the current position is RESULT_DRAW. If all moves lead to positions
247 // classified as RESULT_WIN, the position is classified as RESULT_WIN.
248 // Otherwise, the current position is classified as RESULT_UNKNOWN.
250 bool unknownFound = false;
260 r = db[compute_index(whiteKingSquare, s, pawnSquare, WHITE)];
262 if (r == RESULT_DRAW)
265 if (r == RESULT_UNKNOWN)
268 return unknownFound ? RESULT_UNKNOWN : RESULT_WIN;