Initial import of Glaurung 2.1
[stockfish] / src / bitbase.cpp
1 /*
2   Glaurung, a UCI chess playing engine.
3   Copyright (C) 2004-2008 Tord Romstad
4
5   Glaurung is free software: you can redistribute it and/or modify
6   it under the terms of the GNU General Public License as published by
7   the Free Software Foundation, either version 3 of the License, or
8   (at your option) any later version.
9   
10   Glaurung is distributed in the hope that it will be useful,
11   but WITHOUT ANY WARRANTY; without even the implied warranty of
12   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
13   GNU General Public License for more details.
14   
15   You should have received a copy of the GNU General Public License
16   along with this program.  If not, see <http://www.gnu.org/licenses/>.
17 */
18
19
20 ////
21 //// Includes
22 ////
23
24 #include <cassert>
25
26 #include "bitbase.h"
27 #include "bitboard.h"
28 #include "move.h"
29 #include "square.h"
30
31
32 ////
33 //// Local definitions
34 ////
35
36 namespace {
37
38   enum Result {
39     RESULT_UNKNOWN,
40     RESULT_INVALID,
41     RESULT_WIN,
42     RESULT_LOSS,
43     RESULT_DRAW
44   };
45
46   struct KPKPosition {
47     void from_index(int index);
48     int to_index() const;
49     bool is_legal() const;
50     bool is_immediate_draw() const;
51     bool is_immediate_win() const;
52     Bitboard wk_attacks() const;
53     Bitboard bk_attacks() const;
54     Bitboard pawn_attacks() const;
55     
56     Square whiteKingSquare, blackKingSquare, pawnSquare;
57     Color sideToMove;
58   };
59     
60
61   Result *Bitbase;
62   const int IndexMax = 2*24*64*64;
63   int UnknownCount = 0;
64
65   void initialize();
66   bool next_iteration();
67   Result classify_wtm(const KPKPosition &p);
68   Result classify_btm(const KPKPosition &p);
69   int compute_index(Square wksq, Square bksq, Square psq, Color stm);
70   int compress_result(Result r);
71   
72 }
73
74
75 ////
76 //// Functions
77 ////
78
79 void generate_kpk_bitbase(uint8_t bitbase[]) {
80   // Allocate array and initialize:
81   Bitbase = new Result[IndexMax];
82   initialize();
83
84   // Iterate until all positions are classified:
85   while(next_iteration());
86
87   // Compress bitbase into the supplied parameter:
88   int i, j, b;
89   for(i = 0; i < 24576; i++) {
90     for(b = 0, j = 0; j < 8; b |= (compress_result(Bitbase[8*i+j]) << j), j++);
91     bitbase[i] = b;
92   }
93
94   // Release allocated memory:
95   delete [] Bitbase;
96 }
97
98
99 namespace {
100
101   void KPKPosition::from_index(int index) {
102     int s;
103     sideToMove = Color(index % 2);
104     blackKingSquare = Square((index / 2) % 64);
105     whiteKingSquare = Square((index / 128) % 64);
106     s = (index / 8192) % 24;
107     pawnSquare = make_square(File(s % 4), Rank(s / 4 + 1));
108   }
109
110
111   int KPKPosition::to_index() const {
112     return compute_index(whiteKingSquare, blackKingSquare, pawnSquare,
113                          sideToMove);
114   }
115     
116
117   bool KPKPosition::is_legal() const {
118     if(whiteKingSquare == pawnSquare || whiteKingSquare == blackKingSquare ||
119        pawnSquare == blackKingSquare)
120       return false;
121     if(sideToMove == WHITE) {
122       if(bit_is_set(this->wk_attacks(), blackKingSquare))
123         return false;
124       if(bit_is_set(this->pawn_attacks(), blackKingSquare))
125         return false;
126     }
127     else {
128       if(bit_is_set(this->bk_attacks(), whiteKingSquare))
129         return false;
130     }
131     return true;
132   }
133
134
135   bool KPKPosition::is_immediate_draw() const {
136     if(sideToMove == BLACK) {
137       Bitboard wka = this->wk_attacks();
138       Bitboard bka = this->bk_attacks();
139     
140       // Case 1: Stalemate
141       if((bka & ~(wka | this->pawn_attacks())) == EmptyBoardBB)
142         return true;
143
144       // Case 2: King can capture pawn
145       if(bit_is_set(bka, pawnSquare) && !bit_is_set(wka, pawnSquare))
146         return true;
147     }
148     else {
149       // Case 1: Stalemate
150       if(whiteKingSquare == SQ_A8 && pawnSquare == SQ_A7 &&
151          (blackKingSquare == SQ_C7 || blackKingSquare == SQ_C8))
152         return true;
153     }
154
155     return false;
156   }
157
158
159   bool KPKPosition::is_immediate_win() const {
160     // The position is an immediate win if it is white to move and the white
161     // pawn can be promoted without getting captured:
162     return
163       sideToMove == WHITE &&
164       square_rank(pawnSquare) == RANK_7 &&
165       (square_distance(blackKingSquare, pawnSquare+DELTA_N) > 1 ||
166        bit_is_set(this->wk_attacks(), pawnSquare+DELTA_N));
167   }
168     
169
170   Bitboard KPKPosition::wk_attacks() const {
171     return StepAttackBB[WK][whiteKingSquare];
172   }
173
174
175   Bitboard KPKPosition::bk_attacks() const {
176     return StepAttackBB[BK][blackKingSquare];
177   }
178
179
180   Bitboard KPKPosition::pawn_attacks() const {
181     return StepAttackBB[WP][pawnSquare];
182   }
183
184
185   void initialize() {
186     KPKPosition p;
187     for(int i = 0; i < IndexMax; i++) {
188       p.from_index(i);
189       if(!p.is_legal())
190         Bitbase[i] = RESULT_INVALID;
191       else if(p.is_immediate_draw())
192         Bitbase[i] = RESULT_DRAW;
193       else if(p.is_immediate_win())
194         Bitbase[i] = RESULT_WIN;
195       else {
196         Bitbase[i] = RESULT_UNKNOWN;
197         UnknownCount++;
198       }
199     }
200   }
201
202
203   bool next_iteration() {
204     KPKPosition p;
205     int previousUnknownCount = UnknownCount;
206     
207     for(int i = 0; i < IndexMax; i++)
208       if(Bitbase[i] == RESULT_UNKNOWN) {
209         p.from_index(i);
210
211         Bitbase[i] = (p.sideToMove == WHITE)? classify_wtm(p) : classify_btm(p);
212
213         if(Bitbase[i] == RESULT_WIN || Bitbase[i] == RESULT_LOSS ||
214            Bitbase[i] == RESULT_DRAW)
215           UnknownCount--;
216       }
217
218     return UnknownCount != previousUnknownCount;
219   }
220
221
222   Result classify_wtm(const KPKPosition &p) {
223
224     // If one move leads to a position classified as RESULT_LOSS, the result
225     // of the current position is RESULT_WIN.  If all moves lead to positions
226     // classified as RESULT_DRAW, the current position is classified as
227     // RESULT_DRAW.  Otherwise, the current position is classified as
228     // RESULT_UNKNOWN.
229
230     bool unknownFound = false;
231     Bitboard b;
232     Square s;
233     
234     // King moves
235     b = p.wk_attacks();
236     while(b) {
237       s = pop_1st_bit(&b);
238       switch(Bitbase[compute_index(s, p.blackKingSquare, p.pawnSquare,
239                                    BLACK)]) {
240       case RESULT_LOSS:
241         return RESULT_WIN;
242
243       case RESULT_UNKNOWN:
244         unknownFound = true;
245         break;
246
247       case RESULT_DRAW: case RESULT_INVALID:
248         break;
249
250       default:
251         assert(false);
252       }
253     }
254
255     // Pawn moves
256     if(square_rank(p.pawnSquare) < RANK_7) {
257       s = p.pawnSquare + DELTA_N;
258       switch(Bitbase[compute_index(p.whiteKingSquare, p.blackKingSquare, s,
259                                    BLACK)]) {
260       case RESULT_LOSS:
261         return RESULT_WIN;
262         
263       case RESULT_UNKNOWN:
264         unknownFound = true;
265         break;
266           
267       case RESULT_DRAW: case RESULT_INVALID:
268         break;
269         
270       default:
271         assert(false);
272       }
273
274       if(square_rank(s) == RANK_3 &&
275          s != p.whiteKingSquare && s != p.blackKingSquare) {
276         s += DELTA_N;
277         switch(Bitbase[compute_index(p.whiteKingSquare, p.blackKingSquare, s,
278                                      BLACK)]) {
279         case RESULT_LOSS:
280           return RESULT_WIN;
281           
282         case RESULT_UNKNOWN:
283           unknownFound = true;
284           break;
285           
286         case RESULT_DRAW: case RESULT_INVALID:
287           break;
288           
289         default:
290           assert(false);
291         }
292       }
293     }
294     
295     return unknownFound? RESULT_UNKNOWN : RESULT_DRAW;
296   }
297
298
299   Result classify_btm(const KPKPosition &p) {
300
301     // If one move leads to a position classified as RESULT_DRAW, the result
302     // of the current position is RESULT_DRAW.  If all moves lead to positions
303     // classified as RESULT_WIN, the current position is classified as
304     // RESULT_LOSS.  Otherwise, the current position is classified as
305     // RESULT_UNKNOWN.
306
307     bool unknownFound = false;
308     Bitboard b;
309     Square s;
310
311     // King moves
312     b = p.bk_attacks();
313     while(b) {
314       s = pop_1st_bit(&b);
315       switch(Bitbase[compute_index(p.whiteKingSquare, s, p.pawnSquare,
316                                    WHITE)]) {
317       case RESULT_DRAW:
318         return RESULT_DRAW;
319
320       case RESULT_UNKNOWN:
321         unknownFound = true;
322         break;
323
324       case RESULT_WIN: case RESULT_INVALID:
325         break;
326
327       default:
328         assert(false);
329       }
330     }
331
332     return unknownFound? RESULT_UNKNOWN : RESULT_LOSS;
333   }
334
335
336   int compute_index(Square wksq, Square bksq, Square psq, Color stm) {
337     int p = int(square_file(psq)) + (int(square_rank(psq)) - 1) * 4;
338     int result = int(stm) + 2*int(bksq) + 128*int(wksq) + 8192*p;
339     assert(result >= 0 && result < IndexMax);
340     return result;
341   }
342
343
344   int compress_result(Result r) {
345     return (r == RESULT_WIN || r == RESULT_LOSS)? 1 : 0;
346   }
347       
348 }