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