12 #include "book_make.h"
16 #include "move_legal.h"
23 #define COUNT_MAX ((int)16384)
25 static const int NIL = -1;
29 #define opp_search(s) ((s)==BOOK?ALL:BOOK)
37 // Unfortunately the minggw32 cross compiler [4.2.1-sjlj (mingw32-2)]
38 // seems to have a bug with anon structs contained in unions when using -O2.
39 // See the ASSERT below in "read_entry_file"...
40 // To be fair this seems to be illegal in C++
41 // although it is hard to understand why, and the compiler does not complain
86 static double MinScore;
87 static bool RemoveWhite, RemoveBlack;
89 static bool Quiet=FALSE;
91 static book_t Book[1];
95 static void book_clear ();
96 static void book_insert (const char file_name[]);
97 static void book_filter ();
98 static void book_sort ();
99 static void book_save (const char file_name[]);
101 static int find_entry (const board_t * board, int move);
102 static void resize ();
103 static void halve_stats (uint64 key);
105 static bool keep_entry (int pos);
107 static int entry_score (const entry_t * entry);
109 static int key_compare (const void * p1, const void * p2);
111 static void write_integer (FILE * file, int size, uint64 n);
112 static uint64 read_integer(FILE * file, int size);
114 static void read_entry_file(FILE *f, entry_t *entry);
115 static void write_entry_file(FILE * f, const entry_t * entry);
121 void book_make(int argc, char * argv[]) {
124 const char * pgn_file;
125 const char * bin_file;
128 my_string_set(&pgn_file,"book.pgn");
131 my_string_set(&bin_file,"book.bin");
140 for (i = 1; i < argc; i++) {
144 } else if (my_string_equal(argv[i],"make-book")) {
148 } else if (my_string_equal(argv[i],"-pgn")) {
151 if (argv[i] == NULL) my_fatal("book_make(): missing argument\n");
153 my_string_set(&pgn_file,argv[i]);
155 } else if (my_string_equal(argv[i],"-bin")) {
158 if (argv[i] == NULL) my_fatal("book_make(): missing argument\n");
160 my_string_set(&bin_file,argv[i]);
162 } else if (my_string_equal(argv[i],"-max-ply")) {
165 if (argv[i] == NULL) my_fatal("book_make(): missing argument\n");
167 MaxPly = atoi(argv[i]);
170 } else if (my_string_equal(argv[i],"-min-game")) {
173 if (argv[i] == NULL) my_fatal("book_make(): missing argument\n");
175 MinGame = atoi(argv[i]);
178 } else if (my_string_equal(argv[i],"-min-score")) {
181 if (argv[i] == NULL) my_fatal("book_make(): missing argument\n");
183 MinScore = atof(argv[i]) / 100.0;
184 ASSERT(MinScore>=0.0&&MinScore<=1.0);
186 } else if (my_string_equal(argv[i],"-only-white")) {
191 } else if (my_string_equal(argv[i],"-only-black")) {
196 } else if (my_string_equal(argv[i],"-uniform")) {
202 my_fatal("book_make(): unknown option \"%s\"\n",argv[i]);
208 printf("inserting games ...\n");
209 book_insert(pgn_file);
211 printf("filtering entries ...\n");
214 printf("sorting entries ...\n");
217 printf("saving entries ...\n");
220 printf("all done!\n");
225 static void book_clear() {
230 Book->mask = (Book->alloc * 2) - 1;
232 Book->entry = (entry_t *) my_malloc(Book->alloc*sizeof(entry_t));
235 Book->hash = (sint32 *) my_malloc((Book->alloc*2)*sizeof(sint32));
236 for (index = 0; index < Book->alloc*2; index++) {
237 Book->hash[index] = NIL;
243 static void book_insert(const char file_name[]) {
253 ASSERT(file_name!=NULL);
260 pgn_open(pgn,file_name);
262 while (pgn_next_game(pgn)) {
269 } else if (my_string_equal(pgn->result,"1-0")) {
271 } else if (my_string_equal(pgn->result,"0-1")) {
275 while (pgn_next_move(pgn,string,256)) {
279 move = move_from_san(string,board);
281 if (move == MoveNone || !move_is_legal(move,board)) {
282 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);
285 pos = find_entry(board,move);
287 Book->entry[pos].n++;
288 Book->entry[pos].sum += result+1;
290 if (Book->entry[pos].n >= COUNT_MAX) {
291 halve_stats(board->key);
300 if (pgn->game_nb % 10000 == 0) printf("%d games ...\n",pgn->game_nb);
305 printf("%d game%s.\n",pgn->game_nb,(pgn->game_nb>2)?"s":"");
306 printf("%d entries.\n",Book->size);
313 static void book_filter() {
321 for (src = 0; src < Book->size; src++) {
322 if (keep_entry(src)) Book->entry[dst++] = Book->entry[src];
325 ASSERT(dst>=0&&dst<=Book->size);
328 printf("%d entries.\n",Book->size);
333 static void book_sort() {
335 // sort keys for binary search
337 qsort(Book->entry,Book->size,sizeof(entry_t),&key_compare);
342 static void book_save(const char file_name[]) {
347 ASSERT(file_name!=NULL);
349 file = fopen(file_name,"wb");
350 if (file == NULL) my_fatal("book_save(): can't open file \"%s\" for writing: %s\n",file_name,strerror(errno));
354 for (pos = 0; pos < Book->size; pos++) {
356 ASSERT(keep_entry(pos));
358 write_integer(file,8,Book->entry[pos].key);
359 write_integer(file,2,Book->entry[pos].move);
360 write_integer(file,2,entry_score(&Book->entry[pos]));
361 write_integer(file,2,0);
362 write_integer(file,2,0);
370 static int find_entry(const board_t * board, int move) {
377 ASSERT(move==MoveNone || move_is_ok(move));
379 ASSERT(move==MoveNone || move_is_legal(move,board));
387 for (index = key & (uint64) Book->mask; (pos=Book->hash[index]) != NIL; index = (index+1) & Book->mask) {
389 ASSERT(pos>=0&&pos<Book->size);
391 if (Book->entry[pos].key == key && Book->entry[pos].move == move) {
398 ASSERT(Book->size<=Book->alloc);
400 if (Book->size == Book->alloc) {
402 // allocate more memory
406 for (index = key & (uint64) Book->mask; Book->hash[index] != NIL; index = (index+1) & Book->mask)
410 // create a new entry
412 ASSERT(Book->size<Book->alloc);
415 Book->entry[pos].key = key;
416 Book->entry[pos].move = move;
417 Book->entry[pos].n = 0;
418 Book->entry[pos].sum = 0;
419 Book->entry[pos].colour = board->turn;
421 // insert into the hash table
423 ASSERT(index>=0&&index<Book->alloc*2);
424 ASSERT(Book->hash[index]==NIL);
425 Book->hash[index] = pos;
427 ASSERT(pos>=0&&pos<Book->size);
432 // rebuild_hash_table
434 static void rebuild_hash_table(){
436 for (index = 0; index < Book->alloc*2; index++) {
437 Book->hash[index] = NIL;
439 for (pos = 0; pos < Book->size; pos++) {
440 for (index = Book->entry[pos].key & (uint64) Book->mask; Book->hash[index] != NIL; index = (index+1) & Book->mask)
442 ASSERT(index>=0&&index<Book->alloc*2);
443 Book->hash[index] = pos;
447 static void resize() {
451 ASSERT(Book->size==Book->alloc);
454 Book->mask = (Book->alloc * 2) - 1;
457 size += Book->alloc * sizeof(entry_t);
458 size += (Book->alloc*2) * sizeof(sint32);
460 if (size >= 1048576) if(!Quiet){
461 printf("allocating %gMB ...\n",((double)size)/1048576.0);
466 Book->entry = (entry_t *) my_realloc(Book->entry,Book->alloc*sizeof(entry_t));
467 Book->hash = (sint32 *) my_realloc(Book->hash,(Book->alloc*2)*sizeof(sint32));
469 // rebuild hash table
471 rebuild_hash_table();
477 static void halve_stats(uint64 key) {
484 for (index = key & (uint64) Book->mask; (pos=Book->hash[index]) != NIL; index = (index+1) & Book->mask) {
486 ASSERT(pos>=0&&pos<Book->size);
488 if (Book->entry[pos].key == key) {
489 Book->entry[pos].n = (Book->entry[pos].n + 1) / 2;
490 Book->entry[pos].sum = (Book->entry[pos].sum + 1) / 2;
497 static bool keep_entry(int pos) {
499 const entry_t * entry;
503 ASSERT(pos>=0&&pos<Book->size);
505 entry = &Book->entry[pos];
507 // if (entry->n == 0) return FALSE;
508 if (entry->n < MinGame) return FALSE;
510 if (entry->sum == 0) return FALSE;
512 score = (((double)entry->sum) / ((double)entry->n)) / 2.0;
513 ASSERT(score>=0.0&&score<=1.0);
515 if (score < MinScore) return FALSE;
517 colour = entry->colour;
519 if ((RemoveWhite && colour_is_white(colour))
520 || (RemoveBlack && colour_is_black(colour))) {
524 if (entry_score(entry) == 0) return FALSE; // REMOVE ME?
531 static int entry_score(const entry_t * entry) {
537 // score = entry->n; // popularity
538 score = entry->sum; // "expectancy"
540 if (Uniform) score = 1;
549 static int key_compare(const void * p1, const void * p2) {
551 const entry_t * entry_1, * entry_2;
556 entry_1 = (const entry_t *) p1;
557 entry_2 = (const entry_t *) p2;
559 if (entry_1->key > entry_2->key) {
561 } else if (entry_1->key < entry_2->key) {
564 return entry_score(entry_2) - entry_score(entry_1); // highest score first
570 static void write_integer(FILE * file, int size, uint64 n) {
576 ASSERT(size>0&&size<=8);
577 ASSERT(size==8||n>>(size*8)==0);
579 for (i = size-1; i >= 0; i--) {
580 b = (n >> (i*8)) & 0xFF;
588 static uint64 read_integer(FILE * file, int size) {
593 ASSERT(size>0&&size<=8);
595 for (i = 0; i < size; i++) {
599 my_fatal("read_integer(): fgetc(): EOF reached\n");
601 my_fatal("read_integer(): fgetc(): %s\n",strerror(errno));
612 static void read_entry_file(FILE *f, entry_t *entry){
615 n = entry->key = read_integer(f,8);
616 entry->move = read_integer(f,2);
617 entry->count = read_integer(f,2);
618 entry->n = read_integer(f,2);
619 entry->sum = read_integer(f,2);
620 ASSERT(n==entry->key); // test for mingw compiler bug with anon structs
625 static void write_entry_file(FILE * f, const entry_t * entry) {
627 write_integer(f,8,entry->key);
628 write_integer(f,2,entry->move);
629 write_integer(f,2,entry->count);
630 write_integer(f,2,entry->n);
631 write_integer(f,2,entry->sum);
634 static void print_list(const board_t *board, list_t *list){
637 char move_string[256];
638 for (i = 0; i < list_size(list); i++) {
639 move = list_move(list,i);
640 move_to_san(move,board,move_string,256);
641 printf("%s",move_string);
647 // loads a polyglot book
649 static void book_load(const char filename[]){
656 ASSERT(filename!=NULL);
657 if(!(f=fopen(filename,"rb"))){
658 my_fatal("book_load() : can't open file \"%s\" for reading: %s\n",filename,strerror(errno));
660 fseek(f,0L,SEEK_END); // superportable way to get size of book!
663 for(i=0L;i<size;i++){
664 read_entry_file(f,entry);
665 ASSERT(Book->size<=Book->alloc);
666 if (Book->size == Book->alloc) {
667 // allocate more memoryx
670 // insert into the book
672 Book->entry[pos].key = entry->key;
673 ASSERT(entry->move!=MoveNone);
674 Book->entry[pos].move = entry->move;
675 Book->entry[pos].count = entry->count;
676 Book->entry[pos].n = entry->n;
677 Book->entry[pos].sum = entry->sum;
678 Book->entry[pos].colour = ColourNone;
679 // find free hash table spot
680 for (index = entry->key & (uint64) Book->mask;
681 Book->hash[index] != NIL;
682 index = (index+1) & Book->mask);
683 // insert into the hash table
684 ASSERT(index>=0&&index<Book->alloc*2);
685 ASSERT(Book->hash[index]==NIL);
686 Book->hash[index] = pos;
687 ASSERT(pos>=0&&pos<Book->size);
693 // similar signature as gen_legal_moves
694 static int gen_book_moves(list_t * list, const board_t * board){
695 int first_pos, pos, index;
700 for (index = board->key & (uint64) Book->mask; (first_pos=Book->hash[index]) != NIL; index = (index+1) & Book->mask) {
701 ASSERT(first_pos>=0&&first_pos<Book->size);
702 if (Book->entry[first_pos].key == board->key) {
707 if(!found) return -1;
708 if(Book->entry[first_pos].move==MoveNone) return -1;
709 for (pos = first_pos; pos < Book->size; pos++) {
710 *entry=Book->entry[pos];
711 if (entry->key != board->key) break;
712 if (entry->count > 0 &&
713 entry->move != MoveNone &&
714 move_is_legal(entry->move,board)) {
715 list_add_ex(list,entry->move,entry->count);
721 // gen_opp_book_moves()
722 // moves to which opponent has a reply in book
723 // similar signature as gen_legal_moves
724 static void gen_opp_book_moves(list_t * list, const board_t * board){
726 list_t new_list[1], legal_moves[1];
727 board_t new_board[1];
730 gen_legal_moves(legal_moves,board);
731 for (i = 0; i < list_size(legal_moves); i++) {
732 move = list_move(legal_moves,i);
734 memcpy(new_board, board, sizeof(board_t));
735 move_do(new_board,move);
736 gen_book_moves(new_list,new_board); // wasteful in time but tested!
737 if(list_size(new_list)!=0){
743 static void print_moves(info_t *info){
745 char move_string[256];
752 for(i=0;i<info->height;i++){
754 fprintf(info->output,"%d. ",i/2+1);
759 move_to_san(info->moves[i],board,move_string,256);
760 fprintf(info->output,"%s", move_string);
761 if(color==colour_opp(info->initial_color)){
762 fprintf(info->output,"{%.0f%%} ",100*info->probs[i]);
764 fprintf(info->output," ");
766 move_do(board,info->moves[i]);
770 static int search_book(board_t *board, info_t *info, search_t search){
772 board_t new_board[1];
783 probs[i]=0.0; // kill compiler warnings
785 for(i=0;i<info->height;i++){
786 if(board->key==info->keys[i]){
788 fprintf(info->output,"%d: ",info->line);
790 fprintf(info->output,"{cycle: ply=%d}\n",i);
793 return 1; // end of line because of cycle
796 if(!info->book_trans_only || (info->book_trans_only && search==BOOK)){
797 info->keys[info->height]=board->key;
798 size=Book->size; // hack
799 pos=find_entry(board,MoveNone);
800 if(size==Book->size){
802 fprintf(info->output,"%d: ",info->line);
804 fprintf(info->output,"{trans: line=%d, ply=%d}\n",
805 Book->entry[pos].line,
806 Book->entry[pos].height);
809 return 1; // end of line because of transposition
811 Book->entry[pos].height=info->height;
812 Book->entry[pos].line=info->line;
817 offset=gen_book_moves(list,board);
818 if(info->extended_search){
819 gen_legal_moves(list,board);
821 // ASSERT(offset!=-1);
822 if(offset!=-1){ // only FALSE in starting position for black book
823 Book->entry[offset].colour=board->turn;
825 if(!info->extended_search){
826 for(i=0;i<list_size(list);i++){
827 prob_sum+=((uint16)list_value(list,i));
829 for(i=0;i<list_size(list);i++){
830 probs[i]=((double)((uint16)list_value(list,i)))/((double)prob_sum);
835 gen_opp_book_moves(list,board);
837 for (i = 0; i < list_size(list); i++) {
838 move = list_move(list,i);
839 memcpy(new_board, board, sizeof(board_t));
840 ASSERT(move_is_legal(move,new_board));
841 move_do(new_board,move);
842 ASSERT(search!=opp_search(search));
843 info->moves[info->height++]=move;
845 info->probs[info->height-1]=probs[i];
847 ret=search_book(new_board, info, opp_search(search));
848 if(ret==0 && search==BOOK){
850 fprintf(info->output,"%d: ",info->line);
852 fprintf(info->output,"\n");
855 ret=1; // end of line book move counts for 1
858 ASSERT(info->height>=0);
864 void init_info(info_t *info){
868 info->initial_color=White;
869 info->book_trans_only=FALSE;
873 // remove MoveNone entries from book and rebuild hash table
875 int read_ptr,write_ptr;
877 for(read_ptr=0;read_ptr<Book->size;read_ptr++){
878 if(Book->entry[read_ptr].move!=MoveNone){
879 Book->entry[write_ptr++]=Book->entry[read_ptr];
882 Book->size=write_ptr;
883 rebuild_hash_table();
888 void book_dump(int argc, char * argv[]) {
889 const char * bin_file=NULL;
890 const char * txt_file=NULL;
891 char string[StringSize];
892 int color=ColourNone;
897 my_string_set(&bin_file,"book.bin");
898 for (i = 1; i < argc; i++) {
900 } else if (my_string_equal(argv[i],"dump-book")) {
902 } else if (my_string_equal(argv[i],"-bin")) {
904 if (i==argc) my_fatal("book_dump(): missing argument\n");
905 my_string_set(&bin_file,argv[i]);
906 } else if (my_string_equal(argv[i],"-out")) {
908 if (i==argc) my_fatal("book_dump(): missing argument\n");
909 my_string_set(&txt_file,argv[i]);
910 } else if (my_string_equal(argv[i],"-color") || my_string_equal(argv[i],"-colour")) {
912 if (i == argc) my_fatal("book_dump(): missing argument\n");
913 if(my_string_equal(argv[i],"white")){
915 }else if (my_string_equal(argv[i],"black")){
918 my_fatal("book_dump(): unknown color \"%s\"\n",argv[i]);
921 my_fatal("book_dump(): unknown option \"%s\"\n",argv[i]);
924 if(color==ColourNone){
925 my_fatal("book_dump(): you must specify a color\n");
928 snprintf(string,StringSize,"book_%s.txt",(color==White)?"white":"black");
929 my_string_set(&txt_file,string);
933 if(!Quiet){printf("loading book ...\n");}
937 info->initial_color=color;
938 if(!(f=fopen(txt_file,"w"))){
939 my_fatal("book_dump(): can't open file \"%s\" for writing: %s",
940 txt_file,strerror(errno));
943 fprintf(info->output,"Dump of \"%s\" for %s.\n",
944 bin_file,color==White?"white":"black");
946 if(!Quiet){printf("generating lines for white...\n");}
947 search_book(board,info, BOOK);
949 if(!Quiet){printf("generating lines for black...\n");}
950 search_book(board,info, ALL);
956 void book_info(int argc,char* argv[]){
957 const char *bin_file=NULL;
962 int white_pos,black_pos,total_pos,white_pos_extended,
963 black_pos_extended,white_pos_extended_diff,black_pos_extended_diff;
965 bool extended_search=FALSE;
968 my_string_set(&bin_file,"book.bin");
970 for (i = 1; i < argc; i++) {
972 } else if (my_string_equal(argv[i],"info-book")) {
974 } else if (my_string_equal(argv[i],"-bin")) {
976 if (i==argc) my_fatal("book_info(): missing argument\n");
977 my_string_set(&bin_file,argv[i]);
978 } else if (my_string_equal(argv[i],"-exact")) {
979 extended_search=TRUE;
981 my_fatal("book_info(): unknown option \"%s\"\n",argv[i]);
985 if(!Quiet){printf("loading book ...\n");}
991 info->book_trans_only=FALSE;
992 info->initial_color=White;
993 info->extended_search=FALSE;
994 search_book(board,info, BOOK);
995 printf("Lines for white : %8d\n",info->line-1);
1000 info->initial_color=Black;
1002 ASSERT(Book->size==s);
1004 search_book(board,info, ALL);
1005 printf("Lines for black : %8d\n",info->line-1);
1008 ASSERT(Book->size==s);
1013 for(pos=0;pos<Book->size;pos++){
1014 if(Book->entry[pos].key==last_key){
1015 ASSERT(Book->entry[pos].colour==ColourNone);
1018 last_key=Book->entry[pos].key;
1020 if(Book->entry[pos].colour==White){
1022 }else if(Book->entry[pos].colour==Black){
1026 printf("Positions on lines for white : %8d\n",white_pos);
1027 printf("Positions on lines for black : %8d\n",black_pos);
1030 if(extended_search){
1032 info->book_trans_only=TRUE;
1033 info->initial_color=White;
1034 info->extended_search=TRUE;
1037 search_book(board,info, BOOK);
1040 info->book_trans_only=TRUE;
1041 info->initial_color=Black;
1042 info->extended_search=TRUE;
1045 search_book(board,info, ALL);
1047 ASSERT(Book->size==s);
1048 white_pos_extended=0;
1049 black_pos_extended=0;
1051 for(pos=0;pos<Book->size;pos++){
1052 if(Book->entry[pos].key==last_key){
1053 ASSERT(Book->entry[pos].colour==ColourNone);
1056 last_key=Book->entry[pos].key;
1057 if(Book->entry[pos].colour==White){
1058 white_pos_extended++;
1059 }else if(Book->entry[pos].colour==Black){
1060 black_pos_extended++;
1063 white_pos_extended_diff=white_pos_extended-white_pos;
1064 black_pos_extended_diff=black_pos_extended-black_pos;
1065 printf("Unreachable white positions(?) : %8d\n",
1066 white_pos_extended_diff);
1067 printf("Unreachable black positions(?) : %8d\n",
1068 black_pos_extended_diff);
1071 if(extended_search){
1072 printf("Isolated positions : %8d\n",
1073 total_pos-white_pos_extended-black_pos_extended);
1075 printf("Isolated positions : %8d\n",
1076 total_pos-white_pos-black_pos);
1082 // end of book_make.cpp