src/chess/rules.c

/*
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
 *
 * Copyright 2016 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 "pawn.h"
#include "rook.h"
#include "knight.h"
#include "bishop.h"
#include "queen.h"
#include "king.h"
#include "fen.h"

#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
#include <assert.h>

void gamestate_init(GameState *gamestate) {
    memset(gamestate, 0, sizeof(GameState));

    // TODO: implement feature - game can be started from arbitrary position
    Board initboard = {
        {WROOK, WKNIGHT, WBISHOP, WQUEEN, WKING, WBISHOP, WKNIGHT, WROOK},
        {WPAWN, WPAWN,   WPAWN,   WPAWN,  WPAWN, WPAWN,   WPAWN,   WPAWN},
        {0,     0,       0,       0,      0,     0,       0,       0},
        {0,     0,       0,       0,      0,     0,       0,       0},
        {0,     0,       0,       0,      0,     0,       0,       0},
        {0,     0,       0,       0,      0,     0,       0,       0},
        {BPAWN, BPAWN,   BPAWN,   BPAWN,  BPAWN, BPAWN,   BPAWN,   BPAWN},
        {BROOK, BKNIGHT, BBISHOP, BQUEEN, BKING, BBISHOP, BKNIGHT, BROOK}
    };
    memcpy(gamestate->board, initboard, sizeof(Board));
    char fen[FEN_MAX_LENGTH];
    fen_compute(fen, gamestate);
    gamestate->fen_start = strdup(fen);
}

void gamestate_cleanup(GameState *gamestate) {
    if (gamestate == NULL) return;

    free(gamestate->moves);
    gamestate->moves = NULL;
    free(gamestate->fen_start);
    gamestate->fen_start = NULL;
    if (gamestate->fen) {
        for (unsigned i = 0 ; i < gamestate->movecount ; i++) {
            free(gamestate->fen[i]);
        }
        free(gamestate->fen);
        gamestate->fen = NULL;
    }
    gamestate->movecount = gamestate->movecapacity = 0;
}

static GameState gamestate_copy_sim(GameState *gamestate) {
    GameState simulation = *gamestate;

    /* create new move and position lists for the simulation */
    simulation.movecapacity = 4;
    simulation.movecount = 0;
    simulation.moves = malloc(4 * sizeof(Move));
    simulation.fen = malloc(4 * sizeof(char*));

    /* copy the most recent move and position if a move was played */
    if (gamestate->movecount > 0) {
        simulation.fen_start = strdup(gamestate->movecount == 1 ?
            gamestate->fen_start : gamestate->fen[gamestate->movecount - 2]);
        simulation.moves[0] = gamestate->moves[gamestate->movecount - 1];
        simulation.fen[0] = strdup(gamestate->fen[gamestate->movecount - 1]);
        simulation.movecount++;
    } else {
        simulation.fen_start = strdup(gamestate->fen_start);
    }

    return simulation;
}

Color current_color(GameState *gamestate) {
    return (gamestate->movecount % 2 == 0) ? WHITE : BLACK;
}

