book_make.cpp

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