src/chess/rules.c

/*
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
 *
 * Copyright 2014 Mike Becker. All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *
 *   1. Redistributions of source code must retain the above copyright
 *      notice, this list of conditions and the following disclaimer.
 *
 *   2. Redistributions in binary form must reproduce the above copyright
 *      notice, this list of conditions and the following disclaimer in the
 *      documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
 *
 */

#include "rules.h"
#include "chess.h"
#include <string.h>
#include <stdlib.h>
#include <sys/time.h>

static GameState gamestate_copy_sim(GameState *gamestate) {
    GameState simulation = *gamestate;
    if (simulation.lastmove) {
        MoveList *lastmovecopy = malloc(sizeof(MoveList));
        *lastmovecopy = *(simulation.lastmove);
        simulation.movelist = simulation.lastmove = lastmovecopy;
    }
        
    return simulation;
}

void gamestate_cleanup(GameState *gamestate) {
    MoveList *elem;
    elem = gamestate->movelist;
    while (elem) {
        MoveList *cur = elem;
        elem = elem->next;
        free(cur);
    };
}

static void addmove(GameState* gamestate, Move *move) {
    MoveList *elem = malloc(sizeof(MoveList));
    elem->next = NULL;
    elem->move = *move;
    
    struct timeval curtimestamp;
    gettimeofday(&curtimestamp, NULL);
    elem->move.timestamp.tv_sec = curtimestamp.tv_sec;
    elem->move.timestamp.tv_usec = curtimestamp.tv_usec;
    
    if (gamestate->lastmove) {
        struct movetimeval *lasttstamp = &(gamestate->lastmove->move.timestamp);
        uint64_t sec = curtimestamp.tv_sec - lasttstamp->tv_sec;
        suseconds_t micros;
        if (curtimestamp.tv_usec < lasttstamp->tv_usec) {
            micros = 1e6L-(lasttstamp->tv_usec - curtimestamp.tv_usec);
            sec--;
        } else {
            micros = curtimestamp.tv_usec - lasttstamp->tv_usec;
        }
        
        elem->move.movetime.tv_sec = sec;
        elem->move.movetime.tv_usec = micros;
        
        gamestate->lastmove->next = elem;
        gamestate->lastmove = elem;
    } else {
        elem->move.movetime.tv_usec = 0;
        elem->move.movetime.tv_sec = 0;
        gamestate->movelist = gamestate->lastmove = elem;
    }
}

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

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

void apply_move(GameState *gamestate, Move *move) {
    uint8_t piece = move->piece & PIECE_MASK;
    uint8_t color = move->piece & COLOR_MASK;
    
    /* en passant capture */
    if (move->capture && piece == PAWN &&
        mdst(gamestate->board, move) == 0) {
        gamestate->board[move->fromrow][move->tofile] = 0;
    }
    
    /* remove old en passant threats */
    for (uint8_t file = 0 ; file < 8 ; file++) {
        gamestate->board[3][file] &= ~ENPASSANT_THREAT;
        gamestate->board[4][file] &= ~ENPASSANT_THREAT;
    }
    
    /* add new en passant threat */
    if (piece == PAWN && (
        (move->fromrow == 1 && move->torow == 3) ||
        (move->fromrow == 6 && move->torow == 4))) {
        move->piece |= ENPASSANT_THREAT;
    }
    
    /* move (and maybe capture or promote) */
    msrc(gamestate->board, move) = 0;
    if (move->promotion) {
        mdst(gamestate->board, move) = move->promotion;
    } else {
        mdst(gamestate->board, move) = move->piece;
    }
    
    /* castling */
    if (piece == KING &&
        move->fromfile == fileidx('e')) {
        
        if (move->tofile == fileidx('g')) {
            gamestate->board[move->torow][fileidx('h')] = 0;
            gamestate->board[move->torow][fileidx('f')] = color|ROOK;
        } else if (move->tofile == fileidx('c')) {
            gamestate->board[move->torow][fileidx('a')] = 0;
            gamestate->board[move->torow][fileidx('d')] = color|ROOK;
        }
    }

    addmove(gamestate, move);
}