/* MUST be called BETWEEN validating AND applying a move to work correctly */
static void format_move(GameState *gamestate, Move *move) {
    char *string = &(move->string[0]);
    
    /* at least 8 characters should be available, wipe them out */
    memset(string, 0, 8);
    
    unsigned int idx;
    if (piece_type(move->piece) == KING &&
            abs(move->tofile-move->fromfile) == 2) {
        /* special formats for castling */
        if (move->tofile==fileidx('c')) {
            memcpy(string, "O-O-O", 5);
            idx = 5;
        } else {
            memcpy(string, "O-O", 3);
            idx = 3;
        }
    } else {
        /* start by notating the piece character */
        string[0] = getpiecechr(move->piece);
        idx = string[0] ? 1 : 0;

        /* find out how many source information we do need */
        if (piece_type(move->piece) == PAWN) {
            if (move->capture) {
                string[idx++] = filechr(move->fromfile);
            }
        } else if (piece_type(move->piece) != KING) {
            /* resolve ambiguities, if any */
            Move threats[16];
            size_t threatcount;
            if (get_threats(gamestate, move->torow, move->tofile,
                    piece_color(move->piece), threats, &threatcount)) {
                unsigned int ambrows = 0, ambfiles = 0, ambpiece = 0;
                for (size_t i = 0 ; i < threatcount ; i++) {
                    if (threats[i].piece == move->piece) {
                        ambpiece++;
                        if (threats[i].fromrow == move->fromrow) {
                            ambrows++;
                        }
                        if (threats[i].fromfile == move->fromfile) {
                            ambfiles++;
                        }
                    }
                }
                /* neither file, nor row are ambiguous, name file */
                if (ambpiece > 1 && ambrows == 1 && ambfiles == 1) {
                    /* this is most likely the case with Knights
                     * in diagonal opposition */
                    string[idx++] = filechr(move->fromfile);
                } else {
                    /* ambiguous row, name file */
                    if (ambrows > 1) {
                        string[idx++] = filechr(move->fromfile);
                    }
                    /* ambiguous file, name row */
                    if (ambfiles > 1) {
                        string[idx++] = rowchr(move->fromrow);
                    }
                }
            }
        }

        /* capturing? */
        if (move->capture) {
            string[idx++] = 'x';
        }

        /* destination */
        string[idx++] = filechr(move->tofile);
        string[idx++] = rowchr(move->torow);

        /* promotion? */
        if (move->promotion) {
            string[idx++] = '=';
            string[idx++] = getpiecechr(move->promotion);
        }
    }
    
    /* check? */
    if (move->check) {
        string[idx++] = gamestate->checkmate?'#':'+';
    }
}

static void calc_movetime(GameState *gamestate, Move *move) {
    struct timeval curtimestamp;
    gettimeofday(&curtimestamp, NULL);
    move->timestamp.tv_sec = curtimestamp.tv_sec;
    move->timestamp.tv_usec = (int32_t) curtimestamp.tv_usec;
    move->movetime.tv_usec = 0;
    move->movetime.tv_sec = 0;
    if (gamestate->movecount > 1) {
        struct movetimeval lasttstamp =
            gamestate->moves[gamestate->movecount - 1].timestamp;
        uint64_t sec = curtimestamp.tv_sec - lasttstamp.tv_sec;
        suseconds_t micros;
        if (curtimestamp.tv_usec < lasttstamp.tv_usec) {
            micros = 1000000-(lasttstamp.tv_usec - curtimestamp.tv_usec);
            sec--;
        } else {
            micros = curtimestamp.tv_usec - lasttstamp.tv_usec;
        }
        
        while (micros >= 1000000) {
            micros -= 1000000;
            sec++;
        }

        if (sec >= gamestate->info.delay) {
            move->movetime.tv_sec = sec;
            move->movetime.tv_usec = (int32_t) micros;
        }
    }
}

char getpiecechr(Piece piece) {
    switch (piece_type(piece)) {
    case ROOK: return 'R';
    case KNIGHT: return 'N';
    case BISHOP: return 'B';
    case QUEEN: return 'Q';
    case KING: return 'K';
    default: return '\0';
    }
}

char* getpieceunicode(Piece piece) {
    if (piece_color(piece) == WHITE) {
        switch (piece_type(piece)) {
        case PAWN: return "\u2659";
        case ROOK: return "\u2656";
        case KNIGHT: return "\u2658";
        case BISHOP: return "\u2657";
        case QUEEN: return "\u2655";
        case KING: return "\u2654";
        default: return "";
        }
    } else {
        switch (piece_type(piece)) {
        case PAWN: return "\u265f";
        case ROOK: return "\u265c";
        case KNIGHT: return "\u265e";
        case BISHOP: return "\u265d";
        case QUEEN: return "\u265b";
        case KING: return "\u265a";
        default: return "";
        }
    }
}

