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