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>

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;
    
    if (gamestate->lastmove) {
        gamestate->lastmove->next = elem;
        gamestate->lastmove = elem;
    } else {
        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;
    }
}

static int getlocation(GameState *gamestate, Move *move) {   
    uint8_t piece = move->piece & PIECE_MASK;
    switch (piece) {
        case PAWN: return pawn_getlocation(gamestate, move);
        case ROOK: return rook_getlocation(gamestate, move);
        case KNIGHT: return knight_getlocation(gamestate, move);
        case BISHOP: return bishop_getlocation(gamestate, move);
        case QUEEN: return queen_getlocation(gamestate, move);
        case KING: return king_getlocation(gamestate, move);
        default: return INVALID_MOVE_SYNTAX;
    }
}

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

_Bool validate_move(GameState *gamestate, Move *move) {
    
    _Bool result = validate_move_rules(gamestate, move);
    
    /* cancel processing to save resources */
    if (!result) {
        return 0;
    }
    
    /* 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;
            }
        }
    }
    
    /* simulation move for check validation */
    GameState simulation;
    memcpy(&simulation, gamestate, sizeof(GameState));
    apply_move(&simulation, move);
    
    /* don't move into or stay in check position */
    if (is_covered(&simulation, mykingrow, mykingfile,
        opponent_color(piececolor))) {
        return 0;
    }
    
    /* 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;
        }
    }
    
    return 1;
}

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);
    
    /* 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 get_threats(GameState *gamestate, uint8_t row, uint8_t file,
        uint8_t color, Move *threats, uint8_t *threatcount) {
    Move candidates[16];
    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) {
                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++;
            }
        }
    }

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

_Bool get_real_threats(GameState *gamestate, uint8_t row, uint8_t file,
        uint8_t color, Move *threats, uint8_t *threatcount) {

    Move candidates[16];
    uint8_t candidatecount;
    if (get_threats(gamestate, row, file, color, candidates, &candidatecount)) {
        
        if (threatcount) {
            *threatcount = 0;
        }
        _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_MASK) == color) {
                    kingfile = file;
                    kingrow = row;
                }
            }
        }
        
        for (uint8_t i = 0 ; i < candidatecount ; i++) {
            GameState simulation;
            memcpy(&simulation, gamestate, sizeof(GameState));
            apply_move(&simulation, &(candidates[i]));
            if (!is_covered(&simulation, kingrow, kingfile,
                    opponent_color(color))) {
                result = 1;
                if (threats && threatcount) {
                    threats[(*threatcount)++] = candidates[i];
                }
            }
        }
        
        return result;
    } else {
        return 0;
    }
}

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