-// book_make.c\r
-\r
-// includes\r
-\r
-#include <errno.h>\r
-#include <math.h>\r
-#include <stdio.h>\r
-#include <stdlib.h>\r
-#include <string.h>\r
-\r
-#include "board.h"\r
-#include "book_make.h"\r
-#include "move.h"\r
-#include "move_do.h"\r
-#include "move_gen.h"\r
-#include "move_legal.h"\r
-#include "pgn.h"\r
-#include "san.h"\r
-#include "util.h"\r
-\r
-// constants\r
-\r
-static const int COUNT_MAX = 16384;\r
-static const int StringSize = 4096;\r
-\r
-static const int NIL = -1;\r
-\r
-// defines\r
-\r
-#define opp_search(s) ((s)==BOOK?ALL:BOOK)\r
-\r
-// types\r
-\r
-typedef struct {\r
- uint64 key;\r
- uint16 move;\r
- uint16 count;\r
-// Unfortunately the minggw32 cross compiler [4.2.1-sjlj (mingw32-2)] \r
-// seems to have a bug with anon structs contained in unions when using -O2.\r
-// See the ASSERT below in "read_entry_file"...\r
-// To be fair this seems to be illegal in C++\r
-// although it is hard to understand why, and the compiler does not complain\r
-// even with -Wall.\r
-// union { \r
-// struct { \r
- uint16 n;\r
- uint16 sum;\r
-// };\r
-// struct {\r
- uint8 height;\r
- int line;\r
-// };\r
-// };\r
- uint8 colour;\r
-} entry_t;\r
-\r
-typedef struct {\r
- int size;\r
- int alloc;\r
- uint32 mask;\r
- entry_t * entry;\r
- sint32 * hash;\r
-} book_t;\r
-\r
-typedef enum {\r
- BOOK,\r
- ALL\r
-} search_t;\r
-\r
-typedef struct {\r
- int height;\r
- int line;\r
- int initial_color;\r
- bool book_trans_only;\r
- bool extended_search;\r
- uint16 moves[1024];\r
- double probs[1024];\r
- uint64 keys[1024];\r
- FILE *output;\r
-} info_t;\r
-\r
-\r
-// variables\r
-\r
-static int MaxPly;\r
-static int MinGame;\r
-static double MinScore;\r
-static bool RemoveWhite, RemoveBlack;\r
-static bool Uniform;\r
-static bool Quiet=FALSE;\r
-\r
-static book_t Book[1];\r
-\r
-// prototypes\r
-\r
-static void book_clear ();\r
-static void book_insert (const char file_name[]);\r
-static void book_filter ();\r
-static void book_sort ();\r
-static void book_save (const char file_name[]);\r
-\r
-static int find_entry (const board_t * board, int move);\r
-static void resize ();\r
-static void halve_stats (uint64 key);\r
-\r
-static bool keep_entry (int pos);\r
-\r
-static int entry_score (const entry_t * entry);\r
-\r
-static int key_compare (const void * p1, const void * p2);\r
-\r
-static void write_integer (FILE * file, int size, uint64 n);\r
-static uint64 read_integer(FILE * file, int size);\r
-\r
-static void read_entry_file(FILE *f, entry_t *entry);\r
-static void write_entry_file(FILE * f, const entry_t * entry);\r
-\r
-// functions\r
-\r
-// book_make()\r
-\r
-void book_make(int argc, char * argv[]) {\r
-\r
- int i;\r
- const char * pgn_file;\r
- const char * bin_file;\r
-\r
- pgn_file = NULL;\r
- my_string_set(&pgn_file,"book.pgn");\r
-\r
- bin_file = NULL;\r
- my_string_set(&bin_file,"book.bin");\r
-\r
- MaxPly = 1024;\r
- MinGame = 3;\r
- MinScore = 0.0;\r
- RemoveWhite = FALSE;\r
- RemoveBlack = FALSE;\r
- Uniform = FALSE;\r
-\r
- for (i = 1; i < argc; i++) {\r
-\r
- if (FALSE) {\r
-\r
- } else if (my_string_equal(argv[i],"make-book")) {\r
-\r
- // skip\r
-\r
- } else if (my_string_equal(argv[i],"-pgn")) {\r
-\r
- i++;\r
- if (argv[i] == NULL) my_fatal("book_make(): missing argument\n");\r
-\r
- my_string_set(&pgn_file,argv[i]);\r
-\r
- } else if (my_string_equal(argv[i],"-bin")) {\r
-\r
- i++;\r
- if (argv[i] == NULL) my_fatal("book_make(): missing argument\n");\r
-\r
- my_string_set(&bin_file,argv[i]);\r
-\r
- } else if (my_string_equal(argv[i],"-max-ply")) {\r
-\r
- i++;\r
- if (argv[i] == NULL) my_fatal("book_make(): missing argument\n");\r
-\r
- MaxPly = atoi(argv[i]);\r
- ASSERT(MaxPly>=0);\r
-\r
- } else if (my_string_equal(argv[i],"-min-game")) {\r
-\r
- i++;\r
- if (argv[i] == NULL) my_fatal("book_make(): missing argument\n");\r
-\r
- MinGame = atoi(argv[i]);\r
- ASSERT(MinGame>0);\r
-\r
- } else if (my_string_equal(argv[i],"-min-score")) {\r
-\r
- i++;\r
- if (argv[i] == NULL) my_fatal("book_make(): missing argument\n");\r
-\r
- MinScore = atof(argv[i]) / 100.0;\r
- ASSERT(MinScore>=0.0&&MinScore<=1.0);\r
-\r
- } else if (my_string_equal(argv[i],"-only-white")) {\r
-\r
- RemoveWhite = FALSE;\r
- RemoveBlack = TRUE;\r
-\r
- } else if (my_string_equal(argv[i],"-only-black")) {\r
-\r
- RemoveWhite = TRUE;\r
- RemoveBlack = FALSE;\r
-\r
- } else if (my_string_equal(argv[i],"-uniform")) {\r
-\r
- Uniform = TRUE;\r
-\r
- } else {\r
-\r
- my_fatal("book_make(): unknown option \"%s\"\n",argv[i]);\r
- }\r
- }\r
-\r
- book_clear();\r
-\r
- printf("inserting games ...\n");\r
- book_insert(pgn_file);\r
-\r
- printf("filtering entries ...\n");\r
- book_filter();\r
-\r
- printf("sorting entries ...\n");\r
- book_sort();\r
-\r
- printf("saving entries ...\n");\r
- book_save(bin_file);\r
-\r
- printf("all done!\n");\r
-}\r
-\r
-// book_clear()\r
-\r
-static void book_clear() {\r
-\r
- int index;\r
-\r
- Book->alloc = 1;\r
- Book->mask = (Book->alloc * 2) - 1;\r
-\r
- Book->entry = (entry_t *) my_malloc(Book->alloc*sizeof(entry_t));\r
- Book->size = 0;\r
-\r
- Book->hash = (sint32 *) my_malloc((Book->alloc*2)*sizeof(sint32));\r
- for (index = 0; index < Book->alloc*2; index++) {\r
- Book->hash[index] = NIL;\r
- }\r
-}\r
-\r
-// book_insert()\r
-\r
-static void book_insert(const char file_name[]) {\r
-\r
- pgn_t pgn[1];\r
- board_t board[1];\r
- int ply;\r
- int result;\r
- char string[256];\r
- int move;\r
- int pos;\r
-\r
- ASSERT(file_name!=NULL);\r
-\r
- // init\r
-\r
- pgn->game_nb=1;\r
- // scan loop\r
-\r
- pgn_open(pgn,file_name);\r
-\r
- while (pgn_next_game(pgn)) {\r
-\r
- board_start(board);\r
- ply = 0;\r
- result = 0;\r
-\r
- if (FALSE) {\r
- } else if (my_string_equal(pgn->result,"1-0")) {\r
- result = +1;\r
- } else if (my_string_equal(pgn->result,"0-1")) {\r
- result = -1;\r
- }\r
-\r
- while (pgn_next_move(pgn,string,256)) {\r
-\r
- if (ply < MaxPly) {\r
-\r
- move = move_from_san(string,board);\r
-\r
- if (move == MoveNone || !move_is_legal(move,board)) {\r
- my_fatal("book_insert(): illegal move \"%s\" at line %d, column %d,game %d\n",string,pgn->move_line,pgn->move_column,pgn->game_nb);\r
- }\r
-\r
- pos = find_entry(board,move);\r
-\r
- Book->entry[pos].n++;\r
- Book->entry[pos].sum += result+1;\r
-\r
- if (Book->entry[pos].n >= COUNT_MAX) {\r
- halve_stats(board->key);\r
- }\r
-\r
- move_do(board,move);\r
- ply++;\r
- result = -result;\r
- }\r
- }\r
- pgn->game_nb++;\r
- if (pgn->game_nb % 10000 == 0) printf("%d games ...\n",pgn->game_nb);\r
- }\r
-\r
- pgn_close(pgn);\r
-\r
- printf("%d game%s.\n",pgn->game_nb,(pgn->game_nb>2)?"s":"");\r
- printf("%d entries.\n",Book->size);\r
-\r
- return;\r
-}\r
-\r
-// book_filter()\r
-\r
-static void book_filter() {\r
-\r
- int src, dst;\r
-\r
- // entry loop\r
-\r
- dst = 0;\r
-\r
- for (src = 0; src < Book->size; src++) {\r
- if (keep_entry(src)) Book->entry[dst++] = Book->entry[src];\r
- }\r
-\r
- ASSERT(dst>=0&&dst<=Book->size);\r
- Book->size = dst;\r
-\r
- printf("%d entries.\n",Book->size);\r
-}\r
-\r
-// book_sort()\r
-\r
-static void book_sort() {\r
-\r
- // sort keys for binary search\r
-\r
- qsort(Book->entry,Book->size,sizeof(entry_t),&key_compare);\r
-}\r
-\r
-// book_save()\r
-\r
-static void book_save(const char file_name[]) {\r
-\r
- FILE * file;\r
- int pos;\r
-\r
- ASSERT(file_name!=NULL);\r
-\r
- file = fopen(file_name,"wb");\r
- if (file == NULL) my_fatal("book_save(): can't open file \"%s\" for writing: %s\n",file_name,strerror(errno));\r
-\r
- // entry loop\r
-\r
- for (pos = 0; pos < Book->size; pos++) {\r
-\r
- ASSERT(keep_entry(pos));\r
-\r
- write_integer(file,8,Book->entry[pos].key);\r
- write_integer(file,2,Book->entry[pos].move);\r
- write_integer(file,2,entry_score(&Book->entry[pos]));\r
- write_integer(file,2,0);\r
- write_integer(file,2,0);\r
- }\r
-\r
- fclose(file);\r
-}\r
-\r
-// find_entry()\r
-\r
-static int find_entry(const board_t * board, int move) {\r
-\r
- uint64 key;\r
- int index;\r
- int pos;\r
-\r
- ASSERT(board!=NULL);\r
- ASSERT(move==MoveNone || move_is_ok(move));\r
-\r
- ASSERT(move==MoveNone || move_is_legal(move,board));\r
-\r
- // init\r
-\r
- key = board->key;\r
-\r
- // search\r
-\r
- for (index = key & (uint64) Book->mask; (pos=Book->hash[index]) != NIL; index = (index+1) & Book->mask) {\r
-\r
- ASSERT(pos>=0&&pos<Book->size);\r
-\r
- if (Book->entry[pos].key == key && Book->entry[pos].move == move) {\r
- return pos; // found\r
- }\r
- }\r
-\r
- // not found\r
-\r
- ASSERT(Book->size<=Book->alloc);\r
-\r
- if (Book->size == Book->alloc) {\r
-\r
- // allocate more memory\r
-\r
- resize();\r
-\r
- for (index = key & (uint64) Book->mask; Book->hash[index] != NIL; index = (index+1) & Book->mask)\r
- ;\r
- }\r
-\r
- // create a new entry\r
-\r
- ASSERT(Book->size<Book->alloc);\r
- pos = Book->size++;\r
-\r
- Book->entry[pos].key = key;\r
- Book->entry[pos].move = move;\r
- Book->entry[pos].n = 0;\r
- Book->entry[pos].sum = 0;\r
- Book->entry[pos].colour = board->turn;\r
-\r
- // insert into the hash table\r
-\r
- ASSERT(index>=0&&index<Book->alloc*2);\r
- ASSERT(Book->hash[index]==NIL);\r
- Book->hash[index] = pos;\r
-\r
- ASSERT(pos>=0&&pos<Book->size);\r
-\r
- return pos;\r
-}\r
-\r
-// rebuild_hash_table\r
-\r
-static void rebuild_hash_table(){\r
- int index,pos;\r
- for (index = 0; index < Book->alloc*2; index++) {\r
- Book->hash[index] = NIL;\r
- }\r
- for (pos = 0; pos < Book->size; pos++) {\r
- for (index = Book->entry[pos].key & (uint64) Book->mask; Book->hash[index] != NIL; index = (index+1) & Book->mask)\r
- ;\r
- ASSERT(index>=0&&index<Book->alloc*2);\r
- Book->hash[index] = pos;\r
- }\r
-}\r
-\r
-static void resize() {\r
-\r
- int size;\r
-\r
- ASSERT(Book->size==Book->alloc);\r
-\r
- Book->alloc *= 2;\r
- Book->mask = (Book->alloc * 2) - 1;\r
-\r
- size = 0;\r
- size += Book->alloc * sizeof(entry_t);\r
- size += (Book->alloc*2) * sizeof(sint32);\r
-\r
- if (size >= 1048576) if(!Quiet){\r
- printf("allocating %gMB ...\n",((double)size)/1048576.0);\r
- }\r
-\r
- // resize arrays\r
-\r
- Book->entry = (entry_t *) my_realloc(Book->entry,Book->alloc*sizeof(entry_t));\r
- Book->hash = (sint32 *) my_realloc(Book->hash,(Book->alloc*2)*sizeof(sint32));\r
-\r
- // rebuild hash table\r
-\r
- rebuild_hash_table();\r
-}\r
-\r
-\r
-// halve_stats()\r
-\r
-static void halve_stats(uint64 key) {\r
-\r
- int index;\r
- int pos;\r
-\r
- // search\r
-\r
- for (index = key & (uint64) Book->mask; (pos=Book->hash[index]) != NIL; index = (index+1) & Book->mask) {\r
-\r
- ASSERT(pos>=0&&pos<Book->size);\r
-\r
- if (Book->entry[pos].key == key) {\r
- Book->entry[pos].n = (Book->entry[pos].n + 1) / 2;\r
- Book->entry[pos].sum = (Book->entry[pos].sum + 1) / 2;\r
- }\r
- }\r
-}\r
-\r
-// keep_entry()\r
-\r
-static bool keep_entry(int pos) {\r
-\r
- const entry_t * entry;\r
- int colour;\r
- double score;\r
-\r
- ASSERT(pos>=0&&pos<Book->size);\r
-\r
- entry = &Book->entry[pos];\r
-\r
- // if (entry->n == 0) return FALSE;\r
- if (entry->n < MinGame) return FALSE;\r
-\r
- if (entry->sum == 0) return FALSE;\r
-\r
- score = (((double)entry->sum) / ((double)entry->n)) / 2.0;\r
- ASSERT(score>=0.0&&score<=1.0);\r
-\r
- if (score < MinScore) return FALSE;\r
-\r
- colour = entry->colour;\r
-\r
- if ((RemoveWhite && colour_is_white(colour))\r
- || (RemoveBlack && colour_is_black(colour))) {\r
- return FALSE;\r
- }\r
-\r
- if (entry_score(entry) == 0) return FALSE; // REMOVE ME?\r
-\r
- return TRUE;\r
-}\r
-\r
-// entry_score()\r
-\r
-static int entry_score(const entry_t * entry) {\r
-\r
- int score;\r
-\r
- ASSERT(entry!=NULL);\r
-\r
- // score = entry->n; // popularity\r
- score = entry->sum; // "expectancy"\r
-\r
- if (Uniform) score = 1;\r
-\r
- ASSERT(score>=0);\r
-\r
- return score;\r
-}\r
-\r
-// key_compare()\r
-\r
-static int key_compare(const void * p1, const void * p2) {\r
-\r
- const entry_t * entry_1, * entry_2;\r
-\r
- ASSERT(p1!=NULL);\r
- ASSERT(p2!=NULL);\r
-\r
- entry_1 = (const entry_t *) p1;\r
- entry_2 = (const entry_t *) p2;\r
-\r
- if (entry_1->key > entry_2->key) {\r
- return +1;\r
- } else if (entry_1->key < entry_2->key) {\r
- return -1;\r
- } else {\r
- return entry_score(entry_2) - entry_score(entry_1); // highest score first\r
- }\r
-}\r
-\r
-// write_integer()\r
-\r
-static void write_integer(FILE * file, int size, uint64 n) {\r
-\r
- int i;\r
- int b;\r
-\r
- ASSERT(file!=NULL);\r
- ASSERT(size>0&&size<=8);\r
- ASSERT(size==8||n>>(size*8)==0);\r
-\r
- for (i = size-1; i >= 0; i--) {\r
- b = (n >> (i*8)) & 0xFF;\r
- ASSERT(b>=0&&b<256);\r
- fputc(b,file);\r
- }\r
-}\r
-\r
-// read_integer()\r
-\r
-static uint64 read_integer(FILE * file, int size) {\r
- uint64 n;\r
- int i;\r
- int b;\r
- ASSERT(file!=NULL);\r
- ASSERT(size>0&&size<=8);\r
- n = 0;\r
- for (i = 0; i < size; i++) {\r
- b = fgetc(file);\r
- if (b == EOF) {\r
- if (feof(file)) {\r
- my_fatal("read_integer(): fgetc(): EOF reached\n");\r
- } else { // error\r
- my_fatal("read_integer(): fgetc(): %s\n",strerror(errno));\r
- }\r
- }\r
- ASSERT(b>=0&&b<256);\r
- n = (n << 8) | b;\r
- }\r
- return n;\r
-}\r
-\r
-// read_entry_file\r
-\r
-static void read_entry_file(FILE *f, entry_t *entry){\r
- uint64 n;\r
- ASSERT(entry!=NULL);\r
- n = entry->key = read_integer(f,8);\r
- entry->move = read_integer(f,2);\r
- entry->count = read_integer(f,2);\r
- entry->n = read_integer(f,2);\r
- entry->sum = read_integer(f,2);\r
- ASSERT(n==entry->key); // test for mingw compiler bug with anon structs\r
-}\r
-\r
-// write_entry_file\r
-\r
-static void write_entry_file(FILE * f, const entry_t * entry) {\r
- ASSERT(entry!=NULL);\r
- write_integer(f,8,entry->key);\r
- write_integer(f,2,entry->move);\r
- write_integer(f,2,entry->count);\r
- write_integer(f,2,entry->n);\r
- write_integer(f,2,entry->sum);\r
-}\r
-\r
-static void print_list(const board_t *board, list_t *list){\r
- int i;\r
- uint16 move;\r
- char move_string[256];\r
- for (i = 0; i < list_size(list); i++) {\r
- move = list_move(list,i);\r
- move_to_san(move,board,move_string,256);\r
- printf("%s",move_string);\r
- }\r
- printf("\n");\r
-}\r
-\r
-// book_load()\r
-// loads a polyglot book\r
-\r
-static void book_load(const char filename[]){\r
- FILE* f;\r
- entry_t entry[1];\r
- int size;\r
- int i;\r
- int pos;\r
- int index;\r
- ASSERT(filename!=NULL);\r
- if(!(f=fopen(filename,"rb"))){\r
- my_fatal("book_load() : can't open file \"%s\" for reading: %s\n",filename,strerror(errno));\r
- }\r
- fseek(f,0L,SEEK_END); // superportable way to get size of book!\r
- size=ftell(f)/16;\r
- fseek(f,0,SEEK_SET);\r
- for(i=0L;i<size;i++){\r
- read_entry_file(f,entry);\r
- ASSERT(Book->size<=Book->alloc);\r
- if (Book->size == Book->alloc) {\r
- // allocate more memoryx\r
- resize();\r
- }\r
- // insert into the book\r
- pos = Book->size++;\r
- Book->entry[pos].key = entry->key;\r
- ASSERT(entry->move!=MoveNone);\r
- Book->entry[pos].move = entry->move;\r
- Book->entry[pos].count = entry->count;\r
- Book->entry[pos].n = entry->n;\r
- Book->entry[pos].sum = entry->sum;\r
- Book->entry[pos].colour = ColourNone;\r
- // find free hash table spot\r
- for (index = entry->key & (uint64) Book->mask;\r
- Book->hash[index] != NIL;\r
- index = (index+1) & Book->mask);\r
- // insert into the hash table\r
- ASSERT(index>=0&&index<Book->alloc*2);\r
- ASSERT(Book->hash[index]==NIL);\r
- Book->hash[index] = pos;\r
- ASSERT(pos>=0&&pos<Book->size);\r
- }\r
- fclose(f);\r
-}\r
-\r
-// gen_book_moves()\r
-// similar signature as gen_legal_moves\r
-static int gen_book_moves(list_t * list, const board_t * board){\r
- int first_pos, pos, index;\r
- entry_t entry[1];\r
- list_clear(list);\r
- bool found;\r
- found=FALSE;\r
- for (index = board->key & (uint64) Book->mask; (first_pos=Book->hash[index]) != NIL; index = (index+1) & Book->mask) {\r
- ASSERT(first_pos>=0&&first_pos<Book->size);\r
- if (Book->entry[first_pos].key == board->key) {\r
- found=TRUE;\r
- break; // found\r
- }\r
- }\r
- if(!found) return -1;\r
- if(Book->entry[first_pos].move==MoveNone) return -1;\r
- for (pos = first_pos; pos < Book->size; pos++) {\r
- *entry=Book->entry[pos];\r
- if (entry->key != board->key) break;\r
- if (entry->count > 0 &&\r
- entry->move != MoveNone &&\r
- move_is_legal(entry->move,board)) {\r
- list_add_ex(list,entry->move,entry->count);\r
- }\r
- }\r
- return first_pos;\r
-}\r
-\r
-// gen_opp_book_moves()\r
-// moves to which opponent has a reply in book\r
-// similar signature as gen_legal_moves\r
-static void gen_opp_book_moves(list_t * list, const board_t * board){\r
- int move;\r
- list_t new_list[1], legal_moves[1];\r
- board_t new_board[1];\r
- int i;\r
- list_clear(list);\r
- gen_legal_moves(legal_moves,board);\r
- for (i = 0; i < list_size(legal_moves); i++) {\r
- move = list_move(legal_moves,i);\r
- // scratch_board\r
- memcpy(new_board, board, sizeof(board_t));\r
- move_do(new_board,move);\r
- gen_book_moves(new_list,new_board); // wasteful in time but tested!\r
- if(list_size(new_list)!=0){\r
- list_add(list,move);\r
- }\r
- }\r
-}\r
-\r
-static void print_moves(info_t *info){\r
- board_t board[1];\r
- char move_string[256];\r
- int i;\r
- int color=White;\r
- if(!info->output){\r
- return;\r
- }\r
- board_start(board);\r
- for(i=0;i<info->height;i++){\r
- if(color==White){\r
- fprintf(info->output,"%d. ",i/2+1);\r
- color=Black;\r
- }else{\r
- color=White;\r
- }\r
- move_to_san(info->moves[i],board,move_string,256);\r
- fprintf(info->output,"%s", move_string);\r
- if(color==colour_opp(info->initial_color)){\r
- fprintf(info->output,"{%.0f%%} ",100*info->probs[i]);\r
- }else{\r
- fprintf(info->output," ");\r
- }\r
- move_do(board,info->moves[i]);\r
- }\r
-}\r
-\r
-static int search_book(board_t *board, info_t *info, search_t search){\r
- list_t list[1];\r
- board_t new_board[1];\r
- uint16 move;\r
- int count;\r
- int ret;\r
- int i;\r
- int offset;\r
- int pos;\r
- int size;\r
- int prob_sum;\r
- double probs[256];\r
- for(i=0;i<256;i++){\r
- probs[i]=0.0; // kill compiler warnings\r
- }\r
- for(i=0;i<info->height;i++){\r
- if(board->key==info->keys[i]){\r
- if(info->output){\r
- fprintf(info->output,"%d: ",info->line);\r
- print_moves(info);\r
- fprintf(info->output,"{cycle: ply=%d}\n",i);\r
- }\r
- info->line++;\r
- return 1; // end of line because of cycle\r
- }\r
- }\r
- if(!info->book_trans_only || (info->book_trans_only && search==BOOK)){\r
- info->keys[info->height]=board->key;\r
- size=Book->size; // hack\r
- pos=find_entry(board,MoveNone);\r
- if(size==Book->size){\r
- if(info->output){\r
- fprintf(info->output,"%d: ",info->line);\r
- print_moves(info);\r
- fprintf(info->output,"{trans: line=%d, ply=%d}\n",\r
- Book->entry[pos].line,\r
- Book->entry[pos].height);\r
- }\r
- info->line++;\r
- return 1; // end of line because of transposition\r
- }else{\r
- Book->entry[pos].height=info->height;\r
- Book->entry[pos].line=info->line;\r
- }\r
- }\r
- count=0;\r
- if(search==BOOK){\r
- offset=gen_book_moves(list,board);\r
- if(info->extended_search){\r
- gen_legal_moves(list,board);\r
- }\r
-// ASSERT(offset!=-1);\r
- if(offset!=-1){ // only FALSE in starting position for black book\r
- Book->entry[offset].colour=board->turn;\r
- prob_sum=0;\r
- if(!info->extended_search){\r
- for(i=0;i<list_size(list);i++){\r
- prob_sum+=((uint16)list_value(list,i));\r
- }\r
- for(i=0;i<list_size(list);i++){\r
- probs[i]=((double)((uint16)list_value(list,i)))/((double)prob_sum);\r
- }\r
- }\r
- }\r
- }else{\r
- gen_opp_book_moves(list,board);\r
- }\r
- for (i = 0; i < list_size(list); i++) {\r
- move = list_move(list,i);\r
- memcpy(new_board, board, sizeof(board_t));\r
- ASSERT(move_is_legal(move,new_board));\r
- move_do(new_board,move);\r
- ASSERT(search!=opp_search(search));\r
- info->moves[info->height++]=move;\r
- if(search==BOOK){\r
- info->probs[info->height-1]=probs[i];\r
- }\r
- ret=search_book(new_board, info, opp_search(search));\r
- if(ret==0 && search==BOOK){\r
- if(info->output){\r
- fprintf(info->output,"%d: ",info->line);\r
- print_moves(info);\r
- fprintf(info->output,"\n");\r
- }\r
- info->line++;\r
- ret=1; // end of line book move counts for 1\r
- }\r
- info->height--;\r
- ASSERT(info->height>=0);\r
- count+=ret;\r
- }\r
- return count;\r
-}\r
-\r
-void init_info(info_t *info){\r
- info->line=1;\r
- info->height=0;\r
- info->output=NULL;\r
- info->initial_color=White;\r
- info->book_trans_only=FALSE;\r
-}\r
-\r
-// book_clean()\r
-// remove MoveNone entries from book and rebuild hash table\r
-void book_clean(){\r
- int read_ptr,write_ptr;\r
- write_ptr=0;\r
- for(read_ptr=0;read_ptr<Book->size;read_ptr++){\r
- if(Book->entry[read_ptr].move!=MoveNone){\r
- Book->entry[write_ptr++]=Book->entry[read_ptr];\r
- }\r
- }\r
- Book->size=write_ptr;\r
- rebuild_hash_table();\r
-}\r
-\r
-// book_dump()\r
-\r
-void book_dump(int argc, char * argv[]) {\r
- const char * bin_file=NULL;\r
- const char * txt_file=NULL;\r
- char string[StringSize];\r
- int color=ColourNone;\r
- board_t board[1];\r
- info_t info[1];\r
- int i;\r
- FILE *f;\r
- my_string_set(&bin_file,"book.bin");\r
- for (i = 1; i < argc; i++) {\r
- if (FALSE) {\r
- } else if (my_string_equal(argv[i],"dump-book")) {\r
- // skip\r
- } else if (my_string_equal(argv[i],"-bin")) {\r
- i++;\r
- if (i==argc) my_fatal("book_dump(): missing argument\n");\r
- my_string_set(&bin_file,argv[i]);\r
- } else if (my_string_equal(argv[i],"-out")) {\r
- i++;\r
- if (i==argc) my_fatal("book_dump(): missing argument\n");\r
- my_string_set(&txt_file,argv[i]);\r
- } else if (my_string_equal(argv[i],"-color") || my_string_equal(argv[i],"-colour")) {\r
- i++;\r
- if (i == argc) my_fatal("book_dump(): missing argument\n");\r
- if(my_string_equal(argv[i],"white")){\r
- color=White;\r
- }else if (my_string_equal(argv[i],"black")){\r
- color=Black;\r
- }else{\r
- my_fatal("book_dump(): unknown color \"%s\"\n",argv[i]);\r
- }\r
- } else {\r
- my_fatal("book_dump(): unknown option \"%s\"\n",argv[i]);\r
- }\r
- }\r
- if(color==ColourNone){\r
- my_fatal("book_dump(): you must specify a color\n");\r
- }\r
- if(txt_file==NULL){\r
- snprintf(string,StringSize,"book_%s.txt",color?"white":"black");\r
- my_string_set(&txt_file,string);\r
- }\r
-\r
- book_clear();\r
- if(!Quiet){printf("loading book ...\n");}\r
- book_load(bin_file);\r
- board_start(board);\r
- init_info(info);\r
- info->initial_color=color;\r
- if(!(f=fopen(txt_file,"w"))){\r
- my_fatal("book_dump(): can't open file \"%s\" for writing: %s",\r
- txt_file,strerror(errno));\r
- }\r
- info->output=f;\r
- fprintf(info->output,"Dump of \"%s\" for %s.\n",\r
- bin_file,color==White?"white":"black");\r
- if(color==White){\r
- if(!Quiet){printf("generating lines for white...\n");}\r
- search_book(board,info, BOOK);\r
- }else{\r
- if(!Quiet){printf("generating lines for black...\n");}\r
- search_book(board,info, ALL);\r
- }\r
-}\r
-\r
-// book_info()\r
-\r
-void book_info(int argc,char* argv[]){\r
- const char *bin_file=NULL;\r
- board_t board[1];\r
- info_t info[1];\r
- uint64 last_key;\r
- int pos;\r
- int white_pos,black_pos,total_pos,white_pos_extended,\r
- black_pos_extended,white_pos_extended_diff,black_pos_extended_diff;\r
- int s;\r
- bool extended_search=FALSE;\r
- int i;\r
- Quiet=TRUE;\r
- my_string_set(&bin_file,"book.bin");\r
-\r
- for (i = 1; i < argc; i++) {\r
- if (FALSE) {\r
- } else if (my_string_equal(argv[i],"info-book")) {\r
- // skip\r
- } else if (my_string_equal(argv[i],"-bin")) {\r
- i++;\r
- if (i==argc) my_fatal("book_info(): missing argument\n");\r
- my_string_set(&bin_file,argv[i]);\r
- } else if (my_string_equal(argv[i],"-exact")) {\r
- extended_search=TRUE;\r
- } else {\r
- my_fatal("book_info(): unknown option \"%s\"\n",argv[i]);\r
- }\r
- }\r
- book_clear();\r
- if(!Quiet){printf("loading book ...\n");}\r
- book_load(bin_file);\r
- s=Book->size;\r
-\r
- board_start(board);\r
- init_info(info);\r
- info->book_trans_only=FALSE;\r
- info->initial_color=White;\r
- info->extended_search=FALSE;\r
- search_book(board,info, BOOK);\r
- printf("Lines for white : %8d\n",info->line-1);\r
-\r
-\r
- info->line=1;\r
- info->height=0;\r
- info->initial_color=Black;\r
- book_clean();\r
- ASSERT(Book->size==s);\r
- board_start(board);\r
- search_book(board,info, ALL);\r
- printf("Lines for black : %8d\n",info->line-1);\r
-\r
- book_clean();\r
- ASSERT(Book->size==s);\r
- white_pos=0;\r
- black_pos=0;\r
- total_pos=0;\r
- last_key=0;\r
- for(pos=0;pos<Book->size;pos++){\r
- if(Book->entry[pos].key==last_key){\r
- ASSERT(Book->entry[pos].colour==ColourNone);\r
- continue;\r
- }\r
- last_key=Book->entry[pos].key;\r
- total_pos++;\r
- if(Book->entry[pos].colour==White){\r
- white_pos++;\r
- }else if(Book->entry[pos].colour==Black){\r
- black_pos++;\r
- }\r
- }\r
- printf("Positions on lines for white : %8d\n",white_pos);\r
- printf("Positions on lines for black : %8d\n",black_pos);\r
-\r
- \r
- if(extended_search){\r
- init_info(info);\r
- info->book_trans_only=TRUE;\r
- info->initial_color=White;\r
- info->extended_search=TRUE;\r
- book_clean();\r
- board_start(board);\r
- search_book(board,info, BOOK);\r
-\r
- init_info(info);\r
- info->book_trans_only=TRUE;\r
- info->initial_color=Black;\r
- info->extended_search=TRUE;\r
- book_clean();\r
- board_start(board);\r
- search_book(board,info, ALL);\r
- book_clean();\r
- ASSERT(Book->size==s);\r
- white_pos_extended=0;\r
- black_pos_extended=0;\r
- last_key=0;\r
- for(pos=0;pos<Book->size;pos++){\r
- if(Book->entry[pos].key==last_key){\r
- ASSERT(Book->entry[pos].colour==ColourNone);\r
- continue;\r
- }\r
- last_key=Book->entry[pos].key;\r
- if(Book->entry[pos].colour==White){\r
- white_pos_extended++;\r
- }else if(Book->entry[pos].colour==Black){\r
- black_pos_extended++;\r
- }\r
- }\r
- white_pos_extended_diff=white_pos_extended-white_pos;\r
- black_pos_extended_diff=black_pos_extended-black_pos;\r
- printf("Unreachable white positions(?) : %8d\n",\r
- white_pos_extended_diff);\r
- printf("Unreachable black positions(?) : %8d\n",\r
- black_pos_extended_diff);\r
-\r
- }\r
- if(extended_search){\r
- printf("Isolated positions : %8d\n",\r
- total_pos-white_pos_extended-black_pos_extended);\r
- }else{\r
- printf("Isolated positions : %8d\n",\r
- total_pos-white_pos-black_pos);\r
- }\r
-}\r
-\r
-\r
-\r
-// end of book_make.cpp\r
-\r
+// book_make.c
+
+// includes
+
+#include <errno.h>
+#include <math.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "board.h"
+#include "book_make.h"
+#include "move.h"
+#include "move_do.h"
+#include "move_gen.h"
+#include "move_legal.h"
+#include "pgn.h"
+#include "san.h"
+#include "util.h"
+#include "pgheader.h"
+
+// constants
+
+#define COUNT_MAX ((int)16384)
+
+static const int NIL = -1;
+
+// defines
+
+#define opp_search(s) ((s)==BOOK?ALL:BOOK)
+
+// types
+
+typedef struct {
+ uint64 key;
+ uint16 move;
+ uint16 count;
+// Unfortunately the minggw32 cross compiler [4.2.1-sjlj (mingw32-2)]
+// seems to have a bug with anon structs contained in unions when using -O2.
+// See the ASSERT below in "read_entry_file"...
+// To be fair this seems to be illegal in C++
+// although it is hard to understand why, and the compiler does not complain
+// even with -Wall.
+// union {
+// struct {
+ uint16 n;
+ uint16 sum;
+// };
+// struct {
+ uint8 height;
+ int line;
+// };
+// };
+ uint8 colour;
+} entry_t;
+
+typedef struct {
+ int size;
+ int alloc;
+ uint32 mask;
+ entry_t * entry;
+ sint32 * hash;
+} book_t;
+
+typedef enum {
+ BOOK,
+ ALL
+} search_t;
+
+typedef struct {
+ int height;
+ int line;
+ int initial_color;
+ bool book_trans_only;
+ bool extended_search;
+ uint16 moves[1024];
+ double probs[1024];
+ uint64 keys[1024];
+ FILE *output;
+} info_t;
+
+
+// variables
+
+static int MaxPly;
+static int MinGame;
+static double MinScore;
+static bool RemoveWhite, RemoveBlack;
+static bool Uniform;
+static bool Quiet=FALSE;
+
+static book_t Book[1];
+
+// prototypes
+
+static void book_clear ();
+static void book_insert (const char file_name[]);
+static void book_filter ();
+static void book_sort ();
+static void book_save (const char file_name[]);
+
+static int find_entry (const board_t * board, int move);
+static void resize ();
+static void halve_stats (uint64 key);
+
+static bool keep_entry (int pos);
+
+static int entry_score (const entry_t * entry);
+
+static int key_compare (const void * p1, const void * p2);
+
+static void write_integer (FILE * file, int size, uint64 n);
+static uint64 read_integer(FILE * file, int size);
+
+static void read_entry_file(FILE *f, entry_t *entry);
+static void write_entry_file(FILE * f, const entry_t * entry);
+
+// functions
+
+// book_make()
+
+void book_make(int argc, char * argv[]) {
+
+ int i;
+ const char * pgn_file;
+ const char * bin_file;
+
+ pgn_file = NULL;
+ my_string_set(&pgn_file,"book.pgn");
+
+ bin_file = NULL;
+ my_string_set(&bin_file,"book.bin");
+
+ MaxPly = 1024;
+ MinGame = 3;
+ MinScore = 0.0;
+ RemoveWhite = FALSE;
+ RemoveBlack = FALSE;
+ Uniform = FALSE;
+
+ for (i = 1; i < argc; i++) {
+
+ if (FALSE) {
+
+ } else if (my_string_equal(argv[i],"make-book")) {
+
+ // skip
+
+ } else if (my_string_equal(argv[i],"-pgn")) {
+
+ i++;
+ if (argv[i] == NULL) my_fatal("book_make(): missing argument\n");
+
+ my_string_set(&pgn_file,argv[i]);
+
+ } else if (my_string_equal(argv[i],"-bin")) {
+
+ i++;
+ if (argv[i] == NULL) my_fatal("book_make(): missing argument\n");
+
+ my_string_set(&bin_file,argv[i]);
+
+ } else if (my_string_equal(argv[i],"-max-ply")) {
+
+ i++;
+ if (argv[i] == NULL) my_fatal("book_make(): missing argument\n");
+
+ MaxPly = atoi(argv[i]);
+ ASSERT(MaxPly>=0);
+
+ } else if (my_string_equal(argv[i],"-min-game")) {
+
+ i++;
+ if (argv[i] == NULL) my_fatal("book_make(): missing argument\n");
+
+ MinGame = atoi(argv[i]);
+ ASSERT(MinGame>0);
+
+ } else if (my_string_equal(argv[i],"-min-score")) {
+
+ i++;
+ if (argv[i] == NULL) my_fatal("book_make(): missing argument\n");
+
+ MinScore = atof(argv[i]) / 100.0;
+ ASSERT(MinScore>=0.0&&MinScore<=1.0);
+
+ } else if (my_string_equal(argv[i],"-only-white")) {
+
+ RemoveWhite = FALSE;
+ RemoveBlack = TRUE;
+
+ } else if (my_string_equal(argv[i],"-only-black")) {
+
+ RemoveWhite = TRUE;
+ RemoveBlack = FALSE;
+
+ } else if (my_string_equal(argv[i],"-uniform")) {
+
+ Uniform = TRUE;
+
+ } else {
+
+ my_fatal("book_make(): unknown option \"%s\"\n",argv[i]);
+ }
+ }
+
+ book_clear();
+
+ printf("inserting games ...\n");
+ book_insert(pgn_file);
+
+ printf("filtering entries ...\n");
+ book_filter();
+
+ printf("sorting entries ...\n");
+ book_sort();
+
+ printf("saving entries ...\n");
+ book_save(bin_file);
+
+ printf("all done!\n");
+}
+
+// book_clear()
+
+static void book_clear() {
+
+ int index;
+
+ Book->alloc = 1;
+ Book->mask = (Book->alloc * 2) - 1;
+
+ Book->entry = (entry_t *) my_malloc(Book->alloc*sizeof(entry_t));
+ Book->size = 0;
+
+ Book->hash = (sint32 *) my_malloc((Book->alloc*2)*sizeof(sint32));
+ for (index = 0; index < Book->alloc*2; index++) {
+ Book->hash[index] = NIL;
+ }
+}
+
+// book_insert()
+
+static void book_insert(const char file_name[]) {
+
+ pgn_t pgn[1];
+ board_t board[1];
+ int ply;
+ int result;
+ char string[256];
+ int move;
+ int pos;
+
+ ASSERT(file_name!=NULL);
+
+ // init
+
+ pgn->game_nb=1;
+ // scan loop
+
+ pgn_open(pgn,file_name);
+
+ while (pgn_next_game(pgn)) {
+
+ board_start(board);
+ ply = 0;
+ result = 0;
+
+ if (FALSE) {
+ } else if (my_string_equal(pgn->result,"1-0")) {
+ result = +1;
+ } else if (my_string_equal(pgn->result,"0-1")) {
+ result = -1;
+ }
+
+ while (pgn_next_move(pgn,string,256)) {
+
+ if (ply < MaxPly) {
+
+ move = move_from_san(string,board);
+
+ if (move == MoveNone || !move_is_legal(move,board)) {
+ my_fatal("book_insert(): illegal move \"%s\" at line %d, column %d,game %d\n",string,pgn->move_line,pgn->move_column,pgn->game_nb);
+ }
+
+ pos = find_entry(board,move);
+
+ Book->entry[pos].n++;
+ Book->entry[pos].sum += result+1;
+
+ if (Book->entry[pos].n >= COUNT_MAX) {
+ halve_stats(board->key);
+ }
+
+ move_do(board,move);
+ ply++;
+ result = -result;
+ }
+ }
+ pgn->game_nb++;
+ if (pgn->game_nb % 10000 == 0) printf("%d games ...\n",pgn->game_nb);
+ }
+
+ pgn_close(pgn);
+
+ printf("%d game%s.\n",pgn->game_nb,(pgn->game_nb>2)?"s":"");
+ printf("%d entries.\n",Book->size);
+
+ return;
+}
+
+// book_filter()
+
+static void book_filter() {
+
+ int src, dst;
+
+ // entry loop
+
+ dst = 0;
+
+ for (src = 0; src < Book->size; src++) {
+ if (keep_entry(src)) Book->entry[dst++] = Book->entry[src];
+ }
+
+ ASSERT(dst>=0&&dst<=Book->size);
+ Book->size = dst;
+
+ printf("%d entries.\n",Book->size);
+}
+
+// book_sort()
+
+static void book_sort() {
+
+ // sort keys for binary search
+
+ qsort(Book->entry,Book->size,sizeof(entry_t),&key_compare);
+}
+
+// book_save()
+
+static void book_save(const char file_name[]) {
+
+ FILE * file;
+ int pos;
+ char *header, *raw_header;
+ unsigned int size;
+ int i;
+
+ ASSERT(file_name!=NULL);
+
+ file = fopen(file_name,"wb");
+ if (file == NULL) my_fatal("book_save(): can't open file \"%s\" for writing: %s\n",file_name,strerror(errno));
+
+ pgheader_create(&header,"normal","Created by Polyglot.");
+ pgheader_create_raw(&raw_header,header,&size);
+ free(header);
+
+ // write header
+
+ for(i=0;i<size;i++){
+ fputc(raw_header[i],file);
+ }
+ free(raw_header);
+
+ // entry loop
+
+ for (pos = 0; pos < Book->size; pos++) {
+
+ ASSERT(keep_entry(pos));
+ /* null keys are reserved for the header */
+ if(Book->entry[pos].key!=U64(0x0)){
+ write_integer(file,8,Book->entry[pos].key);
+ write_integer(file,2,Book->entry[pos].move);
+ write_integer(file,2,entry_score(&Book->entry[pos]));
+ write_integer(file,2,0);
+ write_integer(file,2,0);
+ }
+ }
+
+ fclose(file);
+}
+
+// find_entry()
+
+static int find_entry(const board_t * board, int move) {
+
+ uint64 key;
+ int index;
+ int pos;
+
+ ASSERT(board!=NULL);
+ ASSERT(move==MoveNone || move_is_ok(move));
+
+ ASSERT(move==MoveNone || move_is_legal(move,board));
+
+ // init
+
+ key = board->key;
+
+ // search
+
+ for (index = key & (uint64) Book->mask; (pos=Book->hash[index]) != NIL; index = (index+1) & Book->mask) {
+
+ ASSERT(pos>=0&&pos<Book->size);
+
+ if (Book->entry[pos].key == key && Book->entry[pos].move == move) {
+ return pos; // found
+ }
+ }
+
+ // not found
+
+ ASSERT(Book->size<=Book->alloc);
+
+ if (Book->size == Book->alloc) {
+
+ // allocate more memory
+
+ resize();
+
+ for (index = key & (uint64) Book->mask; Book->hash[index] != NIL; index = (index+1) & Book->mask)
+ ;
+ }
+
+ // create a new entry
+
+ ASSERT(Book->size<Book->alloc);
+ pos = Book->size++;
+
+ Book->entry[pos].key = key;
+ Book->entry[pos].move = move;
+ Book->entry[pos].n = 0;
+ Book->entry[pos].sum = 0;
+ Book->entry[pos].colour = board->turn;
+
+ // insert into the hash table
+
+ ASSERT(index>=0&&index<Book->alloc*2);
+ ASSERT(Book->hash[index]==NIL);
+ Book->hash[index] = pos;
+
+ ASSERT(pos>=0&&pos<Book->size);
+
+ return pos;
+}
+
+// rebuild_hash_table
+
+static void rebuild_hash_table(){
+ int index,pos;
+ for (index = 0; index < Book->alloc*2; index++) {
+ Book->hash[index] = NIL;
+ }
+ for (pos = 0; pos < Book->size; pos++) {
+ for (index = Book->entry[pos].key & (uint64) Book->mask; Book->hash[index] != NIL; index = (index+1) & Book->mask)
+ ;
+ ASSERT(index>=0&&index<Book->alloc*2);
+ Book->hash[index] = pos;
+ }
+}
+
+static void resize() {
+
+ int size;
+
+ ASSERT(Book->size==Book->alloc);
+
+ Book->alloc *= 2;
+ Book->mask = (Book->alloc * 2) - 1;
+
+ size = 0;
+ size += Book->alloc * sizeof(entry_t);
+ size += (Book->alloc*2) * sizeof(sint32);
+
+ if (size >= 1048576) if(!Quiet){
+ printf("allocating %gMB ...\n",((double)size)/1048576.0);
+ }
+
+ // resize arrays
+
+ Book->entry = (entry_t *) my_realloc(Book->entry,Book->alloc*sizeof(entry_t));
+ Book->hash = (sint32 *) my_realloc(Book->hash,(Book->alloc*2)*sizeof(sint32));
+
+ // rebuild hash table
+
+ rebuild_hash_table();
+}
+
+
+// halve_stats()
+
+static void halve_stats(uint64 key) {
+
+ int index;
+ int pos;
+
+ // search
+
+ for (index = key & (uint64) Book->mask; (pos=Book->hash[index]) != NIL; index = (index+1) & Book->mask) {
+
+ ASSERT(pos>=0&&pos<Book->size);
+
+ if (Book->entry[pos].key == key) {
+ Book->entry[pos].n = (Book->entry[pos].n + 1) / 2;
+ Book->entry[pos].sum = (Book->entry[pos].sum + 1) / 2;
+ }
+ }
+}
+
+// keep_entry()
+
+static bool keep_entry(int pos) {
+
+ const entry_t * entry;
+ int colour;
+ double score;
+
+ ASSERT(pos>=0&&pos<Book->size);
+
+ entry = &Book->entry[pos];
+
+ // if (entry->n == 0) return FALSE;
+ if (entry->n < MinGame) return FALSE;
+
+ if (entry->sum == 0) return FALSE;
+
+ score = (((double)entry->sum) / ((double)entry->n)) / 2.0;
+ ASSERT(score>=0.0&&score<=1.0);
+
+ if (score < MinScore) return FALSE;
+
+ colour = entry->colour;
+
+ if ((RemoveWhite && colour_is_white(colour))
+ || (RemoveBlack && colour_is_black(colour))) {
+ return FALSE;
+ }
+
+ if (entry_score(entry) == 0) return FALSE; // REMOVE ME?
+
+ return TRUE;
+}
+
+// entry_score()
+
+static int entry_score(const entry_t * entry) {
+
+ int score;
+
+ ASSERT(entry!=NULL);
+
+ // score = entry->n; // popularity
+ score = entry->sum; // "expectancy"
+
+ if (Uniform) score = 1;
+
+ ASSERT(score>=0);
+
+ return score;
+}
+
+// key_compare()
+
+static int key_compare(const void * p1, const void * p2) {
+
+ const entry_t * entry_1, * entry_2;
+
+ ASSERT(p1!=NULL);
+ ASSERT(p2!=NULL);
+
+ entry_1 = (const entry_t *) p1;
+ entry_2 = (const entry_t *) p2;
+
+ if (entry_1->key > entry_2->key) {
+ return +1;
+ } else if (entry_1->key < entry_2->key) {
+ return -1;
+ } else {
+ return entry_score(entry_2) - entry_score(entry_1); // highest score first
+ }
+}
+
+// write_integer()
+
+static void write_integer(FILE * file, int size, uint64 n) {
+
+ int i;
+ int b;
+
+ ASSERT(file!=NULL);
+ ASSERT(size>0&&size<=8);
+ ASSERT(size==8||n>>(size*8)==0);
+
+ for (i = size-1; i >= 0; i--) {
+ b = (n >> (i*8)) & 0xFF;
+ ASSERT(b>=0&&b<256);
+ fputc(b,file);
+ }
+}
+
+// read_integer()
+
+static uint64 read_integer(FILE * file, int size) {
+ uint64 n;
+ int i;
+ int b;
+ ASSERT(file!=NULL);
+ ASSERT(size>0&&size<=8);
+ n = 0;
+ for (i = 0; i < size; i++) {
+ b = fgetc(file);
+ if (b == EOF) {
+ if (feof(file)) {
+ my_fatal("read_integer(): fgetc(): EOF reached\n");
+ } else { // error
+ my_fatal("read_integer(): fgetc(): %s\n",strerror(errno));
+ }
+ }
+ ASSERT(b>=0&&b<256);
+ n = (n << 8) | b;
+ }
+ return n;
+}
+
+// read_entry_file
+
+static void read_entry_file(FILE *f, entry_t *entry){
+ uint64 n;
+ ASSERT(entry!=NULL);
+ n = entry->key = read_integer(f,8);
+ entry->move = read_integer(f,2);
+ entry->count = read_integer(f,2);
+ entry->n = read_integer(f,2);
+ entry->sum = read_integer(f,2);
+ ASSERT(n==entry->key); // test for mingw compiler bug with anon structs
+}
+
+// write_entry_file
+
+static void write_entry_file(FILE * f, const entry_t * entry) {
+ ASSERT(entry!=NULL);
+ write_integer(f,8,entry->key);
+ write_integer(f,2,entry->move);
+ write_integer(f,2,entry->count);
+ write_integer(f,2,entry->n);
+ write_integer(f,2,entry->sum);
+}
+
+static void print_list(const board_t *board, list_t *list){
+ int i;
+ uint16 move;
+ char move_string[256];
+ for (i = 0; i < list_size(list); i++) {
+ move = list_move(list,i);
+ move_to_san(move,board,move_string,256);
+ printf("%s",move_string);
+ }
+ printf("\n");
+}
+
+// book_load()
+// loads a polyglot book
+
+static void book_load(const char filename[]){
+ FILE* f;
+ entry_t entry[1];
+ int size;
+ int i;
+ int pos;
+ int index;
+ ASSERT(filename!=NULL);
+ if(!(f=fopen(filename,"rb"))){
+ my_fatal("book_load() : can't open file \"%s\" for reading: %s\n",filename,strerror(errno));
+ }
+ fseek(f,0L,SEEK_END); // superportable way to get size of book!
+ size=ftell(f)/16;
+ fseek(f,0,SEEK_SET);
+ for(i=0L;i<size;i++){
+ read_entry_file(f,entry);
+ ASSERT(Book->size<=Book->alloc);
+ if (Book->size == Book->alloc) {
+ // allocate more memoryx
+ resize();
+ }
+ // insert into the book
+ pos = Book->size++;
+ Book->entry[pos].key = entry->key;
+ ASSERT(entry->move!=MoveNone);
+ Book->entry[pos].move = entry->move;
+ Book->entry[pos].count = entry->count;
+ Book->entry[pos].n = entry->n;
+ Book->entry[pos].sum = entry->sum;
+ Book->entry[pos].colour = ColourNone;
+ // find free hash table spot
+ for (index = entry->key & (uint64) Book->mask;
+ Book->hash[index] != NIL;
+ index = (index+1) & Book->mask);
+ // insert into the hash table
+ ASSERT(index>=0&&index<Book->alloc*2);
+ ASSERT(Book->hash[index]==NIL);
+ Book->hash[index] = pos;
+ ASSERT(pos>=0&&pos<Book->size);
+ }
+ fclose(f);
+}
+
+// gen_book_moves()
+// similar signature as gen_legal_moves
+static int gen_book_moves(list_t * list, const board_t * board){
+ int first_pos, pos, index;
+ entry_t entry[1];
+ bool found;
+ list_clear(list);
+ found=FALSE;
+ for (index = board->key & (uint64) Book->mask; (first_pos=Book->hash[index]) != NIL; index = (index+1) & Book->mask) {
+ ASSERT(first_pos>=0&&first_pos<Book->size);
+ if (Book->entry[first_pos].key == board->key) {
+ found=TRUE;
+ break; // found
+ }
+ }
+ if(!found) return -1;
+ if(Book->entry[first_pos].move==MoveNone) return -1;
+ for (pos = first_pos; pos < Book->size; pos++) {
+ *entry=Book->entry[pos];
+ if (entry->key != board->key) break;
+ if (entry->count > 0 &&
+ entry->move != MoveNone &&
+ move_is_legal(entry->move,board)) {
+ list_add_ex(list,entry->move,entry->count);
+ }
+ }
+ return first_pos;
+}
+
+// gen_opp_book_moves()
+// moves to which opponent has a reply in book
+// similar signature as gen_legal_moves
+static void gen_opp_book_moves(list_t * list, const board_t * board){
+ int move;
+ list_t new_list[1], legal_moves[1];
+ board_t new_board[1];
+ int i;
+ list_clear(list);
+ gen_legal_moves(legal_moves,board);
+ for (i = 0; i < list_size(legal_moves); i++) {
+ move = list_move(legal_moves,i);
+ // scratch_board
+ memcpy(new_board, board, sizeof(board_t));
+ move_do(new_board,move);
+ gen_book_moves(new_list,new_board); // wasteful in time but tested!
+ if(list_size(new_list)!=0){
+ list_add(list,move);
+ }
+ }
+}
+
+static void print_moves(info_t *info){
+ board_t board[1];
+ char move_string[256];
+ int i;
+ int color=White;
+ if(!info->output){
+ return;
+ }
+ board_start(board);
+ for(i=0;i<info->height;i++){
+ if(color==White){
+ fprintf(info->output,"%d. ",i/2+1);
+ color=Black;
+ }else{
+ color=White;
+ }
+ move_to_san(info->moves[i],board,move_string,256);
+ fprintf(info->output,"%s", move_string);
+ if(color==colour_opp(info->initial_color)){
+ fprintf(info->output,"{%.0f%%} ",100*info->probs[i]);
+ }else{
+ fprintf(info->output," ");
+ }
+ move_do(board,info->moves[i]);
+ }
+}
+
+static int search_book(board_t *board, info_t *info, search_t search){
+ list_t list[1];
+ board_t new_board[1];
+ uint16 move;
+ int count;
+ int ret;
+ int i;
+ int offset;
+ int pos;
+ int size;
+ int prob_sum;
+ double probs[256];
+ for(i=0;i<256;i++){
+ probs[i]=0.0; // kill compiler warnings
+ }
+ for(i=0;i<info->height;i++){
+ if(board->key==info->keys[i]){
+ if(info->output){
+ fprintf(info->output,"%d: ",info->line);
+ print_moves(info);
+ fprintf(info->output,"{cycle: ply=%d}\n",i);
+ }
+ info->line++;
+ return 1; // end of line because of cycle
+ }
+ }
+ if(!info->book_trans_only || (info->book_trans_only && search==BOOK)){
+ info->keys[info->height]=board->key;
+ size=Book->size; // hack
+ pos=find_entry(board,MoveNone);
+ if(size==Book->size){
+ if(info->output){
+ fprintf(info->output,"%d: ",info->line);
+ print_moves(info);
+ fprintf(info->output,"{trans: line=%d, ply=%d}\n",
+ Book->entry[pos].line,
+ Book->entry[pos].height);
+ }
+ info->line++;
+ return 1; // end of line because of transposition
+ }else{
+ Book->entry[pos].height=info->height;
+ Book->entry[pos].line=info->line;
+ }
+ }
+ count=0;
+ if(search==BOOK){
+ offset=gen_book_moves(list,board);
+ if(info->extended_search){
+ gen_legal_moves(list,board);
+ }
+// ASSERT(offset!=-1);
+ if(offset!=-1){ // only FALSE in starting position for black book
+ Book->entry[offset].colour=board->turn;
+ prob_sum=0;
+ if(!info->extended_search){
+ for(i=0;i<list_size(list);i++){
+ prob_sum+=((uint16)list_value(list,i));
+ }
+ for(i=0;i<list_size(list);i++){
+ probs[i]=((double)((uint16)list_value(list,i)))/((double)prob_sum);
+ }
+ }
+ }
+ }else{
+ gen_opp_book_moves(list,board);
+ }
+ for (i = 0; i < list_size(list); i++) {
+ move = list_move(list,i);
+ memcpy(new_board, board, sizeof(board_t));
+ ASSERT(move_is_legal(move,new_board));
+ move_do(new_board,move);
+ ASSERT(search!=opp_search(search));
+ info->moves[info->height++]=move;
+ if(search==BOOK){
+ info->probs[info->height-1]=probs[i];
+ }
+ ret=search_book(new_board, info, opp_search(search));
+ if(ret==0 && search==BOOK){
+ if(info->output){
+ fprintf(info->output,"%d: ",info->line);
+ print_moves(info);
+ fprintf(info->output,"\n");
+ }
+ info->line++;
+ ret=1; // end of line book move counts for 1
+ }
+ info->height--;
+ ASSERT(info->height>=0);
+ count+=ret;
+ }
+ return count;
+}
+
+void init_info(info_t *info){
+ info->line=1;
+ info->height=0;
+ info->output=NULL;
+ info->initial_color=White;
+ info->book_trans_only=FALSE;
+}
+
+// book_clean()
+// remove MoveNone entries from book and rebuild hash table
+void book_clean(){
+ int read_ptr,write_ptr;
+ write_ptr=0;
+ for(read_ptr=0;read_ptr<Book->size;read_ptr++){
+ if(Book->entry[read_ptr].move!=MoveNone){
+ Book->entry[write_ptr++]=Book->entry[read_ptr];
+ }
+ }
+ Book->size=write_ptr;
+ rebuild_hash_table();
+}
+
+// book_dump()
+
+void book_dump(int argc, char * argv[]) {
+ const char * bin_file=NULL;
+ const char * txt_file=NULL;
+ char string[StringSize];
+ int color=ColourNone;
+ board_t board[1];
+ info_t info[1];
+ int i;
+ FILE *f;
+ my_string_set(&bin_file,"book.bin");
+ for (i = 1; i < argc; i++) {
+ if (FALSE) {
+ } else if (my_string_equal(argv[i],"dump-book")) {
+ // skip
+ } else if (my_string_equal(argv[i],"-bin")) {
+ i++;
+ if (i==argc) my_fatal("book_dump(): missing argument\n");
+ my_string_set(&bin_file,argv[i]);
+ } else if (my_string_equal(argv[i],"-out")) {
+ i++;
+ if (i==argc) my_fatal("book_dump(): missing argument\n");
+ my_string_set(&txt_file,argv[i]);
+ } else if (my_string_equal(argv[i],"-color") || my_string_equal(argv[i],"-colour")) {
+ i++;
+ if (i == argc) my_fatal("book_dump(): missing argument\n");
+ if(my_string_equal(argv[i],"white")){
+ color=White;
+ }else if (my_string_equal(argv[i],"black")){
+ color=Black;
+ }else{
+ my_fatal("book_dump(): unknown color \"%s\"\n",argv[i]);
+ }
+ } else {
+ my_fatal("book_dump(): unknown option \"%s\"\n",argv[i]);
+ }
+ }
+ if(color==ColourNone){
+ my_fatal("book_dump(): you must specify a color\n");
+ }
+ if(txt_file==NULL){
+ snprintf(string,StringSize,"book_%s.txt",(color==White)?"white":"black");
+ my_string_set(&txt_file,string);
+ }
+
+ book_clear();
+ if(!Quiet){printf("loading book ...\n");}
+ book_load(bin_file);
+ board_start(board);
+ init_info(info);
+ info->initial_color=color;
+ if(!(f=fopen(txt_file,"w"))){
+ my_fatal("book_dump(): can't open file \"%s\" for writing: %s",
+ txt_file,strerror(errno));
+ }
+ info->output=f;
+ fprintf(info->output,"Dump of \"%s\" for %s.\n",
+ bin_file,color==White?"white":"black");
+ if(color==White){
+ if(!Quiet){printf("generating lines for white...\n");}
+ search_book(board,info, BOOK);
+ }else{
+ if(!Quiet){printf("generating lines for black...\n");}
+ search_book(board,info, ALL);
+ }
+}
+
+// book_info()
+
+void book_info(int argc,char* argv[]){
+ const char *bin_file=NULL;
+ board_t board[1];
+ info_t info[1];
+ uint64 last_key;
+ int pos;
+ int white_pos,black_pos,total_pos,white_pos_extended,
+ black_pos_extended,white_pos_extended_diff,black_pos_extended_diff;
+ int s;
+ bool extended_search=FALSE;
+ int i;
+ Quiet=TRUE;
+ my_string_set(&bin_file,"book.bin");
+
+ for (i = 1; i < argc; i++) {
+ if (FALSE) {
+ } else if (my_string_equal(argv[i],"info-book")) {
+ // skip
+ } else if (my_string_equal(argv[i],"-bin")) {
+ i++;
+ if (i==argc) my_fatal("book_info(): missing argument\n");
+ my_string_set(&bin_file,argv[i]);
+ } else if (my_string_equal(argv[i],"-exact")) {
+ extended_search=TRUE;
+ } else {
+ my_fatal("book_info(): unknown option \"%s\"\n",argv[i]);
+ }
+ }
+ book_clear();
+ if(!Quiet){printf("loading book ...\n");}
+ book_load(bin_file);
+ s=Book->size;
+
+ board_start(board);
+ init_info(info);
+ info->book_trans_only=FALSE;
+ info->initial_color=White;
+ info->extended_search=FALSE;
+ search_book(board,info, BOOK);
+ printf("Lines for white : %8d\n",info->line-1);
+
+
+ info->line=1;
+ info->height=0;
+ info->initial_color=Black;
+ book_clean();
+ ASSERT(Book->size==s);
+ board_start(board);
+ search_book(board,info, ALL);
+ printf("Lines for black : %8d\n",info->line-1);
+
+ book_clean();
+ ASSERT(Book->size==s);
+ white_pos=0;
+ black_pos=0;
+ total_pos=0;
+ last_key=0;
+ for(pos=0;pos<Book->size;pos++){
+ if(Book->entry[pos].key==last_key){
+ ASSERT(Book->entry[pos].colour==ColourNone);
+ continue;
+ }
+ last_key=Book->entry[pos].key;
+ total_pos++;
+ if(Book->entry[pos].colour==White){
+ white_pos++;
+ }else if(Book->entry[pos].colour==Black){
+ black_pos++;
+ }
+ }
+ printf("Positions on lines for white : %8d\n",white_pos);
+ printf("Positions on lines for black : %8d\n",black_pos);
+
+
+ if(extended_search){
+ init_info(info);
+ info->book_trans_only=TRUE;
+ info->initial_color=White;
+ info->extended_search=TRUE;
+ book_clean();
+ board_start(board);
+ search_book(board,info, BOOK);
+
+ init_info(info);
+ info->book_trans_only=TRUE;
+ info->initial_color=Black;
+ info->extended_search=TRUE;
+ book_clean();
+ board_start(board);
+ search_book(board,info, ALL);
+ book_clean();
+ ASSERT(Book->size==s);
+ white_pos_extended=0;
+ black_pos_extended=0;
+ last_key=0;
+ for(pos=0;pos<Book->size;pos++){
+ if(Book->entry[pos].key==last_key){
+ ASSERT(Book->entry[pos].colour==ColourNone);
+ continue;
+ }
+ last_key=Book->entry[pos].key;
+ if(Book->entry[pos].colour==White){
+ white_pos_extended++;
+ }else if(Book->entry[pos].colour==Black){
+ black_pos_extended++;
+ }
+ }
+ white_pos_extended_diff=white_pos_extended-white_pos;
+ black_pos_extended_diff=black_pos_extended-black_pos;
+ printf("Unreachable white positions(?) : %8d\n",
+ white_pos_extended_diff);
+ printf("Unreachable black positions(?) : %8d\n",
+ black_pos_extended_diff);
+
+ }
+ if(extended_search){
+ printf("Isolated positions : %8d\n",
+ total_pos-white_pos_extended-black_pos_extended);
+ }else{
+ printf("Isolated positions : %8d\n",
+ total_pos-white_pos-black_pos);
+ }
+}
+
+
+
+// end of book_make.cpp
+
projects / polyglot.git / blobdiff