Another round of bitboard.cpp cleanups
[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
21 ////
22 //// Includes
23 ////
24
25 #include <cassert>
26
27 #include "bitboard.h"
28 #include "square.h"
29
30
31 ////
32 //// Local definitions
33 ////
34
35 namespace {
36
37   enum Result {
38     RESULT_UNKNOWN,
39     RESULT_INVALID,
40     RESULT_WIN,
41     RESULT_LOSS,
42     RESULT_DRAW
43   };
44
45   struct KPKPosition {
46     void from_index(int index);
47     bool is_legal() const;
48     bool is_immediate_draw() const;
49     bool is_immediate_win() const;
50     Bitboard wk_attacks()   const { return NonSlidingAttacksBB[WK][whiteKingSquare]; }
51     Bitboard bk_attacks()   const { return NonSlidingAttacksBB[BK][blackKingSquare]; }
52     Bitboard pawn_attacks() const { return NonSlidingAttacksBB[WP][pawnSquare]; }
53
54     Square whiteKingSquare, blackKingSquare, pawnSquare;
55     Color sideToMove;
56   };
57
58   const int IndexMax = 2 * 24 * 64 * 64;
59
60   Result classify_wtm(const KPKPosition& pos, const Result bb[]);
61   Result classify_btm(const KPKPosition& pos, const Result bb[]);
62   int compute_index(Square wksq, Square bksq, Square psq, Color stm);
63 }
64
65
66 ////
67 //// Functions
68 ////
69
70 void generate_kpk_bitbase(uint8_t bitbase[]) {
71
72   bool repeat;
73   int i, j, b;
74   KPKPosition pos;
75   Result bb[IndexMax];
76
77   // Initialize table
78   for (i = 0; i < IndexMax; i++)
79   {
80       pos.from_index(i);
81       bb[i] = !pos.is_legal()          ? RESULT_INVALID
82              : pos.is_immediate_draw() ? RESULT_DRAW
83              : pos.is_immediate_win()  ? RESULT_WIN : RESULT_UNKNOWN;
84   }
85
86   // Iterate until all positions are classified (30 cycles needed)
87   do {
88       repeat = false;
89
90       for (i = 0; i < IndexMax; i++)
91           if (bb[i] == RESULT_UNKNOWN)
92           {
93               pos.from_index(i);
94
95               bb[i] = (pos.sideToMove == WHITE) ? classify_wtm(pos, bb)
96                                                 : classify_btm(pos, bb);
97               if (bb[i] != RESULT_UNKNOWN)
98                   repeat = true;
99           }
100
101   } while (repeat);
102
103   // Compress result and map into supplied bitbase parameter
104   for (i = 0; i < 24576; i++)
105   {
106       b = 0;
107       for (j = 0; j < 8; j++)
108           if (bb[8*i+j] == RESULT_WIN || bb[8*i+j] == RESULT_LOSS)
109               b |= (1 << j);
110
111       bitbase[i] = (uint8_t)b;
112   }
113 }
114
115
116 namespace {
117
118   int compute_index(Square wksq, Square bksq, Square psq, Color stm) {
119
120       int p = int(square_file(psq)) + (int(square_rank(psq)) - 1) * 4;
121       int r = int(stm) + 2 * int(bksq) + 128 * int(wksq) + 8192 * p;
122
123       assert(r >= 0 && r < IndexMax);
124
125       return r;
126   }
127
128   void KPKPosition::from_index(int index) {
129
130     int s = (index / 8192) % 24;
131
132     sideToMove = Color(index % 2);
133     blackKingSquare = Square((index / 2) % 64);
134     whiteKingSquare = Square((index / 128) % 64);
135     pawnSquare = make_square(File(s % 4), Rank(s / 4 + 1));
136   }
137
138   bool KPKPosition::is_legal() const {
139
140     if (   whiteKingSquare == pawnSquare
141         || whiteKingSquare == blackKingSquare
142         || pawnSquare == blackKingSquare)
143         return false;
144
145     if (sideToMove == WHITE)
146     {
147         if (   bit_is_set(wk_attacks(), blackKingSquare)
148             || bit_is_set(pawn_attacks(), blackKingSquare))
149             return false;
150     }
151     else if (bit_is_set(bk_attacks(), whiteKingSquare))
152         return false;
153
154     return true;
155   }
156
157   bool KPKPosition::is_immediate_draw() const {
158
159     if (sideToMove == BLACK)
160     {
161         Bitboard wka = wk_attacks();
162         Bitboard bka = bk_attacks();
163
164         // Case 1: Stalemate
165         if ((bka & ~(wka | pawn_attacks())) == EmptyBoardBB)
166             return true;
167
168         // Case 2: King can capture pawn
169         if (bit_is_set(bka, pawnSquare) && !bit_is_set(wka, pawnSquare))
170             return true;
171     }
172     else
173     {
174         // Case 1: Stalemate
175         if (   whiteKingSquare == SQ_A8
176             && pawnSquare == SQ_A7
177             && (blackKingSquare == SQ_C7 || blackKingSquare == SQ_C8))
178             return true;
179     }
180     return false;
181   }
182
183   bool KPKPosition::is_immediate_win() const {
184
185     // The position is an immediate win if it is white to move and the
186     // white pawn can be promoted without getting captured.
187     return   sideToMove == WHITE
188           && square_rank(pawnSquare) == RANK_7
189           && (   square_distance(blackKingSquare, pawnSquare + DELTA_N) > 1
190               || bit_is_set(wk_attacks(), pawnSquare + DELTA_N));
191   }
192
193   Result classify_wtm(const KPKPosition& pos, const Result bb[]) {
194
195     // If one move leads to a position classified as RESULT_LOSS, the result
196     // of the current position is RESULT_WIN. If all moves lead to positions
197     // classified as RESULT_DRAW, the current position is classified RESULT_DRAW
198     // otherwise the current position is classified as RESULT_UNKNOWN.
199
200     bool unknownFound = false;
201     Bitboard b;
202     Square s;
203     int idx;
204
205     // King moves
206     b = pos.wk_attacks();
207     while (b)
208     {
209         s = pop_1st_bit(&b);
210         idx = compute_index(s, pos.blackKingSquare, pos.pawnSquare, BLACK);
211
212         switch (bb[idx]) {
213
214         case RESULT_LOSS:
215             return RESULT_WIN;
216
217         case RESULT_UNKNOWN:
218             unknownFound = true;
219
220         case RESULT_DRAW:
221         case RESULT_INVALID:
222              break;
223
224          default:
225              assert(false);
226         }
227     }
228
229     // Pawn moves
230     if (square_rank(pos.pawnSquare) < RANK_7)
231     {
232         s = pos.pawnSquare + DELTA_N;
233         idx = compute_index(pos.whiteKingSquare, pos.blackKingSquare, s, BLACK);
234
235         switch (bb[idx]) {
236
237         case RESULT_LOSS:
238             return RESULT_WIN;
239
240         case RESULT_UNKNOWN:
241             unknownFound = true;
242
243         case RESULT_DRAW:
244         case RESULT_INVALID:
245             break;
246
247         default:
248             assert(false);
249         }
250
251         // Double pawn push
252         if (   square_rank(s) == RANK_3
253             && s != pos.whiteKingSquare
254             && s != pos.blackKingSquare)
255         {
256             s += DELTA_N;
257             idx = compute_index(pos.whiteKingSquare, pos.blackKingSquare, s, BLACK);
258
259             switch (bb[idx]) {
260
261             case RESULT_LOSS:
262                 return RESULT_WIN;
263
264             case RESULT_UNKNOWN:
265                 unknownFound = true;
266
267             case RESULT_DRAW:
268             case RESULT_INVALID:
269                 break;
270
271             default:
272                 assert(false);
273             }
274         }
275     }
276     return unknownFound ? RESULT_UNKNOWN : RESULT_DRAW;
277   }
278
279
280   Result classify_btm(const KPKPosition& pos, const Result bb[]) {
281
282     // If one move leads to a position classified as RESULT_DRAW, the result
283     // of the current position is RESULT_DRAW. If all moves lead to positions
284     // classified as RESULT_WIN, the current position is classified as
285     // RESULT_LOSS. Otherwise, the current position is classified as
286     // RESULT_UNKNOWN.
287
288     bool unknownFound = false;
289     Bitboard b;
290     Square s;
291     int idx;
292
293     // King moves
294     b = pos.bk_attacks();
295     while (b)
296     {
297         s = pop_1st_bit(&b);
298         idx = compute_index(pos.whiteKingSquare, s, pos.pawnSquare, WHITE);
299
300         switch (bb[idx]) {
301
302         case RESULT_DRAW:
303             return RESULT_DRAW;
304
305         case RESULT_UNKNOWN:
306             unknownFound = true;
307
308         case RESULT_WIN:
309         case RESULT_INVALID:
310             break;
311
312         default:
313             assert(false);
314         }
315     }
316     return unknownFound ? RESULT_UNKNOWN : RESULT_LOSS;
317   }
318
319 }