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(const 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(const 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(const 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 candidates[16];
            size_t ccount;
            if (get_real_candidates(gamestate, move->torow, move->tofile,
                    piece_color(move->piece), candidates, &ccount)) {
                unsigned int ambrows = 0, ambfiles = 0, ambpiece = 0;
                for (size_t i = 0 ; i < ccount ; i++) {
                    if (candidates[i].piece == move->piece) {
                        ambpiece++;
                        if (candidates[i].fromrow == move->fromrow) {
                            ambrows++;
                        }
                        if (candidates[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->checkmate) {
        string[idx++] = '#';
    } else if (move->check) {
        string[idx++] = '+';
    }
}

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;
        }
    }
}

size_t piece_moves_allowed(const GameState *gamestate,
        Row r, File f, Move *moves) {
    Piece p = piece_at(gamestate, r, f);
    Color c = piece_color(p);
    switch (piece_type(p)) {
        case KING:
            return king_moves_allowed(gamestate, c, r, f, moves);
        case QUEEN:
            return queen_moves_allowed(gamestate, c, r, f, moves);
        case ROOK:
            return rook_moves_allowed(gamestate, c, r, f, moves);
        case KNIGHT:
            return knight_moves_allowed(gamestate, c, r, f, moves);
        case BISHOP:
            return bishop_moves_allowed(gamestate, c, r, f, moves);
        case PAWN:
            return pawn_moves_allowed(gamestate, c, r, f, moves);
        default:
            return 0;
    }
}

static bool check_stalemate(const GameState *gamestate) {
    Color next_player = gamestate->movecount % 2 == 0 ? WHITE : BLACK;

    /* scan the board for pieces of the next player's color */
    Move moves[QUEEN_MOVES_MAX];
    for (Row r = 0; r < 8; r++) {
        for (File f = 0; f < 8; f++) {
            if (piece_color(piece_at(gamestate, r, f)) == next_player
                && piece_moves_allowed(gamestate, r, f, moves) > 0) {
                return false;
            }
        }
    }

    return true;
}

static size_t fen_len_without_moves(const char *fen) {
    size_t len = strlen(fen);
    /* find first space that separates the two move counters */
    while (--len > 0 && fen[len] != ' ') {}
    /* find second space that separates the move counters from the rest */
    while (--len > 0 && fen[len] != ' ') {}
    return len;
}

bool check_threefold_repetition(const GameState *gamestate) {
    if (gamestate->movecount < 3) {
        return false;
    }

    /* take the part of the FEN that only describes the board */
    const char *fen = gamestate->fen[gamestate->movecount - 1];
    size_t fen_len = fen_len_without_moves(fen);

    // TODO: develop a test case that involves en passant and add support here

    /* count the previous occurrences */
    unsigned c = 0;
    for (size_t i = gamestate->movecount - 1; i > 0;) {
        const char *other = gamestate->fen[--i];
        size_t other_len = fen_len_without_moves(other);
        if (fen_len != other_len) continue;
        if (strncmp(fen, other, fen_len) == 0) {
            if (++c == 2) return true;
        }
    }
    return false;
}

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;
    }
}

/* applies the move without recalculating gamestate flags */
static void apply_move_internal(GameState *gamestate, Move *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_internal(gamestate, move);

    /* calculate gamestate flags in order of efficiency */
    if (move->checkmate) {
        gamestate->checkmate = true;
    } else if (check_threefold_repetition(gamestate)) {
        gamestate->threefold = true;
    } else if (check_stalemate(gamestate)) {
        gamestate->stalemate = true;
    }
}

void gamestate_at_move(const 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(replay, &(gamestate->moves[i]));
    }
}

