Wed, 11 Jun 2014 15:38:01 +0200
added return code to move validation (for more informative messages) + fixed a bug where simulations added movelist items to the original gamestate
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 static GameState gamestate_copy_sim(GameState *gamestate) {
37 GameState simulation = *gamestate;
38 if (simulation.lastmove) {
39 MoveList *lastmovecopy = malloc(sizeof(MoveList));
40 *lastmovecopy = *(simulation.lastmove);
41 simulation.movelist = simulation.lastmove = lastmovecopy;
42 }
44 return simulation;
45 }
47 void gamestate_cleanup(GameState *gamestate) {
48 MoveList *elem;
49 elem = gamestate->movelist;
50 while (elem) {
51 MoveList *cur = elem;
52 elem = elem->next;
53 free(cur);
54 };
55 }
57 static void addmove(GameState* gamestate, Move *move) {
58 MoveList *elem = malloc(sizeof(MoveList));
59 elem->next = NULL;
60 elem->move = *move;
62 struct timeval curtimestamp;
63 gettimeofday(&curtimestamp, NULL);
64 elem->move.timestamp.tv_sec = curtimestamp.tv_sec;
65 elem->move.timestamp.tv_usec = curtimestamp.tv_usec;
67 if (gamestate->lastmove) {
68 struct movetimeval *lasttstamp = &(gamestate->lastmove->move.timestamp);
69 uint64_t sec = curtimestamp.tv_sec - lasttstamp->tv_sec;
70 suseconds_t micros;
71 if (curtimestamp.tv_usec < lasttstamp->tv_usec) {
72 micros = 1e6L-(lasttstamp->tv_usec - curtimestamp.tv_usec);
73 sec--;
74 } else {
75 micros = curtimestamp.tv_usec - lasttstamp->tv_usec;
76 }
78 elem->move.movetime.tv_sec = sec;
79 elem->move.movetime.tv_usec = micros;
81 gamestate->lastmove->next = elem;
82 gamestate->lastmove = elem;
83 } else {
84 elem->move.movetime.tv_usec = 0;
85 elem->move.movetime.tv_sec = 0;
86 gamestate->movelist = gamestate->lastmove = elem;
87 }
88 }
90 char getpiecechr(uint8_t piece) {
91 switch (piece & PIECE_MASK) {
92 case ROOK: return 'R';
93 case KNIGHT: return 'N';
94 case BISHOP: return 'B';
95 case QUEEN: return 'Q';
96 case KING: return 'K';
97 default: return '\0';
98 }
99 }
101 uint8_t getpiece(char c) {
102 switch (c) {
103 case 'R': return ROOK;
104 case 'N': return KNIGHT;
105 case 'B': return BISHOP;
106 case 'Q': return QUEEN;
107 case 'K': return KING;
108 default: return 0;
109 }
110 }
112 void apply_move(GameState *gamestate, Move *move) {
113 uint8_t piece = move->piece & PIECE_MASK;
114 uint8_t color = move->piece & COLOR_MASK;
116 /* en passant capture */
117 if (move->capture && piece == PAWN &&
118 mdst(gamestate->board, move) == 0) {
119 gamestate->board[move->fromrow][move->tofile] = 0;
120 }
122 /* remove old en passant threats */
123 for (uint8_t file = 0 ; file < 8 ; file++) {
124 gamestate->board[3][file] &= ~ENPASSANT_THREAT;
125 gamestate->board[4][file] &= ~ENPASSANT_THREAT;
126 }
128 /* add new en passant threat */
129 if (piece == PAWN && (
130 (move->fromrow == 1 && move->torow == 3) ||
131 (move->fromrow == 6 && move->torow == 4))) {
132 move->piece |= ENPASSANT_THREAT;
133 }
135 /* move (and maybe capture or promote) */
136 msrc(gamestate->board, move) = 0;
137 if (move->promotion) {
138 mdst(gamestate->board, move) = move->promotion;
139 } else {
140 mdst(gamestate->board, move) = move->piece;
141 }
143 /* castling */
144 if (piece == KING &&
145 move->fromfile == fileidx('e')) {
147 if (move->tofile == fileidx('g')) {
148 gamestate->board[move->torow][fileidx('h')] = 0;
149 gamestate->board[move->torow][fileidx('f')] = color|ROOK;
150 } else if (move->tofile == fileidx('c')) {
151 gamestate->board[move->torow][fileidx('a')] = 0;
152 gamestate->board[move->torow][fileidx('d')] = color|ROOK;
153 }
154 }
156 addmove(gamestate, move);
157 }
159 static int validate_move_rules(GameState *gamestate, Move *move) {
160 /* validate indices (don't trust opponent) */
161 if (!chkidx(move)) {
162 return INVALID_POSITION;
163 }
165 /* must move */
166 if (move->fromfile == move->tofile && move->fromrow == move->torow) {
167 return INVALID_MOVE_SYNTAX;
168 }
170 /* does piece exist */
171 if ((msrc(gamestate->board, move)&(PIECE_MASK|COLOR_MASK))
172 != (move->piece&(PIECE_MASK|COLOR_MASK))) {
173 return INVALID_POSITION;
174 }
176 /* can't capture own pieces */
177 if ((mdst(gamestate->board, move) & COLOR_MASK)
178 == (move->piece & COLOR_MASK)) {
179 return RULES_VIOLATED;
180 }
182 /* must capture, if and only if destination is occupied */
183 if ((mdst(gamestate->board, move) == 0 && move->capture) ||
184 (mdst(gamestate->board, move) != 0 && !move->capture)) {
185 return INVALID_MOVE_SYNTAX;
186 }
188 /* validate individual rules */
189 _Bool chkrules;
190 switch (move->piece & PIECE_MASK) {
191 case PAWN:
192 chkrules = pawn_chkrules(gamestate, move) &&
193 !pawn_isblocked(gamestate, move);
194 break;
195 case ROOK:
196 chkrules = rook_chkrules(move) &&
197 !rook_isblocked(gamestate, move);
198 break;
199 case KNIGHT:
200 chkrules = knight_chkrules(move); /* knight is never blocked */
201 break;
202 case BISHOP:
203 chkrules = bishop_chkrules(move) &&
204 !bishop_isblocked(gamestate, move);
205 break;
206 case QUEEN:
207 chkrules = queen_chkrules(move) &&
208 !queen_isblocked(gamestate, move);
209 break;
210 case KING:
211 chkrules = king_chkrules(gamestate, move) &&
212 !king_isblocked(gamestate, move);
213 break;
214 default:
215 return INVALID_MOVE_SYNTAX;
216 }
218 return chkrules ? VALID_MOVE_SEMANTICS : RULES_VIOLATED;
219 }
221 int validate_move(GameState *gamestate, Move *move) {
223 int result = validate_move_rules(gamestate, move);
225 /* cancel processing to save resources */
226 if (result != VALID_MOVE_SEMANTICS) {
227 return result;
228 }
230 /* find kings for check validation */
231 uint8_t piececolor = (move->piece & COLOR_MASK);
233 uint8_t mykingfile = 0, mykingrow = 0, opkingfile = 0, opkingrow = 0;
234 for (uint8_t row = 0 ; row < 8 ; row++) {
235 for (uint8_t file = 0 ; file < 8 ; file++) {
236 if (gamestate->board[row][file] ==
237 (piececolor == WHITE?WKING:BKING)) {
238 mykingfile = file;
239 mykingrow = row;
240 } else if (gamestate->board[row][file] ==
241 (piececolor == WHITE?BKING:WKING)) {
242 opkingfile = file;
243 opkingrow = row;
244 }
245 }
246 }
248 /* simulate move for check validation */
249 GameState simulation = gamestate_copy_sim(gamestate);
250 Move simmove = *move;
251 apply_move(&simulation, &simmove);
253 /* don't move into or stay in check position */
254 if (is_covered(&simulation, mykingrow, mykingfile,
255 opponent_color(piececolor))) {
257 gamestate_cleanup(&simulation);
258 if ((move->piece & PIECE_MASK) == KING) {
259 return KING_MOVES_INTO_CHECK;
260 } else {
261 /* last move is always not null in this case */
262 return gamestate->lastmove->move.check ?
263 KING_IN_CHECK : PIECE_PINNED;
264 }
265 }
267 /* correct check and checkmate flags (move is still valid) */
268 Move threats[16];
269 uint8_t threatcount;
270 move->check = get_threats(&simulation, opkingrow, opkingfile,
271 piececolor, threats, &threatcount);
273 if (move->check) {
274 /* determine possible escape fields */
275 _Bool canescape = 0;
276 for (int dr = -1 ; dr <= 1 && !canescape ; dr++) {
277 for (int df = -1 ; df <= 1 && !canescape ; df++) {
278 if (!(dr == 0 && df == 0) &&
279 isidx(opkingrow + dr) && isidx(opkingfile + df)) {
281 /* escape field neither blocked nor covered */
282 if ((simulation.board[opkingrow + dr][opkingfile + df]
283 & COLOR_MASK) != opponent_color(piececolor)) {
284 canescape |= !is_covered(&simulation,
285 opkingrow + dr, opkingfile + df, piececolor);
286 }
287 }
288 }
289 }
290 /* can't escape, can he capture? */
291 if (!canescape && threatcount == 1) {
292 canescape = is_attacked(&simulation, threats[0].fromrow,
293 threats[0].fromfile, opponent_color(piececolor));
294 }
296 /* can't capture, can he block? */
297 if (!canescape && threatcount == 1) {
298 Move *threat = &(threats[0]);
299 uint8_t threatpiece = threat->piece & PIECE_MASK;
301 /* knight, pawns and the king cannot be blocked */
302 if (threatpiece == BISHOP || threatpiece == ROOK
303 || threatpiece == QUEEN) {
304 if (threat->fromrow == threat->torow) {
305 /* rook aspect (on row) */
306 int d = threat->tofile > threat->fromfile ? 1 : -1;
307 uint8_t file = threat->fromfile;
308 while (!canescape && file != threat->tofile - d) {
309 file += d;
310 canescape |= is_protected(&simulation,
311 threat->torow, file, opponent_color(piececolor));
312 }
313 } else if (threat->fromfile == threat->tofile) {
314 /* rook aspect (on file) */
315 int d = threat->torow > threat->fromrow ? 1 : -1;
316 uint8_t row = threat->fromrow;
317 while (!canescape && row != threat->torow - d) {
318 row += d;
319 canescape |= is_protected(&simulation,
320 row, threat->tofile, opponent_color(piececolor));
321 }
322 } else {
323 /* bishop aspect */
324 int dr = move->torow > move->fromrow ? 1 : -1;
325 int df = move->tofile > move->fromfile ? 1 : -1;
327 uint8_t row = move->fromrow;
328 uint8_t file = move->fromfile;
329 while (!canescape && file != move->tofile - df
330 && row != move->torow - dr) {
331 row += dr;
332 file += df;
333 canescape |= is_protected(&simulation, row, file,
334 opponent_color(piececolor));
335 }
336 }
337 }
338 }
340 if (!canescape) {
341 gamestate->checkmate = 1;
342 }
343 }
345 gamestate_cleanup(&simulation);
347 return VALID_MOVE_SEMANTICS;
348 }
350 _Bool get_threats(GameState *gamestate, uint8_t row, uint8_t file,
351 uint8_t color, Move *threats, uint8_t *threatcount) {
352 Move candidates[32];
353 int candidatecount = 0;
354 for (uint8_t r = 0 ; r < 8 ; r++) {
355 for (uint8_t f = 0 ; f < 8 ; f++) {
356 if ((gamestate->board[r][f] & COLOR_MASK) == color) {
357 // non-capturing move
358 memset(&(candidates[candidatecount]), 0, sizeof(Move));
359 candidates[candidatecount].piece = gamestate->board[r][f];
360 candidates[candidatecount].fromrow = r;
361 candidates[candidatecount].fromfile = f;
362 candidates[candidatecount].torow = row;
363 candidates[candidatecount].tofile = file;
364 candidatecount++;
366 // capturing move
367 memcpy(&(candidates[candidatecount]),
368 &(candidates[candidatecount-1]), sizeof(Move));
369 candidates[candidatecount].capture = 1;
370 candidatecount++;
371 }
372 }
373 }
375 if (threatcount) {
376 *threatcount = 0;
377 }
380 _Bool result = 0;
382 for (int i = 0 ; i < candidatecount ; i++) {
383 if (validate_move_rules(gamestate, &(candidates[i]))
384 == VALID_MOVE_SEMANTICS) {
385 result = 1;
386 if (threats && threatcount) {
387 threats[(*threatcount)++] = candidates[i];
388 }
389 }
390 }
392 return result;
393 }
395 _Bool is_pinned(GameState *gamestate, Move *move) {
396 uint8_t color = move->piece & COLOR_MASK;
398 uint8_t kingfile = 0, kingrow = 0;
399 for (uint8_t row = 0 ; row < 8 ; row++) {
400 for (uint8_t file = 0 ; file < 8 ; file++) {
401 if (gamestate->board[row][file] == (color|KING)) {
402 kingfile = file;
403 kingrow = row;
404 }
405 }
406 }
408 GameState simulation = gamestate_copy_sim(gamestate);
409 Move simmove = *move;
410 apply_move(&simulation, &simmove);
411 _Bool covered = is_covered(&simulation,
412 kingrow, kingfile, opponent_color(color));
413 gamestate_cleanup(&simulation);
415 return covered;
416 }
418 _Bool get_real_threats(GameState *gamestate, uint8_t row, uint8_t file,
419 uint8_t color, Move *threats, uint8_t *threatcount) {
421 if (threatcount) {
422 *threatcount = 0;
423 }
425 Move candidates[16];
426 uint8_t candidatecount;
427 if (get_threats(gamestate, row, file, color, candidates, &candidatecount)) {
429 _Bool result = 0;
430 uint8_t kingfile = 0, kingrow = 0;
431 for (uint8_t row = 0 ; row < 8 ; row++) {
432 for (uint8_t file = 0 ; file < 8 ; file++) {
433 if (gamestate->board[row][file] == (color|KING)) {
434 kingfile = file;
435 kingrow = row;
436 }
437 }
438 }
440 for (uint8_t i = 0 ; i < candidatecount ; i++) {
441 GameState simulation = gamestate_copy_sim(gamestate);
442 Move simmove = candidates[i];
443 apply_move(&simulation, &simmove);
444 if (!is_covered(&simulation, kingrow, kingfile,
445 opponent_color(color))) {
446 result = 1;
447 if (threats && threatcount) {
448 threats[(*threatcount)++] = candidates[i];
449 }
450 }
451 gamestate_cleanup(&simulation);
452 }
454 return result;
455 } else {
456 return 0;
457 }
458 }
460 static int getlocation(GameState *gamestate, Move *move) {
462 uint8_t color = move->piece & COLOR_MASK;
463 _Bool incheck = gamestate->lastmove?gamestate->lastmove->move.check:0;
465 Move threats[16], *threat = NULL;
466 uint8_t threatcount;
468 if (get_threats(gamestate, move->torow, move->tofile, color,
469 threats, &threatcount)) {
471 // find threats for the specified position
472 for (uint8_t i = 0 ; i < threatcount ; i++) {
473 if ((threats[i].piece & (PIECE_MASK | COLOR_MASK))
474 == move->piece &&
475 (move->fromrow == POS_UNSPECIFIED ||
476 move->fromrow == threats[i].fromrow) &&
477 (move->fromfile == POS_UNSPECIFIED ||
478 move->fromfile == threats[i].fromfile)) {
480 if (threat) {
481 return AMBIGUOUS_MOVE;
482 } else {
483 threat = &(threats[i]);
484 }
485 }
486 }
488 // can't threaten specified position
489 if (!threat) {
490 return INVALID_POSITION;
491 }
493 // found threat is no real threat
494 if (is_pinned(gamestate, threat)) {
495 return incheck?KING_IN_CHECK:PIECE_PINNED;
496 } else {
497 memcpy(move, threat, sizeof(Move));
498 return VALID_MOVE_SYNTAX;
499 }
500 } else {
501 return INVALID_POSITION;
502 }
503 }
505 int eval_move(GameState *gamestate, char *mstr, Move *move) {
506 memset(move, 0, sizeof(Move));
507 move->fromfile = POS_UNSPECIFIED;
508 move->fromrow = POS_UNSPECIFIED;
510 size_t len = strlen(mstr);
511 if (len < 1 || len > 6) {
512 return INVALID_MOVE_SYNTAX;
513 }
515 /* evaluate check/checkmate flags */
516 if (mstr[len-1] == '+') {
517 len--; mstr[len] = '\0';
518 move->check = 1;
519 } else if (mstr[len-1] == '#') {
520 len--; mstr[len] = '\0';
521 /* ignore - validation should set game state */
522 }
524 /* evaluate promotion */
525 if (len > 3 && mstr[len-2] == '=') {
526 move->promotion = getpiece(mstr[len-1]);
527 if (!move->promotion) {
528 return INVALID_MOVE_SYNTAX;
529 } else {
530 move->promotion |= gamestate->mycolor;
531 len -= 2;
532 mstr[len] = 0;
533 }
534 }
536 if (len == 2) {
537 /* pawn move (e.g. "e4") */
538 move->piece = PAWN;
539 move->tofile = fileidx(mstr[0]);
540 move->torow = rowidx(mstr[1]);
541 } else if (len == 3) {
542 if (strcmp(mstr, "O-O") == 0) {
543 /* king side castling */
544 move->piece = KING;
545 move->fromfile = fileidx('e');
546 move->tofile = fileidx('g');
547 move->fromrow = move->torow = gamestate->mycolor == WHITE ? 0 : 7;
548 } else {
549 /* move (e.g. "Nf3") */
550 move->piece = getpiece(mstr[0]);
551 move->tofile = fileidx(mstr[1]);
552 move->torow = rowidx(mstr[2]);
553 }
554 } else if (len == 4) {
555 move->piece = getpiece(mstr[0]);
556 if (!move->piece) {
557 move->piece = PAWN;
558 move->fromfile = fileidx(mstr[0]);
559 }
560 if (mstr[1] == 'x') {
561 /* capture (e.g. "Nxf3", "dxe5") */
562 move->capture = 1;
563 } else {
564 /* move (e.g. "Ndf3", "N2c3", "e2e4") */
565 if (isfile(mstr[1])) {
566 move->fromfile = fileidx(mstr[1]);
567 if (move->piece == PAWN) {
568 move->piece = 0;
569 }
570 } else {
571 move->fromrow = rowidx(mstr[1]);
572 }
573 }
574 move->tofile = fileidx(mstr[2]);
575 move->torow = rowidx(mstr[3]);
576 } else if (len == 5) {
577 if (strcmp(mstr, "O-O-O") == 0) {
578 /* queen side castling "O-O-O" */
579 move->piece = KING;
580 move->fromfile = fileidx('e');
581 move->tofile = fileidx('c');
582 move->fromrow = move->torow = gamestate->mycolor == WHITE ? 0 : 7;
583 } else {
584 move->piece = getpiece(mstr[0]);
585 if (mstr[2] == 'x') {
586 move->capture = 1;
587 if (move->piece) {
588 /* capture (e.g. "Ndxf3") */
589 move->fromfile = fileidx(mstr[1]);
590 } else {
591 /* long notation capture (e.g. "e5xf6") */
592 move->piece = PAWN;
593 move->fromfile = fileidx(mstr[0]);
594 move->fromrow = rowidx(mstr[1]);
595 }
596 } else {
597 /* long notation move (e.g. "Nc5a4") */
598 move->fromfile = fileidx(mstr[1]);
599 move->fromrow = rowidx(mstr[2]);
600 }
601 move->tofile = fileidx(mstr[3]);
602 move->torow = rowidx(mstr[4]);
603 }
604 } else if (len == 6) {
605 /* long notation capture (e.g. "Nc5xf3") */
606 if (mstr[3] == 'x') {
607 move->capture = 1;
608 move->piece = getpiece(mstr[0]);
609 move->fromfile = fileidx(mstr[1]);
610 move->fromrow = rowidx(mstr[2]);
611 move->tofile = fileidx(mstr[4]);
612 move->torow = rowidx(mstr[5]);
613 }
614 }
617 if (move->piece) {
618 if (move->piece == PAWN
619 && move->torow == (gamestate->mycolor==WHITE?7:0)
620 && !move->promotion) {
621 return NEED_PROMOTION;
622 }
624 move->piece |= gamestate->mycolor;
625 if (move->fromfile == POS_UNSPECIFIED
626 || move->fromrow == POS_UNSPECIFIED) {
627 return getlocation(gamestate, move);
628 } else {
629 return chkidx(move) ? VALID_MOVE_SYNTAX : INVALID_POSITION;
630 }
631 } else {
632 return INVALID_MOVE_SYNTAX;
633 }
634 }
636 _Bool is_protected(GameState *gamestate, uint8_t row, uint8_t file,
637 uint8_t color) {
639 Move threats[16];
640 uint8_t threatcount;
641 if (get_real_threats(gamestate, row, file, color, threats, &threatcount)) {
642 for (int i = 0 ; i < threatcount ; i++) {
643 if (threats[i].piece != (color|KING)) {
644 return 1;
645 }
646 }
647 return 0;
648 } else {
649 return 0;
650 }
651 }
653 uint16_t remaining_movetime(GameInfo *gameinfo, GameState *gamestate,
654 uint8_t color) {
655 if (!gameinfo->timecontrol) {
656 return 0;
657 }
659 if (gamestate->movelist) {
660 uint16_t time = gameinfo->time;
661 suseconds_t micros = 0;
663 MoveList *movelist = color == WHITE ?
664 gamestate->movelist : gamestate->movelist->next;
666 while (movelist) {
667 time += gameinfo->addtime;
669 struct movetimeval *movetime = &(movelist->move.movetime);
670 if (movetime->tv_sec >= time) {
671 return 0;
672 }
674 time -= movetime->tv_sec;
675 micros += movetime->tv_usec;
677 movelist = movelist->next ? movelist->next->next : NULL;
678 }
680 time_t sec;
681 movelist = gamestate->lastmove;
682 if ((movelist->move.piece & COLOR_MASK) != color) {
683 struct movetimeval *lastmovetstamp = &(movelist->move.timestamp);
684 struct timeval currenttstamp;
685 gettimeofday(¤ttstamp, NULL);
686 micros += currenttstamp.tv_usec - lastmovetstamp->tv_usec;
687 sec = currenttstamp.tv_sec - lastmovetstamp->tv_sec;
688 if (sec >= time) {
689 return 0;
690 }
692 time -= sec;
693 }
695 sec = micros / 1e6L;
697 if (sec >= time) {
698 return 0;
699 }
701 time -= sec;
703 return time;
704 } else {
705 return gameinfo->time;
706 }
707 }