Piece getpiece(char c, Color color) {
    switch (c) {
        case 'R': return mkpiece(ROOK, color);
        case 'N': return mkpiece(KNIGHT, color);
        case 'B': return mkpiece(BISHOP, color);
        case 'Q': return mkpiece(QUEEN, color);
        case 'K': return mkpiece(KING, color);
        default: return 0;
    }
}

// TODO: check if we really need this "simulate" flag for performance
static void apply_move_impl(GameState *gamestate, Move *move, bool simulate) {
    /* format move before moving (s.t. ambiguities can be resolved) */
    if (!simulate) {
        if (!move->string[0]) {
            format_move(gamestate, move);
        }
    }

    /* en passant capture */
    if (move->capture && piece_type(move->piece) == PAWN &&
            piece_at(gamestate, mdst(move)) == 0) {
        piece_remove(gamestate, move->fromrow, move->tofile);
    }
    
    /* remove old en passant threats */
    for (File file = 0 ; file < 8 ; file++) {
        enpassant_threat_remove(gamestate, 3, file);
        enpassant_threat_remove(gamestate, 4, file);
    }
    
    /* move (and maybe capture or promote) */
    piece_remove(gamestate, msrc(move));
    if (move->promotion) {
        piece_set(gamestate, mdst(move), move->promotion);
    } else {
        piece_set(gamestate, mdst(move), move->piece);
    }

    /* add new en passant threat */
    if (piece_type(move->piece) == PAWN && (
            (move->fromrow == 1 && move->torow == 3) ||
            (move->fromrow == 6 && move->torow == 4))) {
        enpassant_threat_add(gamestate, move->torow, move->tofile);
    }
    
    /* castling */
    if (piece_type(move->piece) == KING && move->fromfile == fileidx('e')) {
        const Color color = piece_color(move->piece);
        if (move->tofile == fileidx('g')) {
            gamestate->board[move->torow][fileidx('h')] = 0;
            gamestate->board[move->torow][fileidx('f')] = mkpiece(ROOK, color);
        } else if (move->tofile == fileidx('c')) {
            gamestate->board[move->torow][fileidx('a')] = 0;
            gamestate->board[move->torow][fileidx('d')] = mkpiece(ROOK, color);
        }
    }
    
    /* add move to the moves array and the new position to the FEN array */
    if (gamestate->movecount == gamestate->movecapacity) {
        gamestate->movecapacity += 64; /* 32 more full moves */
        gamestate->moves = realloc(gamestate->moves,
            gamestate->movecapacity * sizeof(Move));
        gamestate->fen = realloc(gamestate->fen,
            gamestate->movecapacity * sizeof(char*));
    }

    /* copy the move data into the game's move array */
    Move *melem = &gamestate->moves[gamestate->movecount];
    *melem = *move;

    /* calculate the FEN and store it in the FEN array */
    char fen[FEN_MAX_LENGTH];
    fen_compute(fen, gamestate);
    gamestate->fen[gamestate->movecount] = strdup(fen);

    /* only if move has no time info, compute it */
    if (melem->movetime.tv_sec == 0 && melem->movetime.tv_usec == 0) {
        calc_movetime(gamestate, melem);
    }

    /* important: only "add" the move after calculating the time! */
    gamestate->movecount++;
}

void apply_move(GameState *gamestate, Move *move) {
    apply_move_impl(gamestate, move, false);
}

void gamestate_at_move(GameState *gamestate,
        unsigned move_number, GameState *replay) {
    gamestate_init(replay);
    memcpy(&replay->info, &gamestate->info, sizeof(GameInfo));
    replay->review = true;
    if (move_number > gamestate->movecount) {
        move_number = gamestate->movecount;
    }
    for (unsigned i = 0 ; i < move_number ; i++) {
        apply_move_impl(replay, &(gamestate->moves[i]), true);
    }
}

