Wed, 28 May 2014 15:47:57 +0200
refactoring of getlocation mechanism for better short algebraic notation support (does now respect pinned pieces) + fixed a bug where a pawn could advance through a piece (e.g. e2e4 could jump over a piece on e3)
1 /*
2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
3 *
4 * Copyright 2014 Mike Becker. All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions are met:
8 *
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 *
12 * 2. Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in the
14 * documentation and/or other materials provided with the distribution.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
17 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
19 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
20 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
21 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
22 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
23 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
24 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
26 * POSSIBILITY OF SUCH DAMAGE.
27 *
28 */
30 #include "rules.h"
31 #include "chess.h"
32 #include <string.h>
33 #include <stdlib.h>
34 #include <sys/time.h>
36 void gamestate_cleanup(GameState *gamestate) {
37 MoveList *elem;
38 elem = gamestate->movelist;
39 while (elem) {
40 MoveList *cur = elem;
41 elem = elem->next;
42 free(cur);
43 };
44 }
46 static void addmove(GameState* gamestate, Move *move) {
47 MoveList *elem = malloc(sizeof(MoveList));
48 elem->next = NULL;
49 elem->move = *move;
51 struct timeval curtimestamp;
52 gettimeofday(&curtimestamp, NULL);
53 elem->move.timestamp.tv_sec = curtimestamp.tv_sec;
54 elem->move.timestamp.tv_usec = curtimestamp.tv_usec;
56 if (gamestate->lastmove) {
57 struct movetimeval *lasttstamp = &(gamestate->lastmove->move.timestamp);
58 uint64_t sec = curtimestamp.tv_sec - lasttstamp->tv_sec;
59 suseconds_t micros;
60 if (curtimestamp.tv_usec < lasttstamp->tv_usec) {
61 micros = 1e6L-(lasttstamp->tv_usec - curtimestamp.tv_usec);
62 sec--;
63 } else {
64 micros = curtimestamp.tv_usec - lasttstamp->tv_usec;
65 }
67 elem->move.movetime.tv_sec = sec;
68 elem->move.movetime.tv_usec = micros;
70 gamestate->lastmove->next = elem;
71 gamestate->lastmove = elem;
72 } else {
73 elem->move.movetime.tv_usec = 0;
74 elem->move.movetime.tv_sec = 0;
75 gamestate->movelist = gamestate->lastmove = elem;
76 }
77 }
79 char getpiecechr(uint8_t piece) {
80 switch (piece & PIECE_MASK) {
81 case ROOK: return 'R';
82 case KNIGHT: return 'N';
83 case BISHOP: return 'B';
84 case QUEEN: return 'Q';
85 case KING: return 'K';
86 default: return '\0';
87 }
88 }
90 uint8_t getpiece(char c) {
91 switch (c) {
92 case 'R': return ROOK;
93 case 'N': return KNIGHT;
94 case 'B': return BISHOP;
95 case 'Q': return QUEEN;
96 case 'K': return KING;
97 default: return 0;
98 }
99 }
101 void apply_move(GameState *gamestate, Move *move) {
102 uint8_t piece = move->piece & PIECE_MASK;
103 uint8_t color = move->piece & COLOR_MASK;
105 /* en passant capture */
106 if (move->capture && piece == PAWN &&
107 mdst(gamestate->board, move) == 0) {
108 gamestate->board[move->fromrow][move->tofile] = 0;
109 }
111 /* remove old en passant threats */
112 for (uint8_t file = 0 ; file < 8 ; file++) {
113 gamestate->board[3][file] &= ~ENPASSANT_THREAT;
114 gamestate->board[4][file] &= ~ENPASSANT_THREAT;
115 }
117 /* add new en passant threat */
118 if (piece == PAWN && (
119 (move->fromrow == 1 && move->torow == 3) ||
120 (move->fromrow == 6 && move->torow == 4))) {
121 move->piece |= ENPASSANT_THREAT;
122 }
124 /* move (and maybe capture or promote) */
125 msrc(gamestate->board, move) = 0;
126 if (move->promotion) {
127 mdst(gamestate->board, move) = move->promotion;
128 } else {
129 mdst(gamestate->board, move) = move->piece;
130 }
132 /* castling */
133 if (piece == KING &&
134 move->fromfile == fileidx('e')) {
136 if (move->tofile == fileidx('g')) {
137 gamestate->board[move->torow][fileidx('h')] = 0;
138 gamestate->board[move->torow][fileidx('f')] = color|ROOK;
139 } else if (move->tofile == fileidx('c')) {
140 gamestate->board[move->torow][fileidx('a')] = 0;
141 gamestate->board[move->torow][fileidx('d')] = color|ROOK;
142 }
143 }
145 addmove(gamestate, move);
146 }
148 static _Bool validate_move_rules(GameState *gamestate, Move *move) {
149 /* validate indices (don't trust opponent) */
150 if (!chkidx(move)) {
151 return 0;
152 }
154 /* must move */
155 if (move->fromfile == move->tofile && move->fromrow == move->torow) {
156 return 0;
157 }
159 /* does piece exist */
160 if ((msrc(gamestate->board, move)&(PIECE_MASK|COLOR_MASK))
161 != (move->piece&(PIECE_MASK|COLOR_MASK))) {
162 return 0;
163 }
165 /* can't capture own pieces */
166 if ((mdst(gamestate->board, move) & COLOR_MASK)
167 == (move->piece & COLOR_MASK)) {
168 return 0;
169 }
171 /* must capture, if and only if destination is occupied */
172 if ((mdst(gamestate->board, move) == 0 && move->capture) ||
173 (mdst(gamestate->board, move) != 0 && !move->capture)) {
174 return 0;
175 }
177 /* validate individual rules */
178 switch (move->piece & PIECE_MASK) {
179 case PAWN:
180 return pawn_chkrules(gamestate, move) &&
181 !pawn_isblocked(gamestate, move);
182 case ROOK:
183 return rook_chkrules(move) &&
184 !rook_isblocked(gamestate, move);
185 case KNIGHT:
186 return knight_chkrules(move); /* knight is never blocked */
187 case BISHOP:
188 return bishop_chkrules(move) &&
189 !bishop_isblocked(gamestate, move);
190 case QUEEN:
191 return queen_chkrules(move) &&
192 !queen_isblocked(gamestate, move);
193 case KING:
194 return king_chkrules(gamestate, move) &&
195 !king_isblocked(gamestate, move);
196 default:
197 return 0;
198 }
199 }
201 _Bool validate_move(GameState *gamestate, Move *move) {
202 // TODO: provide more details via a return code
204 _Bool result = validate_move_rules(gamestate, move);
206 /* cancel processing to save resources */
207 if (!result) {
208 return 0;
209 }
211 /* find kings for check validation */
212 uint8_t piececolor = (move->piece & COLOR_MASK);
214 uint8_t mykingfile = 0, mykingrow = 0, opkingfile = 0, opkingrow = 0;
215 for (uint8_t row = 0 ; row < 8 ; row++) {
216 for (uint8_t file = 0 ; file < 8 ; file++) {
217 if (gamestate->board[row][file] ==
218 (piececolor == WHITE?WKING:BKING)) {
219 mykingfile = file;
220 mykingrow = row;
221 } else if (gamestate->board[row][file] ==
222 (piececolor == WHITE?BKING:WKING)) {
223 opkingfile = file;
224 opkingrow = row;
225 }
226 }
227 }
229 /* simulation move for check validation */
230 GameState simulation = *gamestate;
231 Move simmove = *move;
232 apply_move(&simulation, &simmove);
234 /* don't move into or stay in check position */
235 if (is_covered(&simulation, mykingrow, mykingfile,
236 opponent_color(piececolor))) {
237 return 0;
238 }
240 /* correct check and checkmate flags (move is still valid) */
241 Move threats[16];
242 uint8_t threatcount;
243 move->check = get_threats(&simulation, opkingrow, opkingfile,
244 piececolor, threats, &threatcount);
246 if (move->check) {
247 /* determine possible escape fields */
248 _Bool canescape = 0;
249 for (int dr = -1 ; dr <= 1 && !canescape ; dr++) {
250 for (int df = -1 ; df <= 1 && !canescape ; df++) {
251 if (!(dr == 0 && df == 0) &&
252 isidx(opkingrow + dr) && isidx(opkingfile + df)) {
254 /* escape field neither blocked nor covered */
255 if ((simulation.board[opkingrow + dr][opkingfile + df]
256 & COLOR_MASK) != opponent_color(piececolor)) {
257 canescape |= !is_covered(&simulation,
258 opkingrow + dr, opkingfile + df, piececolor);
259 }
260 }
261 }
262 }
263 /* can't escape, can he capture? */
264 if (!canescape && threatcount == 1) {
265 canescape = is_attacked(&simulation, threats[0].fromrow,
266 threats[0].fromfile, opponent_color(piececolor));
267 }
269 /* can't capture, can he block? */
270 if (!canescape && threatcount == 1) {
271 Move *threat = &(threats[0]);
272 uint8_t threatpiece = threat->piece & PIECE_MASK;
274 /* knight, pawns and the king cannot be blocked */
275 if (threatpiece == BISHOP || threatpiece == ROOK
276 || threatpiece == QUEEN) {
277 if (threat->fromrow == threat->torow) {
278 /* rook aspect (on row) */
279 int d = threat->tofile > threat->fromfile ? 1 : -1;
280 uint8_t file = threat->fromfile;
281 while (!canescape && file != threat->tofile - d) {
282 file += d;
283 canescape |= is_protected(&simulation,
284 threat->torow, file, opponent_color(piececolor));
285 }
286 } else if (threat->fromfile == threat->tofile) {
287 /* rook aspect (on file) */
288 int d = threat->torow > threat->fromrow ? 1 : -1;
289 uint8_t row = threat->fromrow;
290 while (!canescape && row != threat->torow - d) {
291 row += d;
292 canescape |= is_protected(&simulation,
293 row, threat->tofile, opponent_color(piececolor));
294 }
295 } else {
296 /* bishop aspect */
297 int dr = move->torow > move->fromrow ? 1 : -1;
298 int df = move->tofile > move->fromfile ? 1 : -1;
300 uint8_t row = move->fromrow;
301 uint8_t file = move->fromfile;
302 while (!canescape && file != move->tofile - df
303 && row != move->torow - dr) {
304 row += dr;
305 file += df;
306 canescape |= is_protected(&simulation, row, file,
307 opponent_color(piececolor));
308 }
309 }
310 }
311 }
313 if (!canescape) {
314 gamestate->checkmate = 1;
315 }
316 }
318 return 1;
319 }
321 _Bool get_threats(GameState *gamestate, uint8_t row, uint8_t file,
322 uint8_t color, Move *threats, uint8_t *threatcount) {
323 Move candidates[32];
324 int candidatecount = 0;
325 for (uint8_t r = 0 ; r < 8 ; r++) {
326 for (uint8_t f = 0 ; f < 8 ; f++) {
327 if ((gamestate->board[r][f] & COLOR_MASK) == color) {
328 // non-capturing move
329 memset(&(candidates[candidatecount]), 0, sizeof(Move));
330 candidates[candidatecount].piece = gamestate->board[r][f];
331 candidates[candidatecount].fromrow = r;
332 candidates[candidatecount].fromfile = f;
333 candidates[candidatecount].torow = row;
334 candidates[candidatecount].tofile = file;
335 candidatecount++;
337 // capturing move
338 memcpy(&(candidates[candidatecount]),
339 &(candidates[candidatecount-1]), sizeof(Move));
340 candidates[candidatecount].capture = 1;
341 candidatecount++;
342 }
343 }
344 }
346 if (threatcount) {
347 *threatcount = 0;
348 }
351 _Bool result = 0;
353 for (int i = 0 ; i < candidatecount ; i++) {
354 if (validate_move_rules(gamestate, &(candidates[i]))) {
355 result = 1;
356 if (threats && threatcount) {
357 threats[(*threatcount)++] = candidates[i];
358 }
359 }
360 }
362 return result;
363 }
365 _Bool is_pinned(GameState *gamestate, Move *move) {
366 uint8_t color = move->piece & COLOR_MASK;
368 uint8_t kingfile = 0, kingrow = 0;
369 for (uint8_t row = 0 ; row < 8 ; row++) {
370 for (uint8_t file = 0 ; file < 8 ; file++) {
371 if (gamestate->board[row][file] == (color|KING)) {
372 kingfile = file;
373 kingrow = row;
374 }
375 }
376 }
378 GameState simulation = *gamestate;
379 Move simmove = *move;
380 apply_move(&simulation, &simmove);
381 return is_covered(&simulation, kingrow, kingfile, opponent_color(color));
382 }
384 _Bool get_real_threats(GameState *gamestate, uint8_t row, uint8_t file,
385 uint8_t color, Move *threats, uint8_t *threatcount) {
387 if (threatcount) {
388 *threatcount = 0;
389 }
391 Move candidates[16];
392 uint8_t candidatecount;
393 if (get_threats(gamestate, row, file, color, candidates, &candidatecount)) {
395 _Bool result = 0;
396 uint8_t kingfile = 0, kingrow = 0;
397 for (uint8_t row = 0 ; row < 8 ; row++) {
398 for (uint8_t file = 0 ; file < 8 ; file++) {
399 if (gamestate->board[row][file] == (color|KING)) {
400 kingfile = file;
401 kingrow = row;
402 }
403 }
404 }
406 for (uint8_t i = 0 ; i < candidatecount ; i++) {
407 GameState simulation = *gamestate;
408 Move simmove = candidates[i];
409 apply_move(&simulation, &simmove);
410 if (!is_covered(&simulation, kingrow, kingfile,
411 opponent_color(color))) {
412 result = 1;
413 if (threats && threatcount) {
414 threats[(*threatcount)++] = candidates[i];
415 }
416 }
417 }
419 return result;
420 } else {
421 return 0;
422 }
423 }
424 #include <ncurses.h>
425 static int getlocation(GameState *gamestate, Move *move) {
427 uint8_t color = move->piece & COLOR_MASK;
428 _Bool incheck = gamestate->lastmove?gamestate->lastmove->move.check:0;
430 Move threats[16], *threat = NULL;
431 uint8_t threatcount;
433 if (get_threats(gamestate, move->torow, move->tofile, color,
434 threats, &threatcount)) {
436 // find threats for the specified position
437 for (uint8_t i = 0 ; i < threatcount ; i++) {
438 if ((threats[i].piece & (PIECE_MASK | COLOR_MASK))
439 == move->piece &&
440 (move->fromrow == POS_UNSPECIFIED ||
441 move->fromrow == threats[i].fromrow) &&
442 (move->fromfile == POS_UNSPECIFIED ||
443 move->fromfile == threats[i].fromfile)) {
445 if (threat) {
446 return AMBIGUOUS_MOVE;
447 } else {
448 threat = &(threats[i]);
449 }
450 }
451 }
453 // can't threaten specified position
454 if (!threat) {
455 return INVALID_POSITION;
456 }
458 // found threat is no real threat
459 if (is_pinned(gamestate, threat)) {
460 return incheck?KING_IN_CHECK:PIECE_PINNED;
461 } else {
462 memcpy(move, threat, sizeof(Move));
463 return VALID_MOVE_SYNTAX;
464 }
465 } else {
466 return INVALID_POSITION;
467 }
468 }
470 int eval_move(GameState *gamestate, char *mstr, Move *move) {
471 memset(move, 0, sizeof(Move));
472 move->fromfile = POS_UNSPECIFIED;
473 move->fromrow = POS_UNSPECIFIED;
475 size_t len = strlen(mstr);
477 /* evaluate check/checkmate flags */
478 if (mstr[len-1] == '+') {
479 len--; mstr[len] = '\0';
480 move->check = 1;
481 } else if (mstr[len-1] == '#') {
482 len--; mstr[len] = '\0';
483 /* ignore - validation should set game state */
484 }
486 /* evaluate promotion */
487 if (len > 3 && mstr[len-2] == '=') {
488 move->promotion = getpiece(mstr[len-1]);
489 if (!move->promotion) {
490 return INVALID_MOVE_SYNTAX;
491 } else {
492 move->promotion |= gamestate->mycolor;
493 len -= 2;
494 mstr[len] = 0;
495 }
496 }
498 if (len == 2) {
499 /* pawn move (e.g. "e4") */
500 move->piece = PAWN;
501 move->tofile = fileidx(mstr[0]);
502 move->torow = rowidx(mstr[1]);
503 } else if (len == 3) {
504 if (strcmp(mstr, "O-O") == 0) {
505 /* king side castling */
506 move->piece = KING;
507 move->fromfile = fileidx('e');
508 move->tofile = fileidx('g');
509 move->fromrow = move->torow = gamestate->mycolor == WHITE ? 0 : 7;
510 } else {
511 /* move (e.g. "Nf3") */
512 move->piece = getpiece(mstr[0]);
513 move->tofile = fileidx(mstr[1]);
514 move->torow = rowidx(mstr[2]);
515 }
517 } else if (len == 4) {
518 move->piece = getpiece(mstr[0]);
519 if (!move->piece) {
520 move->piece = PAWN;
521 move->fromfile = fileidx(mstr[0]);
522 }
523 if (mstr[1] == 'x') {
524 /* capture (e.g. "Nxf3", "dxe5") */
525 move->capture = 1;
526 } else {
527 /* move (e.g. "Ndf3", "N2c3", "e2e4") */
528 if (isfile(mstr[1])) {
529 move->fromfile = fileidx(mstr[1]);
530 if (move->piece == PAWN) {
531 move->piece = 0;
532 }
533 } else {
534 move->fromrow = rowidx(mstr[1]);
535 }
536 }
537 move->tofile = fileidx(mstr[2]);
538 move->torow = rowidx(mstr[3]);
539 } else if (len == 5) {
540 if (strcmp(mstr, "O-O-O") == 0) {
541 /* queen side castling "O-O-O" */
542 move->piece = KING;
543 move->fromfile = fileidx('e');
544 move->tofile = fileidx('c');
545 move->fromrow = move->torow = gamestate->mycolor == WHITE ? 0 : 7;
546 } else {
547 move->piece = getpiece(mstr[0]);
548 if (mstr[2] == 'x') {
549 move->capture = 1;
550 if (move->piece) {
551 /* capture (e.g. "Ndxf3") */
552 move->fromfile = fileidx(mstr[1]);
553 } else {
554 /* long notation capture (e.g. "e5xf6") */
555 move->piece = PAWN;
556 move->fromfile = fileidx(mstr[0]);
557 move->fromrow = rowidx(mstr[1]);
558 }
559 } else {
560 /* long notation move (e.g. "Nc5a4") */
561 move->fromfile = fileidx(mstr[1]);
562 move->fromrow = rowidx(mstr[2]);
563 }
564 move->tofile = fileidx(mstr[3]);
565 move->torow = rowidx(mstr[4]);
566 }
567 } else if (len == 6) {
568 /* long notation capture (e.g. "Nc5xf3") */
569 if (mstr[3] == 'x') {
570 move->capture = 1;
571 move->piece = getpiece(mstr[0]);
572 move->fromfile = fileidx(mstr[1]);
573 move->fromrow = rowidx(mstr[2]);
574 move->tofile = fileidx(mstr[4]);
575 move->torow = rowidx(mstr[5]);
576 }
577 }
580 if (move->piece) {
581 if (move->piece == PAWN
582 && move->torow == (gamestate->mycolor==WHITE?7:0)
583 && !move->promotion) {
584 return NEED_PROMOTION;
585 }
587 move->piece |= gamestate->mycolor;
588 if (move->fromfile == POS_UNSPECIFIED
589 || move->fromrow == POS_UNSPECIFIED) {
590 return getlocation(gamestate, move);
591 } else {
592 return chkidx(move) ? VALID_MOVE_SYNTAX : INVALID_POSITION;
593 }
594 } else {
595 return INVALID_MOVE_SYNTAX;
596 }
597 }
599 _Bool is_protected(GameState *gamestate, uint8_t row, uint8_t file,
600 uint8_t color) {
602 Move threats[16];
603 uint8_t threatcount;
604 if (get_real_threats(gamestate, row, file, color, threats, &threatcount)) {
605 for (int i = 0 ; i < threatcount ; i++) {
606 if (threats[i].piece != (color|KING)) {
607 return 1;
608 }
609 }
610 return 0;
611 } else {
612 return 0;
613 }
614 }
616 uint16_t remaining_movetime(GameInfo *gameinfo, GameState *gamestate,
617 uint8_t color) {
618 if (!gameinfo->timecontrol) {
619 return 0;
620 }
622 if (gamestate->movelist) {
623 uint16_t time = gameinfo->time;
624 suseconds_t micros = 0;
626 MoveList *movelist = color == WHITE ?
627 gamestate->movelist : gamestate->movelist->next;
629 while (movelist) {
630 time += gameinfo->addtime;
632 struct movetimeval *movetime = &(movelist->move.movetime);
633 if (movetime->tv_sec >= time) {
634 return 0;
635 }
637 time -= movetime->tv_sec;
638 micros += movetime->tv_usec;
640 movelist = movelist->next ? movelist->next->next : NULL;
641 }
643 time_t sec;
644 movelist = gamestate->lastmove;
645 if ((movelist->move.piece & COLOR_MASK) != color) {
646 struct movetimeval *lastmovetstamp = &(movelist->move.timestamp);
647 struct timeval currenttstamp;
648 gettimeofday(¤ttstamp, NULL);
649 micros += currenttstamp.tv_usec - lastmovetstamp->tv_usec;
650 sec = currenttstamp.tv_sec - lastmovetstamp->tv_sec;
651 if (sec >= time) {
652 return 0;
653 }
655 time -= sec;
656 }
658 sec = micros / 1e6L;
660 if (sec >= time) {
661 return 0;
662 }
664 time -= sec;
666 return time;
667 } else {
668 return gameinfo->time;
669 }
670 }