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)
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.
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.
18 * David Barnes may be contacted as D.J.Barnes@kent.ac.uk
19 * http://www.cs.kent.ac.uk/people/staff/djb/
40 * Code to handle specifications describing the state of the board
41 * in terms of numbers of pieces and material balance between opponents.
43 * Games are then matched against these specifications.
46 /* Define a type to represent classes of occurrance. */
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
54 /* Define a structure to hold details on the occurrances of
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.
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.
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.
76 unsigned match_depth[2];
77 struct ending_details *next;
80 /* Keep a list of endings to be found. */
81 static Ending_details *endings_to_match = NULL;
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
86 /* Define pseudo-letter for minor pieces, used later. */
87 #define MINOR_PIECE 'L'
90 is_English_piece(char c)
91 { Piece piece = EMPTY;
116 /* Initialise the count of required pieces prior to reading
119 static Ending_details *
120 new_ending_details(void)
121 { Ending_details *details = (Ending_details *) MallocOrDie(sizeof(Ending_details));
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;
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;
140 /* Assume that the match must always have a depth of at least two for
141 * two half-move stability.
143 details->move_depth = 2;
144 details->next = NULL;
149 extract_combination(const char *p,Occurs *p_occurs, int *p_number, const char *line)
151 Occurs occurs = EXACTLY;
154 if(isdigit((int) *p)){
155 /* Only single digits are allowed. */
158 if(isdigit((int) *p)){
159 fprintf(GlobalState.logfile,"Number > 9 is too big in %s.\n",
161 while(isdigit((int) *p)){
168 /* Look for trailing annotations. */
172 occurs = NUM_OR_MORE;
176 occurs = NUM_OR_MORE;
180 occurs = NUM_OR_LESS;
185 occurs = NUM_OR_LESS;
195 occurs = SAME_AS_OPPONENT;
199 occurs = NOT_SAME_AS_OPPONENT;
204 occurs = LESS_EQ_THAN_OPPONENT;
208 occurs = LESS_THAN_OPPONENT;
214 occurs = MORE_EQ_THAN_OPPONENT;
218 occurs = MORE_THAN_OPPONENT;
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).
241 * The basic syntax for a piece description is:
242 * piece [number] [occurs]
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)
249 extract_piece_information(const char *line,Ending_details *details,Colour colour)
250 { const char *p = line;
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;
261 /* Skip over the piece. */
263 p = extract_combination(p,&occurs,&number,line);
265 if((piece == KING) && (number != 1)){
266 fprintf(GlobalState.logfile,"A king must occur exactly once.\n");
269 else if((piece == PAWN) && (number > 8)){
270 fprintf(GlobalState.logfile,
271 "No more than 8 pawns are allowed.\n");
274 details->num_pieces[colour][piece] = number;
275 details->occurs[colour][piece] = occurs;
281 else if(isalpha((int) *p) && (toupper((int) *p) == MINOR_PIECE)){
283 p = extract_combination(p,&occurs,&number,line);
285 details->num_minor_pieces[colour] = number;
286 details->minor_occurs[colour] = occurs;
293 fprintf(GlobalState.logfile,"Unknown symbol at %s\n", p);
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",
309 fprintf(GlobalState.logfile,
310 "In a single set it is advisable to stick to either L or B and/or N.\n");
321 decompose_line(const char *line,Ending_details *details)
322 { const char *p = line;
325 /* Skip initial space. */
326 while(isspace((int) *p)){
330 /* Look for a move depth. */
331 if(isdigit((int) *p)){
336 while(isdigit((int) *p)){
337 depth = (depth*10)+(*p-'0');
340 while(isspace((int) *p)){
343 details->move_depth = depth;
346 /* Extract two pairs of piece information. */
347 p = extract_piece_information(p,details,WHITE);
349 while((*p != '\0') && isspace((int) *p)){
353 p = extract_piece_information(p,details,BLACK);
356 /* No explicit requirements for the other colour. */
359 for(piece = PAWN; piece <= KING; piece++){
360 details->num_pieces[BLACK][piece] = 0;
361 details->occurs[BLACK][piece] = NUM_OR_MORE;
363 details->num_pieces[BLACK][KING] = 1;
364 details->occurs[BLACK][KING] = EXACTLY;
368 /* Allow trailing text as a comment. */
376 /* A new game to be looked for. Indicate that we have not
377 * started matching any yet.
380 reset_match_depths(Ending_details *endings)
382 for(; endings != NULL; endings = endings->next){
383 endings->match_depth[WHITE] = 0;
384 endings->match_depth[BLACK] = 0;
388 /* Try to find a match for the given number of piece details. */
390 piece_match(int num_available,int num_to_find, int num_opponents, Occurs occurs)
391 { Boolean match = FALSE;
395 match = num_available == num_to_find;
398 match = num_available >= num_to_find;
401 match = num_available <= num_to_find;
403 case SAME_AS_OPPONENT:
404 match = num_available == num_opponents;
406 case NOT_SAME_AS_OPPONENT:
407 match = num_available != num_opponents;
409 case LESS_THAN_OPPONENT:
410 match = (num_available+num_to_find) <= num_opponents;
412 case MORE_THAN_OPPONENT:
413 match = (num_available-num_to_find) >= num_opponents;
415 case LESS_EQ_THAN_OPPONENT:
416 /* This means exactly num_to_find less than the
419 match = (num_available+num_to_find) == num_opponents;
421 case MORE_EQ_THAN_OPPONENT:
422 /* This means exactly num_to_find greater than the
425 match = (num_available-num_to_find) == num_opponents;
428 fprintf(GlobalState.logfile,
429 "Inconsistent state %d in piece_match.\n",occurs);
435 /* Try to find a match against one player's pieces in the piece_set_colour
436 * set of details_to_find.
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;
444 /* Determine whether we failed on a match for minor pieces or not. */
445 Boolean minor_failure = FALSE;
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];
454 match = piece_match(num_available,num_to_find,num_opponents,occurs);
456 if((piece == KNIGHT) || (piece == BISHOP)){
457 minor_failure = TRUE;
458 /* Carry on trying to match. */
462 minor_failure = FALSE;
467 /* Ensure that the minor pieces match if there is a minor pieces
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];
473 if((num_to_find > 0) || (occurs != EXACTLY)){
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];
480 match = piece_match(num_available,num_to_find,num_opponents,occurs);
482 else if(minor_failure){
483 /* We actually failed with proper matching of individual minor
484 * pieces, and no minor match fixup is possible.
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.
499 ending_match(Ending_details *details_to_find, int num_pieces[2][NUM_PIECE_VALUES],
501 { Boolean match = TRUE;
502 Colour piece_set_colour = WHITE;
504 match = piece_set_match(details_to_find,num_pieces,game_colour,
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,
511 /* Reset colour to its original value. */
512 game_colour = OPPOSITE_COLOUR(game_colour);
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. */
523 /* Reset the match counter. */
524 details_to_find->match_depth[game_colour] = 0;
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. */
543 unsigned move_number = 1;
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
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.
557 game_matches = ending_match(details_to_find,num_pieces,WHITE) |
558 ending_match(details_to_find,num_pieces,BLACK);
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]--;
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]--;
571 colour = OPPOSITE_COLOUR(colour);
572 next_move = next_move->next;
579 fprintf(GlobalState.logfile,
580 "Internal error: Empty move in look_for_ending.\n");
586 See whether a matching comment is required.
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);
597 game_matches = FALSE;
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;
608 for(details = endings_to_match; !matches && (details != NULL);
609 details = details->next){
610 matches = look_for_ending(moves,details);
616 process_ending_line(const char *line)
619 if(non_blank_line(line)){
620 Ending_details *details = new_ending_details();
622 if(decompose_line(line,details)){
623 /* Add it on to the list. */
624 details->next = endings_to_match;
625 endings_to_match = details;
635 build_endings(const char *infile)
636 { FILE *fp = fopen(infile,"r");
640 fprintf(GlobalState.logfile,"Cannot open %s for reading.\n",infile);
645 while((line = read_line(fp)) != NULL){
646 Ok &= process_ending_line(line);