static int validate_move_rules(GameState *gamestate, Move *move) {
    assert((move->piece & ~(PIECE_MASK|COLOR_MASK)) == 0);

    /* validate indices (don't trust opponent) */
    if (!isidx(move->fromrow) || !isidx(move->fromfile) ||
        !isidx(move->torow) || !isidx(move->tofile)) {
        return INVALID_MOVE_SYNTAX;
    }
    
    /* must move */
    if (move->fromfile == move->tofile && move->fromrow == move->torow) {
        return INVALID_MOVE_SYNTAX;
    }
    
    /* does piece exist */
    if (piece_at(gamestate, msrc(move)) != move->piece) {
        return PIECE_NOT_FOUND;
    }

    /* is there any piece at the destination? */
    Piece piece_at_dst = piece_at(gamestate, mdst(move));
    
    /* can't capture own pieces */
    if (piece_color(piece_at_dst) == piece_color(move->piece)) {
        return RULES_VIOLATED;
    }

    /* must capture, if and only if destination is occupied... */
    if (!((piece_at_dst == 0) ^ move->capture)) {
        /* ... or the capture happens en passant */
        if (!move->capture || piece_type(move->piece) != PAWN ||
                !enpassant_threat_exists(gamestate,
                    move->fromrow, move->tofile)) {
            return INVALID_MOVE_SYNTAX;
        }
    }
    
    /* validate individual rules */
    bool chkrules;
    switch (piece_type(move->piece)) {
    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;
    }
    
    /* simulate move for check validation */
    GameState simulation = gamestate_copy_sim(gamestate);
    Move simmove = *move;
    apply_move_impl(&simulation, &simmove, true);
    
    /* find kings for check validation */
    Color piececolor = piece_color(move->piece);
    Color oppcolor = opponent_color(piececolor);
    
    File mykingfile = 0, opkingfile = 0;
    Row  mykingrow = 0, opkingrow = 0;
    for (Row row = 0 ; row < 8 ; row++) {
        for (File file = 0 ; file < 8 ; file++) {
            Piece p = piece_at(&simulation, row, file);
            if (p == mkpiece(KING, piececolor)) {
                mykingfile = file;
                mykingrow = row;
            } else if (p == mkpiece(KING, oppcolor)) {
                opkingfile = file;
                opkingrow = row;
            }
        }
    }
    
    /* don't move into or stay in check position */
    if (is_covered(&simulation, mykingrow, mykingfile, oppcolor)) {
        gamestate_cleanup(&simulation);
        if (piece_type(move->piece) == KING) {
            return KING_MOVES_INTO_CHECK;
        } else {
            if (gamestate->moves[gamestate->movecount - 1].check) {
                return KING_IN_CHECK;
            } else {
                return PIECE_PINNED;
            }
        }
    }
    
    /* correct check and checkmate flags (move is still valid) */
    Move threats[16];
    size_t threatcount;
    move->check = get_threats(&simulation, opkingrow, opkingfile,
        piececolor, threats, &threatcount);
    
    if (move->check) {
        /* determine possible escape fields */
        bool canescape = false;
        for (int dr = -1 ; dr <= 1 && !canescape ; dr++) {
            for (int df = -1 ; df <= 1 && !canescape ; df++) {
                if (dr == 0 && df == 0) continue;
                if (!isidx(opkingrow + dr)) continue;
                if (!isidx(opkingfile + df)) continue;
                Row er = opkingrow + dr;
                File ef = opkingfile + df;

                /* check if escape field is already covered (threatened) */
                if (is_covered(&simulation, er, ef, piececolor))
                    continue;

                /* check if piece of the king's color blocks the field */
                if (piece_color(simulation.board[er][ef]) == oppcolor)
                    continue;

                /* check if an attacking piece blocks the field */
                if (piece_color(simulation.board[er][ef]) == piececolor) {
                    /* test if the king can fight back */
                    GameState sim_retaliate = gamestate_copy_sim(&simulation);
                    Move move_retaliate = {0};
                    move_retaliate.piece = mkpiece(KING, oppcolor);
                    move_retaliate.fromrow = opkingrow;
                    move_retaliate.fromfile = opkingfile;
                    move_retaliate.torow = er;
                    move_retaliate.tofile = ef;
                    move_retaliate.capture = 1;
                    apply_move_impl(&sim_retaliate, &move_retaliate, true);
                    canescape = !is_covered(&sim_retaliate, er, ef, piececolor);
                    gamestate_cleanup(&sim_retaliate);
                } else {
                    /* the field is not covered and unoccupied */
                    canescape = true;
                }
            }
        }

        /* can't escape, can the king be rescued? */
        if (!canescape && threatcount == 1) {
            canescape = is_protected(&simulation,
                    threats[0].fromrow, threats[0].fromfile, oppcolor);
        }
        
        /* can't capture, can he block? */
        if (!canescape && threatcount == 1) {
            Move *threat = &(threats[0]);
            unsigned tptype = piece_type(threat->piece);
            
            /* knight, pawns and the king cannot be blocked */
            if (tptype == BISHOP || tptype == ROOK || tptype == QUEEN) {
                if (threat->fromrow == threat->torow) {
                    /* rook aspect (on row) */
                    int d = threat->tofile > threat->fromfile ? 1 : -1;
                    File file = threat->fromfile;
                    while (!canescape && file != threat->tofile - d) {
                        file += d;
                        canescape |= is_protected(&simulation,
                            threat->torow, file, oppcolor);
                    }
                } else if (threat->fromfile == threat->tofile) {
                    /* rook aspect (on file) */
                    int d = threat->torow > threat->fromrow ? 1 : -1;
                    Row row = threat->fromrow;
                    while (!canescape && row != threat->torow - d) {
                        row += d;
                        canescape |= is_protected(&simulation,
                            row, threat->tofile, oppcolor);
                    }
                } else {
                    /* bishop aspect */
                    int dr = threat->torow > threat->fromrow ? 1 : -1;
                    int df = threat->tofile > threat->fromfile ? 1 : -1;

                    Row row = threat->fromrow;
                    File file = threat->fromfile;
                    while (!canescape && file != threat->tofile - df
                            && row != threat->torow - dr) {
                        row += dr;
                        file += df;
                        canescape |= is_protected(&simulation, row, file,
                            oppcolor);
                    }
                }
            }
        }
            
        if (!canescape) {
            gamestate->checkmate = true;
        }
    }
    
    gamestate_cleanup(&simulation);
    
    return VALID_MOVE_SEMANTICS;
}

