git.sesse.net Git - pgn-extract/blob - map.c

   1 /*
   2  *  Program: pgn-extract: a Portable Game Notation (PGN) extractor.
   3  *  Copyright (C) 1994-2014 David Barnes
   4  *  This program is free software; you can redistribute it and/or modify
   5  *  it under the terms of the GNU General Public License as published by
   6  *  the Free Software Foundation; either version 1, or (at your option)
   7  *  any later version.
   8  *
   9  *  This program is distributed in the hope that it will be useful,
  10  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12  *  GNU General Public License for more details.
  13  *
  14  *  You should have received a copy of the GNU General Public License
  15  *  along with this program; if not, write to the Free Software
  16  *  Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  17  *
  18  *  David Barnes may be contacted as D.J.Barnes@kent.ac.uk
  19  *  http://www.cs.kent.ac.uk/people/staff/djb/
  20  *
  21  */
  22
  23 #include <stdio.h>
  24 #include <stdlib.h>
  25 #include <string.h>
  26 #include "bool.h"
  27 #include "mymalloc.h"
  28 #include "defs.h"
  29 #include "typedef.h"
  30 #include "tokens.h"
  31 #include "taglist.h"
  32 #include "lex.h"
  33 #include "map.h"
  34 #include "decode.h"
  35 #include "apply.h"
  36
  37         /* Structures to hold the x,y displacements of the various
  38          * piece movements.
  39          */
  40
  41 /* Define a list of possible Knight moves. */
  42 #define NUM_KNIGHT_MOVES 8
  43 static short Knight_moves[2*NUM_KNIGHT_MOVES] =
  44         {  1, 2,
  45            1,-2,
  46            2, 1,
  47            2,-1,
  48           -1, 2,
  49           -1,-2,
  50           -2, 1,
  51           -2,-1,
  52         };
  53
  54 /* Define a list of possible Bishop moves. */
  55 #define NUM_BISHOP_MOVES 4
  56 static short Bishop_moves[2*NUM_BISHOP_MOVES] =
  57     {  1, 1,
  58        1,-1,
  59       -1, 1,
  60       -1,-1
  61     };
  62
  63 /* Define a list of possible Rook moves. */
  64 #define NUM_ROOK_MOVES 4
  65 static short Rook_moves[2*NUM_ROOK_MOVES] =
  66     {  1, 0,
  67        0, 1,
  68       -1, 0,
  69        0,-1
  70     };
  71
  72 /* Define a list of possible King moves. */
  73 #define NUM_KING_MOVES 8
  74 static short King_moves[2*NUM_KING_MOVES] =
  75     {  1, 0,
  76        1, 1,
  77        1,-1,
  78        0, 1,
  79        0,-1,
  80       -1, 0,
  81       -1, 1,
  82       -1,-1,
  83     };
  84
  85 /* Define a list of possible Queen moves. */
  86 #define NUM_QUEEN_MOVES 8
  87 static short Queen_moves[2*NUM_QUEEN_MOVES] =
  88     {  1, 0,
  89        1, 1,
  90        1,-1,
  91        0, 1,
  92        0,-1,
  93       -1, 0,
  94       -1, 1,
  95       -1,-1,
  96     };
  97
  98
  99         /* A table of hash values for square/piece/colour combinations.
 100          * When a piece is moved, the hash value is xor-ed into a
 101          * running description of the current board state.
 102          */
 103 #define NUMBER_OF_PIECES 6
 104 static HashCode HashTab[BOARDSIZE][BOARDSIZE][NUMBER_OF_PIECES][2];
 105
 106         /* Prototypes for functions in this file. */
 107
 108         /* Code to allocate and free MovePair structures.  New moves are
 109          * allocated from the move_pool, if it isn't empty.  Old moves
 110          * are freed to this pool.
 111          * This is used to avoid too much fragmentation of the heap.
 112          * Since the program will spend a lot of its life allocating and
 113          * deallocating move structures, we might as well hang on to them.
 114          */
 115 /* Keep a pool of free move structures. */
 116 static MovePair *move_pool = NULL;
 117
 118 static MovePair *
 119 malloc_move(void)
 120 {   MovePair *move;
 121
 122     if(move_pool != NULL){
 123         move = move_pool;
 124         move_pool = move_pool->next;
 125     }
 126     else{
 127         move = (MovePair *)MallocOrDie(sizeof(MovePair));
 128     }
 129     move->next = NULL;
 130     return move;
 131 }
 132
 133         /* Append another move pair onto moves, and return the new list. */
 134 static MovePair *
 135 append_move_pair(Col from_col, Rank from_rank, Col to_col, Rank to_rank,MovePair *moves)
 136 {   MovePair *move = malloc_move();
 137
 138     move->from_rank = from_rank;
 139     move->from_col = from_col;
 140     move->to_rank = to_rank;
 141     move->to_col = to_col;
 142     move->next = moves;
 143     return move;
 144 }
 145
 146         /* Simply add the move to the free move pool. */
 147 static void
 148 free_move_pair(MovePair *move)
 149 {
 150     move->next = move_pool;
 151     move_pool = move;
 152 }
 153
 154         /* Free a whole list of moves to the move pool. */
 155 void
 156 free_move_pair_list(MovePair *move_list)
 157 {
 158     if(move_list != NULL){
 159         free_move_pair_list(move_list->next);
 160         free_move_pair(move_list);
 161     }
 162 }
 163
 164         /* Produce a hash value for each piece, square, colour combination.
 165          * This code is a modified version of that to be found in
 166          * Steven J. Edwards' SAN kit.
 167          */
 168 #define SHIFT_LENGTH 7
 169 void
 170 init_hashtab(void)
 171 {   Piece piece;
 172     Colour colour;
 173     Rank rank;
 174     Col col;
 175     static HashCode seed = 0;
 176
 177     for(col = FIRSTCOL; col <= LASTCOL; col++){
 178       for(rank = FIRSTRANK; rank <= LASTRANK; rank++){
 179         for(piece = PAWN; piece <= KING; piece++){
 180           for(colour = BLACK; colour <= WHITE; colour++){
 181             HashCode code;
 182
 183 #if 1
 184             /* Try to use a wider range of the available values
 185              * in an attempt to avoid spurious hash matches.
 186              */
 187             seed = (seed * 1103515245L) + 123456789L;
 188 #else
 189             /* This is the version used up to and including version 13.8. */
 190             seed = (seed * 1103515245L) + 12345L;
 191 #endif
 192             code = (seed >> SHIFT_LENGTH);
 193             HashTab[col-FIRSTCOL][rank-FIRSTRANK][piece-PAWN][colour-BLACK] = code;
 194           }
 195         }
 196       }
 197     }
 198 }
 199
 200         /* Look up the hash value for this combination. */
 201 HashCode
 202 HashLookup(Col col, Rank rank, Piece piece, Colour colour)
 203 {
 204     return HashTab[col-FIRSTCOL][rank-FIRSTRANK][piece-PAWN][colour-BLACK];
 205 }
 206
 207         /* Is the given piece of the named colour? */
 208 static Boolean
 209 piece_is_colour(Piece coloured_piece, Colour colour)
 210 {
 211     return EXTRACT_COLOUR(coloured_piece) == colour;
 212 }
 213
 214         /* Make the given move.  This is assumed to have been thoroughly
 215          * checked beforehand, and the from_ and to_ information to be
 216          * complete.  Update the board structure to reflect
 217          * the full set of changes implied by it.
 218          */
 219 void
 220 make_move(MoveClass class, Col from_col, Rank from_rank, Col to_col, Rank to_rank,
 221           Piece piece, Colour colour,Board *board)
 222 {   short to_r = RankConvert(to_rank);
 223     short to_c = ColConvert(to_col);
 224     short from_r = RankConvert(from_rank);
 225     short from_c = ColConvert(from_col);
 226     /* Does this move involve a capture? */
 227     Boolean capture = FALSE;
 228
 229     /* If a KING or ROOK is moved, this might affect castling rights. */
 230     if(piece == KING){
 231         if(colour == WHITE){
 232             board->WKingCol = to_col;
 233             board->WKingRank = to_rank;
 234             board->WKingCastle =
 235                     board->WQueenCastle = FALSE;
 236         }
 237         else{
 238             board->BKingCol = to_col;
 239             board->BKingRank = to_rank;
 240             board->BKingCastle =
 241                     board->BQueenCastle = FALSE;
 242         }
 243     }
 244     else if(piece == ROOK){
 245         /* Some castling rights may need disallowing. */
 246         if(colour == WHITE){
 247             if(from_rank == FIRSTRANK){
 248                 if(from_col == FIRSTCOL){
 249                     board->WQueenCastle = FALSE;
 250                 }
 251                 else if(from_col == LASTCOL){
 252                     board->WKingCastle = FALSE;
 253                 }
 254                 else{
 255                     /* No change. */
 256                 }
 257             }
 258         }
 259         else{
 260             if(from_rank == LASTRANK){
 261                 if(from_col == FIRSTCOL){
 262                     board->BQueenCastle = FALSE;
 263                 }
 264                 else if(from_col == LASTCOL){
 265                     board->BKingCastle = FALSE;
 266                 }
 267                 else{
 268                     /* No change. */
 269                 }
 270             }
 271         }
 272     }
 273     else{
 274         /* Castling not in question from the piece being moved,
 275          * but see below for checks on any captured piece.
 276          */
 277     }
 278     /* Check for en-passant rights resulting from this move. */
 279     if(piece != PAWN){
 280         /* The move cannot result in en-passant rights. */
 281         board->EnPassant = FALSE;
 282     }
 283     else{
 284         if(colour == WHITE){
 285             if((from_rank == '2') && (to_rank == '4')){
 286                 /* This move permits an en-passant capture on the following move. */
 287                 board->EnPassant = TRUE;
 288                 board->ep_rank = to_rank-1;
 289                 board->ep_col = to_col;
 290             }
 291             else if((board->EnPassant) && (board->ep_rank == to_rank) &&
 292                         (board->ep_col == to_col)){
 293                 /* This is an ep capture. Remove the intermediate pawn. */
 294                 board->board[RankConvert(to_rank)-1][ColConvert(to_col)] = EMPTY;
 295                 board->hash_value ^= HashLookup(to_col,to_rank-1,PAWN,BLACK);
 296                 board->EnPassant = FALSE;
 297             }
 298             else{
 299                 board->EnPassant = FALSE;
 300             }
 301         }
 302         else{
 303             if((from_rank == '7') && (to_rank == '5')){
 304                 board->EnPassant = TRUE;
 305                 board->ep_rank = to_rank+1;
 306                 board->ep_col = to_col;
 307             }
 308             else if((board->EnPassant) && (board->ep_rank == to_rank) &&
 309                         (board->ep_col == to_col)){
 310                 /* This is an ep capture. Remove the intermediate pawn. */
 311                 board->board[RankConvert(to_rank)+1][ColConvert(to_col)] = EMPTY;
 312                 board->hash_value ^= HashLookup(to_col,to_rank+1,PAWN,WHITE);
 313                 board->EnPassant = FALSE;
 314             }
 315             else{
 316                 board->EnPassant = FALSE;
 317             }
 318         }
 319     }
 320     /* Clear the source square. */
 321     /* NB: Up to v17-18 there was an error here in the calculation of the hash
 322      * when the move class is PAWN_MOVE_WITH_PROMOTION.
 323      * The value of the promoted piece was removed, rather than the value
 324      * of the pawn because piece is the promoted piece rather than PAWN.
 325      */
 326     if(class == PAWN_MOVE_WITH_PROMOTION && piece != PAWN) {
 327         /* Remove the promoted pawn. */
 328         board->hash_value ^= HashLookup(from_col,from_rank,PAWN,colour);
 329     }
 330     else {
 331         board->hash_value ^= HashLookup(from_col,from_rank,piece,colour);
 332     }
 333     board->board[from_r][from_c] = EMPTY;
 334     if(board->board[to_r][to_c] != EMPTY){
 335         /* Delete the captured piece from the hash value. */
 336         Piece coloured_piece = board->board[to_r][to_c];
 337         Piece removed_piece;
 338         Colour removed_colour;
 339
 340         removed_piece = EXTRACT_PIECE(coloured_piece);
 341         removed_colour = EXTRACT_COLOUR(coloured_piece);
 342         board->hash_value ^= HashLookup(to_col,to_rank,removed_piece,removed_colour);
 343         /* See whether the removed piece is a Rook, as this could
 344          * affect castling rights.
 345          */
 346         if(removed_piece == ROOK){
 347             if(removed_colour == WHITE){
 348                 if(to_rank == FIRSTRANK){
 349                     if(to_col == FIRSTCOL){
 350                         board->WQueenCastle = FALSE;
 351                     }
 352                     else if(to_col == LASTCOL){
 353                         board->WKingCastle = FALSE;
 354                     }
 355                     else{
 356                         /* No change. */
 357                     }
 358                 }
 359             }
 360             else{
 361                 if(to_rank == LASTRANK){
 362                     if(to_col == FIRSTCOL){
 363                         board->BQueenCastle = FALSE;
 364                     }
 365                     else if(to_col == LASTCOL){
 366                         board->BKingCastle = FALSE;
 367                     }
 368                     else{
 369                         /* No change. */
 370                     }
 371                 }
 372             }
 373         }
 374         capture = TRUE;
 375     }
 376     /* Deal with the half-move clock. */
 377     if(capture || piece == PAWN) {
 378         board->halfmove_clock = 0;
 379     }
 380     else {
 381         board->halfmove_clock++;
 382     }
 383     /* Place the piece at its destination. */
 384     board->board[to_r][to_c] = MAKE_COLOURED_PIECE(colour,piece);
 385     /* Insert the moved piece into the hash value. */
 386     board->hash_value ^= HashLookup(to_col,to_rank,piece,colour);
 387 }
 388
 389         /* Find pawn moves matching the to_ and from_ information.
 390          * Depending on the input form of the move, some of this will be
 391          * incomplete.  For instance: e4 supplies just the to_ information
 392          * whereas cb supplies some from_ and some to_.
 393          */
 394 MovePair *
 395 find_pawn_moves(Col from_col, Rank from_rank, Col to_col,Rank to_rank,
 396                 Colour colour, const Board *board)
 397 {   short to_r = RankConvert(to_rank);
 398     short to_c = ColConvert(to_col);
 399     short from_r = RankConvert(from_rank);
 400     short from_c = ColConvert(from_col);
 401     MovePair *move_list = NULL;
 402     MovePair *move = NULL;
 403     /* White pawn moves are offset by +1, Black by -1. */
 404     short offset = COLOUR_OFFSET(colour);
 405     Piece piece_to_move = MAKE_COLOURED_PIECE(colour,PAWN);
 406
 407     if((to_col != 0) && (to_rank != 0)){
 408         /* We know the complete destination. */
 409         if(board->board[to_r][to_c] == EMPTY){
 410             /* Destination must be empty for this form. */
 411             if(board->board[to_r-offset][to_c] == piece_to_move){
 412                 /* MovePair of one square. */
 413                 move = append_move_pair(ToCol(to_c),ToRank(to_r-offset),
 414                                         to_col,to_rank,NULL);
 415             }
 416             else if((board->board[to_r-offset][to_c] == EMPTY) &&
 417                             (to_rank == (colour == WHITE?'4':'5'))){
 418                 /* Special case of initial two square move. */
 419                 if(board->board[to_r-2*offset][to_c] == piece_to_move){
 420                     move = append_move_pair(ToCol(to_c),ToRank(to_r-2*offset),
 421                                         to_col,to_rank,NULL);
 422                 }
 423             }
 424             else if(board->EnPassant &&
 425                         (board->ep_rank == to_rank) &&
 426                         (board->ep_col == to_col)){
 427                 /* Make sure that there is a valid pawn in position. */
 428                 if(from_col != 0){
 429                     from_r = to_r-offset;
 430                     if(board->board[from_r][from_c] == piece_to_move){
 431                         move = append_move_pair(ToCol(from_c),ToRank(from_r),
 432                                         to_col,ToRank(to_r),NULL);
 433                     }
 434                 }
 435             }
 436         }
 437         else if(piece_is_colour(board->board[to_r][to_c],OPPOSITE_COLOUR(colour))){
 438             /* Capture on the destination square. */
 439             if(from_col != 0){
 440                 /* We know the from column. */
 441                 from_r = to_r-offset;
 442                 if(board->board[from_r][from_c] == piece_to_move){
 443                     move = append_move_pair(ToCol(from_c),ToRank(from_r),
 444                                         to_col,to_rank,NULL);
 445                 }
 446             }
 447         }
 448         else{
 449             /* We have no move. */
 450             move = NULL;
 451         }
 452         move_list = move;
 453     }
 454     else if((from_col != 0) && (to_col != 0)){
 455         /* Should be a diagonal capture. */
 456         if(((from_col + 1) != to_col) && ((from_col - 1) != to_col)){
 457             /* Inconsistent information. */
 458         }
 459         else{
 460             if(from_rank != 0){
 461                 /* We have complete source information. Check its
 462                  * veracity.
 463                  */
 464                 to_r = from_r - offset;
 465                 if(board->board[from_r][from_c] == piece_to_move){
 466                     Piece occupant = board->board[to_r][to_c];
 467
 468                     if((occupant != EMPTY) &&
 469                             (piece_is_colour(occupant,OPPOSITE_COLOUR(colour)))){
 470                         move = append_move_pair(ToCol(from_c),ToRank(from_r),
 471                                         to_col,ToRank(to_r),NULL);
 472                     }
 473                     else if(board->EnPassant && (board->ep_rank == ToRank(to_r)) &&
 474                                     (board->ep_col == ToCol(to_c))){
 475                         move = append_move_pair(ToCol(from_c),ToRank(from_r),
 476                                         to_col,ToRank(to_r),NULL);
 477                     }
 478                 }
 479             }
 480             else{
 481                 /* We must search the from_col and to_col for appropriate
 482                  * combinations.  There may be more than one.
 483                  */
 484                 short start_rank, end_rank;
 485
 486                 /* Work out from where to start and end. */
 487                 if(colour == WHITE){
 488                     start_rank = RankConvert(FIRSTRANK+1);
 489                     end_rank = RankConvert(LASTRANK);
 490                 }
 491                 else{
 492                     start_rank = RankConvert(LASTRANK-1);
 493                     end_rank = RankConvert(FIRSTRANK);
 494                 }
 495                 for(from_r = start_rank; from_r != end_rank; from_r += offset){
 496                     to_r = from_r+offset;
 497                     if(board->board[from_r][from_c] == piece_to_move){
 498                         Piece occupant = board->board[to_r][to_c];
 499
 500                         if((occupant != EMPTY) &&
 501                                 (piece_is_colour(occupant,OPPOSITE_COLOUR(colour)))){
 502                             move_list = append_move_pair(ToCol(from_c),ToRank(from_r),
 503                                         to_col,ToRank(to_r),move_list);
 504                         }
 505                         else if(board->EnPassant && (board->ep_rank == ToRank(to_r)) &&
 506                                         (board->ep_col == ToCol(to_c))){
 507                             move_list = append_move_pair(ToCol(from_c),ToRank(from_r),
 508                                         to_col,ToRank(to_r),move_list);
 509                         }
 510                     }
 511                 }
 512             }
 513         }
 514     }
 515     return move_list;
 516 }
 517
 518         /* Find knight moves to the given square. */
 519 MovePair *
 520 find_knight_moves(Col to_col,Rank to_rank, Colour colour, const Board *board)
 521 {   short to_r = RankConvert(to_rank);
 522     short to_c = ColConvert(to_col);
 523     unsigned ix;
 524     MovePair *move_list = NULL;
 525     Piece target_piece =  MAKE_COLOURED_PIECE(colour,KNIGHT);
 526
 527     /* Pick up pairs of offsets from to_r,to_c to look for a Knight of
 528      * the right colour.
 529      */
 530     for(ix = 0; ix < 2*NUM_KNIGHT_MOVES; ix += 2){
 531         short r = Knight_moves[ix]+to_r;
 532         short c = Knight_moves[ix+1]+to_c;
 533
 534         if(board->board[r][c] == target_piece){
 535             move_list = append_move_pair(ToCol(c),ToRank(r),to_col,to_rank,move_list);
 536         }
 537     }
 538     return move_list;
 539 }
 540
 541         /* Find bishop moves to the given square. */
 542 MovePair *
 543 find_bishop_moves(Col to_col,Rank to_rank, Colour colour, const Board *board)
 544 {   short to_r = RankConvert(to_rank);
 545     short to_c = ColConvert(to_col);
 546     unsigned ix;
 547     MovePair *move_list = NULL;
 548     Piece target_piece =  MAKE_COLOURED_PIECE(colour,BISHOP);
 549
 550     /* Pick up pairs of offsets from to_r,to_c to look for a Bishop of
 551      * the right colour.
 552      */
 553     for(ix = 0; ix < 2*NUM_BISHOP_MOVES; ix += 2){
 554         short r = to_r, c = to_c;
 555
 556         /* Work backwards from the destination to find a bishop of
 557          * the right colour.
 558          */
 559         do{
 560             r += Bishop_moves[ix];
 561             c += Bishop_moves[ix+1];
 562         } while(board->board[r][c] == EMPTY);
 563
 564         if(board->board[r][c] == target_piece){
 565             move_list = append_move_pair(ToCol(c),ToRank(r),to_col,to_rank,move_list);
 566         }
 567     }
 568     return move_list;
 569 }
 570
 571         /* Find rook moves to the given square. */
 572 MovePair *
 573 find_rook_moves(Col to_col,Rank to_rank, Colour colour, const Board *board)
 574 {   short to_r = RankConvert(to_rank);
 575     short to_c = ColConvert(to_col);
 576     unsigned ix;
 577     MovePair *move_list = NULL;
 578     Piece target_piece = MAKE_COLOURED_PIECE(colour,ROOK);
 579
 580     /* Pick up pairs of offsets from to_r,to_c to look for a Rook of
 581      * the right colour.
 582      */
 583     for(ix = 0; ix < 2*NUM_ROOK_MOVES; ix += 2){
 584         short r = to_r, c = to_c;
 585
 586         /* Work backwards from the destination to find a rook of
 587          * the right colour.
 588          */
 589         do{
 590             r += Rook_moves[ix];
 591             c += Rook_moves[ix+1];
 592         } while(board->board[r][c] == EMPTY);
 593
 594         if(board->board[r][c] == target_piece){
 595             move_list = append_move_pair(ToCol(c),ToRank(r),to_col,to_rank,move_list);
 596         }
 597     }
 598     return move_list;
 599 }
 600
 601         /* Find queen moves to the given square. */
 602 MovePair *
 603 find_queen_moves(Col to_col,Rank to_rank, Colour colour, const Board *board)
 604 {   short to_r = RankConvert(to_rank);
 605     short to_c = ColConvert(to_col);
 606     unsigned ix;
 607     MovePair *move_list = NULL;
 608     Piece target_piece = MAKE_COLOURED_PIECE(colour,QUEEN);
 609
 610     /* Pick up pairs of offsets from to_r,to_c to look for a Knight of
 611      * the right colour.
 612      */
 613     for(ix = 0; ix < 2*NUM_QUEEN_MOVES; ix += 2){
 614         short r = to_r, c = to_c;
 615
 616         /* Work backwards from the destination to find a queen of
 617          * the right colour.
 618          */
 619         do{
 620             r += Queen_moves[ix];
 621             c += Queen_moves[ix+1];
 622         } while(board->board[r][c] == EMPTY);
 623
 624         if(board->board[r][c] == target_piece){
 625             move_list = append_move_pair(ToCol(c),ToRank(r),to_col,to_rank,move_list);
 626         }
 627     }
 628     return move_list;
 629 }
 630
 631         /* Find King moves to the given square. */
 632 MovePair *
 633 find_king_moves(Col to_col,Rank to_rank, Colour colour, const Board *board)
 634 {   short to_r = RankConvert(to_rank);
 635     short to_c = ColConvert(to_col);
 636     unsigned ix;
 637     MovePair *move_list = NULL;
 638     Piece target_piece = MAKE_COLOURED_PIECE(colour,KING);
 639
 640     /* Pick up pairs of offsets from to_r,to_c to look for a King of
 641      * the right colour.
 642      */
 643     for(ix = 0; ix < 2*NUM_KING_MOVES; ix += 2){
 644         short r = King_moves[ix]+to_r;
 645         short c = King_moves[ix+1]+to_c;
 646
 647         if(board->board[r][c] == target_piece){
 648             move_list = append_move_pair(ToCol(c),ToRank(r),to_col,to_rank,move_list);
 649         }
 650     }
 651     return move_list;
 652 }
 653
 654         /* Return true if the king of the given colour is
 655          * in check on the board, FALSE otherwise.
 656          */
 657 CheckStatus
 658 king_is_in_check(const Board *board,Colour king_colour)
 659 {   MovePair *replies = NULL;
 660     /* Assume that there is no check. */
 661     CheckStatus in_check = NOCHECK;
 662     Col king_col;
 663     Rank king_rank;
 664     Colour opponent_colour = OPPOSITE_COLOUR(king_colour);
 665
 666     /* Find out where the king is now. */
 667     if(king_colour == WHITE){
 668         king_col = board->WKingCol;
 669         king_rank = board->WKingRank;
 670     }
 671     else{
 672         king_col = board->BKingCol;
 673         king_rank = board->BKingRank;
 674     }
 675     /* Try and find one move that leaves this king in check.
 676      * There is probably an optimal order for these tests, but I haven't
 677      * tried to find it.
 678      */
 679     if((king_col != LASTCOL) &&
 680                 ((replies = find_pawn_moves(king_col+1,0,king_col,king_rank,
 681                                     opponent_colour,board)) != NULL)){
 682         /* King is in check from a pawn to its right. */
 683     }
 684     else if((king_col != FIRSTCOL) &&
 685                 ((replies = find_pawn_moves(king_col-1,0,king_col,king_rank,
 686                                     opponent_colour,board)) != NULL)){
 687         /* King is in check from a pawn. to its left */
 688     }
 689
 690     if(replies != NULL) {
 691         /* Already found a pawn move. */
 692     }
 693     else if((replies =
 694         find_knight_moves(king_col,king_rank,
 695                                     opponent_colour,board)) != NULL){
 696         /* King is in check from a knight. */
 697     }
 698     else if((replies =
 699         find_bishop_moves(king_col,king_rank,
 700                                     opponent_colour,board)) != NULL){
 701         /* King is in check from a bishop. */
 702     }
 703     else if((replies =
 704         find_rook_moves(king_col,king_rank,
 705                                     opponent_colour,board)) != NULL){
 706         /* King is in check from a rook. */
 707     }
 708     else if((replies =
 709         find_queen_moves(king_col,king_rank,
 710                                     opponent_colour,board)) != NULL){
 711         /* King is in check from a queen. */
 712     }
 713     else if((replies =
 714         find_king_moves(king_col,king_rank,
 715                                     opponent_colour,board)) != NULL){
 716         /* King is in check from a king. */
 717     }
 718     else{
 719         /* King is safe. */
 720     }
 721     if(replies != NULL){
 722        in_check = CHECK;
 723        free_move_pair_list(replies);
 724     }
 725     return in_check;
 726 }
 727
 728         /* possibles contains a list of possible moves of piece.
 729          * This function should exclude all of those moves of this piece
 730          * which leave its own king in check.  The list of remaining legal
 731          * moves is returned as result.
 732          * This function operates by looking for at least one reply by the
 733          * opponent that could capture the king of the given colour.
 734          * Only one such move needs to be found to invalidate one of the
 735          * possible moves.
 736          */
 737 MovePair *
 738 exclude_checks(Piece piece, Colour colour,MovePair *possibles, const Board *board)
 739 {   /* As this function is not called recursively, it should be
 740      * safe to retain a single copy of the board on the stack without risking
 741      * overflow. This has been a problem in the past with the PC version.
 742      */
 743     Board copy_board;
 744     MovePair *valid_move_list = NULL;
 745     MovePair *move;
 746
 747     /* For each possible move, make the move and see if it leaves the king
 748      * in check.
 749      */
 750     for(move = possibles; move != NULL; ){
 751         /* Take a copy of the board before playing this next move. */
 752         copy_board = *board;
 753         make_move(UNKNOWN_MOVE, move->from_col,move->from_rank,
 754                   move->to_col,move->to_rank,piece,colour,&copy_board);
 755         if(king_is_in_check(&copy_board,colour) != NOCHECK){
 756             MovePair *illegal_move = move;
 757
 758             move = move->next;
 759             /* Free the illegal move. */
 760             free_move_pair(illegal_move);
 761         }
 762         else{
 763             /* King is safe and the move may be kept. */
 764             MovePair *legal_move = move;
 765
 766             move = move->next;
 767             legal_move->next = valid_move_list;
 768             valid_move_list = legal_move;
 769         }
 770     }
 771     return valid_move_list;
 772 }
 773
 774     /* We must exclude the possibility of the king passing
 775      * through check, or castling out of it.
 776      */
 777 static Boolean
 778 exclude_castling_across_checks(MoveClass class, Colour colour, const Board *board)
 779 {   Boolean Ok = TRUE;
 780     MovePair *move = malloc_move();
 781     Rank rank = (colour == WHITE)? FIRSTRANK : LASTRANK;
 782     Col to_col;
 783
 784     if(class == KINGSIDE_CASTLE){
 785         /* Start where we are, because you can't castle out of check. */
 786         for(to_col = 'e'; (to_col <= 'g') && Ok; to_col++){
 787             move->from_col = 'e';
 788             move->from_rank = rank;
 789             move->to_col = to_col;
 790             move->to_rank = rank;
 791             move = exclude_checks(KING,colour,move,board);
 792             if(move == NULL){
 793                 Ok = FALSE;
 794             }
 795         }
 796     }
 797     else{
 798         /* Start where we are, because you can't castle out of check. */
 799         for(to_col = 'e'; (to_col <= 'c') && Ok; to_col--){
 800             move->from_col = 'e';
 801             move->from_rank = rank;
 802             move->to_col = to_col;
 803             move->to_rank = rank;
 804             move = exclude_checks(KING,colour,move,board);
 805             if(move == NULL){
 806                 Ok = FALSE;
 807             }
 808         }
 809     }
 810     if(move != NULL){
 811         free_move_pair(move);
 812     }
 813     return Ok;
 814 }
 815
 816         /* Possibles is a list of possible moves of piece.
 817          * Exclude all of those that either leave the king in check
 818          * or those excluded by non-null information in from_col or from_rank.
 819          */
 820 static MovePair *
 821 exclude_moves(Piece piece, Colour colour,Col from_col, Rank from_rank,
 822         MovePair *possibles, const Board *board)
 823 {   MovePair *move_list = NULL;
 824
 825     /* See if we have disambiguating from_ information. */
 826     if((from_col != 0) || (from_rank != 0)){
 827         MovePair *move, *temp;
 828
 829         for(move = possibles; move != NULL; ){
 830             Boolean excluded = FALSE;
 831
 832             if(from_col != 0){
 833                 /* The from_col is specified. */
 834                 if(move->from_col != from_col){
 835                     excluded = TRUE;
 836                 }
 837             }
 838             if((from_rank != 0) && !excluded){
 839                 if(move->from_rank != from_rank){
 840                     excluded = TRUE;
 841                 }
 842             }
 843             temp = move;
 844             move = move->next;
 845             if(!excluded){
 846                 /* Add it to the list of possibles. */
 847                 temp->next = move_list;
 848                 move_list = temp;
 849             }
 850             else{
 851                 /* Discard it. */
 852                 free_move_pair(temp);
 853             }
 854         }
 855     }
 856     else{
 857         /* Everything is still possible. */
 858         move_list = possibles;
 859     }
 860     if(move_list != NULL){
 861         move_list = exclude_checks(piece,colour,move_list,board);
 862     }
 863     return move_list;
 864 }
 865
 866         /* Make a pawn move.
 867          * En-passant information in the original move text is not currently used
 868          * to disambiguate pawn moves.  E.g. with Black pawns on c4 and c5 after
 869          * White move 1. d4 a reply 1... cdep will be rejected as ambiguous.
 870          */
 871 static Boolean
 872 pawn_move(Move *move_details, Colour colour, Board *board)
 873 {   Col from_col = move_details->from_col;
 874     Rank from_rank = move_details->from_rank;
 875     Col to_col = move_details->to_col;
 876     Rank to_rank = move_details->to_rank;
 877     /* Find the basic set of moves that match the move_details criteria. */
 878     MovePair *move_list;
 879     Boolean Ok = TRUE;
 880
 881     /* Make sure that the col values are consistent with a pawn move. */
 882     if((from_col != '\0') && (to_col != '\0') &&
 883             /* Forward. */
 884             (from_col != to_col) &&
 885             /* Capture. */
 886             (from_col != (to_col+1)) && (from_col != (to_col-1))){
 887         /* Inconsistent. */
 888         Ok = FALSE;
 889     }
 890     else if((move_list = find_pawn_moves(from_col,from_rank,to_col,to_rank,
 891                 colour,board)) == NULL){
 892         Ok = FALSE;
 893     }
 894     else{
 895         /* Exclude any moves that leave the king in check, or are disambiguate
 896          * by from_information.
 897          */
 898         move_list = exclude_moves(PAWN,colour,from_col,from_rank,move_list,board);
 899         if(move_list != NULL){
 900             if(move_list->next == NULL){
 901                 /* Unambiguous move. Some pawn moves will have supplied
 902                  * incomplete destinations (e.g. cd as opposed to cxd4)
 903                  * so pick up both from_ and to_ information.
 904                  */
 905                 move_details->from_col = move_list->from_col;
 906                 move_details->from_rank = move_list->from_rank;
 907                 move_details->to_col = move_list->to_col;
 908                 move_details->to_rank = move_list->to_rank;
 909             }
 910             else{
 911                 /* Ambiguous. */
 912                 Ok = FALSE;
 913             }
 914             free_move_pair_list(move_list);
 915         }
 916         else{
 917             /* Excluded. */
 918             Ok = FALSE;
 919         }
 920     }
 921     return Ok;
 922 }
 923
 924         /* Make a pawn move that involves an explicit promotion to promoted_piece. */
 925 static Boolean
 926 promote(Move *move_details, Colour colour, Board *board)
 927 {   Col from_col = move_details->from_col;
 928     Rank from_rank = move_details->from_rank;
 929     Col to_col = move_details->to_col;
 930     Rank to_rank = move_details->to_rank;
 931     MovePair *move_list;
 932     Boolean Ok = FALSE;
 933
 934     if(to_rank == '\0'){
 935         /* We can fill this in. */
 936         if(colour == WHITE){
 937             to_rank = LASTRANK;
 938         }
 939         else{
 940             to_rank = FIRSTRANK;
 941         }
 942     }
 943     /* Now check that to_rank makes sense for the given colour. */
 944     if(((colour == WHITE) && (to_rank != LASTRANK)) ||
 945             ((colour == BLACK) && (to_rank != FIRSTRANK))){
 946         fprintf(GlobalState.logfile,"Illegal pawn promotion to %c%c\n",to_col,to_rank);
 947     }
 948     else{
 949         move_list = find_pawn_moves(from_col,from_rank,to_col,to_rank,colour,board);
 950         if(move_list != NULL){
 951             if(move_list->next == NULL){
 952                 /* Unambiguous move. Some pawn moves will have supplied
 953                  * incomplete destinations (e.g. cd as opposed to cxd8)
 954                  * so pick up both from_ and to_ information.
 955                  */
 956                 move_details->from_col = move_list->from_col;
 957                 move_details->from_rank = move_list->from_rank;
 958                 move_details->to_col = move_list->to_col;
 959                 move_details->to_rank = move_list->to_rank;
 960                 Ok = TRUE;
 961             }
 962             else{
 963                 fprintf(GlobalState.logfile,"Ambiguous pawn move to %c%c\n",to_col,to_rank);
 964             }
 965             free_move_pair_list(move_list);
 966         }
 967         else{
 968             fprintf(GlobalState.logfile,"Illegal pawn promotion to %c%c\n",to_col,to_rank);
 969         }
 970     }
 971     return Ok;
 972 }
 973
 974         /* Make a knight move, indicated by move_details.
 975          * This may result in further information being added to move_details.
 976          */
 977 static Boolean
 978 knight_move(Move *move_details, Colour colour, Board *board)
 979 {   Col from_col = move_details->from_col;
 980     Rank from_rank = move_details->from_rank;
 981     Col to_col = move_details->to_col;
 982     Rank to_rank = move_details->to_rank;
 983     short to_r = RankConvert(to_rank);
 984     short to_c = ColConvert(to_col);
 985     MovePair *move_list = find_knight_moves(to_col,to_rank,colour,board);
 986     /* Assume everything will be ok. */
 987     Boolean Ok = TRUE;
 988
 989     move_list = exclude_moves(KNIGHT,colour,from_col,from_rank,move_list,board);
 990
 991     if(move_list == NULL){
 992         fprintf(GlobalState.logfile,"No knight move possible to %c%c.\n",to_col,to_rank);
 993         Ok = FALSE;
 994     }
 995     else if(move_list->next == NULL){
 996         /* Only one possible.  Check for legality. */
 997         Piece occupant = board->board[to_r][to_c];
 998
 999         if((occupant == EMPTY) || piece_is_colour(occupant,OPPOSITE_COLOUR(colour))){
1000             move_details->from_col = move_list->from_col;
1001             move_details->from_rank = move_list->from_rank;
1002         }
1003         else{
1004             fprintf(GlobalState.logfile,"Knight destination square %c%c is illegal.\n",
1005                                 to_col,to_rank);
1006             Ok = FALSE;
1007         }
1008         free_move_pair(move_list);
1009     }
1010     else{
1011         fprintf(GlobalState.logfile,"Ambiguous knight move to %c%c.\n",to_col,to_rank);
1012         free_move_pair_list(move_list);
1013         Ok = FALSE;
1014     }
1015     return Ok;
1016 }
1017
1018         /* Make a bishop move, indicated by move_details.
1019          * This may result in further information being added to move_details.
1020          */
1021 static Boolean
1022 bishop_move(Move *move_details, Colour colour, Board *board)
1023 {   Col from_col = move_details->from_col;
1024     Rank from_rank = move_details->from_rank;
1025     Col to_col = move_details->to_col;
1026     Rank to_rank = move_details->to_rank;
1027     short to_r = RankConvert(to_rank);
1028     short to_c = ColConvert(to_col);
1029     MovePair *move_list = find_bishop_moves(to_col,to_rank,colour,board);
1030     /* Assume that it is ok. */
1031     Boolean Ok = TRUE;
1032
1033     move_list = exclude_moves(BISHOP,colour,from_col,from_rank,move_list,board);
1034
1035     if(move_list == NULL){
1036         fprintf(GlobalState.logfile,"No bishop move possible to %c%c.\n",to_col,to_rank);
1037         Ok = FALSE;
1038     }
1039     else if(move_list->next == NULL){
1040         /* Only one possible.  Check for legality. */
1041         Piece occupant = board->board[to_r][to_c];
1042
1043         if((occupant == EMPTY) || piece_is_colour(occupant,OPPOSITE_COLOUR(colour))){
1044             move_details->from_col = move_list->from_col;
1045             move_details->from_rank = move_list->from_rank;
1046         }
1047         else{
1048             fprintf(GlobalState.logfile,"Bishop's destination square %c%c is illegal.\n",
1049                                 to_col,to_rank);
1050             Ok = FALSE;
1051         }
1052         free_move_pair(move_list);
1053     }
1054     else{
1055         fprintf(GlobalState.logfile,"Ambiguous bishop move to %c%c.\n",to_col,to_rank);
1056         free_move_pair_list(move_list);
1057         Ok = FALSE;
1058     }
1059     return Ok;
1060 }
1061
1062         /* Make a rook move, indicated by move_details.
1063          * This may result in further information being added to move_details.
1064          */
1065 static Boolean
1066 rook_move(Move *move_details, Colour colour, Board *board)
1067 {   Col from_col = move_details->from_col;
1068     Rank from_rank = move_details->from_rank;
1069     Col to_col = move_details->to_col;
1070     Rank to_rank = move_details->to_rank;
1071     short to_r = RankConvert(to_rank);
1072     short to_c = ColConvert(to_col);
1073     MovePair *move_list = find_rook_moves(to_col,to_rank,colour,board);
1074     /* Assume that it is ok. */
1075     Boolean Ok = TRUE;
1076
1077     if(move_list == NULL){
1078         fprintf(GlobalState.logfile,"No rook move possible to %c%c.\n",to_col,to_rank);
1079         Ok = FALSE;
1080     }
1081     else{
1082         move_list = exclude_moves(ROOK,colour,from_col,from_rank,move_list,board);
1083
1084         if(move_list == NULL){
1085             fprintf(GlobalState.logfile,"Indicated rook move is excluded.\n");
1086             Ok = FALSE;
1087         }
1088         else if(move_list->next == NULL){
1089             /* Only one possible.  Check for legality. */
1090             Piece occupant = board->board[to_r][to_c];
1091
1092             if((occupant == EMPTY) || piece_is_colour(occupant,OPPOSITE_COLOUR(colour))){
1093                 move_details->from_col = move_list->from_col;
1094                 move_details->from_rank = move_list->from_rank;
1095             }
1096             else{
1097                 fprintf(GlobalState.logfile,
1098                                     "Rook's destination square %c%c is illegal.\n",
1099                                     to_col,to_rank);
1100                 Ok = FALSE;
1101             }
1102             free_move_pair(move_list);
1103         }
1104         else{
1105             fprintf(GlobalState.logfile,"Ambiguous rook move to %c%c.\n",to_col,to_rank);
1106             free_move_pair_list(move_list);
1107             Ok = FALSE;
1108         }
1109     }
1110     return Ok;
1111 }
1112
1113         /* Find a queen move indicated by move_details.
1114          * This may result in further information being added to move_details.
1115          */
1116 static Boolean
1117 queen_move(Move *move_details, Colour colour, Board *board)
1118 {   Col from_col = move_details->from_col;
1119     Rank from_rank = move_details->from_rank;
1120     Col to_col = move_details->to_col;
1121     Rank to_rank = move_details->to_rank;
1122     short to_r = RankConvert(to_rank);
1123     short to_c = ColConvert(to_col);
1124     MovePair *move_list = find_queen_moves(to_col,to_rank,colour,board);
1125     /* Assume that it is ok. */
1126     Boolean Ok = TRUE;
1127
1128     move_list = exclude_moves(QUEEN,colour,from_col,from_rank,move_list,board);
1129
1130     if(move_list == NULL){
1131         fprintf(GlobalState.logfile,"No queen move possible to %c%c.\n",to_col,to_rank);
1132         Ok = FALSE;
1133     }
1134     else if(move_list->next == NULL){
1135         /* Only one possible.  Check for legality. */
1136         Piece occupant = board->board[to_r][to_c];
1137
1138         if((occupant == EMPTY) || piece_is_colour(occupant,OPPOSITE_COLOUR(colour))){
1139             move_details->from_col = move_list->from_col;
1140             move_details->from_rank = move_list->from_rank;
1141         }
1142         else{
1143             fprintf(GlobalState.logfile,"Queen's destination square %c%c is illegal.\n",
1144                                         to_col,to_rank);
1145             Ok = FALSE;
1146         }
1147         free_move_pair(move_list);
1148     }
1149     else{
1150         fprintf(GlobalState.logfile,"Ambiguous queen move to %c%c.\n",to_col,to_rank);
1151         free_move_pair_list(move_list);
1152         Ok = FALSE;
1153     }
1154     return Ok;
1155 }
1156
1157         /* Can colour castle kingside? */
1158 static Boolean
1159 can_castle_kingside(Colour colour, const Board *board)
1160 {   /* Assume failure. */
1161     Boolean Ok = FALSE;
1162     Rank king_rank;
1163
1164     if(colour == WHITE){
1165         king_rank = FIRSTRANK;
1166         Ok = board->WKingCastle;
1167     }
1168     else{
1169         king_rank = LASTRANK;
1170         Ok = board->BKingCastle;
1171     }
1172
1173     if(Ok){
1174         /* It is permitted. */
1175         short king_c = ColConvert('e');
1176         short king_r = RankConvert(king_rank);
1177         Piece coloured_king = MAKE_COLOURED_PIECE(colour,KING);
1178         Piece coloured_rook = MAKE_COLOURED_PIECE(colour,ROOK);
1179
1180         if((board->board[king_r][king_c] == coloured_king) &&
1181                 (board->board[king_r][king_c+1] == EMPTY) &&
1182                 (board->board[king_r][king_c+2] == EMPTY) &&
1183                 (board->board[king_r][king_c+3] == coloured_rook)){
1184             if(exclude_castling_across_checks(KINGSIDE_CASTLE,colour,board)){
1185                 Ok = TRUE;
1186             }
1187             else{
1188                 /* Can't castle across check. */
1189                 Ok = FALSE;
1190             }
1191
1192         }
1193         else{
1194             /* Kingside castling is blocked. */
1195             Ok = FALSE;
1196         }
1197     }
1198     else{
1199         /* Kingside castling is forbidden. */
1200     }
1201     return Ok;
1202 }
1203
1204         /* Can colour castle queenside? */
1205 static Boolean
1206 can_castle_queenside(Colour colour, const Board *board)
1207 {   /* Assume failure. */
1208     Boolean Ok = FALSE;
1209     Rank king_rank;
1210
1211     if(colour == WHITE){
1212         king_rank = FIRSTRANK;
1213         Ok = board->WQueenCastle;
1214     }
1215     else{
1216         king_rank = LASTRANK;
1217         Ok = board->BQueenCastle;
1218     }
1219
1220     if(Ok){
1221         /* It is permitted. */
1222         short king_c = ColConvert('e');
1223         short king_r = RankConvert(king_rank);
1224         Piece coloured_king = MAKE_COLOURED_PIECE(colour,KING);
1225         Piece coloured_rook = MAKE_COLOURED_PIECE(colour,ROOK);
1226
1227         if((board->board[king_r][king_c] == coloured_king) &&
1228                 (board->board[king_r][king_c-1] == EMPTY) &&
1229                 (board->board[king_r][king_c-2] == EMPTY) &&
1230                 (board->board[king_r][king_c-3] == EMPTY) &&
1231                 (board->board[king_r][king_c-4] == coloured_rook)){
1232             if(exclude_castling_across_checks(QUEENSIDE_CASTLE,colour,board)){
1233                 Ok = TRUE;
1234             }
1235             else{
1236                 /* Can't castle across check. */
1237                 Ok = FALSE;
1238             }
1239
1240         }
1241         else{
1242             /* Queenside castling is blocked. */
1243             Ok = FALSE;
1244         }
1245     }
1246     else{
1247         /* Queenside castling is forbidden. */
1248     }
1249     return Ok;
1250 }
1251
1252         /* Castle king side. */
1253 static Boolean
1254 kingside_castle(Move *move_details,Colour colour, Board *board)
1255 {   Boolean Ok;
1256
1257     if(can_castle_kingside(colour,board)){
1258         Rank rank = colour == WHITE?FIRSTRANK:LASTRANK;
1259
1260         move_details->from_col = 'e';
1261         move_details->from_rank = rank;
1262         move_details->to_col = 'g';
1263         move_details->to_rank = rank;
1264         Ok = TRUE;
1265     }
1266     else{
1267         fprintf(GlobalState.logfile,"Kingside castling is forbidden to %s.\n",
1268                         colour == WHITE?"White":"Black");
1269         Ok = FALSE;
1270     }
1271     return Ok;
1272 }
1273
1274 static Boolean
1275 queenside_castle(Move *move_details, Colour colour, Board *board)
1276 {   Boolean Ok;
1277
1278     if(can_castle_queenside(colour,board)){
1279         Rank rank = colour == WHITE?FIRSTRANK:LASTRANK;
1280
1281         move_details->from_col = 'e';
1282         move_details->from_rank = rank;
1283         move_details->to_col = 'c';
1284         move_details->to_rank = rank;
1285         Ok = TRUE;
1286     }
1287     else{
1288         fprintf(GlobalState.logfile,"Queenside castling is forbidden to %s.\n",
1289                         colour == WHITE?"White":"Black");
1290         Ok = FALSE;
1291     }
1292     return Ok;
1293 }
1294
1295         /* Move the king according to move_details.
1296          * This may result in further information being added to move_details.
1297          */
1298 static Boolean
1299 king_move(Move *move_details, Colour colour, Board *board)
1300 {   Col from_col = move_details->from_col;
1301     Rank from_rank = move_details->from_rank;
1302     Col to_col = move_details->to_col;
1303     Rank to_rank = move_details->to_rank;
1304     short to_r = RankConvert(to_rank);
1305     short to_c = ColConvert(to_col);
1306     /* Find all possible king moves to the destination squares. */
1307     MovePair *move_list = find_king_moves(to_col,to_rank,colour,board);
1308     /* Assume that it is ok. */
1309     Boolean Ok = TRUE;
1310
1311     /* Exclude disambiguated and illegal moves. */
1312     move_list = exclude_moves(KING,colour,from_col,from_rank,move_list,board);
1313
1314     if(move_list == NULL){
1315         fprintf(GlobalState.logfile,"No king move possible to %c%c.\n",to_col,to_rank);
1316         Ok = FALSE;
1317     }
1318     else if(move_list->next == NULL){
1319         /* Only one possible.  Check for legality. */
1320         Piece occupant = board->board[to_r][to_c];
1321
1322         if((occupant == EMPTY) || piece_is_colour(occupant,OPPOSITE_COLOUR(colour))){
1323             move_details->from_col = move_list->from_col;
1324             move_details->from_rank = move_list->from_rank;
1325         }
1326         else{
1327             fprintf(GlobalState.logfile,"King's destination square %c%c is illegal.\n",
1328                                 to_col,to_rank);
1329             Ok = FALSE;
1330         }
1331         free_move_pair(move_list);
1332     }
1333     else{
1334         fprintf(GlobalState.logfile,
1335                         "Ambiguous king move possible to %c%c.\n",to_col,to_rank);
1336         fprintf(GlobalState.logfile,"Multiple kings?!\n");
1337         free_move_pair_list(move_list);
1338         Ok = FALSE;
1339     }
1340     return Ok;
1341 }
1342
1343         /* Try to complete the full set of move information for
1344          * move details.
1345          * In the process, several fields of move_details are modified
1346          * as accurate information is determined about the effect of the move.
1347          * The from_ and to_ fields are completed, class may be refined, and
1348          * captured_piece is filled in.  The purpose of this is to make it
1349          * possible to call apply_move with a full set of information on the
1350          * move.  In addition, once determine_move_details has done its job,
1351          * it should be possible to use the information to reconstruct the effect
1352          * of a move in reverse, if necessary.  This would be required by a display
1353          * program, for instance.
1354          * NB: this function does not determine whether or not the move gives check.
1355          */
1356 Boolean
1357 determine_move_details(Colour colour,Move *move_details, Board *board)
1358 {   Boolean Ok = FALSE;
1359
1360     if(move_details == NULL){
1361         /* Shouldn't happen. */
1362         fprintf(GlobalState.logfile,
1363                 "Internal error: Empty move details in apply_move.\n");
1364     }
1365     else if(move_details->move[0] == '\0'){
1366         /* Shouldn't happen. */
1367         fprintf(GlobalState.logfile,
1368                 "Internal error: Null move string in apply_move.\n");
1369     }
1370     else if(move_details->class == NULL_MOVE) {
1371         /* Non-standard PGN.
1372          * Nothing more to be done.
1373          */
1374         Ok = TRUE;
1375     }
1376     else{
1377         /* We have something -- normal case. */
1378         const unsigned char *move = move_details->move;
1379         MoveClass class = move_details->class;
1380         Boolean move_handled = FALSE;
1381
1382         /* A new piece on promotion. */
1383         move_details->promoted_piece = EMPTY;
1384
1385         /* Because the decoding process did not have the current board
1386          * position available, trap apparent pawn moves that maybe something
1387          * else.
1388          * At the moment, only do this when full positional information is
1389          * available.
1390          */
1391         if((class == PAWN_MOVE) &&
1392                 (move_details->from_col != 0) &&
1393                        (move_details->from_rank != 0) &&
1394                        (move_details->to_col != 0) &&
1395                        (move_details->to_rank != 0)){
1396             /* Try to work out its details and handle it below. */
1397             move_details = decode_algebraic(move_details,board);
1398             /* Pick up the new class. */
1399             class = move_details->class;
1400         }
1401
1402         /* Deal with apparent pawn moves first. */
1403         if((class == PAWN_MOVE) || (class == ENPASSANT_PAWN_MOVE) ||
1404                         (class == PAWN_MOVE_WITH_PROMOTION)){
1405             move_details->piece_to_move = PAWN;
1406             /* Fill in any promotional details. */
1407             if(class == PAWN_MOVE){
1408                 /* Check for implicit promotion. */
1409                 if(((move_details->to_rank == LASTRANK) && (colour == WHITE)) ||
1410                         ((move_details->to_rank == FIRSTRANK) && (colour == BLACK))){
1411                     /* Don't modify move_details->class as we are not
1412                      * adding the new piece to the move string.
1413                      */
1414                     class = PAWN_MOVE_WITH_PROMOTION;
1415                     /* Since the move string doesn't tell us, we have to
1416                      * assume a queen.
1417                      */
1418                     move_details->promoted_piece = QUEEN;
1419                 }
1420             }
1421             else if(class == ENPASSANT_PAWN_MOVE){
1422                 /* No promotion possible. */
1423             }
1424             else{
1425                 /* Pick up the promoted_piece from the move string. */
1426                 size_t last_char = strlen((const char *)move)-1;
1427
1428                 /* Skip any check character. */
1429                 while(is_check(move[last_char])){
1430                     last_char--;
1431                 }
1432                 /* Pick up what kind of piece it is. */
1433                 move_details->promoted_piece = is_piece(&move[last_char]);
1434                 switch(move_details->promoted_piece){
1435                     case QUEEN: case ROOK: case BISHOP: case KNIGHT:
1436                         /* Ok. */
1437                         break;
1438                     default:
1439                         fprintf(GlobalState.logfile,
1440                                     "Unknown piece in promotion %s\n",move);
1441                         move_details->promoted_piece = EMPTY;
1442                         break;
1443                 }
1444             }
1445             if((class == PAWN_MOVE) || (class == ENPASSANT_PAWN_MOVE)){
1446                 /* Check out the details and confirm the move's class. */
1447                 Ok = pawn_move(move_details,colour,board);
1448                 /* See if we are dealing with and En Passant move. */
1449                 if(Ok){
1450                     if((board->EnPassant) &&
1451                             (board->ep_rank == move_details->to_rank) &&
1452                             (board->ep_col == move_details->to_col)){
1453                         move_details->class = class = ENPASSANT_PAWN_MOVE;
1454                     }
1455                     else{
1456                         /* Just in case the original designation was incorrect. */
1457                         move_details->class = class = PAWN_MOVE;
1458                     }
1459                     move_handled = TRUE;
1460                 }
1461             }
1462             else if (class == PAWN_MOVE_WITH_PROMOTION){
1463                 /* Handle a move involving promotion. */
1464                 Ok = promote(move_details,colour,board);
1465                 move_handled = TRUE;
1466             }
1467             else{
1468                 /* Shouldn't get here. */
1469             }
1470             if(!move_handled){
1471                 /* We failed to find the move, for some reason. */
1472                 /* See if it might be a Bishop move with a lower case 'b'. */
1473                 if(move_details->move[0] == 'b'){
1474                     /* See if we can find an valid Bishop alternative for it. */
1475                     unsigned char alternative_move[MAX_MOVE_LEN+1];
1476                     Move *alternative;
1477
1478                     strcpy((char *) alternative_move,
1479                            (const char *)move_details->move);
1480                     *alternative_move = 'B';
1481                     alternative = decode_move((unsigned char *) alternative_move);
1482                     if(alternative != NULL){
1483                         Ok = bishop_move(alternative,colour,board);
1484                         if(Ok){
1485                             /* Copy the relevant details. */
1486                             move_details->class = alternative->class;
1487                             move_details->from_col = alternative->from_col;
1488                             move_details->from_rank = alternative->from_rank;
1489                             move_details->to_col = alternative->to_col;
1490                             move_details->to_rank = alternative->to_rank;
1491                             move_details->piece_to_move =
1492                                         alternative->piece_to_move;
1493                             free_move_list(alternative);
1494                             move_handled = TRUE;
1495                         }
1496                     }
1497                 }
1498             }
1499         }
1500         if(!move_handled){
1501           /* Pick up any moves not handled as pawn moves.
1502            * This includes algebraic moves that were originally assumed to
1503            * be pawn moves.
1504            */
1505           switch(class){
1506             case PAWN_MOVE:
1507             case ENPASSANT_PAWN_MOVE:
1508             case PAWN_MOVE_WITH_PROMOTION:
1509                 /* No more tries left. */
1510                 break;
1511             case PIECE_MOVE:
1512                 switch(move_details->piece_to_move){
1513                     case KING:
1514                         Ok = king_move(move_details,colour,board);
1515                         break;
1516                     case QUEEN:
1517                         Ok = queen_move(move_details,colour,board);
1518                         break;
1519                     case ROOK:
1520                         Ok = rook_move(move_details,colour,board);
1521                         break;
1522                     case KNIGHT:
1523                         Ok = knight_move(move_details,colour,board);
1524                         break;
1525                     case BISHOP:
1526                         Ok = bishop_move(move_details,colour,board);
1527                         break;
1528                     default:
1529                         Ok = FALSE;
1530                         fprintf(GlobalState.logfile,"Unknown piece move %s\n",move);
1531                         break;
1532                 }
1533                 break;
1534             case KINGSIDE_CASTLE:
1535                 move_details->piece_to_move = KING;
1536                 Ok = kingside_castle(move_details,colour,board);
1537                 break;
1538             case QUEENSIDE_CASTLE:
1539                 move_details->piece_to_move = KING;
1540                 Ok = queenside_castle(move_details,colour,board);
1541                 break;
1542             case UNKNOWN_MOVE:
1543                 Ok = FALSE;
1544                 break;
1545             default:
1546                 fprintf(GlobalState.logfile,
1547                         "Unknown move class in determine_move_details(%d).\n",
1548                                 move_details->class);
1549                 break;
1550           }
1551         }
1552         if(Ok){
1553             /* Fill in the remaining items in move_details. */
1554             short to_r = RankConvert(move_details->to_rank);
1555             short to_c = ColConvert(move_details->to_col);
1556
1557             /* Keep track of any capture. */
1558             if(board->board[to_r][to_c] != EMPTY){
1559                 move_details->captured_piece =
1560                                 EXTRACT_PIECE(board->board[to_r][to_c]);
1561             }
1562             else if(move_details->class == ENPASSANT_PAWN_MOVE){
1563                 move_details->captured_piece = PAWN;
1564             }
1565             else{
1566                 move_details->captured_piece = EMPTY;
1567             }
1568         }
1569     }
1570     return Ok;
1571 }
1572
1573     /* Generate a list of moves of a king or knight from from_col,from_rank.
1574      * This does not include castling for the king, because it is used
1575      * by the code that looks for ways to escape from check for which
1576      * castling is illegal, of course.
1577      */
1578 static MovePair *
1579 GenerateSingleMoves(Colour colour,Piece piece,
1580                     const Board *board,Col from_col, Rank from_rank)
1581 {   short from_r = RankConvert(from_rank);
1582     short from_c = ColConvert(from_col);
1583     unsigned ix;
1584     MovePair *moves = NULL;
1585     Colour target_colour = OPPOSITE_COLOUR(colour);
1586     unsigned num_directions = piece == KING?NUM_KING_MOVES:NUM_KNIGHT_MOVES;
1587     const short *Piece_moves = piece == KING?King_moves:Knight_moves;
1588
1589     /* Pick up pairs of offsets from from_r,from_c to look for an
1590      * EMPTY square, or one containing a piece of OPPOSITE_COLOUR(colour).
1591      */
1592     for(ix = 0; ix < 2*num_directions; ix += 2){
1593         short r = Piece_moves[ix]+from_r;
1594         short c = Piece_moves[ix+1]+from_c;
1595         Piece occupant = board->board[r][c];
1596         Boolean Ok = FALSE;
1597
1598         if(occupant == OFF){
1599             /* Not a valid move. */
1600         }
1601         else if(board->board[r][c] == EMPTY){
1602             Ok = TRUE;
1603         }
1604         else if(EXTRACT_COLOUR(occupant) == target_colour){
1605             Ok = TRUE;
1606         }
1607         else{
1608         }
1609         if(Ok){
1610             /* Fill in the details, and add it to the list. */
1611             moves = append_move_pair(from_col,from_rank,ToCol(c),ToRank(r),moves);
1612         }
1613     }
1614     if(moves != NULL){
1615         moves = exclude_checks(piece,colour,moves,board);
1616     }
1617     return moves;
1618 }
1619
1620         /* Generate a list of moves of a queen, rook or bishop from
1621          * from_col,from_rank.
1622          */
1623 static MovePair *
1624 GenerateMultipleMoves(Colour colour,Piece piece,
1625                 const Board *board,Col from_col, Rank from_rank)
1626 {   short from_r = RankConvert(from_rank);
1627     short from_c = ColConvert(from_col);
1628     unsigned ix;
1629     MovePair *moves = NULL;
1630     Colour target_colour = OPPOSITE_COLOUR(colour);
1631     unsigned num_directions = piece == QUEEN?NUM_QUEEN_MOVES:
1632                                 piece == ROOK?NUM_ROOK_MOVES:NUM_BISHOP_MOVES;
1633     const short *Piece_moves = piece == QUEEN?Queen_moves:
1634                                 piece == ROOK?Rook_moves:Bishop_moves;
1635
1636     /* Pick up pairs of offsets from from_r,from_c to look for an
1637      * EMPTY square, or one containing a piece of OPPOSITE_COLOUR(colour).
1638      */
1639     for(ix = 0; ix < 2*num_directions; ix += 2){
1640         short r = Piece_moves[ix]+from_r;
1641         short c = Piece_moves[ix+1]+from_c;
1642         Piece occupant = board->board[r][c];
1643
1644         /* Include EMPTY squares as possible moves. */
1645         while(occupant == EMPTY){
1646             /* Fill in the details, and add it to the list. */
1647             moves = append_move_pair(from_col,from_rank,ToCol(c),ToRank(r),moves);
1648             /* Move on to the next square in this direction. */
1649             r += Piece_moves[ix];
1650             c += Piece_moves[ix+1];
1651             occupant = board->board[r][c];
1652         }
1653         /* We have come up against an obstruction. */
1654         if(occupant == OFF){
1655             /* Not a valid move. */
1656         }
1657         else if(EXTRACT_COLOUR(occupant) == target_colour){
1658             moves = append_move_pair(from_col,from_rank,ToCol(c),ToRank(r),moves);
1659         }
1660         else{
1661             /* Should be a piece of our own colour. */
1662         }
1663     }
1664     if(moves != NULL){
1665         moves = exclude_checks(piece,colour,moves,board);
1666     }
1667     return moves;
1668 }
1669
1670         /* Generate a list of moves of a pawn from from_col,from_rank. */
1671 static MovePair *
1672 GeneratePawnMoves(Colour colour,const Board *board,Col from_col, Rank from_rank)
1673 {   MovePair *moves = NULL;
1674     Piece piece = PAWN;
1675     Colour target_colour = OPPOSITE_COLOUR(colour);
1676     /* Determine the direction in which a pawn can move. */
1677     short offset = colour == WHITE? 1 : -1;
1678     short to_r, to_c = ColConvert(from_col);
1679
1680     /* Try single step ahead. */
1681     to_r = RankConvert(from_rank)+offset;
1682     if(board->board[to_r][to_c] == EMPTY){
1683         /* Fill in the details, and add it to the list. */
1684         moves = append_move_pair(from_col,from_rank,ToCol(to_c),ToRank(to_r),moves);
1685         if(((colour == WHITE) && (from_rank == FIRSTRANK+1)) ||
1686                ((colour == BLACK) && (from_rank == LASTRANK-1))){
1687            /* Try two steps. */
1688            to_r = RankConvert(from_rank)+2*offset;
1689             if(board->board[to_r][to_c] == EMPTY){
1690                 moves = append_move_pair(from_col,from_rank,ToCol(to_c),ToRank(to_r),moves);
1691             }
1692         }
1693     }
1694     /* Try to left. */
1695     to_r = RankConvert(from_rank)+offset;
1696     to_c = ColConvert(from_col)-1;
1697     if(board->board[to_r][to_c] == OFF){
1698     }
1699     else if(board->board[to_r][to_c] == EMPTY){
1700         if(board->EnPassant && (ToRank(to_r) == board->ep_rank) &&
1701                         (ToCol(to_c) == board->ep_col)){
1702             moves = append_move_pair(from_col,from_rank,ToCol(to_c),ToRank(to_r),moves);
1703         }
1704     }
1705     else if(EXTRACT_COLOUR(board->board[to_r][to_c]) == target_colour){
1706         moves = append_move_pair(from_col,from_rank,ToCol(to_c),ToRank(to_r),moves);
1707     }
1708     else{
1709     }
1710
1711     /* Try to right. */
1712     to_r = RankConvert(from_rank)+offset;
1713     to_c = ColConvert(from_col)+1;
1714     if(board->board[to_r][to_c] == OFF){
1715     }
1716     else if(board->board[to_r][to_c] == EMPTY){
1717         if(board->EnPassant && (ToRank(to_r) == board->ep_rank) &&
1718                         (ToCol(to_c) == board->ep_col)){
1719             moves = append_move_pair(from_col,from_rank,ToCol(to_c),ToRank(to_r),moves);
1720         }
1721     }
1722     else if(EXTRACT_COLOUR(board->board[to_r][to_c]) == target_colour){
1723         moves = append_move_pair(from_col,from_rank,ToCol(to_c),ToRank(to_r),moves);
1724     }
1725     else{
1726     }
1727
1728     if(moves != NULL){
1729         moves = exclude_checks(piece,colour,moves,board);
1730     }
1731     return moves;
1732 }
1733
1734         /* See whether the king of the given colour is in checkmate.
1735          * Assuming that the king is in check, generate all possible moves
1736          * for colour on board until at least one saving move is found.
1737          * Excepted from this are the castling moves (not legal whilst in check)
1738          * and underpromotions (inadequate in thwarting a check).
1739          */
1740 Boolean
1741 king_is_in_checkmate(Colour colour,Board *board)
1742 {  Rank rank;
1743    Col col;
1744    MovePair *moves = NULL;
1745    Boolean in_checkmate = FALSE;
1746
1747    /* Search the board for pieces of the right colour.
1748     * Keep going until we have exhausted all pieces, or until
1749     * we have found a saving move.
1750     */
1751    for(rank = LASTRANK; (rank >= FIRSTRANK) && (moves == NULL); rank--){
1752        for(col = FIRSTCOL; (col <= LASTCOL) && (moves == NULL); col++){
1753            short r = RankConvert(rank);
1754            short c = ColConvert(col);
1755            Piece occupant = board->board[r][c];
1756
1757            if((occupant != EMPTY) && (colour == EXTRACT_COLOUR(occupant))){
1758                /* This square is occupied by a piece of the required colour. */
1759                Piece piece = EXTRACT_PIECE(occupant);
1760
1761                switch(piece){
1762                    case KING:
1763                    case KNIGHT:
1764                        moves = GenerateSingleMoves(colour,piece,board,col,rank);
1765                        break;
1766                    case QUEEN:
1767                    case ROOK:
1768                    case BISHOP:
1769                        moves = GenerateMultipleMoves(colour,piece,board,col,rank);
1770                        break;
1771                    case PAWN:
1772                        moves = GeneratePawnMoves(colour,board,col,rank);
1773                        break;
1774                    default:
1775                        fprintf(GlobalState.logfile,
1776                            "Internal error: unknown piece %d in king_is_in_checmate().\n",
1777                                piece);
1778                 }
1779            }
1780        }
1781    }
1782    if(moves != NULL){
1783         /* No checkmate.  Free the move list. */
1784         free_move_pair_list(moves);
1785    }
1786    else{
1787        in_checkmate = TRUE;
1788    }
1789    return in_checkmate;
1790 }
1791
1792 #if INCLUDE_UNUSED_FUNCTIONS
1793
1794         /* Return an approximation of how many moves there are for
1795          * board->to_move on board.
1796          * This may be exact, but I haven't checked.
1797          * This is not currently used, but I found it useful at one
1798          * point for generating game statistics.
1799          */
1800 static unsigned
1801 approx_how_many_moves(Board *board)
1802 {  Rank rank;
1803    Col col;
1804    Colour colour = board->to_move;
1805    unsigned num_moves = 0;
1806
1807    /* Search the board for pieces of the right colour.
1808     * Keep going until we have exhausted all pieces, or until
1809     * we have found a saving move.
1810     */
1811    for(rank = LASTRANK; rank >= FIRSTRANK; rank--){
1812        for(col = FIRSTCOL; col <= LASTCOL; col++){
1813            short r = RankConvert(rank);
1814            short c = ColConvert(col);
1815            Piece occupant = board->board[r][c];
1816            MovePair *moves = NULL;
1817
1818            if((occupant != EMPTY) && (colour == EXTRACT_COLOUR(occupant))){
1819                /* This square is occupied by a piece of the required colour. */
1820                Piece piece = EXTRACT_PIECE(occupant);
1821
1822                switch(piece){
1823                    case KING:
1824                    case KNIGHT:
1825                        moves = GenerateSingleMoves(colour,piece,board,col,rank);
1826                        break;
1827                    case QUEEN:
1828                    case ROOK:
1829                    case BISHOP:
1830                        moves = GenerateMultipleMoves(colour,piece,board,col,rank);
1831                        break;
1832                    case PAWN:
1833                        moves = GeneratePawnMoves(colour,board,col,rank);
1834                        break;
1835                    default:
1836                        fprintf(GlobalState.logfile,
1837                            "Internal error: unknown piece %d in king_is_in_checmate().\n",
1838                                piece);
1839                 }
1840                if(moves != NULL){
1841                     /* At least one move. */
1842                     MovePair *m;
1843                     for(m = moves; m != NULL; m = m->next){
1844                         num_moves++;
1845                     }
1846                     /* Free the move list. */
1847                     free_move_pair_list(moves);
1848                }
1849            }
1850        }
1851    }
1852    return num_moves;
1853 }
1854 #endif
1855
1856         /* Find all moves for colour board. */
1857 MovePair *
1858 find_all_moves(const Board *board, Colour colour)
1859 {  Rank rank;
1860    Col col;
1861    /* All moves for colour. */
1862    MovePair *all_moves = NULL;
1863
1864    /* Pick up each piece of the required colour. */
1865    for(rank = LASTRANK; rank >= FIRSTRANK; rank--){
1866        short r = RankConvert(rank);
1867        for(col = FIRSTCOL; col <= LASTCOL; col++){
1868            short c = ColConvert(col);
1869            Piece occupant = board->board[r][c];
1870
1871            if((occupant != EMPTY) && (colour == EXTRACT_COLOUR(occupant))){
1872                /* This square is occupied by a piece of the required colour. */
1873                Piece piece = EXTRACT_PIECE(occupant);
1874                    /* List of moves for this piece. */
1875                    MovePair *moves = NULL;
1876
1877                switch(piece){
1878                    case KING:
1879                        moves = GenerateSingleMoves(colour,piece,board,col,rank);
1880                        /* Add any castling, as this is not covered
1881                         * by GenerateSingleMoves.
1882                         */
1883                        if(can_castle_kingside(colour,board)){
1884                            MovePair *m = (MovePair *)
1885                                    MallocOrDie(sizeof(MovePair));
1886                            m->from_col = 'e';
1887                            m->from_rank = rank;
1888                            m->to_col = 'g';
1889                            m->to_rank = rank;
1890                            /* Prepend. */
1891                            m->next = moves;
1892                            moves = m;
1893                        }
1894                        if(can_castle_queenside(colour,board)){
1895                            MovePair *m = (MovePair *)
1896                                    MallocOrDie(sizeof(MovePair));
1897                            m->from_col = 'e';
1898                            m->from_rank = rank;
1899                            m->to_col = 'c';
1900                            m->to_rank = rank;
1901                            /* Prepend. */
1902                            m->next = moves;
1903                            moves = m;
1904                        }
1905                        break;
1906                    case KNIGHT:
1907                        moves = GenerateSingleMoves(colour,piece,board,col,rank);
1908                        break;
1909                    case QUEEN:
1910                    case ROOK:
1911                    case BISHOP:
1912                        moves = GenerateMultipleMoves(colour,piece,board,col,rank);
1913                        break;
1914                    case PAWN:
1915                        moves = GeneratePawnMoves(colour,board,col,rank);
1916                        break;
1917                    default:
1918                        fprintf(GlobalState.logfile,
1919                            "Internal error: unknown piece %d in king_is_in_checmate().\n",
1920                                piece);
1921                 }
1922                if(moves != NULL){
1923                     /* At least one move.
1924                      * Append what we have so far to this list.
1925                      * Find the last one.
1926                      */
1927                     MovePair *m;
1928                     for(m = moves; m->next != NULL; m = m->next){
1929                     }
1930                     m->next = all_moves;
1931                     all_moves = moves;
1932                }
1933            }
1934        }
1935    }
1936    return all_moves;
1937 }
1938