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         else if(GlobalState.output_format == SESSE_BIN){
 718             build_BPFEN_string(board, &move_details->bpfen, &move_details->bpfen_len);
 719         }
 720
 721         if(move_details->class != NULL_MOVE) {
 722             make_move(move_details->class, move_details->from_col,move_details->from_rank,
 723                             move_details->to_col,move_details->to_rank,
 724                             piece_to_move,colour,board);
 725         }
 726         /* See if there are any subsiduary actions. */
 727         switch(move_details->class){
 728             case PAWN_MOVE:
 729             case PIECE_MOVE:
 730             case ENPASSANT_PAWN_MOVE:
 731                 /* Nothing more to do. */
 732                 break;
 733             case PAWN_MOVE_WITH_PROMOTION:
 734                 if(move_details->class == PAWN_MOVE_WITH_PROMOTION){
 735                     if(move_details->promoted_piece != EMPTY){
 736                         /* Now make the promotion. */
 737                         make_move(move_details->class, move_details->to_col,move_details->to_rank,
 738                                   move_details->to_col,move_details->to_rank,
 739                                   move_details->promoted_piece,colour,board);
 740                     }
 741                     else{
 742                         Ok = FALSE;
 743                     }
 744                 }
 745                 break;
 746         case KINGSIDE_CASTLE:
 747             /* Step the Rook to the left of the king. */
 748             piece_to_move = ROOK;
 749             make_move(move_details->class, LASTCOL,move_details->from_rank,move_details->to_col-1,
 750                             move_details->to_rank,
 751                             piece_to_move,colour,board);
 752             break;
 753         case QUEENSIDE_CASTLE:
 754             /* Step the Rook to the right of the king. */
 755             piece_to_move = ROOK;
 756             make_move(move_details->class, FIRSTCOL,move_details->from_rank,move_details->to_col+1,
 757                             move_details->to_rank,
 758                             piece_to_move,colour,board);
 759             break;
 760         case NULL_MOVE:
 761             /* Nothing more to do. */
 762             break;
 763         case UNKNOWN_MOVE:
 764         default:
 765             Ok = FALSE;
 766             break;
 767         }
 768         /* Determine whether or not this move gives check. */
 769         if(Ok){
 770             move_details->check_status =
 771                         king_is_in_check(board,OPPOSITE_COLOUR(colour));
 772             if(move_details->check_status == CHECK){
 773                 /* See whether it is CHECKMATE. */
 774                 if(king_is_in_checkmate(OPPOSITE_COLOUR(colour),board)){
 775                     move_details->check_status = CHECKMATE;
 776                 }
 777             }
 778             /* Handle the halfmove_clock. */
 779             if(piece_to_move == PAWN ||
 780                     move_details->captured_piece != EMPTY) {
 781                 board->halfmove_clock = 0;
 782             }
 783             else {
 784                 board->halfmove_clock++;
 785             }
 786         }
 787     }
 788     else{
 789         Ok = FALSE;
 790     }
 791     return Ok;
 792 }
 793
 794         /* Play out the moves on the given board.
 795          * game_details is updated with the final_ and cumulative_ hash
 796          * values.
 797          * Check move validity unless a NULL_MOVE has been found in this
 798          * variation.
 799          */
 800 static Boolean
 801 play_moves(Game *game_details, Board *board, Move *moves, unsigned max_depth,
 802            Boolean check_move_validity)
 803 {   Boolean game_ok = TRUE;
 804     /* Ply number at which any error was found. */
 805     int error_ply = 0;
 806     /* Force a match if we aren't looking for positional variations. */
 807     Boolean game_matches = GlobalState.positional_variations?FALSE:TRUE;
 808     Move *next_move = moves;
 809     /* Keep track of the final ECO match. */
 810     EcoLog *eco_match = NULL;
 811
 812     /* Try the initial board position for a match.
 813      * This is required because the game might have been set up
 814      * from a FEN string, rather than being the normal starting
 815      * position.
 816      */
 817     if(!game_matches && position_matches(board)){
 818         game_matches = TRUE;
 819         if(GlobalState.add_position_match_comments) {
 820             CommentList *comment = create_match_comment(next_move);
 821             comment->next = game_details->prefix_comment;
 822             game_details->prefix_comment = comment;
 823         }
 824     }
 825     /* Keep going while the game is ok, and we have some more
 826      * moves and we haven't exceeded the search depth without finding
 827      * a match.
 828      */
 829     while(game_ok && (next_move != NULL) &&
 830                 (game_matches || (board->move_number <= max_depth))){
 831         if(*(next_move->move) != '\0'){
 832             /* See if there are any variations associated with this move. */
 833             if((next_move->Variants != NULL) && GlobalState.keep_variations){
 834                 game_matches |= apply_variations(game_details,board,
 835                                                  next_move->Variants,
 836                                                  check_move_validity);
 837             }
 838             /* Now try the main move. */
 839             if(next_move->class == NULL_MOVE) {
 840                 /* We might not be able to check the validity of
 841                  * subsequent moves.
 842                  */
 843 #if 0
 844                 check_move_validity = FALSE;
 845 #endif
 846             }
 847             if(check_move_validity) {
 848                 if(apply_move(board->to_move,next_move,board)){
 849                    /* Don't try for a positional match if we already have one. */
 850                    if(!game_matches && position_matches(board)){
 851                        game_matches = TRUE;
 852                        if(GlobalState.add_position_match_comments) {
 853                            CommentList *comment = create_match_comment(next_move);
 854                            append_comments_to_move(next_move, comment);
 855                        }
 856                    }
 857                    /* Combine this hash value with the cumulative one. */
 858                    game_details->cumulative_hash_value += board->hash_value;
 859                    if(GlobalState.fuzzy_match_duplicates) {
 860                         int plies = 2 * board->move_number - 1;
 861                         /* Check who has just moved. */
 862                         if(board->to_move == BLACK) {
 863                             plies++;
 864                         }
 865                         /* Consider remembering this hash value for fuzzy matches. */
 866                         if(GlobalState.fuzzy_match_depth == plies) {
 867                             /* Remember it. */
 868                             game_details->fuzzy_duplicate_hash = board->hash_value;
 869                         }
 870                    }
 871                    board->to_move = OPPOSITE_COLOUR(board->to_move);
 872                    if(board->to_move == WHITE){
 873                        board->move_number++;
 874                    }
 875                    if(GlobalState.add_ECO && !GlobalState.parsing_ECO_file){
 876                        int half_moves = half_moves_played(board);
 877                        EcoLog *entry = eco_matches(
 878                                board->hash_value,
 879                                game_details->cumulative_hash_value,
 880                                half_moves);
 881                        if(entry != NULL){
 882                            /* Consider keeping the match.
 883                             * Could try to avoid spurious matches which become
 884                             * more likely with larger ECO files and
 885                             * the longer a game goes on.
 886                             * Could be mitigated partly by preferring
 887                             * an ECO line of exactly the same length as
 888                             * the current game line.
 889                             * Not currently implemented.
 890                             */
 891                            if(eco_match == NULL){
 892                                /* We don't have one yet. */
 893                                eco_match = entry;
 894                            }
 895                            else {
 896                                /* Keep it anyway.
 897                                 * This logic always prefers a longer match
 898                                 * to a shorter, irrespective of whether
 899                                 * either match is exact or not.
 900                                 * This logic was followed in versions
 901                                 * up to and including v13.8.
 902                                 */
 903                                eco_match = entry;
 904                            }
 905                        }
 906                        next_move->eco = eco_match;
 907                    }
 908                    next_move = next_move->next;
 909                 }
 910                 else{
 911                     print_error_context(GlobalState.logfile);
 912                     fprintf(GlobalState.logfile,
 913                                     "Failed to make move %u%s %s in the game:\n",
 914                                     board->move_number,
 915                                     (board->to_move == WHITE)?".":"...",
 916                                     next_move->move);
 917                     print_board(board,GlobalState.logfile);
 918                     report_details(GlobalState.logfile);
 919                     game_ok = FALSE;
 920                     /* Work out where the error was. */
 921                     error_ply = 2 * board->move_number - 1;
 922                     /* Check who has just moved. */
 923                     if(board->to_move == BLACK) {
 924                         error_ply++;
 925                     }
 926                 }
 927             }
 928             else {
 929                 /* Go through the motions as if the move were checked. */
 930                board->to_move = OPPOSITE_COLOUR(board->to_move);
 931                if(board->to_move == WHITE){
 932                    board->move_number++;
 933                }
 934                next_move = next_move->next;
 935             }
 936         }
 937         else{
 938             /* An empty move. */
 939             fprintf(GlobalState.logfile,
 940                         "Internal error: Empty move in play_moves.\n");
 941             report_details(GlobalState.logfile);
 942             game_ok = FALSE;
 943             /* Work out where the error was. */
 944             error_ply = 2 * board->move_number - 1;
 945             /* Check who has just moved. */
 946             if(board->to_move == BLACK) {
 947                 error_ply++;
 948             }
 949         }
 950     }
 951     if(game_ok){
 952         if(eco_match != NULL){
 953            /* Free any details of the old one. */
 954            if(game_details->tags[ECO_TAG] != NULL){
 955                (void) free((void *) game_details->tags[ECO_TAG]);
 956                game_details->tags[ECO_TAG] = NULL;
 957            }
 958            if(game_details->tags[OPENING_TAG] != NULL){
 959                (void) free((void *)game_details->tags[OPENING_TAG]);
 960                game_details->tags[OPENING_TAG] = NULL;
 961            }
 962            if(game_details->tags[VARIATION_TAG] != NULL){
 963                (void) free((void *)game_details->tags[VARIATION_TAG]);
 964                game_details->tags[VARIATION_TAG] = NULL;
 965            }
 966            if(game_details->tags[SUB_VARIATION_TAG] != NULL){
 967                (void) free((void *)game_details->tags[SUB_VARIATION_TAG]);
 968                game_details->tags[SUB_VARIATION_TAG] = NULL;
 969            }
 970            /* Add in the new one. */
 971            if(eco_match->ECO_tag != NULL){
 972                game_details->tags[ECO_TAG] = copy_string(eco_match->ECO_tag);
 973            }
 974            if(eco_match->Opening_tag != NULL){
 975                game_details->tags[OPENING_TAG] = copy_string(eco_match->Opening_tag);
 976            }
 977            if(eco_match->Variation_tag != NULL){
 978                game_details->tags[VARIATION_TAG] =
 979                                 copy_string(eco_match->Variation_tag);
 980            }
 981            if(eco_match->Sub_Variation_tag != NULL){
 982                game_details->tags[SUB_VARIATION_TAG] =
 983                                 copy_string(eco_match->Sub_Variation_tag);
 984            }
 985         }
 986     }
 987     /* Fill in the hash value of the final position reached. */
 988     game_details->final_hash_value = board->hash_value;
 989     game_details->moves_ok = game_ok;
 990     game_details->error_ply = error_ply;
 991     if(!game_ok){
 992         /* Decide whether to keep it anyway. */
 993         if(GlobalState.keep_broken_games) {
 994         }
 995         else if(GlobalState.positional_variations){
 996         }
 997         else {
 998             /* Only return a match if it genuinely matched a variation
 999              * in which we were interested.
1000              */
1001             /* We can't have found a genuine match. */
1002             game_matches = FALSE;
1003         }
1004     }
1005     return game_matches;
1006 }
1007
1008         /* Play out the moves of an ECO line on the given board.
1009          * game_details is updated with the final_ and cumulative_ hash
1010          * values.
1011          */
1012
1013 static void
1014 play_eco_moves(Game *game_details, Board *board,Move *moves)
1015 {   Boolean game_ok = TRUE;
1016     /* Ply number at which any error was found. */
1017     int error_ply = 0;
1018     Move *next_move = moves;
1019
1020     /* Keep going while the game is ok, and we have some more
1021      * moves and we haven't exceeded the search depth without finding
1022      * a match.
1023      */
1024     while(game_ok && (next_move != NULL)){
1025         if(*(next_move->move) != '\0'){
1026             /* Ignore variations. */
1027             if(apply_move(board->to_move,next_move,board)){
1028                /* Combine this hash value to the cumulative one. */
1029                game_details->cumulative_hash_value += board->hash_value;
1030                board->to_move = OPPOSITE_COLOUR(board->to_move);
1031                if(board->to_move == WHITE){
1032                    board->move_number++;
1033                }
1034                next_move = next_move->next;
1035             }
1036             else{
1037                 print_error_context(GlobalState.logfile);
1038                 fprintf(GlobalState.logfile,
1039                                 "Failed to make move %u%s %s in the game:\n",
1040                                 board->move_number,
1041                                 (board->to_move == WHITE)?".":"...",
1042                                 next_move->move);
1043                 print_board(board,GlobalState.logfile);
1044                 report_details(GlobalState.logfile);
1045                 game_ok = FALSE;
1046                 /* Work out where the error was. */
1047                 error_ply = 2 * board->move_number - 1;
1048                 /* Check who has just moved. */
1049                 if(board->to_move == BLACK) {
1050                     error_ply++;
1051                 }
1052             }
1053         }
1054         else{
1055             /* An empty move. */
1056             fprintf(GlobalState.logfile,
1057                         "Internal error: Empty move in play_eco_moves.\n");
1058             report_details(GlobalState.logfile);
1059             game_ok = FALSE;
1060             /* Work out where the error was. */
1061             error_ply = 2 * board->move_number - 1;
1062             /* Check who has just moved. */
1063             if(board->to_move == BLACK) {
1064                 error_ply++;
1065             }
1066         }
1067     }
1068     /* Fill in the hash value of the final position reached. */
1069     game_details->final_hash_value = board->hash_value;
1070     game_details->moves_ok = game_ok;
1071     game_details->error_ply = error_ply;
1072 }
1073
1074         /* Play out a variation.
1075          * Check move validity unless a NULL_MOVE has been found in this
1076          * variation.
1077          * Return TRUE if the variation matches a position that
1078          * we are looking for.
1079          */
1080 static Boolean
1081 apply_variations(const Game *game_details,const Board *board,Variation *variation,
1082                  Boolean check_move_validity)
1083 {   /* Force a match if we aren't looking for positional variations. */
1084     Boolean variation_matches = GlobalState.positional_variations?FALSE:TRUE;
1085     /* Allocate space for the copies.
1086      * Allocation is done, rather than relying on local copies in the body
1087      * of the loop because the recursive nature of this function has
1088      * resulted in stack overflow on the PC version.
1089      */
1090     Game *copy_game = (Game *) MallocOrDie(sizeof(*copy_game));
1091     Board *copy_board = allocate_new_board();
1092
1093     while(variation != NULL){
1094         /* Work on the copies. */
1095         *copy_game = *game_details;
1096         *copy_board = *board;
1097
1098         /* We only need one variation to match to declare a match.
1099          * Play out the variation to its full depth, because we
1100          * will want the full move information if the main line
1101          * later matches.
1102          */
1103         variation_matches |= play_moves(copy_game,copy_board,variation->moves,
1104                                         DEFAULT_POSITIONAL_DEPTH,
1105                                         check_move_validity);
1106         variation = variation->next;
1107     }
1108     (void) free((void *)copy_game);
1109     (void) free_board((void *)copy_board);
1110     return variation_matches;
1111 }
1112
1113         /* game_details contains a complete move score.
1114          * Try to apply each move on a new board.
1115          * Store in plycount the number of ply played.
1116          * Return TRUE if the game matches a variation that we are
1117          * looking for.
1118          */
1119 Boolean
1120 apply_move_list(Game *game_details,unsigned *plycount)
1121 {   Move *moves = game_details->moves;
1122     Board *board = new_game_board(game_details->tags[FEN_TAG]);
1123     Boolean game_matches;
1124     /* Set the default search depth. */
1125     unsigned max_depth = GlobalState.depth_of_positional_search;
1126
1127     /* Ensure that we have a sensible search depth. */
1128     if(max_depth == 0){
1129         /* No positional variations specified. */
1130         max_depth = DEFAULT_POSITIONAL_DEPTH;
1131     }
1132
1133     /* Start off the cumulative hash value. */
1134     game_details->cumulative_hash_value = 0;
1135
1136     /* Play through the moves and see if we have a match.
1137      * Check move validity.
1138      */
1139     game_matches = play_moves(game_details,board,moves,max_depth,TRUE);
1140
1141     game_details->moves_checked = TRUE;
1142
1143     /* Record how long the game was. */
1144     if(board->to_move == BLACK){
1145         *plycount = 2 * board->move_number - 1;
1146     }
1147     else{
1148         /* This move number hasn't been played. */
1149         *plycount = 2 * (board->move_number - 1);
1150     }
1151
1152     if(game_matches) {
1153          game_matches = check_for_only_stalemate(board, moves);
1154     }
1155
1156     (void) free_board((void *)board);
1157     return game_matches;
1158 }
1159
1160         /* game_details contains a complete move score.
1161          * Try to apply each move on a new board.
1162          * Store in number_of_moves the length of the game.
1163          * Return TRUE if the game is ok.
1164          */
1165 Boolean
1166 apply_eco_move_list(Game *game_details,unsigned *number_of_half_moves)
1167 {   Move *moves = game_details->moves;
1168     Board *board = new_game_board(game_details->tags[FEN_TAG]);
1169
1170     /* Start off the cumulative hash value. */
1171     game_details->cumulative_hash_value = 0;
1172     play_eco_moves(game_details,board,moves);
1173     game_details->moves_checked = TRUE;
1174     /* Record how long the game was. */
1175     *number_of_half_moves = half_moves_played(board);
1176     (void) free_board((void *)board);
1177     return game_details->moves_ok;
1178 }
1179
1180
1181         /* Return the string associated with the given piece. */
1182 const char *
1183 piece_str(Piece piece)
1184 {
1185     if(piece < NUM_PIECE_VALUES){
1186         return output_piece_characters[piece];
1187     }
1188     else{
1189         return "?";
1190     }
1191 }
1192
1193         /* Rewrite move_details->move according to the details held
1194          * within the structure and the current state of the board.
1195          */
1196 static Boolean
1197 rewrite_SAN_string(Colour colour,Move *move_details, Board *board)
1198 {   Boolean Ok = TRUE;
1199
1200     if(move_details == NULL){
1201         /* Shouldn't happen. */
1202         fprintf(GlobalState.logfile,
1203                 "Internal error: NULL move details in rewrite_SAN_string.\n");
1204         Ok = FALSE;
1205     }
1206     else if(move_details->move[0] == '\0'){
1207         /* Shouldn't happen. */
1208         fprintf(GlobalState.logfile,"Empty move in rewrite_SAN_string.\n");
1209         Ok = FALSE;
1210     }
1211     else{
1212         const unsigned char *move = move_details->move;
1213         MoveClass class = move_details->class;
1214         MovePair *move_list = NULL;
1215         Col to_col = move_details->to_col;
1216         Rank to_rank = move_details->to_rank;
1217         unsigned char new_move_str[MAX_MOVE_LEN+1] = "";
1218
1219         switch(class){
1220             case PAWN_MOVE:
1221             case ENPASSANT_PAWN_MOVE:
1222             case PAWN_MOVE_WITH_PROMOTION:
1223                 move_list = find_pawn_moves(move_details->from_col,
1224                                                 '0',to_col,to_rank,
1225                                                 colour,board);
1226                 break;
1227             case PIECE_MOVE:
1228                 switch(move_details->piece_to_move){
1229                     case KING:
1230                         move_list = find_king_moves(to_col,to_rank,colour,board);
1231                         break;
1232                     case QUEEN:
1233                         move_list = find_queen_moves(to_col,to_rank,colour,board);
1234                         break;
1235                     case ROOK:
1236                         move_list = find_rook_moves(to_col,to_rank,colour,board);
1237                         break;
1238                     case KNIGHT:
1239                         move_list = find_knight_moves(to_col,to_rank,colour,board);
1240                         break;
1241                     case BISHOP:
1242                         move_list = find_bishop_moves(to_col,to_rank,colour,board);
1243                         break;
1244                     default:
1245                         fprintf(GlobalState.logfile,"Unknown piece move %s\n",move);
1246                         Ok = FALSE;
1247                         break;
1248                 }
1249                 break;
1250             case KINGSIDE_CASTLE:
1251             case QUEENSIDE_CASTLE:
1252                 /* No move list to prepare. */
1253                 break;
1254             case NULL_MOVE:
1255                 /* No move list to prepare. */
1256                 break;
1257             case UNKNOWN_MOVE:
1258             default:
1259                 fprintf(GlobalState.logfile,
1260                         "Unknown move class in rewrite_SAN_string(%d).\n",
1261                         move_details->class);
1262                 Ok = FALSE;
1263                 break;
1264         }
1265         if(move_list != NULL){
1266             move_list = exclude_checks(move_details->piece_to_move,colour,
1267                                                 move_list,board);
1268         }
1269         if((move_list == NULL) && (class != KINGSIDE_CASTLE) &&
1270                         (class != QUEENSIDE_CASTLE) && (class != NULL_MOVE)){
1271             Ok = FALSE;
1272         }
1273         /* We should now have enough information in move_details to compose a
1274          * SAN string.
1275          */
1276         if(Ok){
1277             size_t new_move_index = 0;
1278
1279             switch(class){
1280                 case PAWN_MOVE:
1281                 case ENPASSANT_PAWN_MOVE:
1282                 case PAWN_MOVE_WITH_PROMOTION:
1283                     /* See if we need to give the source column. */
1284                     if(move_details->captured_piece != EMPTY){
1285                         new_move_str[new_move_index] = move_details->from_col;
1286                         new_move_index++;
1287                         new_move_str[new_move_index] = 'x';
1288                         new_move_index++;
1289                     }
1290                     else if(move_list->next != NULL){
1291                         new_move_str[new_move_index] = move_details->from_col;
1292                         new_move_index++;
1293                     }
1294                     /* Add in the destination. */
1295                     new_move_str[new_move_index] = to_col;
1296                     new_move_index++;
1297                     new_move_str[new_move_index] = to_rank;
1298                     new_move_index++;
1299                     if(class == PAWN_MOVE_WITH_PROMOTION){
1300                         const char *promoted_piece =
1301                                         piece_str(move_details->promoted_piece);
1302                         new_move_str[new_move_index] = '=';
1303                         new_move_index++;
1304                         strcpy((char *) &new_move_str[new_move_index],
1305                                promoted_piece);
1306                         new_move_index += strlen(promoted_piece);
1307                     }
1308                     new_move_str[new_move_index] = '\0';
1309                     break;
1310                 case PIECE_MOVE:
1311                     {   const char *piece = piece_str(move_details->piece_to_move);
1312                         strcpy((char *) &new_move_str[0],piece);
1313                         new_move_index += strlen(piece);
1314                         /* Check for the need to disambiguate. */
1315                         if(move_list->next != NULL){
1316                             /* It is necessary.  Count how many times
1317                              * the from_ col and rank occur in the list
1318                              * of possibles in order to determine which to use
1319                              * for this purpose.
1320                              */
1321                             int col_times = 0, rank_times = 0;
1322                             MovePair *possible;
1323                             Col from_col = move_details->from_col;
1324                             Rank from_rank = move_details->from_rank;
1325
1326                             for(possible = move_list; possible != NULL;
1327                                             possible = possible->next){
1328                                 if(possible->from_col == from_col){
1329                                     col_times++;
1330                                 }
1331                                 if(possible->from_rank == from_rank){
1332                                     rank_times++;
1333                                 }
1334                             }
1335                             if(col_times == 1){
1336                                 /* Use the col. */
1337                                 new_move_str[new_move_index] = from_col;
1338                                 new_move_index++;
1339                             }
1340                             else if(rank_times == 1){
1341                                 /* Use the rank. */
1342                                 new_move_str[new_move_index] = from_rank;
1343                                 new_move_index++;
1344                             }
1345                             else{
1346                                 /* Use both. */
1347                                 new_move_str[new_move_index] = from_col;
1348                                 new_move_index++;
1349                                 new_move_str[new_move_index] = from_rank;
1350                                 new_move_index++;
1351                             }
1352                         }
1353                         /* See if a capture symbol is needed. */
1354                         if(move_details->captured_piece != EMPTY){
1355                             new_move_str[new_move_index] = 'x';
1356                             new_move_index++;
1357                         }
1358                         /* Add in the destination. */
1359                         new_move_str[new_move_index] = to_col;
1360                         new_move_index++;
1361                         new_move_str[new_move_index] = to_rank;
1362                         new_move_index++;
1363                         new_move_str[new_move_index] = '\0';
1364                     }
1365                     break;
1366                 case KINGSIDE_CASTLE:
1367                     strcpy((char *) new_move_str,"O-O");
1368                     break;
1369                 case QUEENSIDE_CASTLE:
1370                     strcpy((char *) new_move_str,"O-O-O");
1371                     break;
1372                 case NULL_MOVE:
1373                     strcpy((char *) new_move_str, (char *) NULL_MOVE_STRING);
1374                     break;
1375                 case UNKNOWN_MOVE:
1376                 default:
1377                     Ok = FALSE;
1378                     break;
1379             }
1380             if(Ok){
1381                 if(move_details->check_status != NOCHECK){
1382                     if(move_details->check_status == CHECK){
1383                         /* It isn't mate. */
1384                         strcat((char *) new_move_str,"+");
1385                     }
1386                     else{
1387                         if(GlobalState.output_format == CM){
1388                             strcat((char *) new_move_str,"++");
1389                         }
1390                         else{
1391                             strcat((char *) new_move_str,"#");
1392                         }
1393                     }
1394                 }
1395             }
1396             /* Update the move_details structure with the new string. */
1397             strcpy((char *) move_details->move,
1398                    (const char *) new_move_str);
1399         }
1400         if(move_list != NULL){
1401             free_move_pair_list(move_list);
1402         }
1403     }
1404     return Ok;
1405 }
1406
1407         /* Rewrite move_details->move and apply the move to board.
1408          * Return TRUE if the move is ok, FALSE otherwise.
1409          */
1410 static Boolean
1411 rewrite_move(Colour colour,Move *move_details, Board *board, Boolean null_move_found)
1412 {   /* Assume success. */
1413     Boolean Ok = TRUE;
1414
1415     if(rewrite_SAN_string(colour,move_details,board)){
1416         Piece piece_to_move = move_details->piece_to_move;
1417
1418         if(move_details->class != NULL_MOVE) {
1419             make_move(move_details->class, move_details->from_col,move_details->from_rank,
1420                             move_details->to_col,move_details->to_rank,
1421                             piece_to_move,colour,board);
1422         }
1423         else {
1424             null_move_found = TRUE;
1425         }
1426         /* See if there are any subsiduary actions. */
1427         switch(move_details->class){
1428             case PAWN_MOVE:
1429             case PIECE_MOVE:
1430             case ENPASSANT_PAWN_MOVE:
1431                 /* Nothing more to do. */
1432                 break;
1433             case PAWN_MOVE_WITH_PROMOTION:
1434                 if(move_details->class == PAWN_MOVE_WITH_PROMOTION){
1435                     if(move_details->promoted_piece != EMPTY){
1436                         /* @@@ Do promoted moves have '+' properly appended? */
1437                         /* Now make the promotion. */
1438                         make_move(move_details->class, move_details->to_col,move_details->to_rank,
1439                                   move_details->to_col,move_details->to_rank,
1440                                   move_details->promoted_piece,colour,board);
1441                     }
1442                     else{
1443                         Ok = FALSE;
1444                     }
1445                 }
1446                 break;
1447         case KINGSIDE_CASTLE:
1448             /* Step the Rook to the left of the king. */
1449             piece_to_move = ROOK;
1450             make_move(move_details->class, LASTCOL,move_details->from_rank,move_details->to_col-1,
1451                             move_details->to_rank,
1452                             piece_to_move,colour,board);
1453             break;
1454         case QUEENSIDE_CASTLE:
1455             /* Step the Rook to the right of the king. */
1456             piece_to_move = ROOK;
1457             make_move(move_details->class, FIRSTCOL,move_details->from_rank,move_details->to_col+1,
1458                             move_details->to_rank,
1459                             piece_to_move,colour,board);
1460             break;
1461         case NULL_MOVE:
1462             /* Nothing more. */
1463             break;
1464         case UNKNOWN_MOVE:
1465         default:
1466             Ok = FALSE;
1467             break;
1468         }
1469     }
1470     else{
1471         Ok = FALSE;
1472     }
1473     return Ok;
1474 }
1475
1476         /* Rewrite the list of moves by playing through the game. */
1477 static Boolean
1478 rewrite_moves(Board *board, Move *moves, Boolean null_move_found)
1479 {   Boolean game_ok = TRUE;
1480     Move *move_details = moves;
1481
1482     while(game_ok && (move_details != NULL)){
1483         if(*(move_details->move) != '\0'){
1484             /* See if there are any variations associated with this move. */
1485             if((move_details->Variants != NULL) &&
1486                     GlobalState.keep_variations &&
1487                     !rewrite_variations(board,move_details->Variants, null_move_found)){
1488                 /* Something wrong with the variations. */
1489                 game_ok = FALSE;
1490             }
1491             /* @@@ There was a else-if here; not sure why?! */
1492             if(move_details->class == NULL_MOVE) {
1493                 null_move_found = TRUE;
1494             }
1495             if(rewrite_move(board->to_move,move_details,board, null_move_found)){
1496                 board->to_move = OPPOSITE_COLOUR(board->to_move);
1497
1498                 if(GlobalState.output_evaluation) {
1499                     /* Append an evaluation of the new state of the board
1500                      * with the move having been played.
1501                      */
1502                     append_evaluation(move_details, board);
1503                 }
1504
1505                 if(GlobalState.add_FEN_comments) {
1506                     /* Append a FEN comment with the new state of the board
1507                      * with the move having been played.
1508                      */
1509                     append_FEN_comment(move_details, board);
1510                 }
1511
1512                 move_details = move_details->next;
1513                 if(board->to_move == WHITE){
1514                     board->move_number++;
1515                 }
1516             }
1517             else {
1518                 /* Broken games that are being kept have probably already been
1519                  * reported, so don't repeat the error.
1520                  */
1521                 if(!GlobalState.keep_broken_games) {
1522                     fprintf(GlobalState.logfile,
1523                                     "Failed to rewrite move %u%s %s in the game:\n",
1524                                         board->move_number,
1525                                         (board->to_move == WHITE)?".":"...",
1526                                         move_details->move);
1527                     report_details(GlobalState.logfile);
1528                     print_board(board,GlobalState.logfile);
1529                 }
1530                 game_ok = FALSE;
1531             }
1532         }
1533         else{
1534             /* An empty move. */
1535             fprintf(GlobalState.logfile,
1536                                 "Internal error: Empty move in rewrite_moves.\n");
1537             report_details(GlobalState.logfile);
1538             game_ok = FALSE;
1539         }
1540     }
1541     if(!game_ok && GlobalState.keep_broken_games && move_details != NULL) {
1542         /* Try to place the remaining moves into a comment. */
1543         CommentList *comment = (CommentList* ) MallocOrDie(sizeof(*comment));
1544         /* Break the link from the previous move. */
1545         Move *prev;
1546         StringList *commented_move_list = NULL;
1547
1548         /* Find the move before the current one. */
1549         prev = moves;
1550         while(prev != NULL && prev->next != move_details) {
1551             prev = prev->next;
1552         }
1553         if(prev != NULL) {
1554             prev->next = NULL;
1555         }
1556         while(move_details != NULL) {
1557             commented_move_list = save_string_list_item(commented_move_list, (char *) move_details->move);
1558             if(move_details->next == NULL && prev != NULL) {
1559                 /* Pass the terminating result to prev. */
1560                 prev->terminating_result = move_details->terminating_result;
1561                 move_details->terminating_result = NULL;
1562                 move_details = NULL;
1563             }
1564             else {
1565                 move_details = move_details->next;
1566             }
1567         }
1568         comment->Comment = commented_move_list;
1569         comment->next = NULL;
1570
1571         if(prev != NULL) {
1572             append_comments_to_move(prev, comment);
1573         }
1574     }
1575     return game_ok;
1576 }
1577
1578         /* Rewrite the list of variations.
1579          * Return TRUE if the variation are ok. a position that
1580          */
1581 static Boolean
1582 rewrite_variations(const Board *board,Variation *variation, Boolean null_move_found)
1583 {   Board *copy_board = allocate_new_board();
1584     Boolean variations_ok = TRUE;
1585
1586     while((variation != NULL) && variations_ok){
1587         /* Work on the copy. */
1588         *copy_board = *board;
1589
1590         variations_ok = rewrite_moves(copy_board,variation->moves, null_move_found);
1591         variation = variation->next;
1592     }
1593     (void) free_board((void *)copy_board);
1594     return variations_ok;
1595 }
1596
1597         /* moves contains a complete game score.
1598          * Try to rewrite each move into SAN as it is played on a new board.
1599          * Return the final Board position if the game was rewritten alright,
1600          * NULL otherwise.
1601          */
1602 Board *
1603 rewrite_game(Game *current_game)
1604 {
1605     const char *fen = current_game->tags[FEN_TAG];
1606     Board *board = new_game_board(fen);
1607     Boolean game_ok;
1608
1609     /* No null-move found at the start of the game. */
1610     game_ok = rewrite_moves(board,current_game->moves,FALSE);
1611     if(game_ok){
1612     }
1613     else if(GlobalState.keep_broken_games) {
1614     }
1615     else {
1616         (void) free_board((void *)board);
1617         board = NULL;
1618     }
1619     return board;
1620 }
1621
1622
1623         /* Define a table to hold the positional hash codes of interest. */
1624 #define MAX_CODE 53
1625 static HashLog *codes_of_interest[MAX_CODE];
1626
1627         /* move_details is a variation in which we are interested.
1628          * Generate and store the hash value in codes_of_interest.
1629          */
1630 void
1631 store_hash_value(Move *move_details,const char *fen)
1632 {   Move *move = move_details;
1633     Board *board = new_game_board(fen);
1634     Boolean Ok = TRUE;
1635
1636     while((move != NULL) && Ok){
1637         /* Reset print_move number if a variation was printed. */
1638         if(*(move->move) == '\0'){
1639             /* A comment node, not a proper move. */
1640            move = move->next;
1641         }
1642         else if(apply_move(board->to_move,move,board)){
1643            board->to_move = OPPOSITE_COLOUR(board->to_move);
1644            move = move->next;
1645            if(board->to_move == WHITE){
1646                board->move_number++;
1647            }
1648         }
1649         else{
1650             print_error_context(GlobalState.logfile);
1651             fprintf(GlobalState.logfile,"Failed to make move %u%s %s\n",
1652                                 board->move_number,
1653                                 (board->to_move == WHITE)?".":"...",
1654                         move->move);
1655             Ok = FALSE;
1656         }
1657     }
1658
1659     if(!Ok){
1660         exit(1);
1661     }
1662     else{
1663         HashLog *entry = (HashLog *)MallocOrDie(sizeof(*entry));
1664         unsigned ix = board->hash_value % MAX_CODE;
1665
1666         /* We don't include the cumulative hash value as the sequence
1667          * of moves to reach this position is not important.
1668          */
1669         entry->cumulative_hash_value = 0;
1670         entry->final_hash_value = board->hash_value;
1671         /* Link it into the head at this index. */
1672         entry->next = codes_of_interest[ix];
1673         codes_of_interest[ix] = entry;
1674     }
1675     (void) free_board((void *)board);
1676 }
1677
1678         /* Does the current board match a position of interest.
1679          * Look in codes_of_interest for current_hash_value.
1680          */
1681 static Boolean
1682 position_matches(const Board *board)
1683 {
1684     HashCode current_hash_value = board->hash_value;
1685     unsigned ix = current_hash_value % MAX_CODE;
1686     Boolean found = FALSE;
1687     HashLog *entry;
1688
1689     for(entry = codes_of_interest[ix]; !found && (entry != NULL);
1690                         entry = entry->next){
1691         /* We can test against just the position value. */
1692         if(entry->final_hash_value == current_hash_value){
1693             found = TRUE;
1694         }
1695     }
1696     if(!found) {
1697         const char *matching_pattern = matchBoard(board);
1698         found = matching_pattern != NULL;
1699     }
1700     return found;
1701 }
1702
1703     /* Build a basic EPD string from the given board. */
1704 void
1705 build_basic_EPD_string(const Board *board,char *epd)
1706 {   Rank rank;
1707     int ix = 0;
1708     Boolean castling_allowed = FALSE;
1709     for(rank = LASTRANK; rank >= FIRSTRANK; rank--){
1710         Col col;
1711         int consecutive_spaces = 0;
1712         for(col = FIRSTCOL; col <= LASTCOL; col++){
1713             int coloured_piece = board->board[RankConvert(rank)]
1714                                              [ColConvert(col)];
1715             if(coloured_piece != EMPTY){
1716                 if(consecutive_spaces > 0){
1717                     epd[ix] = '0'+consecutive_spaces;
1718                     ix++;
1719                     consecutive_spaces = 0;
1720                 }
1721                 epd[ix] = coloured_piece_to_SAN_letter(coloured_piece);
1722                 ix++;
1723             }
1724             else{
1725                 consecutive_spaces++;
1726             }
1727         }
1728         if(consecutive_spaces > 0){
1729             epd[ix] = '0'+consecutive_spaces;
1730             ix++;
1731         }
1732         /* Terminate the row. */
1733         if(rank != FIRSTRANK){
1734             epd[ix] = '/'; ix++;
1735         }
1736     }
1737     epd[ix] = ' '; ix++;
1738     epd[ix]  = '\0';
1739     epd[ix] = board->to_move == WHITE? 'w' : 'b'; ix++;
1740     epd[ix] = ' '; ix++;
1741
1742     /* Castling details. */
1743     if(board->WKingCastle){
1744         epd[ix] = 'K'; ix++;
1745         castling_allowed = TRUE;
1746     }
1747     if(board->WQueenCastle){
1748         epd[ix] = 'Q'; ix++;
1749         castling_allowed = TRUE;
1750     }
1751     if(board->BKingCastle){
1752         epd[ix] = 'k'; ix++;
1753         castling_allowed = TRUE;
1754     }
1755     if(board->BQueenCastle){
1756         epd[ix] = 'q'; ix++;
1757         castling_allowed = TRUE;
1758     }
1759     if(!castling_allowed){
1760         /* There are no castling rights. */
1761         epd[ix] = '-';
1762         ix++;
1763     }
1764     epd[ix] = ' '; ix++;
1765
1766     /* Enpassant. */
1767     if(board->EnPassant){
1768         epd[ix] = board->ep_col; ix++;
1769         epd[ix] = board->ep_rank; ix++;
1770     }
1771     else{
1772         epd[ix] = '-'; ix++;
1773     }
1774     epd[ix] = '\0';
1775 }
1776
1777     /* Build a FEN string from the given board. */
1778 void
1779 build_FEN_string(const Board *board,char *fen)
1780 {
1781     size_t ix;
1782     int full_move_number =
1783             board->to_move == BLACK ? board->move_number : (board->move_number + 1);
1784
1785     build_basic_EPD_string(board,fen);
1786     /* Append the (pseudo) half move count and the full move count. */
1787     ix = strlen(fen);
1788     fen[ix] = ' '; ix++;
1789
1790     /* Half moves since the last capture or pawn move. */
1791     sprintf(&fen[ix], "%u", board->halfmove_clock);
1792     ix = strlen(fen);
1793     fen[ix] = ' '; ix++;
1794
1795     /* The full move number. */
1796     sprintf(&fen[ix],"%u", full_move_number);
1797 }
1798
1799 void
1800 build_BPFEN_string(const Board *board,char **bpfen, int* bpfen_len)
1801 {   static int bits[256];   /* Max six bits per piece, 32 blanks, and then some. */
1802     int bit_pos = 0;
1803     Rank rank;
1804     int ix = 0;
1805     for(rank = LASTRANK; rank >= FIRSTRANK; rank--){
1806         Col col;
1807         for(col = FIRSTCOL; col <= LASTCOL; col++){
1808             int coloured_piece = board->board[RankConvert(rank)]
1809                                              [ColConvert(col)];
1810             if(coloured_piece == EMPTY){
1811                 bits[bit_pos++] = 0;
1812                 continue;
1813             }
1814             bits[bit_pos++] = 1;
1815             bits[bit_pos++] = (EXTRACT_COLOUR(coloured_piece) == WHITE) ? 1 : 0;
1816             switch(EXTRACT_PIECE(coloured_piece)) {
1817                 case PAWN:
1818                     bits[bit_pos++] = 0;
1819                     break;
1820                 case KNIGHT:
1821                     bits[bit_pos++] = 1;
1822                     bits[bit_pos++] = 0;
1823                     bits[bit_pos++] = 0;
1824                     break;
1825                 case BISHOP:
1826                     bits[bit_pos++] = 1;
1827                     bits[bit_pos++] = 0;
1828                     bits[bit_pos++] = 1;
1829                     break;
1830                 case ROOK:
1831                     bits[bit_pos++] = 1;
1832                     bits[bit_pos++] = 1;
1833                     bits[bit_pos++] = 1;
1834                     bits[bit_pos++] = 0;
1835                     break;
1836                 case QUEEN:
1837                     bits[bit_pos++] = 1;
1838                     bits[bit_pos++] = 1;
1839                     bits[bit_pos++] = 1;
1840                     bits[bit_pos++] = 1;
1841                     bits[bit_pos++] = 0;
1842                     break;
1843                 case KING:
1844                     bits[bit_pos++] = 1;
1845                     bits[bit_pos++] = 1;
1846                     bits[bit_pos++] = 1;
1847                     bits[bit_pos++] = 1;
1848                     bits[bit_pos++] = 1;
1849                     break;
1850             }
1851         }
1852     }
1853     /* Pad board. */
1854     while ((bit_pos % 8) != 0) {
1855         bits[bit_pos++] = 0;
1856     }
1857
1858     /* Non-board information. */
1859     bits[bit_pos++] = (board->to_move == WHITE) ? 0 : 1;
1860     bits[bit_pos++] = board->WKingCastle ? 1 : 0;
1861     bits[bit_pos++] = board->WQueenCastle ? 1 : 0;
1862     bits[bit_pos++] = board->BKingCastle ? 1 : 0;
1863     bits[bit_pos++] = board->BQueenCastle ? 1 : 0;
1864
1865     if(board->EnPassant){
1866         int col_index = board->ep_col - COLBASE;
1867         bits[bit_pos++] = 1;
1868         bits[bit_pos++] = (col_index >> 2) & 1;
1869         bits[bit_pos++] = (col_index >> 1) & 1;
1870         bits[bit_pos++] = col_index & 1;
1871     }
1872     else{
1873         bits[bit_pos++] = 0;
1874     }
1875
1876     /* Pad non-board. */
1877     while ((bit_pos % 8) != 0) {
1878         bits[bit_pos++] = 0;
1879     }
1880
1881     /* Convert from bits to binary form. */
1882     *bpfen = (char *)malloc(bit_pos / 8);
1883     *bpfen_len = bit_pos / 8;
1884
1885     for (ix = 0; ix < bit_pos / 8; ++ix) {
1886         unsigned char ch = 0;
1887         int jx;
1888
1889         for (jx = 0; jx < 8; ++jx) {
1890             ch |= (bits[ix * 8 + jx] << jx);
1891         }
1892
1893         (*bpfen)[ix] = ch;
1894     }
1895 }
1896
1897     /* Append to move_details a FEN comment of the board.
1898      * The board state is immediately following application of the
1899      * given move.
1900      */
1901 static void
1902 append_FEN_comment(Move *move_details, const Board *board)
1903 {
1904     char *FEN_comment = MallocOrDie(FEN_SPACE);
1905     CommentList *comment = (CommentList* ) MallocOrDie(sizeof(*comment));
1906     StringList *current_comment = save_string_list_item(NULL, FEN_comment);
1907
1908     build_FEN_string(board, FEN_comment);
1909     comment->Comment = current_comment;
1910     comment->next = NULL;
1911     append_comments_to_move(move_details, comment);
1912 }
1913
1914     /* Append to move_details an evaluation value for board.
1915      * The board state is immediately following application of the
1916      * given move.
1917      */
1918 static void
1919 append_evaluation(Move *move_details, const Board *board)
1920 {
1921     CommentList *comment = (CommentList* ) MallocOrDie(sizeof(*comment));
1922     /* Space template for the value.
1923      * @@@ There is a buffer-overflow risk here if the evaluation value
1924      * is too large.
1925      */
1926     const char valueSpace[] = "-012456789.00";
1927     char *evaluation = (char *) MallocOrDie(sizeof(valueSpace));
1928     StringList *current_comment;
1929
1930     double value = evaluate(board);
1931
1932     /* @@@ Overflow possible here if the value is too big to fit. */
1933     sprintf(evaluation,"%.2f", value);
1934     if(strlen(evaluation) > strlen(valueSpace)) {
1935         fprintf(GlobalState.logfile,
1936                 "Overflow in evaluation space in append_evaluation()\n");
1937         exit(1);
1938     }
1939
1940     current_comment = save_string_list_item(NULL, evaluation);
1941     comment->Comment = current_comment;
1942     comment->next = NULL;
1943     append_comments_to_move(move_details, comment);
1944 }
1945
1946     /* Append to move_details a comment indicating that this
1947      * move resulted in a positional match.
1948      */
1949 CommentList *
1950 create_match_comment(Move *move_details)
1951 {
1952     /* The comment string. */
1953     char *match_comment = copy_string(GlobalState.position_match_comment);
1954     StringList *current_comment = save_string_list_item(NULL, match_comment);
1955     CommentList *comment = (CommentList* ) MallocOrDie(sizeof(*comment));
1956
1957     comment->Comment = current_comment;
1958     comment->next = NULL;
1959     return comment;
1960 }
1961     /* Return an evaluation of board. */
1962 static double
1963 evaluate(const Board *board)
1964 {
1965     return shannonEvaluation(board);
1966 }
1967
1968     /* Return an evaluation of board based on
1969      * Claude Shannon's technique.
1970      */
1971 static double
1972 shannonEvaluation(const Board *board)
1973 {
1974     MovePair *white_moves, *black_moves;
1975     int whiteMoveCount = 0, blackMoveCount = 0;
1976     int whitePieceCount = 0, blackPieceCount = 0;
1977     double shannonValue = 0.0;
1978
1979     Rank rank;
1980     Col col;
1981
1982     /* Determine the mobilities. */
1983     white_moves = find_all_moves(board, WHITE);
1984     if(white_moves != NULL){
1985         MovePair *m;
1986         for(m = white_moves; m != NULL; m = m->next) {
1987             whiteMoveCount++;
1988         }
1989         free_move_pair_list(white_moves);
1990     }
1991
1992     black_moves = find_all_moves(board, BLACK);
1993     if(black_moves != NULL){
1994         MovePair *m;
1995         for(m = black_moves; m != NULL; m = m->next) {
1996             blackMoveCount++;
1997         }
1998         free_move_pair_list(black_moves);
1999     }
2000
2001
2002     /* Pick up each piece of the required colour. */
2003     for(rank = LASTRANK; rank >= FIRSTRANK; rank--){
2004        short r = RankConvert(rank);
2005        for(col = FIRSTCOL; col <= LASTCOL; col++){
2006            short c = ColConvert(col);
2007            int pieceValue = 0;
2008            Piece occupant = board->board[r][c];
2009            if(occupant != EMPTY) {
2010                /* This square is occupied by a piece of the required colour. */
2011                Piece piece = EXTRACT_PIECE(occupant);
2012
2013                switch(piece){
2014                    case PAWN:
2015                        pieceValue = 1;
2016                        break;
2017                    case BISHOP:
2018                    case KNIGHT:
2019                        pieceValue = 3;
2020                        break;
2021                    case ROOK:
2022                        pieceValue = 5;
2023                        break;
2024                    case QUEEN:
2025                        pieceValue = 9;
2026                        break;
2027                    case KING:
2028                        break;
2029                    default:
2030                        fprintf(GlobalState.logfile,
2031                            "Internal error: unknown piece %d in append_evaluation().\n",
2032                                piece);
2033                }
2034                if(EXTRACT_COLOUR(occupant) == WHITE) {
2035                    whitePieceCount += pieceValue;
2036                }
2037                else {
2038                    blackPieceCount += pieceValue;
2039                }
2040            }
2041        }
2042     }
2043
2044     shannonValue = (whitePieceCount - blackPieceCount) +
2045                    (whiteMoveCount - blackMoveCount) * 0.1;
2046     return shannonValue;
2047 }