git.sesse.net Git - pgn-extract/blob - apply.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 <ctype.h>
  27 #include "bool.h"
  28 #include "mymalloc.h"
  29 #include "defs.h"
  30 #include "typedef.h"
  31 #include "map.h"
  32 #include "apply.h"
  33 #include "tokens.h"
  34 #include "taglist.h"
  35 #include "output.h"
  36 #include "lex.h"
  37 #include "grammar.h"
  38 #include "moves.h"
  39 #include "eco.h"
  40 #include "decode.h"
  41 #include "hashing.h"
  42 #include "fenmatcher.h"
  43
  44 /* Define a positional search depth that should look at the
  45  * full length of a game.  This is used in play_moves().
  46  */
  47 #define DEFAULT_POSITIONAL_DEPTH 300
  48
  49         /* Prototypes of functions limited to this file. */
  50 static Boolean position_matches(const Board *board);
  51 static Boolean play_moves(Game *game_details, Board *board, Move *moves,
  52                 unsigned max_depth, Boolean check_move_validity);
  53 static Boolean apply_variations(const Game *game_details,const Board *board,
  54                                 Variation *variation, Boolean check_move_validity);
  55 static Boolean rewrite_variations(const Board *board,Variation *variation, Boolean null_move_found);
  56 static Boolean rewrite_moves(Board *board, Move *move_details, Boolean null_move_found);
  57 static void append_evaluation(Move *move_details, const Board *board);
  58 static void append_FEN_comment(Move *move_details, const Board *board);
  59 static double evaluate(const Board *board);
  60 static double shannonEvaluation(const Board *board);
  61
  62         /* The English SAN piece characters. These are
  63          * always used when building a FEN string, rather
  64          * than using any language-dependent user settings.
  65          */
  66 static char SAN_piece_characters[NUM_PIECE_VALUES] = {
  67     '?', '?',
  68     'P', 'N', 'B', 'R', 'Q', 'K'
  69 };
  70
  71
  72     /* These letters may be changed via a call to set_output_piece_characters
  73      * with a string of the form "PNBRQK".
  74      * This would normally be done with the -Wsan argument.
  75      */
  76 static const char *output_piece_characters[NUM_PIECE_VALUES] = {
  77     "?", "?",
  78     "P", "N", "B", "R", "Q", "K"
  79 };
  80
  81     /* letters should contain a string of the form: "PNBRQK" */
  82 void set_output_piece_characters(const char *letters)
  83 {
  84     if(letters == NULL){
  85         fprintf(GlobalState.logfile,
  86                 "NULL string passed to set_output_piece_characters.\n");
  87     }
  88     else{
  89         Piece piece;
  90         int piece_index;
  91         for(piece_index = 0, piece = PAWN; piece <= KING &&
  92                                            letters[piece_index] != '\0'; piece++){
  93             /* Check whether we have a single character piece,
  94              * or one of the form X+Y, where the piece is represented
  95              * by the combination XY.
  96              */
  97             if(letters[piece_index+1] == '+'){
  98                 /* A two-char piece. */
  99                 static char double_char_piece[] = "XY";
 100                 double_char_piece[0] = letters[piece_index];
 101                 piece_index++;
 102                 /* Skip the plus. */
 103                 piece_index++;
 104                 if(letters[piece_index] != '\0'){
 105                     double_char_piece[1] = letters[piece_index];
 106                     output_piece_characters[piece] = copy_string(double_char_piece);
 107                     piece_index++;
 108                 }
 109                 else{
 110                     fprintf(GlobalState.logfile,
 111                             "Missing piece letter following + in -Wsan%s.\n",
 112                             letters);
 113                     exit(1);
 114                 }
 115             }
 116             else{
 117                 static char single_char_piece[] = "X";
 118                 *single_char_piece = letters[piece_index];
 119                 output_piece_characters[piece] = copy_string(single_char_piece);
 120                 piece_index++;
 121             }
 122         }
 123         if(piece < NUM_PIECE_VALUES){
 124             fprintf(GlobalState.logfile,
 125                     "Insufficient piece letters found with -Wsan%s.\n",
 126                     letters);
 127             fprintf(GlobalState.logfile,
 128                     "The argument should be of the form -Wsan%s.\n",
 129                     "PNBRQK");
 130             exit(1);
 131         }
 132         else if(letters[piece_index] != '\0'){
 133             fprintf(GlobalState.logfile,
 134                     "Too many piece letters found with -Wsan%s.\n",
 135                     letters);
 136             fprintf(GlobalState.logfile,
 137                     "The argument should be of the form -Wsan%s.\n",
 138                     "PNBRQK");
 139             exit(1);
 140         }
 141         else{
 142             /* Ok. */
 143         }
 144     }
 145 }
 146
 147       /* Return a fresh copy of the given string. */
 148 char *
 149 copy_string(const char *str)
 150 {   char *result;
 151     size_t len = strlen(str);
 152
 153     result = MallocOrDie(len+1);
 154     strcpy(result,str);
 155     return result;
 156 }
 157
 158         /* Allocate space for a new board. */
 159 static Board *
 160 allocate_new_board(void)
 161 {
 162     return (Board *) MallocOrDie(sizeof(Board));
 163 }
 164
 165         /* Free the board space. */
 166 static void
 167 free_board(Board *board)
 168 {
 169     (void) free((void *)board);
 170 }
 171
 172 static Piece
 173 is_FEN_piece(char c)
 174 {   Piece piece = EMPTY;
 175
 176     switch(c){
 177         case 'K': case 'k':
 178             piece = KING;
 179             break;
 180         case 'Q': case 'q':
 181             piece = QUEEN;
 182             break;
 183         case 'R': case 'r':
 184             piece = ROOK;
 185             break;
 186         case 'N': case 'n':
 187             piece = KNIGHT;
 188             break;
 189         case 'B': case 'b':
 190             piece = BISHOP;
 191             break;
 192         case 'P': case 'p':
 193             piece = PAWN;
 194             break;
 195     }
 196     return piece;
 197 }
 198
 199         /* Return the SAN letter associated with the given piece. */
 200 char
 201 SAN_piece_letter(Piece piece)
 202 {
 203     if(piece < NUM_PIECE_VALUES){
 204         return SAN_piece_characters[piece];
 205     }
 206     else{
 207         return '?';
 208     }
 209 }
 210
 211         /* Return the SAN letter for the given Piece. */
 212 char
 213 coloured_piece_to_SAN_letter(Piece coloured_piece)
 214 {   Piece piece = EXTRACT_PIECE(coloured_piece);
 215     char letter = SAN_piece_letter(piece);
 216     if(EXTRACT_COLOUR(coloured_piece) == BLACK){
 217         letter = tolower(letter);
 218     }
 219     return letter;
 220 }
 221
 222         /* Set up the board from the FEN string passed as
 223          * argument.
 224          * This has the form:
 225          *        Forsythe string of the setup position.
 226          *        w/b - colour to move.
 227          *        castling permissions.
 228          *        en-passant square.
 229          *        half-moves since pawn move/piece capture.
 230          *        move number.
 231          */
 232 Board *
 233 new_fen_board(const char *fen)
 234 {   Board *new_board = allocate_new_board();
 235     /* Start with a clear board. */
 236     static const Board initial_board = {
 237         { { OFF,OFF,OFF,OFF,OFF,OFF,OFF,OFF,OFF,OFF,OFF,OFF},
 238           { OFF,OFF,OFF,OFF,OFF,OFF,OFF,OFF,OFF,OFF,OFF,OFF},
 239           { OFF,OFF,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,OFF,OFF},
 240           { OFF,OFF,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,OFF,OFF},
 241           { OFF,OFF,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,OFF,OFF},
 242           { OFF,OFF,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,OFF,OFF},
 243           { OFF,OFF,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,OFF,OFF},
 244           { OFF,OFF,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,OFF,OFF},
 245           { OFF,OFF,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,OFF,OFF},
 246           { OFF,OFF,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,OFF,OFF},
 247           { OFF,OFF,OFF,OFF,OFF,OFF,OFF,OFF,OFF,OFF,OFF,OFF},
 248           { OFF,OFF,OFF,OFF,OFF,OFF,OFF,OFF,OFF,OFF,OFF,OFF}
 249         },
 250         /* Who to move next. */
 251         WHITE,
 252         /* Move number. */
 253         1,
 254         /* Castling rights. */
 255         FALSE, FALSE, FALSE, FALSE,
 256         /* Initial king positions. */
 257         'e',FIRSTRANK,
 258         'e',LASTRANK,
 259         /* En Passant rights. */
 260         FALSE, 0, 0,
 261         /* Initial hash value. */
 262         0ul,
 263         /* halfmove_clock */
 264         0,
 265       };
 266     Rank rank = LASTRANK;
 267     Col col;
 268     const char *fen_char = fen;
 269     Boolean Ok = TRUE;
 270     /* In some circumstances we will try to parse the game data,
 271      * even if there are errors.
 272      */
 273     Boolean try_to_parse_game = FALSE;
 274
 275     /* Reset the contents of the new board. */
 276     *new_board = initial_board;
 277     /* Extract the piece positions. */
 278     col = FIRSTCOL;
 279     while(Ok && (*fen_char != ' ') && (*fen_char != '\0') &&
 280                 (rank >= FIRSTRANK)){
 281         Piece piece;
 282         char ch = *fen_char;
 283         Colour colour;
 284
 285         if((piece = is_FEN_piece(ch)) != EMPTY){
 286             if(isupper((int) ch)){
 287                 colour = WHITE;
 288             }
 289             else{
 290                 colour = BLACK;
 291             }
 292             if(col <= LASTCOL){
 293                 new_board->board[RankConvert(rank)][ColConvert(col)] =
 294                                 MAKE_COLOURED_PIECE(colour,piece);
 295                 if(piece == KING){
 296                     if(colour == WHITE){
 297                         new_board->WKingCol = col;
 298                         new_board->WKingRank = rank;
 299                     }
 300                     else{
 301                         new_board->BKingCol = col;
 302                         new_board->BKingRank = rank;
 303                     }
 304                 }
 305                 col++;
 306                 fen_char++;
 307             }
 308             else{
 309                 Ok = FALSE;
 310             }
 311         }
 312         else if(isdigit((int) ch)){
 313            if(('1' <= ch) && (ch <= '8')){
 314                col += ch - '0';
 315                /* In filling up the remaining columns of a rank we will
 316                 * temporarily exceed LASTCOL, but we expect the
 317                 * next character to be '/' so that we reset.
 318                 */
 319                if(col <= (LASTCOL+1)){
 320                    fen_char++;
 321                }
 322                else{
 323                    Ok = FALSE;
 324                }
 325            }
 326            else{
 327                Ok = FALSE;
 328            }
 329         }
 330         else if(ch == '/'){
 331             /* End of that rank. We should have completely filled the
 332              * previous rank.
 333              */
 334             if(col == (LASTCOL+1)){
 335                 col = FIRSTCOL;
 336                 rank--;
 337                 fen_char++;
 338             }
 339             else{
 340                 Ok = FALSE;
 341             }
 342         }
 343         else{
 344             /* Unknown character. */
 345             Ok = FALSE;
 346         }
 347     }
 348     /* As we don't print any error messages until the end of the function,
 349      * we don't need to guard everything with if(Ok).
 350      */
 351     if(*fen_char == ' '){
 352         /* Find out who is to move. */
 353         fen_char++;
 354     }
 355     else{
 356         Ok = FALSE;
 357     }
 358     if(*fen_char == 'w'){
 359         new_board->to_move = WHITE;
 360         fen_char++;
 361     }
 362     else if(*fen_char == 'b'){
 363         new_board->to_move = BLACK;
 364         fen_char++;
 365     }
 366     else{
 367         Ok = FALSE;
 368     }
 369     if(*fen_char == ' '){
 370         fen_char++;
 371     }
 372     else{
 373         Ok = FALSE;
 374     }
 375     /* Determine castling rights. */
 376     if(*fen_char == '-'){
 377         /* No castling rights -- default above. */
 378         new_board->WKingCastle = new_board->WQueenCastle =
 379             new_board->BKingCastle = new_board->BQueenCastle = FALSE;
 380         fen_char++;
 381     }
 382     else{
 383         /* Check to make sure that this section isn't empty. */
 384         if(*fen_char == ' '){
 385             Ok = FALSE;
 386         }
 387         if(*fen_char == 'K'){
 388             new_board->WKingCastle = TRUE;
 389             fen_char++;
 390         }
 391         if(*fen_char == 'Q'){
 392             new_board->WQueenCastle = TRUE;
 393             fen_char++;
 394         }
 395         if(*fen_char == 'k'){
 396             new_board->BKingCastle = TRUE;
 397             fen_char++;
 398         }
 399         if(*fen_char == 'q'){
 400             new_board->BQueenCastle = TRUE;
 401             fen_char++;
 402         }
 403     }
 404     if(*fen_char == ' '){
 405         fen_char++;
 406     }
 407     else{
 408         Ok = FALSE;
 409     }
 410     /* If we are ok to this point, try to make a best efforts approach
 411      * to handle the game, even if there are subsequent errors.
 412      */
 413     if(Ok){
 414        try_to_parse_game = TRUE;
 415     }
 416     /* Check for an en-passant square. */
 417     if(*fen_char == '-'){
 418         /* None. */
 419         fen_char++;
 420     }
 421     else if(is_col(*fen_char)){
 422         col = *fen_char;
 423         fen_char++;
 424         if(is_rank(*fen_char)){
 425             rank = *fen_char;
 426             fen_char++;
 427             /* Make sure that the en-passant indicator is consistent
 428              * with whose move it is.
 429              */
 430             if(((new_board->to_move == WHITE) && (rank == '6')) ||
 431                 ((new_board->to_move == BLACK) && (rank == '3'))){
 432                 /* Consistent. */
 433                 new_board->EnPassant = TRUE;
 434                 new_board->ep_rank = rank;
 435                 new_board->ep_col = col;
 436             }
 437             else{
 438                 Ok = FALSE;
 439             }
 440         }
 441         else{
 442             Ok = FALSE;
 443         }
 444     }
 445     else{
 446         Ok = FALSE;
 447     }
 448     if(*fen_char == ' '){
 449         fen_char++;
 450     }
 451     else{
 452         Ok = FALSE;
 453     }
 454     /* Check for half-move count since last pawn move
 455      * or capture.
 456      */
 457     if(isdigit((int) *fen_char)){
 458         unsigned halfmove_clock = *fen_char-'0';
 459         fen_char++;
 460         while(isdigit((int) *fen_char)){
 461             halfmove_clock = (halfmove_clock*10)+(*fen_char-'0');
 462             fen_char++;
 463         }
 464         new_board->halfmove_clock = halfmove_clock;
 465     }
 466     else{
 467         Ok = FALSE;
 468     }
 469     if(*fen_char == ' '){
 470         fen_char++;
 471     }
 472     else{
 473         Ok = FALSE;
 474     }
 475     /* Check for current move number. */
 476     if(isdigit((int) *fen_char)){
 477         unsigned move_number = 0;
 478
 479         move_number = *fen_char-'0';
 480         fen_char++;
 481         while(isdigit((int) *fen_char)){
 482             move_number = (move_number*10)+(*fen_char-'0');
 483             fen_char++;
 484         }
 485         if(move_number < 1) {
 486             move_number = 1;
 487         }
 488         new_board->move_number = move_number;
 489     }
 490     else{
 491         Ok = FALSE;
 492     }
 493     /* Allow trailing space. */
 494     while(isspace((int) *fen_char)){
 495         fen_char++;
 496     }
 497     if(*fen_char != '\0'){
 498         Ok = FALSE;
 499     }
 500     if(Ok){
 501     }
 502     else{
 503         fprintf(GlobalState.logfile,"Illegal FEN string %s at %s",fen,fen_char);
 504         if(try_to_parse_game){
 505             fprintf(GlobalState.logfile," Attempting to parse the game, anyway.");
 506         }
 507         else{
 508             (void) free_board((void *)new_board);
 509             new_board = NULL;
 510         }
 511         putc('\n',GlobalState.logfile);
 512     }
 513     return new_board;
 514 }
 515
 516         /* Set up a board structure for a new game.
 517          * This involves placing the pieces in their initial positions,
 518          * setting up castling and en-passant rights, and initialising
 519          * the hash positions.
 520          * If the fen argument is NULL then a completely new board is
 521          * setup, otherwise the indicated FEN position is returned.
 522          */
 523 static Board *
 524 new_game_board(const char *fen)
 525 {   Board *new_board;
 526     static const Board initial_board =
 527       {
 528         { { OFF,OFF,OFF,OFF,OFF,OFF,OFF,OFF,OFF,OFF,OFF,OFF},
 529           { OFF,OFF,OFF,OFF,OFF,OFF,OFF,OFF,OFF,OFF,OFF,OFF},
 530           { OFF,OFF,W(ROOK),W(KNIGHT),W(BISHOP),W(QUEEN),
 531                             W(KING),W(BISHOP),W(KNIGHT),W(ROOK),OFF,OFF},
 532           { OFF,OFF,W(PAWN),W(PAWN),W(PAWN),W(PAWN),
 533                             W(PAWN),W(PAWN),W(PAWN),W(PAWN),OFF,OFF},
 534           { OFF,OFF,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,OFF,OFF},
 535           { OFF,OFF,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,OFF,OFF},
 536           { OFF,OFF,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,OFF,OFF},
 537           { OFF,OFF,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,OFF,OFF},
 538           { OFF,OFF,B(PAWN),B(PAWN),B(PAWN),B(PAWN),
 539                             B(PAWN),B(PAWN),B(PAWN),B(PAWN),OFF,OFF},
 540           { OFF,OFF,B(ROOK),B(KNIGHT),B(BISHOP),B(QUEEN),
 541                             B(KING),B(BISHOP),B(KNIGHT),B(ROOK),OFF,OFF},
 542           { OFF,OFF,OFF,OFF,OFF,OFF,OFF,OFF,OFF,OFF,OFF,OFF},
 543           { OFF,OFF,OFF,OFF,OFF,OFF,OFF,OFF,OFF,OFF,OFF,OFF}
 544         },
 545         /* Who to move next. */
 546         WHITE,
 547         /* Move number. */
 548         1,
 549         /* Castling rights. */
 550         TRUE, TRUE, TRUE, TRUE,
 551         /* Initial king positions. */
 552         'e',FIRSTRANK,
 553         'e',LASTRANK,
 554         /* En Passant rights. */
 555         FALSE, 0, 0,
 556         /* Initial hash value. */
 557         0ul,
 558         /* halfmove_clock */
 559         0,
 560       };
 561     /* Iterate over the columns. */
 562     Col col;
 563
 564     if(fen != NULL){
 565         new_board = new_fen_board(fen);
 566     }
 567     /* Guard against failure of new_fen_board as well as the
 568      * normal game situation.
 569      */
 570     if((fen == NULL) || (new_board == NULL)){
 571         /* Use the initial board setup. */
 572         new_board = allocate_new_board();
 573         *new_board = initial_board;
 574     }
 575
 576     /* Generate the hash value for the initial position. */
 577     for(col = FIRSTCOL; col <= LASTCOL; col++){
 578         Rank rank;
 579
 580         for(rank = FIRSTRANK; rank <= LASTRANK; rank++){
 581             /* Find the basic components. */
 582             Piece coloured_piece = new_board->board[
 583                                 RankConvert(rank)][ColConvert(col)];
 584             Piece piece = EXTRACT_PIECE(coloured_piece);
 585             Colour colour = EXTRACT_COLOUR(coloured_piece);
 586
 587             if(coloured_piece != EMPTY){
 588                 new_board->hash_value ^= HashLookup(col,rank,piece,colour);
 589             }
 590         }
 591     }
 592     return new_board;
 593 }
 594
 595         /* Print out the current occupant of the given square. */
 596 static void
 597 print_square(Col col, Rank rank, const Board *board,FILE *outfp)
 598 {   short r = RankConvert(rank);
 599     short c = ColConvert(col);
 600
 601     Piece coloured_piece = board->board[r][c];
 602     switch((int) coloured_piece){
 603         case W(PAWN):
 604         case W(KNIGHT):
 605         case W(BISHOP):
 606         case W(ROOK):
 607         case W(QUEEN):
 608         case W(KING):
 609         case B(PAWN):
 610         case B(KNIGHT):
 611         case B(BISHOP):
 612         case B(ROOK):
 613         case B(QUEEN):
 614         case B(KING):
 615             putc(coloured_piece_to_SAN_letter(coloured_piece),outfp);
 616             break;
 617         case EMPTY:
 618             putc('.',outfp);
 619             break;
 620         case OFF:
 621             putc('?',outfp);
 622             break;
 623         default:
 624             fprintf(GlobalState.logfile,
 625                 "Attempt to print illegal square %c%c in print_square.\n",
 626                         col,rank);
 627             break;
 628     }
 629 }
 630
 631         /* Print out the contents of the given board. */
 632 static void
 633 print_board(const Board *board,FILE *outfp)
 634 {  Rank rank;
 635    Col col;
 636
 637    for(rank = LASTRANK; rank >= FIRSTRANK; rank--){
 638        for(col = FIRSTCOL; col <= LASTCOL; col++){
 639            print_square(col,rank,board,outfp);
 640        }
 641        putc('\n',outfp);
 642    }
 643    putc('\n',outfp);
 644 }
 645
 646 #if INCLUDE_UNUSED_FUNCTIONS
 647
 648         /* Check the consistency of the board. */
 649 static void
 650 check_board(const Board *board,const char *where)
 651 {  Rank rank;
 652    Col col;
 653
 654    for(rank = LASTRANK; rank >= FIRSTRANK; rank--){
 655        for(col = FIRSTCOL; col <= LASTCOL; col++){
 656           short r = RankConvert(rank);
 657           short c = ColConvert(col);
 658
 659           switch(board->board[r][c]){
 660             case W(PAWN):
 661             case W(KNIGHT):
 662             case W(BISHOP):
 663             case W(ROOK):
 664             case W(QUEEN):
 665             case W(KING):
 666             case B(PAWN):
 667             case B(KNIGHT):
 668             case B(BISHOP):
 669             case B(ROOK):
 670             case B(QUEEN):
 671             case B(KING):
 672             case EMPTY:
 673                 break;
 674             default:
 675                 fprintf(GlobalState.logfile,
 676                                 "%s: Illegal square %c%c (%u %u) contains %d.\n",
 677                                 where,col,rank,r,c,board->board[r][c]);
 678                 report_details(GlobalState.logfile);
 679                 abort();
 680                 break;
 681           }
 682       }
 683    }
 684 }
 685 #endif
 686
 687     /* Return the number of half moves that have been completed
 688      * on the board.
 689      */
 690 static int
 691 half_moves_played(const Board *board)
 692 {
 693     int half_moves = 2*(board->move_number-1);
 694     if(board->to_move == BLACK){
 695         half_moves ++;
 696     }
 697     return half_moves;
 698 }
 699
 700         /* Implement move_details on the board.
 701          * Return TRUE if the move is ok, FALSE otherwise.
 702          * move_details is completed by the call to determine_move_details.
 703          * Thereafter, it is safe to make the move on board.
 704          */
 705 static Boolean
 706 apply_move(Colour colour,Move *move_details, Board *board)
 707 {   /* Assume success. */
 708     Boolean Ok = TRUE;
 709
 710     if(determine_move_details(colour,move_details,board)){
 711         Piece piece_to_move = move_details->piece_to_move;
 712
 713         if(GlobalState.output_format == EPD){
 714             move_details->epd = (char *) MallocOrDie(FEN_SPACE);
 715             build_basic_EPD_string(board,move_details->epd);
 716         }
 717
 718         if(move_details->class != NULL_MOVE) {
 719             make_move(move_details->class, move_details->from_col,move_details->from_rank,
 720                             move_details->to_col,move_details->to_rank,
 721                             piece_to_move,colour,board);
 722         }
 723         /* See if there are any subsiduary actions. */
 724         switch(move_details->class){
 725             case PAWN_MOVE:
 726             case PIECE_MOVE:
 727             case ENPASSANT_PAWN_MOVE:
 728                 /* Nothing more to do. */
 729                 break;
 730             case PAWN_MOVE_WITH_PROMOTION:
 731                 if(move_details->class == PAWN_MOVE_WITH_PROMOTION){
 732                     if(move_details->promoted_piece != EMPTY){
 733                         /* Now make the promotion. */
 734                         make_move(move_details->class, move_details->to_col,move_details->to_rank,
 735                                   move_details->to_col,move_details->to_rank,
 736                                   move_details->promoted_piece,colour,board);
 737                     }
 738                     else{
 739                         Ok = FALSE;
 740                     }
 741                 }
 742                 break;
 743         case KINGSIDE_CASTLE:
 744             /* Step the Rook to the left of the king. */
 745             piece_to_move = ROOK;
 746             make_move(move_details->class, LASTCOL,move_details->from_rank,move_details->to_col-1,
 747                             move_details->to_rank,
 748                             piece_to_move,colour,board);
 749             break;
 750         case QUEENSIDE_CASTLE:
 751             /* Step the Rook to the right of the king. */
 752             piece_to_move = ROOK;
 753             make_move(move_details->class, FIRSTCOL,move_details->from_rank,move_details->to_col+1,
 754                             move_details->to_rank,
 755                             piece_to_move,colour,board);
 756             break;
 757         case NULL_MOVE:
 758             /* Nothing more to do. */
 759             break;
 760         case UNKNOWN_MOVE:
 761         default:
 762             Ok = FALSE;
 763             break;
 764         }
 765         /* Determine whether or not this move gives check. */
 766         if(Ok){
 767             move_details->check_status =
 768                         king_is_in_check(board,OPPOSITE_COLOUR(colour));
 769             if(move_details->check_status == CHECK){
 770                 /* See whether it is CHECKMATE. */
 771                 if(king_is_in_checkmate(OPPOSITE_COLOUR(colour),board)){
 772                     move_details->check_status = CHECKMATE;
 773                 }
 774             }
 775             /* Handle the halfmove_clock. */
 776             if(piece_to_move == PAWN ||
 777                     move_details->captured_piece != EMPTY) {
 778                 board->halfmove_clock = 0;
 779             }
 780             else {
 781                 board->halfmove_clock++;
 782             }
 783         }
 784     }
 785     else{
 786         Ok = FALSE;
 787     }
 788     return Ok;
 789 }
 790
 791         /* Play out the moves on the given board.
 792          * game_details is updated with the final_ and cumulative_ hash
 793          * values.
 794          * Check move validity unless a NULL_MOVE has been found in this
 795          * variation.
 796          */
 797 static Boolean
 798 play_moves(Game *game_details, Board *board, Move *moves, unsigned max_depth,
 799            Boolean check_move_validity)
 800 {   Boolean game_ok = TRUE;
 801     /* Ply number at which any error was found. */
 802     int error_ply = 0;
 803     /* Force a match if we aren't looking for positional variations. */
 804     Boolean game_matches = GlobalState.positional_variations?FALSE:TRUE;
 805     Move *next_move = moves;
 806     /* Keep track of the final ECO match. */
 807     EcoLog *eco_match = NULL;
 808
 809     /* Try the initial board position for a match.
 810      * This is required because the game might have been set up
 811      * from a FEN string, rather than being the normal starting
 812      * position.
 813      */
 814     if(!game_matches && position_matches(board)){
 815         game_matches = TRUE;
 816         if(GlobalState.add_position_match_comments) {
 817             CommentList *comment = create_match_comment(next_move);
 818             comment->next = game_details->prefix_comment;
 819             game_details->prefix_comment = comment;
 820         }
 821     }
 822     /* Keep going while the game is ok, and we have some more
 823      * moves and we haven't exceeded the search depth without finding
 824      * a match.
 825      */
 826     while(game_ok && (next_move != NULL) &&
 827                 (game_matches || (board->move_number <= max_depth))){
 828         if(*(next_move->move) != '\0'){
 829             /* See if there are any variations associated with this move. */
 830             if((next_move->Variants != NULL) && GlobalState.keep_variations){
 831                 game_matches |= apply_variations(game_details,board,
 832                                                  next_move->Variants,
 833                                                  check_move_validity);
 834             }
 835             /* Now try the main move. */
 836             if(next_move->class == NULL_MOVE) {
 837                 /* We might not be able to check the validity of
 838                  * subsequent moves.
 839                  */
 840 #if 0
 841                 check_move_validity = FALSE;
 842 #endif
 843             }
 844             if(check_move_validity) {
 845                 if(apply_move(board->to_move,next_move,board)){
 846                    /* Don't try for a positional match if we already have one. */
 847                    if(!game_matches && position_matches(board)){
 848                        game_matches = TRUE;
 849                        if(GlobalState.add_position_match_comments) {
 850                            CommentList *comment = create_match_comment(next_move);
 851                            append_comments_to_move(next_move, comment);
 852                        }
 853                    }
 854                    /* Combine this hash value with the cumulative one. */
 855                    game_details->cumulative_hash_value += board->hash_value;
 856                    if(GlobalState.fuzzy_match_duplicates) {
 857                         int plies = 2 * board->move_number - 1;
 858                         /* Check who has just moved. */
 859                         if(board->to_move == BLACK) {
 860                             plies++;
 861                         }
 862                         /* Consider remembering this hash value for fuzzy matches. */
 863                         if(GlobalState.fuzzy_match_depth == plies) {
 864                             /* Remember it. */
 865                             game_details->fuzzy_duplicate_hash = board->hash_value;
 866                         }
 867                    }
 868                    board->to_move = OPPOSITE_COLOUR(board->to_move);
 869                    if(board->to_move == WHITE){
 870                        board->move_number++;
 871                    }
 872                    if(GlobalState.add_ECO && !GlobalState.parsing_ECO_file){
 873                        int half_moves = half_moves_played(board);
 874                        EcoLog *entry = eco_matches(
 875                                board->hash_value,
 876                                game_details->cumulative_hash_value,
 877                                half_moves);
 878                        if(entry != NULL){
 879                            /* Consider keeping the match.
 880                             * Could try to avoid spurious matches which become
 881                             * more likely with larger ECO files and
 882                             * the longer a game goes on.
 883                             * Could be mitigated partly by preferring
 884                             * an ECO line of exactly the same length as
 885                             * the current game line.
 886                             * Not currently implemented.
 887                             */
 888                            if(eco_match == NULL){
 889                                /* We don't have one yet. */
 890                                eco_match = entry;
 891                            }
 892                            else {
 893                                /* Keep it anyway.
 894                                 * This logic always prefers a longer match
 895                                 * to a shorter, irrespective of whether
 896                                 * either match is exact or not.
 897                                 * This logic was followed in versions
 898                                 * up to and including v13.8.
 899                                 */
 900                                eco_match = entry;
 901                            }
 902                        }
 903                    }
 904                    next_move = next_move->next;
 905                 }
 906                 else{
 907                     print_error_context(GlobalState.logfile);
 908                     fprintf(GlobalState.logfile,
 909                                     "Failed to make move %u%s %s in the game:\n",
 910                                     board->move_number,
 911                                     (board->to_move == WHITE)?".":"...",
 912                                     next_move->move);
 913                     print_board(board,GlobalState.logfile);
 914                     report_details(GlobalState.logfile);
 915                     game_ok = FALSE;
 916                     /* Work out where the error was. */
 917                     error_ply = 2 * board->move_number - 1;
 918                     /* Check who has just moved. */
 919                     if(board->to_move == BLACK) {
 920                         error_ply++;
 921                     }
 922                 }
 923             }
 924             else {
 925                 /* Go through the motions as if the move were checked. */
 926                board->to_move = OPPOSITE_COLOUR(board->to_move);
 927                if(board->to_move == WHITE){
 928                    board->move_number++;
 929                }
 930                next_move = next_move->next;
 931             }
 932         }
 933         else{
 934             /* An empty move. */
 935             fprintf(GlobalState.logfile,
 936                         "Internal error: Empty move in play_moves.\n");
 937             report_details(GlobalState.logfile);
 938             game_ok = FALSE;
 939             /* Work out where the error was. */
 940             error_ply = 2 * board->move_number - 1;
 941             /* Check who has just moved. */
 942             if(board->to_move == BLACK) {
 943                 error_ply++;
 944             }
 945         }
 946     }
 947     if(game_ok){
 948         if(eco_match != NULL){
 949            /* Free any details of the old one. */
 950            if(game_details->tags[ECO_TAG] != NULL){
 951                (void) free((void *) game_details->tags[ECO_TAG]);
 952                game_details->tags[ECO_TAG] = NULL;
 953            }
 954            if(game_details->tags[OPENING_TAG] != NULL){
 955                (void) free((void *)game_details->tags[OPENING_TAG]);
 956                game_details->tags[OPENING_TAG] = NULL;
 957            }
 958            if(game_details->tags[VARIATION_TAG] != NULL){
 959                (void) free((void *)game_details->tags[VARIATION_TAG]);
 960                game_details->tags[VARIATION_TAG] = NULL;
 961            }
 962            if(game_details->tags[SUB_VARIATION_TAG] != NULL){
 963                (void) free((void *)game_details->tags[SUB_VARIATION_TAG]);
 964                game_details->tags[SUB_VARIATION_TAG] = NULL;
 965            }
 966            /* Add in the new one. */
 967            if(eco_match->ECO_tag != NULL){
 968                game_details->tags[ECO_TAG] = copy_string(eco_match->ECO_tag);
 969            }
 970            if(eco_match->Opening_tag != NULL){
 971                game_details->tags[OPENING_TAG] = copy_string(eco_match->Opening_tag);
 972            }
 973            if(eco_match->Variation_tag != NULL){
 974                game_details->tags[VARIATION_TAG] =
 975                                 copy_string(eco_match->Variation_tag);
 976            }
 977            if(eco_match->Sub_Variation_tag != NULL){
 978                game_details->tags[SUB_VARIATION_TAG] =
 979                                 copy_string(eco_match->Sub_Variation_tag);
 980            }
 981         }
 982     }
 983     /* Fill in the hash value of the final position reached. */
 984     game_details->final_hash_value = board->hash_value;
 985     game_details->moves_ok = game_ok;
 986     game_details->error_ply = error_ply;
 987     if(!game_ok){
 988         /* Decide whether to keep it anyway. */
 989         if(GlobalState.keep_broken_games) {
 990         }
 991         else if(GlobalState.positional_variations){
 992         }
 993         else {
 994             /* Only return a match if it genuinely matched a variation
 995              * in which we were interested.
 996              */
 997             /* We can't have found a genuine match. */
 998             game_matches = FALSE;
 999         }
1000     }
1001     return game_matches;
1002 }
1003
1004         /* Play out the moves of an ECO line on the given board.
1005          * game_details is updated with the final_ and cumulative_ hash
1006          * values.
1007          */
1008
1009 static void
1010 play_eco_moves(Game *game_details, Board *board,Move *moves)
1011 {   Boolean game_ok = TRUE;
1012     /* Ply number at which any error was found. */
1013     int error_ply = 0;
1014     Move *next_move = moves;
1015
1016     /* Keep going while the game is ok, and we have some more
1017      * moves and we haven't exceeded the search depth without finding
1018      * a match.
1019      */
1020     while(game_ok && (next_move != NULL)){
1021         if(*(next_move->move) != '\0'){
1022             /* Ignore variations. */
1023             if(apply_move(board->to_move,next_move,board)){
1024                /* Combine this hash value to the cumulative one. */
1025                game_details->cumulative_hash_value += board->hash_value;
1026                board->to_move = OPPOSITE_COLOUR(board->to_move);
1027                if(board->to_move == WHITE){
1028                    board->move_number++;
1029                }
1030                next_move = next_move->next;
1031             }
1032             else{
1033                 print_error_context(GlobalState.logfile);
1034                 fprintf(GlobalState.logfile,
1035                                 "Failed to make move %u%s %s in the game:\n",
1036                                 board->move_number,
1037                                 (board->to_move == WHITE)?".":"...",
1038                                 next_move->move);
1039                 print_board(board,GlobalState.logfile);
1040                 report_details(GlobalState.logfile);
1041                 game_ok = FALSE;
1042                 /* Work out where the error was. */
1043                 error_ply = 2 * board->move_number - 1;
1044                 /* Check who has just moved. */
1045                 if(board->to_move == BLACK) {
1046                     error_ply++;
1047                 }
1048             }
1049         }
1050         else{
1051             /* An empty move. */
1052             fprintf(GlobalState.logfile,
1053                         "Internal error: Empty move in play_eco_moves.\n");
1054             report_details(GlobalState.logfile);
1055             game_ok = FALSE;
1056             /* Work out where the error was. */
1057             error_ply = 2 * board->move_number - 1;
1058             /* Check who has just moved. */
1059             if(board->to_move == BLACK) {
1060                 error_ply++;
1061             }
1062         }
1063     }
1064     /* Fill in the hash value of the final position reached. */
1065     game_details->final_hash_value = board->hash_value;
1066     game_details->moves_ok = game_ok;
1067     game_details->error_ply = error_ply;
1068 }
1069
1070         /* Play out a variation.
1071          * Check move validity unless a NULL_MOVE has been found in this
1072          * variation.
1073          * Return TRUE if the variation matches a position that
1074          * we are looking for.
1075          */
1076 static Boolean
1077 apply_variations(const Game *game_details,const Board *board,Variation *variation,
1078                  Boolean check_move_validity)
1079 {   /* Force a match if we aren't looking for positional variations. */
1080     Boolean variation_matches = GlobalState.positional_variations?FALSE:TRUE;
1081     /* Allocate space for the copies.
1082      * Allocation is done, rather than relying on local copies in the body
1083      * of the loop because the recursive nature of this function has
1084      * resulted in stack overflow on the PC version.
1085      */
1086     Game *copy_game = (Game *) MallocOrDie(sizeof(*copy_game));
1087     Board *copy_board = allocate_new_board();
1088
1089     while(variation != NULL){
1090         /* Work on the copies. */
1091         *copy_game = *game_details;
1092         *copy_board = *board;
1093
1094         /* We only need one variation to match to declare a match.
1095          * Play out the variation to its full depth, because we
1096          * will want the full move information if the main line
1097          * later matches.
1098          */
1099         variation_matches |= play_moves(copy_game,copy_board,variation->moves,
1100                                         DEFAULT_POSITIONAL_DEPTH,
1101                                         check_move_validity);
1102         variation = variation->next;
1103     }
1104     (void) free((void *)copy_game);
1105     (void) free_board((void *)copy_board);
1106     return variation_matches;
1107 }
1108
1109         /* game_details contains a complete move score.
1110          * Try to apply each move on a new board.
1111          * Store in plycount the number of ply played.
1112          * Return TRUE if the game matches a variation that we are
1113          * looking for.
1114          */
1115 Boolean
1116 apply_move_list(Game *game_details,unsigned *plycount)
1117 {   Move *moves = game_details->moves;
1118     Board *board = new_game_board(game_details->tags[FEN_TAG]);
1119     Boolean game_matches;
1120     /* Set the default search depth. */
1121     unsigned max_depth = GlobalState.depth_of_positional_search;
1122
1123     /* Ensure that we have a sensible search depth. */
1124     if(max_depth == 0){
1125         /* No positional variations specified. */
1126         max_depth = DEFAULT_POSITIONAL_DEPTH;
1127     }
1128
1129     /* Start off the cumulative hash value. */
1130     game_details->cumulative_hash_value = 0;
1131
1132     /* Play through the moves and see if we have a match.
1133      * Check move validity.
1134      */
1135     game_matches = play_moves(game_details,board,moves,max_depth,TRUE);
1136
1137     game_details->moves_checked = TRUE;
1138
1139     /* Record how long the game was. */
1140     if(board->to_move == BLACK){
1141         *plycount = 2 * board->move_number - 1;
1142     }
1143     else{
1144         /* This move number hasn't been played. */
1145         *plycount = 2 * (board->move_number - 1);
1146     }
1147
1148     if(game_matches) {
1149          game_matches = check_for_only_stalemate(board, moves);
1150     }
1151
1152     (void) free_board((void *)board);
1153     return game_matches;
1154 }
1155
1156         /* game_details contains a complete move score.
1157          * Try to apply each move on a new board.
1158          * Store in number_of_moves the length of the game.
1159          * Return TRUE if the game is ok.
1160          */
1161 Boolean
1162 apply_eco_move_list(Game *game_details,unsigned *number_of_half_moves)
1163 {   Move *moves = game_details->moves;
1164     Board *board = new_game_board(game_details->tags[FEN_TAG]);
1165
1166     /* Start off the cumulative hash value. */
1167     game_details->cumulative_hash_value = 0;
1168     play_eco_moves(game_details,board,moves);
1169     game_details->moves_checked = TRUE;
1170     /* Record how long the game was. */
1171     *number_of_half_moves = half_moves_played(board);
1172     (void) free_board((void *)board);
1173     return game_details->moves_ok;
1174 }
1175
1176
1177         /* Return the string associated with the given piece. */
1178 const char *
1179 piece_str(Piece piece)
1180 {
1181     if(piece < NUM_PIECE_VALUES){
1182         return output_piece_characters[piece];
1183     }
1184     else{
1185         return "?";
1186     }
1187 }
1188
1189         /* Rewrite move_details->move according to the details held
1190          * within the structure and the current state of the board.
1191          */
1192 static Boolean
1193 rewrite_SAN_string(Colour colour,Move *move_details, Board *board)
1194 {   Boolean Ok = TRUE;
1195
1196     if(move_details == NULL){
1197         /* Shouldn't happen. */
1198         fprintf(GlobalState.logfile,
1199                 "Internal error: NULL move details in rewrite_SAN_string.\n");
1200         Ok = FALSE;
1201     }
1202     else if(move_details->move[0] == '\0'){
1203         /* Shouldn't happen. */
1204         fprintf(GlobalState.logfile,"Empty move in rewrite_SAN_string.\n");
1205         Ok = FALSE;
1206     }
1207     else{
1208         const unsigned char *move = move_details->move;
1209         MoveClass class = move_details->class;
1210         MovePair *move_list = NULL;
1211         Col to_col = move_details->to_col;
1212         Rank to_rank = move_details->to_rank;
1213         unsigned char new_move_str[MAX_MOVE_LEN+1] = "";
1214
1215         switch(class){
1216             case PAWN_MOVE:
1217             case ENPASSANT_PAWN_MOVE:
1218             case PAWN_MOVE_WITH_PROMOTION:
1219                 move_list = find_pawn_moves(move_details->from_col,
1220                                                 '0',to_col,to_rank,
1221                                                 colour,board);
1222                 break;
1223             case PIECE_MOVE:
1224                 switch(move_details->piece_to_move){
1225                     case KING:
1226                         move_list = find_king_moves(to_col,to_rank,colour,board);
1227                         break;
1228                     case QUEEN:
1229                         move_list = find_queen_moves(to_col,to_rank,colour,board);
1230                         break;
1231                     case ROOK:
1232                         move_list = find_rook_moves(to_col,to_rank,colour,board);
1233                         break;
1234                     case KNIGHT:
1235                         move_list = find_knight_moves(to_col,to_rank,colour,board);
1236                         break;
1237                     case BISHOP:
1238                         move_list = find_bishop_moves(to_col,to_rank,colour,board);
1239                         break;
1240                     default:
1241                         fprintf(GlobalState.logfile,"Unknown piece move %s\n",move);
1242                         Ok = FALSE;
1243                         break;
1244                 }
1245                 break;
1246             case KINGSIDE_CASTLE:
1247             case QUEENSIDE_CASTLE:
1248                 /* No move list to prepare. */
1249                 break;
1250             case NULL_MOVE:
1251                 /* No move list to prepare. */
1252                 break;
1253             case UNKNOWN_MOVE:
1254             default:
1255                 fprintf(GlobalState.logfile,
1256                         "Unknown move class in rewrite_SAN_string(%d).\n",
1257                         move_details->class);
1258                 Ok = FALSE;
1259                 break;
1260         }
1261         if(move_list != NULL){
1262             move_list = exclude_checks(move_details->piece_to_move,colour,
1263                                                 move_list,board);
1264         }
1265         if((move_list == NULL) && (class != KINGSIDE_CASTLE) &&
1266                         (class != QUEENSIDE_CASTLE) && (class != NULL_MOVE)){
1267             Ok = FALSE;
1268         }
1269         /* We should now have enough information in move_details to compose a
1270          * SAN string.
1271          */
1272         if(Ok){
1273             size_t new_move_index = 0;
1274
1275             switch(class){
1276                 case PAWN_MOVE:
1277                 case ENPASSANT_PAWN_MOVE:
1278                 case PAWN_MOVE_WITH_PROMOTION:
1279                     /* See if we need to give the source column. */
1280                     if(move_details->captured_piece != EMPTY){
1281                         new_move_str[new_move_index] = move_details->from_col;
1282                         new_move_index++;
1283                         new_move_str[new_move_index] = 'x';
1284                         new_move_index++;
1285                     }
1286                     else if(move_list->next != NULL){
1287                         new_move_str[new_move_index] = move_details->from_col;
1288                         new_move_index++;
1289                     }
1290                     /* Add in the destination. */
1291                     new_move_str[new_move_index] = to_col;
1292                     new_move_index++;
1293                     new_move_str[new_move_index] = to_rank;
1294                     new_move_index++;
1295                     if(class == PAWN_MOVE_WITH_PROMOTION){
1296                         const char *promoted_piece =
1297                                         piece_str(move_details->promoted_piece);
1298                         new_move_str[new_move_index] = '=';
1299                         new_move_index++;
1300                         strcpy((char *) &new_move_str[new_move_index],
1301                                promoted_piece);
1302                         new_move_index += strlen(promoted_piece);
1303                     }
1304                     new_move_str[new_move_index] = '\0';
1305                     break;
1306                 case PIECE_MOVE:
1307                     {   const char *piece = piece_str(move_details->piece_to_move);
1308                         strcpy((char *) &new_move_str[0],piece);
1309                         new_move_index += strlen(piece);
1310                         /* Check for the need to disambiguate. */
1311                         if(move_list->next != NULL){
1312                             /* It is necessary.  Count how many times
1313                              * the from_ col and rank occur in the list
1314                              * of possibles in order to determine which to use
1315                              * for this purpose.
1316                              */
1317                             int col_times = 0, rank_times = 0;
1318                             MovePair *possible;
1319                             Col from_col = move_details->from_col;
1320                             Rank from_rank = move_details->from_rank;
1321
1322                             for(possible = move_list; possible != NULL;
1323                                             possible = possible->next){
1324                                 if(possible->from_col == from_col){
1325                                     col_times++;
1326                                 }
1327                                 if(possible->from_rank == from_rank){
1328                                     rank_times++;
1329                                 }
1330                             }
1331                             if(col_times == 1){
1332                                 /* Use the col. */
1333                                 new_move_str[new_move_index] = from_col;
1334                                 new_move_index++;
1335                             }
1336                             else if(rank_times == 1){
1337                                 /* Use the rank. */
1338                                 new_move_str[new_move_index] = from_rank;
1339                                 new_move_index++;
1340                             }
1341                             else{
1342                                 /* Use both. */
1343                                 new_move_str[new_move_index] = from_col;
1344                                 new_move_index++;
1345                                 new_move_str[new_move_index] = from_rank;
1346                                 new_move_index++;
1347                             }
1348                         }
1349                         /* See if a capture symbol is needed. */
1350                         if(move_details->captured_piece != EMPTY){
1351                             new_move_str[new_move_index] = 'x';
1352                             new_move_index++;
1353                         }
1354                         /* Add in the destination. */
1355                         new_move_str[new_move_index] = to_col;
1356                         new_move_index++;
1357                         new_move_str[new_move_index] = to_rank;
1358                         new_move_index++;
1359                         new_move_str[new_move_index] = '\0';
1360                     }
1361                     break;
1362                 case KINGSIDE_CASTLE:
1363                     strcpy((char *) new_move_str,"O-O");
1364                     break;
1365                 case QUEENSIDE_CASTLE:
1366                     strcpy((char *) new_move_str,"O-O-O");
1367                     break;
1368                 case NULL_MOVE:
1369                     strcpy((char *) new_move_str, (char *) NULL_MOVE_STRING);
1370                     break;
1371                 case UNKNOWN_MOVE:
1372                 default:
1373                     Ok = FALSE;
1374                     break;
1375             }
1376             if(Ok){
1377                 if(move_details->check_status != NOCHECK){
1378                     if(move_details->check_status == CHECK){
1379                         /* It isn't mate. */
1380                         strcat((char *) new_move_str,"+");
1381                     }
1382                     else{
1383                         if(GlobalState.output_format == CM){
1384                             strcat((char *) new_move_str,"++");
1385                         }
1386                         else{
1387                             strcat((char *) new_move_str,"#");
1388                         }
1389                     }
1390                 }
1391             }
1392             /* Update the move_details structure with the new string. */
1393             strcpy((char *) move_details->move,
1394                    (const char *) new_move_str);
1395         }
1396         if(move_list != NULL){
1397             free_move_pair_list(move_list);
1398         }
1399     }
1400     return Ok;
1401 }
1402
1403         /* Rewrite move_details->move and apply the move to board.
1404          * Return TRUE if the move is ok, FALSE otherwise.
1405          */
1406 static Boolean
1407 rewrite_move(Colour colour,Move *move_details, Board *board, Boolean null_move_found)
1408 {   /* Assume success. */
1409     Boolean Ok = TRUE;
1410
1411     if(rewrite_SAN_string(colour,move_details,board)){
1412         Piece piece_to_move = move_details->piece_to_move;
1413
1414         if(move_details->class != NULL_MOVE) {
1415             make_move(move_details->class, move_details->from_col,move_details->from_rank,
1416                             move_details->to_col,move_details->to_rank,
1417                             piece_to_move,colour,board);
1418         }
1419         else {
1420             null_move_found = TRUE;
1421         }
1422         /* See if there are any subsiduary actions. */
1423         switch(move_details->class){
1424             case PAWN_MOVE:
1425             case PIECE_MOVE:
1426             case ENPASSANT_PAWN_MOVE:
1427                 /* Nothing more to do. */
1428                 break;
1429             case PAWN_MOVE_WITH_PROMOTION:
1430                 if(move_details->class == PAWN_MOVE_WITH_PROMOTION){
1431                     if(move_details->promoted_piece != EMPTY){
1432                         /* @@@ Do promoted moves have '+' properly appended? */
1433                         /* Now make the promotion. */
1434                         make_move(move_details->class, move_details->to_col,move_details->to_rank,
1435                                   move_details->to_col,move_details->to_rank,
1436                                   move_details->promoted_piece,colour,board);
1437                     }
1438                     else{
1439                         Ok = FALSE;
1440                     }
1441                 }
1442                 break;
1443         case KINGSIDE_CASTLE:
1444             /* Step the Rook to the left of the king. */
1445             piece_to_move = ROOK;
1446             make_move(move_details->class, LASTCOL,move_details->from_rank,move_details->to_col-1,
1447                             move_details->to_rank,
1448                             piece_to_move,colour,board);
1449             break;
1450         case QUEENSIDE_CASTLE:
1451             /* Step the Rook to the right of the king. */
1452             piece_to_move = ROOK;
1453             make_move(move_details->class, FIRSTCOL,move_details->from_rank,move_details->to_col+1,
1454                             move_details->to_rank,
1455                             piece_to_move,colour,board);
1456             break;
1457         case NULL_MOVE:
1458             /* Nothing more. */
1459             break;
1460         case UNKNOWN_MOVE:
1461         default:
1462             Ok = FALSE;
1463             break;
1464         }
1465     }
1466     else{
1467         Ok = FALSE;
1468     }
1469     return Ok;
1470 }
1471
1472         /* Rewrite the list of moves by playing through the game. */
1473 static Boolean
1474 rewrite_moves(Board *board, Move *moves, Boolean null_move_found)
1475 {   Boolean game_ok = TRUE;
1476     Move *move_details = moves;
1477
1478     while(game_ok && (move_details != NULL)){
1479         if(*(move_details->move) != '\0'){
1480             /* See if there are any variations associated with this move. */
1481             if((move_details->Variants != NULL) &&
1482                     GlobalState.keep_variations &&
1483                     !rewrite_variations(board,move_details->Variants, null_move_found)){
1484                 /* Something wrong with the variations. */
1485                 game_ok = FALSE;
1486             }
1487             /* @@@ There was a else-if here; not sure why?! */
1488             if(move_details->class == NULL_MOVE) {
1489                 null_move_found = TRUE;
1490             }
1491             if(rewrite_move(board->to_move,move_details,board, null_move_found)){
1492                 board->to_move = OPPOSITE_COLOUR(board->to_move);
1493
1494                 if(GlobalState.output_evaluation) {
1495                     /* Append an evaluation of the new state of the board
1496                      * with the move having been played.
1497                      */
1498                     append_evaluation(move_details, board);
1499                 }
1500
1501                 if(GlobalState.add_FEN_comments) {
1502                     /* Append a FEN comment with the new state of the board
1503                      * with the move having been played.
1504                      */
1505                     append_FEN_comment(move_details, board);
1506                 }
1507
1508                 move_details = move_details->next;
1509                 if(board->to_move == WHITE){
1510                     board->move_number++;
1511                 }
1512             }
1513             else {
1514                 /* Broken games that are being kept have probably already been
1515                  * reported, so don't repeat the error.
1516                  */
1517                 if(!GlobalState.keep_broken_games) {
1518                     fprintf(GlobalState.logfile,
1519                                     "Failed to rewrite move %u%s %s in the game:\n",
1520                                         board->move_number,
1521                                         (board->to_move == WHITE)?".":"...",
1522                                         move_details->move);
1523                     report_details(GlobalState.logfile);
1524                     print_board(board,GlobalState.logfile);
1525                 }
1526                 game_ok = FALSE;
1527             }
1528         }
1529         else{
1530             /* An empty move. */
1531             fprintf(GlobalState.logfile,
1532                                 "Internal error: Empty move in rewrite_moves.\n");
1533             report_details(GlobalState.logfile);
1534             game_ok = FALSE;
1535         }
1536     }
1537     if(!game_ok && GlobalState.keep_broken_games && move_details != NULL) {
1538         /* Try to place the remaining moves into a comment. */
1539         CommentList *comment = (CommentList* ) MallocOrDie(sizeof(*comment));
1540         /* Break the link from the previous move. */
1541         Move *prev;
1542         StringList *commented_move_list = NULL;
1543
1544         /* Find the move before the current one. */
1545         prev = moves;
1546         while(prev != NULL && prev->next != move_details) {
1547             prev = prev->next;
1548         }
1549         if(prev != NULL) {
1550             prev->next = NULL;
1551         }
1552         while(move_details != NULL) {
1553             commented_move_list = save_string_list_item(commented_move_list, (char *) move_details->move);
1554             if(move_details->next == NULL && prev != NULL) {
1555                 /* Pass the terminating result to prev. */
1556                 prev->terminating_result = move_details->terminating_result;
1557                 move_details->terminating_result = NULL;
1558                 move_details = NULL;
1559             }
1560             else {
1561                 move_details = move_details->next;
1562             }
1563         }
1564         comment->Comment = commented_move_list;
1565         comment->next = NULL;
1566
1567         if(prev != NULL) {
1568             append_comments_to_move(prev, comment);
1569         }
1570     }
1571     return game_ok;
1572 }
1573
1574         /* Rewrite the list of variations.
1575          * Return TRUE if the variation are ok. a position that
1576          */
1577 static Boolean
1578 rewrite_variations(const Board *board,Variation *variation, Boolean null_move_found)
1579 {   Board *copy_board = allocate_new_board();
1580     Boolean variations_ok = TRUE;
1581
1582     while((variation != NULL) && variations_ok){
1583         /* Work on the copy. */
1584         *copy_board = *board;
1585
1586         variations_ok = rewrite_moves(copy_board,variation->moves, null_move_found);
1587         variation = variation->next;
1588     }
1589     (void) free_board((void *)copy_board);
1590     return variations_ok;
1591 }
1592
1593         /* moves contains a complete game score.
1594          * Try to rewrite each move into SAN as it is played on a new board.
1595          * Return the final Board position if the game was rewritten alright,
1596          * NULL otherwise.
1597          */
1598 Board *
1599 rewrite_game(Game *current_game)
1600 {
1601     const char *fen = current_game->tags[FEN_TAG];
1602     Board *board = new_game_board(fen);
1603     Boolean game_ok;
1604
1605     /* No null-move found at the start of the game. */
1606     game_ok = rewrite_moves(board,current_game->moves,FALSE);
1607     if(game_ok){
1608     }
1609     else if(GlobalState.keep_broken_games) {
1610     }
1611     else {
1612         (void) free_board((void *)board);
1613         board = NULL;
1614     }
1615     return board;
1616 }
1617
1618
1619         /* Define a table to hold the positional hash codes of interest. */
1620 #define MAX_CODE 53
1621 static HashLog *codes_of_interest[MAX_CODE];
1622
1623         /* move_details is a variation in which we are interested.
1624          * Generate and store the hash value in codes_of_interest.
1625          */
1626 void
1627 store_hash_value(Move *move_details,const char *fen)
1628 {   Move *move = move_details;
1629     Board *board = new_game_board(fen);
1630     Boolean Ok = TRUE;
1631
1632     while((move != NULL) && Ok){
1633         /* Reset print_move number if a variation was printed. */
1634         if(*(move->move) == '\0'){
1635             /* A comment node, not a proper move. */
1636            move = move->next;
1637         }
1638         else if(apply_move(board->to_move,move,board)){
1639            board->to_move = OPPOSITE_COLOUR(board->to_move);
1640            move = move->next;
1641            if(board->to_move == WHITE){
1642                board->move_number++;
1643            }
1644         }
1645         else{
1646             print_error_context(GlobalState.logfile);
1647             fprintf(GlobalState.logfile,"Failed to make move %u%s %s\n",
1648                                 board->move_number,
1649                                 (board->to_move == WHITE)?".":"...",
1650                         move->move);
1651             Ok = FALSE;
1652         }
1653     }
1654
1655     if(!Ok){
1656         exit(1);
1657     }
1658     else{
1659         HashLog *entry = (HashLog *)MallocOrDie(sizeof(*entry));
1660         unsigned ix = board->hash_value % MAX_CODE;
1661
1662         /* We don't include the cumulative hash value as the sequence
1663          * of moves to reach this position is not important.
1664          */
1665         entry->cumulative_hash_value = 0;
1666         entry->final_hash_value = board->hash_value;
1667         /* Link it into the head at this index. */
1668         entry->next = codes_of_interest[ix];
1669         codes_of_interest[ix] = entry;
1670     }
1671     (void) free_board((void *)board);
1672 }
1673
1674         /* Does the current board match a position of interest.
1675          * Look in codes_of_interest for current_hash_value.
1676          */
1677 static Boolean
1678 position_matches(const Board *board)
1679 {
1680     HashCode current_hash_value = board->hash_value;
1681     unsigned ix = current_hash_value % MAX_CODE;
1682     Boolean found = FALSE;
1683     HashLog *entry;
1684
1685     for(entry = codes_of_interest[ix]; !found && (entry != NULL);
1686                         entry = entry->next){
1687         /* We can test against just the position value. */
1688         if(entry->final_hash_value == current_hash_value){
1689             found = TRUE;
1690         }
1691     }
1692     if(!found) {
1693         const char *matching_pattern = matchBoard(board);
1694         found = matching_pattern != NULL;
1695     }
1696     return found;
1697 }
1698
1699     /* Build a basic EPD string from the given board. */
1700 void
1701 build_basic_EPD_string(const Board *board,char *epd)
1702 {   Rank rank;
1703     int ix = 0;
1704     Boolean castling_allowed = FALSE;
1705     for(rank = LASTRANK; rank >= FIRSTRANK; rank--){
1706         Col col;
1707         int consecutive_spaces = 0;
1708         for(col = FIRSTCOL; col <= LASTCOL; col++){
1709             int coloured_piece = board->board[RankConvert(rank)]
1710                                              [ColConvert(col)];
1711             if(coloured_piece != EMPTY){
1712                 if(consecutive_spaces > 0){
1713                     epd[ix] = '0'+consecutive_spaces;
1714                     ix++;
1715                     consecutive_spaces = 0;
1716                 }
1717                 epd[ix] = coloured_piece_to_SAN_letter(coloured_piece);
1718                 ix++;
1719             }
1720             else{
1721                 consecutive_spaces++;
1722             }
1723         }
1724         if(consecutive_spaces > 0){
1725             epd[ix] = '0'+consecutive_spaces;
1726             ix++;
1727         }
1728         /* Terminate the row. */
1729         if(rank != FIRSTRANK){
1730             epd[ix] = '/'; ix++;
1731         }
1732     }
1733     epd[ix] = ' '; ix++;
1734     epd[ix]  = '\0';
1735     epd[ix] = board->to_move == WHITE? 'w' : 'b'; ix++;
1736     epd[ix] = ' '; ix++;
1737
1738     /* Castling details. */
1739     if(board->WKingCastle){
1740         epd[ix] = 'K'; ix++;
1741         castling_allowed = TRUE;
1742     }
1743     if(board->WQueenCastle){
1744         epd[ix] = 'Q'; ix++;
1745         castling_allowed = TRUE;
1746     }
1747     if(board->BKingCastle){
1748         epd[ix] = 'k'; ix++;
1749         castling_allowed = TRUE;
1750     }
1751     if(board->BQueenCastle){
1752         epd[ix] = 'q'; ix++;
1753         castling_allowed = TRUE;
1754     }
1755     if(!castling_allowed){
1756         /* There are no castling rights. */
1757         epd[ix] = '-';
1758         ix++;
1759     }
1760     epd[ix] = ' '; ix++;
1761
1762     /* Enpassant. */
1763     if(board->EnPassant){
1764         epd[ix] = board->ep_col; ix++;
1765         epd[ix] = board->ep_rank; ix++;
1766     }
1767     else{
1768         epd[ix] = '-'; ix++;
1769     }
1770     epd[ix] = '\0';
1771 }
1772
1773     /* Build a FEN string from the given board. */
1774 void
1775 build_FEN_string(const Board *board,char *fen)
1776 {
1777     size_t ix;
1778     int full_move_number =
1779             board->to_move == BLACK ? board->move_number : (board->move_number + 1);
1780
1781     build_basic_EPD_string(board,fen);
1782     /* Append the (pseudo) half move count and the full move count. */
1783     ix = strlen(fen);
1784     fen[ix] = ' '; ix++;
1785
1786     /* Half moves since the last capture or pawn move. */
1787     sprintf(&fen[ix], "%u", board->halfmove_clock);
1788     ix = strlen(fen);
1789     fen[ix] = ' '; ix++;
1790
1791     /* The full move number. */
1792     sprintf(&fen[ix],"%u", full_move_number);
1793 }
1794
1795     /* Append to move_details a FEN comment of the board.
1796      * The board state is immediately following application of the
1797      * given move.
1798      */
1799 static void
1800 append_FEN_comment(Move *move_details, const Board *board)
1801 {
1802     char *FEN_comment = MallocOrDie(FEN_SPACE);
1803     CommentList *comment = (CommentList* ) MallocOrDie(sizeof(*comment));
1804     StringList *current_comment = save_string_list_item(NULL, FEN_comment);
1805
1806     build_FEN_string(board, FEN_comment);
1807     comment->Comment = current_comment;
1808     comment->next = NULL;
1809     append_comments_to_move(move_details, comment);
1810 }
1811
1812     /* Append to move_details an evaluation value for board.
1813      * The board state is immediately following application of the
1814      * given move.
1815      */
1816 static void
1817 append_evaluation(Move *move_details, const Board *board)
1818 {
1819     CommentList *comment = (CommentList* ) MallocOrDie(sizeof(*comment));
1820     /* Space template for the value.
1821      * @@@ There is a buffer-overflow risk here if the evaluation value
1822      * is too large.
1823      */
1824     const char valueSpace[] = "-012456789.00";
1825     char *evaluation = (char *) MallocOrDie(sizeof(valueSpace));
1826     StringList *current_comment;
1827
1828     double value = evaluate(board);
1829
1830     /* @@@ Overflow possible here if the value is too big to fit. */
1831     sprintf(evaluation,"%.2f", value);
1832     if(strlen(evaluation) > strlen(valueSpace)) {
1833         fprintf(GlobalState.logfile,
1834                 "Overflow in evaluation space in append_evaluation()\n");
1835         exit(1);
1836     }
1837
1838     current_comment = save_string_list_item(NULL, evaluation);
1839     comment->Comment = current_comment;
1840     comment->next = NULL;
1841     append_comments_to_move(move_details, comment);
1842 }
1843
1844     /* Append to move_details a comment indicating that this
1845      * move resulted in a positional match.
1846      */
1847 CommentList *
1848 create_match_comment(Move *move_details)
1849 {
1850     /* The comment string. */
1851     char *match_comment = copy_string(GlobalState.position_match_comment);
1852     StringList *current_comment = save_string_list_item(NULL, match_comment);
1853     CommentList *comment = (CommentList* ) MallocOrDie(sizeof(*comment));
1854
1855     comment->Comment = current_comment;
1856     comment->next = NULL;
1857     return comment;
1858 }
1859     /* Return an evaluation of board. */
1860 static double
1861 evaluate(const Board *board)
1862 {
1863     return shannonEvaluation(board);
1864 }
1865
1866     /* Return an evaluation of board based on
1867      * Claude Shannon's technique.
1868      */
1869 static double
1870 shannonEvaluation(const Board *board)
1871 {
1872     MovePair *white_moves, *black_moves;
1873     int whiteMoveCount = 0, blackMoveCount = 0;
1874     int whitePieceCount = 0, blackPieceCount = 0;
1875     double shannonValue = 0.0;
1876
1877     Rank rank;
1878     Col col;
1879
1880     /* Determine the mobilities. */
1881     white_moves = find_all_moves(board, WHITE);
1882     if(white_moves != NULL){
1883         MovePair *m;
1884         for(m = white_moves; m != NULL; m = m->next) {
1885             whiteMoveCount++;
1886         }
1887         free_move_pair_list(white_moves);
1888     }
1889
1890     black_moves = find_all_moves(board, BLACK);
1891     if(black_moves != NULL){
1892         MovePair *m;
1893         for(m = black_moves; m != NULL; m = m->next) {
1894             blackMoveCount++;
1895         }
1896         free_move_pair_list(black_moves);
1897     }
1898
1899
1900     /* Pick up each piece of the required colour. */
1901     for(rank = LASTRANK; rank >= FIRSTRANK; rank--){
1902        short r = RankConvert(rank);
1903        for(col = FIRSTCOL; col <= LASTCOL; col++){
1904            short c = ColConvert(col);
1905            int pieceValue = 0;
1906            Piece occupant = board->board[r][c];
1907            if(occupant != EMPTY) {
1908                /* This square is occupied by a piece of the required colour. */
1909                Piece piece = EXTRACT_PIECE(occupant);
1910
1911                switch(piece){
1912                    case PAWN:
1913                        pieceValue = 1;
1914                        break;
1915                    case BISHOP:
1916                    case KNIGHT:
1917                        pieceValue = 3;
1918                        break;
1919                    case ROOK:
1920                        pieceValue = 5;
1921                        break;
1922                    case QUEEN:
1923                        pieceValue = 9;
1924                        break;
1925                    case KING:
1926                        break;
1927                    default:
1928                        fprintf(GlobalState.logfile,
1929                            "Internal error: unknown piece %d in append_evaluation().\n",
1930                                piece);
1931                }
1932                if(EXTRACT_COLOUR(occupant) == WHITE) {
1933                    whitePieceCount += pieceValue;
1934                }
1935                else {
1936                    blackPieceCount += pieceValue;
1937                }
1938            }
1939        }
1940     }
1941
1942     shannonValue = (whitePieceCount - blackPieceCount) +
1943                    (whiteMoveCount - blackMoveCount) * 0.1;
1944     return shannonValue;
1945 }