Mercurial > hg > terminal-chess / file revision
src/chess/rules.c@1891d88cbd10
src/chess/rules.c
Thu, 17 Apr 2014 11:41:02 +0200
- author
- Mike Becker <universe@uap-core.de>
- date
- Thu, 17 Apr 2014 11:41:02 +0200
- changeset 44
- 1891d88cbd10
- parent 40
- 47162a7621da
- child 47
- d726e4b46c33
- permissions
- -rw-r--r--
surrender is now resign
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 static int getlocation(GameState *gamestate, Move *move) {
102 uint8_t piece = move->piece & PIECE_MASK;
103 switch (piece) {
104 case PAWN: return pawn_getlocation(gamestate, move);
105 case ROOK: return rook_getlocation(gamestate, move);
106 case KNIGHT: return knight_getlocation(gamestate, move);
107 case BISHOP: return bishop_getlocation(gamestate, move);
108 case QUEEN: return queen_getlocation(gamestate, move);
109 case KING: return king_getlocation(gamestate, move);
110 default: return INVALID_MOVE_SYNTAX;
111 }
112 }
114 void apply_move(GameState *gamestate, Move *move) {
115 uint8_t piece = move->piece & PIECE_MASK;
116 uint8_t color = move->piece & COLOR_MASK;
118 /* en passant capture */
119 if (move->capture && piece == PAWN &&
120 mdst(gamestate->board, move) == 0) {
121 gamestate->board[move->fromrow][move->tofile] = 0;
122 }
124 /* remove old en passant threats */
125 for (uint8_t file = 0 ; file < 8 ; file++) {
126 gamestate->board[3][file] &= ~ENPASSANT_THREAT;
127 gamestate->board[4][file] &= ~ENPASSANT_THREAT;
128 }
130 /* add new en passant threat */
131 if (piece == PAWN && (
132 (move->fromrow == 1 && move->torow == 3) ||
133 (move->fromrow == 6 && move->torow == 4))) {
134 move->piece |= ENPASSANT_THREAT;
135 }
137 /* move (and maybe capture or promote) */
138 msrc(gamestate->board, move) = 0;
139 if (move->promotion) {
140 mdst(gamestate->board, move) = move->promotion;
141 } else {
142 mdst(gamestate->board, move) = move->piece;
143 }
145 /* castling */
146 if (piece == KING &&
147 move->fromfile == fileidx('e')) {
149 if (move->tofile == fileidx('g')) {
150 gamestate->board[move->torow][fileidx('h')] = 0;
151 gamestate->board[move->torow][fileidx('f')] = color|ROOK;
152 } else if (move->tofile == fileidx('c')) {
153 gamestate->board[move->torow][fileidx('a')] = 0;
154 gamestate->board[move->torow][fileidx('d')] = color|ROOK;
155 }
156 }
158 addmove(gamestate, move);
159 }
161 static _Bool validate_move_rules(GameState *gamestate, Move *move) {
162 /* validate indices (don't trust opponent) */
163 if (!chkidx(move)) {
164 return 0;
165 }
167 /* must move */
168 if (move->fromfile == move->tofile && move->fromrow == move->torow) {
169 return 0;
170 }
172 /* does piece exist */
173 if (msrc(gamestate->board, move) != move->piece) {
174 return 0;
175 }
177 /* can't capture own pieces */
178 if ((mdst(gamestate->board, move) & COLOR_MASK)
179 == (move->piece & COLOR_MASK)) {
180 return 0;
181 }
183 /* validate individual rules */
184 switch (move->piece & PIECE_MASK) {
185 case PAWN:
186 return pawn_chkrules(gamestate, move) &&
187 !pawn_isblocked(gamestate, move);
188 case ROOK:
189 return rook_chkrules(move) &&
190 !rook_isblocked(gamestate, move);
191 case KNIGHT:
192 return knight_chkrules(move); /* knight is never blocked */
193 case BISHOP:
194 return bishop_chkrules(move) &&
195 !bishop_isblocked(gamestate, move);
196 case QUEEN:
197 return queen_chkrules(move) &&
198 !queen_isblocked(gamestate, move);
199 case KING:
200 return king_chkrules(gamestate, move) &&
201 !king_isblocked(gamestate, move);
202 default:
203 return 0;
204 }
205 }
207 _Bool validate_move(GameState *gamestate, Move *move) {
209 _Bool result = validate_move_rules(gamestate, move);
211 /* cancel processing to save resources */
212 if (!result) {
213 return 0;
214 }
216 /* find kings for check validation */
217 uint8_t piececolor = (move->piece & COLOR_MASK);
219 uint8_t mykingfile = 0, mykingrow = 0, opkingfile = 0, opkingrow = 0;
220 for (uint8_t row = 0 ; row < 8 ; row++) {
221 for (uint8_t file = 0 ; file < 8 ; file++) {
222 if (gamestate->board[row][file] ==
223 (piececolor == WHITE?WKING:BKING)) {
224 mykingfile = file;
225 mykingrow = row;
226 } else if (gamestate->board[row][file] ==
227 (piececolor == WHITE?BKING:WKING)) {
228 opkingfile = file;
229 opkingrow = row;
230 }
231 }
232 }
234 /* simulation move for check validation */
235 GameState simulation;
236 memcpy(&simulation, gamestate, sizeof(GameState));
237 apply_move(&simulation, move);
239 /* don't move into or stay in check position */
240 if (is_covered(&simulation, mykingrow, mykingfile,
241 opponent_color(piececolor))) {
242 return 0;
243 }
245 /* correct check and checkmate flags (move is still valid) */
246 Move threats[16];
247 uint8_t threatcount;
248 move->check = get_threats(&simulation, opkingrow, opkingfile,
249 piececolor, threats, &threatcount);
251 if (move->check) {
252 /* determine possible escape fields */
253 _Bool canescape = 0;
254 for (int dr = -1 ; dr <= 1 && !canescape ; dr++) {
255 for (int df = -1 ; df <= 1 && !canescape ; df++) {
256 if (!(dr == 0 && df == 0) &&
257 isidx(opkingrow + dr) && isidx(opkingfile + df)) {
259 /* escape field neither blocked nor covered */
260 if ((simulation.board[opkingrow + dr][opkingfile + df]
261 & COLOR_MASK) != opponent_color(piececolor)) {
262 canescape |= !is_covered(&simulation,
263 opkingrow + dr, opkingfile + df, piececolor);
264 }
265 }
266 }
267 }
268 /* can't escape, can he capture? */
269 if (!canescape && threatcount == 1) {
270 canescape = is_attacked(&simulation, threats[0].fromrow,
271 threats[0].fromfile, opponent_color(piececolor));
272 }
274 /* can't capture, can he block? */
275 if (!canescape && threatcount == 1) {
276 Move *threat = &(threats[0]);
277 uint8_t threatpiece = threat->piece & PIECE_MASK;
279 /* knight, pawns and the king cannot be blocked */
280 if (threatpiece == BISHOP || threatpiece == ROOK
281 || threatpiece == QUEEN) {
282 if (threat->fromrow == threat->torow) {
283 /* rook aspect (on row) */
284 int d = threat->tofile > threat->fromfile ? 1 : -1;
285 uint8_t file = threat->fromfile;
286 while (!canescape && file != threat->tofile - d) {
287 file += d;
288 canescape |= is_protected(&simulation,
289 threat->torow, file, opponent_color(piececolor));
290 }
291 } else if (threat->fromfile == threat->tofile) {
292 /* rook aspect (on file) */
293 int d = threat->torow > threat->fromrow ? 1 : -1;
294 uint8_t row = threat->fromrow;
295 while (!canescape && row != threat->torow - d) {
296 row += d;
297 canescape |= is_protected(&simulation,
298 row, threat->tofile, opponent_color(piececolor));
299 }
300 } else {
301 /* bishop aspect */
302 int dr = move->torow > move->fromrow ? 1 : -1;
303 int df = move->tofile > move->fromfile ? 1 : -1;
305 uint8_t row = move->fromrow;
306 uint8_t file = move->fromfile;
307 while (!canescape && file != move->tofile - df
308 && row != move->torow - dr) {
309 row += dr;
310 file += df;
311 canescape |= is_protected(&simulation, row, file,
312 opponent_color(piececolor));
313 }
314 }
315 }
316 }
318 if (!canescape) {
319 gamestate->checkmate = 1;
320 }
321 }
323 return 1;
324 }
326 int eval_move(GameState *gamestate, char *mstr, Move *move) {
327 memset(move, 0, sizeof(Move));
328 move->fromfile = POS_UNSPECIFIED;
329 move->fromrow = POS_UNSPECIFIED;
331 size_t len = strlen(mstr);
333 /* evaluate check/checkmate flags */
334 if (mstr[len-1] == '+') {
335 len--; mstr[len] = '\0';
336 move->check = 1;
337 } else if (mstr[len-1] == '#') {
338 len--; mstr[len] = '\0';
339 /* ignore - validation should set game state */
340 }
342 /* evaluate promotion */
343 if (len > 3 && mstr[len-2] == '=') {
344 move->promotion = getpiece(mstr[len-1]);
345 if (!move->promotion) {
346 return INVALID_MOVE_SYNTAX;
347 } else {
348 move->promotion |= gamestate->mycolor;
349 len -= 2;
350 mstr[len] = 0;
351 }
352 }
354 if (len == 2) {
355 /* pawn move (e.g. "e4") */
356 move->piece = PAWN;
357 move->tofile = fileidx(mstr[0]);
358 move->torow = rowidx(mstr[1]);
359 } else if (len == 3) {
360 if (strcmp(mstr, "O-O") == 0) {
361 /* king side castling */
362 move->piece = KING;
363 move->fromfile = fileidx('e');
364 move->tofile = fileidx('g');
365 move->fromrow = move->torow = gamestate->mycolor == WHITE ? 0 : 7;
366 } else {
367 /* move (e.g. "Nf3") */
368 move->piece = getpiece(mstr[0]);
369 move->tofile = fileidx(mstr[1]);
370 move->torow = rowidx(mstr[2]);
371 }
373 } else if (len == 4) {
374 move->piece = getpiece(mstr[0]);
375 if (!move->piece) {
376 move->piece = PAWN;
377 move->fromfile = fileidx(mstr[0]);
378 }
379 if (mstr[1] == 'x') {
380 /* capture (e.g. "Nxf3", "dxe5") */
381 move->capture = 1;
382 } else {
383 /* move (e.g. "Ndf3", "N2c3", "e2e4") */
384 if (isfile(mstr[1])) {
385 move->fromfile = fileidx(mstr[1]);
386 if (move->piece == PAWN) {
387 move->piece = 0;
388 }
389 } else {
390 move->fromrow = rowidx(mstr[1]);
391 }
392 }
393 move->tofile = fileidx(mstr[2]);
394 move->torow = rowidx(mstr[3]);
395 } else if (len == 5) {
396 if (strcmp(mstr, "O-O-O") == 0) {
397 /* queen side castling "O-O-O" */
398 move->piece = KING;
399 move->fromfile = fileidx('e');
400 move->tofile = fileidx('c');
401 move->fromrow = move->torow = gamestate->mycolor == WHITE ? 0 : 7;
402 } else {
403 move->piece = getpiece(mstr[0]);
404 if (mstr[2] == 'x') {
405 move->capture = 1;
406 if (move->piece) {
407 /* capture (e.g. "Ndxf3") */
408 move->fromfile = fileidx(mstr[1]);
409 } else {
410 /* long notation capture (e.g. "e5xf6") */
411 move->piece = PAWN;
412 move->fromfile = fileidx(mstr[0]);
413 move->fromrow = rowidx(mstr[1]);
414 }
415 } else {
416 /* long notation move (e.g. "Nc5a4") */
417 move->fromfile = fileidx(mstr[1]);
418 move->fromrow = rowidx(mstr[2]);
419 }
420 move->tofile = fileidx(mstr[3]);
421 move->torow = rowidx(mstr[4]);
422 }
423 } else if (len == 6) {
424 /* long notation capture (e.g. "Nc5xf3") */
425 if (mstr[3] == 'x') {
426 move->capture = 1;
427 move->piece = getpiece(mstr[0]);
428 move->fromfile = fileidx(mstr[1]);
429 move->fromrow = rowidx(mstr[2]);
430 move->tofile = fileidx(mstr[4]);
431 move->torow = rowidx(mstr[5]);
432 }
433 }
436 if (move->piece) {
437 if (move->piece == PAWN
438 && move->torow == (gamestate->mycolor==WHITE?7:0)
439 && !move->promotion) {
440 return NEED_PROMOTION;
441 }
443 move->piece |= gamestate->mycolor;
444 if (move->fromfile == POS_UNSPECIFIED
445 || move->fromrow == POS_UNSPECIFIED) {
446 return getlocation(gamestate, move);
447 } else {
448 return chkidx(move) ? VALID_MOVE_SYNTAX : INVALID_POSITION;
449 }
450 } else {
451 return INVALID_MOVE_SYNTAX;
452 }
453 }
455 _Bool get_threats(GameState *gamestate, uint8_t row, uint8_t file,
456 uint8_t color, Move *threats, uint8_t *threatcount) {
457 Move candidates[16];
458 int candidatecount = 0;
459 for (uint8_t r = 0 ; r < 8 ; r++) {
460 for (uint8_t f = 0 ; f < 8 ; f++) {
461 if ((gamestate->board[r][f] & COLOR_MASK) == color) {
462 memset(&(candidates[candidatecount]), 0, sizeof(Move));
463 candidates[candidatecount].piece = gamestate->board[r][f];
464 candidates[candidatecount].fromrow = r;
465 candidates[candidatecount].fromfile = f;
466 candidates[candidatecount].torow = row;
467 candidates[candidatecount].tofile = file;
468 candidatecount++;
469 }
470 }
471 }
473 if (threatcount) {
474 *threatcount = 0;
475 }
478 _Bool result = 0;
480 for (int i = 0 ; i < candidatecount ; i++) {
481 if (validate_move_rules(gamestate, &(candidates[i]))) {
482 result = 1;
483 if (threats && threatcount) {
484 threats[(*threatcount)++] = candidates[i];
485 }
486 }
487 }
489 return result;
490 }
492 _Bool get_real_threats(GameState *gamestate, uint8_t row, uint8_t file,
493 uint8_t color, Move *threats, uint8_t *threatcount) {
495 Move candidates[16];
496 uint8_t candidatecount;
497 if (get_threats(gamestate, row, file, color, candidates, &candidatecount)) {
499 if (threatcount) {
500 *threatcount = 0;
501 }
502 _Bool result = 0;
503 uint8_t kingfile = 0, kingrow = 0;
504 for (uint8_t row = 0 ; row < 8 ; row++) {
505 for (uint8_t file = 0 ; file < 8 ; file++) {
506 if ((gamestate->board[row][file] & COLOR_MASK) == color) {
507 kingfile = file;
508 kingrow = row;
509 }
510 }
511 }
513 for (uint8_t i = 0 ; i < candidatecount ; i++) {
514 GameState simulation;
515 memcpy(&simulation, gamestate, sizeof(GameState));
516 apply_move(&simulation, &(candidates[i]));
517 if (!is_covered(&simulation, kingrow, kingfile,
518 opponent_color(color))) {
519 result = 1;
520 if (threats && threatcount) {
521 threats[(*threatcount)++] = candidates[i];
522 }
523 }
524 }
526 return result;
527 } else {
528 return 0;
529 }
530 }
532 _Bool is_protected(GameState *gamestate, uint8_t row, uint8_t file,
533 uint8_t color) {
535 Move threats[16];
536 uint8_t threatcount;
537 if (get_real_threats(gamestate, row, file, color, threats, &threatcount)) {
538 for (int i = 0 ; i < threatcount ; i++) {
539 if (threats[i].piece != (color|KING)) {
540 return 1;
541 }
542 }
543 return 0;
544 } else {
545 return 0;
546 }
547 }
549 uint16_t remaining_movetime(GameInfo *gameinfo, GameState *gamestate,
550 uint8_t color) {
551 if (!gameinfo->timecontrol) {
552 return 0;
553 }
555 if (gamestate->movelist) {
556 uint16_t time = gameinfo->time;
557 suseconds_t micros = 0;
559 MoveList *movelist = color == WHITE ?
560 gamestate->movelist : gamestate->movelist->next;
562 while (movelist) {
563 time += gameinfo->addtime;
565 struct movetimeval *movetime = &(movelist->move.movetime);
566 if (movetime->tv_sec >= time) {
567 return 0;
568 }
570 time -= movetime->tv_sec;
571 micros += movetime->tv_usec;
573 movelist = movelist->next ? movelist->next->next : NULL;
574 }
576 time_t sec;
577 movelist = gamestate->lastmove;
578 if ((movelist->move.piece & COLOR_MASK) != color) {
579 struct movetimeval *lastmovetstamp = &(movelist->move.timestamp);
580 struct timeval currenttstamp;
581 gettimeofday(¤ttstamp, NULL);
582 micros += currenttstamp.tv_usec - lastmovetstamp->tv_usec;
583 sec = currenttstamp.tv_sec - lastmovetstamp->tv_sec;
584 if (sec >= time) {
585 return 0;
586 }
588 time -= sec;
589 }
591 sec = micros / 1e6L;
593 if (sec >= time) {
594 return 0;
595 }
597 time -= sec;
599 return time;
600 } else {
601 return gameinfo->time;
602 }
603 }
