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