1 /* DreamChess
2 **
3 ** DreamChess is the legal property of its developers, whose names are too
4 ** numerous to list here. Please refer to the AUTHORS.txt file distributed
5 ** with this source distribution.
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 #include <stdio.h>
22 #include <stdlib.h>
23
24 #include "board.h"
25 #include "commands.h"
26 #include "dreamer.h"
27 #include "e_comm.h"
28 #include "history.h"
29 #include "move.h"
30 #include "move_data.h"
31 #include "transposition.h"
32
33 /* Global move tables. */
34 int ***rook_moves;
35 int ***bishop_moves;
36 int ***queen_moves;
37 int **knight_moves;
38 int **king_moves;
39 int **white_pawn_capture_moves;
40 int **black_pawn_capture_moves;
41
42 /* Global move list. Add 1 for in_check function */
43 move_t moves[(MAX_DEPTH + 1) * 256];
44 int moves_start[MAX_DEPTH + 2];
45 int moves_cur[MAX_DEPTH + 1];
46
47 #define add_moves_ray(FUNCNAME, MOVES, PIECE, PLAYER, OPPONENT_FIND, LOOP) \
48 static move_t *FUNCNAME(board_t *board, move_t *move) { \
49 int source; \
50 bitboard_t bitboard = board->bitboard[PIECE + PLAYER]; \
51 \
52 /* Look for the pieces, starting at player's side of the board. */ \
53 for (LOOP) { \
54 int **ray; \
55 \
56 /* If no more pieces of this type are found, we're done. */ \
57 if (!bitboard) \
58 return move; \
59 \
60 /* If no piece of this type is at this square, continue searching. */ \
61 if (!(bitboard & square_bit[source])) \
62 continue; \
63 \
64 /* Iterate over rays. */ \
65 for (ray = MOVES[source]; *ray; ray++) { \
66 int elm; \
67 \
68 /* Iterate over ray elements. */ \
69 for (elm = 1; elm <= (*ray)[0]; elm++) { \
70 int dest = (*ray)[elm]; \
71 \
72 /* If there's a white piece at the destination, break off the ray. */ \
73 if (board->bitboard[ALL + PLAYER] & square_bit[dest]) \
74 break; \
75 \
76 /* The move is legal. */ \
77 \
78 /* If there's a black piece at the destination, this is a capture move. */ \
79 if (board->bitboard[ALL + OPPONENT(PLAYER)] & square_bit[dest]) { \
80 int piece = OPPONENT_FIND(board, dest); \
81 \
82 /* If we are capturing a king, previous board position was illegal. */ \
83 if (piece == KING + OPPONENT(PLAYER)) \
84 return NULL; \
85 \
86 *move++ = MOVE(PIECE + PLAYER, source, dest, CAPTURE_MOVE, piece); \
87 \
88 /* Break off the ray. */ \
89 break; \
90 } else { \
91 /* Normal move. */ \
92 *move++ = MOVE(PIECE + PLAYER, source, dest, NORMAL_MOVE, 0); \
93 } \
94 } \
95 } \
96 \
97 /* Remove piece from the copy of the bitboard. */ \
98 bitboard ^= square_bit[source]; \
99 } \
100 \
101 return move; \
102 }
103
104 #define add_moves_single(FUNCNAME, MOVES, PIECE, PLAYER, OPPONENT_FIND, LOOP) \
105 static move_t *FUNCNAME(board_t *board, move_t *move) { \
106 int source; \
107 bitboard_t bitboard = board->bitboard[PIECE + PLAYER]; \
108 \
109 /* Look for the pieces, starting at player's side of the board. */ \
110 for (LOOP) { \
111 int *moves = MOVES[source]; \
112 int elm; \
113 \
114 /* If no more pieces of this type are found, we're done. */ \
115 if (!bitboard) \
116 return move; \
117 \
118 /* If no piece of this type is at this square, continue searching. */ \
119 if (!(bitboard & square_bit[source])) \
120 continue; \
121 \
122 /* Iterate over moves. */ \
123 for (elm = 1; elm <= moves[0]; elm++) { \
124 int dest = moves[elm]; \
125 \
126 /* If there's a white piece at the destination, skip this possible move. */ \
127 if (board->bitboard[ALL + PLAYER] & square_bit[dest]) \
128 continue; \
129 \
130 /* The move is legal. */ \
131 \
132 /* If there's a black piece at the destination, this is a capture move. */ \
133 if (board->bitboard[ALL + OPPONENT(PLAYER)] & square_bit[dest]) { \
134 int piece = OPPONENT_FIND(board, dest); \
135 \
136 /* If we are capturing a king, previous board position was illegal. */ \
137 if (piece == KING + OPPONENT(PLAYER)) \
138 return NULL; \
139 \
140 *move++ = MOVE(PIECE + PLAYER, source, dest, CAPTURE_MOVE, piece); \
141 } else { \
142 /* Normal move. */ \
143 *move++ = MOVE(PIECE + PLAYER, source, dest, NORMAL_MOVE, 0); \
144 } \
145 } \
146 \
147 /* Remove piece from the copy of the bitboard. */ \
148 bitboard ^= square_bit[source]; \
149 } \
150 \
151 return move; \
152 }
153
154 #define add_pawn_moves(FUNCNAME, MOVES, INC, TEST1, TEST2, PLAYER, OPPONENT_FIND, LOOP) \
155 static move_t *FUNCNAME(board_t *board, move_t *move) { \
156 int source; \
157 bitboard_t bitboard = board->bitboard[PAWN + PLAYER]; \
158 bitboard_t bitboard_all = board->bitboard[WHITE_ALL] | board->bitboard[BLACK_ALL]; \
159 \
160 for (LOOP) { \
161 int dest; \
162 int elm; \
163 \
164 if (!bitboard) \
165 return move; \
166 \
167 if (!(bitboard & square_bit[source])) \
168 continue; \
169 \
170 dest = source + INC; \
171 \
172 if (!(bitboard_all & square_bit[dest])) { \
173 if (TEST1) { \
174 /* Normal move. */ \
175 *move++ = MOVE(PAWN + PLAYER, source, dest, NORMAL_MOVE, 0); \
176 \
177 if (TEST2) { \
178 dest += INC; \
179 if (!(bitboard_all & square_bit[dest])) { \
180 /* Double push. */ \
181 *move++ = MOVE(PAWN + PLAYER, source, dest, NORMAL_MOVE, 0); \
182 } \
183 } \
184 } else { \
185 /* Pawn promotion. */ \
186 *move++ = MOVE(PAWN + PLAYER, source, dest, NORMAL_MOVE | PROMOTION_MOVE_QUEEN, 0); \
187 *move++ = MOVE(PAWN + PLAYER, source, dest, NORMAL_MOVE | PROMOTION_MOVE_ROOK, 0); \
188 *move++ = MOVE(PAWN + PLAYER, source, dest, NORMAL_MOVE | PROMOTION_MOVE_BISHOP, 0); \
189 *move++ = MOVE(PAWN + PLAYER, source, dest, NORMAL_MOVE | PROMOTION_MOVE_KNIGHT, 0); \
190 } \
191 } \
192 \
193 /* Check for capture moves. */ \
194 for (elm = 1; elm <= MOVES[source][0]; elm++) { \
195 int dest = MOVES[source][elm]; \
196 int piece; \
197 \
198 /* If there's not a black piece at the destination, skip this possible move. */ \
199 if (board->bitboard[ALL + OPPONENT(PLAYER)] & square_bit[dest]) { \
200 piece = OPPONENT_FIND(board, dest); \
201 \
202 /* If we are capturing a king, previous board position was illegal. */ \
203 if (piece == KING + OPPONENT(PLAYER)) \
204 return NULL; \
205 \
206 /* The move is legal. */ \
207 if (TEST1) { \
208 *move++ = MOVE(PAWN + PLAYER, source, dest, CAPTURE_MOVE, piece); \
209 } else { \
210 *move++ = MOVE(PAWN + PLAYER, source, dest, CAPTURE_MOVE | PROMOTION_MOVE_QUEEN, piece); \
211 *move++ = MOVE(PAWN + PLAYER, source, dest, CAPTURE_MOVE | PROMOTION_MOVE_ROOK, piece); \
212 *move++ = MOVE(PAWN + PLAYER, source, dest, CAPTURE_MOVE | PROMOTION_MOVE_BISHOP, piece); \
213 *move++ = MOVE(PAWN + PLAYER, source, dest, CAPTURE_MOVE | PROMOTION_MOVE_KNIGHT, piece); \
214 } \
215 } else if (board->en_passant & square_bit[dest]) { \
216 /* En passant capture. */ \
217 *move++ = MOVE(PAWN + PLAYER, source, dest, CAPTURE_MOVE_EN_PASSANT, PAWN + OPPONENT(PLAYER)); \
218 } \
219 } \
220 \
221 /* Remove piece from the copy of the bitboard. */ \
222 bitboard ^= square_bit[source]; \
223 } \
224 \
225 return move; \
226 }
227
228 add_moves_ray(add_black_rook_moves, rook_moves, ROOK, SIDE_BLACK, find_white_piece, source = 63; source >= 0; source--)
229 add_moves_ray(add_white_rook_moves, rook_moves, ROOK, SIDE_WHITE, find_black_piece, source = 0; source < 64; source++)
230 add_moves_ray(add_black_bishop_moves, bishop_moves, BISHOP, SIDE_BLACK, find_white_piece, source = 63; source >= 0;
231 source--)
232 add_moves_ray(add_white_bishop_moves, bishop_moves, BISHOP, SIDE_WHITE, find_black_piece, source = 0; source < 64;
233 source++)
234 add_moves_ray(add_white_queen_moves, queen_moves, QUEEN, SIDE_WHITE, find_black_piece, source = 0; source < 64;
235 source++)
236 add_moves_ray(add_black_queen_moves, queen_moves, QUEEN, SIDE_BLACK, find_white_piece, source = 63; source >= 0;
237 source--)
238 add_moves_single(add_white_knight_moves, knight_moves, KNIGHT, SIDE_WHITE, find_black_piece, source = 0; source < 64;
239 source++)
240 add_moves_single(add_black_knight_moves, knight_moves, KNIGHT, SIDE_BLACK, find_white_piece, source = 63; source >= 0;
241 source--)
242 add_moves_single(add_white_king_moves, king_moves, KING, SIDE_WHITE, find_black_piece, source = 0; source < 64;
243 source++)
244 add_moves_single(add_black_king_moves, king_moves, KING, SIDE_BLACK, find_white_piece, source = 63; source >= 0;
245 source--)
246 add_pawn_moves(add_white_pawn_moves, white_pawn_capture_moves, +8, dest <= 55, !(source & ~15), SIDE_WHITE,
247 find_black_piece, source = 8;
248 source <= 55; source++)
249 add_pawn_moves(add_black_pawn_moves, black_pawn_capture_moves, -8, dest >= 8, source >= 48, SIDE_BLACK,
250 find_white_piece, source = 55;
251 source >= 8; source--)
252
add_white_castle_moves(board_t * board,move_t * move)253 static move_t *add_white_castle_moves(board_t *board, move_t *move) {
254 /* Kingside castle. Check for empty squares. */
255 if ((board->castle_flags & WHITE_CAN_CASTLE_KINGSIDE) &&
256 (!((board->bitboard[BLACK_ALL] | board->bitboard[WHITE_ALL]) & WHITE_EMPTY_KINGSIDE))) {
257 *move++ = MOVE(WHITE_KING, SQUARE_E1, SQUARE_G1, CASTLING_MOVE_KINGSIDE, 0);
258 }
259
260 /* Queenside castle. Check for empty squares. */
261 if ((board->castle_flags & WHITE_CAN_CASTLE_QUEENSIDE) &&
262 (!((board->bitboard[BLACK_ALL] | board->bitboard[WHITE_ALL]) & WHITE_EMPTY_QUEENSIDE))) {
263 *move++ = MOVE(WHITE_KING, SQUARE_E1, SQUARE_C1, CASTLING_MOVE_QUEENSIDE, 0);
264 }
265
266 return move;
267 }
268
add_black_castle_moves(board_t * board,move_t * move)269 static move_t *add_black_castle_moves(board_t *board, move_t *move) {
270 /* Kingside castle. Check for empty squares. */
271 if ((board->castle_flags & BLACK_CAN_CASTLE_KINGSIDE) &&
272 (!((board->bitboard[BLACK_ALL] | board->bitboard[WHITE_ALL]) & BLACK_EMPTY_KINGSIDE))) {
273 *move++ = MOVE(BLACK_KING, SQUARE_E8, SQUARE_G8, CASTLING_MOVE_KINGSIDE, 0);
274 }
275
276 /* Queenside castle. Check for empty squares. */
277 if ((board->castle_flags & BLACK_CAN_CASTLE_QUEENSIDE) &&
278 (!((board->bitboard[BLACK_ALL] | board->bitboard[WHITE_ALL]) & BLACK_EMPTY_QUEENSIDE))) {
279 *move++ = MOVE(BLACK_KING, SQUARE_E8, SQUARE_C8, CASTLING_MOVE_QUEENSIDE, 0);
280 }
281
282 return move;
283 }
284
compute_legal_moves(board_t * board,int ply)285 int compute_legal_moves(board_t *board, int ply) {
286 move_t *move = &moves[moves_start[ply]];
287
288 if (board->current_player == SIDE_WHITE) {
289 move = add_white_castle_moves(board, move);
290
291 if (!(move = add_white_king_moves(board, move)) || !(move = add_white_queen_moves(board, move)) ||
292 !(move = add_white_rook_moves(board, move)) || !(move = add_white_bishop_moves(board, move)) ||
293 !(move = add_white_knight_moves(board, move)) || !(move = add_white_pawn_moves(board, move)))
294 return -1;
295 } else {
296 move = add_black_castle_moves(board, move);
297
298 if (!(move = add_black_king_moves(board, move)) || !(move = add_black_queen_moves(board, move)) ||
299 !(move = add_black_rook_moves(board, move)) || !(move = add_black_bishop_moves(board, move)) ||
300 !(move = add_black_knight_moves(board, move)) || !(move = add_black_pawn_moves(board, move)))
301 return -1;
302 }
303
304 moves_start[ply + 1] = moves_start[ply] + move - &moves[moves_start[ply]];
305 moves_cur[ply] = moves_start[ply];
306 return 0;
307 }
308
move_next(board_t * board,int ply)309 move_t move_next(board_t *board, int ply) {
310 if (moves_cur[ply] == moves_start[ply + 1])
311 return NO_MOVE;
312
313 if (moves_cur[ply] == moves_start[ply]) {
314 move_t move = lookup_best_move(board);
315
316 if (move != NO_MOVE)
317 best_first(ply, move);
318 } else
319 sort_next(ply, board->current_player);
320
321 return moves[moves_cur[ply]++];
322 }
323
324 #if 0
325 void list_moves(int ply)
326 {
327 int i;
328 for (i = moves_start[ply]; i < moves_start[ply + 1]; i++)
329 {
330 char *s = coord_move_str(moves[i]);
331 e_comm_send("%i %s\n", i, s);
332 free(s);
333 }
334 }
335 #endif
336
move_init(void)337 void move_init(void) {
338 rook_moves = all_rook_moves();
339 knight_moves = all_knight_moves();
340 king_moves = all_king_moves();
341 bishop_moves = all_bishop_moves();
342 queen_moves = all_queen_moves();
343 white_pawn_capture_moves = all_white_pawn_capture_moves();
344 black_pawn_capture_moves = all_black_pawn_capture_moves();
345 }
346
free_moves_ray(int *** moves)347 static void free_moves_ray(int ***moves) {
348 int **ray;
349 int source;
350
351 for (source = 0; source < 64; source++) {
352
353 /* Iterate over rays. */
354 for (ray = moves[source]; *ray; ray++)
355 free(*ray);
356
357 free(moves[source]);
358 }
359
360 free(moves);
361 }
362
free_moves_single(int ** moves)363 static void free_moves_single(int **moves) {
364 int source;
365
366 for (source = 0; source < 64; source++) {
367 free(moves[source]);
368 }
369
370 free(moves);
371 }
372
move_exit(void)373 void move_exit(void) {
374 free_moves_ray(queen_moves);
375 free_moves_ray(bishop_moves);
376 free_moves_ray(rook_moves);
377 free_moves_single(knight_moves);
378 free_moves_single(king_moves);
379 free_moves_single(white_pawn_capture_moves);
380 free_moves_single(black_pawn_capture_moves);
381 }
382