terminal-chess: src/chess/rules.c@c6a1ad6cf749

     1 /*

     2  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.

     3  *

     4  * Copyright 2014 Mike Becker. All rights reserved.

     5  *

     6  * Redistribution and use in source and binary forms, with or without

     7  * modification, are permitted provided that the following conditions are met:

     8  *

     9  *   1. Redistributions of source code must retain the above copyright

    10  *      notice, this list of conditions and the following disclaimer.

    11  *

    12  *   2. Redistributions in binary form must reproduce the above copyright

    13  *      notice, this list of conditions and the following disclaimer in the

    14  *      documentation and/or other materials provided with the distribution.

    15  *

    16  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"

    17  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE

    18  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE

    19  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE

    20  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR

    21  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF

    22  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS

    23  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN

    24  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)

    25  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE

    26  * POSSIBILITY OF SUCH DAMAGE.

    27  *

    28  */

    30 #include "rules.h"

    31 #include "chess.h"

    32 #include <string.h>

    33 #include <stdlib.h>

    35 void gamestate_cleanup(GameState *gamestate) {

    36     MoveList *elem;

    37     elem = gamestate->movelist;

    38     while (elem) {

    39         MoveList *cur = elem;

    40         elem = elem->next;

    41         free(cur);

    42     };

    43 }

    45 static void addmove(GameState* gamestate, Move *move) {

    46     MoveList *elem = malloc(sizeof(MoveList));

    47     elem->next = NULL;

    48     elem->move = *move;

    50     if (gamestate->lastmove) {

    51         gamestate->lastmove->next = elem;

    52         gamestate->lastmove = elem;

    53     } else {

    54         gamestate->movelist = gamestate->lastmove = elem;

    55     }

    56 }

    58 char getpiecechr(uint8_t piece) {

    59     switch (piece & PIECE_MASK) {

    60     case ROOK: return 'R';

    61     case KNIGHT: return 'N';

    62     case BISHOP: return 'B';

    63     case QUEEN: return 'Q';

    64     case KING: return 'K';

    65     default: return '\0';

    66     }

    67 }

    69 uint8_t getpiece(char c) {

    70     switch (c) {

    71         case 'R': return ROOK;

    72         case 'N': return KNIGHT;

    73         case 'B': return BISHOP;

    74         case 'Q': return QUEEN;

    75         case 'K': return KING;

    76         default: return 0;

    77     }

    78 }

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

    81     uint8_t piece = move->piece & PIECE_MASK;

    82     switch (piece) {

    83         case PAWN: return pawn_getlocation(gamestate, move);

    84         case ROOK: return rook_getlocation(gamestate, move);

    85         case KNIGHT: return knight_getlocation(gamestate, move);

    86         case BISHOP: return bishop_getlocation(gamestate, move);

    87         case QUEEN: return queen_getlocation(gamestate, move);

    88         case KING: return king_getlocation(gamestate, move);

    89         default: return INVALID_MOVE_SYNTAX;

    90     }

    91 }

    93 void apply_move(GameState *gamestate, Move *move) {

    94     uint8_t piece = move->piece & PIECE_MASK;

    95     uint8_t color = move->piece & COLOR_MASK;

    97     /* en passant capture */

    98     if (move->capture && piece == PAWN &&

    99         mdst(gamestate->board, move) == 0) {

   100         gamestate->board[move->fromrow][move->tofile] = 0;

   101     }

   103     /* remove old en passant threats */

   104     for (uint8_t file = 0 ; file < 8 ; file++) {

   105         gamestate->board[3][file] &= ~ENPASSANT_THREAT;

   106         gamestate->board[4][file] &= ~ENPASSANT_THREAT;

   107     }

   109     /* add new en passant threat */

   110     if (piece == PAWN && (

   111         (move->fromrow == 1 && move->torow == 3) ||

   112         (move->fromrow == 6 && move->torow == 4))) {

   113         move->piece |= ENPASSANT_THREAT;

   114     }

   116     /* move (and maybe capture or promote) */

   117     msrc(gamestate->board, move) = 0;

   118     if (move->promotion) {

   119         mdst(gamestate->board, move) = move->promotion;

   120     } else {

   121         mdst(gamestate->board, move) = move->piece;

   122     }

   124     /* castling */

   125     if (piece == KING &&

   126         move->fromfile == fileidx('e')) {

   128         if (move->tofile == fileidx('g')) {

   129             gamestate->board[move->torow][fileidx('h')] = 0;

   130             gamestate->board[move->torow][fileidx('f')] = color|ROOK;

   131         } else if (move->tofile == fileidx('c')) {

   132             gamestate->board[move->torow][fileidx('a')] = 0;

   133             gamestate->board[move->torow][fileidx('d')] = color|ROOK;

   134         }

   135     }

   137     addmove(gamestate, move);

   138 }

   140 static _Bool validate_move_rules(GameState *gamestate, Move *move) {

   141     /* validate indices (don't trust opponent) */

   142     if (!chkidx(move)) {

   143         return 0;

   144     }

   146     /* must move */

   147     if (move->fromfile == move->tofile && move->fromrow == move->torow) {

   148         return 0;

   149     }

   151     /* does piece exist */

   152     if (msrc(gamestate->board, move) != move->piece) {

   153         return 0;

   154     }

   156     /* can't capture own pieces */

   157     if ((mdst(gamestate->board, move) & COLOR_MASK)

   158         == (move->piece & COLOR_MASK)) {

   159         return 0;

   160     }

   162     /* validate individual rules */

   163     switch (move->piece & PIECE_MASK) {

   164     case PAWN:

   165         return pawn_chkrules(gamestate, move) &&

   166             !pawn_isblocked(gamestate, move);

   167     case ROOK:

   168         return rook_chkrules(move) &&

   169             !rook_isblocked(gamestate, move);

   170     case KNIGHT:

   171         return knight_chkrules(move); /* knight is never blocked */

   172     case BISHOP:

   173         return bishop_chkrules(move) &&

   174             !bishop_isblocked(gamestate, move);

   175     case QUEEN:

   176         return queen_chkrules(move) &&

   177             !queen_isblocked(gamestate, move);

   178     case KING:

   179         return king_chkrules(gamestate, move) &&

   180             !king_isblocked(gamestate, move);

   181     default:

   182         return 0;

   183     }

   184 }

   186 _Bool validate_move(GameState *gamestate, Move *move) {

   188     _Bool result = validate_move_rules(gamestate, move);

   190     /* cancel processing to save resources */

   191     if (!result) {

   192         return 0;

   193     }

   195     /* find kings for check validation */

   196     uint8_t piececolor = (move->piece & COLOR_MASK);

   198     uint8_t mykingfile = 0, mykingrow = 0, opkingfile = 0, opkingrow = 0;

   199     for (uint8_t row = 0 ; row < 8 ; row++) {

   200         for (uint8_t file = 0 ; file < 8 ; file++) {

   201             if (gamestate->board[row][file] ==

   202                     (piececolor == WHITE?WKING:BKING)) {

   203                 mykingfile = file;

   204                 mykingrow = row;

   205             } else if (gamestate->board[row][file] ==

   206                     (piececolor == WHITE?BKING:WKING)) {

   207                 opkingfile = file;

   208                 opkingrow = row;

   209             }

   210         }

   211     }

   213     /* simulation move for check validation */

   214     GameState simulation;

   215     memcpy(&simulation, gamestate, sizeof(GameState));

   216     apply_move(&simulation, move);

   218     /* don't move into or stay in check position */

   219     if (is_covered(&simulation, mykingrow, mykingfile,

   220         opponent_color(piececolor))) {

   221         return 0;

   222     }

   224     /* correct check and checkmate flags (move is still valid) */

   225     Move threats[16];

   226     uint8_t threatcount;

   227     move->check = get_threats(&simulation, opkingrow, opkingfile,

   228         piececolor, threats, &threatcount);

   230     if (move->check) {

   231         /* determine possible escape fields */

   232         _Bool canescape = 0;

   233         for (int dr = -1 ; dr <= 1 && !canescape ; dr++) {

   234             for (int df = -1 ; df <= 1 && !canescape ; df++) {

   235                 if (!(dr == 0 && df == 0)  &&

   236                         isidx(opkingrow + dr) && isidx(opkingfile + df)) {

   238                     /* escape field neither blocked nor covered */

   239                     if ((simulation.board[opkingrow + dr][opkingfile + df]

   240                             & COLOR_MASK) != opponent_color(piececolor)) {

   241                         canescape |= !is_covered(&simulation,

   242                             opkingrow + dr, opkingfile + df, piececolor);

   243                     }

   244                 }

   245             }

   246         }

   247         /* can't escape, can he capture? */

   248         if (!canescape && threatcount == 1) {

   249             canescape = is_attacked(&simulation, threats[0].fromrow,

   250                 threats[0].fromfile, opponent_color(piececolor));

   251         }

   253         /* can't capture, can he block? */

   254         if (!canescape && threatcount == 1) {

   255             Move *threat = &(threats[0]);

   256             uint8_t threatpiece = threat->piece & PIECE_MASK;

   258             /* knight, pawns and the king cannot be blocked */

   259             if (threatpiece == BISHOP || threatpiece == ROOK

   260                 || threatpiece == QUEEN) {

   261                 if (threat->fromrow == threat->torow) {

   262                     /* rook aspect (on row) */

   263                     int d = threat->tofile > threat->fromfile ? 1 : -1;

   264                     uint8_t file = threat->fromfile;

   265                     while (!canescape && file != threat->tofile - d) {

   266                         file += d;

   267                         canescape |= is_protected(&simulation,

   268                             threat->torow, file, opponent_color(piececolor));

   269                     }

   270                 } else if (threat->fromfile == threat->tofile) {

   271                     /* rook aspect (on file) */

   272                     int d = threat->torow > threat->fromrow ? 1 : -1;

   273                     uint8_t row = threat->fromrow;

   274                     while (!canescape && row != threat->torow - d) {

   275                         row += d;

   276                         canescape |= is_protected(&simulation,

   277                             row, threat->tofile, opponent_color(piececolor));

   278                     }

   279                 } else {

   280                     /* bishop aspect */

   281                     int dr = move->torow > move->fromrow ? 1 : -1;

   282                     int df = move->tofile > move->fromfile ? 1 : -1;

   284                     uint8_t row = move->fromrow;

   285                     uint8_t file = move->fromfile;

   286                     while (!canescape && file != move->tofile - df

   287                         && row != move->torow - dr) {

   288                         row += dr;

   289                         file += df;

   290                         canescape |= is_protected(&simulation, row, file,

   291                             opponent_color(piececolor));

   292                     }

   293                 }

   294             }

   295         }

   297         if (!canescape) {

   298             gamestate->checkmate = 1;

   299         }

   300     }

   302     return 1;

   303 }

   305 int eval_move(GameState *gamestate, char *mstr, Move *move) {

   306     memset(move, 0, sizeof(Move));

   307     move->fromfile = POS_UNSPECIFIED;

   308     move->fromrow = POS_UNSPECIFIED;

   310     size_t len = strlen(mstr);

   312     /* evaluate check/checkmate flags */

   313     if (mstr[len-1] == '+') {

   314         len--; mstr[len] = '\0';

   315         move->check = 1;

   316     } else if (mstr[len-1] == '#') {

   317         len--; mstr[len] = '\0';

   318         /* ignore - validation should set game state */

   319     }

   321     /* evaluate promotion */

   322     if (len > 3 && mstr[len-2] == '=') {

   323         move->promotion = getpiece(mstr[len-1]);

   324         if (!move->promotion) {

   325             return INVALID_MOVE_SYNTAX;

   326         } else {

   327             move->promotion |= gamestate->mycolor;

   328             len -= 2;

   329             mstr[len] = 0;

   330         }

   331     }

   333     if (len == 2) {

   334         /* pawn move (e.g. "e4") */

   335         move->piece = PAWN;

   336         move->tofile = fileidx(mstr[0]);

   337         move->torow = rowidx(mstr[1]);

   338     } else if (len == 3) {

   339         if (strcmp(mstr, "O-O") == 0) {

   340             /* king side castling */

   341             move->piece = KING;

   342             move->fromfile = fileidx('e');

   343             move->tofile = fileidx('g');

   344             move->fromrow = move->torow = gamestate->mycolor == WHITE ? 0 : 7;

   345         } else {

   346             /* move (e.g. "Nf3") */

   347             move->piece = getpiece(mstr[0]);

   348             move->tofile = fileidx(mstr[1]);

   349             move->torow = rowidx(mstr[2]);

   350         }

   352     } else if (len == 4) {

   353         move->piece = getpiece(mstr[0]);

   354         if (!move->piece) {

   355             move->piece = PAWN;

   356             move->fromfile = fileidx(mstr[0]);

   357         }

   358         if (mstr[1] == 'x') {

   359             /* capture (e.g. "Nxf3", "dxe5") */

   360             move->capture = 1;

   361         } else {

   362             /* move (e.g. "Ndf3", "N2c3", "e2e4") */

   363             if (isfile(mstr[1])) {

   364                 move->fromfile = fileidx(mstr[1]);

   365                 if (move->piece == PAWN) {

   366                     move->piece = 0;

   367                 }

   368             } else {

   369                 move->fromrow = rowidx(mstr[1]);

   370             }

   371         }

   372         move->tofile = fileidx(mstr[2]);

   373         move->torow = rowidx(mstr[3]);

   374     } else if (len == 5) {

   375         if (strcmp(mstr, "O-O-O") == 0) {

   376             /* queen side castling "O-O-O" */

   377             move->piece = KING;

   378             move->fromfile = fileidx('e');

   379             move->tofile = fileidx('c');

   380             move->fromrow = move->torow = gamestate->mycolor == WHITE ? 0 : 7;

   381         } else {

   382             move->piece = getpiece(mstr[0]);

   383             if (mstr[2] == 'x') {

   384                 move->capture = 1;

   385                 if (move->piece) {

   386                     /* capture (e.g. "Ndxf3") */

   387                     move->fromfile = fileidx(mstr[1]);

   388                 } else {

   389                     /* long notation capture (e.g. "e5xf6") */

   390                     move->piece = PAWN;

   391                     move->fromfile = fileidx(mstr[0]);

   392                     move->fromrow = rowidx(mstr[1]);

   393                 }

   394             } else {

   395                 /* long notation move (e.g. "Nc5a4") */

   396                 move->fromfile = fileidx(mstr[1]);

   397                 move->fromrow = rowidx(mstr[2]);

   398             }

   399             move->tofile = fileidx(mstr[3]);

   400             move->torow = rowidx(mstr[4]);

   401         }

   402     } else if (len == 6) {

   403         /* long notation capture (e.g. "Nc5xf3") */

   404         if (mstr[3] == 'x') {

   405             move->capture = 1;

   406             move->piece = getpiece(mstr[0]);

   407             move->fromfile = fileidx(mstr[1]);

   408             move->fromrow = rowidx(mstr[2]);

   409             move->tofile = fileidx(mstr[4]);

   410             move->torow = rowidx(mstr[5]);

   411         }

   412     }

   415     if (move->piece) {

   416         if (move->piece == PAWN

   417             && move->torow == (gamestate->mycolor==WHITE?7:0)

   418             && !move->promotion) {

   419             return NEED_PROMOTION;

   420         }

   422         move->piece |= gamestate->mycolor;

   423         if (move->fromfile == POS_UNSPECIFIED

   424             || move->fromrow == POS_UNSPECIFIED) {

   425             return getlocation(gamestate, move);

   426         } else {

   427             return chkidx(move) ? VALID_MOVE_SYNTAX : INVALID_POSITION;

   428         }

   429     } else {

   430         return INVALID_MOVE_SYNTAX;

   431     }

   432 }

   434 _Bool get_threats(GameState *gamestate, uint8_t row, uint8_t file,

   435         uint8_t color, Move *threats, uint8_t *threatcount) {

   436     Move candidates[16];

   437     int candidatecount = 0;

   438     for (uint8_t r = 0 ; r < 8 ; r++) {

   439         for (uint8_t f = 0 ; f < 8 ; f++) {

   440             if ((gamestate->board[r][f] & COLOR_MASK) == color) {

   441                 memset(&(candidates[candidatecount]), 0, sizeof(Move));

   442                 candidates[candidatecount].piece = gamestate->board[r][f];

   443                 candidates[candidatecount].fromrow = r;

   444                 candidates[candidatecount].fromfile = f;

   445                 candidates[candidatecount].torow = row;

   446                 candidates[candidatecount].tofile = file;

   447                 candidatecount++;

   448             }

   449         }

   450     }

   452     if (threatcount) {

   453         *threatcount = 0;

   454     }

   457     _Bool result = 0;

   459     for (int i = 0 ; i < candidatecount ; i++) {

   460         if (validate_move_rules(gamestate, &(candidates[i]))) {

   461             result = 1;

   462             if (threats && threatcount) {

   463                 threats[(*threatcount)++] = candidates[i];

   464             }

   465         }

   466     }

   468     return result;

   469 }

   471 _Bool get_real_threats(GameState *gamestate, uint8_t row, uint8_t file,

   472         uint8_t color, Move *threats, uint8_t *threatcount) {

   474     Move candidates[16];

   475     uint8_t candidatecount;

   476     if (get_threats(gamestate, row, file, color, candidates, &candidatecount)) {

   478         if (threatcount) {

   479             *threatcount = 0;

   480         }

   481         _Bool result = 0;

   482         uint8_t kingfile = 0, kingrow = 0;

   483         for (uint8_t row = 0 ; row < 8 ; row++) {

   484             for (uint8_t file = 0 ; file < 8 ; file++) {

   485                 if ((gamestate->board[row][file] & COLOR_MASK) == color) {

   486                     kingfile = file;

   487                     kingrow = row;

   488                 }

   489             }

   490         }

   492         for (uint8_t i = 0 ; i < candidatecount ; i++) {

   493             GameState simulation;

   494             memcpy(&simulation, gamestate, sizeof(GameState));

   495             apply_move(&simulation, &(candidates[i]));

   496             if (!is_covered(&simulation, kingrow, kingfile,

   497                     opponent_color(color))) {

   498                 result = 1;

   499                 if (threats && threatcount) {

   500                     threats[(*threatcount)++] = candidates[i];

   501                 }

   502             }

   503         }

   505         return result;

   506     } else {

   507         return 0;

   508     }

   509 }

   511 _Bool is_protected(GameState *gamestate, uint8_t row, uint8_t file,

   512         uint8_t color) {

   514     Move threats[16];

   515     uint8_t threatcount;

   516     if (get_real_threats(gamestate, row, file, color, threats, &threatcount)) {

   517         for (int i = 0 ; i < threatcount ; i++) {

   518             if (threats[i].piece != (color|KING)) {

   519                 return 1;

   520             }

   521         }

   522         return 0;

   523     } else {

   524         return 0;

   525     }

   526 }

Mercurial > hg > terminal-chess / file revision

src/chess/rules.c@c6a1ad6cf749

src/chess/rules.c