/* return 0 = no check, 1 = check, 2 = checkmate */
static int determine_check_or_checkmate(
        const GameState *gamestate, const Move *move) {

    /* simulate the move */
    GameState simulation = gamestate_copy_sim(gamestate);
    Move simmove = *move;
    apply_move_internal(&simulation, &simmove);

    /* find the opposing king */
    Color piececolor = piece_color(move->piece);
    Color oppcolor = opponent_color(piececolor);
    File opkingfile = 0;
    Row 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, oppcolor)) {
                opkingfile = file;
                opkingrow = row;
            }
        }
    }

    /* determine if the opposing king is now threatened */
    Move threats[16];
    size_t threatcount;
    bool incheck = get_threats(&simulation, opkingrow, opkingfile,
        piececolor, threats, &threatcount);

    if (!incheck) {
        gamestate_cleanup(&simulation);
        return 0;
    }

    /* 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;
            Row er = opkingrow + dr;
            File ef = opkingfile + df;
            if (!isidx(er) || !isidx(ef)) continue;

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

            /* check if escape field is already covered (threatened) */
            if (is_covered(&simulation, er, ef, piececolor))
                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 = true;
                apply_move_internal(&sim_retaliate, &move_retaliate);
                canescape = !is_covered(&sim_retaliate, er, ef, piececolor);
                gamestate_cleanup(&sim_retaliate);
                continue;
            }

            /* 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);
                }
            }
        }
    }
    gamestate_cleanup(&simulation);
    return canescape ? 1 : 2;
}

static int validate_move_rules(const GameState *gamestate, const 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_isblocked(gamestate, move);
            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(const GameState *gamestate, const Move *move) {
    int result = validate_move_rules(gamestate, move);
    if (result != VALID_MOVE_SEMANTICS) {
        return result;
    }

    /* test if the move would expose our own king */
    GameState simulation = gamestate_copy_sim(gamestate);
    Move simmove = *move;
    apply_move_internal(&simulation, &simmove);
    Color piececolor = piece_color(move->piece);
    Color oppcolor = opponent_color(piececolor);
    File kingfile = 0;
    Row kingrow = 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)) {
                kingfile = file;
                kingrow = row;
            }
        }
    }
    if (is_covered(&simulation, kingrow, kingfile, oppcolor)) {
        if (piece_type(move->piece) == KING) {
            result = KING_MOVES_INTO_CHECK;
        } else {
            if (is_check_position(gamestate)) {
                result = KING_IN_CHECK;
            } else {
                result = PIECE_PINNED;
            }
        }
    }
    gamestate_cleanup(&simulation);

    if (result != VALID_MOVE_SEMANTICS) {
        return result;
    }

    /* validate check and checkmate flags */
    int cocm = determine_check_or_checkmate(gamestate, move);
    if (cocm == 2) {
        if (!move->checkmate) {
            return MISSING_CHECKMATE;
        }
    } else if (cocm == 1) {
        if (!move->check) {
            return MISSING_CHECK;
        }
    } else if (move->checkmate) {
        return INVALID_CHECKMATE;
    } else if (move->check) {
        return INVALID_CHECK;
    }
    
    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_candidates(const GameState *gamestate, Row row, File file,
        Color color, Move *moves, size_t *movecount) {
    Move candidates[32];
    size_t ccount = 0;
    for (Row r = 0 ; r < 8 ; r++) {
        for (File f = 0 ; f < 8 ; f++) {
            Piece p = piece_at(gamestate, r, f);
            if (piece_color(p) == color) {
                /* non-capturing move */
                memset(&(candidates[ccount]), 0, sizeof(Move));
                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 = true;
                ccount++;
            }
        }
    }

    if (movecount) {
        *movecount = 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 (moves && movecount) {
                moves[(*movecount)++] = candidates[i];
            }
        }
    }

    return result;
}

bool get_threats(const GameState *gamestate, Row row, File file,
        Color color, Move *threats, size_t *threatcount) {

    /* simulate a capturing move on the target position */
    Color opcolor = opponent_color(color);
    GameState simulation = gamestate_copy_sim(gamestate);
    if (piece_color(piece_at(&simulation, row, file)) != opcolor) {
        /* set a fake pawn if the field is not occupied by the opponent */
        piece_set(&simulation, row, file, mkpiece(PAWN, opcolor));
    }

    Move candidates[16];
    size_t ccount = 0;
    for (Row r = 0 ; r < 8 ; r++) {
        for (File f = 0 ; f < 8 ; f++) {
            Piece p = piece_at(&simulation, r, f);
            if (piece_color(p) == color) {
                memset(&(candidates[ccount]), 0, sizeof(Move));
                candidates[ccount].piece = p;
                candidates[ccount].fromrow = r;
                candidates[ccount].fromfile = f;
                candidates[ccount].torow = row;
                candidates[ccount].tofile = file;
                candidates[ccount].capture = true;
                if (piece_type(p) == PAWN && (row == 0 || row == 7)) {
                    /* the exact piece for promotion does not matter */
                    candidates[ccount].promotion = mkpiece(QUEEN, color);
                }
                ccount++;
            }
        }
    }

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

    gamestate_cleanup(&simulation);
    
    return result;
}

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

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

