10 Opening Book Data Structure: Index BookData
12 Index: IndexEntry.. (NUM_SECTION times)
14 IndexEntry: SectionPointer SectionSize
16 BookData: Section.. (NUM_SECTION times)
18 Section: [DataEntry]..
20 DataEntry: Header Move...
24 4 byte: position of the section in character
27 2 byte: size of the section in character
30 1 byte: number of bytes for the DataEntry
38 #define BK_SIZE_INDEX 6
39 #define BK_SIZE_HEADER 9
40 #define BK_SIZE_MOVE 4
41 #define BK_MAX_MOVE 32
43 #if ( BK_SIZE_HEADER + BK_SIZE_MOVE * BK_MAX_MOVE > UCHAR_MAX )
44 # error "Maximum size of DataEntry is larger than UCHAR_MAX"
47 typedef struct { unsigned short smove, freq; } book_move_t;
49 typedef struct { int from, to; } ft_t;
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,
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 );
63 int iret = file_close( pf_book );
64 if ( iret < 0 ) { return iret; }
66 pf_book = file_open( str_book, "rb+" );
67 if ( pf_book == NULL ) { return -2; }
76 int iret = file_close( pf_book );
77 if ( iret < 0 ) { return iret; }
86 book_probe( tree_t * restrict ptree )
88 book_move_t abook_move[ BK_MAX_MOVE+1 ];
91 unsigned int move, position, freq_lower_limit;
92 int is_flip, i, j, moves, ply;
94 key = book_hash_func( ptree, &is_flip );
96 moves = book_read( key, abook_move, &position );
97 if ( moves <= 0 ) { return moves; }
99 #if ! defined(MINIMUM) || ! defined(NDEBUG)
100 for ( j = i = 0; i < moves; i++ ) { j += abook_move[i].freq; }
101 if ( j != USHRT_MAX )
103 str_error = "normalization error (book.bin)";
108 /* decision of book move based on pseudo-random number */
109 if ( game_status & flag_puzzling ) { j = 0; }
111 drand = (double)rand64() / (double)UINT64_MAX;
113 if ( game_status & flag_narrow_book )
115 #if defined(BK_ULTRA_NARROW)
116 freq_lower_limit = abook_move[0].freq;
118 freq_lower_limit = abook_move[0].freq / 2U;
121 for ( i = 1; i < moves; i++ )
123 if ( abook_move[i].freq < freq_lower_limit ) { break; }
126 normalize_book_move( abook_move, moves );
129 for ( j = moves-1; j > 0; j-- )
131 dscore = (double)( abook_move[j].freq ) / (double)USHRT_MAX;
132 if ( drand <= dscore ) { break; }
135 if ( ! abook_move[j].freq ) { j = 0; }
139 if ( ! ( game_status & ( flag_pondering | flag_puzzling ) ) )
141 Out( " move freq\n" );
142 OutCsaShogi( "info" );
143 for ( i = 0; i < moves; i++ )
147 dscore = (double)abook_move[i].freq / (double)USHRT_MAX;
148 move = bm2move( ptree, (unsigned int)abook_move[i].smove, is_flip );
149 str = str_CSA_move( move );
151 Out( " %c %s %5.1f\n", i == j ? '*' : ' ', str, dscore * 100.0 );
152 OutCsaShogi( " %s(%.0f%%)", str, dscore * 100.0 );
157 move = bm2move( ptree, (unsigned int)abook_move[j].smove, is_flip );
158 if ( ! is_move_valid( ptree, move, root_turn ) )
160 out_warning( "BAD BOOK MOVE!! " );
164 ply = record_game.moves;
165 if ( game_status & flag_pondering ) { ply++; }
166 if ( ply < HASH_REG_HIST_LEN )
168 history_book_learn[ ply ].key_book = key;
169 history_book_learn[ ply ].move_probed = move;
170 history_book_learn[ ply ].key_probed = (unsigned int)HASH_KEY;
171 history_book_learn[ ply ].hand_probed = HAND_B;
172 history_book_learn[ ply ].data = (unsigned int)is_flip << 30;
173 if ( game_status & flag_narrow_book )
175 history_book_learn[ ply ].data |= 1U << 29;
179 ptree->current_move[1] = move;
186 book_read( uint64_t key, book_move_t *pbook_move, unsigned int *pposition )
189 const unsigned char *p;
190 unsigned int position, size_section, size, u;
191 int ibook_section, moves;
194 ibook_section = (int)( (unsigned int)key & (unsigned int)( NUM_SECTION-1 ) );
196 if ( fseek( pf_book, BK_SIZE_INDEX*ibook_section, SEEK_SET ) == EOF )
198 str_error = str_io_error;
202 if ( fread( &position, sizeof(int), 1, pf_book ) != 1 )
204 str_error = str_io_error;
208 if ( fread( &s, sizeof(unsigned short), 1, pf_book ) != 1 )
210 str_error = str_io_error;
213 size_section = (unsigned int)s;
214 if ( size_section > MAX_SIZE_SECTION )
216 str_error = str_book_error;
220 if ( fseek( pf_book, (long)position, SEEK_SET ) == EOF )
222 str_error = str_io_error;
225 if ( fread( book_section, sizeof(unsigned char), (size_t)size_section,
226 pf_book ) != (size_t)size_section )
228 str_error = str_io_error;
234 *pposition = position;
235 while ( book_section + size_section > p )
237 size = (unsigned int)p[0];
238 book_key = *(uint64_t *)( p + 1 );
239 if ( book_key == key ) { break; }
243 if ( book_section + size_section <= p ) { return 0; }
245 for ( moves = 0, u = BK_SIZE_HEADER; u < size; moves++, u += BK_SIZE_MOVE )
247 pbook_move[moves].smove = *(unsigned short *)(p+u+0);
248 pbook_move[moves].freq = *(unsigned short *)(p+u+2);
256 flip_ft( ft_t ft, int turn, int is_flip )
258 int ito_rank, ito_file, ifrom_rank, ifrom_file;
260 ito_rank = airank[ft.to];
261 ito_file = aifile[ft.to];
262 if ( ft.from < nsquare )
264 ifrom_rank = airank[ft.from];
265 ifrom_file = aifile[ft.from];
267 else { ifrom_rank = ifrom_file = 0; }
271 ito_rank = rank9 - ito_rank;
272 ito_file = file9 - ito_file;
273 if ( ft.from < nsquare )
275 ifrom_rank = rank9 - ifrom_rank;
276 ifrom_file = file9 - ifrom_file;
282 ito_file = file9 - ito_file;
283 if ( ft.from < nsquare ) { ifrom_file = file9 - ifrom_file; }
286 ft.to = ito_rank * nfile + ito_file;
287 if ( ft.from < nsquare ) { ft.from = ifrom_rank * nfile + ifrom_file; }
294 bm2move( const tree_t * restrict ptree, unsigned int bmove, int is_flip )
301 ft.from = I2From(bmove);
302 ft = flip_ft( ft, root_turn, is_flip );
303 is_promote = I2IsPromote(bmove);
305 move = (unsigned int)( is_promote | From2Move(ft.from) | ft.to );
306 if ( ft.from >= nsquare ) { return move; }
310 move |= Cap2Move(BOARD[ft.to]);
311 move |= Piece2Move(-BOARD[ft.from]);
314 move |= Cap2Move(-BOARD[ft.to]);
315 move |= Piece2Move(BOARD[ft.from]);
323 book_hash_func( const tree_t * restrict ptree, int *pis_flip )
325 uint64_t key, key_flip;
327 int i, iflip, irank, ifile, piece;
330 hand = root_turn ? HAND_W : HAND_B;
331 i = I2HandPawn(hand); if ( i ) { key ^= b_hand_pawn_rand[i-1]; }
332 i = I2HandLance(hand); if ( i ) { key ^= b_hand_lance_rand[i-1]; }
333 i = I2HandKnight(hand); if ( i ) { key ^= b_hand_knight_rand[i-1]; }
334 i = I2HandSilver(hand); if ( i ) { key ^= b_hand_silver_rand[i-1]; }
335 i = I2HandGold(hand); if ( i ) { key ^= b_hand_gold_rand[i-1]; }
336 i = I2HandBishop(hand); if ( i ) { key ^= b_hand_bishop_rand[i-1]; }
337 i = I2HandRook(hand); if ( i ) { key ^= b_hand_rook_rand[i-1]; }
339 hand = root_turn ? HAND_B : HAND_W;
340 i = I2HandPawn(hand); if ( i ) { key ^= w_hand_pawn_rand[i-1]; }
341 i = I2HandLance(hand); if ( i ) { key ^= w_hand_lance_rand[i-1]; }
342 i = I2HandKnight(hand); if ( i ) { key ^= w_hand_knight_rand[i-1]; }
343 i = I2HandSilver(hand); if ( i ) { key ^= w_hand_silver_rand[i-1]; }
344 i = I2HandGold(hand); if ( i ) { key ^= w_hand_gold_rand[i-1]; }
345 i = I2HandBishop(hand); if ( i ) { key ^= w_hand_bishop_rand[i-1]; }
346 i = I2HandRook(hand); if ( i ) { key ^= w_hand_rook_rand[i-1]; }
350 for ( irank = rank1; irank <= rank9; irank++ )
351 for ( ifile = file1; ifile <= file9; ifile++ )
355 i = ( rank9 - irank ) * nfile + file9 - ifile;
356 iflip = ( rank9 - irank ) * nfile + ifile;
357 piece = -(int)BOARD[nsquare-i-1];
360 i = irank * nfile + ifile;
361 iflip = irank * nfile + file9 - ifile;
362 piece = (int)BOARD[i];
365 #define Foo(t_pc) key ^= (t_pc ## _rand)[i]; \
366 key_flip ^= (t_pc ## _rand)[iflip];
369 case pawn: Foo( b_pawn ); break;
370 case lance: Foo( b_lance ); break;
371 case knight: Foo( b_knight ); break;
372 case silver: Foo( b_silver ); break;
373 case gold: Foo( b_gold ); break;
374 case bishop: Foo( b_bishop ); break;
375 case rook: Foo( b_rook ); break;
376 case king: Foo( b_king ); break;
377 case pro_pawn: Foo( b_pro_pawn ); break;
378 case pro_lance: Foo( b_pro_lance ); break;
379 case pro_knight: Foo( b_pro_knight ); break;
380 case pro_silver: Foo( b_pro_silver ); break;
381 case horse: Foo( b_horse ); break;
382 case dragon: Foo( b_dragon ); break;
383 case -pawn: Foo( w_pawn ); break;
384 case -lance: Foo( w_lance ); break;
385 case -knight: Foo( w_knight ); break;
386 case -silver: Foo( w_silver ); break;
387 case -gold: Foo( w_gold ); break;
388 case -bishop: Foo( w_bishop ); break;
389 case -rook: Foo( w_rook ); break;
390 case -king: Foo( w_king ); break;
391 case -pro_pawn: Foo( w_pro_pawn ); break;
392 case -pro_lance: Foo( w_pro_lance ); break;
393 case -pro_knight: Foo( w_pro_knight ); break;
394 case -pro_silver: Foo( w_pro_silver ); break;
395 case -horse: Foo( w_horse ); break;
396 case -dragon: Foo( w_dragon ); break;
401 if ( key > key_flip )
406 else { *pis_flip = 0; }
413 normalize_book_move( book_move_t * restrict pbook_move, int moves )
417 unsigned int u, norm;
420 /* insertion sort by nwin */
421 pbook_move[moves].freq = 0;
422 for ( i = moves-2; i >= 0; i-- )
424 u = pbook_move[i].freq;
425 swap = pbook_move[i];
426 for ( j = i+1; pbook_move[j].freq > u; j++ )
428 pbook_move[j-1] = pbook_move[j];
430 pbook_move[j-1] = swap;
434 for ( norm = 0, i = 0; i < moves; i++ ) { norm += pbook_move[i].freq; }
435 dscale = (double)USHRT_MAX / (double)norm;
436 for ( norm = 0, i = 0; i < moves; i++ )
438 u = (unsigned int)( (double)pbook_move[i].freq * dscale );
439 if ( ! u ) { u = 1U; }
440 if ( u > USHRT_MAX ) { u = USHRT_MAX; }
442 pbook_move[i].freq = (unsigned short)u;
445 if ( norm > (unsigned int)pbook_move[0].freq + USHRT_MAX )
447 str_error = "normalization error";
452 = (unsigned short)( pbook_move[0].freq + USHRT_MAX - norm );
458 #if ! defined(MINIMUM)
460 #define MaxNumCell 0x400000
461 #if defined(BK_SMALL)
462 # define MaxPlyBook 64
464 # define MaxPlyBook 128
468 unsigned int nwin, ngame, nwin_bnz, ngame_bnz, move;
473 unsigned short smove;
474 unsigned char result;
477 static unsigned int move2bm( unsigned int move, int turn, int is_flip );
478 static int find_min_cell( const cell_t *pcell, int ntemp );
479 static int read_a_cell( cell_t *pcell, FILE *pf );
480 static int CONV_CDECL compare( const void * p1, const void *p2 );
481 static int dump_cell( cell_t *pcell, int ncell, int num_tmpfile );
482 static int examine_game( tree_t * restrict ptree, record_t *pr,
483 int *presult, unsigned int *pmoves );
484 static int move_selection( const record_move_t *p, int ngame, int nwin );
485 static int make_cell_csa( tree_t * restrict ptree, record_t *pr,
486 cell_t *pcell, int num_tmpfile );
487 static int merge_cell( record_move_t *precord_move, FILE **ppf,
489 static int read_anti_book( tree_t * restrict ptree, record_t * pr );
492 book_create( tree_t * restrict ptree )
496 char str_filename[SIZE_FILENAME];
497 record_move_t *precord_move;
499 int iret, num_tmpfile, i, j;
504 pcell = memory_alloc( sizeof(cell_t) * MaxNumCell );
505 if ( pcell == NULL ) { return -2; }
507 Out("\n [book.csa]\n");
509 iret = record_open( &record, "book.csa", mode_read, NULL, NULL );
510 if ( iret < 0 ) { return iret; }
512 num_tmpfile = make_cell_csa( ptree, &record, pcell, num_tmpfile );
513 if ( num_tmpfile < 0 )
515 memory_free( pcell );
516 record_close( &record );
520 iret = record_close( &record );
523 memory_free( pcell );
527 memory_free( pcell );
531 str_error = "No book data";
535 if ( num_tmpfile > 100 )
537 str_error = "Number of tmp??.bin files are too large.";
542 if ( iret < 0 ) { return iret; }
544 pf_book = file_open( str_book, "wb" );
545 if ( pf_book == NULL ) { return -2; }
547 precord_move = memory_alloc( sizeof(record_move_t) * (MAX_LEGAL_MOVES+1) );
548 if ( precord_move == NULL ) { return -2; }
550 for ( i = 0; i < num_tmpfile; i++ )
552 snprintf( str_filename, SIZE_FILENAME, "tmp%02d.bin", i );
553 ppf[i] = file_open( str_filename, "rb" );
554 if ( ppf[i] == NULL )
556 memory_free( precord_move );
557 file_close( pf_book );
558 for ( j = 0; j < i; j++ ) { file_close( ppf[j] ); }
563 iret = merge_cell( precord_move, ppf, num_tmpfile );
566 memory_free( precord_move );
567 file_close( pf_book );
568 for ( i = 0; i < num_tmpfile; i++ ) { file_close( ppf[i] ); }
572 memory_free( precord_move );
575 if ( iret < 0 ) { return iret; }
578 iret = record_open( &record, "book_anti.csa", mode_read, NULL, NULL );
579 if ( iret < 0 ) { return iret; }
581 iret = read_anti_book( ptree, &record );
584 record_close( &record );
589 return record_close( &record );
594 read_anti_book( tree_t * restrict ptree, record_t * pr )
597 book_move_t abook_move[ BK_MAX_MOVE+1 ];
599 unsigned int move, position, bm, umoves;
600 int iret, result, istatus, is_flip, i, moves;
604 istatus = examine_game( ptree, pr, &result, &umoves );
605 if ( istatus < 0 ) { return istatus; }
608 str_error = "no result in book_anti.csa";
612 while ( pr->moves < umoves-1U )
614 istatus = in_CSA( ptree, pr, NULL, 0 );
615 if ( istatus != record_misc )
617 str_error = "internal error at book.c";
622 istatus = in_CSA( ptree, pr, &move, flag_nomake_move );
623 if ( istatus < 0 ) { return istatus; }
625 key = book_hash_func( ptree, &is_flip );
627 moves = book_read( key, abook_move, &position );
628 if ( moves < 0 ) { return moves; }
630 bm = move2bm( move, root_turn, is_flip );
631 for ( i = 0; i < moves; i++ )
633 if ( bm == abook_move[i].smove ) { break; }
638 out_board( ptree, stdout, 0, 0 );
639 printf( "%s is not found in the book\n\n", str_CSA_move(move) );
642 abook_move[i].freq = 0;
644 iret = normalize_book_move( abook_move, moves );
645 if ( iret < 0 ) { return iret; }
647 for ( i = 0; i < moves; i++ )
649 *(unsigned short *)( book_section + i*BK_SIZE_MOVE )
650 = abook_move[i].smove;
651 *(unsigned short *)( book_section + i*BK_SIZE_MOVE + 2 )
652 = abook_move[i].freq;
654 size = (size_t)( moves * BK_SIZE_MOVE );
655 if ( fseek( pf_book, (long)(position+BK_SIZE_HEADER), SEEK_SET ) == EOF
656 || fwrite( book_section, sizeof(unsigned char),
657 size, pf_book ) != size )
659 str_error = str_io_error;
663 out_board( ptree, stdout, 0, 0 );
664 printf( "%s is discarded\n\n", str_CSA_move(move) );
667 if ( istatus != record_eof && istatus != record_next )
669 istatus = record_wind( pr );
670 if ( istatus < 0 ) { return istatus; }
672 } while ( istatus != record_eof );
679 make_cell_csa( tree_t * restrict ptree, record_t *pr, cell_t *pcell,
684 unsigned int hand, move;
685 } rep_tbl[MaxPlyBook+1];
687 unsigned int nwhite_win, nblack_win, ndraw, ninvalid, nbnz_black, nbnz_white;
688 unsigned int move, moves, uresult;
689 int icell, result, is_flip, iret, istatus, ply, i, black_bnz, white_bnz;
691 nwhite_win = nblack_win = ndraw = ninvalid = nbnz_white = nbnz_black = 0;
692 icell = black_bnz = white_bnz = 0;
693 istatus = record_next;
695 while ( istatus != record_eof ) {
697 istatus = examine_game( ptree, pr, &result, &moves );
698 if ( istatus < 0 ) { return istatus; }
700 if ( result == -1 ) { nwhite_win++; }
701 else if ( result == 1 ) { nblack_win++; }
702 else if ( result == 0 ) { ndraw++; }
708 if ( moves > MaxPlyBook ) { moves = MaxPlyBook; }
710 for ( ply = 0;; ply++ ) {
711 istatus = in_CSA( ptree, pr, &move, flag_nomake_move );
714 black_bnz = strcmp( pr->str_name1, "Bonanza" ) ? 0 : 1;
715 white_bnz = strcmp( pr->str_name2, "Bonanza" ) ? 0 : 1;
716 if ( ! strcmp( pr->str_name1, "Bonanza" ) )
721 else { black_bnz = 0; }
722 if ( ! strcmp( pr->str_name2, "Bonanza" ) )
727 else { white_bnz = 0; }
729 if ( istatus < 0 ) { return istatus; }
730 if ( istatus == record_resign && ! moves ) { break; }
731 if ( istatus != record_misc )
733 str_error = "internal error at book.c";
737 rep_tbl[ply].hash_key = HASH_KEY;
738 rep_tbl[ply].hand = HAND_B;
739 rep_tbl[ply].move = move;
740 for ( i = ( ply & 1 ); i < ply; i += 2 )
742 if ( rep_tbl[i].hash_key == HASH_KEY
743 && rep_tbl[i].hand == HAND_B
744 && rep_tbl[i].move == move ) { break; }
748 key = book_hash_func( ptree, &is_flip );
749 uresult = (unsigned int)( root_turn ? -1*result+1 : result+1 );
750 if ( ( root_turn == black && black_bnz )
751 || ( root_turn == white && white_bnz ) ) { uresult |= 0x4U; }
753 pcell[icell].key = key;
754 pcell[icell].result = (unsigned char)uresult;
755 pcell[icell].smove = (unsigned short)move2bm( move, root_turn,
758 if ( icell == MaxNumCell ) {
759 iret = dump_cell( pcell, icell, num_tmpfile++ );
760 if ( iret < 0 ) { return iret; }
763 if ( ! ( (icell-1) & 0x1ffff ) ) { Out( "." ); }
766 if ( pr->moves >= moves ) { break; }
768 iret = make_move_root( ptree, move, 0 );
769 if ( iret < 0 ) { return iret; }
772 if ( istatus != record_eof && istatus != record_next )
774 istatus = record_wind( pr );
775 if ( istatus < 0 ) { return istatus; }
779 iret = dump_cell( pcell, icell, num_tmpfile++ );
780 if ( iret < 0 ) { return iret; }
789 " White Bnz: %7u\n", nblack_win + nwhite_win + ndraw + ninvalid,
790 ninvalid, nblack_win, nwhite_win, ndraw, nbnz_black, nbnz_white );
797 merge_cell( record_move_t *precord_move, FILE **ppf, int num_tmpfile )
803 unsigned int book_moves, book_positions, move, size_data, size_section;
804 unsigned int max_size_section, nwin, nwin_bnz, ngame, ngame_bnz, position;
805 unsigned int u, norm;
806 int i, j, iret, ibook_section, imin, nmove;
809 for ( i = 0; i < num_tmpfile; i++ )
811 iret = read_a_cell( acell + i, ppf[i] );
812 if ( iret < 0 ) { return iret; }
815 imin = find_min_cell( acell, num_tmpfile );
816 position = BK_SIZE_INDEX * NUM_SECTION;
817 max_size_section = book_moves = book_positions = 0;
818 for ( ibook_section = 0; ibook_section < NUM_SECTION; ibook_section++ ) {
821 key = acell[imin].key;
822 i = (int)( (unsigned int)key & (unsigned int)(NUM_SECTION-1) );
823 if ( i != ibook_section || key == UINT64_MAX ) { break; }
825 nwin = nmove = nwin_bnz = ngame = ngame_bnz = precord_move[0].move = 0;
827 move = (unsigned int)acell[imin].smove;
828 for ( i = 0; precord_move[i].move && precord_move[i].move != move;
830 if ( ! precord_move[i].move )
832 precord_move[i].nwin = precord_move[i].ngame = 0;
833 precord_move[i].nwin_bnz = precord_move[i].ngame_bnz = 0;
834 precord_move[i].move = move;
835 precord_move[i+1].move = 0;
839 if ( acell[imin].result & b0010 )
841 if ( acell[imin].result & b0100 )
843 precord_move[i].nwin_bnz += 1;
846 precord_move[i].nwin += 1;
850 if ( acell[imin].result & b0100 )
852 precord_move[i].ngame_bnz += 1;
855 precord_move[i].ngame += 1;
858 iret = read_a_cell( acell + imin, ppf[imin] );
859 if ( iret < 0 ) { return iret; }
861 imin = find_min_cell( acell, num_tmpfile );
862 } while ( key == acell[imin].key );
865 while ( nmove > 1 && ngame_bnz >= 128 )
867 double max_rate, rate;
870 for ( i = 0; i < nmove; i++ )
872 rate = ( (double)precord_move[i].nwin_bnz
873 / (double)( precord_move[i].ngame_bnz + 7 ) );
874 if ( rate > max_rate ) { max_rate = rate; }
876 if ( max_rate < 0.1 ) { break; }
881 rate = ( (double)precord_move[i].nwin_bnz
882 / (double)( precord_move[i].ngame_bnz + 7 ) );
884 if ( rate > max_rate ) { i++; }
886 precord_move[i] = precord_move[nmove-1];
889 } while ( i < nmove );
894 if ( ! nmove ) { continue; }
898 if ( move_selection( precord_move + i, ngame, nwin ) ) { i++; }
900 precord_move[i] = precord_move[nmove-1];
903 } while ( i < nmove );
905 if ( ! nmove ) { continue; }
907 size_data = BK_SIZE_HEADER + BK_SIZE_MOVE * nmove;
908 if ( size_section + size_data > MAX_SIZE_SECTION
909 || size_data > UCHAR_MAX )
911 str_error = "book_section buffer overflow";
914 if ( nmove > BK_MAX_MOVE )
916 str_error = "BK_MAX_MOVE is too small";
920 /* insertion sort by nwin */
921 precord_move[nmove].nwin = 0;
922 for ( i = nmove-2; i >= 0; i-- )
924 u = precord_move[i].nwin;
925 swap = precord_move[i];
926 for ( j = i+1; precord_move[j].nwin > u; j++ )
928 precord_move[j-1] = precord_move[j];
930 precord_move[j-1] = swap;
934 for ( norm = 0, i = 0; i < nmove; i++ ) { norm += precord_move[i].nwin; }
935 dscale = (double)USHRT_MAX / (double)norm;
936 for ( norm = 0, i = 0; i < nmove; i++ )
938 u = (unsigned int)( (double)precord_move[i].nwin * dscale );
939 if ( ! u ) { u = 1U; }
940 if ( u > USHRT_MAX ) { u = USHRT_MAX; }
942 precord_move[i].nwin = u;
945 if ( norm > precord_move[0].nwin + USHRT_MAX )
947 str_error = "normalization error\n";
950 precord_move[0].nwin += USHRT_MAX - norm;
952 book_section[size_section+0] = (unsigned char)size_data;
953 *(uint64_t *)(book_section+size_section+1) = key;
955 for ( u = size_section+BK_SIZE_HEADER, i = 0; i < nmove;
956 u += BK_SIZE_MOVE, i++ )
958 *(unsigned short *)(book_section+u)
959 = (unsigned short)precord_move[i].move;
960 *(unsigned short *)(book_section+u+2)
961 = (unsigned short)precord_move[i].nwin;
965 size_section += size_data;
967 if ( fseek( pf_book, BK_SIZE_INDEX * ibook_section, SEEK_SET ) == EOF )
969 str_error = str_io_error;
972 if ( fwrite( &position, sizeof(unsigned int), 1, pf_book ) != 1 )
974 str_error = str_io_error;
977 s = (unsigned short)size_section;
978 if ( fwrite( &s, sizeof(unsigned short), 1, pf_book ) != 1 )
980 str_error = str_io_error;
983 if ( fseek( pf_book, position, SEEK_SET ) == EOF )
985 str_error = str_io_error;
988 if ( fwrite( &book_section, sizeof(unsigned char), (size_t)size_section,
989 pf_book ) != (size_t)size_section )
991 str_error = str_io_error;
995 if ( size_section > max_size_section ) { max_size_section = size_section; }
996 position += size_section;
999 Out( "Positions in the book: %u\n", book_positions );
1000 Out( "Moves in the book: %u\n", book_moves );
1001 Out( "Max. size of a section: %d\n", max_size_section );
1008 move_selection( const record_move_t *p, int ngame, int nwin )
1010 double total_win_norm, win_norm, win, game, win_move, game_move;
1012 #if defined(BK_SMALL)
1013 if ( ! p->nwin || p->ngame < 3 ) { return 0; }
1015 if ( ! p->nwin || p->ngame < 2 ) { return 0; }
1019 game = (double)ngame;
1020 win_move = (double)p->nwin;
1021 game_move = (double)p->ngame;
1023 total_win_norm = win * game_move;
1024 win_norm = win_move * game;
1025 if ( win_norm < total_win_norm * 0.85 ) { return 0; }
1032 find_min_cell( const cell_t *pcell, int num_tmpfile )
1037 for ( i = 1; i < num_tmpfile; i++ )
1039 if ( compare( pcell+imin, pcell+i ) == 1 ) { imin = i; }
1046 read_a_cell( cell_t *pcell, FILE *pf )
1048 if ( fread( &pcell->key, sizeof(uint64_t), 1, pf ) != 1 )
1052 pcell->key = UINT64_MAX;
1055 str_error = str_io_error;
1058 if ( fread( &pcell->smove, sizeof(unsigned short), 1, pf ) != 1 )
1060 str_error = str_io_error;
1063 if ( fread( &pcell->result, sizeof(unsigned char), 1, pf ) != 1 )
1065 str_error = str_io_error;
1074 examine_game( tree_t * restrict ptree, record_t *pr, int *presult,
1075 unsigned int *pmoves )
1078 int iret, istatus, is_lost, is_win;
1083 iret = record_getpos( pr, &rpos );
1084 if ( iret < 0 ) { return iret; }
1086 is_lost = is_win = 0;
1089 istatus = in_CSA( ptree, pr, NULL, flag_detect_hang );
1092 /* the game is end, however the record is invalid */
1093 if ( strstr( str_error, str_bad_record ) != NULL
1094 && ( game_status & mask_game_end ) )
1099 /* a hang-king and a double-pawn are counted as a lost game */
1100 if ( strstr( str_error, str_king_hang ) != NULL
1101 || strstr( str_error, str_double_pawn ) != NULL
1102 || strstr( str_error, str_mate_drppawn ) != NULL )
1110 /* previous move had an error, count as a won game */
1111 else if ( istatus == record_error )
1116 else if ( istatus == record_misc ) { moves++; }
1117 } while ( istatus != record_next && istatus != record_eof );
1119 if ( istatus != record_next && istatus != record_eof )
1121 istatus = record_wind( pr );
1122 if ( istatus < 0 ) { return istatus; }
1125 if ( ! ( is_lost || is_win || ( game_status & mask_game_end ) ) )
1130 if ( is_win ) { *presult = root_turn ? -1 : 1; }
1131 else if ( is_lost || ( game_status & ( flag_mated | flag_resigned ) ) )
1133 *presult = root_turn ? 1 : -1;
1135 else { *presult = 0; }
1139 iret = record_setpos( pr, &rpos );
1140 if ( iret < 0 ) { return iret; }
1147 dump_cell( cell_t *pcell, int ncell, int num_tmpfile )
1149 char str_filename[SIZE_FILENAME];
1154 qsort( pcell, ncell, sizeof(cell_t), compare );
1156 Out( " dump", str_filename );
1157 snprintf( str_filename, SIZE_FILENAME, "tmp%02d.bin", num_tmpfile );
1158 pf = file_open( str_filename, "wb" );
1159 if ( pf == NULL ) { return -2; }
1161 for ( i = 0; i < ncell; i++ )
1163 if ( fwrite( &pcell[i].key, sizeof(uint64_t), 1, pf ) != 1 )
1166 str_error = str_io_error;
1169 if ( fwrite( &pcell[i].smove, sizeof(unsigned short), 1, pf ) != 1 )
1172 str_error = str_io_error;
1175 if ( fwrite( &pcell[i].result, sizeof(unsigned char), 1, pf ) != 1 )
1178 str_error = str_io_error;
1183 iret = file_close( pf );
1184 if ( iret < 0 ) { return iret; }
1186 Out( " done (%s)\n", str_filename );
1192 static int CONV_CDECL
1193 compare( const void * p1, const void * p2 )
1195 const cell_t * pcell1 = p1;
1196 const cell_t * pcell2 = p2;
1197 unsigned int u1, u2;
1199 u1 = (unsigned int)pcell1->key & (unsigned int)(NUM_SECTION-1);
1200 u2 = (unsigned int)pcell2->key & (unsigned int)(NUM_SECTION-1);
1202 if ( u1 < u2 ) { return -1; }
1203 if ( u1 > u2 ) { return 1; }
1204 if ( pcell1->key < pcell2->key ) { return -1; }
1205 if ( pcell1->key > pcell2->key ) { return 1; }
1212 move2bm( unsigned int move, int turn, int is_flip )
1219 ft.from = I2From(move);
1220 is_promote = I2IsPromote(move);
1222 ft = flip_ft( ft, turn, is_flip );
1224 bmove = (unsigned int)( is_promote | From2Move(ft.from) | ft.to );
1230 #endif /* no MINIMUM */