book.c

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 #include <math.h>
   4 #include <string.h>
   5 #include <limits.h>
   6 #include <float.h>
   7 #include "shogi.h"
   8
   9 /*
  10   Opening Book Data Structure: Index BookData
  11
  12     Index:         IndexEntry.. (NUM_SECTION times)
  13
  14       IndexEntry:  SectionPointer SectionSize
  15
  16     BookData:      Section.. (NUM_SECTION times)
  17
  18       Section:     [DataEntry]..
  19
  20         DataEntry: Header Move...
  21
  22
  23 - SectionPointer
  24   4 byte:  position of the section in character
  25
  26 - SectionSize
  27   2 byte:  size of the section in character
  28
  29 - Header
  30   1 byte:  number of bytes for the DataEntry
  31   8 byte:  hash key
  32
  33 - Move
  34   2 byte:  a book move
  35   2 byte:  frequency
  36  */
  37
  38 #define BK_SIZE_INDEX     6
  39 #define BK_SIZE_HEADER    9
  40 #define BK_SIZE_MOVE      4
  41 #define BK_MAX_MOVE       32
  42
  43 #if ( BK_SIZE_HEADER + BK_SIZE_MOVE * BK_MAX_MOVE > UCHAR_MAX )
  44 #  error "Maximum size of DataEntry is larger than UCHAR_MAX"
  45 #endif
  46
  47 typedef struct { unsigned short smove, freq; } book_move_t;
  48
  49 typedef struct { int from, to; } ft_t;
  50
  51 static int book_read( uint64_t key, book_move_t *pbook_move,
  52                       unsigned int *pposition );
  53 static uint64_t book_hash_func( const tree_t * restrict ptree,int *pis_flip );
  54 static unsigned int bm2move( const tree_t * restrict ptree, unsigned int bmove,
  55                              int is_flip );
  56 static ft_t flip_ft( ft_t ft, int turn, int is_flip );
  57 static int normalize_book_move( book_move_t * restrict pbook_move, int moves );
  58
  59
  60 int
  61 book_on( void )
  62 {
  63   int iret = file_close( pf_book );
  64   if ( iret < 0 ) { return iret; }
  65
  66   pf_book = file_open( str_book, "rb+" );
  67   if ( pf_book == NULL ) { return -2; }
  68
  69   return 1;
  70 }
  71
  72
  73 int
  74 book_off( void )
  75 {
  76   int iret = file_close( pf_book );
  77   if ( iret < 0 ) { return iret; }
  78
  79   pf_book = NULL;
  80
  81   return 1;
  82 }
  83
  84
  85 int
  86 book_probe( tree_t * restrict ptree )
  87 {
  88   book_move_t abook_move[ BK_MAX_MOVE+1 ];
  89   uint64_t key;
  90   double dscore, drand;
  91   unsigned int move, position, freq_lower_limit;
  92   int is_flip, i, j, moves, ply;
  93
  94   key   = book_hash_func( ptree, &is_flip );
  95
  96   moves = book_read( key, abook_move, &position );
  97   if ( moves <= 0 ) { return moves; }
  98
  99 #if ! defined(MINIMUM) || ! defined(NDEBUG)
 100   for ( j = i = 0; i < moves; i++ ) { j += abook_move[i].freq; }
 101   if ( j != USHRT_MAX )
 102     {
 103       str_error = "normalization error (book.bin)";
 104       return -1;
 105     }
 106 #endif
 107
 108   /* decision of book move based on pseudo-random number */
 109   if ( game_status & flag_puzzling ) { j = 0; }
 110   else {
 111     drand = (double)rand64() / (double)UINT64_MAX;
 112
 113     if ( game_status & flag_narrow_book )
 114       {
 115 #if defined(BK_ULTRA_NARROW)
 116         freq_lower_limit = abook_move[0].freq;
 117 #else
 118         freq_lower_limit = abook_move[0].freq / 2U;
 119 #endif
 120
 121         for ( i = 1; i < moves; i++ )
 122           {
 123             if ( abook_move[i].freq < freq_lower_limit ) { break; }
 124           }
 125         moves = i;
 126         normalize_book_move( abook_move, moves );
 127       }
 128
 129     for ( j = moves-1; j > 0; j-- )
 130       {
 131         dscore = (double)( abook_move[j].freq ) / (double)USHRT_MAX;
 132         if ( drand <= dscore ) { break; }
 133         drand -= dscore;
 134       }
 135     if ( ! abook_move[j].freq ) { j = 0; }
 136   }
 137
 138   /* show results */
 139   if ( ! ( game_status & ( flag_pondering | flag_puzzling ) ) )
 140     {
 141       Out( "    move     freq\n" );
 142       OutCsaShogi( "info" );
 143       for ( i = 0; i < moves; i++ )
 144         {
 145           const char *str;
 146
 147           dscore = (double)abook_move[i].freq / (double)USHRT_MAX;
 148           move = bm2move( ptree, (unsigned int)abook_move[i].smove, is_flip );
 149           str  = str_CSA_move( move );
 150
 151           Out( "  %c %s  %5.1f\n", i == j ? '*' : ' ', str, dscore * 100.0 );
 152           OutCsaShogi( " %s(%.0f%%)", str, dscore * 100.0 );
 153         }
 154       OutCsaShogi( "\n" );
 155     }
 156
 157   move = bm2move( ptree, (unsigned int)abook_move[j].smove, is_flip );
 158   if ( ! is_move_valid( ptree, move, root_turn ) )
 159     {
 160       out_warning( "BAD BOOK MOVE!! " );
 161       return 0;
 162     }
 163
 164   ply = record_game.moves;
 165   if ( game_status & flag_pondering ) { ply++; }
 166   if ( ply < HASH_REG_HIST_LEN )
 167     {
 168       history_book_learn[ ply ].key_book    = key;
 169       history_book_learn[ ply ].move_probed = move;
 170       history_book_learn[ ply ].key_probed  = (unsigned int)HASH_KEY;
 171       history_book_learn[ ply ].hand_probed = HAND_B;
 172       history_book_learn[ ply ].data        = (unsigned int)is_flip << 30;
 173       if ( game_status & flag_narrow_book )
 174         {
 175           history_book_learn[ ply ].data |= 1U << 29;
 176         }
 177     }
 178
 179   ptree->current_move[1] = move;
 180
 181   return 1;
 182 }
 183
 184
 185 static int
 186 book_read( uint64_t key, book_move_t *pbook_move, unsigned int *pposition )
 187 {
 188   uint64_t book_key;
 189   const unsigned char *p;
 190   unsigned int position, size_section, size, u;
 191   int ibook_section, moves;
 192   unsigned short s;
 193
 194   ibook_section = (int)( (unsigned int)key & (unsigned int)( NUM_SECTION-1 ) );
 195
 196   if ( fseek( pf_book, BK_SIZE_INDEX*ibook_section, SEEK_SET ) == EOF )
 197     {
 198       str_error = str_io_error;
 199       return -2;
 200     }
 201
 202   if ( fread( &position, sizeof(int), 1, pf_book ) != 1 )
 203     {
 204       str_error = str_io_error;
 205       return -2;
 206     }
 207
 208   if ( fread( &s, sizeof(unsigned short), 1, pf_book ) != 1 )
 209     {
 210       str_error = str_io_error;
 211       return -2;
 212     }
 213   size_section = (unsigned int)s;
 214   if ( size_section > MAX_SIZE_SECTION )
 215     {
 216       str_error = str_book_error;
 217       return -2;
 218     }
 219
 220   if ( fseek( pf_book, (long)position, SEEK_SET ) == EOF )
 221     {
 222       str_error = str_io_error;
 223       return -2;
 224     }
 225   if ( fread( book_section, sizeof(unsigned char), (size_t)size_section,
 226               pf_book ) != (size_t)size_section )
 227     {
 228       str_error = str_io_error;
 229       return -2;
 230     }
 231
 232   size       = 0;
 233   p          = book_section;
 234   *pposition = position;
 235   while ( book_section + size_section > p )
 236     {
 237       size     = (unsigned int)p[0];
 238       book_key = *(uint64_t *)( p + 1 );
 239       if ( book_key == key ) { break; }
 240       p          += size;
 241       *pposition += size;
 242     }
 243   if ( book_section + size_section <= p ) { return 0; }
 244
 245   for ( moves = 0, u = BK_SIZE_HEADER; u < size; moves++, u += BK_SIZE_MOVE )
 246     {
 247       pbook_move[moves].smove  = *(unsigned short *)(p+u+0);
 248       pbook_move[moves].freq   = *(unsigned short *)(p+u+2);
 249     }
 250
 251   return moves;
 252 }
 253
 254
 255 static ft_t
 256 flip_ft( ft_t ft, int turn, int is_flip )
 257 {
 258   int ito_rank, ito_file, ifrom_rank, ifrom_file;
 259
 260   ito_rank = airank[ft.to];
 261   ito_file = aifile[ft.to];
 262   if ( ft.from < nsquare )
 263     {
 264       ifrom_rank = airank[ft.from];
 265       ifrom_file = aifile[ft.from];
 266     }
 267   else { ifrom_rank = ifrom_file = 0; }
 268
 269   if ( turn )
 270     {
 271       ito_rank = rank9 - ito_rank;
 272       ito_file = file9 - ito_file;
 273       if ( ft.from < nsquare )
 274         {
 275           ifrom_rank = rank9 - ifrom_rank;
 276           ifrom_file = file9 - ifrom_file;
 277         }
 278     }
 279
 280   if ( is_flip )
 281     {
 282       ito_file = file9 - ito_file;
 283       if ( ft.from < nsquare ) { ifrom_file = file9 - ifrom_file; }
 284     }
 285
 286   ft.to = ito_rank * nfile + ito_file;
 287   if ( ft.from < nsquare ) { ft.from = ifrom_rank * nfile + ifrom_file; }
 288
 289   return ft;
 290 }
 291
 292
 293 static unsigned int
 294 bm2move( const tree_t * restrict ptree, unsigned int bmove, int is_flip )
 295 {
 296   ft_t ft;
 297   unsigned int move;
 298   int is_promote;
 299
 300   ft.to      = I2To(bmove);
 301   ft.from    = I2From(bmove);
 302   ft         = flip_ft( ft, root_turn, is_flip );
 303   is_promote = I2IsPromote(bmove);
 304
 305   move  = (unsigned int)( is_promote | From2Move(ft.from) | ft.to );
 306   if ( ft.from >= nsquare ) { return move; }
 307
 308   if ( root_turn )
 309     {
 310       move |= Cap2Move(BOARD[ft.to]);
 311       move |= Piece2Move(-BOARD[ft.from]);
 312     }
 313   else {
 314     move |= Cap2Move(-BOARD[ft.to]);
 315     move |= Piece2Move(BOARD[ft.from]);
 316   }
 317
 318   return move;
 319 }
 320
 321
 322 static uint64_t
 323 book_hash_func( const tree_t * restrict ptree, int *pis_flip )
 324 {
 325   uint64_t key, key_flip;
 326   unsigned int hand;
 327   int i, iflip, irank, ifile, piece;
 328
 329   key = 0;
 330   hand = root_turn ? HAND_W : HAND_B;
 331   i = I2HandPawn(hand);    if ( i ) { key ^= b_hand_pawn_rand[i-1]; }
 332   i = I2HandLance(hand);   if ( i ) { key ^= b_hand_lance_rand[i-1]; }
 333   i = I2HandKnight(hand);  if ( i ) { key ^= b_hand_knight_rand[i-1]; }
 334   i = I2HandSilver(hand);  if ( i ) { key ^= b_hand_silver_rand[i-1]; }
 335   i = I2HandGold(hand);    if ( i ) { key ^= b_hand_gold_rand[i-1]; }
 336   i = I2HandBishop(hand);  if ( i ) { key ^= b_hand_bishop_rand[i-1]; }
 337   i = I2HandRook(hand);    if ( i ) { key ^= b_hand_rook_rand[i-1]; }
 338
 339   hand = root_turn ? HAND_B : HAND_W;
 340   i = I2HandPawn(hand);    if ( i ) { key ^= w_hand_pawn_rand[i-1]; }
 341   i = I2HandLance(hand);   if ( i ) { key ^= w_hand_lance_rand[i-1]; }
 342   i = I2HandKnight(hand);  if ( i ) { key ^= w_hand_knight_rand[i-1]; }
 343   i = I2HandSilver(hand);  if ( i ) { key ^= w_hand_silver_rand[i-1]; }
 344   i = I2HandGold(hand);    if ( i ) { key ^= w_hand_gold_rand[i-1]; }
 345   i = I2HandBishop(hand);  if ( i ) { key ^= w_hand_bishop_rand[i-1]; }
 346   i = I2HandRook(hand);    if ( i ) { key ^= w_hand_rook_rand[i-1]; }
 347
 348   key_flip = key;
 349
 350   for ( irank = rank1; irank <= rank9; irank++ )
 351     for ( ifile = file1; ifile <= file9; ifile++ )
 352       {
 353         if ( root_turn )
 354           {
 355             i     = ( rank9 - irank ) * nfile + file9 - ifile;
 356             iflip = ( rank9 - irank ) * nfile + ifile;
 357             piece = -(int)BOARD[nsquare-i-1];
 358           }
 359         else {
 360           i     = irank * nfile + ifile;
 361           iflip = irank * nfile + file9 - ifile;
 362           piece = (int)BOARD[i];
 363         }
 364
 365 #define Foo(t_pc)  key      ^= (t_pc ## _rand)[i];     \
 366                    key_flip ^= (t_pc ## _rand)[iflip];
 367         switch ( piece )
 368           {
 369           case  pawn:        Foo( b_pawn );        break;
 370           case  lance:       Foo( b_lance );       break;
 371           case  knight:      Foo( b_knight );      break;
 372           case  silver:      Foo( b_silver );      break;
 373           case  gold:        Foo( b_gold );        break;
 374           case  bishop:      Foo( b_bishop );      break;
 375           case  rook:        Foo( b_rook );        break;
 376           case  king:        Foo( b_king );        break;
 377           case  pro_pawn:    Foo( b_pro_pawn );    break;
 378           case  pro_lance:   Foo( b_pro_lance );   break;
 379           case  pro_knight:  Foo( b_pro_knight );  break;
 380           case  pro_silver:  Foo( b_pro_silver );  break;
 381           case  horse:       Foo( b_horse );       break;
 382           case  dragon:      Foo( b_dragon );      break;
 383           case -pawn:        Foo( w_pawn );        break;
 384           case -lance:       Foo( w_lance );       break;
 385           case -knight:      Foo( w_knight );      break;
 386           case -silver:      Foo( w_silver );      break;
 387           case -gold:        Foo( w_gold );        break;
 388           case -bishop:      Foo( w_bishop );      break;
 389           case -rook:        Foo( w_rook );        break;
 390           case -king:        Foo( w_king );        break;
 391           case -pro_pawn:    Foo( w_pro_pawn );    break;
 392           case -pro_lance:   Foo( w_pro_lance );   break;
 393           case -pro_knight:  Foo( w_pro_knight );  break;
 394           case -pro_silver:  Foo( w_pro_silver );  break;
 395           case -horse:       Foo( w_horse );       break;
 396           case -dragon:      Foo( w_dragon );      break;
 397           }
 398 #undef Foo
 399       }
 400
 401   if ( key > key_flip )
 402     {
 403       key       = key_flip;
 404       *pis_flip = 1;
 405     }
 406   else { *pis_flip = 0; }
 407
 408   return key;
 409 }
 410
 411
 412 static int
 413 normalize_book_move( book_move_t * restrict pbook_move, int moves )
 414 {
 415   book_move_t swap;
 416   double dscale;
 417   unsigned int u, norm;
 418   int i, j;
 419
 420   /* insertion sort by nwin */
 421   pbook_move[moves].freq = 0;
 422   for ( i = moves-2; i >= 0; i-- )
 423     {
 424       u    = pbook_move[i].freq;
 425       swap = pbook_move[i];
 426       for ( j = i+1; pbook_move[j].freq > u; j++ )
 427         {
 428           pbook_move[j-1] = pbook_move[j];
 429         }
 430       pbook_move[j-1] = swap;
 431     }
 432
 433   /* normalization */
 434   for ( norm = 0, i = 0; i < moves; i++ ) { norm += pbook_move[i].freq; }
 435   dscale = (double)USHRT_MAX / (double)norm;
 436   for ( norm = 0, i = 0; i < moves; i++ )
 437     {
 438       u = (unsigned int)( (double)pbook_move[i].freq * dscale );
 439       if ( ! u )           { u = 1U; }
 440       if ( u > USHRT_MAX ) { u = USHRT_MAX; }
 441
 442       pbook_move[i].freq = (unsigned short)u;
 443       norm              += u;
 444     }
 445   if ( norm > (unsigned int)pbook_move[0].freq + USHRT_MAX )
 446     {
 447       str_error = "normalization error";
 448       return -2;
 449     }
 450
 451   pbook_move[0].freq
 452     = (unsigned short)( pbook_move[0].freq + USHRT_MAX - norm );
 453
 454   return 1;
 455 }
 456
 457
 458 #if ! defined(MINIMUM)
 459
 460 #define MaxNumCell      0x400000
 461 #if defined(BK_SMALL)
 462 #  define MaxPlyBook    64
 463 #else
 464 #  define MaxPlyBook    128
 465 #endif
 466
 467 typedef struct {
 468   unsigned int nwin, ngame, nwin_bnz, ngame_bnz, move;
 469 } record_move_t;
 470
 471 typedef struct {
 472   uint64_t key;
 473   unsigned short smove;
 474   unsigned char result;
 475 } cell_t;
 476
 477 static unsigned int move2bm( unsigned int move, int turn, int is_flip );
 478 static int find_min_cell( const cell_t *pcell, int ntemp );
 479 static int read_a_cell( cell_t *pcell, FILE *pf );
 480 static int CONV_CDECL compare( const void * p1, const void *p2 );
 481 static int dump_cell( cell_t *pcell, int ncell, int num_tmpfile );
 482 static int examine_game( tree_t * restrict ptree, record_t *pr,
 483                          int *presult, unsigned int *pmoves );
 484 static int move_selection( const record_move_t *p, int ngame, int nwin );
 485 static int make_cell_csa( tree_t * restrict ptree, record_t *pr,
 486                           cell_t *pcell, int num_tmpfile );
 487 static int merge_cell( record_move_t *precord_move, FILE **ppf,
 488                        int num_tmpfile );
 489 static int read_anti_book( tree_t * restrict ptree, record_t * pr );
 490
 491 int
 492 book_create( tree_t * restrict ptree )
 493 {
 494   record_t record;
 495   FILE *ppf[101];
 496   char str_filename[SIZE_FILENAME];
 497   record_move_t *precord_move;
 498   cell_t *pcell;
 499   int iret, num_tmpfile, i, j;
 500
 501
 502   num_tmpfile = 0;
 503
 504   pcell = memory_alloc( sizeof(cell_t) * MaxNumCell );
 505   if ( pcell == NULL ) { return -2; }
 506
 507   Out("\n  [book.csa]\n");
 508
 509   iret = record_open( &record, "book.csa", mode_read, NULL, NULL );
 510   if ( iret < 0 ) { return iret; }
 511
 512   num_tmpfile = make_cell_csa( ptree, &record, pcell, num_tmpfile );
 513   if ( num_tmpfile < 0 )
 514     {
 515       memory_free( pcell );
 516       record_close( &record );
 517       return num_tmpfile;
 518     }
 519
 520   iret = record_close( &record );
 521   if ( iret < 0 )
 522     {
 523       memory_free( pcell );
 524       return iret;
 525     }
 526
 527   memory_free( pcell );
 528
 529   if ( ! num_tmpfile )
 530     {
 531       str_error = "No book data";
 532       return -2;
 533     }
 534
 535   if ( num_tmpfile > 100 )
 536     {
 537       str_error = "Number of tmp??.bin files are too large.";
 538       return -2;
 539     }
 540
 541   iret = book_off();
 542   if ( iret < 0 ) { return iret; }
 543
 544   pf_book = file_open( str_book, "wb" );
 545   if ( pf_book == NULL ) { return -2; }
 546
 547   precord_move = memory_alloc( sizeof(record_move_t) * (MAX_LEGAL_MOVES+1) );
 548   if ( precord_move == NULL ) { return -2; }
 549
 550   for ( i = 0; i < num_tmpfile; i++ )
 551     {
 552       snprintf( str_filename, SIZE_FILENAME, "tmp%02d.bin", i );
 553       ppf[i] = file_open( str_filename, "rb" );
 554       if ( ppf[i] == NULL )
 555         {
 556           memory_free( precord_move );
 557           file_close( pf_book );
 558           for ( j = 0; j < i; j++ ) { file_close( ppf[j] ); }
 559           return -2;
 560         }
 561     }
 562
 563   iret = merge_cell( precord_move, ppf, num_tmpfile );
 564   if ( iret < 0 )
 565     {
 566       memory_free( precord_move );
 567       file_close( pf_book );
 568       for ( i = 0; i < num_tmpfile; i++ ) { file_close( ppf[i] ); }
 569       return iret;
 570     }
 571
 572   memory_free( precord_move );
 573
 574   iret = book_on();
 575   if ( iret < 0 ) { return iret; }
 576
 577 #if 1
 578   iret = record_open( &record, "book_anti.csa", mode_read, NULL, NULL );
 579   if ( iret < 0 ) { return iret; }
 580
 581   iret = read_anti_book( ptree, &record );
 582   if ( iret < 0 )
 583     {
 584       record_close( &record );
 585       return iret;
 586     }
 587 #endif
 588
 589   return record_close( &record );
 590 }
 591
 592
 593 static int
 594 read_anti_book( tree_t * restrict ptree, record_t * pr )
 595 {
 596   uint64_t key;
 597   book_move_t abook_move[ BK_MAX_MOVE+1 ];
 598   size_t size;
 599   unsigned int move, position, bm, umoves;
 600   int iret, result, istatus, is_flip, i, moves;
 601
 602   do {
 603
 604     istatus = examine_game( ptree, pr, &result, &umoves );
 605     if ( istatus < 0 ) { return istatus; }
 606     if ( result == -2 )
 607       {
 608         str_error = "no result in book_anti.csa";
 609         return -2;
 610       }
 611
 612     while ( pr->moves < umoves-1U )
 613       {
 614         istatus = in_CSA( ptree, pr, NULL, 0 );
 615         if ( istatus != record_misc )
 616           {
 617             str_error = "internal error at book.c";
 618             return -2;
 619           }
 620       }
 621
 622     istatus = in_CSA( ptree, pr, &move, flag_nomake_move );
 623     if ( istatus < 0 ) { return istatus; }
 624
 625     key = book_hash_func( ptree, &is_flip );
 626
 627     moves = book_read( key, abook_move, &position );
 628     if ( moves < 0 ) { return moves; }
 629
 630     bm = move2bm( move, root_turn, is_flip );
 631     for ( i = 0; i < moves; i++ )
 632       {
 633         if ( bm == abook_move[i].smove ) { break; }
 634       }
 635
 636     if ( i == moves )
 637       {
 638         out_board( ptree, stdout, 0, 0 );
 639         printf( "%s is not found in the book\n\n", str_CSA_move(move) );
 640       }
 641     else {
 642       abook_move[i].freq = 0;
 643
 644       iret = normalize_book_move( abook_move, moves );
 645       if ( iret < 0 ) { return iret; }
 646
 647       for ( i = 0; i < moves; i++ )
 648         {
 649           *(unsigned short *)( book_section + i*BK_SIZE_MOVE )
 650             = abook_move[i].smove;
 651           *(unsigned short *)( book_section + i*BK_SIZE_MOVE + 2 )
 652             = abook_move[i].freq;
 653         }
 654       size = (size_t)( moves * BK_SIZE_MOVE );
 655       if ( fseek( pf_book, (long)(position+BK_SIZE_HEADER), SEEK_SET ) == EOF
 656            || fwrite( book_section, sizeof(unsigned char),
 657                       size, pf_book ) != size )
 658         {
 659           str_error = str_io_error;
 660           return -2;
 661         }
 662
 663       out_board( ptree, stdout, 0, 0 );
 664       printf( "%s is discarded\n\n", str_CSA_move(move) );
 665     }
 666
 667     if ( istatus != record_eof && istatus != record_next )
 668       {
 669         istatus = record_wind( pr );
 670         if ( istatus < 0 ) { return istatus; }
 671       }
 672   } while ( istatus != record_eof );
 673
 674   return 1;
 675 }
 676
 677
 678 static int
 679 make_cell_csa( tree_t * restrict ptree, record_t *pr, cell_t *pcell,
 680                int num_tmpfile )
 681 {
 682   struct {
 683     uint64_t hash_key;
 684     unsigned int hand, move;
 685   } rep_tbl[MaxPlyBook+1];
 686   uint64_t key;
 687   unsigned int nwhite_win, nblack_win, ndraw, ninvalid, nbnz_black, nbnz_white;
 688   unsigned int move, moves, uresult;
 689   int icell, result, is_flip, iret, istatus, ply, i, black_bnz, white_bnz;
 690
 691   nwhite_win = nblack_win = ndraw = ninvalid = nbnz_white = nbnz_black = 0;
 692   icell = black_bnz = white_bnz = 0;
 693   istatus = record_next;
 694
 695   while ( istatus != record_eof ) {
 696
 697     istatus = examine_game( ptree, pr, &result, &moves );
 698     if ( istatus < 0 ) { return istatus; }
 699
 700     if      ( result == -1 ) { nwhite_win++; }
 701     else if ( result ==  1 ) { nblack_win++; }
 702     else if ( result ==  0 ) { ndraw++; }
 703     else {
 704       ninvalid++;
 705       continue;
 706     }
 707
 708     if ( moves > MaxPlyBook ) { moves = MaxPlyBook; }
 709
 710     for ( ply = 0;; ply++ ) {
 711       istatus = in_CSA( ptree, pr, &move, flag_nomake_move );
 712       if ( ! ply )
 713         {
 714           black_bnz = strcmp( pr->str_name1, "Bonanza" ) ? 0 : 1;
 715           white_bnz = strcmp( pr->str_name2, "Bonanza" ) ? 0 : 1;
 716           if ( ! strcmp( pr->str_name1, "Bonanza" ) )
 717             {
 718               black_bnz   = 1;
 719               nbnz_black += 1;
 720             }
 721           else { black_bnz = 0; }
 722           if ( ! strcmp( pr->str_name2, "Bonanza" ) )
 723             {
 724               white_bnz   = 1;
 725               nbnz_white += 1;
 726             }
 727           else { white_bnz = 0; }
 728         }
 729       if ( istatus < 0 ) { return istatus; }
 730       if ( istatus == record_resign && ! moves ) { break; }
 731       if ( istatus != record_misc )
 732         {
 733           str_error = "internal error at book.c";
 734           return -2;
 735         }
 736
 737       rep_tbl[ply].hash_key = HASH_KEY;
 738       rep_tbl[ply].hand     = HAND_B;
 739       rep_tbl[ply].move     = move;
 740       for ( i = ( ply & 1 ); i < ply; i += 2 )
 741         {
 742           if ( rep_tbl[i].hash_key == HASH_KEY
 743                && rep_tbl[i].hand == HAND_B
 744                && rep_tbl[i].move == move ) { break; }
 745         }
 746
 747       if ( i == ply ) {
 748         key     = book_hash_func( ptree, &is_flip );
 749         uresult = (unsigned int)( root_turn ? -1*result+1 : result+1 );
 750         if ( ( root_turn == black && black_bnz )
 751              || ( root_turn == white && white_bnz ) ) { uresult |= 0x4U; }
 752
 753         pcell[icell].key    = key;
 754         pcell[icell].result = (unsigned char)uresult;
 755         pcell[icell].smove  = (unsigned short)move2bm( move, root_turn,
 756                                                        is_flip );
 757         icell++;
 758         if ( icell == MaxNumCell ) {
 759           iret = dump_cell( pcell, icell, num_tmpfile++ );
 760           if ( iret < 0 ) { return iret; }
 761           icell = 0;
 762         }
 763         if ( ! ( (icell-1) & 0x1ffff ) ) { Out( "." ); }
 764       }
 765
 766       if ( pr->moves >= moves ) { break; }
 767
 768       iret = make_move_root( ptree, move, 0 );
 769       if ( iret < 0 ) { return iret; }
 770     }
 771
 772     if ( istatus != record_eof && istatus != record_next )
 773       {
 774         istatus = record_wind( pr );
 775         if ( istatus < 0 ) { return istatus; }
 776       }
 777   }
 778
 779   iret  = dump_cell( pcell, icell, num_tmpfile++ );
 780   if ( iret < 0 ) { return iret; }
 781
 782   Out( "\n"
 783        "Total games:   %7u\n"
 784        "  Discarded:   %7u\n"
 785        "  Black wins:  %7u\n"
 786        "  White wins:  %7u\n"
 787        "  Drawn:       %7u\n"
 788        "  Black Bnz:   %7u\n"
 789        "  White Bnz:   %7u\n", nblack_win + nwhite_win + ndraw + ninvalid,
 790        ninvalid, nblack_win, nwhite_win, ndraw, nbnz_black, nbnz_white );
 791
 792   return num_tmpfile;
 793 }
 794
 795
 796 static int
 797 merge_cell( record_move_t *precord_move, FILE **ppf, int num_tmpfile )
 798 {
 799   double dscale;
 800   record_move_t swap;
 801   cell_t acell[101];
 802   uint64_t key;
 803   unsigned int book_moves, book_positions, move, size_data, size_section;
 804   unsigned int max_size_section, nwin, nwin_bnz, ngame, ngame_bnz, position;
 805   unsigned int u, norm;
 806   int i, j, iret, ibook_section, imin, nmove;
 807   unsigned short s;
 808
 809   for ( i = 0; i < num_tmpfile; i++ )
 810     {
 811       iret = read_a_cell( acell + i, ppf[i] );
 812       if ( iret < 0 ) { return iret; }
 813     }
 814
 815   imin             = find_min_cell( acell, num_tmpfile );
 816   position         = BK_SIZE_INDEX * NUM_SECTION;
 817   max_size_section = book_moves = book_positions = 0;
 818   for ( ibook_section = 0; ibook_section < NUM_SECTION; ibook_section++ ) {
 819     size_section = 0;
 820     for (;;) {
 821       key  = acell[imin].key;
 822       i    = (int)( (unsigned int)key & (unsigned int)(NUM_SECTION-1) );
 823       if ( i != ibook_section || key == UINT64_MAX ) { break; }
 824
 825       nwin = nmove = nwin_bnz = ngame = ngame_bnz = precord_move[0].move = 0;
 826       do {
 827         move = (unsigned int)acell[imin].smove;
 828         for ( i = 0; precord_move[i].move && precord_move[i].move != move;
 829               i++ );
 830         if ( ! precord_move[i].move )
 831           {
 832             precord_move[i].nwin     = precord_move[i].ngame     = 0;
 833             precord_move[i].nwin_bnz = precord_move[i].ngame_bnz = 0;
 834             precord_move[i].move     = move;
 835             precord_move[i+1].move   = 0;
 836             nmove++;
 837           }
 838
 839         if ( acell[imin].result & b0010 )
 840           {
 841             if ( acell[imin].result & b0100 )
 842               {
 843                 precord_move[i].nwin_bnz += 1;
 844                 nwin_bnz                 += 1;
 845               }
 846             precord_move[i].nwin     += 1;
 847             nwin                     += 1;
 848           }
 849
 850         if ( acell[imin].result & b0100 )
 851           {
 852             precord_move[i].ngame_bnz += 1;
 853             ngame_bnz                 += 1;
 854           }
 855         precord_move[i].ngame += 1;
 856         ngame                 += 1;
 857
 858         iret = read_a_cell( acell + imin, ppf[imin] );
 859         if ( iret < 0 ) { return iret; }
 860
 861         imin = find_min_cell( acell, num_tmpfile );
 862       } while ( key == acell[imin].key );
 863
 864 #if defined(BK_COM)
 865       while ( nmove > 1 && ngame_bnz >= 128 )
 866         {
 867           double max_rate, rate;
 868
 869           max_rate = 0.0;
 870           for ( i = 0; i < nmove; i++ )
 871             {
 872               rate = ( (double)precord_move[i].nwin_bnz
 873                        / (double)( precord_move[i].ngame_bnz + 7 ) );
 874               if ( rate > max_rate ) { max_rate = rate; }
 875             }
 876           if ( max_rate < 0.1 ) { break; }
 877
 878           max_rate *= 0.85;
 879           i = 0;
 880           do {
 881             rate = ( (double)precord_move[i].nwin_bnz
 882                      / (double)( precord_move[i].ngame_bnz + 7 ) );
 883
 884             if ( rate > max_rate ) { i++; }
 885             else {
 886               precord_move[i] = precord_move[nmove-1];
 887               nmove -= 1;
 888             }
 889           } while ( i < nmove );
 890
 891           break;
 892         }
 893 #endif
 894       if ( ! nmove ) { continue; }
 895
 896       i = 0;
 897       do {
 898         if ( move_selection( precord_move + i, ngame, nwin ) ) { i++; }
 899         else {
 900           precord_move[i] = precord_move[nmove-1];
 901           nmove -= 1;
 902         }
 903       } while ( i < nmove );
 904
 905       if ( ! nmove ) { continue; }
 906
 907       size_data = BK_SIZE_HEADER + BK_SIZE_MOVE * nmove;
 908       if ( size_section + size_data > MAX_SIZE_SECTION
 909            || size_data > UCHAR_MAX )
 910         {
 911           str_error = "book_section buffer overflow";
 912           return -2;
 913         }
 914       if ( nmove > BK_MAX_MOVE )
 915         {
 916           str_error = "BK_MAX_MOVE is too small";
 917           return -2;
 918         }
 919
 920       /* insertion sort by nwin */
 921       precord_move[nmove].nwin = 0;
 922       for ( i = nmove-2; i >= 0; i-- )
 923         {
 924           u    = precord_move[i].nwin;
 925           swap = precord_move[i];
 926           for ( j = i+1; precord_move[j].nwin > u; j++ )
 927             {
 928               precord_move[j-1] = precord_move[j];
 929             }
 930           precord_move[j-1] = swap;
 931         }
 932
 933       /* normalize nwin */
 934       for ( norm = 0, i = 0; i < nmove; i++ ) { norm += precord_move[i].nwin; }
 935       dscale = (double)USHRT_MAX / (double)norm;
 936       for ( norm = 0, i = 0; i < nmove; i++ )
 937         {
 938           u = (unsigned int)( (double)precord_move[i].nwin * dscale );
 939           if ( ! u )           { u = 1U; }
 940           if ( u > USHRT_MAX ) { u = USHRT_MAX; }
 941
 942           precord_move[i].nwin = u;
 943           norm                += u;
 944         }
 945       if ( norm > precord_move[0].nwin + USHRT_MAX )
 946         {
 947           str_error = "normalization error\n";
 948           return -2;
 949         }
 950       precord_move[0].nwin += USHRT_MAX - norm;
 951
 952       book_section[size_section+0] = (unsigned char)size_data;
 953       *(uint64_t *)(book_section+size_section+1) = key;
 954
 955       for ( u = size_section+BK_SIZE_HEADER, i = 0; i < nmove;
 956             u += BK_SIZE_MOVE, i++ )
 957         {
 958           *(unsigned short *)(book_section+u)
 959             = (unsigned short)precord_move[i].move;
 960           *(unsigned short *)(book_section+u+2)
 961             = (unsigned short)precord_move[i].nwin;
 962         }
 963       book_positions += 1;
 964       book_moves     += nmove;
 965       size_section   += size_data;
 966     }
 967     if ( fseek( pf_book, BK_SIZE_INDEX * ibook_section, SEEK_SET ) == EOF )
 968       {
 969         str_error = str_io_error;
 970         return -2;
 971       }
 972     if ( fwrite( &position, sizeof(unsigned int), 1, pf_book ) != 1 )
 973       {
 974         str_error = str_io_error;
 975         return -2;
 976       }
 977     s = (unsigned short)size_section;
 978     if ( fwrite( &s, sizeof(unsigned short), 1, pf_book ) != 1 )
 979       {
 980         str_error = str_io_error;
 981         return -2;
 982       }
 983     if ( fseek( pf_book, position, SEEK_SET ) == EOF )
 984       {
 985         str_error = str_io_error;
 986         return -2;
 987       }
 988     if ( fwrite( &book_section, sizeof(unsigned char), (size_t)size_section,
 989                  pf_book ) != (size_t)size_section )
 990       {
 991         str_error = str_io_error;
 992         return -2;
 993       }
 994
 995     if ( size_section > max_size_section ) { max_size_section = size_section; }
 996     position += size_section;
 997   }
 998
 999   Out( "Positions in the book:  %u\n", book_positions );
1000   Out( "Moves in the book:      %u\n", book_moves );
1001   Out( "Max. size of a section: %d\n", max_size_section );
1002
1003   return 1;
1004 }
1005
1006
1007 static int
1008 move_selection( const record_move_t *p, int ngame, int nwin )
1009 {
1010   double total_win_norm, win_norm, win, game, win_move, game_move;
1011
1012 #if defined(BK_SMALL)
1013   if ( ! p->nwin || p->ngame < 3 ) { return 0; }
1014 #else
1015   if ( ! p->nwin || p->ngame < 2 ) { return 0; }
1016 #endif
1017
1018   win       = (double)nwin;
1019   game      = (double)ngame;
1020   win_move  = (double)p->nwin;
1021   game_move = (double)p->ngame;
1022
1023   total_win_norm = win      * game_move;
1024   win_norm       = win_move * game;
1025   if ( win_norm < total_win_norm * 0.85 ) { return 0; }
1026
1027   return 1;
1028 }
1029
1030
1031 static int
1032 find_min_cell( const cell_t *pcell, int num_tmpfile )
1033 {
1034   int imin, i;
1035
1036   imin = 0;
1037   for ( i = 1; i < num_tmpfile; i++ )
1038     {
1039       if ( compare( pcell+imin, pcell+i ) == 1 ) { imin = i; }
1040     }
1041   return imin;
1042 }
1043
1044
1045 static int
1046 read_a_cell( cell_t *pcell, FILE *pf )
1047 {
1048   if ( fread( &pcell->key, sizeof(uint64_t), 1, pf ) != 1 )
1049     {
1050       if ( feof( pf ) )
1051         {
1052           pcell->key = UINT64_MAX;
1053           return 1;
1054         }
1055       str_error = str_io_error;
1056       return -2;
1057     }
1058   if ( fread( &pcell->smove, sizeof(unsigned short), 1, pf ) != 1 )
1059     {
1060       str_error = str_io_error;
1061       return -2;
1062     }
1063   if ( fread( &pcell->result, sizeof(unsigned char), 1, pf ) != 1 )
1064     {
1065       str_error = str_io_error;
1066       return -2;
1067     }
1068
1069   return 1;
1070 }
1071
1072
1073 static int
1074 examine_game( tree_t * restrict ptree, record_t *pr, int *presult,
1075               unsigned int *pmoves )
1076 {
1077   rpos_t rpos;
1078   int iret, istatus, is_lost, is_win;
1079   unsigned int moves;
1080
1081   *presult = -2;
1082
1083   iret = record_getpos( pr, &rpos );
1084   if ( iret < 0 ) { return iret; }
1085
1086   is_lost = is_win = 0;
1087   moves = 0;
1088   do {
1089     istatus = in_CSA( ptree, pr, NULL, flag_detect_hang );
1090     if ( istatus < 0 )
1091       {
1092         /* the game is end, however the record is invalid */
1093         if ( strstr( str_error, str_bad_record ) != NULL
1094              && ( game_status & mask_game_end ) )
1095           {
1096             break;
1097           }
1098
1099         /* a hang-king and a double-pawn are counted as a lost game */
1100         if ( strstr( str_error, str_king_hang ) != NULL
1101              || strstr( str_error, str_double_pawn )  != NULL
1102              || strstr( str_error, str_mate_drppawn ) != NULL )
1103           {
1104             is_lost = 1;
1105             break;
1106           }
1107
1108         return istatus;
1109       }
1110     /* previous move had an error, count as a won game */
1111     else if ( istatus == record_error )
1112       {
1113         is_win = 1;
1114         break;
1115       }
1116     else if ( istatus == record_misc ) { moves++; }
1117   } while ( istatus != record_next && istatus != record_eof );
1118
1119   if ( istatus != record_next && istatus != record_eof )
1120     {
1121       istatus = record_wind( pr );
1122       if ( istatus < 0 ) { return istatus; }
1123     }
1124
1125   if ( ! ( is_lost || is_win || ( game_status & mask_game_end ) ) )
1126     {
1127       return istatus;
1128     }
1129
1130   if      ( is_win ) { *presult = root_turn ? -1 : 1; }
1131   else if ( is_lost || ( game_status & ( flag_mated | flag_resigned ) ) )
1132     {
1133       *presult = root_turn ? 1 : -1;
1134     }
1135   else { *presult = 0; }
1136
1137   *pmoves = moves;
1138
1139   iret = record_setpos( pr, &rpos );
1140   if ( iret < 0 ) { return iret; }
1141
1142   return istatus;
1143 }
1144
1145
1146 static int
1147 dump_cell( cell_t *pcell, int ncell, int num_tmpfile )
1148 {
1149   char str_filename[SIZE_FILENAME];
1150   FILE *pf;
1151   int i, iret;
1152
1153   Out( " sort" );
1154   qsort( pcell, ncell, sizeof(cell_t), compare );
1155
1156   Out( " dump", str_filename );
1157   snprintf( str_filename, SIZE_FILENAME, "tmp%02d.bin", num_tmpfile );
1158   pf = file_open( str_filename, "wb" );
1159   if ( pf == NULL ) { return -2; }
1160
1161   for ( i = 0; i < ncell; i++ )
1162     {
1163       if ( fwrite( &pcell[i].key, sizeof(uint64_t), 1, pf ) != 1 )
1164         {
1165           file_close( pf );
1166           str_error = str_io_error;
1167           return -2;
1168         }
1169       if ( fwrite( &pcell[i].smove, sizeof(unsigned short), 1, pf ) != 1 )
1170         {
1171           file_close( pf );
1172           str_error = str_io_error;
1173           return -2;
1174         }
1175       if ( fwrite( &pcell[i].result, sizeof(unsigned char), 1, pf ) != 1 )
1176         {
1177           file_close( pf );
1178           str_error = str_io_error;
1179           return -2;
1180         }
1181     }
1182
1183   iret = file_close( pf );
1184   if ( iret < 0 ) { return iret; }
1185
1186   Out( " done (%s)\n", str_filename );
1187
1188   return 1;
1189 }
1190
1191
1192 static int CONV_CDECL
1193 compare( const void * p1, const void * p2 )
1194 {
1195   const cell_t * pcell1 = p1;
1196   const cell_t * pcell2 = p2;
1197   unsigned int u1, u2;
1198
1199   u1 = (unsigned int)pcell1->key & (unsigned int)(NUM_SECTION-1);
1200   u2 = (unsigned int)pcell2->key & (unsigned int)(NUM_SECTION-1);
1201
1202   if ( u1 < u2 ) { return -1; }
1203   if ( u1 > u2 ) { return  1; }
1204   if ( pcell1->key < pcell2->key ) { return -1; }
1205   if ( pcell1->key > pcell2->key ) { return  1; }
1206
1207   return 0;
1208 }
1209
1210
1211 static unsigned int
1212 move2bm( unsigned int move, int turn, int is_flip )
1213 {
1214   ft_t ft;
1215   unsigned int bmove;
1216   int is_promote;
1217
1218   ft.to      = I2To(move);
1219   ft.from    = I2From(move);
1220   is_promote = I2IsPromote(move);
1221
1222   ft = flip_ft( ft, turn, is_flip );
1223
1224   bmove = (unsigned int)( is_promote | From2Move(ft.from) | ft.to );
1225
1226   return bmove;
1227 }
1228
1229
1230 #endif /* no MINIMUM */