book_make.c

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