X-Git-Url: http://winboard.nl/cgi-bin?p=polyglot.git;a=blobdiff_plain;f=book_make.cpp;h=ba02f512baa9357408530a0c55b0f3e6fb319e4d;hp=ffffc9b6b733a5268efd531fcc4b6d033891df91;hb=ad2265d4fc54fc9ba99fc606e6174df34bfb4a0f;hpb=6442b61046f46f65bfc4bf0b3727abe2dc27acb8

diff --git a/book_make.cpp b/book_make.cpp
index ffffc9b..ba02f51 100644
--- a/book_make.cpp
+++ b/book_make.cpp
@@ -1,4 +1,3 @@
-
 // book_make.cpp
 
 // includes
@@ -13,6 +12,7 @@
 #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"
@@ -21,17 +21,31 @@
 // constants
 
 static const int COUNT_MAX = 16384;
+static const int StringSize = 4096;
 
 static const int NIL = -1;
 
+// defines
+
+#define opp_search(s) ((s)==BOOK?ALL:BOOK)
+
 // types
 
 struct entry_t {
-   uint64 key;
-   uint16 move;
-   uint16 n;
-   uint16 sum;
-   uint16 colour;
+    uint64 key;
+    uint16 move;
+    uint16 count;
+    union{   // unfortunately minggw32 seems to have a bug with anon unions.
+        struct { 
+            uint16 n;
+            uint16 sum;
+        };
+        struct{
+            uint8 height;
+            int line;
+        };
+    };
+    uint8 colour;
 };
 
 struct book_t {
@@ -42,6 +56,24 @@ struct book_t {
    sint32 * hash;
 };
 
+enum search_t {
+    BOOK,
+    ALL
+};
+
+struct info_t {
+    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;
+};
+
+
 // variables
 
 static int MaxPly;
@@ -49,6 +81,7 @@ static int MinGame;
 static double MinScore;
 static bool RemoveWhite, RemoveBlack;
 static bool Uniform;
+static bool Quiet=false;
 
 static book_t Book[1];
 
@@ -71,6 +104,10 @@ 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
 
@@ -332,9 +369,9 @@ static int find_entry(const board_t * board, int move) {
    int pos;
 
    ASSERT(board!=NULL);
-   ASSERT(move_is_ok(move));
+   ASSERT(move==MoveNone || move_is_ok(move));
 
-   ASSERT(move_is_legal(move,board));
+   ASSERT(move==MoveNone || move_is_legal(move,board));
 
    // init
 
@@ -342,7 +379,7 @@ static int find_entry(const board_t * board, int move) {
 
    // search
 
-   for (index = key & Book->mask; (pos=Book->hash[index]) != NIL; index = (index+1) & Book->mask) {
+   for (index = key & (uint64) Book->mask; (pos=Book->hash[index]) != NIL; index = (index+1) & Book->mask) {
 
       ASSERT(pos>=0&&pos<Book->size);
 
@@ -361,7 +398,7 @@ static int find_entry(const board_t * board, int move) {
 
       resize();
 
-      for (index = key & Book->mask; Book->hash[index] != NIL; index = (index+1) & Book->mask)
+      for (index = key & (uint64) Book->mask; Book->hash[index] != NIL; index = (index+1) & Book->mask)
          ;
    }
 
@@ -387,13 +424,24 @@ static int find_entry(const board_t * board, int move) {
    return pos;
 }
 
-// resize()
+// 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;
-   int pos;
-   int index;
 
    ASSERT(Book->size==Book->alloc);
 
@@ -403,7 +451,9 @@ static void resize() {
    size = 0;
    size += Book->alloc * sizeof(entry_t);
    size += (Book->alloc*2) * sizeof(sint32);
-   if (size >= 1048576) printf("allocating %gMB ...\n",double(size)/1048576.0);
+
+   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));
@@ -411,20 +461,10 @@ static void resize() {
 
    // rebuild hash table
 
-   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 & Book->mask; Book->hash[index] != NIL; index = (index+1) & Book->mask)
-         ;
-
-      ASSERT(index>=0&&index<Book->alloc*2);
-      Book->hash[index] = pos;
-   }
+   rebuild_hash_table();
 }
 
+
 // halve_stats()
 
 static void halve_stats(uint64 key) {
@@ -434,7 +474,7 @@ static void halve_stats(uint64 key) {
 
    // search
 
-   for (index = key & Book->mask; (pos=Book->hash[index]) != NIL; index = (index+1) & Book->mask) {
+   for (index = key & (uint64) Book->mask; (pos=Book->hash[index]) != NIL; index = (index+1) & Book->mask) {
 
       ASSERT(pos>=0&&pos<Book->size);
 
@@ -536,5 +576,501 @@ static void write_integer(FILE * file, int size, uint64 n) {
    }
 }
 
+// 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];
+    list_clear(list);
+    bool found;
+    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(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":"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