Piece piece_at(const GameState *gamestate, Row row, File file) {
    return gamestate->board[row][file] & (PIECE_MASK|COLOR_MASK);
}

void piece_set(GameState *gamestate, Row row, File file, Piece piece) {
    gamestate->board[row][file] = piece;
}

bool get_threats(GameState *gamestate, Row row, File file,
        Color color, Move *threats, size_t *threatcount) {
    Move candidates[32];
    size_t ccount = 0;
    for (Row r = 0 ; r < 8 ; r++) {
        for (File f = 0 ; f < 8 ; f++) {
            if (piece_color(gamestate->board[r][f]) == color) {
                /* non-capturing move */
                memset(&(candidates[ccount]), 0, sizeof(Move));
                Piece p = piece_at(gamestate, r, f);
                candidates[ccount].piece = p;
                candidates[ccount].fromrow = r;
                candidates[ccount].fromfile = f;
                candidates[ccount].torow = row;
                candidates[ccount].tofile = file;
                if (piece_type(p) == PAWN && (row == 0 || row == 7)) {
                    /* the exact piece for promotion does not matter */
                    candidates[ccount].promotion = mkpiece(QUEEN, color);
                }
                ccount++;

                /* capturing move */
                memcpy(&(candidates[ccount]),
                    &(candidates[ccount-1]), sizeof(Move));
                candidates[ccount].capture = 1;
                ccount++;
            }
        }
    }

    if (threatcount) {
        *threatcount = 0;
    }
    
    
    bool result = false;
    
    for (size_t i = 0 ; i < ccount ; i++) {
        if (validate_move_rules(gamestate, &(candidates[i]))
                == VALID_MOVE_SEMANTICS) {
            result = true;
            if (threats && threatcount) {
                threats[(*threatcount)++] = candidates[i];
            }
        }
    }
    
    return result;
}

