book_make.cpp

   1 \r
   2 // book_make.cpp\r
   3 \r
   4 // includes\r
   5 \r
   6 #include <cerrno>\r
   7 #include <cmath>\r
   8 #include <cstdio>\r
   9 #include <cstdlib>\r
  10 #include <cstring>\r
  11 \r
  12 #include "board.h"\r
  13 #include "book_make.h"\r
  14 #include "move.h"\r
  15 #include "move_do.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 \r
  25 static const int NIL = -1;\r
  26 \r
  27 // types\r
  28 \r
  29 struct entry_t {\r
  30    uint64 key;\r
  31    uint16 move;\r
  32    uint16 n;\r
  33    uint16 sum;\r
  34    uint16 colour;\r
  35 };\r
  36 \r
  37 struct book_t {\r
  38    int size;\r
  39    int alloc;\r
  40    uint32 mask;\r
  41    entry_t * entry;\r
  42    sint32 * hash;\r
  43 };\r
  44 \r
  45 // variables\r
  46 \r
  47 static int MaxPly;\r
  48 static int MinGame;\r
  49 static double MinScore;\r
  50 static bool RemoveWhite, RemoveBlack;\r
  51 static bool Uniform;\r
  52 \r
  53 static book_t Book[1];\r
  54 \r
  55 // prototypes\r
  56 \r
  57 static void   book_clear    ();\r
  58 static void   book_insert   (const char file_name[]);\r
  59 static void   book_filter   ();\r
  60 static void   book_sort     ();\r
  61 static void   book_save     (const char file_name[]);\r
  62 \r
  63 static int    find_entry    (const board_t * board, int move);\r
  64 static void   resize        ();\r
  65 static void   halve_stats   (uint64 key);\r
  66 \r
  67 static bool   keep_entry    (int pos);\r
  68 \r
  69 static int    entry_score    (const entry_t * entry);\r
  70 \r
  71 static int    key_compare   (const void * p1, const void * p2);\r
  72 \r
  73 static void   write_integer (FILE * file, int size, uint64 n);\r
  74 \r
  75 // functions\r
  76 \r
  77 // book_make()\r
  78 \r
  79 void book_make(int argc, char * argv[]) {\r
  80 \r
  81    int i;\r
  82    const char * pgn_file;\r
  83    const char * bin_file;\r
  84 \r
  85    pgn_file = NULL;\r
  86    my_string_set(&pgn_file,"book.pgn");\r
  87 \r
  88    bin_file = NULL;\r
  89    my_string_set(&bin_file,"book.bin");\r
  90 \r
  91    MaxPly = 1024;\r
  92    MinGame = 3;\r
  93    MinScore = 0.0;\r
  94    RemoveWhite = false;\r
  95    RemoveBlack = false;\r
  96    Uniform = false;\r
  97 \r
  98    for (i = 1; i < argc; i++) {\r
  99 \r
 100       if (false) {\r
 101 \r
 102       } else if (my_string_equal(argv[i],"make-book")) {\r
 103 \r
 104          // skip\r
 105 \r
 106       } else if (my_string_equal(argv[i],"-pgn")) {\r
 107 \r
 108          i++;\r
 109          if (argv[i] == NULL) my_fatal("book_make(): missing argument\n");\r
 110 \r
 111          my_string_set(&pgn_file,argv[i]);\r
 112 \r
 113       } else if (my_string_equal(argv[i],"-bin")) {\r
 114 \r
 115          i++;\r
 116          if (argv[i] == NULL) my_fatal("book_make(): missing argument\n");\r
 117 \r
 118          my_string_set(&bin_file,argv[i]);\r
 119 \r
 120       } else if (my_string_equal(argv[i],"-max-ply")) {\r
 121 \r
 122          i++;\r
 123          if (argv[i] == NULL) my_fatal("book_make(): missing argument\n");\r
 124 \r
 125          MaxPly = atoi(argv[i]);\r
 126          ASSERT(MaxPly>=0);\r
 127 \r
 128       } else if (my_string_equal(argv[i],"-min-game")) {\r
 129 \r
 130          i++;\r
 131          if (argv[i] == NULL) my_fatal("book_make(): missing argument\n");\r
 132 \r
 133          MinGame = atoi(argv[i]);\r
 134          ASSERT(MinGame>0);\r
 135 \r
 136       } else if (my_string_equal(argv[i],"-min-score")) {\r
 137 \r
 138          i++;\r
 139          if (argv[i] == NULL) my_fatal("book_make(): missing argument\n");\r
 140 \r
 141          MinScore = atof(argv[i]) / 100.0;\r
 142          ASSERT(MinScore>=0.0&&MinScore<=1.0);\r
 143 \r
 144       } else if (my_string_equal(argv[i],"-only-white")) {\r
 145 \r
 146          RemoveWhite = false;\r
 147          RemoveBlack = true;\r
 148 \r
 149       } else if (my_string_equal(argv[i],"-only-black")) {\r
 150 \r
 151          RemoveWhite = true;\r
 152          RemoveBlack = false;\r
 153 \r
 154       } else if (my_string_equal(argv[i],"-uniform")) {\r
 155 \r
 156          Uniform = true;\r
 157 \r
 158       } else {\r
 159 \r
 160          my_fatal("book_make(): unknown option \"%s\"\n",argv[i]);\r
 161       }\r
 162    }\r
 163 \r
 164    book_clear();\r
 165 \r
 166    printf("inserting games ...\n");\r
 167    book_insert(pgn_file);\r
 168 \r
 169    printf("filtering entries ...\n");\r
 170    book_filter();\r
 171 \r
 172    printf("sorting entries ...\n");\r
 173    book_sort();\r
 174 \r
 175    printf("saving entries ...\n");\r
 176    book_save(bin_file);\r
 177 \r
 178    printf("all done!\n");\r
 179 }\r
 180 \r
 181 // book_clear()\r
 182 \r
 183 static void book_clear() {\r
 184 \r
 185    int index;\r
 186 \r
 187    Book->alloc = 1;\r
 188    Book->mask = (Book->alloc * 2) - 1;\r
 189 \r
 190    Book->entry = (entry_t *) my_malloc(Book->alloc*sizeof(entry_t));\r
 191    Book->size = 0;\r
 192 \r
 193    Book->hash = (sint32 *) my_malloc((Book->alloc*2)*sizeof(sint32));\r
 194    for (index = 0; index < Book->alloc*2; index++) {\r
 195       Book->hash[index] = NIL;\r
 196    }\r
 197 }\r
 198 \r
 199 // book_insert()\r
 200 \r
 201 static void book_insert(const char file_name[]) {\r
 202 \r
 203    pgn_t pgn[1];\r
 204    board_t board[1];\r
 205    int ply;\r
 206    int result;\r
 207    char string[256];\r
 208    int move;\r
 209    int pos;\r
 210 \r
 211    ASSERT(file_name!=NULL);\r
 212 \r
 213    // init\r
 214 \r
 215    pgn->game_nb=1;\r
 216    // scan loop\r
 217 \r
 218    pgn_open(pgn,file_name);\r
 219 \r
 220    while (pgn_next_game(pgn)) {\r
 221 \r
 222       board_start(board);\r
 223       ply = 0;\r
 224       result = 0;\r
 225 \r
 226       if (false) {\r
 227       } else if (my_string_equal(pgn->result,"1-0")) {\r
 228          result = +1;\r
 229       } else if (my_string_equal(pgn->result,"0-1")) {\r
 230          result = -1;\r
 231       }\r
 232 \r
 233       while (pgn_next_move(pgn,string,256)) {\r
 234 \r
 235          if (ply < MaxPly) {\r
 236 \r
 237             move = move_from_san(string,board);\r
 238 \r
 239             if (move == MoveNone || !move_is_legal(move,board)) {\r
 240                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
 241             }\r
 242 \r
 243             pos = find_entry(board,move);\r
 244 \r
 245             Book->entry[pos].n++;\r
 246             Book->entry[pos].sum += result+1;\r
 247 \r
 248             if (Book->entry[pos].n >= COUNT_MAX) {\r
 249                halve_stats(board->key);\r
 250             }\r
 251 \r
 252             move_do(board,move);\r
 253             ply++;\r
 254             result = -result;\r
 255          }\r
 256       }\r
 257           pgn->game_nb++;\r
 258       if (pgn->game_nb % 10000 == 0) printf("%d games ...\n",pgn->game_nb);\r
 259    }\r
 260 \r
 261    pgn_close(pgn);\r
 262 \r
 263    printf("%d game%s.\n",pgn->game_nb,(pgn->game_nb>2)?"s":"");\r
 264    printf("%d entries.\n",Book->size);\r
 265 \r
 266    return;\r
 267 }\r
 268 \r
 269 // book_filter()\r
 270 \r
 271 static void book_filter() {\r
 272 \r
 273    int src, dst;\r
 274 \r
 275    // entry loop\r
 276 \r
 277    dst = 0;\r
 278 \r
 279    for (src = 0; src < Book->size; src++) {\r
 280       if (keep_entry(src)) Book->entry[dst++] = Book->entry[src];\r
 281    }\r
 282 \r
 283    ASSERT(dst>=0&&dst<=Book->size);\r
 284    Book->size = dst;\r
 285 \r
 286    printf("%d entries.\n",Book->size);\r
 287 }\r
 288 \r
 289 // book_sort()\r
 290 \r
 291 static void book_sort() {\r
 292 \r
 293    // sort keys for binary search\r
 294 \r
 295    qsort(Book->entry,Book->size,sizeof(entry_t),&key_compare);\r
 296 }\r
 297 \r
 298 // book_save()\r
 299 \r
 300 static void book_save(const char file_name[]) {\r
 301 \r
 302    FILE * file;\r
 303    int pos;\r
 304 \r
 305    ASSERT(file_name!=NULL);\r
 306 \r
 307    file = fopen(file_name,"wb");\r
 308    if (file == NULL) my_fatal("book_save(): can't open file \"%s\" for writing: %s\n",file_name,strerror(errno));\r
 309 \r
 310    // entry loop\r
 311 \r
 312    for (pos = 0; pos < Book->size; pos++) {\r
 313 \r
 314       ASSERT(keep_entry(pos));\r
 315 \r
 316       write_integer(file,8,Book->entry[pos].key);\r
 317       write_integer(file,2,Book->entry[pos].move);\r
 318       write_integer(file,2,entry_score(&Book->entry[pos]));\r
 319       write_integer(file,2,0);\r
 320       write_integer(file,2,0);\r
 321    }\r
 322 \r
 323    fclose(file);\r
 324 }\r
 325 \r
 326 // find_entry()\r
 327 \r
 328 static int find_entry(const board_t * board, int move) {\r
 329 \r
 330    uint64 key;\r
 331    int index;\r
 332    int pos;\r
 333 \r
 334    ASSERT(board!=NULL);\r
 335    ASSERT(move_is_ok(move));\r
 336 \r
 337    ASSERT(move_is_legal(move,board));\r
 338 \r
 339    // init\r
 340 \r
 341    key = board->key;\r
 342 \r
 343    // search\r
 344 \r
 345    for (index = key & Book->mask; (pos=Book->hash[index]) != NIL; index = (index+1) & Book->mask) {\r
 346 \r
 347       ASSERT(pos>=0&&pos<Book->size);\r
 348 \r
 349       if (Book->entry[pos].key == key && Book->entry[pos].move == move) {\r
 350          return pos; // found\r
 351       }\r
 352    }\r
 353 \r
 354    // not found\r
 355 \r
 356    ASSERT(Book->size<=Book->alloc);\r
 357 \r
 358    if (Book->size == Book->alloc) {\r
 359 \r
 360       // allocate more memory\r
 361 \r
 362       resize();\r
 363 \r
 364       for (index = key & Book->mask; Book->hash[index] != NIL; index = (index+1) & Book->mask)\r
 365          ;\r
 366    }\r
 367 \r
 368    // create a new entry\r
 369 \r
 370    ASSERT(Book->size<Book->alloc);\r
 371    pos = Book->size++;\r
 372 \r
 373    Book->entry[pos].key = key;\r
 374    Book->entry[pos].move = move;\r
 375    Book->entry[pos].n = 0;\r
 376    Book->entry[pos].sum = 0;\r
 377    Book->entry[pos].colour = board->turn;\r
 378 \r
 379    // insert into the hash table\r
 380 \r
 381    ASSERT(index>=0&&index<Book->alloc*2);\r
 382    ASSERT(Book->hash[index]==NIL);\r
 383    Book->hash[index] = pos;\r
 384 \r
 385    ASSERT(pos>=0&&pos<Book->size);\r
 386 \r
 387    return pos;\r
 388 }\r
 389 \r
 390 // resize()\r
 391 \r
 392 static void resize() {\r
 393 \r
 394    int size;\r
 395    int pos;\r
 396    int index;\r
 397 \r
 398    ASSERT(Book->size==Book->alloc);\r
 399 \r
 400    Book->alloc *= 2;\r
 401    Book->mask = (Book->alloc * 2) - 1;\r
 402 \r
 403    size = 0;\r
 404    size += Book->alloc * sizeof(entry_t);\r
 405    size += (Book->alloc*2) * sizeof(sint32);\r
 406    if (size >= 1048576) printf("allocating %gMB ...\n",double(size)/1048576.0);\r
 407    // resize arrays\r
 408 \r
 409    Book->entry = (entry_t *) my_realloc(Book->entry,Book->alloc*sizeof(entry_t));\r
 410    Book->hash = (sint32 *) my_realloc(Book->hash,(Book->alloc*2)*sizeof(sint32));\r
 411 \r
 412    // rebuild hash table\r
 413 \r
 414    for (index = 0; index < Book->alloc*2; index++) {\r
 415       Book->hash[index] = NIL;\r
 416    }\r
 417 \r
 418    for (pos = 0; pos < Book->size; pos++) {\r
 419 \r
 420       for (index = Book->entry[pos].key & Book->mask; Book->hash[index] != NIL; index = (index+1) & Book->mask)\r
 421          ;\r
 422 \r
 423       ASSERT(index>=0&&index<Book->alloc*2);\r
 424       Book->hash[index] = pos;\r
 425    }\r
 426 }\r
 427 \r
 428 // halve_stats()\r
 429 \r
 430 static void halve_stats(uint64 key) {\r
 431 \r
 432    int index;\r
 433    int pos;\r
 434 \r
 435    // search\r
 436 \r
 437    for (index = key & Book->mask; (pos=Book->hash[index]) != NIL; index = (index+1) & Book->mask) {\r
 438 \r
 439       ASSERT(pos>=0&&pos<Book->size);\r
 440 \r
 441       if (Book->entry[pos].key == key) {\r
 442          Book->entry[pos].n = (Book->entry[pos].n + 1) / 2;\r
 443          Book->entry[pos].sum = (Book->entry[pos].sum + 1) / 2;\r
 444       }\r
 445    }\r
 446 }\r
 447 \r
 448 // keep_entry()\r
 449 \r
 450 static bool keep_entry(int pos) {\r
 451 \r
 452    const entry_t * entry;\r
 453    int colour;\r
 454    double score;\r
 455 \r
 456    ASSERT(pos>=0&&pos<Book->size);\r
 457 \r
 458    entry = &Book->entry[pos];\r
 459 \r
 460    // if (entry->n == 0) return false;\r
 461    if (entry->n < MinGame) return false;\r
 462 \r
 463    if (entry->sum == 0) return false;\r
 464 \r
 465    score = (double(entry->sum) / double(entry->n)) / 2.0;\r
 466    ASSERT(score>=0.0&&score<=1.0);\r
 467 \r
 468    if (score < MinScore) return false;\r
 469 \r
 470    colour = entry->colour;\r
 471 \r
 472    if ((RemoveWhite && colour_is_white(colour))\r
 473     || (RemoveBlack && colour_is_black(colour))) {\r
 474       return false;\r
 475    }\r
 476 \r
 477    if (entry_score(entry) == 0) return false; // REMOVE ME?\r
 478 \r
 479    return true;\r
 480 }\r
 481 \r
 482 // entry_score()\r
 483 \r
 484 static int entry_score(const entry_t * entry) {\r
 485 \r
 486    int score;\r
 487 \r
 488    ASSERT(entry!=NULL);\r
 489 \r
 490    // score = entry->n; // popularity\r
 491    score = entry->sum; // "expectancy"\r
 492 \r
 493    if (Uniform) score = 1;\r
 494 \r
 495    ASSERT(score>=0);\r
 496 \r
 497    return score;\r
 498 }\r
 499 \r
 500 // key_compare()\r
 501 \r
 502 static int key_compare(const void * p1, const void * p2) {\r
 503 \r
 504    const entry_t * entry_1, * entry_2;\r
 505 \r
 506    ASSERT(p1!=NULL);\r
 507    ASSERT(p2!=NULL);\r
 508 \r
 509    entry_1 = (const entry_t *) p1;\r
 510    entry_2 = (const entry_t *) p2;\r
 511 \r
 512    if (entry_1->key > entry_2->key) {\r
 513       return +1;\r
 514    } else if (entry_1->key < entry_2->key) {\r
 515       return -1;\r
 516    } else {\r
 517       return entry_score(entry_2) - entry_score(entry_1); // highest score first\r
 518    }\r
 519 }\r
 520 \r
 521 // write_integer()\r
 522 \r
 523 static void write_integer(FILE * file, int size, uint64 n) {\r
 524 \r
 525    int i;\r
 526    int b;\r
 527 \r
 528    ASSERT(file!=NULL);\r
 529    ASSERT(size>0&&size<=8);\r
 530    ASSERT(size==8||n>>(size*8)==0);\r
 531 \r
 532    for (i = size-1; i >= 0; i--) {\r
 533       b = (n >> (i*8)) & 0xFF;\r
 534       ASSERT(b>=0&&b<256);\r
 535       fputc(b,file);\r
 536    }\r
 537 }\r
 538 \r
 539 // end of book_make.cpp\r
 540 \r