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