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