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/>.
34 //// Local definitions
48 void from_index(int index);
50 bool is_legal() const;
51 bool is_immediate_draw() const;
52 bool is_immediate_win() const;
53 Bitboard wk_attacks() const;
54 Bitboard bk_attacks() const;
55 Bitboard pawn_attacks() const;
57 Square whiteKingSquare, blackKingSquare, pawnSquare;
63 const int IndexMax = 2*24*64*64;
67 bool next_iteration();
68 Result classify_wtm(const KPKPosition &p);
69 Result classify_btm(const KPKPosition &p);
70 int compute_index(Square wksq, Square bksq, Square psq, Color stm);
71 int compress_result(Result r);
80 void generate_kpk_bitbase(uint8_t bitbase[]) {
81 // Allocate array and initialize:
82 Bitbase = new Result[IndexMax];
85 // Iterate until all positions are classified:
86 while(next_iteration());
88 // Compress bitbase into the supplied parameter:
90 for(i = 0; i < 24576; i++) {
91 for(b = 0, j = 0; j < 8; b |= (compress_result(Bitbase[8*i+j]) << j), j++);
92 assert(b == int(uint8_t(b)));
93 bitbase[i] = (uint8_t)b;
96 // Release allocated memory:
103 void KPKPosition::from_index(int index) {
105 sideToMove = Color(index % 2);
106 blackKingSquare = Square((index / 2) % 64);
107 whiteKingSquare = Square((index / 128) % 64);
108 s = (index / 8192) % 24;
109 pawnSquare = make_square(File(s % 4), Rank(s / 4 + 1));
113 int KPKPosition::to_index() const {
114 return compute_index(whiteKingSquare, blackKingSquare, pawnSquare,
119 bool KPKPosition::is_legal() const {
120 if(whiteKingSquare == pawnSquare || whiteKingSquare == blackKingSquare ||
121 pawnSquare == blackKingSquare)
123 if(sideToMove == WHITE) {
124 if(bit_is_set(this->wk_attacks(), blackKingSquare))
126 if(bit_is_set(this->pawn_attacks(), blackKingSquare))
130 if(bit_is_set(this->bk_attacks(), whiteKingSquare))
137 bool KPKPosition::is_immediate_draw() const {
138 if(sideToMove == BLACK) {
139 Bitboard wka = this->wk_attacks();
140 Bitboard bka = this->bk_attacks();
143 if((bka & ~(wka | this->pawn_attacks())) == EmptyBoardBB)
146 // Case 2: King can capture pawn
147 if(bit_is_set(bka, pawnSquare) && !bit_is_set(wka, pawnSquare))
152 if(whiteKingSquare == SQ_A8 && pawnSquare == SQ_A7 &&
153 (blackKingSquare == SQ_C7 || blackKingSquare == SQ_C8))
161 bool KPKPosition::is_immediate_win() const {
162 // The position is an immediate win if it is white to move and the white
163 // pawn can be promoted without getting captured:
165 sideToMove == WHITE &&
166 square_rank(pawnSquare) == RANK_7 &&
167 (square_distance(blackKingSquare, pawnSquare+DELTA_N) > 1 ||
168 bit_is_set(this->wk_attacks(), pawnSquare+DELTA_N));
172 Bitboard KPKPosition::wk_attacks() const {
173 return StepAttackBB[WK][whiteKingSquare];
177 Bitboard KPKPosition::bk_attacks() const {
178 return StepAttackBB[BK][blackKingSquare];
182 Bitboard KPKPosition::pawn_attacks() const {
183 return StepAttackBB[WP][pawnSquare];
189 for(int i = 0; i < IndexMax; i++) {
192 Bitbase[i] = RESULT_INVALID;
193 else if(p.is_immediate_draw())
194 Bitbase[i] = RESULT_DRAW;
195 else if(p.is_immediate_win())
196 Bitbase[i] = RESULT_WIN;
198 Bitbase[i] = RESULT_UNKNOWN;
205 bool next_iteration() {
207 int previousUnknownCount = UnknownCount;
209 for(int i = 0; i < IndexMax; i++)
210 if(Bitbase[i] == RESULT_UNKNOWN) {
213 Bitbase[i] = (p.sideToMove == WHITE)? classify_wtm(p) : classify_btm(p);
215 if(Bitbase[i] == RESULT_WIN || Bitbase[i] == RESULT_LOSS ||
216 Bitbase[i] == RESULT_DRAW)
220 return UnknownCount != previousUnknownCount;
224 Result classify_wtm(const KPKPosition &p) {
226 // If one move leads to a position classified as RESULT_LOSS, the result
227 // of the current position is RESULT_WIN. If all moves lead to positions
228 // classified as RESULT_DRAW, the current position is classified as
229 // RESULT_DRAW. Otherwise, the current position is classified as
232 bool unknownFound = false;
240 switch(Bitbase[compute_index(s, p.blackKingSquare, p.pawnSquare,
249 case RESULT_DRAW: case RESULT_INVALID:
258 if(square_rank(p.pawnSquare) < RANK_7) {
259 s = p.pawnSquare + DELTA_N;
260 switch(Bitbase[compute_index(p.whiteKingSquare, p.blackKingSquare, s,
269 case RESULT_DRAW: case RESULT_INVALID:
276 if(square_rank(s) == RANK_3 &&
277 s != p.whiteKingSquare && s != p.blackKingSquare) {
279 switch(Bitbase[compute_index(p.whiteKingSquare, p.blackKingSquare, s,
288 case RESULT_DRAW: case RESULT_INVALID:
297 return unknownFound? RESULT_UNKNOWN : RESULT_DRAW;
301 Result classify_btm(const KPKPosition &p) {
303 // If one move leads to a position classified as RESULT_DRAW, the result
304 // of the current position is RESULT_DRAW. If all moves lead to positions
305 // classified as RESULT_WIN, the current position is classified as
306 // RESULT_LOSS. Otherwise, the current position is classified as
309 bool unknownFound = false;
317 switch(Bitbase[compute_index(p.whiteKingSquare, s, p.pawnSquare,
326 case RESULT_WIN: case RESULT_INVALID:
334 return unknownFound? RESULT_UNKNOWN : RESULT_LOSS;
338 int compute_index(Square wksq, Square bksq, Square psq, Color stm) {
339 int p = int(square_file(psq)) + (int(square_rank(psq)) - 1) * 4;
340 int result = int(stm) + 2*int(bksq) + 128*int(wksq) + 8192*p;
341 assert(result >= 0 && result < IndexMax);
346 int compress_result(Result r) {
347 return (r == RESULT_WIN || r == RESULT_LOSS)? 1 : 0;