universe@19: /*
universe@19:  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
universe@19:  *
universe@19:  * Copyright 2014 Mike Becker. All rights reserved.
universe@19:  *
universe@19:  * Redistribution and use in source and binary forms, with or without
universe@19:  * modification, are permitted provided that the following conditions are met:
universe@19:  *
universe@19:  *   1. Redistributions of source code must retain the above copyright
universe@19:  *      notice, this list of conditions and the following disclaimer.
universe@19:  *
universe@19:  *   2. Redistributions in binary form must reproduce the above copyright
universe@19:  *      notice, this list of conditions and the following disclaimer in the
universe@19:  *      documentation and/or other materials provided with the distribution.
universe@19:  *
universe@19:  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
universe@19:  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
universe@19:  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
universe@19:  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
universe@19:  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
universe@19:  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
universe@19:  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
universe@19:  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
universe@19:  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
universe@19:  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
universe@19:  * POSSIBILITY OF SUCH DAMAGE.
universe@19:  *
universe@19:  */
universe@19: 
universe@19: #include "rules.h"
universe@19: #include "chess.h"
universe@19: #include <string.h>
universe@23: #include <stdlib.h>
universe@23: 
universe@23: void gamestate_cleanup(GameState *gamestate) {
universe@23:     MoveList *elem;
universe@23:     elem = gamestate->movelist;
universe@23:     while (elem) {
universe@23:         MoveList *cur = elem;
universe@23:         elem = elem->next;
universe@23:         free(cur);
universe@23:     };
universe@23: }
universe@23: 
universe@23: static void addmove(GameState* gamestate, Move *move) {
universe@23:     MoveList *elem = malloc(sizeof(MoveList));
universe@23:     elem->next = NULL;
universe@23:     elem->move = *move;
universe@23:     
universe@23:     if (gamestate->lastmove) {
universe@23:         gamestate->lastmove->next = elem;
universe@23:         gamestate->lastmove = elem;
universe@23:     } else {
universe@23:         gamestate->movelist = gamestate->lastmove = elem;
universe@23:     }
universe@23: }
universe@19: 
universe@19: char getpiecechr(uint8_t piece) {
universe@19:     switch (piece & PIECE_MASK) {
universe@19:     case ROOK: return 'R';
universe@19:     case KNIGHT: return 'N';
universe@19:     case BISHOP: return 'B';
universe@19:     case QUEEN: return 'Q';
universe@19:     case KING: return 'K';
universe@19:     default: return '\0';
universe@19:     }
universe@19: }
universe@19: 
universe@19: uint8_t getpiece(char c) {
universe@19:     switch (c) {
universe@19:         case 'R': return ROOK;
universe@19:         case 'N': return KNIGHT;
universe@19:         case 'B': return BISHOP;
universe@19:         case 'Q': return QUEEN;
universe@19:         case 'K': return KING;
universe@19:         default: return 0;
universe@19:     }
universe@19: }
universe@19: 
universe@23: static int getlocation(GameState *gamestate, Move *move) {   
universe@19:     uint8_t piece = move->piece & PIECE_MASK;
universe@19:     switch (piece) {
universe@23:         case PAWN: return pawn_getlocation(gamestate, move);
universe@23:         case ROOK: return rook_getlocation(gamestate, move);
universe@23:         case KNIGHT: return knight_getlocation(gamestate, move);
universe@23:         case BISHOP: return bishop_getlocation(gamestate, move);
universe@23:         case QUEEN: return queen_getlocation(gamestate, move);
universe@23:         case KING: return king_getlocation(gamestate, move);
universe@19:         default: return INVALID_MOVE_SYNTAX;
universe@19:     }
universe@19: }
universe@19: 
universe@28: _Bool get_any_threat_for(GameState *gamestate, uint8_t row, uint8_t file,
universe@28:         uint8_t color, Move *threat) {
universe@25:     Move threats[16];
universe@25:     int threatcount = 0;
universe@25:     for (uint8_t r = 0 ; r < 8 ; r++) {
universe@25:         for (uint8_t f = 0 ; f < 8 ; f++) {
universe@25:             if ((gamestate->board[r][f] & COLOR_MASK) == color) {
universe@28:                 memset(&(threats[threatcount]), 0, sizeof(Move));
universe@25:                 threats[threatcount].piece = gamestate->board[r][f];
universe@25:                 threats[threatcount].fromrow = r;
universe@25:                 threats[threatcount].fromfile = f;
universe@25:                 threats[threatcount].torow = row;
universe@25:                 threats[threatcount].tofile = file;
universe@25:                 threatcount++;
universe@25:             }
universe@25:         }
universe@25:     }
universe@25:     
universe@25:     for (int i = 0 ; i < threatcount ; i++) {
universe@25:         if (validate_move(gamestate, &(threats[i]))) {
universe@28:             if (threat) {
universe@28:                 *threat = threats[i];
universe@28:             }
universe@25:             return 1;
universe@25:         }
universe@25:     }
universe@25:     
universe@25:     return 0;
universe@25: }
universe@19: 
universe@23: void apply_move(GameState *gamestate, Move *move) {
universe@19:     uint8_t piece = move->piece & PIECE_MASK;
universe@19:     uint8_t color = move->piece & COLOR_MASK;
universe@19:     
universe@19:     /* en passant capture */
universe@19:     if (move->capture && piece == PAWN &&
universe@23:         mdst(gamestate->board, move) == 0) {
universe@23:         gamestate->board[move->fromrow][move->tofile] = 0;
universe@19:     }
universe@19:     
universe@19:     /* remove old en passant threats */
universe@19:     for (uint8_t file = 0 ; file < 8 ; file++) {
universe@23:         gamestate->board[3][file] &= ~ENPASSANT_THREAT;
universe@23:         gamestate->board[4][file] &= ~ENPASSANT_THREAT;
universe@19:     }
universe@19:     
universe@19:     /* add new en passant threat */
universe@19:     if (piece == PAWN && (
universe@19:         (move->fromrow == 1 && move->torow == 3) ||
universe@19:         (move->fromrow == 6 && move->torow == 4))) {
universe@19:         move->piece |= ENPASSANT_THREAT;
universe@19:     }
universe@19:     
universe@19:     /* move (and maybe capture or promote) */
universe@23:     msrc(gamestate->board, move) = 0;
universe@19:     if (move->promotion) {
universe@23:         mdst(gamestate->board, move) = move->promotion;
universe@19:     } else {
universe@23:         mdst(gamestate->board, move) = move->piece;
universe@19:     }
universe@19:     
universe@19:     /* castling */
universe@19:     if (piece == KING &&
universe@19:         move->fromfile == fileidx('e')) {
universe@19:         
universe@19:         if (move->tofile == fileidx('g')) {
universe@23:             gamestate->board[move->torow][fileidx('h')] = 0;
universe@23:             gamestate->board[move->torow][fileidx('f')] = color|ROOK;
universe@19:         } else if (move->tofile == fileidx('c')) {
universe@23:             gamestate->board[move->torow][fileidx('a')] = 0;
universe@23:             gamestate->board[move->torow][fileidx('d')] = color|ROOK;
universe@19:         }
universe@19:     }
universe@28: 
universe@23:     addmove(gamestate, move);
universe@19: }
universe@19: 
universe@23: _Bool validate_move(GameState *gamestate, Move *move) {
universe@19:     _Bool result;
universe@19:     
universe@19:     /* validate indices (don't trust opponent) */
universe@19:     if (!chkidx(move)) {
universe@19:         return 0;
universe@19:     }
universe@19:     
universe@21:     /* must move */
universe@21:     if (move->fromfile == move->tofile && move->fromrow == move->torow) {
universe@21:         return 0;
universe@21:     }
universe@21:     
universe@19:     /* does piece exist */
universe@23:     result = msrc(gamestate->board, move) == move->piece;
universe@19:     
universe@19:     /* can't capture own pieces */
universe@28:     uint8_t piececolor = (move->piece & COLOR_MASK);
universe@28:     if ((mdst(gamestate->board, move) & COLOR_MASK) == piececolor) {
universe@19:         return 0;
universe@19:     }
universe@19:     
universe@19:     /* validate individual rules */
universe@19:     switch (move->piece & PIECE_MASK) {
universe@19:     case PAWN:
universe@23:         result = result && pawn_chkrules(gamestate, move);
universe@23:         result = result && !pawn_isblocked(gamestate, move);
universe@19:         break;
universe@19:     case ROOK:
universe@19:         result = result && rook_chkrules(move);
universe@23:         result = result && !rook_isblocked(gamestate, move);
universe@19:         break;
universe@19:     case KNIGHT:
universe@19:         result = result && knight_chkrules(move);
universe@23:         result = result && !knight_isblocked(gamestate, move);
universe@19:         break;
universe@19:     case BISHOP:
universe@19:         result = result && bishop_chkrules(move);
universe@23:         result = result && !bishop_isblocked(gamestate, move);
universe@19:         break;
universe@19:     case QUEEN:
universe@19:         result = result && queen_chkrules(move);
universe@23:         result = result && !queen_isblocked(gamestate, move);
universe@19:         break;
universe@19:     case KING:
universe@23:         result = result && king_chkrules(gamestate, move);
universe@23:         result = result && !king_isblocked(gamestate, move);
universe@19:         break;
universe@19:     default:
universe@19:         result = 0;
universe@19:     }
universe@19:     
universe@25:     /* cancel processing to avoid recursion overflow with is_covered() */
universe@25:     if (!result) {
universe@25:         return 0;
universe@25:     }
universe@25:     
universe@28:     /* find kings for check validation */
universe@28:     uint8_t mykingfile = 0, mykingrow = 0, opkingfile = 0, opkingrow = 0;
universe@28:     for (uint8_t row = 0 ; row < 8 ; row++) {
universe@28:         for (uint8_t file = 0 ; file < 8 ; file++) {
universe@28:             if (gamestate->board[row][file] ==
universe@28:                     (piececolor == WHITE?WKING:BKING)) {
universe@28:                 mykingfile = file;
universe@28:                 mykingrow = row;
universe@28:             } else if (gamestate->board[row][file] ==
universe@28:                     (piececolor == WHITE?BKING:WKING)) {
universe@28:                 opkingfile = file;
universe@28:                 opkingrow = row;
universe@28:             }
universe@28:         }
universe@28:     }
universe@28:     
universe@28:     /* simulation move for check validation */
universe@28:     GameState simulation;
universe@28:     memcpy(&simulation, gamestate, sizeof(GameState));
universe@28:     apply_move(&simulation, move);
universe@28:     
universe@28:     /* don't move into or stay in check position */
universe@28:     if (is_covered(&simulation, mykingrow, mykingfile,
universe@28:         opponent_color(piececolor))) {
universe@28:         return 0;
universe@28:     }
universe@19:     
universe@25:     /* correct check and checkmate flags (move is still valid) */
universe@28:     Move threat;
universe@28:     move->check = get_any_threat_for(&simulation, opkingrow, opkingfile,
universe@28:         piececolor, &threat);
universe@19:     
universe@28:     if (move->check) {
universe@28:         /* determine possible escape fields */
universe@28:         _Bool canescape = 0;
universe@28:         for (int dr = -1 ; dr <= 1 && !canescape ; dr++) {
universe@28:             for (int df = -1 ; df <= 1 && !canescape ; df++) {
universe@28:                 if (!(dr == 0 && df == 0)  &&
universe@28:                         isidx(opkingrow + dr) && isidx(opkingfile + df)) {
universe@28:                     
universe@28:                     /* escape field neither blocked nor covered */
universe@28:                     if ((simulation.board[opkingrow + dr][opkingfile + df]
universe@28:                             & COLOR_MASK) != opponent_color(piececolor)) {
universe@28:                         canescape |= !is_covered(&simulation,
universe@28:                             opkingrow + dr, opkingfile + df, piececolor);
universe@28:                     }
universe@28:                 }
universe@28:             }
universe@28:         }
universe@28:         /* can't escape, can we capture? */
universe@28:         if (!canescape) {
universe@28:             canescape = is_covered(&simulation, threat.fromrow,
universe@28:                 threat.fromfile, opponent_color(piececolor));
universe@28: 
universe@28:             /* can't capture, can we block? */
universe@28:             // TODO: make it so
universe@28:             
universe@28:             if (!canescape) {
universe@28:                 gamestate->checkmate = 1;
universe@28:             }
universe@28:         }
universe@28:     }
universe@28:     
universe@28:     return 1;
universe@19: }
universe@19: 
universe@23: int eval_move(GameState *gamestate, char *mstr, Move *move) {
universe@19:     memset(move, 0, sizeof(Move));
universe@19:     move->fromfile = POS_UNSPECIFIED;
universe@19:     move->fromrow = POS_UNSPECIFIED;
universe@19: 
universe@19:     size_t len = strlen(mstr);
universe@19:     
universe@19:     /* evaluate check/checkmate flags */
universe@19:     if (mstr[len-1] == '+') {
universe@19:         len--; mstr[len] = '\0';
universe@19:         move->check = 1;
universe@19:     } else if (mstr[len-1] == '#') {
universe@19:         len--; mstr[len] = '\0';
universe@27:         /* ignore - validation should set game state */
universe@19:     }
universe@19:     
universe@19:     /* evaluate promotion */
universe@19:     if (len > 3 && mstr[len-2] == '=') {
universe@19:         move->promotion = getpiece(mstr[len-1]);
universe@19:         if (!move->promotion) {
universe@19:             return INVALID_MOVE_SYNTAX;
universe@19:         } else {
universe@23:             move->promotion |= gamestate->mycolor;
universe@19:             len -= 2;
universe@19:             mstr[len] = 0;
universe@19:         }
universe@19:     }
universe@19:     
universe@19:     if (len == 2) {
universe@19:         /* pawn move (e.g. "e4") */
universe@19:         move->piece = PAWN;
universe@19:         move->tofile = fileidx(mstr[0]);
universe@19:         move->torow = rowidx(mstr[1]);
universe@19:     } else if (len == 3) {
universe@19:         if (strcmp(mstr, "O-O") == 0) {
universe@19:             /* king side castling */
universe@19:             move->piece = KING;
universe@19:             move->fromfile = fileidx('e');
universe@19:             move->tofile = fileidx('g');
universe@23:             move->fromrow = move->torow = gamestate->mycolor == WHITE ? 0 : 7;
universe@19:         } else {
universe@19:             /* move (e.g. "Nf3") */
universe@19:             move->piece = getpiece(mstr[0]);
universe@19:             move->tofile = fileidx(mstr[1]);
universe@19:             move->torow = rowidx(mstr[2]);
universe@19:         }
universe@19:         
universe@19:     } else if (len == 4) {
universe@19:         move->piece = getpiece(mstr[0]);
universe@19:         if (!move->piece) {
universe@19:             move->piece = PAWN;
universe@19:             move->fromfile = fileidx(mstr[0]);
universe@19:         }
universe@19:         if (mstr[1] == 'x') {
universe@19:             /* capture (e.g. "Nxf3", "dxe5") */
universe@19:             move->capture = 1;
universe@19:         } else {
universe@19:             /* move (e.g. "Ndf3", "N2c3", "e2e4") */
universe@19:             if (isfile(mstr[1])) {
universe@19:                 move->fromfile = fileidx(mstr[1]);
universe@19:                 if (move->piece == PAWN) {
universe@19:                     move->piece = 0;
universe@19:                 }
universe@19:             } else {
universe@19:                 move->fromrow = rowidx(mstr[1]);
universe@19:             }
universe@19:         }
universe@19:         move->tofile = fileidx(mstr[2]);
universe@19:         move->torow = rowidx(mstr[3]);
universe@19:     } else if (len == 5) {
universe@19:         if (strcmp(mstr, "O-O-O") == 0) {
universe@19:             /* queen side castling "O-O-O" */
universe@19:             move->piece = KING;
universe@19:             move->fromfile = fileidx('e');
universe@19:             move->tofile = fileidx('c');
universe@23:             move->fromrow = move->torow = gamestate->mycolor == WHITE ? 0 : 7;
universe@19:         } else {
universe@19:             move->piece = getpiece(mstr[0]);
universe@19:             if (mstr[2] == 'x') {
universe@19:                 move->capture = 1;
universe@19:                 if (move->piece) {
universe@19:                     /* capture (e.g. "Ndxf3") */
universe@19:                     move->fromfile = fileidx(mstr[1]);
universe@19:                 } else {
universe@19:                     /* long notation capture (e.g. "e5xf6") */
universe@19:                     move->piece = PAWN;
universe@19:                     move->fromfile = fileidx(mstr[0]);
universe@19:                     move->fromrow = rowidx(mstr[1]);
universe@19:                 }
universe@19:             } else {
universe@19:                 /* long notation move (e.g. "Nc5a4") */
universe@19:                 move->fromfile = fileidx(mstr[1]);
universe@19:                 move->fromrow = rowidx(mstr[2]);
universe@19:             }
universe@19:             move->tofile = fileidx(mstr[3]);
universe@19:             move->torow = rowidx(mstr[4]);
universe@19:         }
universe@19:     } else if (len == 6) {
universe@19:         /* long notation capture (e.g. "Nc5xf3") */
universe@19:         if (mstr[3] == 'x') {
universe@19:             move->capture = 1;
universe@19:             move->piece = getpiece(mstr[0]);
universe@19:             move->fromfile = fileidx(mstr[1]);
universe@19:             move->fromrow = rowidx(mstr[2]);
universe@19:             move->tofile = fileidx(mstr[4]);
universe@19:             move->torow = rowidx(mstr[5]);
universe@19:         }
universe@19:     }
universe@19: 
universe@19:     
universe@19:     if (move->piece) {
universe@23:         if (move->piece == PAWN
universe@23:             && move->torow == (gamestate->mycolor==WHITE?7:0)
universe@19:             && !move->promotion) {
universe@19:             return NEED_PROMOTION;
universe@19:         }
universe@19:         
universe@23:         move->piece |= gamestate->mycolor;
universe@19:         if (move->fromfile == POS_UNSPECIFIED
universe@19:             || move->fromrow == POS_UNSPECIFIED) {
universe@23:             return getlocation(gamestate, move);
universe@19:         } else {
universe@19:             return chkidx(move) ? VALID_MOVE_SYNTAX : INVALID_POSITION;
universe@19:         }
universe@19:     } else {
universe@19:         return INVALID_MOVE_SYNTAX;
universe@19:     }
universe@19: }