Additional cleanup in bitbase.cpp
[stockfish] / 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-2010 Marco Costalba, Joona Kiiski, Tord Romstad
5
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.
10
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.
15
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/>.
18 */
19
20 #include <cassert>
21
22 #include "bitboard.h"
23 #include "types.h"
24
25 namespace {
26
27   enum Result {
28     RESULT_UNKNOWN,
29     RESULT_INVALID,
30     RESULT_WIN,
31     RESULT_LOSS,
32     RESULT_DRAW
33   };
34
35   struct KPKPosition {
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]; }
43
44     Square whiteKingSquare, blackKingSquare, pawnSquare;
45     Color sideToMove;
46   };
47
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
50
51   // Each uint32_t stores results of 32 positions, one per bit
52   uint32_t KPKBitbase[IndexMax / 32];
53
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);
57 }
58
59
60 uint32_t probe_kpk_bitbase(Square wksq, Square wpsq, Square bksq, Color stm) {
61
62   int index = compute_index(wksq, bksq, wpsq, stm);
63
64   return KPKBitbase[index / 32] & (1 << (index & 31));
65 }
66
67
68 void init_kpk_bitbase() {
69
70   Result bb[IndexMax];
71   KPKPosition pos;
72   bool repeat;
73
74   // Initialize table
75   for (int i = 0; i < IndexMax; i++)
76   {
77       pos.from_index(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;
81   }
82
83   // Iterate until all positions are classified (30 cycles needed)
84   do {
85       repeat = false;
86
87       for (int i = 0; i < IndexMax; i++)
88           if (bb[i] == RESULT_UNKNOWN)
89           {
90               pos.from_index(i);
91
92               bb[i] = (pos.sideToMove == WHITE) ? classify_wtm(pos, bb)
93                                                 : classify_btm(pos, bb);
94               if (bb[i] != RESULT_UNKNOWN)
95                   repeat = true;
96           }
97
98   } while (repeat);
99
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);
105 }
106
107
108 namespace {
109
110  // A KPK bitbase index is an integer in [0, IndexMax] range
111  //
112  // Information is mapped in this way
113  //
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)
119
120   int compute_index(Square wksq, Square bksq, Square wpsq, Color stm) {
121
122     assert(square_file(wpsq) <= FILE_D);
123
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;
126
127     assert(r >= 0 && r < IndexMax);
128
129     return r;
130   }
131
132   void KPKPosition::from_index(int index) {
133
134     int s = (index / 8192) % 24;
135
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));
140   }
141
142   bool KPKPosition::is_legal() const {
143
144     if (   whiteKingSquare == pawnSquare
145         || whiteKingSquare == blackKingSquare
146         || blackKingSquare == pawnSquare)
147         return false;
148
149     if (sideToMove == WHITE)
150     {
151         if (   bit_is_set(wk_attacks(), blackKingSquare)
152             || bit_is_set(pawn_attacks(), blackKingSquare))
153             return false;
154     }
155     else if (bit_is_set(bk_attacks(), whiteKingSquare))
156         return false;
157
158     return true;
159   }
160
161   bool KPKPosition::is_immediate_draw() const {
162
163     if (sideToMove == BLACK)
164     {
165         Bitboard wka = wk_attacks();
166         Bitboard bka = bk_attacks();
167
168         // Case 1: Stalemate
169         if ((bka & ~(wka | pawn_attacks())) == EmptyBoardBB)
170             return true;
171
172         // Case 2: King can capture pawn
173         if (bit_is_set(bka, pawnSquare) && !bit_is_set(wka, pawnSquare))
174             return true;
175     }
176     else
177     {
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))
182             return true;
183     }
184     return false;
185   }
186
187   bool KPKPosition::is_immediate_win() const {
188
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));
196   }
197
198   Result classify_wtm(const KPKPosition& pos, const Result bb[]) {
199
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.
204
205     bool unknownFound = false;
206     Bitboard b;
207     Square s;
208     Result r;
209
210     // King moves
211     b = pos.wk_attacks();
212     while (b)
213     {
214         s = pop_1st_bit(&b);
215         r = bb[compute_index(s, pos.blackKingSquare, pos.pawnSquare, BLACK)];
216
217         if (r == RESULT_LOSS)
218             return RESULT_WIN;
219
220         if (r == RESULT_UNKNOWN)
221             unknownFound = true;
222     }
223
224     // Pawn moves
225     if (square_rank(pos.pawnSquare) < RANK_7)
226     {
227         s = pos.pawnSquare + DELTA_N;
228         r = bb[compute_index(pos.whiteKingSquare, pos.blackKingSquare, s, BLACK)];
229
230         if (r == RESULT_LOSS)
231             return RESULT_WIN;
232
233         if (r == RESULT_UNKNOWN)
234             unknownFound = true;
235
236         // Double pawn push
237         if (   square_rank(s) == RANK_3
238             && s != pos.whiteKingSquare
239             && s != pos.blackKingSquare)
240         {
241             s += DELTA_N;
242             r = bb[compute_index(pos.whiteKingSquare, pos.blackKingSquare, s, BLACK)];
243
244             if (r == RESULT_LOSS)
245                 return RESULT_WIN;
246
247             if (r == RESULT_UNKNOWN)
248                 unknownFound = true;
249         }
250     }
251     return unknownFound ? RESULT_UNKNOWN : RESULT_DRAW;
252   }
253
254
255   Result classify_btm(const KPKPosition& pos, const Result bb[]) {
256
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
261     // RESULT_UNKNOWN.
262
263     bool unknownFound = false;
264     Bitboard b;
265     Square s;
266     Result r;
267
268     // King moves
269     b = pos.bk_attacks();
270     while (b)
271     {
272         s = pop_1st_bit(&b);
273         r = bb[compute_index(pos.whiteKingSquare, s, pos.pawnSquare, WHITE)];
274
275         if (r == RESULT_DRAW)
276             return RESULT_DRAW;
277
278         if (r == RESULT_UNKNOWN)
279             unknownFound = true;
280     }
281     return unknownFound ? RESULT_UNKNOWN : RESULT_LOSS;
282   }
283
284 }