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/
24 * These routines are concerned with gathering moves of
25 * the various sorts of variations specified by the -v
26 * and -x flags. In the former case, there are also functions
27 * for checking the moves of a game against the variation
28 * lists that are wanted. Checking of the variations specified
29 * by the -x flag is handled elsewhere by apply_move_list().
49 #include "fenmatcher.h"
51 /* Define a character that can be used in the variations file to
52 * mean that we don't mind what move was played at this point.
55 * means look for all games in which Black playes 1...b6, regardless
56 * of White's first move.
59 /* Define a character that can be used in the variations file to
60 * mean that we do not wish to match a particular move.
63 * means look for games in which Black does not play 2. Nf3 against
64 * the Sicilian defence.
66 #define DISALLOWED_MOVE '!'
68 /* Hold details of a single move within a variation. */
70 /* Characters of the move.
71 * Alternative notations for the same move are separated by
72 * a non-move character, e.g.:
74 * could all be alternatives for the same basic pawn capture.
77 /* If we are interested in matching the moves in any order,
78 * then we need to record whether or not the current move has
79 * been matched or not.
84 /* Hold details of a single variation, with a pointer to
85 * an alternative variation.
87 typedef struct variation_list {
88 /* The list of moves. */
90 /* Keep a count of how many ANY_MOVE moves there are in the move
91 * list for each colour. If these are non-zero then one is used
92 * when a match fails when looking for permutations.
94 unsigned num_white_any_moves;
95 unsigned num_black_any_moves;
96 /* Keep a count of how many DISALLOWED_MOVE moves there are in the move
97 * list for each colour. If these are non-zero then the game
98 * must be searched for them when looking for permutations before
99 * the full search is made.
101 unsigned num_white_disallowed_moves;
102 unsigned num_black_disallowed_moves;
103 /* How many half-moves in the variation? */
105 struct variation_list *next;
108 /* The head of the variations-of-interest list. */
109 static variation_list *games_to_keep = NULL;
111 static Boolean textual_variation_match(const char *variation_move,
112 const unsigned char *actual_move);
114 /*** Functions concerned with reading details of the variations
118 /* Remove any move number prefix from str.
119 * Return NULL if there is no move (only number)
120 * otherwise return the head of the move portion.
123 strip_move_number(char *str)
125 while(isdigit((int) *str)){
141 /* Define values for malloc/realloc allocation. */
142 #define INIT_MOVE_NUMBER 10
143 #define MOVE_INCREMENT 5
145 /* Break up a single line of moves into a list of moves
146 * comprising a variation.
148 static variation_list *
149 compose_variation(char *line)
150 { variation_list *variation;
151 variant_move *move_list;
152 /* Keep track of the number of moves extracted from line. */
153 unsigned num_moves = 0;
154 unsigned max_moves = 0;
157 variation = (variation_list *)MallocOrDie(sizeof(variation_list));
158 /* We don't yet know how many ANY_MOVEs or DISALLOWED_MOVES there
159 * will be in this variation.
161 variation->num_white_any_moves = 0;
162 variation->num_black_any_moves = 0;
163 variation->num_white_disallowed_moves = 0;
164 variation->num_black_disallowed_moves = 0;
165 /* Allocate an initial number of pointers for the moves of the variation. */
166 move_list = (variant_move *) MallocOrDie(INIT_MOVE_NUMBER *
168 max_moves = INIT_MOVE_NUMBER;
169 /* Find the first move. */
170 move = strtok(line," ");
172 if((move = strip_move_number(move)) == NULL){
173 /* Only a move number. */
176 /* See if we need some more space. */
177 if(num_moves == max_moves){
178 move_list = (variant_move *)realloc((void *)move_list,
179 (max_moves+MOVE_INCREMENT) * sizeof(*move_list));
180 if(move_list == NULL){
181 /* Catastrophic failure. */
182 free((void *)variation);
186 max_moves += MOVE_INCREMENT;
189 /* Keep the move and initialise the matched field for
190 * when we start matching games.
192 move_list[num_moves].move = move;
193 move_list[num_moves].matched = FALSE;
194 /* Keep track of moves that will match anything. */
195 if(*move == ANY_MOVE){
196 /* Odd numbered half-moves in the variant list are Black. */
197 if(num_moves & 0x01){
198 variation->num_black_any_moves++;
201 variation->num_white_any_moves++;
203 /* Beware of the potential for false matches. */
204 if(strlen(move) > 1){
205 fprintf(GlobalState.logfile,
206 "Warning: %c in %s should not be followed by additional move text.\n",
208 fprintf(GlobalState.logfile,"It could give false matches.\n");
211 else if(*move == DISALLOWED_MOVE){
212 /* Odd numbered half-moves in the variant list are Black. */
213 if(num_moves & 0x01){
214 variation->num_black_disallowed_moves++;
217 variation->num_white_disallowed_moves++;
221 /* Unadorned move. */
225 move = strtok((char *)NULL," ");
227 variation->moves = move_list;
228 variation->length = num_moves;
229 variation->next = NULL;
233 /* Read each line of input and decompose it into a variation
234 * to be placed in the games_to_keep list.
237 add_textual_variations_from_file(FILE *fpin)
240 while((line = read_line(fpin)) != NULL){
241 add_textual_variation_from_line(line);
245 /* Add the text of the given line to the list of games_to_keep.
248 add_textual_variation_from_line(char *line)
250 if(non_blank_line(line)){
251 variation_list *next_variation = compose_variation(line);
252 if(next_variation != NULL){
253 next_variation->next = games_to_keep;
254 games_to_keep = next_variation;
259 /*** Functions concerned with reading details of the positional
260 *** variations of interest.
263 /* Break up a single line of moves into a list of moves
264 * comprising a positional variation.
265 * In doing so, set GlobalState.depth_of_positional_search
266 * if this variation is longer than the default.
269 compose_positional_variation(char *line)
271 /* Build a linked list of the moves of the variation. */
272 Move *head = NULL, *tail = NULL;
274 /* Keep track of the depth. */
277 move = strtok(line," ");
278 while(Ok && (move != NULL) && (*move != '*')){
279 if((move = strip_move_number(move)) == NULL){
280 /* Only a move number. */
283 Move *next = decode_move((unsigned char *) move);
286 fprintf(GlobalState.logfile,"Failed to identify %s\n",move);
290 /* Chain it on to the list. */
303 /* Pick up the next likely move. */
304 move = strtok(NULL," ");
307 /* Determine whether the depth of this variation exceeds
308 * the current default.
309 * Depth is counted in move pairs.
310 * Add some extras, in order to be surer of catching transpositions.
312 depth = ((depth+1) / 2) + 4;
313 if(depth > GlobalState.depth_of_positional_search){
314 GlobalState.depth_of_positional_search = depth;
319 free_move_list(head);
326 /* Read each line of input and decompose it into a positional variation
327 * to be placed in the list of required hash values.
330 add_positional_variations_from_file(FILE *fpin)
333 while((line = read_line(fpin)) != NULL){
334 add_positional_variation_from_line(line);
339 add_positional_variation_from_line(char *line)
341 if(non_blank_line(line)){
342 Move *next_variation = compose_positional_variation(line);
343 if(next_variation != NULL){
344 /* We need a NULL fen string, because this is from
345 * the initial position.
347 store_hash_value(next_variation,(const char *)NULL);
348 free_move_list(next_variation);
349 /* We need to know globally that positional variations
352 GlobalState.positional_variations = TRUE;
357 /* Treat fen_string as being a position to be matched.
360 add_fen_positional_match(const char *fen_string)
362 store_hash_value((Move *)NULL,fen_string);
363 GlobalState.positional_variations = TRUE;
366 /* Treat fen_pattern as being a position to be matched.
369 add_fen_pattern_match(const char *fen_pattern)
371 add_fen_pattern(fen_pattern);
372 GlobalState.positional_variations = TRUE;
375 /* Roughly define a move character for the purposes of textual
381 return (Boolean) isalpha((int) c) || isdigit((int) c) || (c == '-');
384 /* Return TRUE if there is a match for actual_move in variation_move.
385 * A match means that the string in actual_move is found surrounded
386 * by non-move characters in variation_move. For instance,
387 * variation_move == "Nc6|Nf3|f3" would match
388 * actual_move == "f3" but not actual_move == "c6".
391 textual_variation_match(const char *variation_move,const unsigned char *actual_move)
392 { const char *match_point;
393 Boolean found = FALSE;
395 for(match_point = variation_move; !found && (match_point != NULL); ){
396 /* Try for a match from where we are. */
397 match_point = strstr(match_point,(const char *) actual_move);
398 if(match_point != NULL){
399 /* A possible match. Make sure that the match point
400 * is surrounded by non-move characters so as to be sure
401 * that we haven't picked up part way through a variation string.
405 if(match_point != variation_move){
406 if(move_char(match_point[-1])){
410 if(move_char(match_point[strlen((const char *) actual_move)])){
414 /* Move on the match point and try again. */
415 while(move_char(*match_point)){
425 /*** Functions concerned with matching the moves of the current game
426 *** against the variations of interest.
429 /* Do the moves of the current game match the given variation?
430 * Go for a straight 1-1 match in the ordering, without considering
432 * Return TRUE if so, FALSE otherwise.
435 straight_match(Move *current_game_head, variation_list variation)
437 variant_move *moves_of_the_variation;
438 /* Which is the next move that we wish to match. */
440 unsigned move_index = 0;
441 /* Assume that it matches. */
442 Boolean matches = TRUE;
444 /* Access the head of the current game. */
445 next_move = current_game_head;
446 /* Go for a straight move-by-move match in the order in which
447 * the variation is listed.
448 * Point at the head of the moves list.
450 moves_of_the_variation = variation.moves;
452 while(matches && (next_move != NULL) && (move_index < variation.length)){
453 Boolean this_move_matches;
455 if(*(moves_of_the_variation[move_index].move) == ANY_MOVE){
456 /* Still matching as we don't care what the actual move is. */
460 textual_variation_match(moves_of_the_variation[move_index].move,
462 if(this_move_matches){
463 /* We found a match, check that it isn't disallowed. */
464 if(*moves_of_the_variation[move_index].move == DISALLOWED_MOVE){
465 /* This move is disallowed and implies failure. */
470 if(*moves_of_the_variation[move_index].move != DISALLOWED_MOVE){
471 /* No match found for this move. */
475 /* This is ok, because we didn't want a match. */
480 /* If we are still matching, go on to the next move. */
483 next_move = next_move->next;
486 /* The game could be shorter than the variation, so don't rely
487 * on the fact that matches is still true.
489 matches = (move_index == variation.length);
493 /* Do the moves of the current game match the given variation?
494 * Try all possible orderings for the moves, within the
495 * constraint of proper WHITE/BLACK moves.
496 * The parameter variation is passed as a copy because we modify
497 * the num_ fields within it.
498 * Note that there is a possibility of a false match in this
499 * function if a variant move is specified in a form such as:
501 * This is because the num_ field is set from this on the basis of the
502 * ANY_MOVE character at the start. However, this could also match a
503 * normal move with its c4 component. If it is used for the latter
504 * purpose then it should not count as an any_ move. There is a warning
505 * issued about this when variations are read in.
506 * Return TRUE if we match, FALSE otherwise.
508 * The DISALLOWED_MOVE presents some problems with permutation matches
509 * because an ANY_MOVE could match an otherwise disallowed move. The
510 * approach that has been taken is to cause matching of a single disallowed
511 * move to result in complete failure of the current match.
514 permutation_match(Move *current_game_head, variation_list variation)
515 { variant_move *moves_of_the_variation;
516 /* Which is the next move that we wish to match? */
518 unsigned variant_index = 0;
519 /* Assume that it matches. */
520 Boolean matches = TRUE;
521 /* How many moves have we matched?
522 * When this reaches variation.length we have a full match.
524 unsigned matched_moves = 0;
525 Boolean white_to_move = TRUE;
527 moves_of_the_variation = variation.moves;
528 /* Clear all of the matched fields of the variation. */
529 for(variant_index = 0; variant_index < variation.length; variant_index++){
530 moves_of_the_variation[variant_index].matched = FALSE;
532 /* Access the head of the current game. */
533 next_move = current_game_head;
536 * The first task is to ensure that there are no DISALLOWED_MOVEs in
539 if((variation.num_white_disallowed_moves > 0) ||
540 (variation.num_black_disallowed_moves > 0)){
541 unsigned tested_moves = 0;
542 Boolean disallowed_move_found = FALSE;
544 /* Keep going as long as we still have not found a diallowed move,
545 * we haven't matched the whole variation, and we haven't reached the end of
548 while((!disallowed_move_found) && (tested_moves < variation.length) &&
549 (next_move != NULL)){
550 /* We want to see if next_move is a disallowed move of the variation. */
552 /* White; start with the first move. */
556 /* For a Black move, start at the second half-move in the list, if any. */
559 /* Try each move of the variation in turn, until a match is found. */
560 while((!disallowed_move_found) && (variant_index < variation.length)){
561 if((*moves_of_the_variation[variant_index].move ==
563 (textual_variation_match(
564 moves_of_the_variation[variant_index].move,next_move->move))){
566 disallowed_move_found = TRUE;
568 if(!disallowed_move_found){
569 /* Move on to the next available move -- 2 half moves along. */
573 if(!disallowed_move_found){
574 /* Ok so far, so move on. */
576 white_to_move = !white_to_move;
577 next_move = next_move->next;
580 if(disallowed_move_found){
581 /* This rules out the whole match. */
585 /* In effect, each DISALLOWED_MOVE now becomes an ANY_MOVE. */
586 for(variant_index = 0; variant_index < variation.length; variant_index++){
587 if(*moves_of_the_variation[variant_index].move == DISALLOWED_MOVE){
588 moves_of_the_variation[variant_index].matched = TRUE;
589 if((variant_index & 1) == 0){
590 variation.num_white_any_moves++;
593 variation.num_black_any_moves++;
601 * Having eliminated moves which have been disallowed, try permutations
602 * of the variation against the moves of the current game.
604 /* Access the head of the current game. */
605 next_move = current_game_head;
606 white_to_move = TRUE;
607 /* Keep going as long as we still have matches, we haven't
608 * matched the whole variation, and we haven't reached the end of
611 while(matches && (matched_moves < variation.length) && (next_move != NULL)){
612 /* Assume failure. */
614 /* We want to find next_move in an unmatched move of the variation. */
616 /* Start with the first move. */
620 /* For a Black move, start at the second half-move in the list, if any. */
623 /* Try each move of the variation in turn, until a match is found. */
624 while((!matches) && (variant_index < variation.length)){
625 if(moves_of_the_variation[variant_index].matched){
626 /* We can't try this. */
629 Boolean this_move_matches = textual_variation_match(
630 moves_of_the_variation[variant_index].move,
632 if(this_move_matches){
634 moves_of_the_variation[variant_index].matched = TRUE;
639 /* Move on to the next available move -- 2 half moves along. */
643 /* See if we made a straight match. */
645 /* See if we have some ANY_MOVEs available. */
646 if(white_to_move && (variation.num_white_any_moves > 0)){
648 variation.num_white_any_moves--;
650 else if(!white_to_move && (variation.num_black_any_moves > 0)){
652 variation.num_black_any_moves--;
658 /* We have tried everything, did we succeed? */
660 /* Yes, so move on. */
662 next_move = next_move->next;
663 white_to_move = !white_to_move;
667 /* Ensure that we completed the variation. */
668 matches = matched_moves == (variation.length);
674 /* Determine whether or not the current game is wanted.
675 * It will be if we are either not looking for checkmate-only
676 * games, or if we are and the games does end in checkmate.
679 check_for_only_checkmate(const Move *moves)
681 if(GlobalState.match_only_checkmate) {
682 /* Check that the final move is checkmate. */
683 while(moves != NULL && moves->check_status != CHECKMATE) {
694 /* No restriction to a checkmate game. */
699 /* Determine whether or not the current game is wanted.
700 * It will be if we are either not looking for stalemate-only
701 * games, or if we are and the games does end in stalemate.
704 check_for_only_stalemate(const Board *board, const Move *moves)
706 if(GlobalState.match_only_stalemate) {
707 const Move *move = moves;
709 MovePair *available_moves;
711 /* Check that the final move is not check or checkmate. */
712 while(move->next != NULL) {
715 if(move->check_status != NOCHECK) {
716 /* Cannot be stalemate. */
719 /* See if the player to move has any moves available. */
720 available_moves = find_all_moves(board, board->to_move);
721 if(available_moves == NULL) {
733 /* No restriction to a stalemate game. */
737 /* Determine whether or not the current game is wanted.
738 * It will be if it matches one of the current variations
739 * and its tag details match those that we are interested in.
742 check_textual_variations(Game game_details)
743 { Boolean wanted = FALSE;
744 variation_list *variation;
746 if(games_to_keep != NULL){
747 for(variation = games_to_keep; (variation != NULL) && !wanted;
748 variation = variation->next){
749 if(GlobalState.match_permutations){
750 wanted = permutation_match(game_details.moves,*variation);
753 wanted = straight_match(game_details.moves,*variation);
758 /* There are no variations, assume that selection is done
759 * on the basis of the Details.
766 /* Determine whether the number of moves in this game
767 * is within the bounds of what we want.
770 check_move_bounds(unsigned plycount)
771 { Boolean in_bounds = TRUE;
773 unsigned number_of_moves = (plycount + 1) / 2;
774 if(GlobalState.check_move_bounds){
775 in_bounds = (GlobalState.lower_move_bound <= number_of_moves) &&
776 (number_of_moves <= GlobalState.upper_move_bound);