terminal-chess: src/chess/rules.c@866025982aa9

     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     clock_gettime(CLOCK_REALTIME, &(elem->move.timestamp));

    52     if (gamestate->lastmove) {

    53         struct timespec *lasttstamp = &(gamestate->lastmove->move.timestamp);

    54         time_t sec = elem->move.timestamp.tv_sec - lasttstamp->tv_sec;

    55         long int nanos;

    56         if (elem->move.timestamp.tv_nsec < lasttstamp->tv_nsec) {

    57             nanos = 1e9L-(lasttstamp->tv_nsec - elem->move.timestamp.tv_nsec);

    58             sec--;

    59         } else {

    60             nanos = elem->move.timestamp.tv_nsec - lasttstamp->tv_nsec;

    61         }

    63         elem->move.movetime.tv_sec = sec;

    64         elem->move.movetime.tv_nsec = nanos;

    66         gamestate->lastmove->next = elem;

    67         gamestate->lastmove = elem;

    68     } else {

    69         elem->move.movetime.tv_nsec = 0;

    70         elem->move.movetime.tv_sec = 0;

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

    72     }

    73 }

    75 char getpiecechr(uint8_t piece) {

    76     switch (piece & PIECE_MASK) {

    77     case ROOK: return 'R';

    78     case KNIGHT: return 'N';

    79     case BISHOP: return 'B';

    80     case QUEEN: return 'Q';

    81     case KING: return 'K';

    82     default: return '\0';

    83     }

    84 }

    86 uint8_t getpiece(char c) {

    87     switch (c) {

    88         case 'R': return ROOK;

    89         case 'N': return KNIGHT;

    90         case 'B': return BISHOP;

    91         case 'Q': return QUEEN;

    92         case 'K': return KING;

    93         default: return 0;

    94     }

    95 }

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

    98     uint8_t piece = move->piece & PIECE_MASK;

    99     switch (piece) {

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

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

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

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

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

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

   106         default: return INVALID_MOVE_SYNTAX;

   107     }

   108 }

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

   111     uint8_t piece = move->piece & PIECE_MASK;

   112     uint8_t color = move->piece & COLOR_MASK;

   114     /* en passant capture */

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

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

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

   118     }

   120     /* remove old en passant threats */

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

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

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

   124     }

   126     /* add new en passant threat */

   127     if (piece == PAWN && (

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

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

   130         move->piece |= ENPASSANT_THREAT;

   131     }

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

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

   135     if (move->promotion) {

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

   137     } else {

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

   139     }

   141     /* castling */

   142     if (piece == KING &&

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

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

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

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

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

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

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

   151         }

   152     }

   154     addmove(gamestate, move);

   155 }

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

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

   159     if (!chkidx(move)) {

   160         return 0;

   161     }

   163     /* must move */

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

   165         return 0;

   166     }

   168     /* does piece exist */

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

   170         return 0;

   171     }

   173     /* can't capture own pieces */

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

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

   176         return 0;

   177     }

   179     /* validate individual rules */

   180     switch (move->piece & PIECE_MASK) {

   181     case PAWN:

   182         return pawn_chkrules(gamestate, move) &&

   183             !pawn_isblocked(gamestate, move);

   184     case ROOK:

   185         return rook_chkrules(move) &&

   186             !rook_isblocked(gamestate, move);

   187     case KNIGHT:

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

   189     case BISHOP:

   190         return bishop_chkrules(move) &&

   191             !bishop_isblocked(gamestate, move);

   192     case QUEEN:

   193         return queen_chkrules(move) &&

   194             !queen_isblocked(gamestate, move);

   195     case KING:

   196         return king_chkrules(gamestate, move) &&

   197             !king_isblocked(gamestate, move);

   198     default:

   199         return 0;

   200     }

   201 }

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

   205     _Bool result = validate_move_rules(gamestate, move);

   207     /* cancel processing to save resources */

   208     if (!result) {

   209         return 0;

   210     }

   212     /* find kings for check validation */

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

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

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

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

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

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

   220                 mykingfile = file;

   221                 mykingrow = row;

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

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

   224                 opkingfile = file;

   225                 opkingrow = row;

   226             }

   227         }

   228     }

   230     /* simulation move for check validation */

   231     GameState simulation;

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

   233     apply_move(&simulation, move);

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

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

   237         opponent_color(piececolor))) {

   238         return 0;

   239     }

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

   242     Move threats[16];

   243     uint8_t threatcount;

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

   245         piececolor, threats, &threatcount);

   247     if (move->check) {

   248         /* determine possible escape fields */

   249         _Bool canescape = 0;

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

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

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

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

   255                     /* escape field neither blocked nor covered */

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

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

   258                         canescape |= !is_covered(&simulation,

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

   260                     }

   261                 }

   262             }

   263         }

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

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

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

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

   268         }

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

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

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

   273             uint8_t threatpiece = threat->piece & PIECE_MASK;

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

   276             if (threatpiece == BISHOP || threatpiece == ROOK

   277                 || threatpiece == QUEEN) {

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

   279                     /* rook aspect (on row) */

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

   281                     uint8_t file = threat->fromfile;

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

   283                         file += d;

   284                         canescape |= is_protected(&simulation,

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

   286                     }

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

   288                     /* rook aspect (on file) */

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

   290                     uint8_t row = threat->fromrow;

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

   292                         row += d;

   293                         canescape |= is_protected(&simulation,

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

   295                     }

   296                 } else {

   297                     /* bishop aspect */

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

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

   301                     uint8_t row = move->fromrow;

   302                     uint8_t file = move->fromfile;

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

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

   305                         row += dr;

   306                         file += df;

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

   308                             opponent_color(piececolor));

   309                     }

   310                 }

   311             }

   312         }

   314         if (!canescape) {

   315             gamestate->checkmate = 1;

   316         }

   317     }

   319     return 1;

   320 }

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

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

   324     move->fromfile = POS_UNSPECIFIED;

   325     move->fromrow = POS_UNSPECIFIED;

   327     size_t len = strlen(mstr);

   329     /* evaluate check/checkmate flags */

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

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

   332         move->check = 1;

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

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

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

   336     }

   338     /* evaluate promotion */

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

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

   341         if (!move->promotion) {

   342             return INVALID_MOVE_SYNTAX;

   343         } else {

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

   345             len -= 2;

   346             mstr[len] = 0;

   347         }

   348     }

   350     if (len == 2) {

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

   352         move->piece = PAWN;

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

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

   355     } else if (len == 3) {

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

   357             /* king side castling */

   358             move->piece = KING;

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

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

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

   362         } else {

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

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

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

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

   367         }

   369     } else if (len == 4) {

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

   371         if (!move->piece) {

   372             move->piece = PAWN;

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

   374         }

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

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

   377             move->capture = 1;

   378         } else {

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

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

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

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

   383                     move->piece = 0;

   384                 }

   385             } else {

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

   387             }

   388         }

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

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

   391     } else if (len == 5) {

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

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

   394             move->piece = KING;

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

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

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

   398         } else {

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

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

   401                 move->capture = 1;

   402                 if (move->piece) {

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

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

   405                 } else {

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

   407                     move->piece = PAWN;

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

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

   410                 }

   411             } else {

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

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

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

   415             }

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

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

   418         }

   419     } else if (len == 6) {

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

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

   422             move->capture = 1;

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

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

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

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

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

   428         }

   429     }

   432     if (move->piece) {

   433         if (move->piece == PAWN

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

   435             && !move->promotion) {

   436             return NEED_PROMOTION;

   437         }

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

   440         if (move->fromfile == POS_UNSPECIFIED

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

   442             return getlocation(gamestate, move);

   443         } else {

   444             return chkidx(move) ? VALID_MOVE_SYNTAX : INVALID_POSITION;

   445         }

   446     } else {

   447         return INVALID_MOVE_SYNTAX;

   448     }

   449 }

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

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

   453     Move candidates[16];

   454     int candidatecount = 0;

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

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

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

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

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

   460                 candidates[candidatecount].fromrow = r;

   461                 candidates[candidatecount].fromfile = f;

   462                 candidates[candidatecount].torow = row;

   463                 candidates[candidatecount].tofile = file;

   464                 candidatecount++;

   465             }

   466         }

   467     }

   469     if (threatcount) {

   470         *threatcount = 0;

   471     }

   474     _Bool result = 0;

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

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

   478             result = 1;

   479             if (threats && threatcount) {

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

   481             }

   482         }

   483     }

   485     return result;

   486 }

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

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

   491     Move candidates[16];

   492     uint8_t candidatecount;

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

   495         if (threatcount) {

   496             *threatcount = 0;

   497         }

   498         _Bool result = 0;

   499         uint8_t kingfile = 0, kingrow = 0;

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

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

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

   503                     kingfile = file;

   504                     kingrow = row;

   505                 }

   506             }

   507         }

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

   510             GameState simulation;

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

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

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

   514                     opponent_color(color))) {

   515                 result = 1;

   516                 if (threats && threatcount) {

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

   518                 }

   519             }

   520         }

   522         return result;

   523     } else {

   524         return 0;

   525     }

   526 }

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

   529         uint8_t color) {

   531     Move threats[16];

   532     uint8_t threatcount;

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

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

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

   536                 return 1;

   537             }

   538         }

   539         return 0;

   540     } else {

   541         return 0;

   542     }

   543 }

   545 uint16_t remaining_movetime(GameInfo *gameinfo, GameState *gamestate,

   546         uint8_t color) {

   547     if (!gameinfo->timecontrol) {

   548         return 0;

   549     }

   551     if (gamestate->movelist) {

   552         uint16_t time = gameinfo->time;

   553         long int nanos = 0;

   555         MoveList *movelist = color == WHITE ?

   556             gamestate->movelist : gamestate->movelist->next;

   558         while (movelist) {

   559             time += gameinfo->addtime;

   561             struct timespec *movetime = &(movelist->move.movetime);

   562             if (movetime->tv_sec >= time) {

   563                 return 0;

   564             }

   566             time -= movetime->tv_sec;

   567             nanos += movetime->tv_nsec;

   569             movelist = movelist->next ? movelist->next->next : NULL;

   570         }

   572         time_t sec;

   573         movelist = gamestate->lastmove;

   574         if ((movelist->move.piece & COLOR_MASK) != color) {

   575             struct timespec *lastmovetstamp = &(movelist->move.timestamp);

   576             struct timespec currenttstamp;

   577             clock_gettime(CLOCK_REALTIME, &currenttstamp);

   578             nanos += currenttstamp.tv_nsec - lastmovetstamp->tv_nsec;

   579             sec = currenttstamp.tv_sec - lastmovetstamp->tv_sec;

   580             if (sec >= time) {

   581                 return 0;

   582             }

   584             time -= sec;

   585         }

   587         sec = nanos / 1e9L;

   589         if (sec >= time) {

   590             return 0;

   591         }

   593         time -= sec;

   595         return time;

   596     } else {

   597         return gameinfo->time;

   598     }

   599 }

Mercurial > hg > terminal-chess / file revision

src/chess/rules.c@866025982aa9

src/chess/rules.c