bool is_pinned(GameState *gamestate, Move *move) {
    Color color = piece_color(move->piece);

    GameState simulation = gamestate_copy_sim(gamestate);
    Move simmove = *move;
    apply_move(&simulation, &simmove);
    
    File kingfile = 0;
    Row kingrow = 0;
    for (Row row = 0 ; row < 8 ; row++) {
        for (File file = 0 ; file < 8 ; file++) {
            if (simulation.board[row][file] == (color|KING)) {
                kingfile = file;
                kingrow = row;
            }
        }
    }
    
    bool covered = is_covered(&simulation,
        kingrow, kingfile, opponent_color(color));
    gamestate_cleanup(&simulation);
    
    return covered;
}

bool get_real_threats(GameState *gamestate, Row row, File file,
        Color color, Move *threats, size_t *threatcount) {
    
    if (threatcount) {
        *threatcount = 0;
    }

    Move candidates[16];
    size_t candidatecount;
    if (get_threats(gamestate, row, file, color, candidates, &candidatecount)) {
        
        bool result = false;
        File kingfile = 0;
        Row kingrow = 0;
        for (Row r = 0 ; r < 8 ; r++) {
            for (File f = 0 ; f < 8 ; f++) {
                if (gamestate->board[r][f] == (color|KING)) {
                    kingfile = f;
                    kingrow = r;
                }
            }
        }

        for (size_t i = 0 ; i < candidatecount ; i++) {
            // TODO: check if we really need full-blown simulations here
            GameState simulation = gamestate_copy_sim(gamestate);
            Move simmove = candidates[i];
            apply_move(&simulation, &simmove);
            if (!is_covered(&simulation, kingrow, kingfile,
                    opponent_color(color))) {
                result = true;
                if (threats && threatcount) {
                    threats[(*threatcount)++] = candidates[i];
                }
            }
            gamestate_cleanup(&simulation);
        }
        
        return result;
    } else {
        return false;
    }
}

static int getlocation(GameState *gamestate, Move *move) {   

    Color color = piece_color(move->piece);
    bool incheck = false;
    if (gamestate->movecount > 0) {
        incheck = gamestate->moves[gamestate->movecount - 1].check;
    }
    
    Move threats[16], *threat = NULL;
    size_t threatcount;

    /* determine all threats and sort out the unreal threats on our own */
    if (get_threats(gamestate, move->torow, move->tofile, color,
            threats, &threatcount)) {
        
        bool found = false;
        
        /* find threats for the specified position */
        for (size_t i = 0 ; i < threatcount ; i++) {
            if (threats[i].piece == move->piece &&
                    (move->fromrow == POS_UNSPECIFIED ||
                    move->fromrow == threats[i].fromrow) &&
                    (move->fromfile == POS_UNSPECIFIED ||
                    move->fromfile == threats[i].fromfile)) {

                /* found a threat, here it does not matter if it's valid! */
                found = true;

                /* discard pinned pieces */
                if (!is_pinned(gamestate, &(threats[i]))) {
                    if (threat) {
                        /* we've already found a valid threat */
                        return AMBIGUOUS_MOVE;
                    } else {
                        threat = &(threats[i]);
                    }
                }
            }
        }
        
        /* can't threaten specified position */
        if (!threat) {
            if (found) {
                if (piece_type(move->piece) == KING) {
                    return KING_MOVES_INTO_CHECK;
                } else if (incheck) {
                    return KING_IN_CHECK;
                } else {
                    return PIECE_PINNED;
                }
            } else {
                return PIECE_NOT_FOUND;
            }
        }

        /* found a threat, copy the source location */
        move->fromrow = threat->fromrow;
        move->fromfile = threat->fromfile;
        return VALID_MOVE_SYNTAX;
    } else {
        return PIECE_NOT_FOUND;
    }
}

