Big trailing whitespace cleanup part 1
[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     bitbase[i] = b;
93   }
94
95   // Release allocated memory:
96   delete [] Bitbase;
97 }
98
99
100 namespace {
101
102   void KPKPosition::from_index(int index) {
103     int s;
104     sideToMove = Color(index % 2);
105     blackKingSquare = Square((index / 2) % 64);
106     whiteKingSquare = Square((index / 128) % 64);
107     s = (index / 8192) % 24;
108     pawnSquare = make_square(File(s % 4), Rank(s / 4 + 1));
109   }
110
111
112   int KPKPosition::to_index() const {
113     return compute_index(whiteKingSquare, blackKingSquare, pawnSquare,
114                          sideToMove);
115   }
116
117
118   bool KPKPosition::is_legal() const {
119     if(whiteKingSquare == pawnSquare || whiteKingSquare == blackKingSquare ||
120        pawnSquare == blackKingSquare)
121       return false;
122     if(sideToMove == WHITE) {
123       if(bit_is_set(this->wk_attacks(), blackKingSquare))
124         return false;
125       if(bit_is_set(this->pawn_attacks(), blackKingSquare))
126         return false;
127     }
128     else {
129       if(bit_is_set(this->bk_attacks(), whiteKingSquare))
130         return false;
131     }
132     return true;
133   }
134
135
136   bool KPKPosition::is_immediate_draw() const {
137     if(sideToMove == BLACK) {
138       Bitboard wka = this->wk_attacks();
139       Bitboard bka = this->bk_attacks();
140
141       // Case 1: Stalemate
142       if((bka & ~(wka | this->pawn_attacks())) == EmptyBoardBB)
143         return true;
144
145       // Case 2: King can capture pawn
146       if(bit_is_set(bka, pawnSquare) && !bit_is_set(wka, pawnSquare))
147         return true;
148     }
149     else {
150       // Case 1: Stalemate
151       if(whiteKingSquare == SQ_A8 && pawnSquare == SQ_A7 &&
152          (blackKingSquare == SQ_C7 || blackKingSquare == SQ_C8))
153         return true;
154     }
155
156     return false;
157   }
158
159
160   bool KPKPosition::is_immediate_win() const {
161     // The position is an immediate win if it is white to move and the white
162     // pawn can be promoted without getting captured:
163     return
164       sideToMove == WHITE &&
165       square_rank(pawnSquare) == RANK_7 &&
166       (square_distance(blackKingSquare, pawnSquare+DELTA_N) > 1 ||
167        bit_is_set(this->wk_attacks(), pawnSquare+DELTA_N));
168   }
169
170
171   Bitboard KPKPosition::wk_attacks() const {
172     return StepAttackBB[WK][whiteKingSquare];
173   }
174
175
176   Bitboard KPKPosition::bk_attacks() const {
177     return StepAttackBB[BK][blackKingSquare];
178   }
179
180
181   Bitboard KPKPosition::pawn_attacks() const {
182     return StepAttackBB[WP][pawnSquare];
183   }
184
185
186   void initialize() {
187     KPKPosition p;
188     for(int i = 0; i < IndexMax; i++) {
189       p.from_index(i);
190       if(!p.is_legal())
191         Bitbase[i] = RESULT_INVALID;
192       else if(p.is_immediate_draw())
193         Bitbase[i] = RESULT_DRAW;
194       else if(p.is_immediate_win())
195         Bitbase[i] = RESULT_WIN;
196       else {
197         Bitbase[i] = RESULT_UNKNOWN;
198         UnknownCount++;
199       }
200     }
201   }
202
203
204   bool next_iteration() {
205     KPKPosition p;
206     int previousUnknownCount = UnknownCount;
207
208     for(int i = 0; i < IndexMax; i++)
209       if(Bitbase[i] == RESULT_UNKNOWN) {
210         p.from_index(i);
211
212         Bitbase[i] = (p.sideToMove == WHITE)? classify_wtm(p) : classify_btm(p);
213
214         if(Bitbase[i] == RESULT_WIN || Bitbase[i] == RESULT_LOSS ||
215            Bitbase[i] == RESULT_DRAW)
216           UnknownCount--;
217       }
218
219     return UnknownCount != previousUnknownCount;
220   }
221
222
223   Result classify_wtm(const KPKPosition &p) {
224
225     // If one move leads to a position classified as RESULT_LOSS, the result
226     // of the current position is RESULT_WIN.  If all moves lead to positions
227     // classified as RESULT_DRAW, the current position is classified as
228     // RESULT_DRAW.  Otherwise, the current position is classified as
229     // RESULT_UNKNOWN.
230
231     bool unknownFound = false;
232     Bitboard b;
233     Square s;
234
235     // King moves
236     b = p.wk_attacks();
237     while(b) {
238       s = pop_1st_bit(&b);
239       switch(Bitbase[compute_index(s, p.blackKingSquare, p.pawnSquare,
240                                    BLACK)]) {
241       case RESULT_LOSS:
242         return RESULT_WIN;
243
244       case RESULT_UNKNOWN:
245         unknownFound = true;
246         break;
247
248       case RESULT_DRAW: case RESULT_INVALID:
249         break;
250
251       default:
252         assert(false);
253       }
254     }
255
256     // Pawn moves
257     if(square_rank(p.pawnSquare) < RANK_7) {
258       s = p.pawnSquare + DELTA_N;
259       switch(Bitbase[compute_index(p.whiteKingSquare, p.blackKingSquare, s,
260                                    BLACK)]) {
261       case RESULT_LOSS:
262         return RESULT_WIN;
263
264       case RESULT_UNKNOWN:
265         unknownFound = true;
266         break;
267
268       case RESULT_DRAW: case RESULT_INVALID:
269         break;
270
271       default:
272         assert(false);
273       }
274
275       if(square_rank(s) == RANK_3 &&
276          s != p.whiteKingSquare && s != p.blackKingSquare) {
277         s += DELTA_N;
278         switch(Bitbase[compute_index(p.whiteKingSquare, p.blackKingSquare, s,
279                                      BLACK)]) {
280         case RESULT_LOSS:
281           return RESULT_WIN;
282
283         case RESULT_UNKNOWN:
284           unknownFound = true;
285           break;
286
287         case RESULT_DRAW: case RESULT_INVALID:
288           break;
289
290         default:
291           assert(false);
292         }
293       }
294     }
295
296     return unknownFound? RESULT_UNKNOWN : RESULT_DRAW;
297   }
298
299
300   Result classify_btm(const KPKPosition &p) {
301
302     // If one move leads to a position classified as RESULT_DRAW, the result
303     // of the current position is RESULT_DRAW.  If all moves lead to positions
304     // classified as RESULT_WIN, the current position is classified as
305     // RESULT_LOSS.  Otherwise, the current position is classified as
306     // RESULT_UNKNOWN.
307
308     bool unknownFound = false;
309     Bitboard b;
310     Square s;
311
312     // King moves
313     b = p.bk_attacks();
314     while(b) {
315       s = pop_1st_bit(&b);
316       switch(Bitbase[compute_index(p.whiteKingSquare, s, p.pawnSquare,
317                                    WHITE)]) {
318       case RESULT_DRAW:
319         return RESULT_DRAW;
320
321       case RESULT_UNKNOWN:
322         unknownFound = true;
323         break;
324
325       case RESULT_WIN: case RESULT_INVALID:
326         break;
327
328       default:
329         assert(false);
330       }
331     }
332
333     return unknownFound? RESULT_UNKNOWN : RESULT_LOSS;
334   }
335
336
337   int compute_index(Square wksq, Square bksq, Square psq, Color stm) {
338     int p = int(square_file(psq)) + (int(square_rank(psq)) - 1) * 4;
339     int result = int(stm) + 2*int(bksq) + 128*int(wksq) + 8192*p;
340     assert(result >= 0 && result < IndexMax);
341     return result;
342   }
343
344
345   int compress_result(Result r) {
346     return (r == RESULT_WIN || r == RESULT_LOSS)? 1 : 0;
347   }
348
349 }