1 /* see.cpp
2
3 GNU Chess engine
4
5 Copyright (C) 2001-2011 Free Software Foundation, Inc.
6
7 This program is free software: you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation, either version 3 of the License, or
10 (at your option) any later version.
11
12 This program is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with this program. If not, see <http://www.gnu.org/licenses/>.
19 */
20
21
22 // see.cpp
23
24 // includes
25
26 #include "attack.h"
27 #include "board.h"
28 #include "colour.h"
29 #include "move.h"
30 #include "piece.h"
31 #include "see.h"
32 #include "util.h"
33 #include "value.h"
34
35 // macros
36
37 #define ALIST_CLEAR(alist) ((alist)->size=0)
38
39 namespace engine {
40
41 // types
42
43 struct alist_t {
44 int size;
45 int square[15];
46 };
47
48 struct alists_t {
49 alist_t alist[ColourNb][1];
50 };
51
52 // prototypes
53
54 static int see_rec (alists_t * alists, const board_t * board, int colour, int to, int piece_value);
55
56 static void alist_build (alist_t * alist, const board_t * board, int to, int colour);
57 static void alists_hidden (alists_t * alists, const board_t * board, int from, int to);
58
59 static void alist_add (alist_t * alist, int square, const board_t * board);
60 static void alist_remove (alist_t * alist, int pos);
61 static int alist_pop (alist_t * alist, const board_t * board);
62
63 // functions
64
65 // see_move()
66
see_move(int move,const board_t * board)67 int see_move(int move, const board_t * board) {
68
69 int att, def;
70 int from, to;
71 alists_t alists[1];
72 int value, piece_value;
73 int piece, capture;
74 alist_t * alist;
75 int pos;
76
77 ASSERT(move_is_ok(move));
78 ASSERT(board!=NULL);
79
80 // init
81
82 from = MOVE_FROM(move);
83 to = MOVE_TO(move);
84
85 // move the piece
86
87 piece_value = 0;
88
89 piece = board->square[from];
90 ASSERT(piece_is_ok(piece));
91
92 att = PIECE_COLOUR(piece);
93 def = COLOUR_OPP(att);
94
95 // promote
96
97 if (MOVE_IS_PROMOTE(move)) {
98 ASSERT(PIECE_IS_PAWN(piece));
99 piece = move_promote(move);
100 ASSERT(piece_is_ok(piece));
101 ASSERT(COLOUR_IS(piece,att));
102 }
103
104 piece_value += VALUE_PIECE(piece);
105
106 // clear attacker lists
107
108 ALIST_CLEAR(alists->alist[Black]);
109 ALIST_CLEAR(alists->alist[White]);
110
111 // find hidden attackers
112
113 alists_hidden(alists,board,from,to);
114
115 // capture the piece
116
117 value = 0;
118
119 capture = board->square[to];
120
121 if (capture != Empty) {
122
123 ASSERT(piece_is_ok(capture));
124 ASSERT(COLOUR_IS(capture,def));
125
126 value += VALUE_PIECE(capture);
127 }
128
129 // promote
130
131 if (MOVE_IS_PROMOTE(move)) {
132 value += VALUE_PIECE(piece) - ValuePawn;
133 }
134
135 // en-passant
136
137 if (MOVE_IS_EN_PASSANT(move)) {
138 ASSERT(value==0);
139 ASSERT(PIECE_IS_PAWN(board->square[SQUARE_EP_DUAL(to)]));
140 value += ValuePawn;
141 alists_hidden(alists,board,SQUARE_EP_DUAL(to),to);
142 }
143
144 // build defender list
145
146 alist = alists->alist[def];
147
148 alist_build(alist,board,to,def);
149 if (alist->size == 0) return value; // no defender => stop SEE
150
151 // build attacker list
152
153 alist = alists->alist[att];
154
155 alist_build(alist,board,to,att);
156
157 // remove the moved piece (if it's an attacker)
158
159 for (pos = 0; pos < alist->size && alist->square[pos] != from; pos++)
160 ;
161
162 if (pos < alist->size) alist_remove(alist,pos);
163
164 // SEE search
165
166 value -= see_rec(alists,board,def,to,piece_value);
167
168 return value;
169 }
170
171 // see_square()
172
see_square(const board_t * board,int to,int colour)173 int see_square(const board_t * board, int to, int colour) {
174
175 int att, def;
176 alists_t alists[1];
177 alist_t * alist;
178 int piece_value;
179 int piece;
180
181 ASSERT(board!=NULL);
182 ASSERT(SQUARE_IS_OK(to));
183 ASSERT(COLOUR_IS_OK(colour));
184
185 ASSERT(COLOUR_IS(board->square[to],COLOUR_OPP(colour)));
186
187 // build attacker list
188
189 att = colour;
190 alist = alists->alist[att];
191
192 ALIST_CLEAR(alist);
193 alist_build(alist,board,to,att);
194
195 if (alist->size == 0) return 0; // no attacker => stop SEE
196
197 // build defender list
198
199 def = COLOUR_OPP(att);
200 alist = alists->alist[def];
201
202 ALIST_CLEAR(alist);
203 alist_build(alist,board,to,def);
204
205 // captured piece
206
207 piece = board->square[to];
208 ASSERT(piece_is_ok(piece));
209 ASSERT(COLOUR_IS(piece,def));
210
211 piece_value = VALUE_PIECE(piece);
212
213 // SEE search
214
215 return see_rec(alists,board,att,to,piece_value);
216 }
217
218 // see_rec()
219
see_rec(alists_t * alists,const board_t * board,int colour,int to,int piece_value)220 static int see_rec(alists_t * alists, const board_t * board, int colour, int to, int piece_value) {
221
222 int from, piece;
223 int value;
224
225 ASSERT(alists!=NULL);
226 ASSERT(board!=NULL);
227 ASSERT(COLOUR_IS_OK(colour));
228 ASSERT(SQUARE_IS_OK(to));
229 ASSERT(piece_value>0);
230
231 // find the least valuable attacker
232
233 from = alist_pop(alists->alist[colour],board);
234 if (from == SquareNone) return 0; // no more attackers
235
236 // find hidden attackers
237
238 alists_hidden(alists,board,from,to);
239
240 // calculate the capture value
241
242 value = +piece_value; // captured piece
243 if (value == ValueKing) return value; // do not allow an answer to a king capture
244
245 piece = board->square[from];
246 ASSERT(piece_is_ok(piece));
247 ASSERT(COLOUR_IS(piece,colour));
248 piece_value = VALUE_PIECE(piece);
249
250 // promote
251
252 if (piece_value == ValuePawn && SQUARE_IS_PROMOTE(to)) { // HACK: PIECE_IS_PAWN(piece)
253 ASSERT(PIECE_IS_PAWN(piece));
254 piece_value = ValueQueen;
255 value += ValueQueen - ValuePawn;
256 }
257
258 value -= see_rec(alists,board,COLOUR_OPP(colour),to,piece_value);
259
260 if (value < 0) value = 0;
261
262 return value;
263 }
264
265 // alist_build()
266
alist_build(alist_t * alist,const board_t * board,int to,int colour)267 static void alist_build(alist_t * alist, const board_t * board, int to, int colour) {
268
269 const sq_t * ptr;
270 int from;
271 int piece;
272 int delta;
273 int inc;
274 int sq;
275 int pawn;
276
277 ASSERT(alist!=NULL);
278 ASSERT(board!=NULL);
279 ASSERT(SQUARE_IS_OK(to));
280 ASSERT(COLOUR_IS_OK(colour));
281
282 // piece attacks
283
284 for (ptr = &board->piece[colour][0]; (from=*ptr) != SquareNone; ptr++) {
285
286 piece = board->square[from];
287 delta = to - from;
288
289 if (PSEUDO_ATTACK(piece,delta)) {
290
291 inc = DELTA_INC_ALL(delta);
292 ASSERT(inc!=IncNone);
293
294 sq = from;
295 do {
296 sq += inc;
297 if (sq == to) { // attack
298 alist_add(alist,from,board);
299 break;
300 }
301 } while (board->square[sq] == Empty);
302 }
303 }
304
305 // pawn attacks
306
307 inc = PAWN_MOVE_INC(colour);
308 pawn = PAWN_MAKE(colour);
309
310 from = to - (inc-1);
311 if (board->square[from] == pawn) alist_add(alist,from,board);
312
313 from = to - (inc+1);
314 if (board->square[from] == pawn) alist_add(alist,from,board);
315 }
316
317 // alists_hidden()
318
alists_hidden(alists_t * alists,const board_t * board,int from,int to)319 static void alists_hidden(alists_t * alists, const board_t * board, int from, int to) {
320
321 int inc;
322 int sq, piece;
323
324 ASSERT(alists!=NULL);
325 ASSERT(board!=NULL);
326 ASSERT(SQUARE_IS_OK(from));
327 ASSERT(SQUARE_IS_OK(to));
328
329 inc = DELTA_INC_LINE(to-from);
330
331 if (inc != IncNone) { // line
332
333 sq = from;
334 do sq -= inc; while ((piece=board->square[sq]) == Empty);
335
336 if (SLIDER_ATTACK(piece,inc)) {
337
338 ASSERT(piece_is_ok(piece));
339 ASSERT(PIECE_IS_SLIDER(piece));
340
341 alist_add(alists->alist[PIECE_COLOUR(piece)],sq,board);
342 }
343 }
344 }
345
346 // alist_add()
347
alist_add(alist_t * alist,int square,const board_t * board)348 static void alist_add(alist_t * alist, int square, const board_t * board) {
349
350 int piece;
351 int size, pos;
352
353 ASSERT(alist!=NULL);
354 ASSERT(SQUARE_IS_OK(square));
355 ASSERT(board!=NULL);
356
357 // insert in MV order
358
359 piece = board->square[square];
360 size = ++alist->size; // HACK
361 ASSERT(size>0&&size<16);
362
363 for (pos = size-1; pos > 0 && piece > board->square[alist->square[pos-1]]; pos--) { // HACK
364 ASSERT(pos>0&&pos<size);
365 alist->square[pos] = alist->square[pos-1];
366 }
367
368 ASSERT(pos>=0&&pos<size);
369 alist->square[pos] = square;
370 }
371
372 // alist_remove()
373
alist_remove(alist_t * alist,int pos)374 static void alist_remove(alist_t * alist, int pos) {
375
376 int size, i;
377
378 ASSERT(alist!=NULL);
379 ASSERT(pos>=0&&pos<alist->size);
380
381 size = alist->size--; // HACK
382 ASSERT(size>=1);
383
384 ASSERT(pos>=0&&pos<size);
385
386 for (i = pos; i < size-1; i++) {
387 ASSERT(i>=0&&i<size-1);
388 alist->square[i] = alist->square[i+1];
389 }
390 }
391
392 // alist_pop()
393
alist_pop(alist_t * alist,const board_t * board)394 static int alist_pop(alist_t * alist, const board_t * board) {
395
396 int sq;
397 int size;
398
399 ASSERT(alist!=NULL);
400 ASSERT(board!=NULL);
401
402 sq = SquareNone;
403
404 size = alist->size;
405
406 if (size != 0) {
407 size--;
408 ASSERT(size>=0);
409 sq = alist->square[size];
410 alist->size = size;
411 }
412
413 return sq;
414 }
415
416 } // namespace engine
417
418 // end of see.cpp
419
420