12 #include "book_make.h"
16 #include "move_legal.h"
24 #define COUNT_MAX ((int)16384)
26 static const int NIL = -1;
30 #define opp_search(s) ((s)==BOOK?ALL:BOOK)
38 // Unfortunately the minggw32 cross compiler [4.2.1-sjlj (mingw32-2)]
39 // seems to have a bug with anon structs contained in unions when using -O2.
40 // See the ASSERT below in "read_entry_file"...
41 // To be fair this seems to be illegal in C++
42 // although it is hard to understand why, and the compiler does not complain
87 static double MinScore;
88 static bool RemoveWhite, RemoveBlack;
90 static bool Quiet=FALSE;
92 static book_t Book[1];
96 static void book_clear ();
97 static void book_insert (const char file_name[]);
98 static void book_filter ();
99 static void book_sort ();
100 static void book_save (const char file_name[]);
102 static int find_entry (const board_t * board, int move);
103 static void resize ();
104 static void halve_stats (uint64 key);
106 static bool keep_entry (int pos);
108 static int entry_score (const entry_t * entry);
110 static int key_compare (const void * p1, const void * p2);
112 static void write_integer (FILE * file, int size, uint64 n);
113 static uint64 read_integer(FILE * file, int size);
115 static void read_entry_file(FILE *f, entry_t *entry);
116 static void write_entry_file(FILE * f, const entry_t * entry);
122 void book_make(int argc, char * argv[]) {
125 const char * pgn_file;
126 const char * bin_file;
129 my_string_set(&pgn_file,"book.pgn");
132 my_string_set(&bin_file,"book.bin");
141 for (i = 1; i < argc; i++) {
145 } else if (my_string_equal(argv[i],"make-book")) {
149 } else if (my_string_equal(argv[i],"-pgn")) {
152 if (argv[i] == NULL) my_fatal("book_make(): missing argument\n");
154 my_string_set(&pgn_file,argv[i]);
156 } else if (my_string_equal(argv[i],"-bin")) {
159 if (argv[i] == NULL) my_fatal("book_make(): missing argument\n");
161 my_string_set(&bin_file,argv[i]);
163 } else if (my_string_equal(argv[i],"-max-ply")) {
166 if (argv[i] == NULL) my_fatal("book_make(): missing argument\n");
168 MaxPly = atoi(argv[i]);
171 } else if (my_string_equal(argv[i],"-min-game")) {
174 if (argv[i] == NULL) my_fatal("book_make(): missing argument\n");
176 MinGame = atoi(argv[i]);
179 } else if (my_string_equal(argv[i],"-min-score")) {
182 if (argv[i] == NULL) my_fatal("book_make(): missing argument\n");
184 MinScore = atof(argv[i]) / 100.0;
185 ASSERT(MinScore>=0.0&&MinScore<=1.0);
187 } else if (my_string_equal(argv[i],"-only-white")) {
192 } else if (my_string_equal(argv[i],"-only-black")) {
197 } else if (my_string_equal(argv[i],"-uniform")) {
203 my_fatal("book_make(): unknown option \"%s\"\n",argv[i]);
209 printf("inserting games ...\n");
210 book_insert(pgn_file);
212 printf("filtering entries ...\n");
215 printf("sorting entries ...\n");
218 printf("saving entries ...\n");
221 printf("all done!\n");
226 static void book_clear() {
231 Book->mask = (Book->alloc * 2) - 1;
233 Book->entry = (entry_t *) my_malloc(Book->alloc*sizeof(entry_t));
236 Book->hash = (sint32 *) my_malloc((Book->alloc*2)*sizeof(sint32));
237 for (index = 0; index < Book->alloc*2; index++) {
238 Book->hash[index] = NIL;
244 static void book_insert(const char file_name[]) {
254 ASSERT(file_name!=NULL);
261 pgn_open(pgn,file_name);
263 while (pgn_next_game(pgn)) {
270 } else if (my_string_equal(pgn->result,"1-0")) {
272 } else if (my_string_equal(pgn->result,"0-1")) {
276 while (pgn_next_move(pgn,string,256)) {
280 move = move_from_san(string,board);
282 if (move == MoveNone || !move_is_legal(move,board)) {
283 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);
286 pos = find_entry(board,move);
288 Book->entry[pos].n++;
289 Book->entry[pos].sum += result+1;
291 if (Book->entry[pos].n >= COUNT_MAX) {
292 halve_stats(board->key);
301 if (pgn->game_nb % 10000 == 0) printf("%d games ...\n",pgn->game_nb);
306 printf("%d game%s.\n",pgn->game_nb,(pgn->game_nb>2)?"s":"");
307 printf("%d entries.\n",Book->size);
314 static void book_filter() {
322 for (src = 0; src < Book->size; src++) {
323 if (keep_entry(src)) Book->entry[dst++] = Book->entry[src];
326 ASSERT(dst>=0&&dst<=Book->size);
329 printf("%d entries.\n",Book->size);
334 static void book_sort() {
336 // sort keys for binary search
338 qsort(Book->entry,Book->size,sizeof(entry_t),&key_compare);
343 static void book_save(const char file_name[]) {
347 char *header, *raw_header;
351 ASSERT(file_name!=NULL);
353 file = fopen(file_name,"wb");
354 if (file == NULL) my_fatal("book_save(): can't open file \"%s\" for writing: %s\n",file_name,strerror(errno));
356 pgheader_create(&header,"normal","Created by Polyglot.");
357 pgheader_create_raw(&raw_header,header,&size);
363 fputc(raw_header[i],file);
369 for (pos = 0; pos < Book->size; pos++) {
371 ASSERT(keep_entry(pos));
372 /* null keys are reserved for the header */
373 if(Book->entry[pos].key!=U64(0x0)){
374 write_integer(file,8,Book->entry[pos].key);
375 write_integer(file,2,Book->entry[pos].move);
376 write_integer(file,2,entry_score(&Book->entry[pos]));
377 write_integer(file,2,0);
378 write_integer(file,2,0);
387 static int find_entry(const board_t * board, int move) {
394 ASSERT(move==MoveNone || move_is_ok(move));
396 ASSERT(move==MoveNone || move_is_legal(move,board));
404 for (index = key & (uint64) Book->mask; (pos=Book->hash[index]) != NIL; index = (index+1) & Book->mask) {
406 ASSERT(pos>=0&&pos<Book->size);
408 if (Book->entry[pos].key == key && Book->entry[pos].move == move) {
415 ASSERT(Book->size<=Book->alloc);
417 if (Book->size == Book->alloc) {
419 // allocate more memory
423 for (index = key & (uint64) Book->mask; Book->hash[index] != NIL; index = (index+1) & Book->mask)
427 // create a new entry
429 ASSERT(Book->size<Book->alloc);
432 Book->entry[pos].key = key;
433 Book->entry[pos].move = move;
434 Book->entry[pos].n = 0;
435 Book->entry[pos].sum = 0;
436 Book->entry[pos].colour = board->turn;
438 // insert into the hash table
440 ASSERT(index>=0&&index<Book->alloc*2);
441 ASSERT(Book->hash[index]==NIL);
442 Book->hash[index] = pos;
444 ASSERT(pos>=0&&pos<Book->size);
449 // rebuild_hash_table
451 static void rebuild_hash_table(){
453 for (index = 0; index < Book->alloc*2; index++) {
454 Book->hash[index] = NIL;
456 for (pos = 0; pos < Book->size; pos++) {
457 for (index = Book->entry[pos].key & (uint64) Book->mask; Book->hash[index] != NIL; index = (index+1) & Book->mask)
459 ASSERT(index>=0&&index<Book->alloc*2);
460 Book->hash[index] = pos;
464 static void resize() {
468 ASSERT(Book->size==Book->alloc);
471 Book->mask = (Book->alloc * 2) - 1;
474 size += Book->alloc * sizeof(entry_t);
475 size += (Book->alloc*2) * sizeof(sint32);
477 if (size >= 1048576) if(!Quiet){
478 printf("allocating %gMB ...\n",((double)size)/1048576.0);
483 Book->entry = (entry_t *) my_realloc(Book->entry,Book->alloc*sizeof(entry_t));
484 Book->hash = (sint32 *) my_realloc(Book->hash,(Book->alloc*2)*sizeof(sint32));
486 // rebuild hash table
488 rebuild_hash_table();
494 static void halve_stats(uint64 key) {
501 for (index = key & (uint64) Book->mask; (pos=Book->hash[index]) != NIL; index = (index+1) & Book->mask) {
503 ASSERT(pos>=0&&pos<Book->size);
505 if (Book->entry[pos].key == key) {
506 Book->entry[pos].n = (Book->entry[pos].n + 1) / 2;
507 Book->entry[pos].sum = (Book->entry[pos].sum + 1) / 2;
514 static bool keep_entry(int pos) {
516 const entry_t * entry;
520 ASSERT(pos>=0&&pos<Book->size);
522 entry = &Book->entry[pos];
524 // if (entry->n == 0) return FALSE;
525 if (entry->n < MinGame) return FALSE;
527 if (entry->sum == 0) return FALSE;
529 score = (((double)entry->sum) / ((double)entry->n)) / 2.0;
530 ASSERT(score>=0.0&&score<=1.0);
532 if (score < MinScore) return FALSE;
534 colour = entry->colour;
536 if ((RemoveWhite && colour_is_white(colour))
537 || (RemoveBlack && colour_is_black(colour))) {
541 if (entry_score(entry) == 0) return FALSE; // REMOVE ME?
548 static int entry_score(const entry_t * entry) {
554 // score = entry->n; // popularity
555 score = entry->sum; // "expectancy"
557 if (Uniform) score = 1;
566 static int key_compare(const void * p1, const void * p2) {
568 const entry_t * entry_1, * entry_2;
573 entry_1 = (const entry_t *) p1;
574 entry_2 = (const entry_t *) p2;
576 if (entry_1->key > entry_2->key) {
578 } else if (entry_1->key < entry_2->key) {
581 return entry_score(entry_2) - entry_score(entry_1); // highest score first
587 static void write_integer(FILE * file, int size, uint64 n) {
593 ASSERT(size>0&&size<=8);
594 ASSERT(size==8||n>>(size*8)==0);
596 for (i = size-1; i >= 0; i--) {
597 b = (n >> (i*8)) & 0xFF;
605 static uint64 read_integer(FILE * file, int size) {
610 ASSERT(size>0&&size<=8);
612 for (i = 0; i < size; i++) {
616 my_fatal("read_integer(): fgetc(): EOF reached\n");
618 my_fatal("read_integer(): fgetc(): %s\n",strerror(errno));
629 static void read_entry_file(FILE *f, entry_t *entry){
632 n = entry->key = read_integer(f,8);
633 entry->move = read_integer(f,2);
634 entry->count = read_integer(f,2);
635 entry->n = read_integer(f,2);
636 entry->sum = read_integer(f,2);
637 ASSERT(n==entry->key); // test for mingw compiler bug with anon structs
642 static void write_entry_file(FILE * f, const entry_t * entry) {
644 write_integer(f,8,entry->key);
645 write_integer(f,2,entry->move);
646 write_integer(f,2,entry->count);
647 write_integer(f,2,entry->n);
648 write_integer(f,2,entry->sum);
651 static void print_list(const board_t *board, list_t *list){
654 char move_string[256];
655 for (i = 0; i < list_size(list); i++) {
656 move = list_move(list,i);
657 move_to_san(move,board,move_string,256);
658 printf("%s",move_string);
664 // loads a polyglot book
666 static void book_load(const char filename[]){
673 ASSERT(filename!=NULL);
674 if(!(f=fopen(filename,"rb"))){
675 my_fatal("book_load() : can't open file \"%s\" for reading: %s\n",filename,strerror(errno));
677 fseek(f,0L,SEEK_END); // superportable way to get size of book!
680 for(i=0L;i<size;i++){
681 read_entry_file(f,entry);
682 ASSERT(Book->size<=Book->alloc);
683 if (Book->size == Book->alloc) {
684 // allocate more memoryx
687 // insert into the book
689 Book->entry[pos].key = entry->key;
690 ASSERT(entry->move!=MoveNone);
691 Book->entry[pos].move = entry->move;
692 Book->entry[pos].count = entry->count;
693 Book->entry[pos].n = entry->n;
694 Book->entry[pos].sum = entry->sum;
695 Book->entry[pos].colour = ColourNone;
696 // find free hash table spot
697 for (index = entry->key & (uint64) Book->mask;
698 Book->hash[index] != NIL;
699 index = (index+1) & Book->mask);
700 // insert into the hash table
701 ASSERT(index>=0&&index<Book->alloc*2);
702 ASSERT(Book->hash[index]==NIL);
703 Book->hash[index] = pos;
704 ASSERT(pos>=0&&pos<Book->size);
710 // similar signature as gen_legal_moves
711 static int gen_book_moves(list_t * list, const board_t * board){
712 int first_pos, pos, index;
717 for (index = board->key & (uint64) Book->mask; (first_pos=Book->hash[index]) != NIL; index = (index+1) & Book->mask) {
718 ASSERT(first_pos>=0&&first_pos<Book->size);
719 if (Book->entry[first_pos].key == board->key) {
724 if(!found) return -1;
725 if(Book->entry[first_pos].move==MoveNone) return -1;
726 for (pos = first_pos; pos < Book->size; pos++) {
727 *entry=Book->entry[pos];
728 if (entry->key != board->key) break;
729 if (entry->count > 0 &&
730 entry->move != MoveNone &&
731 move_is_legal(entry->move,board)) {
732 list_add_ex(list,entry->move,entry->count);
738 // gen_opp_book_moves()
739 // moves to which opponent has a reply in book
740 // similar signature as gen_legal_moves
741 static void gen_opp_book_moves(list_t * list, const board_t * board){
743 list_t new_list[1], legal_moves[1];
744 board_t new_board[1];
747 gen_legal_moves(legal_moves,board);
748 for (i = 0; i < list_size(legal_moves); i++) {
749 move = list_move(legal_moves,i);
751 memcpy(new_board, board, sizeof(board_t));
752 move_do(new_board,move);
753 gen_book_moves(new_list,new_board); // wasteful in time but tested!
754 if(list_size(new_list)!=0){
760 static void print_moves(info_t *info){
762 char move_string[256];
769 for(i=0;i<info->height;i++){
771 fprintf(info->output,"%d. ",i/2+1);
776 move_to_san(info->moves[i],board,move_string,256);
777 fprintf(info->output,"%s", move_string);
778 if(color==colour_opp(info->initial_color)){
779 fprintf(info->output,"{%.0f%%} ",100*info->probs[i]);
781 fprintf(info->output," ");
783 move_do(board,info->moves[i]);
787 static int search_book(board_t *board, info_t *info, search_t search){
789 board_t new_board[1];
800 probs[i]=0.0; // kill compiler warnings
802 for(i=0;i<info->height;i++){
803 if(board->key==info->keys[i]){
805 fprintf(info->output,"%d: ",info->line);
807 fprintf(info->output,"{cycle: ply=%d}\n",i);
810 return 1; // end of line because of cycle
813 if(!info->book_trans_only || (info->book_trans_only && search==BOOK)){
814 info->keys[info->height]=board->key;
815 size=Book->size; // hack
816 pos=find_entry(board,MoveNone);
817 if(size==Book->size){
819 fprintf(info->output,"%d: ",info->line);
821 fprintf(info->output,"{trans: line=%d, ply=%d}\n",
822 Book->entry[pos].line,
823 Book->entry[pos].height);
826 return 1; // end of line because of transposition
828 Book->entry[pos].height=info->height;
829 Book->entry[pos].line=info->line;
834 offset=gen_book_moves(list,board);
835 if(info->extended_search){
836 gen_legal_moves(list,board);
838 // ASSERT(offset!=-1);
839 if(offset!=-1){ // only FALSE in starting position for black book
840 Book->entry[offset].colour=board->turn;
842 if(!info->extended_search){
843 for(i=0;i<list_size(list);i++){
844 prob_sum+=((uint16)list_value(list,i));
846 for(i=0;i<list_size(list);i++){
847 probs[i]=((double)((uint16)list_value(list,i)))/((double)prob_sum);
852 gen_opp_book_moves(list,board);
854 for (i = 0; i < list_size(list); i++) {
855 move = list_move(list,i);
856 memcpy(new_board, board, sizeof(board_t));
857 ASSERT(move_is_legal(move,new_board));
858 move_do(new_board,move);
859 ASSERT(search!=opp_search(search));
860 info->moves[info->height++]=move;
862 info->probs[info->height-1]=probs[i];
864 ret=search_book(new_board, info, opp_search(search));
865 if(ret==0 && search==BOOK){
867 fprintf(info->output,"%d: ",info->line);
869 fprintf(info->output,"\n");
872 ret=1; // end of line book move counts for 1
875 ASSERT(info->height>=0);
881 void init_info(info_t *info){
885 info->initial_color=White;
886 info->book_trans_only=FALSE;
890 // remove MoveNone entries from book and rebuild hash table
892 int read_ptr,write_ptr;
894 for(read_ptr=0;read_ptr<Book->size;read_ptr++){
895 if(Book->entry[read_ptr].move!=MoveNone){
896 Book->entry[write_ptr++]=Book->entry[read_ptr];
899 Book->size=write_ptr;
900 rebuild_hash_table();
905 void book_dump(int argc, char * argv[]) {
906 const char * bin_file=NULL;
907 const char * txt_file=NULL;
908 char string[StringSize];
909 int color=ColourNone;
914 my_string_set(&bin_file,"book.bin");
915 for (i = 1; i < argc; i++) {
917 } else if (my_string_equal(argv[i],"dump-book")) {
919 } else if (my_string_equal(argv[i],"-bin")) {
921 if (i==argc) my_fatal("book_dump(): missing argument\n");
922 my_string_set(&bin_file,argv[i]);
923 } else if (my_string_equal(argv[i],"-out")) {
925 if (i==argc) my_fatal("book_dump(): missing argument\n");
926 my_string_set(&txt_file,argv[i]);
927 } else if (my_string_equal(argv[i],"-color") || my_string_equal(argv[i],"-colour")) {
929 if (i == argc) my_fatal("book_dump(): missing argument\n");
930 if(my_string_equal(argv[i],"white")){
932 }else if (my_string_equal(argv[i],"black")){
935 my_fatal("book_dump(): unknown color \"%s\"\n",argv[i]);
938 my_fatal("book_dump(): unknown option \"%s\"\n",argv[i]);
941 if(color==ColourNone){
942 my_fatal("book_dump(): you must specify a color\n");
945 snprintf(string,StringSize,"book_%s.txt",(color==White)?"white":"black");
946 my_string_set(&txt_file,string);
950 if(!Quiet){printf("loading book ...\n");}
954 info->initial_color=color;
955 if(!(f=fopen(txt_file,"w"))){
956 my_fatal("book_dump(): can't open file \"%s\" for writing: %s",
957 txt_file,strerror(errno));
960 fprintf(info->output,"Dump of \"%s\" for %s.\n",
961 bin_file,color==White?"white":"black");
963 if(!Quiet){printf("generating lines for white...\n");}
964 search_book(board,info, BOOK);
966 if(!Quiet){printf("generating lines for black...\n");}
967 search_book(board,info, ALL);
973 void book_info(int argc,char* argv[]){
974 const char *bin_file=NULL;
979 int white_pos,black_pos,total_pos,white_pos_extended,
980 black_pos_extended,white_pos_extended_diff,black_pos_extended_diff;
982 bool extended_search=FALSE;
985 my_string_set(&bin_file,"book.bin");
987 for (i = 1; i < argc; i++) {
989 } else if (my_string_equal(argv[i],"info-book")) {
991 } else if (my_string_equal(argv[i],"-bin")) {
993 if (i==argc) my_fatal("book_info(): missing argument\n");
994 my_string_set(&bin_file,argv[i]);
995 } else if (my_string_equal(argv[i],"-exact")) {
996 extended_search=TRUE;
998 my_fatal("book_info(): unknown option \"%s\"\n",argv[i]);
1002 if(!Quiet){printf("loading book ...\n");}
1003 book_load(bin_file);
1008 info->book_trans_only=FALSE;
1009 info->initial_color=White;
1010 info->extended_search=FALSE;
1011 search_book(board,info, BOOK);
1012 printf("Lines for white : %8d\n",info->line-1);
1017 info->initial_color=Black;
1019 ASSERT(Book->size==s);
1021 search_book(board,info, ALL);
1022 printf("Lines for black : %8d\n",info->line-1);
1025 ASSERT(Book->size==s);
1030 for(pos=0;pos<Book->size;pos++){
1031 if(Book->entry[pos].key==last_key){
1032 ASSERT(Book->entry[pos].colour==ColourNone);
1035 last_key=Book->entry[pos].key;
1037 if(Book->entry[pos].colour==White){
1039 }else if(Book->entry[pos].colour==Black){
1043 printf("Positions on lines for white : %8d\n",white_pos);
1044 printf("Positions on lines for black : %8d\n",black_pos);
1047 if(extended_search){
1049 info->book_trans_only=TRUE;
1050 info->initial_color=White;
1051 info->extended_search=TRUE;
1054 search_book(board,info, BOOK);
1057 info->book_trans_only=TRUE;
1058 info->initial_color=Black;
1059 info->extended_search=TRUE;
1062 search_book(board,info, ALL);
1064 ASSERT(Book->size==s);
1065 white_pos_extended=0;
1066 black_pos_extended=0;
1068 for(pos=0;pos<Book->size;pos++){
1069 if(Book->entry[pos].key==last_key){
1070 ASSERT(Book->entry[pos].colour==ColourNone);
1073 last_key=Book->entry[pos].key;
1074 if(Book->entry[pos].colour==White){
1075 white_pos_extended++;
1076 }else if(Book->entry[pos].colour==Black){
1077 black_pos_extended++;
1080 white_pos_extended_diff=white_pos_extended-white_pos;
1081 black_pos_extended_diff=black_pos_extended-black_pos;
1082 printf("Unreachable white positions(?) : %8d\n",
1083 white_pos_extended_diff);
1084 printf("Unreachable black positions(?) : %8d\n",
1085 black_pos_extended_diff);
1088 if(extended_search){
1089 printf("Isolated positions : %8d\n",
1090 total_pos-white_pos_extended-black_pos_extended);
1092 printf("Isolated positions : %8d\n",
1093 total_pos-white_pos-black_pos);
1099 // end of book_make.cpp