book_make.c

   1 // book_make.c
   2
   3 // includes
   4
   5 #include <errno.h>
   6 #include <math.h>
   7 #include <stdio.h>
   8 #include <stdlib.h>
   9 #include <string.h>
  10
  11 #include "board.h"
  12 #include "book_make.h"
  13 #include "move.h"
  14 #include "move_do.h"
  15 #include "move_gen.h"
  16 #include "move_legal.h"
  17 #include "pgn.h"
  18 #include "san.h"
  19 #include "util.h"
  20 #include "pgheader.h"
  21
  22 // constants
  23
  24 #define COUNT_MAX ((int)16384)
  25
  26 static const int NIL = -1;
  27
  28 // defines
  29
  30 #define opp_search(s) ((s)==BOOK?ALL:BOOK)
  31
  32 // types
  33
  34 typedef struct {
  35     uint64 key;
  36     uint16 move;
  37     uint16 count;
  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
  43 // even with -Wall.
  44 //    union {
  45 //        struct {
  46             uint16 n;
  47             uint16 sum;
  48 //        };
  49 //        struct {
  50             uint8 height;
  51             int line;
  52 //        };
  53 //   };
  54     uint8 colour;
  55 } entry_t;
  56
  57 typedef struct {
  58    int size;
  59    int alloc;
  60    uint32 mask;
  61    entry_t * entry;
  62    sint32 * hash;
  63 } book_t;
  64
  65 typedef enum {
  66     BOOK,
  67     ALL
  68 } search_t;
  69
  70 typedef struct {
  71     int height;
  72     int line;
  73     int initial_color;
  74     bool book_trans_only;
  75     bool extended_search;
  76     uint16 moves[1024];
  77     double probs[1024];
  78     uint64 keys[1024];
  79     FILE *output;
  80 } info_t;
  81
  82
  83 // variables
  84
  85 static int MaxPly;
  86 static int MinGame;
  87 static double MinScore;
  88 static bool RemoveWhite, RemoveBlack;
  89 static bool Uniform;
  90 static bool Quiet=FALSE;
  91
  92 static book_t Book[1];
  93
  94 // prototypes
  95
  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[]);
 101
 102 static int    find_entry    (const board_t * board, int move);
 103 static void   resize        ();
 104 static void   halve_stats   (uint64 key);
 105
 106 static bool   keep_entry    (int pos);
 107
 108 static int    entry_score    (const entry_t * entry);
 109
 110 static int    key_compare   (const void * p1, const void * p2);
 111
 112 static void   write_integer (FILE * file, int size, uint64 n);
 113 static uint64 read_integer(FILE * file, int size);
 114
 115 static void read_entry_file(FILE *f, entry_t *entry);
 116 static void write_entry_file(FILE * f, const entry_t * entry);
 117
 118 // functions
 119
 120 // book_make()
 121
 122 void book_make(int argc, char * argv[]) {
 123
 124    int i;
 125    const char * pgn_file;
 126    const char * bin_file;
 127
 128    pgn_file = NULL;
 129    my_string_set(&pgn_file,"book.pgn");
 130
 131    bin_file = NULL;
 132    my_string_set(&bin_file,"book.bin");
 133
 134    MaxPly = 1024;
 135    MinGame = 3;
 136    MinScore = 0.0;
 137    RemoveWhite = FALSE;
 138    RemoveBlack = FALSE;
 139    Uniform = FALSE;
 140
 141    for (i = 1; i < argc; i++) {
 142
 143       if (FALSE) {
 144
 145       } else if (my_string_equal(argv[i],"make-book")) {
 146
 147          // skip
 148
 149       } else if (my_string_equal(argv[i],"-pgn")) {
 150
 151          i++;
 152          if (argv[i] == NULL) my_fatal("book_make(): missing argument\n");
 153
 154          my_string_set(&pgn_file,argv[i]);
 155
 156       } else if (my_string_equal(argv[i],"-bin")) {
 157
 158          i++;
 159          if (argv[i] == NULL) my_fatal("book_make(): missing argument\n");
 160
 161          my_string_set(&bin_file,argv[i]);
 162
 163       } else if (my_string_equal(argv[i],"-max-ply")) {
 164
 165          i++;
 166          if (argv[i] == NULL) my_fatal("book_make(): missing argument\n");
 167
 168          MaxPly = atoi(argv[i]);
 169          ASSERT(MaxPly>=0);
 170
 171       } else if (my_string_equal(argv[i],"-min-game")) {
 172
 173          i++;
 174          if (argv[i] == NULL) my_fatal("book_make(): missing argument\n");
 175
 176          MinGame = atoi(argv[i]);
 177          ASSERT(MinGame>0);
 178
 179       } else if (my_string_equal(argv[i],"-min-score")) {
 180
 181          i++;
 182          if (argv[i] == NULL) my_fatal("book_make(): missing argument\n");
 183
 184          MinScore = atof(argv[i]) / 100.0;
 185          ASSERT(MinScore>=0.0&&MinScore<=1.0);
 186
 187       } else if (my_string_equal(argv[i],"-only-white")) {
 188
 189          RemoveWhite = FALSE;
 190          RemoveBlack = TRUE;
 191
 192       } else if (my_string_equal(argv[i],"-only-black")) {
 193
 194          RemoveWhite = TRUE;
 195          RemoveBlack = FALSE;
 196
 197       } else if (my_string_equal(argv[i],"-uniform")) {
 198
 199          Uniform = TRUE;
 200
 201       } else {
 202
 203          my_fatal("book_make(): unknown option \"%s\"\n",argv[i]);
 204       }
 205    }
 206
 207    book_clear();
 208
 209    printf("inserting games ...\n");
 210    book_insert(pgn_file);
 211
 212    printf("filtering entries ...\n");
 213    book_filter();
 214
 215    printf("sorting entries ...\n");
 216    book_sort();
 217
 218    printf("saving entries ...\n");
 219    book_save(bin_file);
 220
 221    printf("all done!\n");
 222 }
 223
 224 // book_clear()
 225
 226 static void book_clear() {
 227
 228    int index;
 229
 230    Book->alloc = 1;
 231    Book->mask = (Book->alloc * 2) - 1;
 232
 233    Book->entry = (entry_t *) my_malloc(Book->alloc*sizeof(entry_t));
 234    Book->size = 0;
 235
 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;
 239    }
 240 }
 241
 242 // book_insert()
 243
 244 static void book_insert(const char file_name[]) {
 245
 246    pgn_t pgn[1];
 247    board_t board[1];
 248    int ply;
 249    int result;
 250    char string[256];
 251    int move;
 252    int pos;
 253
 254    ASSERT(file_name!=NULL);
 255
 256    // init
 257
 258    pgn->game_nb=1;
 259    // scan loop
 260
 261    pgn_open(pgn,file_name);
 262
 263    while (pgn_next_game(pgn)) {
 264
 265       board_start(board);
 266       ply = 0;
 267       result = 0;
 268
 269       if (FALSE) {
 270       } else if (my_string_equal(pgn->result,"1-0")) {
 271          result = +1;
 272       } else if (my_string_equal(pgn->result,"0-1")) {
 273          result = -1;
 274       }
 275
 276       while (pgn_next_move(pgn,string,256)) {
 277
 278          if (ply < MaxPly) {
 279
 280             move = move_from_san(string,board);
 281
 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);
 284             }
 285
 286             pos = find_entry(board,move);
 287
 288             Book->entry[pos].n++;
 289             Book->entry[pos].sum += result+1;
 290
 291             if (Book->entry[pos].n >= COUNT_MAX) {
 292                halve_stats(board->key);
 293             }
 294
 295             move_do(board,move);
 296             ply++;
 297             result = -result;
 298          }
 299       }
 300           pgn->game_nb++;
 301       if (pgn->game_nb % 10000 == 0) printf("%d games ...\n",pgn->game_nb);
 302    }
 303
 304    pgn_close(pgn);
 305
 306    printf("%d game%s.\n",pgn->game_nb,(pgn->game_nb>2)?"s":"");
 307    printf("%d entries.\n",Book->size);
 308
 309    return;
 310 }
 311
 312 // book_filter()
 313
 314 static void book_filter() {
 315
 316    int src, dst;
 317
 318    // entry loop
 319
 320    dst = 0;
 321
 322    for (src = 0; src < Book->size; src++) {
 323       if (keep_entry(src)) Book->entry[dst++] = Book->entry[src];
 324    }
 325
 326    ASSERT(dst>=0&&dst<=Book->size);
 327    Book->size = dst;
 328
 329    printf("%d entries.\n",Book->size);
 330 }
 331
 332 // book_sort()
 333
 334 static void book_sort() {
 335
 336    // sort keys for binary search
 337
 338    qsort(Book->entry,Book->size,sizeof(entry_t),&key_compare);
 339 }
 340
 341 // book_save()
 342
 343 static void book_save(const char file_name[]) {
 344
 345    FILE * file;
 346    int pos;
 347    char *header, *raw_header;
 348    unsigned int size;
 349    int i;
 350
 351    ASSERT(file_name!=NULL);
 352
 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));
 355
 356    pgheader_create(&header,"normal","Created by Polyglot.");
 357    pgheader_create_raw(&raw_header,header,&size);
 358    free(header);
 359
 360    // write header
 361
 362    for(i=0;i<size;i++){
 363        fputc(raw_header[i],file);
 364    }
 365    free(raw_header);
 366
 367    // entry loop
 368
 369    for (pos = 0; pos < Book->size; pos++) {
 370
 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);
 379       }
 380    }
 381
 382    fclose(file);
 383 }
 384
 385 // find_entry()
 386
 387 static int find_entry(const board_t * board, int move) {
 388
 389    uint64 key;
 390    int index;
 391    int pos;
 392
 393    ASSERT(board!=NULL);
 394    ASSERT(move==MoveNone || move_is_ok(move));
 395
 396    ASSERT(move==MoveNone || move_is_legal(move,board));
 397
 398    // init
 399
 400    key = board->key;
 401
 402    // search
 403
 404    for (index = key & (uint64) Book->mask; (pos=Book->hash[index]) != NIL; index = (index+1) & Book->mask) {
 405
 406       ASSERT(pos>=0&&pos<Book->size);
 407
 408       if (Book->entry[pos].key == key && Book->entry[pos].move == move) {
 409          return pos; // found
 410       }
 411    }
 412
 413    // not found
 414
 415    ASSERT(Book->size<=Book->alloc);
 416
 417    if (Book->size == Book->alloc) {
 418
 419       // allocate more memory
 420
 421       resize();
 422
 423       for (index = key & (uint64) Book->mask; Book->hash[index] != NIL; index = (index+1) & Book->mask)
 424          ;
 425    }
 426
 427    // create a new entry
 428
 429    ASSERT(Book->size<Book->alloc);
 430    pos = Book->size++;
 431
 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;
 437
 438    // insert into the hash table
 439
 440    ASSERT(index>=0&&index<Book->alloc*2);
 441    ASSERT(Book->hash[index]==NIL);
 442    Book->hash[index] = pos;
 443
 444    ASSERT(pos>=0&&pos<Book->size);
 445
 446    return pos;
 447 }
 448
 449 // rebuild_hash_table
 450
 451 static void rebuild_hash_table(){
 452     int index,pos;
 453     for (index = 0; index < Book->alloc*2; index++) {
 454         Book->hash[index] = NIL;
 455     }
 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)
 458          ;
 459         ASSERT(index>=0&&index<Book->alloc*2);
 460         Book->hash[index] = pos;
 461     }
 462 }
 463
 464 static void resize() {
 465
 466    int size;
 467
 468    ASSERT(Book->size==Book->alloc);
 469
 470    Book->alloc *= 2;
 471    Book->mask = (Book->alloc * 2) - 1;
 472
 473    size = 0;
 474    size += Book->alloc * sizeof(entry_t);
 475    size += (Book->alloc*2) * sizeof(sint32);
 476
 477    if (size >= 1048576) if(!Quiet){
 478            printf("allocating %gMB ...\n",((double)size)/1048576.0);
 479        }
 480
 481    // resize arrays
 482
 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));
 485
 486    // rebuild hash table
 487
 488    rebuild_hash_table();
 489 }
 490
 491
 492 // halve_stats()
 493
 494 static void halve_stats(uint64 key) {
 495
 496    int index;
 497    int pos;
 498
 499    // search
 500
 501    for (index = key & (uint64) Book->mask; (pos=Book->hash[index]) != NIL; index = (index+1) & Book->mask) {
 502
 503       ASSERT(pos>=0&&pos<Book->size);
 504
 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;
 508       }
 509    }
 510 }
 511
 512 // keep_entry()
 513
 514 static bool keep_entry(int pos) {
 515
 516    const entry_t * entry;
 517    int colour;
 518    double score;
 519
 520    ASSERT(pos>=0&&pos<Book->size);
 521
 522    entry = &Book->entry[pos];
 523
 524    // if (entry->n == 0) return FALSE;
 525    if (entry->n < MinGame) return FALSE;
 526
 527    if (entry->sum == 0) return FALSE;
 528
 529    score = (((double)entry->sum) / ((double)entry->n)) / 2.0;
 530    ASSERT(score>=0.0&&score<=1.0);
 531
 532    if (score < MinScore) return FALSE;
 533
 534    colour = entry->colour;
 535
 536    if ((RemoveWhite && colour_is_white(colour))
 537     || (RemoveBlack && colour_is_black(colour))) {
 538       return FALSE;
 539    }
 540
 541    if (entry_score(entry) == 0) return FALSE; // REMOVE ME?
 542
 543    return TRUE;
 544 }
 545
 546 // entry_score()
 547
 548 static int entry_score(const entry_t * entry) {
 549
 550    int score;
 551
 552    ASSERT(entry!=NULL);
 553
 554    // score = entry->n; // popularity
 555    score = entry->sum; // "expectancy"
 556
 557    if (Uniform) score = 1;
 558
 559    ASSERT(score>=0);
 560
 561    return score;
 562 }
 563
 564 // key_compare()
 565
 566 static int key_compare(const void * p1, const void * p2) {
 567
 568    const entry_t * entry_1, * entry_2;
 569
 570    ASSERT(p1!=NULL);
 571    ASSERT(p2!=NULL);
 572
 573    entry_1 = (const entry_t *) p1;
 574    entry_2 = (const entry_t *) p2;
 575
 576    if (entry_1->key > entry_2->key) {
 577       return +1;
 578    } else if (entry_1->key < entry_2->key) {
 579       return -1;
 580    } else {
 581       return entry_score(entry_2) - entry_score(entry_1); // highest score first
 582    }
 583 }
 584
 585 // write_integer()
 586
 587 static void write_integer(FILE * file, int size, uint64 n) {
 588
 589    int i;
 590    int b;
 591
 592    ASSERT(file!=NULL);
 593    ASSERT(size>0&&size<=8);
 594    ASSERT(size==8||n>>(size*8)==0);
 595
 596    for (i = size-1; i >= 0; i--) {
 597       b = (n >> (i*8)) & 0xFF;
 598       ASSERT(b>=0&&b<256);
 599       fputc(b,file);
 600    }
 601 }
 602
 603 // read_integer()
 604
 605 static uint64 read_integer(FILE * file, int size) {
 606    uint64 n;
 607    int i;
 608    int b;
 609    ASSERT(file!=NULL);
 610    ASSERT(size>0&&size<=8);
 611    n = 0;
 612    for (i = 0; i < size; i++) {
 613       b = fgetc(file);
 614       if (b == EOF) {
 615          if (feof(file)) {
 616             my_fatal("read_integer(): fgetc(): EOF reached\n");
 617          } else { // error
 618             my_fatal("read_integer(): fgetc(): %s\n",strerror(errno));
 619          }
 620       }
 621       ASSERT(b>=0&&b<256);
 622       n = (n << 8) | b;
 623    }
 624    return n;
 625 }
 626
 627 // read_entry_file
 628
 629 static void read_entry_file(FILE *f, entry_t *entry){
 630     uint64 n;
 631     ASSERT(entry!=NULL);
 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
 638 }
 639
 640 // write_entry_file
 641
 642 static void write_entry_file(FILE * f, const entry_t * entry) {
 643    ASSERT(entry!=NULL);
 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);
 649 }
 650
 651 static void print_list(const board_t *board, list_t *list){
 652     int i;
 653     uint16 move;
 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);
 659     }
 660     printf("\n");
 661 }
 662
 663 // book_load()
 664 // loads a polyglot book
 665
 666 static void book_load(const char filename[]){
 667     FILE* f;
 668     entry_t entry[1];
 669     int size;
 670     int i;
 671     int pos;
 672     int index;
 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));
 676     }
 677     fseek(f,0L,SEEK_END);   // superportable way to get size of book!
 678     size=ftell(f)/16;
 679     fseek(f,0,SEEK_SET);
 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
 685             resize();
 686         }
 687             // insert into the book
 688         pos = Book->size++;
 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);
 705     }
 706     fclose(f);
 707 }
 708
 709 // gen_book_moves()
 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;
 713     entry_t entry[1];
 714     bool found;
 715     list_clear(list);
 716     found=FALSE;
 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) {
 720             found=TRUE;
 721             break; // found
 722         }
 723     }
 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);
 733         }
 734     }
 735     return first_pos;
 736 }
 737
 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){
 742     int move;
 743     list_t new_list[1], legal_moves[1];
 744     board_t new_board[1];
 745     int i;
 746     list_clear(list);
 747     gen_legal_moves(legal_moves,board);
 748     for (i = 0; i < list_size(legal_moves); i++) {
 749         move = list_move(legal_moves,i);
 750             // scratch_board
 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){
 755             list_add(list,move);
 756         }
 757     }
 758 }
 759
 760 static void print_moves(info_t *info){
 761     board_t board[1];
 762     char move_string[256];
 763     int i;
 764     int color=White;
 765     if(!info->output){
 766         return;
 767     }
 768     board_start(board);
 769     for(i=0;i<info->height;i++){
 770         if(color==White){
 771             fprintf(info->output,"%d. ",i/2+1);
 772             color=Black;
 773         }else{
 774             color=White;
 775         }
 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]);
 780         }else{
 781             fprintf(info->output," ");
 782         }
 783         move_do(board,info->moves[i]);
 784     }
 785 }
 786
 787 static int search_book(board_t *board, info_t *info, search_t search){
 788     list_t list[1];
 789     board_t new_board[1];
 790     uint16 move;
 791     int count;
 792     int ret;
 793     int i;
 794     int offset;
 795     int pos;
 796     int size;
 797     int prob_sum;
 798     double probs[256];
 799     for(i=0;i<256;i++){
 800         probs[i]=0.0;  // kill compiler warnings
 801     }
 802     for(i=0;i<info->height;i++){
 803         if(board->key==info->keys[i]){
 804             if(info->output){
 805                 fprintf(info->output,"%d: ",info->line);
 806                 print_moves(info);
 807                 fprintf(info->output,"{cycle: ply=%d}\n",i);
 808             }
 809             info->line++;
 810             return 1; // end of line because of cycle
 811         }
 812     }
 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){
 818             if(info->output){
 819                 fprintf(info->output,"%d: ",info->line);
 820                 print_moves(info);
 821                 fprintf(info->output,"{trans: line=%d, ply=%d}\n",
 822                         Book->entry[pos].line,
 823                         Book->entry[pos].height);
 824             }
 825             info->line++;
 826             return 1; // end of line because of transposition
 827         }else{
 828             Book->entry[pos].height=info->height;
 829             Book->entry[pos].line=info->line;
 830         }
 831     }
 832     count=0;
 833     if(search==BOOK){
 834         offset=gen_book_moves(list,board);
 835         if(info->extended_search){
 836             gen_legal_moves(list,board);
 837         }
 838 //        ASSERT(offset!=-1);
 839         if(offset!=-1){ // only FALSE in starting position for black book
 840             Book->entry[offset].colour=board->turn;
 841             prob_sum=0;
 842             if(!info->extended_search){
 843                 for(i=0;i<list_size(list);i++){
 844                     prob_sum+=((uint16)list_value(list,i));
 845                 }
 846                 for(i=0;i<list_size(list);i++){
 847                     probs[i]=((double)((uint16)list_value(list,i)))/((double)prob_sum);
 848                 }
 849             }
 850         }
 851     }else{
 852         gen_opp_book_moves(list,board);
 853     }
 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;
 861         if(search==BOOK){
 862             info->probs[info->height-1]=probs[i];
 863         }
 864         ret=search_book(new_board, info, opp_search(search));
 865         if(ret==0 && search==BOOK){
 866             if(info->output){
 867                 fprintf(info->output,"%d: ",info->line);
 868                 print_moves(info);
 869                 fprintf(info->output,"\n");
 870             }
 871             info->line++;
 872             ret=1; // end of line book move counts for 1
 873         }
 874         info->height--;
 875         ASSERT(info->height>=0);
 876         count+=ret;
 877     }
 878     return count;
 879 }
 880
 881 void init_info(info_t *info){
 882     info->line=1;
 883     info->height=0;
 884     info->output=NULL;
 885     info->initial_color=White;
 886     info->book_trans_only=FALSE;
 887 }
 888
 889 // book_clean()
 890 // remove MoveNone entries from book and rebuild hash table
 891 void book_clean(){
 892     int read_ptr,write_ptr;
 893     write_ptr=0;
 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];
 897         }
 898     }
 899     Book->size=write_ptr;
 900     rebuild_hash_table();
 901 }
 902
 903 // book_dump()
 904
 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;
 910     board_t board[1];
 911     info_t info[1];
 912     int i;
 913     FILE *f;
 914     my_string_set(&bin_file,"book.bin");
 915     for (i = 1; i < argc; i++) {
 916         if (FALSE) {
 917         } else if (my_string_equal(argv[i],"dump-book")) {
 918                 // skip
 919         } else if (my_string_equal(argv[i],"-bin")) {
 920             i++;
 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")) {
 924             i++;
 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")) {
 928             i++;
 929             if (i == argc) my_fatal("book_dump(): missing argument\n");
 930             if(my_string_equal(argv[i],"white")){
 931                 color=White;
 932             }else if (my_string_equal(argv[i],"black")){
 933                 color=Black;
 934             }else{
 935                 my_fatal("book_dump(): unknown color \"%s\"\n",argv[i]);
 936             }
 937         } else {
 938             my_fatal("book_dump(): unknown option \"%s\"\n",argv[i]);
 939         }
 940     }
 941     if(color==ColourNone){
 942         my_fatal("book_dump(): you must specify a color\n");
 943     }
 944     if(txt_file==NULL){
 945         snprintf(string,StringSize,"book_%s.txt",(color==White)?"white":"black");
 946         my_string_set(&txt_file,string);
 947     }
 948
 949     book_clear();
 950     if(!Quiet){printf("loading book ...\n");}
 951     book_load(bin_file);
 952     board_start(board);
 953     init_info(info);
 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));
 958     }
 959     info->output=f;
 960     fprintf(info->output,"Dump of \"%s\" for %s.\n",
 961             bin_file,color==White?"white":"black");
 962     if(color==White){
 963         if(!Quiet){printf("generating lines for white...\n");}
 964         search_book(board,info, BOOK);
 965     }else{
 966         if(!Quiet){printf("generating lines for black...\n");}
 967         search_book(board,info, ALL);
 968     }
 969 }
 970
 971 // book_info()
 972
 973 void book_info(int argc,char* argv[]){
 974     const char *bin_file=NULL;
 975     board_t board[1];
 976     info_t info[1];
 977     uint64 last_key;
 978     int pos;
 979     int white_pos,black_pos,total_pos,white_pos_extended,
 980         black_pos_extended,white_pos_extended_diff,black_pos_extended_diff;
 981     int s;
 982     bool extended_search=FALSE;
 983     int i;
 984     Quiet=TRUE;
 985     my_string_set(&bin_file,"book.bin");
 986
 987     for (i = 1; i < argc; i++) {
 988         if (FALSE) {
 989         } else if (my_string_equal(argv[i],"info-book")) {
 990                 // skip
 991         } else if (my_string_equal(argv[i],"-bin")) {
 992             i++;
 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;
 997         } else {
 998             my_fatal("book_info(): unknown option \"%s\"\n",argv[i]);
 999         }
1000     }
1001     book_clear();
1002     if(!Quiet){printf("loading book ...\n");}
1003     book_load(bin_file);
1004     s=Book->size;
1005
1006     board_start(board);
1007     init_info(info);
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);
1013
1014
1015     info->line=1;
1016     info->height=0;
1017     info->initial_color=Black;
1018     book_clean();
1019     ASSERT(Book->size==s);
1020     board_start(board);
1021     search_book(board,info, ALL);
1022     printf("Lines for black                : %8d\n",info->line-1);
1023
1024     book_clean();
1025     ASSERT(Book->size==s);
1026     white_pos=0;
1027     black_pos=0;
1028     total_pos=0;
1029     last_key=0;
1030     for(pos=0;pos<Book->size;pos++){
1031         if(Book->entry[pos].key==last_key){
1032             ASSERT(Book->entry[pos].colour==ColourNone);
1033             continue;
1034         }
1035         last_key=Book->entry[pos].key;
1036         total_pos++;
1037         if(Book->entry[pos].colour==White){
1038             white_pos++;
1039         }else if(Book->entry[pos].colour==Black){
1040             black_pos++;
1041         }
1042     }
1043     printf("Positions on lines for white   : %8d\n",white_pos);
1044     printf("Positions on lines for black   : %8d\n",black_pos);
1045
1046
1047     if(extended_search){
1048         init_info(info);
1049         info->book_trans_only=TRUE;
1050         info->initial_color=White;
1051         info->extended_search=TRUE;
1052         book_clean();
1053         board_start(board);
1054         search_book(board,info, BOOK);
1055
1056         init_info(info);
1057         info->book_trans_only=TRUE;
1058         info->initial_color=Black;
1059         info->extended_search=TRUE;
1060         book_clean();
1061         board_start(board);
1062         search_book(board,info, ALL);
1063         book_clean();
1064         ASSERT(Book->size==s);
1065         white_pos_extended=0;
1066         black_pos_extended=0;
1067         last_key=0;
1068         for(pos=0;pos<Book->size;pos++){
1069             if(Book->entry[pos].key==last_key){
1070                 ASSERT(Book->entry[pos].colour==ColourNone);
1071                 continue;
1072             }
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++;
1078             }
1079         }
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);
1086
1087     }
1088     if(extended_search){
1089         printf("Isolated positions             : %8d\n",
1090                total_pos-white_pos_extended-black_pos_extended);
1091     }else{
1092         printf("Isolated positions             : %8d\n",
1093                total_pos-white_pos-black_pos);
1094     }
1095 }
1096
1097
1098
1099 // end of book_make.cpp
1100