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