static int eval_move1(const char *pstr, Move *move, Color color) {
    memset(move, 0, sizeof(Move));
    move->fromfile = POS_UNSPECIFIED;
    move->fromrow = POS_UNSPECIFIED;

    size_t len = strlen(pstr);
    if (len < 1 || len > 6) {
        return INVALID_MOVE_SYNTAX;
    }
    char mstr[8];
    strcpy(mstr, pstr);
    
    /* evaluate check/checkmate flags */
    if (mstr[len-1] == '+' || mstr[len-1] == '#') {
        len--; mstr[len] = '\0';
        move->check = true;
    }
    
    /* evaluate promotion */
    if (len > 3 && mstr[len-2] == '=') {
        move->promotion = getpiece(mstr[len-1], color);
        if (!move->promotion) {
            return INVALID_MOVE_SYNTAX;
        } else {
            len -= 2;
            mstr[len] = 0;
        }
    }
    
    if (len == 2) {
        /* pawn move (e.g. "e4") */
        move->piece = mkpiece(PAWN, color);
        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 = mkpiece(KING, color);
            move->fromfile = fileidx('e');
            move->tofile = fileidx('g');
            move->fromrow = move->torow = color == WHITE ? 0 : 7;
        } else {
            /* move (e.g. "Nf3") */
            move->piece = getpiece(mstr[0], color);
            move->tofile = fileidx(mstr[1]);
            move->torow = rowidx(mstr[2]);
        }
    } else if (len == 4) {
        move->piece = getpiece(mstr[0], color);
        if (move->piece == 0) {
            move->piece = mkpiece(PAWN, color);
            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]);
                /* when the piece is a pawn, second char cannot be a file */
                if (piece_type(move->piece) == PAWN) {
                    /* invalidate the result */
                    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 = mkpiece(KING, color);
            move->fromfile = fileidx('e');
            move->tofile = fileidx('c');
            move->fromrow = move->torow = color == WHITE ? 0 : 7;
        } else {
            move->piece = getpiece(mstr[0], color);
            if (mstr[2] == 'x') {
                move->capture = 1;
                if (move->piece) {
                    /* capture (e.g. "Ndxf3" or "R1xh3") */
                    if (isfile(mstr[1])) {
                        move->fromfile = fileidx(mstr[1]);
                    } else if (isrow(mstr[1])) {
                        move->fromrow = rowidx(mstr[1]);
                    } else {
                        return INVALID_MOVE_SYNTAX;
                    }
                } else {
                    /* long notation capture (e.g. "e5xf6") */
                    move->piece = mkpiece(PAWN, color);
                    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], color);
            move->fromfile = fileidx(mstr[1]);
            move->fromrow = rowidx(mstr[2]);
            move->tofile = fileidx(mstr[4]);
            move->torow = rowidx(mstr[5]);
        }
    }

    
    if (!move->piece) {
        return INVALID_MOVE_SYNTAX;
    }

    if (piece_type(move->piece) == PAWN
            && move->torow == (color==WHITE?7:0)
            && !move->promotion) {
        return NEED_PROMOTION;
    }

    /* up to this point
     * destination indices must be specified and valid
     * source indices must either be valid or unspecified
     */
    if (!isidxr(move->fromrow) || !isidxr(move->fromfile) ||
        !isidx(move->torow) || !isidx(move->tofile)) {
        return INVALID_MOVE_SYNTAX;
    }

    return VALID_MOVE_SYNTAX;
}

