git.sesse.net Git - pgn-extract/blob - end.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 "end.h"
  32 #include "lines.h"
  33 #include "tokens.h"
  34 #include "taglist.h"
  35 #include "lex.h"
  36 #include "apply.h"
  37 #include "grammar.h"
  38
  39 /**
  40  * Code to handle specifications describing the state of the board
  41  * in terms of numbers of pieces and material balance between opponents.
  42  *
  43  * Games are then matched against these specifications.
  44  */
  45
  46 /* Define a type to represent classes of occurrance. */
  47 typedef enum {
  48     EXACTLY, NUM_OR_MORE, NUM_OR_LESS,
  49     SAME_AS_OPPONENT, NOT_SAME_AS_OPPONENT,
  50     LESS_THAN_OPPONENT, MORE_THAN_OPPONENT,
  51     LESS_EQ_THAN_OPPONENT, MORE_EQ_THAN_OPPONENT
  52 } Occurs;
  53
  54 /* Define a structure to hold details on the occurrances of
  55  * each of the pieces.
  56  */
  57
  58 typedef struct ending_details{
  59     /* There is not a proper distinction between black and white
  60      * but we still need information on the two sets of pieces
  61      * specified in the input file.
  62      */
  63     int num_pieces[2][NUM_PIECE_VALUES];
  64     Occurs occurs[2][NUM_PIECE_VALUES];
  65     /* Numbers of general minor pieces. */
  66     int num_minor_pieces[2];
  67     Occurs minor_occurs[2];
  68     /* How long a given relationship must last to be recognised.
  69      * This value is in half moves.
  70      */
  71     unsigned move_depth;
  72     /* How long a match relationship has been matched.
  73      * This is always reset to zero on failure and incremented on
  74      * success. A full match is only returned when match_depth == move_depth.
  75      */
  76     unsigned match_depth[2];
  77     struct ending_details *next;
  78 } Ending_details;
  79
  80 /* Keep a list of endings to be found. */
  81 static Ending_details *endings_to_match = NULL;
  82
  83         /* What kind of piece is the character, c, likely to represent?
  84          * NB: This is NOT the same as is_piece() in decode.c
  85          */
  86 /* Define pseudo-letter for minor pieces, used later. */
  87 #define MINOR_PIECE 'L'
  88
  89 static Piece
  90 is_English_piece(char c)
  91 {   Piece piece = EMPTY;
  92
  93     switch(c){
  94         case 'K': case 'k':
  95             piece = KING;
  96             break;
  97         case 'Q': case 'q':
  98             piece = QUEEN;
  99             break;
 100         case 'R': case 'r':
 101             piece = ROOK;
 102             break;
 103         case 'N': case 'n':
 104             piece = KNIGHT;
 105             break;
 106         case 'B': case 'b':
 107             piece = BISHOP;
 108             break;
 109         case 'P': case 'p':
 110             piece = PAWN;
 111             break;
 112     }
 113     return piece;
 114 }
 115
 116         /* Initialise the count of required pieces prior to reading
 117          * in the data.
 118          */
 119 static Ending_details *
 120 new_ending_details(void)
 121 {   Ending_details *details = (Ending_details *) MallocOrDie(sizeof(Ending_details));
 122     int c;
 123     Piece piece;
 124
 125     for(piece = PAWN; piece <= KING; piece++){
 126         for(c = 0; c < 2; c++){
 127            details->num_pieces[c][piece] = 0;
 128            details->occurs[c][piece] = EXACTLY;
 129         }
 130     }
 131     /* Fill out some miscellaneous colour based information. */
 132     for(c = 0; c < 2; c++){
 133         /* Only the KING is a requirement for each side. */
 134         details->num_pieces[c][KING] = 1;
 135         details->match_depth[c] = 0;
 136         /* How many general minor pieces to match. */
 137         details->num_minor_pieces[c] = 0;
 138         details->minor_occurs[c] = EXACTLY;
 139     }
 140     /* Assume that the match must always have a depth of at least two for
 141      * two half-move stability.
 142      */
 143     details->move_depth = 2;
 144     details->next = NULL;
 145     return details;
 146 }
 147
 148 static const char *
 149 extract_combination(const char *p,Occurs *p_occurs, int *p_number, const char *line)
 150 {   Boolean Ok = TRUE;
 151     Occurs occurs = EXACTLY;
 152     int number = 1;
 153
 154     if(isdigit((int) *p)){
 155         /* Only single digits are allowed. */
 156         number = *p-'0';
 157         p++;
 158         if(isdigit((int) *p)){
 159             fprintf(GlobalState.logfile,"Number > 9 is too big in %s.\n",
 160                         line);
 161             while(isdigit((int) *p)){
 162                 p++;
 163             }
 164             Ok = FALSE;
 165         }
 166     }
 167     if(Ok){
 168         /* Look for trailing annotations. */
 169         switch(*p){
 170           case '*':
 171             number = 0;
 172             occurs = NUM_OR_MORE;
 173             p++;
 174             break;
 175           case '+':
 176             occurs = NUM_OR_MORE;
 177             p++;
 178             break;
 179           case '-':
 180             occurs = NUM_OR_LESS;
 181             p++;
 182             break;
 183           case '?':
 184             number = 1;
 185             occurs = NUM_OR_LESS;
 186             p++;
 187             break;
 188           case '=':
 189           case '#':
 190           case '<':
 191           case '>':
 192             switch(*p){
 193               case '=':
 194                 p++;
 195                 occurs = SAME_AS_OPPONENT;
 196                 break;
 197               case '#':
 198                 p++;
 199                 occurs = NOT_SAME_AS_OPPONENT;
 200                 break;
 201               case '<':
 202                 p++;
 203                 if(*p == '='){
 204                       occurs = LESS_EQ_THAN_OPPONENT;
 205                       p++;
 206                 }
 207                 else{
 208                       occurs = LESS_THAN_OPPONENT;
 209                 }
 210                 break;
 211               case '>':
 212                 p++;
 213                 if(*p == '='){
 214                       occurs = MORE_EQ_THAN_OPPONENT;
 215                       p++;
 216                 }
 217                 else{
 218                       occurs = MORE_THAN_OPPONENT;
 219                 }
 220                 break;
 221             }
 222             break;
 223         }
 224     }
 225
 226     if(Ok){
 227         *p_occurs = occurs;
 228         *p_number = number;
 229         return p;
 230     }
 231     else{
 232         return NULL;
 233     }
 234 }
 235
 236         /* Extract a single piece set of information from line.
 237          * Return where we have got to as the result.
 238          * colour == WHITE means we are looking at the first set of
 239          * pieces, so some of the notation is illegal (i.e. the relative ops).
 240          *
 241          * The basic syntax for a piece description is:
 242          *        piece [number] [occurs]
 243          * For instance:
 244          *        P2+ Pawn occurs at least twice or more.
 245          *        R= Rook occurs same number of times as opponent. (colour == BLACK)
 246          *        P1>= Exactly one pawn more than the opponent. (colour == BLACK)
 247          */
 248 static const char *
 249 extract_piece_information(const char *line,Ending_details *details,Colour colour)
 250 {   const char *p = line;
 251     Boolean Ok = TRUE;
 252
 253     while(Ok && (*p != '\0') && !isspace((int) *p)){
 254         Piece piece = is_English_piece(*p);
 255         /* By default a piece should occur exactly once. */
 256         Occurs occurs = EXACTLY;
 257         int number = 1;
 258
 259         if(piece != EMPTY){
 260
 261             /* Skip over the piece. */
 262             p++;
 263             p = extract_combination(p,&occurs,&number,line);
 264             if(p != NULL){
 265                 if((piece == KING) && (number != 1)){
 266                     fprintf(GlobalState.logfile,"A king must occur exactly once.\n");
 267                     number = 1;
 268                 }
 269                 else if((piece == PAWN) && (number > 8)){
 270                     fprintf(GlobalState.logfile,
 271                                 "No more than 8 pawns are allowed.\n");
 272                     number = 8;
 273                 }
 274                 details->num_pieces[colour][piece] = number;
 275                 details->occurs[colour][piece] = occurs;
 276             }
 277             else{
 278                 Ok = FALSE;
 279             }
 280         }
 281         else if(isalpha((int) *p) && (toupper((int) *p) == MINOR_PIECE)){
 282             p++;
 283             p = extract_combination(p,&occurs,&number,line);
 284             if(p != NULL){
 285                 details->num_minor_pieces[colour] = number;
 286                 details->minor_occurs[colour] = occurs;
 287             }
 288             else{
 289                 Ok = FALSE;
 290             }
 291         }
 292         else{
 293             fprintf(GlobalState.logfile,"Unknown symbol at %s\n", p);
 294             Ok = FALSE;
 295         }
 296     }
 297     if(Ok){
 298         /* Make a sanity check on the use of minor pieces. */
 299         if((details->num_minor_pieces[colour] > 0) ||
 300                 (details->minor_occurs[colour] != EXACTLY)){
 301             /* Warn about use of BISHOP and KNIGHT letters. */
 302             if((details->num_pieces[colour][BISHOP] > 0) ||
 303                     (details->occurs[colour][BISHOP] != EXACTLY) ||
 304                     (details->num_pieces[colour][KNIGHT] > 0) ||
 305                     (details->occurs[colour][KNIGHT] != EXACTLY)){
 306                 fprintf(GlobalState.logfile,
 307                     "Warning: the mixture of minor pieces in %s is not guaranteed to work.\n",
 308                         line);
 309                 fprintf(GlobalState.logfile,
 310                         "In a single set it is advisable to stick to either L or B and/or N.\n");
 311             }
 312         }
 313       return p;
 314     }
 315     else{
 316       return NULL;
 317     }
 318 }
 319
 320 static Boolean
 321 decompose_line(const char *line,Ending_details *details)
 322 {   const char *p = line;
 323     Boolean Ok = TRUE;
 324
 325     /* Skip initial space. */
 326     while(isspace((int) *p)){
 327         p++;
 328     }
 329
 330     /* Look for a move depth. */
 331     if(isdigit((int) *p)){
 332         unsigned depth;
 333
 334         depth = *p-'0';
 335         p++;
 336         while(isdigit((int) *p)){
 337             depth = (depth*10)+(*p-'0');
 338             p++;
 339         }
 340         while(isspace((int) *p)){
 341             p++;
 342         }
 343         details->move_depth = depth;
 344     }
 345
 346     /* Extract two pairs of piece information. */
 347     p = extract_piece_information(p,details,WHITE);
 348     if(p != NULL){
 349         while((*p != '\0') && isspace((int) *p)){
 350             p++;
 351         }
 352         if(*p != '\0'){
 353             p = extract_piece_information(p,details,BLACK);
 354         }
 355         else{
 356             /* No explicit requirements for the other colour. */
 357             Piece piece;
 358
 359             for(piece = PAWN; piece <= KING; piece++){
 360                details->num_pieces[BLACK][piece] = 0;
 361                details->occurs[BLACK][piece] = NUM_OR_MORE;
 362             }
 363             details->num_pieces[BLACK][KING] = 1;
 364             details->occurs[BLACK][KING] = EXACTLY;
 365         }
 366     }
 367     if(p != NULL){
 368         /* Allow trailing text as a comment. */
 369     }
 370     else{
 371         Ok = FALSE;
 372     }
 373     return Ok;
 374 }
 375
 376         /* A new game to be looked for. Indicate that we have not
 377          * started matching any yet.
 378          */
 379 static void
 380 reset_match_depths(Ending_details *endings)
 381 {
 382     for(; endings != NULL; endings = endings->next){
 383         endings->match_depth[WHITE] = 0;
 384         endings->match_depth[BLACK] = 0;
 385     }
 386 }
 387
 388         /* Try to find a match for the given number of piece details. */
 389 static Boolean
 390 piece_match(int num_available,int num_to_find, int num_opponents, Occurs occurs)
 391 {   Boolean match = FALSE;
 392
 393     switch(occurs){
 394         case EXACTLY:
 395             match = num_available == num_to_find;
 396             break;
 397         case NUM_OR_MORE:
 398             match = num_available >= num_to_find;
 399             break;
 400         case NUM_OR_LESS:
 401             match = num_available <= num_to_find;
 402             break;
 403         case SAME_AS_OPPONENT:
 404             match = num_available == num_opponents;
 405             break;
 406         case NOT_SAME_AS_OPPONENT:
 407             match = num_available != num_opponents;
 408             break;
 409         case LESS_THAN_OPPONENT:
 410             match = (num_available+num_to_find) <= num_opponents;
 411             break;
 412         case MORE_THAN_OPPONENT:
 413             match = (num_available-num_to_find) >= num_opponents;
 414             break;
 415         case LESS_EQ_THAN_OPPONENT:
 416             /* This means exactly num_to_find less than the
 417              * opponent.
 418              */
 419             match = (num_available+num_to_find) == num_opponents;
 420             break;
 421         case MORE_EQ_THAN_OPPONENT:
 422             /* This means exactly num_to_find greater than the
 423              * opponent.
 424              */
 425             match = (num_available-num_to_find) == num_opponents;
 426             break;
 427         default:
 428             fprintf(GlobalState.logfile,
 429                 "Inconsistent state %d in piece_match.\n",occurs);
 430             match = FALSE;
 431     }
 432     return match;
 433 }
 434
 435     /* Try to find a match against one player's pieces in the piece_set_colour
 436      * set of details_to_find.
 437      */
 438 static Boolean
 439 piece_set_match(Ending_details *details_to_find,
 440                 int num_pieces[2][NUM_PIECE_VALUES],
 441                 Colour game_colour, Colour piece_set_colour)
 442 {   Boolean match = TRUE;
 443     Piece piece;
 444     /* Determine whether we failed on a match for minor pieces or not. */
 445     Boolean minor_failure = FALSE;
 446
 447     /* No need to check KING. */
 448     for(piece = PAWN; (piece < KING) && match; piece++){
 449         int num_available = num_pieces[game_colour][piece];
 450         int num_opponents = num_pieces[OPPOSITE_COLOUR(game_colour)][piece];
 451         int num_to_find = details_to_find->num_pieces[piece_set_colour][piece];
 452         Occurs occurs = details_to_find->occurs[piece_set_colour][piece];
 453
 454         match = piece_match(num_available,num_to_find,num_opponents,occurs);
 455         if(!match){
 456             if((piece == KNIGHT) || (piece == BISHOP)){
 457                 minor_failure = TRUE;
 458                 /* Carry on trying to match. */
 459                 match = TRUE;
 460             }
 461             else{
 462                 minor_failure = FALSE;
 463             }
 464         }
 465     }
 466     if(match){
 467         /* Ensure that the minor pieces match if there is a minor pieces
 468          * requirement.
 469          */
 470         int num_to_find = details_to_find->num_minor_pieces[piece_set_colour];
 471         Occurs occurs = details_to_find->minor_occurs[piece_set_colour];
 472
 473         if((num_to_find > 0) || (occurs != EXACTLY)){
 474             int num_available =
 475                         num_pieces[game_colour][BISHOP]+
 476                         num_pieces[game_colour][KNIGHT];
 477             int num_opponents = num_pieces[OPPOSITE_COLOUR(game_colour)][BISHOP]+
 478                                 num_pieces[OPPOSITE_COLOUR(game_colour)][KNIGHT];
 479
 480             match = piece_match(num_available,num_to_find,num_opponents,occurs);
 481         }
 482         else if(minor_failure){
 483             /* We actually failed with proper matching of individual minor
 484              * pieces, and no minor match fixup is possible.
 485              */
 486             match = FALSE;
 487         }
 488         else{
 489             /* Match stands. */
 490         }
 491     }
 492     return match;
 493 }
 494         /* Look for an ending match between current_details and
 495          * details_to_find. Only return TRUE if we have both a match
 496          * and match_depth >= move_depth in details_to_find.
 497          */
 498 static Boolean
 499 ending_match(Ending_details *details_to_find, int num_pieces[2][NUM_PIECE_VALUES],
 500         Colour game_colour)
 501 {   Boolean match = TRUE;
 502     Colour piece_set_colour = WHITE;
 503
 504     match = piece_set_match(details_to_find,num_pieces,game_colour,
 505                                 piece_set_colour);
 506     if(match){
 507         game_colour = OPPOSITE_COLOUR(game_colour);
 508         piece_set_colour = OPPOSITE_COLOUR(piece_set_colour);
 509         match = piece_set_match(details_to_find,num_pieces,game_colour,
 510                                 piece_set_colour);
 511         /* Reset colour to its original value. */
 512         game_colour = OPPOSITE_COLOUR(game_colour);
 513     }
 514
 515     if(match){
 516         details_to_find->match_depth[game_colour]++;
 517         if(details_to_find->match_depth[game_colour] < details_to_find->move_depth){
 518             /* Not a full match yet. */
 519             match = FALSE;
 520         }
 521     }
 522     else{
 523         /* Reset the match counter. */
 524         details_to_find->match_depth[game_colour] = 0;
 525     }
 526     return match;
 527 }
 528
 529 static Boolean
 530 look_for_ending(Move *moves,Ending_details *details_to_find)
 531 {   Boolean game_ok = TRUE;
 532     Boolean game_matches = FALSE;
 533     Boolean match_comment_added = FALSE;
 534     Move *next_move = moves;
 535     Colour colour = WHITE;
 536     /* The initial game position has the full set of piece details. */
 537     int num_pieces[2][NUM_PIECE_VALUES] = {
 538             /* Dummies for OFF and EMPTY at the start. */
 539             /*   P N B R Q K */
 540             {0,0,8,2,2,2,1,1},
 541             {0,0,8,2,2,2,1,1}
 542     };
 543     unsigned move_number = 1;
 544
 545     /* Ensure that all previous match indications are cleared. */
 546     reset_match_depths(endings_to_match);
 547     /* Keep going while the game is ok, and we have some more
 548      * moves and we haven't exceeded the search depth without finding
 549      * a match.
 550      */
 551     while(game_ok && (next_move != NULL) && !game_matches){
 552         /* Try before applying each move.
 553          * Note, that we wish to try both ways around because we might
 554          * have WT,BT WF,BT ... If we don't try BLACK on WHITE success
 555          * then we might miss a match.
 556          */
 557         game_matches = ending_match(details_to_find,num_pieces,WHITE) |
 558                             ending_match(details_to_find,num_pieces,BLACK);
 559         if(!game_matches){
 560             if(*(next_move->move) != '\0'){
 561                /* Remove any captured pieces. */
 562                if(next_move->captured_piece != EMPTY){
 563                    num_pieces[OPPOSITE_COLOUR(colour)][next_move->captured_piece]--;
 564                }
 565                if(next_move->promoted_piece != EMPTY){
 566                    num_pieces[OPPOSITE_COLOUR(colour)][next_move->promoted_piece]++;
 567                    /* Remove the promoting pawn. */
 568                    num_pieces[OPPOSITE_COLOUR(colour)][PAWN]--;
 569                }
 570
 571                colour = OPPOSITE_COLOUR(colour);
 572                next_move = next_move->next;
 573                if(colour == WHITE){
 574                    move_number++;
 575                }
 576             }
 577             else{
 578                 /* An empty move. */
 579                 fprintf(GlobalState.logfile,
 580                             "Internal error: Empty move in look_for_ending.\n");
 581                 game_ok = FALSE;
 582             }
 583         }
 584         else {
 585             /* Match.
 586                See whether a matching comment is required.
 587              */
 588             if(GlobalState.add_position_match_comments && !match_comment_added) {
 589                 if(next_move != NULL) {
 590                     CommentList *comment = create_match_comment(next_move);
 591                     append_comments_to_move(next_move, comment);
 592                 }
 593             }
 594         }
 595     }
 596     if(!game_ok){
 597         game_matches = FALSE;
 598     }
 599     return game_matches;
 600 }
 601
 602 Boolean
 603 check_for_ending(Move *moves)
 604 {   /* Match if there are no endings to match. */
 605     Boolean matches = (endings_to_match == NULL)? TRUE : FALSE;
 606     Ending_details *details;
 607
 608     for(details = endings_to_match; !matches && (details != NULL);
 609                         details = details->next){
 610         matches = look_for_ending(moves,details);
 611     }
 612     return matches;
 613 }
 614
 615 Boolean
 616 process_ending_line(const char *line)
 617 {   Boolean Ok = TRUE;
 618
 619     if(non_blank_line(line)){
 620         Ending_details *details = new_ending_details();
 621
 622         if(decompose_line(line,details)){
 623             /* Add it on to the list. */
 624             details->next = endings_to_match;
 625             endings_to_match = details;
 626         }
 627         else{
 628             Ok = FALSE;
 629         }
 630     }
 631     return Ok;
 632 }
 633
 634 Boolean
 635 build_endings(const char *infile)
 636 {   FILE *fp = fopen(infile,"r");
 637     Boolean Ok = TRUE;
 638
 639     if(fp == NULL){
 640         fprintf(GlobalState.logfile,"Cannot open %s for reading.\n",infile);
 641         exit(1);
 642     }
 643     else{
 644         char *line;
 645         while((line = read_line(fp)) != NULL){
 646             Ok &= process_ending_line(line);
 647             (void) free(line);
 648         }
 649         (void) fclose(fp);
 650     }
 651     return Ok;
 652 }