c2html

universe@41: universe@41: universe@41: universe@41: c2html universe@41: universe@41: universe@41: universe@41: universe@41:
universe@41:   1  /*
universe@41:   2   * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
universe@41:   3   *
universe@41:   4   * Copyright 2014 Mike Becker. All rights reserved.
universe@41:   5   *
universe@41:   6   * Redistribution and use in source and binary forms, with or without
universe@41:   7   * modification, are permitted provided that the following conditions are met:
universe@41:   8   *
universe@41:   9   *   1. Redistributions of source code must retain the above copyright
universe@41:  10   *      notice, this list of conditions and the following disclaimer.
universe@41:  11   *
universe@41:  12   *   2. Redistributions in binary form must reproduce the above copyright
universe@41:  13   *      notice, this list of conditions and the following disclaimer in the
universe@41:  14   *      documentation and/or other materials provided with the distribution.
universe@41:  15   *
universe@41:  16   * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
universe@41:  17   * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
universe@41:  18   * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
universe@41:  19   * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
universe@41:  20   * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
universe@41:  21   * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
universe@41:  22   * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
universe@41:  23   * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
universe@41:  24   * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
universe@41:  25   * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
universe@41:  26   * POSSIBILITY OF SUCH DAMAGE.
universe@41:  27   *
universe@41:  28   */
universe@41:  29  
universe@41:  30  #include "rules.h"
universe@41:  31  #include "chess.h"
universe@41:  32  #include <string.h>
universe@41:  33  #include <stdlib.h>
universe@41:  34  #include <sys/time.h>
universe@41:  35  
universe@41:  36  static GameState gamestate_copy_sim(GameState *gamestate) {
universe@41:  37      GameState simulation = *gamestate;
universe@41:  38      if (simulation.lastmove) {
universe@41:  39          MoveList *lastmovecopy = malloc(sizeof(MoveList));
universe@41:  40          *lastmovecopy = *(simulation.lastmove);
universe@41:  41          simulation.movelist = simulation.lastmove = lastmovecopy;
universe@41:  42      }
universe@41:  43  
universe@41:  44      return simulation;
universe@41:  45  }
universe@41:  46  
universe@41:  47  void gamestate_init(GameState *gamestate) {
universe@41:  48      memset(gamestate, 0, sizeof(GameState));
universe@41:  49      
universe@41:  50      Board initboard = {
universe@41:  51          {WROOK, WKNIGHT, WBISHOP, WQUEEN, WKING, WBISHOP, WKNIGHT, WROOK},
universe@41:  52          {WPAWN, WPAWN,   WPAWN,   WPAWN,  WPAWN, WPAWN,   WPAWN,   WPAWN},
universe@41:  53          {0,     0,       0,       0,      0,     0,       0,       0},
universe@41:  54          {0,     0,       0,       0,      0,     0,       0,       0},
universe@41:  55          {0,     0,       0,       0,      0,     0,       0,       0},
universe@41:  56          {0,     0,       0,       0,      0,     0,       0,       0},
universe@41:  57          {BPAWN, BPAWN,   BPAWN,   BPAWN,  BPAWN, BPAWN,   BPAWN,   BPAWN},
universe@41:  58          {BROOK, BKNIGHT, BBISHOP, BQUEEN, BKING, BBISHOP, BKNIGHT, BROOK}
universe@41:  59      };
universe@41:  60      memcpy(gamestate->board, initboard, sizeof(Board));
universe@41:  61  }
universe@41:  62  
universe@41:  63  void gamestate_cleanup(GameState *gamestate) {
universe@41:  64      MoveList *elem;
universe@41:  65      elem = gamestate->movelist;
universe@41:  66      while (elem) {
universe@41:  67          MoveList *cur = elem;
universe@41:  68          elem = elem->next;
universe@41:  69          free(cur);
universe@41:  70      };
universe@41:  71  }
universe@41:  72  
universe@41:  73  /* MUST be called IMMEDIATLY after applying a move to work correctly */
universe@41:  74  static void format_move(GameState *gamestate, Move *move) {
universe@41:  75      char *string = move->string;
universe@41:  76      
universe@41:  77      /* at least 8 characters should be available, wipe them out */
universe@41:  78      memset(string, 0, 8);
universe@41:  79      
universe@41:  80      /* special formats for castling */
universe@41:  81      if ((move->piece&PIECE_MASK) == KING &&
universe@41:  82              abs(move->tofile-move->fromfile) == 2) {
universe@41:  83          if (move->tofile==fileidx('c')) {
universe@41:  84              memcpy(string, "O-O-O", 5);
universe@41:  85          } else {
universe@41:  86              memcpy(string, "O-O", 3);
universe@41:  87          }
universe@41:  88      }
universe@41:  89  
universe@41:  90      /* start by notating the piece character */
universe@41:  91      string[0] = getpiecechr(move->piece);
universe@41:  92      int idx = string[0] ? 1 : 0;
universe@41:  93      
universe@41:  94      /* find out how many source information we do need */
universe@41:  95      uint8_t piece = move->piece & PIECE_MASK;
universe@41:  96      if (piece == PAWN) {
universe@41:  97          if (move->capture) {
universe@41:  98              string[idx++] = filechr(move->fromfile);
universe@41:  99          }
universe@41: 100      } else if (piece != KING) {
universe@41: 101          Move threats[16];
universe@41: 102          uint8_t threatcount;
universe@41: 103          get_real_threats(gamestate, move->torow, move->tofile,
universe@41: 104              move->piece&COLOR_MASK, threats, &threatcount);
universe@41: 105          if (threatcount > 1) {
universe@41: 106              int ambrows = 0, ambfiles = 0;
universe@41: 107              for (uint8_t i = 0 ; i < threatcount ; i++) {
universe@41: 108                  if (threats[i].fromrow == move->fromrow) {
universe@41: 109                      ambrows++;
universe@41: 110                  }
universe@41: 111                  if (threats[i].fromfile == move->fromfile) {
universe@41: 112                      ambfiles++;
universe@41: 113                  }
universe@41: 114              }
universe@41: 115              /* ambiguous row, name file */
universe@41: 116              if (ambrows > 1) {
universe@41: 117                  string[idx++] = filechr(move->fromfile);
universe@41: 118              }
universe@41: 119              /* ambiguous file, name row */
universe@41: 120              if (ambfiles > 1) {
universe@41: 121                  string[idx++] = filechr(move->fromrow);
universe@41: 122              }
universe@41: 123          }
universe@41: 124      }
universe@41: 125      
universe@41: 126      /* capturing? */
universe@41: 127      if (move->capture) {
universe@41: 128          string[idx++] = 'x';
universe@41: 129      }
universe@41: 130      
universe@41: 131      /* destination */
universe@41: 132      string[idx++] = filechr(move->tofile);
universe@41: 133      string[idx++] = rowchr(move->torow);
universe@41: 134      
universe@41: 135      /* promotion? */
universe@41: 136      if (move->promotion) {
universe@41: 137          string[idx++] = '=';
universe@41: 138          string[idx++] = getpiecechr(move->promotion);
universe@41: 139      }
universe@41: 140      
universe@41: 141      /* check? */
universe@41: 142      if (move->check) {
universe@41: 143          /* works only, if this function is called when applying the move */
universe@41: 144          string[idx++] = gamestate->checkmate?'#':'+';
universe@41: 145      }
universe@41: 146  }
universe@41: 147  
universe@41: 148  static void addmove(GameState* gamestate, Move *move) {
universe@41: 149      MoveList *elem = malloc(sizeof(MoveList));
universe@41: 150      elem->next = NULL;
universe@41: 151      elem->move = *move;
universe@41: 152      
universe@41: 153      struct timeval curtimestamp;
universe@41: 154      gettimeofday(&curtimestamp, NULL);
universe@41: 155      elem->move.timestamp.tv_sec = curtimestamp.tv_sec;
universe@41: 156      elem->move.timestamp.tv_usec = curtimestamp.tv_usec;
universe@41: 157      
universe@41: 158      if (gamestate->lastmove) {
universe@41: 159          struct movetimeval *lasttstamp = &(gamestate->lastmove->move.timestamp);
universe@41: 160          uint64_t sec = curtimestamp.tv_sec - lasttstamp->tv_sec;
universe@41: 161          suseconds_t micros;
universe@41: 162          if (curtimestamp.tv_usec < lasttstamp->tv_usec) {
universe@41: 163              micros = 1e6L-(lasttstamp->tv_usec - curtimestamp.tv_usec);
universe@41: 164              sec--;
universe@41: 165          } else {
universe@41: 166              micros = curtimestamp.tv_usec - lasttstamp->tv_usec;
universe@41: 167          }
universe@41: 168          
universe@41: 169          elem->move.movetime.tv_sec = sec;
universe@41: 170          elem->move.movetime.tv_usec = micros;
universe@41: 171          
universe@41: 172          gamestate->lastmove->next = elem;
universe@41: 173          gamestate->lastmove = elem;
universe@41: 174      } else {
universe@41: 175          elem->move.movetime.tv_usec = 0;
universe@41: 176          elem->move.movetime.tv_sec = 0;
universe@41: 177          gamestate->movelist = gamestate->lastmove = elem;
universe@41: 178      }
universe@41: 179  }
universe@41: 180  
universe@41: 181  char getpiecechr(uint8_t piece) {
universe@41: 182      switch (piece & PIECE_MASK) {
universe@41: 183      case ROOK: return 'R';
universe@41: 184      case KNIGHT: return 'N';
universe@41: 185      case BISHOP: return 'B';
universe@41: 186      case QUEEN: return 'Q';
universe@41: 187      case KING: return 'K';
universe@41: 188      default: return '\0';
universe@41: 189      }
universe@41: 190  }
universe@41: 191  
universe@41: 192  uint8_t getpiece(char c) {
universe@41: 193      switch (c) {
universe@41: 194          case 'R': return ROOK;
universe@41: 195          case 'N': return KNIGHT;
universe@41: 196          case 'B': return BISHOP;
universe@41: 197          case 'Q': return QUEEN;
universe@41: 198          case 'K': return KING;
universe@41: 199          default: return 0;
universe@41: 200      }
universe@41: 201  }
universe@41: 202  
universe@41: 203  static void apply_move_impl(GameState *gamestate, Move *move, _Bool simulate) {
universe@41: 204      uint8_t piece = move->piece & PIECE_MASK;
universe@41: 205      uint8_t color = move->piece & COLOR_MASK;
universe@41: 206      
universe@41: 207      /* en passant capture */
universe@41: 208      if (move->capture && piece == PAWN &&
universe@41: 209          mdst(gamestate->board, move) == 0) {
universe@41: 210          gamestate->board[move->fromrow][move->tofile] = 0;
universe@41: 211      }
universe@41: 212      
universe@41: 213      /* remove old en passant threats */
universe@41: 214      for (uint8_t file = 0 ; file < 8 ; file++) {
universe@41: 215          gamestate->board[3][file] &= ~ENPASSANT_THREAT;
universe@41: 216          gamestate->board[4][file] &= ~ENPASSANT_THREAT;
universe@41: 217      }
universe@41: 218      
universe@41: 219      /* add new en passant threat */
universe@41: 220      if (piece == PAWN && (
universe@41: 221          (move->fromrow == 1 && move->torow == 3) ||
universe@41: 222          (move->fromrow == 6 && move->torow == 4))) {
universe@41: 223          move->piece |= ENPASSANT_THREAT;
universe@41: 224      }
universe@41: 225      
universe@41: 226      /* move (and maybe capture or promote) */
universe@41: 227      msrc(gamestate->board, move) = 0;
universe@41: 228      if (move->promotion) {
universe@41: 229          mdst(gamestate->board, move) = move->promotion;
universe@41: 230      } else {
universe@41: 231          mdst(gamestate->board, move) = move->piece;
universe@41: 232      }
universe@41: 233      
universe@41: 234      /* castling */
universe@41: 235      if (piece == KING && move->fromfile == fileidx('e')) {
universe@41: 236          
universe@41: 237          if (move->tofile == fileidx('g')) {
universe@41: 238              gamestate->board[move->torow][fileidx('h')] = 0;
universe@41: 239              gamestate->board[move->torow][fileidx('f')] = color|ROOK;
universe@41: 240          } else if (move->tofile == fileidx('c')) {
universe@41: 241              gamestate->board[move->torow][fileidx('a')] = 0;
universe@41: 242              gamestate->board[move->torow][fileidx('d')] = color|ROOK;
universe@41: 243          }
universe@41: 244      }
universe@41: 245  
universe@41: 246      if (!simulate) {
universe@41: 247          if (!move->string[0]) {
universe@41: 248              format_move(gamestate, move);
universe@41: 249          }
universe@41: 250      }
universe@41: 251      /* add move, even in simulation (checkmate test needs it) */
universe@41: 252      addmove(gamestate, move);
universe@41: 253  }
universe@41: 254  
universe@41: 255  void apply_move(GameState *gamestate, Move *move) {
universe@41: 256      apply_move_impl(gamestate, move, 0);
universe@41: 257  }
universe@41: 258  
universe@41: 259  static int validate_move_rules(GameState *gamestate, Move *move) {
universe@41: 260      /* validate indices (don't trust opponent) */
universe@41: 261      if (!chkidx(move)) {
universe@41: 262          return INVALID_POSITION;
universe@41: 263      }
universe@41: 264      
universe@41: 265      /* must move */
universe@41: 266      if (move->fromfile == move->tofile && move->fromrow == move->torow) {
universe@41: 267          return INVALID_MOVE_SYNTAX;
universe@41: 268      }
universe@41: 269      
universe@41: 270      /* does piece exist */
universe@41: 271      if ((msrc(gamestate->board, move)&(PIECE_MASK|COLOR_MASK))
universe@41: 272             != (move->piece&(PIECE_MASK|COLOR_MASK))) {
universe@41: 273          return INVALID_POSITION;
universe@41: 274      }
universe@41: 275      
universe@41: 276      /* can't capture own pieces */
universe@41: 277      if ((mdst(gamestate->board, move) & COLOR_MASK)
universe@41: 278              == (move->piece & COLOR_MASK)) {
universe@41: 279          return RULES_VIOLATED;
universe@41: 280      }
universe@41: 281      
universe@41: 282      /* must capture, if and only if destination is occupied */
universe@41: 283      if ((mdst(gamestate->board, move) == 0 && move->capture) ||
universe@41: 284              (mdst(gamestate->board, move) != 0 && !move->capture)) {
universe@41: 285          return INVALID_MOVE_SYNTAX;
universe@41: 286      }
universe@41: 287      
universe@41: 288      /* validate individual rules */
universe@41: 289      _Bool chkrules;
universe@41: 290      switch (move->piece & PIECE_MASK) {
universe@41: 291      case PAWN:
universe@41: 292          chkrules = pawn_chkrules(gamestate, move) &&
universe@41: 293              !pawn_isblocked(gamestate, move);
universe@41: 294          break;
universe@41: 295      case ROOK:
universe@41: 296          chkrules = rook_chkrules(move) &&
universe@41: 297              !rook_isblocked(gamestate, move);
universe@41: 298          break;
universe@41: 299      case KNIGHT:
universe@41: 300          chkrules = knight_chkrules(move); /* knight is never blocked */
universe@41: 301          break;
universe@41: 302      case BISHOP:
universe@41: 303          chkrules = bishop_chkrules(move) &&
universe@41: 304              !bishop_isblocked(gamestate, move);
universe@41: 305          break;
universe@41: 306      case QUEEN:
universe@41: 307          chkrules = queen_chkrules(move) &&
universe@41: 308              !queen_isblocked(gamestate, move);
universe@41: 309          break;
universe@41: 310      case KING:
universe@41: 311          chkrules = king_chkrules(gamestate, move) &&
universe@41: 312              !king_isblocked(gamestate, move);
universe@41: 313          break;
universe@41: 314      default:
universe@41: 315          return INVALID_MOVE_SYNTAX;
universe@41: 316      }
universe@41: 317      
universe@41: 318      return chkrules ? VALID_MOVE_SEMANTICS : RULES_VIOLATED;
universe@41: 319  }
universe@41: 320  
universe@41: 321  int validate_move(GameState *gamestate, Move *move) {
universe@41: 322      
universe@41: 323      int result = validate_move_rules(gamestate, move);
universe@41: 324      
universe@41: 325      /* cancel processing to save resources */
universe@41: 326      if (result != VALID_MOVE_SEMANTICS) {
universe@41: 327          return result;
universe@41: 328      }
universe@41: 329      
universe@41: 330      /* find kings for check validation */
universe@41: 331      uint8_t piececolor = (move->piece & COLOR_MASK);
universe@41: 332      
universe@41: 333      uint8_t mykingfile = 0, mykingrow = 0, opkingfile = 0, opkingrow = 0;
universe@41: 334      for (uint8_t row = 0 ; row < 8 ; row++) {
universe@41: 335          for (uint8_t file = 0 ; file < 8 ; file++) {
universe@41: 336              if (gamestate->board[row][file] ==
universe@41: 337                      (piececolor == WHITE?WKING:BKING)) {
universe@41: 338                  mykingfile = file;
universe@41: 339                  mykingrow = row;
universe@41: 340              } else if (gamestate->board[row][file] ==
universe@41: 341                      (piececolor == WHITE?BKING:WKING)) {
universe@41: 342                  opkingfile = file;
universe@41: 343                  opkingrow = row;
universe@41: 344              }
universe@41: 345          }
universe@41: 346      }
universe@41: 347      
universe@41: 348      /* simulate move for check validation */
universe@41: 349      GameState simulation = gamestate_copy_sim(gamestate);
universe@41: 350      Move simmove = *move;
universe@41: 351      apply_move_impl(&simulation, &simmove, 1);
universe@41: 352      
universe@41: 353      /* don't move into or stay in check position */
universe@41: 354      if (is_covered(&simulation, mykingrow, mykingfile,
universe@41: 355          opponent_color(piececolor))) {
universe@41: 356          
universe@41: 357          gamestate_cleanup(&simulation);
universe@41: 358          if ((move->piece & PIECE_MASK) == KING) {
universe@41: 359              return KING_MOVES_INTO_CHECK;
universe@41: 360          } else {
universe@41: 361              /* last move is always not null in this case */
universe@41: 362              return gamestate->lastmove->move.check ?
universe@41: 363                  KING_IN_CHECK : PIECE_PINNED;
universe@41: 364          }
universe@41: 365      }
universe@41: 366      
universe@41: 367      /* correct check and checkmate flags (move is still valid) */
universe@41: 368      Move threats[16];
universe@41: 369      uint8_t threatcount;
universe@41: 370      move->check = get_threats(&simulation, opkingrow, opkingfile,
universe@41: 371          piececolor, threats, &threatcount);
universe@41: 372      
universe@41: 373      if (move->check) {
universe@41: 374          /* determine possible escape fields */
universe@41: 375          _Bool canescape = 0;
universe@41: 376          for (int dr = -1 ; dr <= 1 && !canescape ; dr++) {
universe@41: 377              for (int df = -1 ; df <= 1 && !canescape ; df++) {
universe@41: 378                  if (!(dr == 0 && df == 0)  &&
universe@41: 379                          isidx(opkingrow + dr) && isidx(opkingfile + df)) {
universe@41: 380                      
universe@41: 381                      /* escape field neither blocked nor covered */
universe@41: 382                      if ((simulation.board[opkingrow + dr][opkingfile + df]
universe@41: 383                              & COLOR_MASK) != opponent_color(piececolor)) {
universe@41: 384                          canescape |= !is_covered(&simulation,
universe@41: 385                              opkingrow + dr, opkingfile + df, piececolor);
universe@41: 386                      }
universe@41: 387                  }
universe@41: 388              }
universe@41: 389          }
universe@41: 390          /* can't escape, can he capture? */
universe@41: 391          if (!canescape && threatcount == 1) {
universe@41: 392              canescape = is_attacked(&simulation, threats[0].fromrow,
universe@41: 393                  threats[0].fromfile, opponent_color(piececolor));
universe@41: 394          }
universe@41: 395          
universe@41: 396          /* can't capture, can he block? */
universe@41: 397          if (!canescape && threatcount == 1) {
universe@41: 398              Move *threat = &(threats[0]);
universe@41: 399              uint8_t threatpiece = threat->piece & PIECE_MASK;
universe@41: 400              
universe@41: 401              /* knight, pawns and the king cannot be blocked */
universe@41: 402              if (threatpiece == BISHOP || threatpiece == ROOK
universe@41: 403                  || threatpiece == QUEEN) {
universe@41: 404                  if (threat->fromrow == threat->torow) {
universe@41: 405                      /* rook aspect (on row) */
universe@41: 406                      int d = threat->tofile > threat->fromfile ? 1 : -1;
universe@41: 407                      uint8_t file = threat->fromfile;
universe@41: 408                      while (!canescape && file != threat->tofile - d) {
universe@41: 409                          file += d;
universe@41: 410                          canescape |= is_protected(&simulation,
universe@41: 411                              threat->torow, file, opponent_color(piececolor));
universe@41: 412                      }
universe@41: 413                  } else if (threat->fromfile == threat->tofile) {
universe@41: 414                      /* rook aspect (on file) */
universe@41: 415                      int d = threat->torow > threat->fromrow ? 1 : -1;
universe@41: 416                      uint8_t row = threat->fromrow;
universe@41: 417                      while (!canescape && row != threat->torow - d) {
universe@41: 418                          row += d;
universe@41: 419                          canescape |= is_protected(&simulation,
universe@41: 420                              row, threat->tofile, opponent_color(piececolor));
universe@41: 421                      }
universe@41: 422                  } else {
universe@41: 423                      /* bishop aspect */
universe@41: 424                      int dr = threat->torow > threat->fromrow ? 1 : -1;
universe@41: 425                      int df = threat->tofile > threat->fromfile ? 1 : -1;
universe@41: 426  
universe@41: 427                      uint8_t row = threat->fromrow;
universe@41: 428                      uint8_t file = threat->fromfile;
universe@41: 429                      while (!canescape && file != threat->tofile - df
universe@41: 430                          && row != threat->torow - dr) {
universe@41: 431                          row += dr;
universe@41: 432                          file += df;
universe@41: 433                          canescape |= is_protected(&simulation, row, file,
universe@41: 434                              opponent_color(piececolor));
universe@41: 435                      }
universe@41: 436                  }
universe@41: 437              }
universe@41: 438          }
universe@41: 439              
universe@41: 440          if (!canescape) {
universe@41: 441              gamestate->checkmate = 1;
universe@41: 442          }
universe@41: 443      }
universe@41: 444      
universe@41: 445      gamestate_cleanup(&simulation);
universe@41: 446      
universe@41: 447      return VALID_MOVE_SEMANTICS;
universe@41: 448  }
universe@41: 449  
universe@41: 450  _Bool get_threats(GameState *gamestate, uint8_t row, uint8_t file,
universe@41: 451          uint8_t color, Move *threats, uint8_t *threatcount) {
universe@41: 452      Move candidates[32];
universe@41: 453      int candidatecount = 0;
universe@41: 454      for (uint8_t r = 0 ; r < 8 ; r++) {
universe@41: 455          for (uint8_t f = 0 ; f < 8 ; f++) {
universe@41: 456              if ((gamestate->board[r][f] & COLOR_MASK) == color) {
universe@41: 457                  // non-capturing move
universe@41: 458                  memset(&(candidates[candidatecount]), 0, sizeof(Move));
universe@41: 459                  candidates[candidatecount].piece = gamestate->board[r][f];
universe@41: 460                  candidates[candidatecount].fromrow = r;
universe@41: 461                  candidates[candidatecount].fromfile = f;
universe@41: 462                  candidates[candidatecount].torow = row;
universe@41: 463                  candidates[candidatecount].tofile = file;
universe@41: 464                  candidatecount++;
universe@41: 465  
universe@41: 466                  // capturing move
universe@41: 467                  memcpy(&(candidates[candidatecount]),
universe@41: 468                      &(candidates[candidatecount-1]), sizeof(Move));
universe@41: 469                  candidates[candidatecount].capture = 1;
universe@41: 470                  candidatecount++;
universe@41: 471              }
universe@41: 472          }
universe@41: 473      }
universe@41: 474  
universe@41: 475      if (threatcount) {
universe@41: 476          *threatcount = 0;
universe@41: 477      }
universe@41: 478      
universe@41: 479      
universe@41: 480      _Bool result = 0;
universe@41: 481      
universe@41: 482      for (int i = 0 ; i < candidatecount ; i++) {
universe@41: 483          if (validate_move_rules(gamestate, &(candidates[i]))
universe@41: 484                  == VALID_MOVE_SEMANTICS) {
universe@41: 485              result = 1;
universe@41: 486              if (threats && threatcount) {
universe@41: 487                  threats[(*threatcount)++] = candidates[i];
universe@41: 488              }
universe@41: 489          }
universe@41: 490      }
universe@41: 491      
universe@41: 492      return result;
universe@41: 493  }
universe@41: 494  
universe@41: 495  _Bool is_pinned(GameState *gamestate, Move *move) {
universe@41: 496      uint8_t color = move->piece & COLOR_MASK;
universe@41: 497  
universe@41: 498      uint8_t kingfile = 0, kingrow = 0;
universe@41: 499      for (uint8_t row = 0 ; row < 8 ; row++) {
universe@41: 500          for (uint8_t file = 0 ; file < 8 ; file++) {
universe@41: 501              if (gamestate->board[row][file] == (color|KING)) {
universe@41: 502                  kingfile = file;
universe@41: 503                  kingrow = row;
universe@41: 504              }
universe@41: 505          }
universe@41: 506      }
universe@41: 507  
universe@41: 508      GameState simulation = gamestate_copy_sim(gamestate);
universe@41: 509      Move simmove = *move;
universe@41: 510      apply_move(&simulation, &simmove);
universe@41: 511      _Bool covered = is_covered(&simulation,
universe@41: 512          kingrow, kingfile, opponent_color(color));
universe@41: 513      gamestate_cleanup(&simulation);
universe@41: 514      
universe@41: 515      return covered;
universe@41: 516  }
universe@41: 517  
universe@41: 518  _Bool get_real_threats(GameState *gamestate, uint8_t row, uint8_t file,
universe@41: 519          uint8_t color, Move *threats, uint8_t *threatcount) {
universe@41: 520      
universe@41: 521      if (threatcount) {
universe@41: 522          *threatcount = 0;
universe@41: 523      }
universe@41: 524  
universe@41: 525      Move candidates[16];
universe@41: 526      uint8_t candidatecount;
universe@41: 527      if (get_threats(gamestate, row, file, color, candidates, &candidatecount)) {
universe@41: 528          
universe@41: 529          _Bool result = 0;
universe@41: 530          uint8_t kingfile = 0, kingrow = 0;
universe@41: 531          for (uint8_t row = 0 ; row < 8 ; row++) {
universe@41: 532              for (uint8_t file = 0 ; file < 8 ; file++) {
universe@41: 533                  if (gamestate->board[row][file] == (color|KING)) {
universe@41: 534                      kingfile = file;
universe@41: 535                      kingrow = row;
universe@41: 536                  }
universe@41: 537              }
universe@41: 538          }
universe@41: 539  
universe@41: 540          for (uint8_t i = 0 ; i < candidatecount ; i++) {
universe@41: 541              GameState simulation = gamestate_copy_sim(gamestate);
universe@41: 542              Move simmove = candidates[i];
universe@41: 543              apply_move(&simulation, &simmove);
universe@41: 544              if (!is_covered(&simulation, kingrow, kingfile,
universe@41: 545                      opponent_color(color))) {
universe@41: 546                  result = 1;
universe@41: 547                  if (threats && threatcount) {
universe@41: 548                      threats[(*threatcount)++] = candidates[i];
universe@41: 549                  }
universe@41: 550              }
universe@41: 551          }
universe@41: 552          
universe@41: 553          return result;
universe@41: 554      } else {
universe@41: 555          return 0;
universe@41: 556      }
universe@41: 557  }
universe@41: 558  
universe@41: 559  static int getlocation(GameState *gamestate, Move *move) {   
universe@41: 560  
universe@41: 561      uint8_t color = move->piece & COLOR_MASK;
universe@41: 562      _Bool incheck = gamestate->lastmove?gamestate->lastmove->move.check:0;
universe@41: 563      
universe@41: 564      Move threats[16], *threat = NULL;
universe@41: 565      uint8_t threatcount;
universe@41: 566      
universe@41: 567      if (get_threats(gamestate, move->torow, move->tofile, color,
universe@41: 568              threats, &threatcount)) {
universe@41: 569          
universe@41: 570          int reason = INVALID_POSITION;
universe@41: 571          
universe@41: 572          // find threats for the specified position
universe@41: 573          for (uint8_t i = 0 ; i < threatcount ; i++) {
universe@41: 574              if ((threats[i].piece & (PIECE_MASK | COLOR_MASK))
universe@41: 575                      == move->piece &&
universe@41: 576                      (move->fromrow == POS_UNSPECIFIED ||
universe@41: 577                      move->fromrow == threats[i].fromrow) &&
universe@41: 578                      (move->fromfile == POS_UNSPECIFIED ||
universe@41: 579                      move->fromfile == threats[i].fromfile)) {
universe@41: 580  
universe@41: 581                  if (threat) {
universe@41: 582                      return AMBIGUOUS_MOVE;
universe@41: 583                  } else {
universe@41: 584                      // found threat is no real threat
universe@41: 585                      if (is_pinned(gamestate, &(threats[i]))) {
universe@41: 586                          reason = incheck?KING_IN_CHECK:PIECE_PINNED;
universe@41: 587                      } else {
universe@41: 588                          threat = &(threats[i]);
universe@41: 589                      }
universe@41: 590                  }
universe@41: 591              }
universe@41: 592          }
universe@41: 593          
universe@41: 594          // can't threaten specified position
universe@41: 595          if (!threat) {
universe@41: 596              return reason;
universe@41: 597          }
universe@41: 598  
universe@41: 599          memcpy(move, threat, sizeof(Move));
universe@41: 600          return VALID_MOVE_SYNTAX;
universe@41: 601      } else {
universe@41: 602          return INVALID_POSITION;
universe@41: 603      }
universe@41: 604  }
universe@41: 605  
universe@41: 606  int eval_move(GameState *gamestate, char *mstr, Move *move, uint8_t color) {
universe@41: 607      memset(move, 0, sizeof(Move));
universe@41: 608      move->fromfile = POS_UNSPECIFIED;
universe@41: 609      move->fromrow = POS_UNSPECIFIED;
universe@41: 610  
universe@41: 611      size_t len = strlen(mstr);
universe@41: 612      if (len < 1 || len > 6) {
universe@41: 613          return INVALID_MOVE_SYNTAX;
universe@41: 614      }
universe@41: 615      
universe@41: 616      /* evaluate check/checkmate flags */
universe@41: 617      if (mstr[len-1] == '+') {
universe@41: 618          len--; mstr[len] = '\0';
universe@41: 619          move->check = 1;
universe@41: 620      } else if (mstr[len-1] == '#') {
universe@41: 621          len--; mstr[len] = '\0';
universe@41: 622          /* ignore - validation should set game state */
universe@41: 623      }
universe@41: 624      
universe@41: 625      /* evaluate promotion */
universe@41: 626      if (len > 3 && mstr[len-2] == '=') {
universe@41: 627          move->promotion = getpiece(mstr[len-1]);
universe@41: 628          if (!move->promotion) {
universe@41: 629              return INVALID_MOVE_SYNTAX;
universe@41: 630          } else {
universe@41: 631              move->promotion |= color;
universe@41: 632              len -= 2;
universe@41: 633              mstr[len] = 0;
universe@41: 634          }
universe@41: 635      }
universe@41: 636      
universe@41: 637      if (len == 2) {
universe@41: 638          /* pawn move (e.g. "e4") */
universe@41: 639          move->piece = PAWN;
universe@41: 640          move->tofile = fileidx(mstr[0]);
universe@41: 641          move->torow = rowidx(mstr[1]);
universe@41: 642      } else if (len == 3) {
universe@41: 643          if (strcmp(mstr, "O-O") == 0) {
universe@41: 644              /* king side castling */
universe@41: 645              move->piece = KING;
universe@41: 646              move->fromfile = fileidx('e');
universe@41: 647              move->tofile = fileidx('g');
universe@41: 648              move->fromrow = move->torow = color == WHITE ? 0 : 7;
universe@41: 649          } else {
universe@41: 650              /* move (e.g. "Nf3") */
universe@41: 651              move->piece = getpiece(mstr[0]);
universe@41: 652              move->tofile = fileidx(mstr[1]);
universe@41: 653              move->torow = rowidx(mstr[2]);
universe@41: 654          }
universe@41: 655      } else if (len == 4) {
universe@41: 656          move->piece = getpiece(mstr[0]);
universe@41: 657          if (!move->piece) {
universe@41: 658              move->piece = PAWN;
universe@41: 659              move->fromfile = fileidx(mstr[0]);
universe@41: 660          }
universe@41: 661          if (mstr[1] == 'x') {
universe@41: 662              /* capture (e.g. "Nxf3", "dxe5") */
universe@41: 663              move->capture = 1;
universe@41: 664          } else {
universe@41: 665              /* move (e.g. "Ndf3", "N2c3", "e2e4") */
universe@41: 666              if (isfile(mstr[1])) {
universe@41: 667                  move->fromfile = fileidx(mstr[1]);
universe@41: 668                  if (move->piece == PAWN) {
universe@41: 669                      move->piece = 0;
universe@41: 670                  }
universe@41: 671              } else {
universe@41: 672                  move->fromrow = rowidx(mstr[1]);
universe@41: 673              }
universe@41: 674          }
universe@41: 675          move->tofile = fileidx(mstr[2]);
universe@41: 676          move->torow = rowidx(mstr[3]);
universe@41: 677      } else if (len == 5) {
universe@41: 678          if (strcmp(mstr, "O-O-O") == 0) {
universe@41: 679              /* queen side castling "O-O-O" */
universe@41: 680              move->piece = KING;
universe@41: 681              move->fromfile = fileidx('e');
universe@41: 682              move->tofile = fileidx('c');
universe@41: 683              move->fromrow = move->torow = color == WHITE ? 0 : 7;
universe@41: 684          } else {
universe@41: 685              move->piece = getpiece(mstr[0]);
universe@41: 686              if (mstr[2] == 'x') {
universe@41: 687                  move->capture = 1;
universe@41: 688                  if (move->piece) {
universe@41: 689                      /* capture (e.g. "Ndxf3") */
universe@41: 690                      move->fromfile = fileidx(mstr[1]);
universe@41: 691                  } else {
universe@41: 692                      /* long notation capture (e.g. "e5xf6") */
universe@41: 693                      move->piece = PAWN;
universe@41: 694                      move->fromfile = fileidx(mstr[0]);
universe@41: 695                      move->fromrow = rowidx(mstr[1]);
universe@41: 696                  }
universe@41: 697              } else {
universe@41: 698                  /* long notation move (e.g. "Nc5a4") */
universe@41: 699                  move->fromfile = fileidx(mstr[1]);
universe@41: 700                  move->fromrow = rowidx(mstr[2]);
universe@41: 701              }
universe@41: 702              move->tofile = fileidx(mstr[3]);
universe@41: 703              move->torow = rowidx(mstr[4]);
universe@41: 704          }
universe@41: 705      } else if (len == 6) {
universe@41: 706          /* long notation capture (e.g. "Nc5xf3") */
universe@41: 707          if (mstr[3] == 'x') {
universe@41: 708              move->capture = 1;
universe@41: 709              move->piece = getpiece(mstr[0]);
universe@41: 710              move->fromfile = fileidx(mstr[1]);
universe@41: 711              move->fromrow = rowidx(mstr[2]);
universe@41: 712              move->tofile = fileidx(mstr[4]);
universe@41: 713              move->torow = rowidx(mstr[5]);
universe@41: 714          }
universe@41: 715      }
universe@41: 716  
universe@41: 717      
universe@41: 718      if (move->piece) {
universe@41: 719          if (move->piece == PAWN
universe@41: 720              && move->torow == (color==WHITE?7:0)
universe@41: 721              && !move->promotion) {
universe@41: 722              return NEED_PROMOTION;
universe@41: 723          }
universe@41: 724          
universe@41: 725          move->piece |= color;
universe@41: 726          if (move->fromfile == POS_UNSPECIFIED
universe@41: 727              || move->fromrow == POS_UNSPECIFIED) {
universe@41: 728              return getlocation(gamestate, move);
universe@41: 729          } else {
universe@41: 730              return chkidx(move) ? VALID_MOVE_SYNTAX : INVALID_POSITION;
universe@41: 731          }
universe@41: 732      } else {
universe@41: 733          return INVALID_MOVE_SYNTAX;
universe@41: 734      }
universe@41: 735  }
universe@41: 736  
universe@41: 737  _Bool is_protected(GameState *gamestate, uint8_t row, uint8_t file,
universe@41: 738          uint8_t color) {
universe@41: 739      
universe@41: 740      Move threats[16];
universe@41: 741      uint8_t threatcount;
universe@41: 742      if (get_real_threats(gamestate, row, file, color, threats, &threatcount)) {
universe@41: 743          for (int i = 0 ; i < threatcount ; i++) {
universe@41: 744              if (threats[i].piece != (color|KING)) {
universe@41: 745                  return 1;
universe@41: 746              }
universe@41: 747          }
universe@41: 748          return 0;
universe@41: 749      } else {
universe@41: 750          return 0;
universe@41: 751      }
universe@41: 752  }
universe@41: 753  
universe@41: 754  uint16_t remaining_movetime(GameInfo *gameinfo, GameState *gamestate,
universe@41: 755          uint8_t color) {
universe@41: 756      if (!gameinfo->timecontrol) {
universe@41: 757          return 0;
universe@41: 758      }
universe@41: 759      
universe@41: 760      if (gamestate->movelist) {
universe@41: 761          uint16_t time = gameinfo->time;
universe@41: 762          suseconds_t micros = 0;
universe@41: 763          
universe@41: 764          MoveList *movelist = color == WHITE ?
universe@41: 765              gamestate->movelist : gamestate->movelist->next;
universe@41: 766          
universe@41: 767          while (movelist) {
universe@41: 768              time += gameinfo->addtime;
universe@41: 769              
universe@41: 770              struct movetimeval *movetime = &(movelist->move.movetime);
universe@41: 771              if (movetime->tv_sec >= time) {
universe@41: 772                  return 0;
universe@41: 773              }
universe@41: 774              
universe@41: 775              time -= movetime->tv_sec;
universe@41: 776              micros += movetime->tv_usec;
universe@41: 777              
universe@41: 778              movelist = movelist->next ? movelist->next->next : NULL;
universe@41: 779          }
universe@41: 780          
universe@41: 781          time_t sec;
universe@41: 782          movelist = gamestate->lastmove;
universe@41: 783          if ((movelist->move.piece & COLOR_MASK) != color) {
universe@41: 784              struct movetimeval *lastmovetstamp = &(movelist->move.timestamp);
universe@41: 785              struct timeval currenttstamp;
universe@41: 786              gettimeofday(¤ttstamp, NULL);
universe@41: 787              micros += currenttstamp.tv_usec - lastmovetstamp->tv_usec;
universe@41: 788              sec = currenttstamp.tv_sec - lastmovetstamp->tv_sec;
universe@41: 789              if (sec >= time) {
universe@41: 790                  return 0;
universe@41: 791              }
universe@41: 792              
universe@41: 793              time -= sec;
universe@41: 794          }
universe@41: 795          
universe@41: 796          sec = micros / 1e6L;
universe@41: 797          
universe@41: 798          if (sec >= time) {
universe@41: 799              return 0;
universe@41: 800          }
universe@41: 801  
universe@41: 802          time -= sec;
universe@41: 803          
universe@41: 804          return time;
universe@41: 805      } else {
universe@41: 806          return gameinfo->time;
universe@41: 807      }
universe@41: 808  }
universe@41:
universe@41: universe@41: universe@41: