?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
search: fixed a bug in NULL move pruning
[owl.git] / movegen.c
blob9075e5dfe22b19f426d29115b4f6779def1aef04
1 /*
2 * This program is free software; you can redistribute it and/or modify
3 * it under the terms of the GNU General Public License as published by
4 * the Free Software Foundation; either version 2 of the License, or
5 * (at your option) any later version.
6 *
7 * This program is distributed in the hope that it will be useful,
8 * but WITHOUT ANY WARRANTY; without even the implied warranty of
9 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
10 * GNU General Public License for more details.
11 *
12 * You should have received a copy of the GNU General Public License
13 * along with this program; if not, write to the Free Software
14 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
15 */
16 #include <assert.h>
17 #include "common.h"
18 #include "attacks.h"
19 #include "board.h"
20 #include "engine.h"
21 #include "move.h"
22
23 #define CreateMove(from, to, type, piece) (SET_FROM(from) | SET_TO(to) | SET_TYPE(type) | SET_PROMOTE(piece))
24
25 const int sign_8[2] = {-8, 8};
26 const int sign_16[2] = {-16, 16};
27 const int ks[2] = {WHITE_CASTLE_KINGSIDE, BLACK_CASTLE_KINGSIDE};
28 const int qs[2] = {WHITE_CASTLE_QUEENSIDE, BLACK_CASTLE_QUEENSIDE};
29
30 /* forward declarations of functions */
31 static int cap(int move, int side, int *see);
32 static int gen_non_quiescent_moves(struct moves_t *moves);
33
34 /* pawn pushes */
35 static void gen_pawn_push_one(int side, struct moves_t *moves);
36 static void gen_pawn_push_two(int side, struct moves_t *moves);
37
38 /* piece moves including captures */
39 static void gen_knight(int side, int capture, uint64_t mask, struct moves_t *moves);
40 static void gen_bishop(int side, int capture, uint64_t mask, struct moves_t *moves);
41 static void gen_rook(int side, int capture, uint64_t mask, struct moves_t *moves);
42 static void gen_queen(int side, int capture, uint64_t mask, struct moves_t *moves);
43 static void gen_king(int side, int capture, uint64_t mask, struct moves_t *moves);
44
45 /* castle moves */
46 static void gen_castle(int side, struct moves_t *moves);
47
48 /* pawn promotes */
49 static void gen_pawn_promote_minor(int side, struct moves_t *moves);
50 static void gen_pawn_promote_queen(int side, struct moves_t *moves);
51
52 /* pawn promotes and captures */
53 static void gen_pawn_cap_promote(int side, struct moves_t *moves);
54
55 /* score for move ordering */
56 static int
57 cap(int move, int side, int *see)
58 {
59 *see = SEE(move);
60 if (*see < 0)
61 return (*see);
62 else
63 return (*see) + 10000000;
64 }
65
66 /* return only legal moves */
67 int
68 gen_legal_moves(struct moves_t *moves)
69 {
70 int i;
71 struct moves_t tmp_moves;
72
73 moves->count = 0;
74 gen_moves(&tmp_moves);
75
76 for (i = 0; i < tmp_moves.count; i++) {
77 if (make_move(tmp_moves.move[i], TRUE)) {
78 moves->move[moves->count] = tmp_moves.move[i];
79 moves->score[moves->count] = tmp_moves.score[i];
80 moves->see[moves->count] = tmp_moves.see[i];
81 moves->count++;
82 }
83 }
84 return moves->count;
85 }
86
87 /* generate all pseudo legal moves */
88 int
89 gen_moves(struct moves_t *moves)
90 {
91 gen_quiescent_moves(moves, side_boards[1 ^ brd.wtm]);
92 gen_non_quiescent_moves(moves);
93
94 return moves->count;
95 }
96
97 /* generate captures and queen promotions */
98 int
99 gen_quiescent_moves(struct moves_t *moves, uint64_t target)
100 {
101 moves->count = 0;
102
103 gen_pawn_cap_promote(brd.wtm, moves);
104 gen_knight(brd.wtm, TRUE, target, moves);
105 gen_bishop(brd.wtm, TRUE, target, moves);
106 gen_rook(brd.wtm, TRUE, target, moves);
107 gen_queen(brd.wtm, TRUE, target, moves);
108 gen_king(brd.wtm, TRUE, target, moves);
109 gen_pawn_promote_queen(brd.wtm, moves);
110
111 return moves->count;
112 }
113
114 /* generate non-captures and non-queen promotions */
115 static int
116 gen_non_quiescent_moves(struct moves_t *moves)
117 {
118 uint64_t target = ~complete;
119
120 gen_pawn_push_one(brd.wtm, moves);
121 gen_pawn_push_two(brd.wtm, moves);
122 gen_knight(brd.wtm, FALSE, target, moves);
123 gen_bishop(brd.wtm, FALSE, target, moves);
124 gen_rook(brd.wtm, FALSE, target, moves);
125 gen_queen(brd.wtm, FALSE, target, moves);
126 gen_pawn_promote_minor(brd.wtm, moves);
127 gen_king(brd.wtm, FALSE, target, moves);
128 gen_castle(brd.wtm, moves);
129
130 return moves->count;
131 }
132
133 static void
134 gen_pawn_push_one(int side, struct moves_t *moves)
135 {
136 int to;
137 uint64_t move_mask;
138
139 /* remove pawns that can be promoted (there is another routine
140 for them) */
141 move_mask = side ? ((PAWNS(BLACK) >> 8) & ~complete & ~_RANK1) : \
142 ((PAWNS(WHITE) << 8) & ~complete & ~_RANK8);
143
144 while (move_mask) {
145 to = bit_scan_clear(&move_mask);
146 moves->move[moves->count] = CreateMove(to + sign_8[side], to, \
147 TYPE_PAWN_ONE, 0);
148 moves->score[moves->count] = history[side][PAWN][(to + sign_8[side]) | \
149 (to << 6)];
150 moves->count++;
151 }
152 }
153
154 static void
155 gen_pawn_push_two(int side, struct moves_t *moves)
156 {
157 int to;
158 uint64_t move_mask;
159
160 /* mask pawns standing on their initial positions */
161 move_mask = side ? (((PAWNS(BLACK) & _RANK7) >> 16) & \
162 (~complete & (~complete >> 8))) : (((PAWNS(WHITE) & _RANK2) << 16) & \
163 (~complete & (~complete << 8)));
164
165 while (move_mask) {
166 to = bit_scan_clear(&move_mask);
167 moves->move[moves->count] = CreateMove(to + sign_16[side], to, \
168 TYPE_PAWN_TWO, 0);
169 moves->score[moves->count] = history[side][PAWN][(to + sign_16[side]) | \
170 (to << 6)];
171 moves->count++;
172 }
173 }
174
175 static void
176 gen_knight(int side, int capture, uint64_t mask, struct moves_t *moves)
177 {
178 int from, to;
179 uint64_t move_mask;
180 uint64_t pieces;
181
182 pieces = KNIGHTS(side);
183
184 while (pieces) {
185 from = bit_scan_clear(&pieces);
186 move_mask = piece_moves[KNIGHT][from] & mask;
187
188 while (move_mask) {
189 to = bit_scan_clear(&move_mask);
190 moves->move[moves->count] = CreateMove(from, to, \
191 capture ? TYPE_CAPTURE : 0, 0);
192 moves->score[moves->count] = capture ? \
193 cap(moves->move[moves->count], side, \
194 &moves->see[moves->count]) : history[side][KNIGHT][from | \
195 (to << 6)];
196 moves->count++;
197 }
198 }
199 }
200
201 static void
202 gen_bishop(int side, int capture, uint64_t mask, struct moves_t *moves)
203 {
204 int from, to;
205 uint64_t move_mask;
206 uint64_t pieces;
207
208 pieces = BISHOPS(side);
209
210 while (pieces) {
211 from = bit_scan_clear(&pieces);
212 move_mask = BISHOP_ATTACKS(from, complete) & mask;
213
214 while (move_mask) {
215 to = bit_scan_clear(&move_mask);
216 moves->move[moves->count] = CreateMove(from, to, \
217 capture ? TYPE_CAPTURE : 0, 0);
218 moves->score[moves->count] = capture ? \
219 cap(moves->move[moves->count], side, \
220 &moves->see[moves->count]) : history[side][BISHOP][from | \
221 (to << 6)];
222 moves->count++;
223 }
224 }
225 }
226
227 static void
228 gen_rook(int side, int capture, uint64_t mask, struct moves_t *moves)
229 {
230 int from, to;
231 uint64_t move_mask;
232 uint64_t pieces;
233
234 pieces = ROOKS(side);
235
236 while (pieces) {
237 from = bit_scan_clear(&pieces);
238 move_mask = ROOK_ATTACKS(from, complete) & mask;
239
240 while (move_mask) {
241 to = bit_scan_clear(&move_mask);
242 moves->move[moves->count] = CreateMove(from, to, \
243 capture ? TYPE_CAPTURE : 0, 0);
244 moves->score[moves->count] = capture ? \
245 cap(moves->move[moves->count], side, \
246 &moves->see[moves->count]) : history[side][ROOK][from | \
247 (to << 6)];
248 moves->count++;
249 }
250 }
251 }
252
253 static void
254 gen_queen(int side, int capture, uint64_t mask, struct moves_t *moves)
255 {
256 int from, to;
257 uint64_t move_mask;
258 uint64_t pieces;
259
260 pieces = QUEENS(side);
261
262 while (pieces) {
263 from = bit_scan_clear(&pieces);
264 move_mask = QUEEN_ATTACKS(from, complete) & mask;
265
266 while (move_mask) {
267 to = bit_scan_clear(&move_mask);
268 moves->move[moves->count] = CreateMove(from, to, \
269 capture ? TYPE_CAPTURE : 0, 0);
270 moves->score[moves->count] = capture ? \
271 cap(moves->move[moves->count], side, \
272 &moves->see[moves->count]) : history[side][QUEEN][from | \
273 (to << 6)];
274 moves->count++;
275 }
276 }
277 }
278
279 static void
280 gen_king(int side, int capture, uint64_t mask, struct moves_t *moves)
281 {
282 int from, to;
283 uint64_t move_mask;
284
285 from = brd.kings[side];
286 move_mask = piece_moves[KING][from] & mask;
287
288 while (move_mask) {
289 to = bit_scan_clear(&move_mask);
290 moves->move[moves->count] = CreateMove(from, to, \
291 capture ? TYPE_CAPTURE : 0, 0);
292 moves->score[moves->count] = capture ? \
293 cap(moves->move[moves->count], side, \
294 &moves->see[moves->count]) : history[side][KING][from | \
295 (to << 6)];
296 moves->count++;
297 }
298 }
299
300 static void
301 gen_castle(int side, struct moves_t *moves)
302 {
303 if (!brd.castle_mask)
304 return;
305
306 if ((brd.castle_mask & ks[side]) && !square64[F1 + side * (F8 - F1)] && \
307 !square64[G1 + side * (G8 - G1)]) {
308 moves->move[moves->count] = CreateMove(E1 + side * (E8 - E1), \
309 G1 + side * (G8 - G1), TYPE_CASTLE, 0);
310 moves->score[moves->count] = history[side][KING][(E1 + side * (E8 - E1))\
311 | ((G1 + side * (G8 - G1)) << 6)];
312 moves->count++;
313 }
314 if ((brd.castle_mask & qs[side]) && !square64[B1 + side * (B8 - B1)] && \
315 !square64[C1 + side * (C8 - C1)] && !square64[D1 + side * (D8 - D1)]) {
316 moves->move[moves->count] = CreateMove(E1 + side * (E8 - E1), \
317 C1 + side * (C8 - C1), TYPE_CASTLE, 0);
318 moves->score[moves->count] = history[side][KING][(E1 + side * (E8 - E1))\
319 | ((C1 + side * (C8 - C1)) << 6)];
320 moves->count++;
321 }
322 }
323
324 static void
325 gen_pawn_promote_minor(int side, struct moves_t *moves)
326 {
327 int piece, to;
328 uint64_t mask;
329
330 mask = side == WHITE? (PAWNS(WHITE) << 8) & ~complete & _RANK8 : \
331 (PAWNS(BLACK) >> 8) & ~complete & _RANK1;
332 while (mask) {
333 to = bit_scan_clear(&mask);
334
335 for (piece = KNIGHT; piece < QUEEN; piece++) {
336 moves->move[moves->count] = CreateMove(to + sign_8[side], to, \
337 TYPE_PROMOTE, piece);
338 moves->score[moves->count] = cap(moves->move[moves->count], side, &moves->see[moves->count]);
339 if (moves->score[moves->count] < 0)
340 moves->score[moves->count] = -piece_value[PAWN];
341 moves->count++;
342 }
343 }
344 }
345
346 static void
347 gen_pawn_promote_queen(int side, struct moves_t *moves)
348 {
349 int to;
350 uint64_t mask;
351
352 mask = side == WHITE? (PAWNS(WHITE) << 8) & ~complete & _RANK8 :\
353 (PAWNS(BLACK) >> 8) & ~complete & _RANK1;
354 while (mask) {
355 to = bit_scan_clear(&mask);
356
357 moves->move[moves->count] = CreateMove(to + sign_8[side], to, \
358 TYPE_PROMOTE, QUEEN);
359 moves->score[moves->count] = cap(moves->move[moves->count], side, &moves->see[moves->count]);
360 if (moves->score[moves->count] < 0)
361 /* small bonus for queen promotions */
362 moves->score[moves->count] = -piece_value[PAWN] + 1;
363 moves->count++;
364 }
365 }
366
367 static void
368 gen_pawn_cap_promote(int side, struct moves_t *moves)
369 {
370 int k, l;
371 int piece;
372 int to;
373 uint64_t mask;
374 uint64_t enemies;
375
376 enemies = side_boards[1 ^ side] | (brd.ep == -1? 0 : BIT(brd.ep));
377
378 if (side == WHITE) {
379 for (k = 0, l = 0; k <= 2; k += 2, l += 7) {
380 mask = ((PAWNS(WHITE) & ~file_bit[l]) << (7 + k)) & enemies;
381 while (mask) {
382 to = bit_scan_clear(&mask);
383
384 if (to >= 56) {
385 for (piece = KNIGHT; piece < KING; piece++) {
386 moves->move[moves->count] = CreateMove(to - 7 - k, \
387 to, TYPE_PROMOTE | TYPE_CAPTURE, piece);
388 moves->score[moves->count] = cap(moves->move[moves->count], side, \
389 &moves->see[moves->count]);
390 moves->count++;
391 }
392 } else {
393 moves->move[moves->count] = CreateMove(to - 7 - k, to, \
394 (to != brd.ep? TYPE_CAPTURE : TYPE_ENPASSANT), 0);
395 moves->score[moves->count] = \
396 cap(moves->move[moves->count], \
397 side, &moves->see[moves->count]);
398 moves->count++;
399 }
400 }
401 }
402 } else {
403 for (k = 0, l = 7; k <= 2; k += 2, l -= 7) {
404 mask = ((PAWNS(BLACK) & ~file_bit[l]) >> (7 + k)) & enemies;
405 while (mask) {
406 to = bit_scan_clear(&mask);
407
408 if (to <= 7) {
409 for (piece = KNIGHT; piece < KING; piece++) {
410 moves->move[moves->count] = CreateMove(to + 7 + k, \
411 to, TYPE_PROMOTE | TYPE_CAPTURE, piece);
412 moves->score[moves->count] = cap(moves->move[moves->count], side, \
413 &moves->see[moves->count]);
414 moves->count++;
415 }
416 } else {
417 moves->move[moves->count] = CreateMove(to + 7 + k, to, \
418 (to != brd.ep? TYPE_CAPTURE : TYPE_ENPASSANT), 0);
419 moves->score[moves->count] = \
420 cap(moves->move[moves->count], \
421 side, &moves->see[moves->count]);
422 moves->count++;
423 }
424 }
425 }
426 }
427 }
Xboard-compatible chess engine