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;
56 #if INCLUDE_UNUSED_FUNCTIONS
60 for(ix = 0; ix < ECO_TABLE_SIZE; ix++){
61 if(EcoTable[ix] != 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);
73 /* Return at how many points this match works.
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
84 eco_match_level(EcoLog *entry,HashCode current_hash_value,
85 HashCode cumulative_hash_value,unsigned half_moves_played)
89 if(entry->required_hash_value == current_hash_value){
91 if(entry->cumulative_hash_value == cumulative_hash_value){
93 if(entry->half_moves == half_moves_played){
102 /* Quality values for aspects of an ECO match.
105 static int ECO_REQUIRED_HASH_VALUE = 1;
106 static int ECO_HALF_MOVE_VALUE = 1;
107 static int ECO_CUMULATIVE_HASH_VALUE = 0;
109 /* Rate the quality of the given match.
112 static int eco_match_quality(EcoLog* entry,
113 HashCode current_hash_value,
114 HashCode cumulative_hash_value,
115 int half_moves_played)
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;
123 if(entry->cumulative_hash_value == cumulative_hash_value){
124 quality += ECO_CUMULATIVE_HASH_VALUE;
131 void initEcoTable(void)
133 /* Avoid multiple calls. */
134 if(EcoTable == NULL){
136 EcoTable = (EcoLog **) MallocOrDie(ECO_TABLE_SIZE*sizeof(EcoLog *));
138 for(i = 0; i < ECO_TABLE_SIZE; i++){
144 /* Enter the ECO details of game into EcoTable.
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
157 static EcoLog *last_entry = NULL;
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;
172 if(variation == NULL){
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];
187 if(variation == NULL){
190 fprintf(GlobalState.logfile,"%s %s %s\n",tag,opening,variation);
191 fprintf(GlobalState.logfile,"Possible duplicate move sequences.\n");
198 /* First occurrence, so add it to the log. */
199 entry = (EcoLog *)MallocOrDie(sizeof(*entry));
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
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;
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;
218 entry->ECO_tag = copy_string(game_details.tags[ECO_TAG]);
222 entry->ECO_tag = NULL;
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;
232 entry->Opening_tag = copy_string(game_details.tags[OPENING_TAG]);
236 entry->Opening_tag = NULL;
238 if(game_details.tags[VARIATION_TAG] != NULL){
239 entry->Variation_tag = copy_string(game_details.tags[VARIATION_TAG]);
242 entry->Variation_tag = NULL;
244 if(game_details.tags[SUB_VARIATION_TAG] != NULL){
245 entry->Sub_Variation_tag =
246 copy_string(game_details.tags[SUB_VARIATION_TAG]);
249 entry->Sub_Variation_tag = NULL;
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. */
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.
265 eco_matches(HashCode current_hash_value, HashCode cumulative_hash_value,
266 unsigned half_moves_played)
268 EcoLog *possible = NULL;
270 /* Don't bother trying if we are too far on in the game. */
271 if(half_moves_played <= maximum_half_moves){
273 unsigned ix = current_hash_value % ECO_TABLE_SIZE;
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){
283 else if(abs(half_moves_played-entry->half_moves) <=
284 ECO_HALF_MOVE_LIMIT){
285 /* Retain this as a possible. */
289 /* Ignore it, as the lines are too distant. */
297 /* Depending upon the ECO_level and the eco string of the
298 * current game, open the correctly named ECO 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.
305 static const char suffix[] = ".pgn";
306 enum { MAXNAME = MAX_ECO_LEVEL+sizeof(suffix)-1 };
307 static char filename[MAXNAME+1];
309 if((eco == NULL) || !isalpha((int) *eco)){
310 strcpy(filename,"noeco.pgn");
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");
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");
323 strncpy(filename,eco,ECO_level);
324 filename[ECO_level] = '\0';
325 strcat(filename,suffix);
327 return must_open_file(filename,"a");