static int validate_move_rules(GameState *gamestate, Move *move) {
    /* validate indices (don't trust opponent) */
    if (!chkidx(move)) {
        return INVALID_POSITION;
    }
    
    /* must move */
    if (move->fromfile == move->tofile && move->fromrow == move->torow) {
        return INVALID_MOVE_SYNTAX;
    }
    
    /* does piece exist */
    if ((msrc(gamestate->board, move)&(PIECE_MASK|COLOR_MASK))
           != (move->piece&(PIECE_MASK|COLOR_MASK))) {
        return INVALID_POSITION;
    }
    
    /* can't capture own pieces */
    if ((mdst(gamestate->board, move) & COLOR_MASK)
            == (move->piece & COLOR_MASK)) {
        return RULES_VIOLATED;
    }
    
    /* must capture, if and only if destination is occupied */
    if ((mdst(gamestate->board, move) == 0 && move->capture) ||
            (mdst(gamestate->board, move) != 0 && !move->capture)) {
        return INVALID_MOVE_SYNTAX;
    }
    
    /* validate individual rules */
    _Bool chkrules;
    switch (move->piece & PIECE_MASK) {
    case PAWN:
        chkrules = pawn_chkrules(gamestate, move) &&
            !pawn_isblocked(gamestate, move);
        break;
    case ROOK:
        chkrules = rook_chkrules(move) &&
            !rook_isblocked(gamestate, move);
        break;
    case KNIGHT:
        chkrules = knight_chkrules(move); /* knight is never blocked */
        break;
    case BISHOP:
        chkrules = bishop_chkrules(move) &&
            !bishop_isblocked(gamestate, move);
        break;
    case QUEEN:
        chkrules = queen_chkrules(move) &&
            !queen_isblocked(gamestate, move);
        break;
    case KING:
        chkrules = king_chkrules(gamestate, move) &&
            !king_isblocked(gamestate, move);
        break;
    default:
        return INVALID_MOVE_SYNTAX;
    }
    
    return chkrules ? VALID_MOVE_SEMANTICS : RULES_VIOLATED;
}

int validate_move(GameState *gamestate, Move *move) {
    
    int result = validate_move_rules(gamestate, move);
    
    /* cancel processing to save resources */
    if (result != VALID_MOVE_SEMANTICS) {
        return result;
    }
    
    /* find kings for check validation */
    uint8_t piececolor = (move->piece & COLOR_MASK);
    
    uint8_t mykingfile = 0, mykingrow = 0, opkingfile = 0, opkingrow = 0;
    for (uint8_t row = 0 ; row < 8 ; row++) {
        for (uint8_t file = 0 ; file < 8 ; file++) {
            if (gamestate->board[row][file] ==
                    (piececolor == WHITE?WKING:BKING)) {
                mykingfile = file;
                mykingrow = row;
            } else if (gamestate->board[row][file] ==
                    (piececolor == WHITE?BKING:WKING)) {
                opkingfile = file;
                opkingrow = row;
            }
        }
    }
    
    /* simulate move for check validation */
    GameState simulation = gamestate_copy_sim(gamestate);
    Move simmove = *move;
    apply_move(&simulation, &simmove);
    
    /* don't move into or stay in check position */
    if (is_covered(&simulation, mykingrow, mykingfile,
        opponent_color(piececolor))) {
        
        gamestate_cleanup(&simulation);
        if ((move->piece & PIECE_MASK) == KING) {
            return KING_MOVES_INTO_CHECK;
        } else {
            /* last move is always not null in this case */
            return gamestate->lastmove->move.check ?
                KING_IN_CHECK : PIECE_PINNED;
        }
    }
    
    /* correct check and checkmate flags (move is still valid) */
    Move threats[16];
    uint8_t threatcount;
    move->check = get_threats(&simulation, opkingrow, opkingfile,
        piececolor, threats, &threatcount);
    
    if (move->check) {
        /* determine possible escape fields */
        _Bool canescape = 0;
        for (int dr = -1 ; dr <= 1 && !canescape ; dr++) {
            for (int df = -1 ; df <= 1 && !canescape ; df++) {
                if (!(dr == 0 && df == 0)  &&
                        isidx(opkingrow + dr) && isidx(opkingfile + df)) {
                    
                    /* escape field neither blocked nor covered */
                    if ((simulation.board[opkingrow + dr][opkingfile + df]
                            & COLOR_MASK) != opponent_color(piececolor)) {
                        canescape |= !is_covered(&simulation,
                            opkingrow + dr, opkingfile + df, piececolor);
                    }
                }
            }
        }
        /* can't escape, can he capture? */
        if (!canescape && threatcount == 1) {
            canescape = is_attacked(&simulation, threats[0].fromrow,
                threats[0].fromfile, opponent_color(piececolor));
        }
        
        /* can't capture, can he block? */
        if (!canescape && threatcount == 1) {
            Move *threat = &(threats[0]);
            uint8_t threatpiece = threat->piece & PIECE_MASK;
            
            /* knight, pawns and the king cannot be blocked */
            if (threatpiece == BISHOP || threatpiece == ROOK
                || threatpiece == QUEEN) {
                if (threat->fromrow == threat->torow) {
                    /* rook aspect (on row) */
                    int d = threat->tofile > threat->fromfile ? 1 : -1;
                    uint8_t file = threat->fromfile;
                    while (!canescape && file != threat->tofile - d) {
                        file += d;
                        canescape |= is_protected(&simulation,
                            threat->torow, file, opponent_color(piececolor));
                    }
                } else if (threat->fromfile == threat->tofile) {
                    /* rook aspect (on file) */
                    int d = threat->torow > threat->fromrow ? 1 : -1;
                    uint8_t row = threat->fromrow;
                    while (!canescape && row != threat->torow - d) {
                        row += d;
                        canescape |= is_protected(&simulation,
                            row, threat->tofile, opponent_color(piececolor));
                    }
                } else {
                    /* bishop aspect */
                    int dr = move->torow > move->fromrow ? 1 : -1;
                    int df = move->tofile > move->fromfile ? 1 : -1;

                    uint8_t row = move->fromrow;
                    uint8_t file = move->fromfile;
                    while (!canescape && file != move->tofile - df
                        && row != move->torow - dr) {
                        row += dr;
                        file += df;
                        canescape |= is_protected(&simulation, row, file,
                            opponent_color(piececolor));
                    }
                }
            }
        }
            
        if (!canescape) {
            gamestate->checkmate = 1;
        }
    }
    
    gamestate_cleanup(&simulation);
    
    return VALID_MOVE_SEMANTICS;
}

