git.sesse.net Git - pgn-extract/blob - eco.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 "tokens.h"
  33 #include "taglist.h"
  34 #include "lex.h"
  35 #include "eco.h"
  36 #include "apply.h"
  37
  38 /* Place a limit on how distant a position may be from the ECO line
  39  * it purports to match. This is to try to stop collisions way past
  40  * where the line could still be active.
  41  */
  42 #define ECO_HALF_MOVE_LIMIT 6
  43 /* Keep track of the longest ECO line, in half moves, plus
  44  * ECO_HALF_MOVE_LIMIT.
  45  * If a line exceeds this length, don't bother attempting
  46  * a match.
  47  */
  48 static unsigned maximum_half_moves = ECO_HALF_MOVE_LIMIT;
  49
  50 /* Define a table to hold hash values of the ECO positions.
  51  * This is used to enable duplicate detection.
  52  */
  53 #define ECO_TABLE_SIZE 4096
  54 static EcoLog **EcoTable;
  55
  56 #if INCLUDE_UNUSED_FUNCTIONS
  57 static void
  58 dumpEcoTable(void)
  59 {   unsigned ix;
  60     for(ix = 0; ix < ECO_TABLE_SIZE; ix++){
  61         if(EcoTable[ix] != NULL){
  62             EcoLog *entry = NULL;
  63             for(entry = EcoTable[ix]; entry != NULL; entry = entry->next){
  64                 fprintf(stderr,"%s %lu %lu ",entry->ECO_tag,
  65                                 entry->required_hash_value,
  66                                 entry->cumulative_hash_value);
  67             }
  68             fprintf(stderr,"\n");
  69         }
  70     }
  71 }
  72
  73         /* Return at how many points this match works.
  74          *        required_hash_value
  75          *            cumulative_hash_value
  76          * This is a heuristic attempt to permit later
  77          * longer matches to be chosen in preference to
  78          * earlier shorter matches, while avoiding the
  79          * greater probability of false matches when there
  80          * are a lot of ECO lines and we are further into
  81          * a game.
  82          */
  83 static int
  84 eco_match_level(EcoLog *entry,HashCode current_hash_value,
  85                 HashCode cumulative_hash_value,unsigned half_moves_played)
  86 {
  87     int level = 0;
  88     if(entry != NULL){
  89         if(entry->required_hash_value == current_hash_value){
  90             level++;
  91             if(entry->cumulative_hash_value == cumulative_hash_value){
  92             level++;
  93                 if(entry->half_moves == half_moves_played){
  94                     level++;
  95                 }
  96             }
  97         }
  98     }
  99     return level;
 100 }
 101
 102 /* Quality values for aspects of an ECO match.
 103  * Currently unused.
 104  */
 105 static int ECO_REQUIRED_HASH_VALUE = 1;
 106 static int ECO_HALF_MOVE_VALUE = 1;
 107 static int ECO_CUMULATIVE_HASH_VALUE = 0;
 108
 109 /* Rate the quality of the given match.
 110  * Currently unused.
 111  */
 112 static int eco_match_quality(EcoLog* entry,
 113                       HashCode current_hash_value,
 114                       HashCode cumulative_hash_value,
 115                       int half_moves_played)
 116 {
 117     int quality = 0;
 118     if(entry->required_hash_value == current_hash_value){
 119         quality += ECO_REQUIRED_HASH_VALUE;
 120         if(abs(half_moves_played - entry->half_moves) <= ECO_HALF_MOVE_LIMIT) {
 121             quality += ECO_HALF_MOVE_VALUE;
 122         }
 123         if(entry->cumulative_hash_value == cumulative_hash_value){
 124             quality += ECO_CUMULATIVE_HASH_VALUE;
 125         }
 126     }
 127     return quality;
 128 }
 129 #endif
 130
 131 void initEcoTable(void)
 132 {
 133     /* Avoid multiple calls. */
 134     if(EcoTable == NULL){
 135         int i;
 136         EcoTable = (EcoLog **) MallocOrDie(ECO_TABLE_SIZE*sizeof(EcoLog *));
 137
 138         for(i = 0; i < ECO_TABLE_SIZE; i++){
 139             EcoTable[i] = NULL;
 140         }
 141     }
 142 }
 143
 144         /* Enter the ECO details of game into EcoTable.
 145          */
 146 void
 147 save_eco_details(Game game_details,unsigned number_of_half_moves)
 148 {   unsigned ix = game_details.final_hash_value % ECO_TABLE_SIZE;
 149     EcoLog *entry = NULL;
 150     /* Assume that it can be saved: that there is no collision. */
 151     Boolean can_save = TRUE;
 152     /* In an effort to save string space, keep a record of the
 153      * last entry stored, because there is a good chance that it
 154      * will have the same ECO_tag and Opening_tag as the next
 155      * one.
 156      */
 157     static EcoLog *last_entry = NULL;
 158
 159     for(entry = EcoTable[ix]; (entry != NULL) && can_save; entry = entry->next){
 160         if((entry->required_hash_value == game_details.final_hash_value) &&
 161             (entry->half_moves == number_of_half_moves) &&
 162             (entry->cumulative_hash_value == game_details.cumulative_hash_value)){
 163             const char *tag = entry->ECO_tag,
 164                        *opening = entry->Opening_tag,
 165                        *variation = entry->Variation_tag;
 166             if(tag == NULL){
 167                 tag = "";
 168             }
 169             if(opening == NULL){
 170                 opening = "";
 171             }
 172             if(variation == NULL){
 173                 variation = "";
 174             }
 175             fprintf(GlobalState.logfile,"ECO hash collision of ");
 176             fprintf(GlobalState.logfile,"%s %s %s",tag,opening,variation);
 177             fprintf(GlobalState.logfile," against ");
 178             tag = game_details.tags[ECO_TAG];
 179             opening = game_details.tags[OPENING_TAG];
 180             variation = game_details.tags[VARIATION_TAG];
 181             if(tag == NULL){
 182                 tag = "";
 183             }
 184             if(opening == NULL){
 185                 opening = "";
 186             }
 187             if(variation == NULL){
 188                 variation = "";
 189             }
 190             fprintf(GlobalState.logfile,"%s %s %s\n",tag,opening,variation);
 191             fprintf(GlobalState.logfile,"Possible duplicate move sequences.\n");
 192
 193             can_save = FALSE;
 194         }
 195     }
 196
 197     if(can_save){
 198         /* First occurrence, so add it to the log. */
 199         entry = (EcoLog *)MallocOrDie(sizeof(*entry));
 200
 201         entry->required_hash_value = game_details.final_hash_value;
 202         entry->cumulative_hash_value = game_details.cumulative_hash_value;
 203         /* Keep a record of the current move number as a sanity
 204          * check on matches.
 205          */
 206         entry->half_moves = number_of_half_moves;
 207         /* Check for a new greater depth. */
 208         if(number_of_half_moves+ECO_HALF_MOVE_LIMIT > maximum_half_moves){
 209             maximum_half_moves = number_of_half_moves+ECO_HALF_MOVE_LIMIT;
 210         }
 211         if(game_details.tags[ECO_TAG] != NULL){
 212             if((last_entry != NULL) && (last_entry->ECO_tag != NULL) &&
 213                     (strcmp(last_entry->ECO_tag,game_details.tags[ECO_TAG]) == 0)){
 214                 /* Share the last entry's tag. */
 215                 entry->ECO_tag = last_entry->ECO_tag;
 216             }
 217             else{
 218                 entry->ECO_tag = copy_string(game_details.tags[ECO_TAG]);
 219             }
 220         }
 221         else{
 222             entry->ECO_tag = NULL;
 223         }
 224         if(game_details.tags[OPENING_TAG] != NULL){
 225             if((last_entry != NULL) && (last_entry->Opening_tag != NULL) &&
 226                     (strcmp(last_entry->Opening_tag,
 227                                         game_details.tags[OPENING_TAG]) == 0)){
 228                 /* Share the last entry's tag. */
 229                 entry->Opening_tag = last_entry->Opening_tag;
 230             }
 231             else{
 232                 entry->Opening_tag = copy_string(game_details.tags[OPENING_TAG]);
 233             }
 234         }
 235         else{
 236             entry->Opening_tag = NULL;
 237         }
 238         if(game_details.tags[VARIATION_TAG] != NULL){
 239             entry->Variation_tag = copy_string(game_details.tags[VARIATION_TAG]);
 240         }
 241         else{
 242             entry->Variation_tag = NULL;
 243         }
 244         if(game_details.tags[SUB_VARIATION_TAG] != NULL){
 245             entry->Sub_Variation_tag =
 246                         copy_string(game_details.tags[SUB_VARIATION_TAG]);
 247         }
 248         else{
 249             entry->Sub_Variation_tag = NULL;
 250         }
 251         /* Link it into the head at this index. */
 252         entry->next =  EcoTable[ix];
 253         EcoTable[ix] = entry;
 254         /* Keep this one for next time around. */
 255         last_entry = entry;
 256     }
 257 }
 258
 259
 260         /* Look in EcoTable for current_hash_value.
 261          * Use cumulative_hash_value to refine the match.
 262          * An exact match is preferable to a partial match.
 263          */
 264 EcoLog *
 265 eco_matches(HashCode current_hash_value, HashCode cumulative_hash_value,
 266             unsigned half_moves_played)
 267 {
 268     EcoLog *possible = NULL;
 269
 270     /* Don't bother trying if we are too far on in the game.  */
 271     if(half_moves_played <= maximum_half_moves){
 272         /* Where to look. */
 273         unsigned ix = current_hash_value % ECO_TABLE_SIZE;
 274         EcoLog *entry;
 275
 276         for(entry = EcoTable[ix]; entry != NULL; entry = entry->next){
 277             if(entry->required_hash_value == current_hash_value){
 278                 /* See if we have a full match. */
 279                 if(half_moves_played == entry->half_moves &&
 280                        entry->cumulative_hash_value == cumulative_hash_value){
 281                     return entry;
 282                 }
 283                 else if(abs(half_moves_played-entry->half_moves) <=
 284                             ECO_HALF_MOVE_LIMIT){
 285                         /* Retain this as a possible. */
 286                         possible = entry;
 287                 }
 288                 else{
 289                     /* Ignore it, as the lines are too distant. */
 290                 }
 291             }
 292         }
 293     }
 294     return possible;
 295 }
 296
 297         /* Depending upon the ECO_level and the eco string of the
 298          * current game, open the correctly named ECO file.
 299          */
 300 FILE *
 301 open_eco_output_file(EcoDivision ECO_level,const char *eco)
 302 {   /* Allow space for the maximum number of
 303      * ECO digits plus a .pgn suffix.
 304      */
 305     static const char suffix[] = ".pgn";
 306     enum { MAXNAME = MAX_ECO_LEVEL+sizeof(suffix)-1 };
 307     static char filename[MAXNAME+1];
 308
 309     if((eco == NULL) || !isalpha((int) *eco)){
 310         strcpy(filename,"noeco.pgn");
 311     }
 312     else if(ECO_level == DONT_DIVIDE){
 313        fprintf(GlobalState.logfile,
 314            "Internal error: ECO division in open_eco_output_file\n");
 315        strcpy(filename,"noeco");
 316     }
 317     else if(ECO_level == DONT_DIVIDE){
 318        fprintf(GlobalState.logfile,
 319            "Internal error: ECO division in open_eco_output_file\n");
 320        strcpy(filename,"noeco");
 321     }
 322     else{
 323        strncpy(filename,eco,ECO_level);
 324        filename[ECO_level] = '\0';
 325        strcat(filename,suffix);
 326     }
 327     return must_open_file(filename,"a");
 328 }