Safe guard some wild and ugly casts
[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 Marco Costalba
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 "bitbase.h"
28 #include "bitboard.h"
29 #include "move.h"
30 #include "square.h"
31
32
33 ////
34 //// Local definitions
35 ////
36
37 namespace {
38
39   enum Result {
40     RESULT_UNKNOWN,
41     RESULT_INVALID,
42     RESULT_WIN,
43     RESULT_LOSS,
44     RESULT_DRAW
45   };
46
47   struct KPKPosition {
48     void from_index(int index);
49     int to_index() const;
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;
56
57     Square whiteKingSquare, blackKingSquare, pawnSquare;
58     Color sideToMove;
59   };
60
61
62   Result *Bitbase;
63   const int IndexMax = 2*24*64*64;
64   int UnknownCount = 0;
65
66   void initialize();
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);
72
73 }
74
75
76 ////
77 //// Functions
78 ////
79
80 void generate_kpk_bitbase(uint8_t bitbase[]) {
81   // Allocate array and initialize:
82   Bitbase = new Result[IndexMax];
83   initialize();
84
85   // Iterate until all positions are classified:
86   while(next_iteration());
87
88   // Compress bitbase into the supplied parameter:
89   int i, j, b;
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;
94   }
95
96   // Release allocated memory:
97   delete [] Bitbase;
98 }
99
100
101 namespace {
102
103   void KPKPosition::from_index(int index) {
104     int s;
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));
110   }
111
112
113   int KPKPosition::to_index() const {
114     return compute_index(whiteKingSquare, blackKingSquare, pawnSquare,
115                          sideToMove);
116   }
117
118
119   bool KPKPosition::is_legal() const {
120     if(whiteKingSquare == pawnSquare || whiteKingSquare == blackKingSquare ||
121        pawnSquare == blackKingSquare)
122       return false;
123     if(sideToMove == WHITE) {
124       if(bit_is_set(this->wk_attacks(), blackKingSquare))
125         return false;
126       if(bit_is_set(this->pawn_attacks(), blackKingSquare))
127         return false;
128     }
129     else {
130       if(bit_is_set(this->bk_attacks(), whiteKingSquare))
131         return false;
132     }
133     return true;
134   }
135
136
137   bool KPKPosition::is_immediate_draw() const {
138     if(sideToMove == BLACK) {
139       Bitboard wka = this->wk_attacks();
140       Bitboard bka = this->bk_attacks();
141
142       // Case 1: Stalemate
143       if((bka & ~(wka | this->pawn_attacks())) == EmptyBoardBB)
144         return true;
145
146       // Case 2: King can capture pawn
147       if(bit_is_set(bka, pawnSquare) && !bit_is_set(wka, pawnSquare))
148         return true;
149     }
150     else {
151       // Case 1: Stalemate
152       if(whiteKingSquare == SQ_A8 && pawnSquare == SQ_A7 &&
153          (blackKingSquare == SQ_C7 || blackKingSquare == SQ_C8))
154         return true;
155     }
156
157     return false;
158   }
159
160
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:
164     return
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));
169   }
170
171
172   Bitboard KPKPosition::wk_attacks() const {
173     return StepAttackBB[WK][whiteKingSquare];
174   }
175
176
177   Bitboard KPKPosition::bk_attacks() const {
178     return StepAttackBB[BK][blackKingSquare];
179   }
180
181
182   Bitboard KPKPosition::pawn_attacks() const {
183     return StepAttackBB[WP][pawnSquare];
184   }
185
186
187   void initialize() {
188     KPKPosition p;
189     for(int i = 0; i < IndexMax; i++) {
190       p.from_index(i);
191       if(!p.is_legal())
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;
197       else {
198         Bitbase[i] = RESULT_UNKNOWN;
199         UnknownCount++;
200       }
201     }
202   }
203
204
205   bool next_iteration() {
206     KPKPosition p;
207     int previousUnknownCount = UnknownCount;
208
209     for(int i = 0; i < IndexMax; i++)
210       if(Bitbase[i] == RESULT_UNKNOWN) {
211         p.from_index(i);
212
213         Bitbase[i] = (p.sideToMove == WHITE)? classify_wtm(p) : classify_btm(p);
214
215         if(Bitbase[i] == RESULT_WIN || Bitbase[i] == RESULT_LOSS ||
216            Bitbase[i] == RESULT_DRAW)
217           UnknownCount--;
218       }
219
220     return UnknownCount != previousUnknownCount;
221   }
222
223
224   Result classify_wtm(const KPKPosition &p) {
225
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
230     // RESULT_UNKNOWN.
231
232     bool unknownFound = false;
233     Bitboard b;
234     Square s;
235
236     // King moves
237     b = p.wk_attacks();
238     while(b) {
239       s = pop_1st_bit(&b);
240       switch(Bitbase[compute_index(s, p.blackKingSquare, p.pawnSquare,
241                                    BLACK)]) {
242       case RESULT_LOSS:
243         return RESULT_WIN;
244
245       case RESULT_UNKNOWN:
246         unknownFound = true;
247         break;
248
249       case RESULT_DRAW: case RESULT_INVALID:
250         break;
251
252       default:
253         assert(false);
254       }
255     }
256
257     // Pawn moves
258     if(square_rank(p.pawnSquare) < RANK_7) {
259       s = p.pawnSquare + DELTA_N;
260       switch(Bitbase[compute_index(p.whiteKingSquare, p.blackKingSquare, s,
261                                    BLACK)]) {
262       case RESULT_LOSS:
263         return RESULT_WIN;
264
265       case RESULT_UNKNOWN:
266         unknownFound = true;
267         break;
268
269       case RESULT_DRAW: case RESULT_INVALID:
270         break;
271
272       default:
273         assert(false);
274       }
275
276       if(square_rank(s) == RANK_3 &&
277          s != p.whiteKingSquare && s != p.blackKingSquare) {
278         s += DELTA_N;
279         switch(Bitbase[compute_index(p.whiteKingSquare, p.blackKingSquare, s,
280                                      BLACK)]) {
281         case RESULT_LOSS:
282           return RESULT_WIN;
283
284         case RESULT_UNKNOWN:
285           unknownFound = true;
286           break;
287
288         case RESULT_DRAW: case RESULT_INVALID:
289           break;
290
291         default:
292           assert(false);
293         }
294       }
295     }
296
297     return unknownFound? RESULT_UNKNOWN : RESULT_DRAW;
298   }
299
300
301   Result classify_btm(const KPKPosition &p) {
302
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
307     // RESULT_UNKNOWN.
308
309     bool unknownFound = false;
310     Bitboard b;
311     Square s;
312
313     // King moves
314     b = p.bk_attacks();
315     while(b) {
316       s = pop_1st_bit(&b);
317       switch(Bitbase[compute_index(p.whiteKingSquare, s, p.pawnSquare,
318                                    WHITE)]) {
319       case RESULT_DRAW:
320         return RESULT_DRAW;
321
322       case RESULT_UNKNOWN:
323         unknownFound = true;
324         break;
325
326       case RESULT_WIN: case RESULT_INVALID:
327         break;
328
329       default:
330         assert(false);
331       }
332     }
333
334     return unknownFound? RESULT_UNKNOWN : RESULT_LOSS;
335   }
336
337
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);
342     return result;
343   }
344
345
346   int compress_result(Result r) {
347     return (r == RESULT_WIN || r == RESULT_LOSS)? 1 : 0;
348   }
349
350 }