bool get_real_candidates(const GameState *gamestate, Row row, File file,
        Color color, Move *moves, size_t *movecount) {

    if (movecount) {
        *movecount = 0;
    }

    Move candidates[16];
    size_t ccount;
    if (get_candidates(gamestate, row, file, color, candidates, &ccount)) {
        bool result = false;
        for (size_t i = 0 ; i < ccount ; i++) {
            if (!is_pinned(gamestate, &candidates[i])) {
                result = true;
                if (moves && movecount) {
                    moves[(*movecount)++] = candidates[i];
                }
            }
        }
        return result;
    } else {
        return false;
    }
}

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

    Move candidates[16];
    size_t ccount;
    if (get_threats(gamestate, row, file, color, candidates, &ccount)) {
        bool result = false;
        for (size_t i = 0 ; i < ccount ; i++) {
            if (!is_pinned(gamestate, &candidates[i])) {
                result = true;
                if (threats && threatcount) {
                    threats[(*threatcount)++] = candidates[i];
                }
            }
        }
        return result;
    } else {
        return false;
    }
}

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

    Color color = piece_color(move->piece);
    bool incheck = false;
    if (gamestate->movecount > 0) {
        incheck = is_check_position(gamestate);
    }
    
    Move candidates[16], *candidate = NULL;
    size_t candidatecount;

    /* determine all candidate moves and sort out the invalid ones */
    if (get_candidates(gamestate, move->torow, move->tofile, color,
            candidates, &candidatecount)) {
        
        bool found = false;
        
        for (size_t i = 0 ; i < candidatecount ; i++) {
            /* filter by partial fromrow/fromfile information */
            if (candidates[i].piece == move->piece &&
                    (move->fromrow == POS_UNSPECIFIED ||
                    move->fromrow == candidates[i].fromrow) &&
                    (move->fromfile == POS_UNSPECIFIED ||
                    move->fromfile == candidates[i].fromfile)) {

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

                /* discard pinned pieces */
                if (!is_pinned(gamestate, &(candidates[i]))) {
                    if (candidate) {
                        /* we've already found a valid candidate */
                        return AMBIGUOUS_MOVE;
                    } else {
                        candidate = &(candidates[i]);
                    }
                }
            }
        }
        
        /* no valid candidate left */
        if (!candidate) {
            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 candidate, copy the source location */
        move->fromrow = candidate->fromrow;
        move->fromfile = candidate->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] == '#') {
        move->check = true;
        move->checkmate = mstr[len-1] == '#';
        len--; mstr[len] = '\0';
    }
    
    /* 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 = true;
        } 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 = true;
                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 = true;
            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_move2(const GameState *gamestate,
        const char *mstr, Color color, Move *move, bool lazy) {
    int result = eval_move1(mstr, move, color);
    if (result == VALID_MOVE_SYNTAX) {
        if (move->fromfile == POS_UNSPECIFIED
            || move->fromrow == POS_UNSPECIFIED) {
            result = getlocation(gamestate, move);
        }
        if (result == VALID_MOVE_SYNTAX) {
            /* correct check/checkmate flags */
            if (lazy) {
                move->check = move->checkmate = false;
                switch (determine_check_or_checkmate(gamestate, move)) {
                    case 2: move->checkmate = true;
                    case 1: move->check = true;
                }
            }

            /* format the move string */
            format_move(gamestate, move);
        }
    }
    return result;
}

int eval_move_lazy(const GameState *gamestate,
        const char *mstr, Color color, Move *move) {
    return eval_move2(gamestate, mstr, color, move, true);
}

int eval_move(const GameState *gamestate,
        const char *mstr, Color color, Move *move) {
    return eval_move2(gamestate, mstr, color, move, false);
}

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

bool is_protected(const GameState *gamestate, Row row, File file, Color color) {
    Move candidates[16];
    size_t ccount;
    /* we need all candidates - not only threats! */
    if (get_candidates(gamestate, row, file, color, candidates, &ccount)) {
        for (size_t i = 0 ; i < ccount ; i++) {
            /* skip the king */
            if (piece_type(candidates[i].piece) == KING) continue;
            /* skip pinned pieces */
            if (is_pinned(gamestate, &candidates[i])) continue;
            /* found one */
            return true;
        }
    }
    return false;
}

uint16_t remaining_movetime(const 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(const 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);
    }
}

size_t filter_moves_allowed(const GameState *gamestate,
        Color c, Row r, File f, Move *moves, moves_generator_func func) {

    /* worst case: the queen has the most moves */
    Move candidates[QUEEN_MOVES_MAX];
    size_t candidatecount = func(gamestate, c, r, f, candidates);
    size_t count = 0;

    for (size_t i = 0 ; i < candidatecount ; i++) {
        if (validate_move(gamestate, &candidates[i]) == VALID_MOVE_SEMANTICS) {
            moves[count++] = candidates[i];
        }
    }

    return count;
}