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