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/
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.
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
48 static unsigned maximum_half_moves = ECO_HALF_MOVE_LIMIT;
50 /* Define a table to hold hash values of the ECO positions.
51 * This is used to enable duplicate detection.
53 #define ECO_TABLE_SIZE 4096
54 static EcoLog **EcoTable;
59 for(ix = 0; ix < ECO_TABLE_SIZE; ix++){
60 if(EcoTable[ix] != 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 : "");
73 #if INCLUDE_UNUSED_FUNCTIONS
74 /* Return at how many points this match works.
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
85 eco_match_level(EcoLog *entry,HashCode current_hash_value,
86 HashCode cumulative_hash_value,unsigned half_moves_played)
90 if(entry->required_hash_value == current_hash_value){
92 if(entry->cumulative_hash_value == cumulative_hash_value){
94 if(entry->half_moves == half_moves_played){
103 /* Quality values for aspects of an ECO match.
106 static int ECO_REQUIRED_HASH_VALUE = 1;
107 static int ECO_HALF_MOVE_VALUE = 1;
108 static int ECO_CUMULATIVE_HASH_VALUE = 0;
110 /* Rate the quality of the given match.
113 static int eco_match_quality(EcoLog* entry,
114 HashCode current_hash_value,
115 HashCode cumulative_hash_value,
116 int half_moves_played)
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;
124 if(entry->cumulative_hash_value == cumulative_hash_value){
125 quality += ECO_CUMULATIVE_HASH_VALUE;
132 void initEcoTable(void)
134 /* Avoid multiple calls. */
135 if(EcoTable == NULL){
137 EcoTable = (EcoLog **) MallocOrDie(ECO_TABLE_SIZE*sizeof(EcoLog *));
139 for(i = 0; i < ECO_TABLE_SIZE; i++){
145 /* Enter the ECO details of game into EcoTable.
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
158 static EcoLog *last_entry = NULL;
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;
173 if(variation == NULL){
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];
188 if(variation == NULL){
191 fprintf(GlobalState.logfile,"%s %s %s\n",tag,opening,variation);
192 fprintf(GlobalState.logfile,"Possible duplicate move sequences.\n");
199 /* First occurrence, so add it to the log. */
200 entry = (EcoLog *)MallocOrDie(sizeof(*entry));
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
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;
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;
219 entry->ECO_tag = copy_string(game_details.tags[ECO_TAG]);
223 entry->ECO_tag = NULL;
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;
233 entry->Opening_tag = copy_string(game_details.tags[OPENING_TAG]);
237 entry->Opening_tag = NULL;
239 if(game_details.tags[VARIATION_TAG] != NULL){
240 entry->Variation_tag = copy_string(game_details.tags[VARIATION_TAG]);
243 entry->Variation_tag = NULL;
245 if(game_details.tags[SUB_VARIATION_TAG] != NULL){
246 entry->Sub_Variation_tag =
247 copy_string(game_details.tags[SUB_VARIATION_TAG]);
250 entry->Sub_Variation_tag = NULL;
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. */
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.
266 eco_matches(HashCode current_hash_value, HashCode cumulative_hash_value,
267 unsigned half_moves_played)
269 EcoLog *possible = NULL;
271 /* Don't bother trying if we are too far on in the game. */
272 if(half_moves_played <= maximum_half_moves){
274 unsigned ix = current_hash_value % ECO_TABLE_SIZE;
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){
284 else if(abs(half_moves_played-entry->half_moves) <=
285 ECO_HALF_MOVE_LIMIT){
286 /* Retain this as a possible. */
290 /* Ignore it, as the lines are too distant. */
298 /* Depending upon the ECO_level and the eco string of the
299 * current game, open the correctly named ECO 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.
306 static const char suffix[] = ".pgn";
307 enum { MAXNAME = MAX_ECO_LEVEL+sizeof(suffix)-1 };
308 static char filename[MAXNAME+1];
310 if((eco == NULL) || !isalpha((int) *eco)){
311 strcpy(filename,"noeco.pgn");
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");
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");
324 strncpy(filename,eco,ECO_level);
325 filename[ECO_level] = '\0';
326 strcat(filename,suffix);
328 return must_open_file(filename,"a");