_Bool get_threats(GameState *gamestate, uint8_t row, uint8_t file,
        uint8_t color, Move *threats, uint8_t *threatcount) {
    Move candidates[32];
    int candidatecount = 0;
    for (uint8_t r = 0 ; r < 8 ; r++) {
        for (uint8_t f = 0 ; f < 8 ; f++) {
            if ((gamestate->board[r][f] & COLOR_MASK) == color) {
                // non-capturing move
                memset(&(candidates[candidatecount]), 0, sizeof(Move));
                candidates[candidatecount].piece = gamestate->board[r][f];
                candidates[candidatecount].fromrow = r;
                candidates[candidatecount].fromfile = f;
                candidates[candidatecount].torow = row;
                candidates[candidatecount].tofile = file;
                candidatecount++;

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

    if (threatcount) {
        *threatcount = 0;
    }
    
    
    _Bool result = 0;
    
    for (int i = 0 ; i < candidatecount ; i++) {
        if (validate_move_rules(gamestate, &(candidates[i]))
                == VALID_MOVE_SEMANTICS) {
            result = 1;
            if (threats && threatcount) {
                threats[(*threatcount)++] = candidates[i];
            }
        }
    }
    
    return result;
}

_Bool is_pinned(GameState *gamestate, Move *move) {
    uint8_t color = move->piece & COLOR_MASK;

    uint8_t kingfile = 0, kingrow = 0;
    for (uint8_t row = 0 ; row < 8 ; row++) {
        for (uint8_t file = 0 ; file < 8 ; file++) {
            if (gamestate->board[row][file] == (color|KING)) {
                kingfile = file;
                kingrow = row;
            }
        }
    }

    GameState simulation = gamestate_copy_sim(gamestate);
    Move simmove = *move;
    apply_move(&simulation, &simmove);
    _Bool covered = is_covered(&simulation,
        kingrow, kingfile, opponent_color(color));
    gamestate_cleanup(&simulation);
    
    return covered;
}

_Bool get_real_threats(GameState *gamestate, uint8_t row, uint8_t file,
        uint8_t color, Move *threats, uint8_t *threatcount) {
    
    if (threatcount) {
        *threatcount = 0;
    }

    Move candidates[16];
    uint8_t candidatecount;
    if (get_threats(gamestate, row, file, color, candidates, &candidatecount)) {
        
        _Bool result = 0;
        uint8_t kingfile = 0, kingrow = 0;
        for (uint8_t row = 0 ; row < 8 ; row++) {
            for (uint8_t file = 0 ; file < 8 ; file++) {
                if (gamestate->board[row][file] == (color|KING)) {
                    kingfile = file;
                    kingrow = row;
                }
            }
        }

        for (uint8_t i = 0 ; i < candidatecount ; i++) {
            GameState simulation = gamestate_copy_sim(gamestate);
            Move simmove = candidates[i];
            apply_move(&simulation, &simmove);
            if (!is_covered(&simulation, kingrow, kingfile,
                    opponent_color(color))) {
                result = 1;
                if (threats && threatcount) {
                    threats[(*threatcount)++] = candidates[i];
                }
            }
            gamestate_cleanup(&simulation);
        }
        
        return result;
    } else {
        return 0;
    }
}

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

    uint8_t color = move->piece & COLOR_MASK;
    _Bool incheck = gamestate->lastmove?gamestate->lastmove->move.check:0;
    
    Move threats[16], *threat = NULL;
    uint8_t threatcount;
    
    if (get_threats(gamestate, move->torow, move->tofile, color,
            threats, &threatcount)) {
        
        // find threats for the specified position
        for (uint8_t i = 0 ; i < threatcount ; i++) {
            if ((threats[i].piece & (PIECE_MASK | COLOR_MASK))
                    == move->piece &&
                    (move->fromrow == POS_UNSPECIFIED ||
                    move->fromrow == threats[i].fromrow) &&
                    (move->fromfile == POS_UNSPECIFIED ||
                    move->fromfile == threats[i].fromfile)) {

                if (threat) {
                    return AMBIGUOUS_MOVE;
                } else {
                    threat = &(threats[i]);
                }
            }
        }
        
        // can't threaten specified position
        if (!threat) {
            return INVALID_POSITION;
        }

        // found threat is no real threat
        if (is_pinned(gamestate, threat)) {
            return incheck?KING_IN_CHECK:PIECE_PINNED;
        } else {
            memcpy(move, threat, sizeof(Move));
            return VALID_MOVE_SYNTAX;
        }
    } else {
        return INVALID_POSITION;
    }
}

int eval_move(GameState *gamestate, char *mstr, Move *move) {
    memset(move, 0, sizeof(Move));
    move->fromfile = POS_UNSPECIFIED;
    move->fromrow = POS_UNSPECIFIED;

    size_t len = strlen(mstr);
    if (len < 1 || len > 6) {
        return INVALID_MOVE_SYNTAX;
    }
    
    /* evaluate check/checkmate flags */
    if (mstr[len-1] == '+') {
        len--; mstr[len] = '\0';
        move->check = 1;
    } else if (mstr[len-1] == '#') {
        len--; mstr[len] = '\0';
        /* ignore - validation should set game state */
    }
    
    /* evaluate promotion */
    if (len > 3 && mstr[len-2] == '=') {
        move->promotion = getpiece(mstr[len-1]);
        if (!move->promotion) {
            return INVALID_MOVE_SYNTAX;
        } else {
            move->promotion |= gamestate->mycolor;
            len -= 2;
            mstr[len] = 0;
        }
    }
    
    if (len == 2) {
        /* pawn move (e.g. "e4") */
        move->piece = PAWN;
        move->tofile = fileidx(mstr[0]);
        move->torow = rowidx(mstr[1]);
    } else if (len == 3) {
        if (strcmp(mstr, "O-O") == 0) {
            /* king side castling */
            move->piece = KING;
            move->fromfile = fileidx('e');
            move->tofile = fileidx('g');
            move->fromrow = move->torow = gamestate->mycolor == WHITE ? 0 : 7;
        } else {
            /* move (e.g. "Nf3") */
            move->piece = getpiece(mstr[0]);
            move->tofile = fileidx(mstr[1]);
            move->torow = rowidx(mstr[2]);
        }
    } else if (len == 4) {
        move->piece = getpiece(mstr[0]);
        if (!move->piece) {
            move->piece = PAWN;
            move->fromfile = fileidx(mstr[0]);
        }
        if (mstr[1] == 'x') {
            /* capture (e.g. "Nxf3", "dxe5") */
            move->capture = 1;
        } else {
            /* move (e.g. "Ndf3", "N2c3", "e2e4") */
            if (isfile(mstr[1])) {
                move->fromfile = fileidx(mstr[1]);
                if (move->piece == PAWN) {
                    move->piece = 0;
                }
            } else {
                move->fromrow = rowidx(mstr[1]);
            }
        }
        move->tofile = fileidx(mstr[2]);
        move->torow = rowidx(mstr[3]);
    } else if (len == 5) {
        if (strcmp(mstr, "O-O-O") == 0) {
            /* queen side castling "O-O-O" */
            move->piece = KING;
            move->fromfile = fileidx('e');
            move->tofile = fileidx('c');
            move->fromrow = move->torow = gamestate->mycolor == WHITE ? 0 : 7;
        } else {
            move->piece = getpiece(mstr[0]);
            if (mstr[2] == 'x') {
                move->capture = 1;
                if (move->piece) {
                    /* capture (e.g. "Ndxf3") */
                    move->fromfile = fileidx(mstr[1]);
                } else {
                    /* long notation capture (e.g. "e5xf6") */
                    move->piece = PAWN;
                    move->fromfile = fileidx(mstr[0]);
                    move->fromrow = rowidx(mstr[1]);
                }
            } else {
                /* long notation move (e.g. "Nc5a4") */
                move->fromfile = fileidx(mstr[1]);
                move->fromrow = rowidx(mstr[2]);
            }
            move->tofile = fileidx(mstr[3]);
            move->torow = rowidx(mstr[4]);
        }
    } else if (len == 6) {
        /* long notation capture (e.g. "Nc5xf3") */
        if (mstr[3] == 'x') {
            move->capture = 1;
            move->piece = getpiece(mstr[0]);
            move->fromfile = fileidx(mstr[1]);
            move->fromrow = rowidx(mstr[2]);
            move->tofile = fileidx(mstr[4]);
            move->torow = rowidx(mstr[5]);
        }
    }

    
    if (move->piece) {
        if (move->piece == PAWN
            && move->torow == (gamestate->mycolor==WHITE?7:0)
            && !move->promotion) {
            return NEED_PROMOTION;
        }
        
        move->piece |= gamestate->mycolor;
        if (move->fromfile == POS_UNSPECIFIED
            || move->fromrow == POS_UNSPECIFIED) {
            return getlocation(gamestate, move);
        } else {
            return chkidx(move) ? VALID_MOVE_SYNTAX : INVALID_POSITION;
        }
    } else {
        return INVALID_MOVE_SYNTAX;
    }
}

_Bool is_protected(GameState *gamestate, uint8_t row, uint8_t file,
        uint8_t color) {
    
    Move threats[16];
    uint8_t threatcount;
    if (get_real_threats(gamestate, row, file, color, threats, &threatcount)) {
        for (int i = 0 ; i < threatcount ; i++) {
            if (threats[i].piece != (color|KING)) {
                return 1;
            }
        }
        return 0;
    } else {
        return 0;
    }
}

uint16_t remaining_movetime(GameInfo *gameinfo, GameState *gamestate,
        uint8_t color) {
    if (!gameinfo->timecontrol) {
        return 0;
    }
    
    if (gamestate->movelist) {
        uint16_t time = gameinfo->time;
        suseconds_t micros = 0;
        
        MoveList *movelist = color == WHITE ?
            gamestate->movelist : gamestate->movelist->next;
        
        while (movelist) {
            time += gameinfo->addtime;
            
            struct movetimeval *movetime = &(movelist->move.movetime);
            if (movetime->tv_sec >= time) {
                return 0;
            }
            
            time -= movetime->tv_sec;
            micros += movetime->tv_usec;
            
            movelist = movelist->next ? movelist->next->next : NULL;
        }
        
        time_t sec;
        movelist = gamestate->lastmove;
        if ((movelist->move.piece & COLOR_MASK) != color) {
            struct movetimeval *lastmovetstamp = &(movelist->move.timestamp);
            struct timeval currenttstamp;
            gettimeofday(&currenttstamp, NULL);
            micros += currenttstamp.tv_usec - lastmovetstamp->tv_usec;
            sec = currenttstamp.tv_sec - lastmovetstamp->tv_sec;
            if (sec >= time) {
                return 0;
            }
            
            time -= sec;
        }
        
        sec = micros / 1e6L;
        
        if (sec >= time) {
            return 0;
        }

        time -= sec;
        
        return time;
    } else {
        return gameinfo->time;
    }
}