Mercurial > hg > terminal-chess / file revision
src/chess/rules.c@ebe0c961e9a6
src/chess/rules.c
Thu, 10 Apr 2014 11:44:55 +0200
- author
- Mike Becker <universe@uap-core.de>
- date
- Thu, 10 Apr 2014 11:44:55 +0200
- changeset 36
- ebe0c961e9a6
- parent 33
- 866025982aa9
- child 40
- 47162a7621da
- permissions
- -rw-r--r--
reduced awesome great nanosecond precision so we can compile on OS X
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 gettimeofday(&(elem->move.timestamp), NULL);
53 if (gamestate->lastmove) {
54 struct timeval *lasttstamp = &(gamestate->lastmove->move.timestamp);
55 time_t sec = elem->move.timestamp.tv_sec - lasttstamp->tv_sec;
56 suseconds_t micros;
57 if (elem->move.timestamp.tv_usec < lasttstamp->tv_usec) {
58 micros = 1e6L-(lasttstamp->tv_usec - elem->move.timestamp.tv_usec);
59 sec--;
60 } else {
61 micros = elem->move.timestamp.tv_usec - lasttstamp->tv_usec;
62 }
64 elem->move.movetime.tv_sec = sec;
65 elem->move.movetime.tv_usec = micros;
67 gamestate->lastmove->next = elem;
68 gamestate->lastmove = elem;
69 } else {
70 elem->move.movetime.tv_usec = 0;
71 elem->move.movetime.tv_sec = 0;
72 gamestate->movelist = gamestate->lastmove = elem;
73 }
74 }
76 char getpiecechr(uint8_t piece) {
77 switch (piece & PIECE_MASK) {
78 case ROOK: return 'R';
79 case KNIGHT: return 'N';
80 case BISHOP: return 'B';
81 case QUEEN: return 'Q';
82 case KING: return 'K';
83 default: return '\0';
84 }
85 }
87 uint8_t getpiece(char c) {
88 switch (c) {
89 case 'R': return ROOK;
90 case 'N': return KNIGHT;
91 case 'B': return BISHOP;
92 case 'Q': return QUEEN;
93 case 'K': return KING;
94 default: return 0;
95 }
96 }
98 static int getlocation(GameState *gamestate, Move *move) {
99 uint8_t piece = move->piece & PIECE_MASK;
100 switch (piece) {
101 case PAWN: return pawn_getlocation(gamestate, move);
102 case ROOK: return rook_getlocation(gamestate, move);
103 case KNIGHT: return knight_getlocation(gamestate, move);
104 case BISHOP: return bishop_getlocation(gamestate, move);
105 case QUEEN: return queen_getlocation(gamestate, move);
106 case KING: return king_getlocation(gamestate, move);
107 default: return INVALID_MOVE_SYNTAX;
108 }
109 }
111 void apply_move(GameState *gamestate, Move *move) {
112 uint8_t piece = move->piece & PIECE_MASK;
113 uint8_t color = move->piece & COLOR_MASK;
115 /* en passant capture */
116 if (move->capture && piece == PAWN &&
117 mdst(gamestate->board, move) == 0) {
118 gamestate->board[move->fromrow][move->tofile] = 0;
119 }
121 /* remove old en passant threats */
122 for (uint8_t file = 0 ; file < 8 ; file++) {
123 gamestate->board[3][file] &= ~ENPASSANT_THREAT;
124 gamestate->board[4][file] &= ~ENPASSANT_THREAT;
125 }
127 /* add new en passant threat */
128 if (piece == PAWN && (
129 (move->fromrow == 1 && move->torow == 3) ||
130 (move->fromrow == 6 && move->torow == 4))) {
131 move->piece |= ENPASSANT_THREAT;
132 }
134 /* move (and maybe capture or promote) */
135 msrc(gamestate->board, move) = 0;
136 if (move->promotion) {
137 mdst(gamestate->board, move) = move->promotion;
138 } else {
139 mdst(gamestate->board, move) = move->piece;
140 }
142 /* castling */
143 if (piece == KING &&
144 move->fromfile == fileidx('e')) {
146 if (move->tofile == fileidx('g')) {
147 gamestate->board[move->torow][fileidx('h')] = 0;
148 gamestate->board[move->torow][fileidx('f')] = color|ROOK;
149 } else if (move->tofile == fileidx('c')) {
150 gamestate->board[move->torow][fileidx('a')] = 0;
151 gamestate->board[move->torow][fileidx('d')] = color|ROOK;
152 }
153 }
155 addmove(gamestate, move);
156 }
158 static _Bool validate_move_rules(GameState *gamestate, Move *move) {
159 /* validate indices (don't trust opponent) */
160 if (!chkidx(move)) {
161 return 0;
162 }
164 /* must move */
165 if (move->fromfile == move->tofile && move->fromrow == move->torow) {
166 return 0;
167 }
169 /* does piece exist */
170 if (msrc(gamestate->board, move) != move->piece) {
171 return 0;
172 }
174 /* can't capture own pieces */
175 if ((mdst(gamestate->board, move) & COLOR_MASK)
176 == (move->piece & COLOR_MASK)) {
177 return 0;
178 }
180 /* validate individual rules */
181 switch (move->piece & PIECE_MASK) {
182 case PAWN:
183 return pawn_chkrules(gamestate, move) &&
184 !pawn_isblocked(gamestate, move);
185 case ROOK:
186 return rook_chkrules(move) &&
187 !rook_isblocked(gamestate, move);
188 case KNIGHT:
189 return knight_chkrules(move); /* knight is never blocked */
190 case BISHOP:
191 return bishop_chkrules(move) &&
192 !bishop_isblocked(gamestate, move);
193 case QUEEN:
194 return queen_chkrules(move) &&
195 !queen_isblocked(gamestate, move);
196 case KING:
197 return king_chkrules(gamestate, move) &&
198 !king_isblocked(gamestate, move);
199 default:
200 return 0;
201 }
202 }
204 _Bool validate_move(GameState *gamestate, Move *move) {
206 _Bool result = validate_move_rules(gamestate, move);
208 /* cancel processing to save resources */
209 if (!result) {
210 return 0;
211 }
213 /* find kings for check validation */
214 uint8_t piececolor = (move->piece & COLOR_MASK);
216 uint8_t mykingfile = 0, mykingrow = 0, opkingfile = 0, opkingrow = 0;
217 for (uint8_t row = 0 ; row < 8 ; row++) {
218 for (uint8_t file = 0 ; file < 8 ; file++) {
219 if (gamestate->board[row][file] ==
220 (piececolor == WHITE?WKING:BKING)) {
221 mykingfile = file;
222 mykingrow = row;
223 } else if (gamestate->board[row][file] ==
224 (piececolor == WHITE?BKING:WKING)) {
225 opkingfile = file;
226 opkingrow = row;
227 }
228 }
229 }
231 /* simulation move for check validation */
232 GameState simulation;
233 memcpy(&simulation, gamestate, sizeof(GameState));
234 apply_move(&simulation, move);
236 /* don't move into or stay in check position */
237 if (is_covered(&simulation, mykingrow, mykingfile,
238 opponent_color(piececolor))) {
239 return 0;
240 }
242 /* correct check and checkmate flags (move is still valid) */
243 Move threats[16];
244 uint8_t threatcount;
245 move->check = get_threats(&simulation, opkingrow, opkingfile,
246 piececolor, threats, &threatcount);
248 if (move->check) {
249 /* determine possible escape fields */
250 _Bool canescape = 0;
251 for (int dr = -1 ; dr <= 1 && !canescape ; dr++) {
252 for (int df = -1 ; df <= 1 && !canescape ; df++) {
253 if (!(dr == 0 && df == 0) &&
254 isidx(opkingrow + dr) && isidx(opkingfile + df)) {
256 /* escape field neither blocked nor covered */
257 if ((simulation.board[opkingrow + dr][opkingfile + df]
258 & COLOR_MASK) != opponent_color(piececolor)) {
259 canescape |= !is_covered(&simulation,
260 opkingrow + dr, opkingfile + df, piececolor);
261 }
262 }
263 }
264 }
265 /* can't escape, can he capture? */
266 if (!canescape && threatcount == 1) {
267 canescape = is_attacked(&simulation, threats[0].fromrow,
268 threats[0].fromfile, opponent_color(piececolor));
269 }
271 /* can't capture, can he block? */
272 if (!canescape && threatcount == 1) {
273 Move *threat = &(threats[0]);
274 uint8_t threatpiece = threat->piece & PIECE_MASK;
276 /* knight, pawns and the king cannot be blocked */
277 if (threatpiece == BISHOP || threatpiece == ROOK
278 || threatpiece == QUEEN) {
279 if (threat->fromrow == threat->torow) {
280 /* rook aspect (on row) */
281 int d = threat->tofile > threat->fromfile ? 1 : -1;
282 uint8_t file = threat->fromfile;
283 while (!canescape && file != threat->tofile - d) {
284 file += d;
285 canescape |= is_protected(&simulation,
286 threat->torow, file, opponent_color(piececolor));
287 }
288 } else if (threat->fromfile == threat->tofile) {
289 /* rook aspect (on file) */
290 int d = threat->torow > threat->fromrow ? 1 : -1;
291 uint8_t row = threat->fromrow;
292 while (!canescape && row != threat->torow - d) {
293 row += d;
294 canescape |= is_protected(&simulation,
295 row, threat->tofile, opponent_color(piececolor));
296 }
297 } else {
298 /* bishop aspect */
299 int dr = move->torow > move->fromrow ? 1 : -1;
300 int df = move->tofile > move->fromfile ? 1 : -1;
302 uint8_t row = move->fromrow;
303 uint8_t file = move->fromfile;
304 while (!canescape && file != move->tofile - df
305 && row != move->torow - dr) {
306 row += dr;
307 file += df;
308 canescape |= is_protected(&simulation, row, file,
309 opponent_color(piececolor));
310 }
311 }
312 }
313 }
315 if (!canescape) {
316 gamestate->checkmate = 1;
317 }
318 }
320 return 1;
321 }
323 int eval_move(GameState *gamestate, char *mstr, Move *move) {
324 memset(move, 0, sizeof(Move));
325 move->fromfile = POS_UNSPECIFIED;
326 move->fromrow = POS_UNSPECIFIED;
328 size_t len = strlen(mstr);
330 /* evaluate check/checkmate flags */
331 if (mstr[len-1] == '+') {
332 len--; mstr[len] = '\0';
333 move->check = 1;
334 } else if (mstr[len-1] == '#') {
335 len--; mstr[len] = '\0';
336 /* ignore - validation should set game state */
337 }
339 /* evaluate promotion */
340 if (len > 3 && mstr[len-2] == '=') {
341 move->promotion = getpiece(mstr[len-1]);
342 if (!move->promotion) {
343 return INVALID_MOVE_SYNTAX;
344 } else {
345 move->promotion |= gamestate->mycolor;
346 len -= 2;
347 mstr[len] = 0;
348 }
349 }
351 if (len == 2) {
352 /* pawn move (e.g. "e4") */
353 move->piece = PAWN;
354 move->tofile = fileidx(mstr[0]);
355 move->torow = rowidx(mstr[1]);
356 } else if (len == 3) {
357 if (strcmp(mstr, "O-O") == 0) {
358 /* king side castling */
359 move->piece = KING;
360 move->fromfile = fileidx('e');
361 move->tofile = fileidx('g');
362 move->fromrow = move->torow = gamestate->mycolor == WHITE ? 0 : 7;
363 } else {
364 /* move (e.g. "Nf3") */
365 move->piece = getpiece(mstr[0]);
366 move->tofile = fileidx(mstr[1]);
367 move->torow = rowidx(mstr[2]);
368 }
370 } else if (len == 4) {
371 move->piece = getpiece(mstr[0]);
372 if (!move->piece) {
373 move->piece = PAWN;
374 move->fromfile = fileidx(mstr[0]);
375 }
376 if (mstr[1] == 'x') {
377 /* capture (e.g. "Nxf3", "dxe5") */
378 move->capture = 1;
379 } else {
380 /* move (e.g. "Ndf3", "N2c3", "e2e4") */
381 if (isfile(mstr[1])) {
382 move->fromfile = fileidx(mstr[1]);
383 if (move->piece == PAWN) {
384 move->piece = 0;
385 }
386 } else {
387 move->fromrow = rowidx(mstr[1]);
388 }
389 }
390 move->tofile = fileidx(mstr[2]);
391 move->torow = rowidx(mstr[3]);
392 } else if (len == 5) {
393 if (strcmp(mstr, "O-O-O") == 0) {
394 /* queen side castling "O-O-O" */
395 move->piece = KING;
396 move->fromfile = fileidx('e');
397 move->tofile = fileidx('c');
398 move->fromrow = move->torow = gamestate->mycolor == WHITE ? 0 : 7;
399 } else {
400 move->piece = getpiece(mstr[0]);
401 if (mstr[2] == 'x') {
402 move->capture = 1;
403 if (move->piece) {
404 /* capture (e.g. "Ndxf3") */
405 move->fromfile = fileidx(mstr[1]);
406 } else {
407 /* long notation capture (e.g. "e5xf6") */
408 move->piece = PAWN;
409 move->fromfile = fileidx(mstr[0]);
410 move->fromrow = rowidx(mstr[1]);
411 }
412 } else {
413 /* long notation move (e.g. "Nc5a4") */
414 move->fromfile = fileidx(mstr[1]);
415 move->fromrow = rowidx(mstr[2]);
416 }
417 move->tofile = fileidx(mstr[3]);
418 move->torow = rowidx(mstr[4]);
419 }
420 } else if (len == 6) {
421 /* long notation capture (e.g. "Nc5xf3") */
422 if (mstr[3] == 'x') {
423 move->capture = 1;
424 move->piece = getpiece(mstr[0]);
425 move->fromfile = fileidx(mstr[1]);
426 move->fromrow = rowidx(mstr[2]);
427 move->tofile = fileidx(mstr[4]);
428 move->torow = rowidx(mstr[5]);
429 }
430 }
433 if (move->piece) {
434 if (move->piece == PAWN
435 && move->torow == (gamestate->mycolor==WHITE?7:0)
436 && !move->promotion) {
437 return NEED_PROMOTION;
438 }
440 move->piece |= gamestate->mycolor;
441 if (move->fromfile == POS_UNSPECIFIED
442 || move->fromrow == POS_UNSPECIFIED) {
443 return getlocation(gamestate, move);
444 } else {
445 return chkidx(move) ? VALID_MOVE_SYNTAX : INVALID_POSITION;
446 }
447 } else {
448 return INVALID_MOVE_SYNTAX;
449 }
450 }
452 _Bool get_threats(GameState *gamestate, uint8_t row, uint8_t file,
453 uint8_t color, Move *threats, uint8_t *threatcount) {
454 Move candidates[16];
455 int candidatecount = 0;
456 for (uint8_t r = 0 ; r < 8 ; r++) {
457 for (uint8_t f = 0 ; f < 8 ; f++) {
458 if ((gamestate->board[r][f] & COLOR_MASK) == color) {
459 memset(&(candidates[candidatecount]), 0, sizeof(Move));
460 candidates[candidatecount].piece = gamestate->board[r][f];
461 candidates[candidatecount].fromrow = r;
462 candidates[candidatecount].fromfile = f;
463 candidates[candidatecount].torow = row;
464 candidates[candidatecount].tofile = file;
465 candidatecount++;
466 }
467 }
468 }
470 if (threatcount) {
471 *threatcount = 0;
472 }
475 _Bool result = 0;
477 for (int i = 0 ; i < candidatecount ; i++) {
478 if (validate_move_rules(gamestate, &(candidates[i]))) {
479 result = 1;
480 if (threats && threatcount) {
481 threats[(*threatcount)++] = candidates[i];
482 }
483 }
484 }
486 return result;
487 }
489 _Bool get_real_threats(GameState *gamestate, uint8_t row, uint8_t file,
490 uint8_t color, Move *threats, uint8_t *threatcount) {
492 Move candidates[16];
493 uint8_t candidatecount;
494 if (get_threats(gamestate, row, file, color, candidates, &candidatecount)) {
496 if (threatcount) {
497 *threatcount = 0;
498 }
499 _Bool result = 0;
500 uint8_t kingfile = 0, kingrow = 0;
501 for (uint8_t row = 0 ; row < 8 ; row++) {
502 for (uint8_t file = 0 ; file < 8 ; file++) {
503 if ((gamestate->board[row][file] & COLOR_MASK) == color) {
504 kingfile = file;
505 kingrow = row;
506 }
507 }
508 }
510 for (uint8_t i = 0 ; i < candidatecount ; i++) {
511 GameState simulation;
512 memcpy(&simulation, gamestate, sizeof(GameState));
513 apply_move(&simulation, &(candidates[i]));
514 if (!is_covered(&simulation, kingrow, kingfile,
515 opponent_color(color))) {
516 result = 1;
517 if (threats && threatcount) {
518 threats[(*threatcount)++] = candidates[i];
519 }
520 }
521 }
523 return result;
524 } else {
525 return 0;
526 }
527 }
529 _Bool is_protected(GameState *gamestate, uint8_t row, uint8_t file,
530 uint8_t color) {
532 Move threats[16];
533 uint8_t threatcount;
534 if (get_real_threats(gamestate, row, file, color, threats, &threatcount)) {
535 for (int i = 0 ; i < threatcount ; i++) {
536 if (threats[i].piece != (color|KING)) {
537 return 1;
538 }
539 }
540 return 0;
541 } else {
542 return 0;
543 }
544 }
546 uint16_t remaining_movetime(GameInfo *gameinfo, GameState *gamestate,
547 uint8_t color) {
548 if (!gameinfo->timecontrol) {
549 return 0;
550 }
552 if (gamestate->movelist) {
553 uint16_t time = gameinfo->time;
554 suseconds_t micros = 0;
556 MoveList *movelist = color == WHITE ?
557 gamestate->movelist : gamestate->movelist->next;
559 while (movelist) {
560 time += gameinfo->addtime;
562 struct timeval *movetime = &(movelist->move.movetime);
563 if (movetime->tv_sec >= time) {
564 return 0;
565 }
567 time -= movetime->tv_sec;
568 micros += movetime->tv_usec;
570 movelist = movelist->next ? movelist->next->next : NULL;
571 }
573 time_t sec;
574 movelist = gamestate->lastmove;
575 if ((movelist->move.piece & COLOR_MASK) != color) {
576 struct timeval *lastmovetstamp = &(movelist->move.timestamp);
577 struct timeval currenttstamp;
578 gettimeofday(¤ttstamp, NULL);
579 micros += currenttstamp.tv_usec - lastmovetstamp->tv_usec;
580 sec = currenttstamp.tv_sec - lastmovetstamp->tv_sec;
581 if (sec >= time) {
582 return 0;
583 }
585 time -= sec;
586 }
588 sec = micros / 1e6L;
590 if (sec >= time) {
591 return 0;
592 }
594 time -= sec;
596 return time;
597 } else {
598 return gameinfo->time;
599 }
600 }
