terminal-chess: src/chess/rules.c@0cedda2544da (annotated)

src/chess/rules.c@0cedda2544da (annotated)

src/chess/rules.c

Wed, 11 Jun 2014 15:38:01 +0200

author: Mike Becker <universe@uap-core.de>
date: Wed, 11 Jun 2014 15:38:01 +0200
changeset 48: 0cedda2544da
parent 47: d726e4b46c33
child 49: 02c509a44e98
permissions: -rw-r--r--

added return code to move validation (for more informative messages) + fixed a bug where simulations added movelist items to the original gamestate

 /*
  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
  *
  * Copyright 2014 Mike Becker. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions are met:
  *
  *   1. Redistributions of source code must retain the above copyright
  *      notice, this list of conditions and the following disclaimer.
  *
  *   2. Redistributions in binary form must reproduce the above copyright
  *      notice, this list of conditions and the following disclaimer in the
  *      documentation and/or other materials provided with the distribution.
  *
  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  * POSSIBILITY OF SUCH DAMAGE.
  *
  */
 #include "rules.h"
 #include "chess.h"
 #include <string.h>
 #include <stdlib.h>
 #include <sys/time.h>
 static GameState gamestate_copy_sim(GameState *gamestate) {
     GameState simulation = *gamestate;
     if (simulation.lastmove) {
         MoveList *lastmovecopy = malloc(sizeof(MoveList));
         *lastmovecopy = *(simulation.lastmove);
         simulation.movelist = simulation.lastmove = lastmovecopy;
     }
     return simulation;
 }
 void gamestate_cleanup(GameState *gamestate) {
     MoveList *elem;
     elem = gamestate->movelist;
     while (elem) {
         MoveList *cur = elem;
         elem = elem->next;
         free(cur);
     };
 }
 static void addmove(GameState* gamestate, Move *move) {
     MoveList *elem = malloc(sizeof(MoveList));
     elem->next = NULL;
     elem->move = *move;
     struct timeval curtimestamp;
     gettimeofday(&curtimestamp, NULL);
     elem->move.timestamp.tv_sec = curtimestamp.tv_sec;
     elem->move.timestamp.tv_usec = curtimestamp.tv_usec;
     if (gamestate->lastmove) {
         struct movetimeval *lasttstamp = &(gamestate->lastmove->move.timestamp);
         uint64_t sec = curtimestamp.tv_sec - lasttstamp->tv_sec;
         suseconds_t micros;
         if (curtimestamp.tv_usec < lasttstamp->tv_usec) {
             micros = 1e6L-(lasttstamp->tv_usec - curtimestamp.tv_usec);
             sec--;
         } else {
             micros = curtimestamp.tv_usec - lasttstamp->tv_usec;
         }
         elem->move.movetime.tv_sec = sec;
         elem->move.movetime.tv_usec = micros;
         gamestate->lastmove->next = elem;
         gamestate->lastmove = elem;
     } else {
         elem->move.movetime.tv_usec = 0;
         elem->move.movetime.tv_sec = 0;
         gamestate->movelist = gamestate->lastmove = elem;
     }
 }
 char getpiecechr(uint8_t piece) {
     switch (piece & PIECE_MASK) {
     case ROOK: return 'R';
     case KNIGHT: return 'N';
     case BISHOP: return 'B';
     case QUEEN: return 'Q';
     case KING: return 'K';
     default: return '\0';
     }
 }
 uint8_t getpiece(char c) {
     switch (c) {
         case 'R': return ROOK;
         case 'N': return KNIGHT;
         case 'B': return BISHOP;
         case 'Q': return QUEEN;
         case 'K': return KING;
         default: return 0;
     }
 }
 void apply_move(GameState *gamestate, Move *move) {
     uint8_t piece = move->piece & PIECE_MASK;
     uint8_t color = move->piece & COLOR_MASK;
     /* en passant capture */
     if (move->capture && piece == PAWN &&
         mdst(gamestate->board, move) == 0) {
         gamestate->board[move->fromrow][move->tofile] = 0;
     }
     /* remove old en passant threats */
     for (uint8_t file = 0 ; file < 8 ; file++) {
         gamestate->board[3][file] &= ~ENPASSANT_THREAT;
         gamestate->board[4][file] &= ~ENPASSANT_THREAT;
     }
     /* add new en passant threat */
     if (piece == PAWN && (
         (move->fromrow == 1 && move->torow == 3) ||
         (move->fromrow == 6 && move->torow == 4))) {
         move->piece |= ENPASSANT_THREAT;
     }
     /* move (and maybe capture or promote) */
     msrc(gamestate->board, move) = 0;
     if (move->promotion) {
         mdst(gamestate->board, move) = move->promotion;
     } else {
         mdst(gamestate->board, move) = move->piece;
     }
     /* castling */
     if (piece == KING &&
         move->fromfile == fileidx('e')) {
         if (move->tofile == fileidx('g')) {
             gamestate->board[move->torow][fileidx('h')] = 0;
             gamestate->board[move->torow][fileidx('f')] = color|ROOK;
         } else if (move->tofile == fileidx('c')) {
             gamestate->board[move->torow][fileidx('a')] = 0;
             gamestate->board[move->torow][fileidx('d')] = color|ROOK;
         }
     }
     addmove(gamestate, move);
 }
 static int validate_move_rules(GameState *gamestate, Move *move) {
     /* validate indices (don't trust opponent) */
     if (!chkidx(move)) {
         return INVALID_POSITION;
     }
     /* must move */
     if (move->fromfile == move->tofile && move->fromrow == move->torow) {
         return INVALID_MOVE_SYNTAX;
     }
     /* does piece exist */
     if ((msrc(gamestate->board, move)&(PIECE_MASK|COLOR_MASK))
            != (move->piece&(PIECE_MASK|COLOR_MASK))) {
         return INVALID_POSITION;
     }
     /* can't capture own pieces */
     if ((mdst(gamestate->board, move) & COLOR_MASK)
             == (move->piece & COLOR_MASK)) {
         return RULES_VIOLATED;
     }
     /* must capture, if and only if destination is occupied */
     if ((mdst(gamestate->board, move) == 0 && move->capture) ||
             (mdst(gamestate->board, move) != 0 && !move->capture)) {
         return INVALID_MOVE_SYNTAX;
     }
     /* validate individual rules */
     _Bool chkrules;
     switch (move->piece & PIECE_MASK) {
     case PAWN:
         chkrules = pawn_chkrules(gamestate, move) &&
             !pawn_isblocked(gamestate, move);
         break;
     case ROOK:
         chkrules = rook_chkrules(move) &&
             !rook_isblocked(gamestate, move);
         break;
     case KNIGHT:
         chkrules = knight_chkrules(move); /* knight is never blocked */
         break;
     case BISHOP:
         chkrules = bishop_chkrules(move) &&
             !bishop_isblocked(gamestate, move);
         break;
     case QUEEN:
         chkrules = queen_chkrules(move) &&
             !queen_isblocked(gamestate, move);
         break;
     case KING:
         chkrules = king_chkrules(gamestate, move) &&
             !king_isblocked(gamestate, move);
         break;
     default:
         return INVALID_MOVE_SYNTAX;
     }
     return chkrules ? VALID_MOVE_SEMANTICS : RULES_VIOLATED;
 }
 int validate_move(GameState *gamestate, Move *move) {
     int result = validate_move_rules(gamestate, move);
     /* cancel processing to save resources */
     if (result != VALID_MOVE_SEMANTICS) {
         return result;
     }
     /* find kings for check validation */
     uint8_t piececolor = (move->piece & COLOR_MASK);
     uint8_t mykingfile = 0, mykingrow = 0, opkingfile = 0, opkingrow = 0;
     for (uint8_t row = 0 ; row < 8 ; row++) {
         for (uint8_t file = 0 ; file < 8 ; file++) {
             if (gamestate->board[row][file] ==
                     (piececolor == WHITE?WKING:BKING)) {
                 mykingfile = file;
                 mykingrow = row;
             } else if (gamestate->board[row][file] ==
                     (piececolor == WHITE?BKING:WKING)) {
                 opkingfile = file;
                 opkingrow = row;
             }
         }
     }
     /* simulate move for check validation */
     GameState simulation = gamestate_copy_sim(gamestate);
     Move simmove = *move;
     apply_move(&simulation, &simmove);
     /* don't move into or stay in check position */
     if (is_covered(&simulation, mykingrow, mykingfile,
         opponent_color(piececolor))) {
         gamestate_cleanup(&simulation);
         if ((move->piece & PIECE_MASK) == KING) {
             return KING_MOVES_INTO_CHECK;
         } else {
             /* last move is always not null in this case */
             return gamestate->lastmove->move.check ?
                 KING_IN_CHECK : PIECE_PINNED;
         }
     }
     /* correct check and checkmate flags (move is still valid) */
     Move threats[16];
     uint8_t threatcount;
     move->check = get_threats(&simulation, opkingrow, opkingfile,
         piececolor, threats, &threatcount);
     if (move->check) {
         /* determine possible escape fields */
         _Bool canescape = 0;
         for (int dr = -1 ; dr <= 1 && !canescape ; dr++) {
             for (int df = -1 ; df <= 1 && !canescape ; df++) {
                 if (!(dr == 0 && df == 0)  &&
                         isidx(opkingrow + dr) && isidx(opkingfile + df)) {
                     /* escape field neither blocked nor covered */
                     if ((simulation.board[opkingrow + dr][opkingfile + df]
                             & COLOR_MASK) != opponent_color(piececolor)) {
                         canescape |= !is_covered(&simulation,
                             opkingrow + dr, opkingfile + df, piececolor);
                     }
                 }
             }
         }
         /* can't escape, can he capture? */
         if (!canescape && threatcount == 1) {
             canescape = is_attacked(&simulation, threats[0].fromrow,
                 threats[0].fromfile, opponent_color(piececolor));
         }
         /* can't capture, can he block? */
         if (!canescape && threatcount == 1) {
             Move *threat = &(threats[0]);
             uint8_t threatpiece = threat->piece & PIECE_MASK;
             /* knight, pawns and the king cannot be blocked */
             if (threatpiece == BISHOP || threatpiece == ROOK
                 || threatpiece == QUEEN) {
                 if (threat->fromrow == threat->torow) {
                     /* rook aspect (on row) */
                     int d = threat->tofile > threat->fromfile ? 1 : -1;
                     uint8_t file = threat->fromfile;
                     while (!canescape && file != threat->tofile - d) {
                         file += d;
                         canescape |= is_protected(&simulation,
                             threat->torow, file, opponent_color(piececolor));
                     }
                 } else if (threat->fromfile == threat->tofile) {
                     /* rook aspect (on file) */
                     int d = threat->torow > threat->fromrow ? 1 : -1;
                     uint8_t row = threat->fromrow;
                     while (!canescape && row != threat->torow - d) {
                         row += d;
                         canescape |= is_protected(&simulation,
                             row, threat->tofile, opponent_color(piececolor));
                     }
                 } else {
                     /* bishop aspect */
                     int dr = move->torow > move->fromrow ? 1 : -1;
                     int df = move->tofile > move->fromfile ? 1 : -1;
                     uint8_t row = move->fromrow;
                     uint8_t file = move->fromfile;
                     while (!canescape && file != move->tofile - df
                         && row != move->torow - dr) {
                         row += dr;
                         file += df;
                         canescape |= is_protected(&simulation, row, file,
                             opponent_color(piececolor));
                     }
                 }
             }
         }
         if (!canescape) {
             gamestate->checkmate = 1;
         }
     }
     gamestate_cleanup(&simulation);
     return VALID_MOVE_SEMANTICS;
 }
 _Bool get_threats(GameState *gamestate, uint8_t row, uint8_t file,
         uint8_t color, Move *threats, uint8_t *threatcount) {
     Move candidates[32];
     int candidatecount = 0;
     for (uint8_t r = 0 ; r < 8 ; r++) {
         for (uint8_t f = 0 ; f < 8 ; f++) {
             if ((gamestate->board[r][f] & COLOR_MASK) == color) {
                 // non-capturing move
                 memset(&(candidates[candidatecount]), 0, sizeof(Move));
                 candidates[candidatecount].piece = gamestate->board[r][f];
                 candidates[candidatecount].fromrow = r;
                 candidates[candidatecount].fromfile = f;
                 candidates[candidatecount].torow = row;
                 candidates[candidatecount].tofile = file;
                 candidatecount++;
                 // capturing move
                 memcpy(&(candidates[candidatecount]),
                     &(candidates[candidatecount-1]), sizeof(Move));
                 candidates[candidatecount].capture = 1;
                 candidatecount++;
             }
         }
     }
     if (threatcount) {
         *threatcount = 0;
     }
     _Bool result = 0;
     for (int i = 0 ; i < candidatecount ; i++) {
         if (validate_move_rules(gamestate, &(candidates[i]))
                 == VALID_MOVE_SEMANTICS) {
             result = 1;
             if (threats && threatcount) {
                 threats[(*threatcount)++] = candidates[i];
             }
         }
     }
     return result;
 }
 _Bool is_pinned(GameState *gamestate, Move *move) {
     uint8_t color = move->piece & COLOR_MASK;
     uint8_t kingfile = 0, kingrow = 0;
     for (uint8_t row = 0 ; row < 8 ; row++) {
         for (uint8_t file = 0 ; file < 8 ; file++) {
             if (gamestate->board[row][file] == (color|KING)) {
                 kingfile = file;
                 kingrow = row;
             }
         }
     }
     GameState simulation = gamestate_copy_sim(gamestate);
     Move simmove = *move;
     apply_move(&simulation, &simmove);
     _Bool covered = is_covered(&simulation,
         kingrow, kingfile, opponent_color(color));
     gamestate_cleanup(&simulation);
     return covered;
 }
 _Bool get_real_threats(GameState *gamestate, uint8_t row, uint8_t file,
         uint8_t color, Move *threats, uint8_t *threatcount) {
     if (threatcount) {
         *threatcount = 0;
     }
     Move candidates[16];
     uint8_t candidatecount;
     if (get_threats(gamestate, row, file, color, candidates, &candidatecount)) {
         _Bool result = 0;
         uint8_t kingfile = 0, kingrow = 0;
         for (uint8_t row = 0 ; row < 8 ; row++) {
             for (uint8_t file = 0 ; file < 8 ; file++) {
                 if (gamestate->board[row][file] == (color|KING)) {
                     kingfile = file;
                     kingrow = row;
                 }
             }
         }
         for (uint8_t i = 0 ; i < candidatecount ; i++) {
             GameState simulation = gamestate_copy_sim(gamestate);
             Move simmove = candidates[i];
             apply_move(&simulation, &simmove);
             if (!is_covered(&simulation, kingrow, kingfile,
                     opponent_color(color))) {
                 result = 1;
                 if (threats && threatcount) {
                     threats[(*threatcount)++] = candidates[i];
                 }
             }
             gamestate_cleanup(&simulation);
         }
         return result;
     } else {
         return 0;
     }
 }
 static int getlocation(GameState *gamestate, Move *move) {
     uint8_t color = move->piece & COLOR_MASK;
     _Bool incheck = gamestate->lastmove?gamestate->lastmove->move.check:0;
     Move threats[16], *threat = NULL;
     uint8_t threatcount;
     if (get_threats(gamestate, move->torow, move->tofile, color,
             threats, &threatcount)) {
         // find threats for the specified position
         for (uint8_t i = 0 ; i < threatcount ; i++) {
             if ((threats[i].piece & (PIECE_MASK | COLOR_MASK))
                     == move->piece &&
                     (move->fromrow == POS_UNSPECIFIED ||
                     move->fromrow == threats[i].fromrow) &&
                     (move->fromfile == POS_UNSPECIFIED ||
                     move->fromfile == threats[i].fromfile)) {
                 if (threat) {
                     return AMBIGUOUS_MOVE;
                 } else {
                     threat = &(threats[i]);
                 }
             }
         }
         // can't threaten specified position
         if (!threat) {
             return INVALID_POSITION;
         }
         // found threat is no real threat
         if (is_pinned(gamestate, threat)) {
             return incheck?KING_IN_CHECK:PIECE_PINNED;
         } else {
             memcpy(move, threat, sizeof(Move));
             return VALID_MOVE_SYNTAX;
         }
     } else {
         return INVALID_POSITION;
     }
 }
 int eval_move(GameState *gamestate, char *mstr, Move *move) {
     memset(move, 0, sizeof(Move));
     move->fromfile = POS_UNSPECIFIED;
     move->fromrow = POS_UNSPECIFIED;
     size_t len = strlen(mstr);
     if (len < 1 || len > 6) {
         return INVALID_MOVE_SYNTAX;
     }
     /* evaluate check/checkmate flags */
     if (mstr[len-1] == '+') {
         len--; mstr[len] = '\0';
         move->check = 1;
     } else if (mstr[len-1] == '#') {
         len--; mstr[len] = '\0';
         /* ignore - validation should set game state */
     }
     /* evaluate promotion */
     if (len > 3 && mstr[len-2] == '=') {
         move->promotion = getpiece(mstr[len-1]);
         if (!move->promotion) {
             return INVALID_MOVE_SYNTAX;
         } else {
             move->promotion |= gamestate->mycolor;
             len -= 2;
             mstr[len] = 0;
         }
     }
     if (len == 2) {
         /* pawn move (e.g. "e4") */
         move->piece = PAWN;
         move->tofile = fileidx(mstr[0]);
         move->torow = rowidx(mstr[1]);
     } else if (len == 3) {
         if (strcmp(mstr, "O-O") == 0) {
             /* king side castling */
             move->piece = KING;
             move->fromfile = fileidx('e');
             move->tofile = fileidx('g');
             move->fromrow = move->torow = gamestate->mycolor == WHITE ? 0 : 7;
         } else {
             /* move (e.g. "Nf3") */
             move->piece = getpiece(mstr[0]);
             move->tofile = fileidx(mstr[1]);
             move->torow = rowidx(mstr[2]);
         }
     } else if (len == 4) {
         move->piece = getpiece(mstr[0]);
         if (!move->piece) {
             move->piece = PAWN;
             move->fromfile = fileidx(mstr[0]);
         }
         if (mstr[1] == 'x') {
             /* capture (e.g. "Nxf3", "dxe5") */
             move->capture = 1;
         } else {
             /* move (e.g. "Ndf3", "N2c3", "e2e4") */
             if (isfile(mstr[1])) {
                 move->fromfile = fileidx(mstr[1]);
                 if (move->piece == PAWN) {
                     move->piece = 0;
                 }
             } else {
                 move->fromrow = rowidx(mstr[1]);
             }
         }
         move->tofile = fileidx(mstr[2]);
         move->torow = rowidx(mstr[3]);
     } else if (len == 5) {
         if (strcmp(mstr, "O-O-O") == 0) {
             /* queen side castling "O-O-O" */
             move->piece = KING;
             move->fromfile = fileidx('e');
             move->tofile = fileidx('c');
             move->fromrow = move->torow = gamestate->mycolor == WHITE ? 0 : 7;
         } else {
             move->piece = getpiece(mstr[0]);
             if (mstr[2] == 'x') {
                 move->capture = 1;
                 if (move->piece) {
                     /* capture (e.g. "Ndxf3") */
                     move->fromfile = fileidx(mstr[1]);
                 } else {
                     /* long notation capture (e.g. "e5xf6") */
                     move->piece = PAWN;
                     move->fromfile = fileidx(mstr[0]);
                     move->fromrow = rowidx(mstr[1]);
                 }
             } else {
                 /* long notation move (e.g. "Nc5a4") */
                 move->fromfile = fileidx(mstr[1]);
                 move->fromrow = rowidx(mstr[2]);
             }
             move->tofile = fileidx(mstr[3]);
             move->torow = rowidx(mstr[4]);
         }
     } else if (len == 6) {
         /* long notation capture (e.g. "Nc5xf3") */
         if (mstr[3] == 'x') {
             move->capture = 1;
             move->piece = getpiece(mstr[0]);
             move->fromfile = fileidx(mstr[1]);
             move->fromrow = rowidx(mstr[2]);
             move->tofile = fileidx(mstr[4]);
             move->torow = rowidx(mstr[5]);
         }
     }
     if (move->piece) {
         if (move->piece == PAWN
             && move->torow == (gamestate->mycolor==WHITE?7:0)
             && !move->promotion) {
             return NEED_PROMOTION;
         }
         move->piece |= gamestate->mycolor;
         if (move->fromfile == POS_UNSPECIFIED
             || move->fromrow == POS_UNSPECIFIED) {
             return getlocation(gamestate, move);
         } else {
             return chkidx(move) ? VALID_MOVE_SYNTAX : INVALID_POSITION;
         }
     } else {
         return INVALID_MOVE_SYNTAX;
     }
 }
 _Bool is_protected(GameState *gamestate, uint8_t row, uint8_t file,
         uint8_t color) {
     Move threats[16];
     uint8_t threatcount;
     if (get_real_threats(gamestate, row, file, color, threats, &threatcount)) {
         for (int i = 0 ; i < threatcount ; i++) {
             if (threats[i].piece != (color|KING)) {
                 return 1;
             }
         }
         return 0;
     } else {
         return 0;
     }
 }
 uint16_t remaining_movetime(GameInfo *gameinfo, GameState *gamestate,
         uint8_t color) {
     if (!gameinfo->timecontrol) {
         return 0;
     }
     if (gamestate->movelist) {
         uint16_t time = gameinfo->time;
         suseconds_t micros = 0;
         MoveList *movelist = color == WHITE ?
             gamestate->movelist : gamestate->movelist->next;
         while (movelist) {
             time += gameinfo->addtime;
             struct movetimeval *movetime = &(movelist->move.movetime);
             if (movetime->tv_sec >= time) {
                 return 0;
             }
             time -= movetime->tv_sec;
             micros += movetime->tv_usec;
             movelist = movelist->next ? movelist->next->next : NULL;
         }
         time_t sec;
         movelist = gamestate->lastmove;
         if ((movelist->move.piece & COLOR_MASK) != color) {
             struct movetimeval *lastmovetstamp = &(movelist->move.timestamp);
             struct timeval currenttstamp;
             gettimeofday(&currenttstamp, NULL);
             micros += currenttstamp.tv_usec - lastmovetstamp->tv_usec;
             sec = currenttstamp.tv_sec - lastmovetstamp->tv_sec;
             if (sec >= time) {
                 return 0;
             }
             time -= sec;
         }
         sec = micros / 1e6L;
         if (sec >= time) {
             return 0;
         }
         time -= sec;
         return time;
     } else {
         return gameinfo->time;
     }
 }

Mercurial > hg > terminal-chess / annotate

src/chess/rules.c@0cedda2544da (annotated)

src/chess/rules.c