int eval_move(GameState *gamestate, const char *mstr,
        Move *move, Color color) {
    int result = eval_move1(mstr, move, color);
    if (result == VALID_MOVE_SYNTAX) {
        if (move->fromfile == POS_UNSPECIFIED
            || move->fromrow == POS_UNSPECIFIED) {
            return getlocation(gamestate, move);
        }
    }
    return result;
}

int check_move(const char *mstr, Color color) {
    Move move;
    return eval_move1(mstr, &move, color);
}

bool is_protected(GameState *gamestate, Row row, File file, Color color) {
    Move threats[16];
    size_t threatcount;
    if (get_real_threats(gamestate, row, file, color, threats, &threatcount)) {
        for (size_t i = 0 ; i < threatcount ; i++) {
            if (threats[i].piece != (color|KING)) {
                return true;
            }
        }
        return false;
    } else {
        return false;
    }
}

uint16_t remaining_movetime(GameState *gamestate, Color color) {
    unsigned move_number = gamestate->movecount;
    if (color == BLACK) {
        move_number |= 1;
    } else {
        move_number = (move_number + 1) & ~1;
    }
    return remaining_movetime2(gamestate, move_number);
}

uint16_t remaining_movetime2(GameState *gamestate, unsigned move_number) {
    if (!gamestate->info.timecontrol) {
        return 0;
    }

    unsigned total_time = gamestate->info.time;
    unsigned used_time = 0;
    suseconds_t micros = 0;

    /* when this is a 0+X game, the clock starts with the increment */
    if (gamestate->info.time == 0) {
        total_time += gamestate->info.addtime;
    }

    /* go through all already played moves */
    unsigned first_move = move_number % 2;
    unsigned next_move = move_number;
    if (next_move > gamestate->movecount) next_move = gamestate->movecount;
    for (unsigned i = first_move ; i < next_move ; i += 2) {
        used_time += gamestate->moves[i].movetime.tv_sec;
        micros += gamestate->moves[i].movetime.tv_usec;
        /* add increments starting with move 2 */
        if (i > 1) total_time += gamestate->info.addtime;
    }

    /* apply microseconds */
    while (micros >= 1000000) {
        micros -= 1000000;
        used_time++;
    }

    /* when the player is currently playing, count down the clock */
    if (is_game_running(gamestate) && move_number > 1 &&
            move_number == gamestate->movecount) {
        struct movetimeval lastmovetstamp =
            gamestate->moves[move_number - 1].timestamp;
        struct timeval currenttstamp;
        gettimeofday(&currenttstamp, NULL);

        /* calculate current move time */
        unsigned cmsec = currenttstamp.tv_sec - lastmovetstamp.tv_sec;
        suseconds_t cmusec = currenttstamp.tv_usec - lastmovetstamp.tv_usec;

        /* add microseconds carried over from last move and apply both */
        cmusec += micros;
        cmsec += cmusec / 1000000;

        /* add the time and respect a possible dealy */
        if (cmsec >= gamestate->info.delay) {
            used_time += cmsec - gamestate->info.delay;
        }
    }

    return used_time >= total_time ? 0 : total_time - used_time;
}

int print_clk(uint16_t time, char *str, bool always_hours) {
    unsigned hours = time / 3600;
    unsigned minutes = (time % 3600) / 60;
    unsigned seconds = time % 60;
    if (hours > 0 || always_hours) {
        return snprintf(str, 9, "%u:%02u:%02u", hours, minutes, seconds);
    } else {
        return snprintf(str, 6, "%02u:%02u", minutes, seconds);
    }
}

bool check_threefold_repetition(GameState *gamestate) {
    // TODO: implement threefold repetition detection
    return false;
}