Bitwise operator overloads between Bitboard and Square
[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-2012 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_DRAW
32   };
33
34   struct KPKPosition {
35     Result classify_knowns(int index);
36     Result classify(int index, Result db[]);
37
38   private:
39     void from_index(int index);
40     Result classify_white(const Result db[]);
41     Result classify_black(const Result db[]);
42     Bitboard wk_attacks()   const { return StepAttacksBB[W_KING][whiteKingSquare]; }
43     Bitboard bk_attacks()   const { return StepAttacksBB[B_KING][blackKingSquare]; }
44     Bitboard pawn_attacks() const { return StepAttacksBB[W_PAWN][pawnSquare]; }
45
46     Square whiteKingSquare, blackKingSquare, pawnSquare;
47     Color sideToMove;
48   };
49
50   // The possible pawns squares are 24, the first 4 files and ranks from 2 to 7
51   const int IndexMax = 2 * 24 * 64 * 64; // color * wp_sq * wk_sq * bk_sq = 196608
52
53   // Each uint32_t stores results of 32 positions, one per bit
54   uint32_t KPKBitbase[IndexMax / 32];
55
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 kpk_bitbase_init() {
69
70   Result db[IndexMax];
71   KPKPosition pos;
72   int index, bit, repeat = 1;
73
74   // Initialize table
75   for (index = 0; index < IndexMax; index++)
76       db[index] = pos.classify_knowns(index);
77
78   // Iterate until all positions are classified (30 cycles needed)
79   while (repeat)
80       for (repeat = index = 0; index < IndexMax; index++)
81           if (   db[index] == RESULT_UNKNOWN
82               && pos.classify(index, db) != RESULT_UNKNOWN)
83               repeat = 1;
84
85   // Map 32 position results into one KPKBitbase[] entry
86   for (index = 0; index < IndexMax / 32; index++)
87       for (bit = 0; bit < 32; bit++)
88           if (db[32 * index + bit] == RESULT_WIN)
89               KPKBitbase[index] |= (1 << bit);
90 }
91
92
93 namespace {
94
95   // A KPK bitbase index is an integer in [0, IndexMax] range
96   //
97   // Information is mapped in this way
98   //
99   // bit     0: side to move (WHITE or BLACK)
100   // bit  1- 6: black king square (from SQ_A1 to SQ_H8)
101   // bit  7-12: white king square (from SQ_A1 to SQ_H8)
102   // bit 13-14: white pawn file (from FILE_A to FILE_D)
103   // bit 15-17: white pawn rank - 1 (from RANK_2 - 1 to RANK_7 - 1)
104
105   int compute_index(Square wksq, Square bksq, Square wpsq, Color stm) {
106
107     assert(file_of(wpsq) <= FILE_D);
108
109     int p = file_of(wpsq) + 4 * (rank_of(wpsq) - 1);
110     int r = stm + 2 * bksq + 128 * wksq + 8192 * p;
111
112     assert(r >= 0 && r < IndexMax);
113
114     return r;
115   }
116
117   void KPKPosition::from_index(int index) {
118
119     int s = index >> 13;
120     sideToMove = Color(index & 1);
121     blackKingSquare = Square((index >> 1) & 63);
122     whiteKingSquare = Square((index >> 7) & 63);
123     pawnSquare = make_square(File(s & 3), Rank((s >> 2) + 1));
124   }
125
126   Result KPKPosition::classify_knowns(int index) {
127
128     from_index(index);
129
130     // Check if two pieces are on the same square
131     if (   whiteKingSquare == pawnSquare
132         || whiteKingSquare == blackKingSquare
133         || blackKingSquare == pawnSquare)
134         return RESULT_INVALID;
135
136     // Check if a king can be captured
137     if (   (wk_attacks() & blackKingSquare)
138         || ((pawn_attacks() & blackKingSquare) && sideToMove == WHITE))
139         return RESULT_INVALID;
140
141     // The position is an immediate win if it is white to move and the
142     // white pawn can be promoted without getting captured.
143     if (   rank_of(pawnSquare) == RANK_7
144         && sideToMove == WHITE
145         && whiteKingSquare != pawnSquare + DELTA_N
146         && (   square_distance(blackKingSquare, pawnSquare + DELTA_N) > 1
147             || (wk_attacks() & (pawnSquare + DELTA_N))))
148         return RESULT_WIN;
149
150     // Check for known draw positions
151     //
152     // Case 1: Stalemate
153     if (   sideToMove == BLACK
154         && !(bk_attacks() & ~(wk_attacks() | pawn_attacks())))
155         return RESULT_DRAW;
156
157     // Case 2: King can capture pawn
158     if (   sideToMove == BLACK
159         && (bk_attacks() & pawnSquare) && !(wk_attacks() & pawnSquare))
160         return RESULT_DRAW;
161
162     // Case 3: Black king in front of white pawn
163     if (   blackKingSquare == pawnSquare + DELTA_N
164         && rank_of(pawnSquare) < RANK_7)
165         return RESULT_DRAW;
166
167     //  Case 4: White king in front of pawn and black has opposition
168     if (   whiteKingSquare == pawnSquare + DELTA_N
169         && blackKingSquare == pawnSquare + DELTA_N + DELTA_N + DELTA_N
170         && rank_of(pawnSquare) < RANK_5
171         && sideToMove == WHITE)
172         return RESULT_DRAW;
173
174     // Case 5: Stalemate with rook pawn
175     if (   blackKingSquare == SQ_A8
176         && file_of(pawnSquare) == FILE_A)
177         return RESULT_DRAW;
178
179     return RESULT_UNKNOWN;
180   }
181
182   Result KPKPosition::classify(int index, Result db[]) {
183
184     from_index(index);
185     db[index] = (sideToMove == WHITE ? classify_white(db) : classify_black(db));
186     return db[index];
187   }
188
189   Result KPKPosition::classify_white(const Result db[]) {
190
191     // If one move leads to a position classified as RESULT_WIN, the result
192     // of the current position is RESULT_WIN. If all moves lead to positions
193     // classified as RESULT_DRAW, the current position is classified RESULT_DRAW
194     // otherwise the current position is classified as RESULT_UNKNOWN.
195
196     bool unknownFound = false;
197     Bitboard b;
198     Square s;
199     Result r;
200
201     // King moves
202     b = wk_attacks();
203     while (b)
204     {
205         s = pop_1st_bit(&b);
206         r = db[compute_index(s, blackKingSquare, pawnSquare, BLACK)];
207
208         if (r == RESULT_WIN)
209             return RESULT_WIN;
210
211         if (r == RESULT_UNKNOWN)
212             unknownFound = true;
213     }
214
215     // Pawn moves
216     if (rank_of(pawnSquare) < RANK_7)
217     {
218         s = pawnSquare + DELTA_N;
219         r = db[compute_index(whiteKingSquare, blackKingSquare, s, BLACK)];
220
221         if (r == RESULT_WIN)
222             return RESULT_WIN;
223
224         if (r == RESULT_UNKNOWN)
225             unknownFound = true;
226
227         // Double pawn push
228         if (rank_of(s) == RANK_3 && r != RESULT_INVALID)
229         {
230             s += DELTA_N;
231             r = db[compute_index(whiteKingSquare, blackKingSquare, s, BLACK)];
232
233             if (r == RESULT_WIN)
234                 return RESULT_WIN;
235
236             if (r == RESULT_UNKNOWN)
237                 unknownFound = true;
238         }
239     }
240     return unknownFound ? RESULT_UNKNOWN : RESULT_DRAW;
241   }
242
243   Result KPKPosition::classify_black(const Result db[]) {
244
245     // If one move leads to a position classified as RESULT_DRAW, the result
246     // of the current position is RESULT_DRAW. If all moves lead to positions
247     // classified as RESULT_WIN, the position is classified as RESULT_WIN.
248     // Otherwise, the current position is classified as RESULT_UNKNOWN.
249
250     bool unknownFound = false;
251     Bitboard b;
252     Square s;
253     Result r;
254
255     // King moves
256     b = bk_attacks();
257     while (b)
258     {
259         s = pop_1st_bit(&b);
260         r = db[compute_index(whiteKingSquare, s, pawnSquare, WHITE)];
261
262         if (r == RESULT_DRAW)
263             return RESULT_DRAW;
264
265         if (r == RESULT_UNKNOWN)
266             unknownFound = true;
267     }
268     return unknownFound ? RESULT_UNKNOWN : RESULT_WIN;
269   }
270
271 }