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 ) ) )
146 Out( SIGN " move freq\n" );
147 OutCsaShogi( "info" );
148 for ( i = 0; i < moves; i++ )
152 dscore = (double)abook_move[i].freq / (double)USHRT_MAX;
153 move = bm2move( ptree, (unsigned int)abook_move[i].smove, is_flip );
154 str = str_CSA_move( move );
156 Out( " %c %s %5.1f\n", i == j ? '*' : ' ', str, dscore * 100.0 );
157 OutCsaShogi( " %s(%.0f%%)", str, dscore * 100.0 );
162 move = bm2move( ptree, (unsigned int)abook_move[j].smove, is_flip );
163 if ( ! is_move_valid( ptree, move, root_turn ) )
165 out_warning( "BAD BOOK MOVE!! " );
169 ply = record_game.moves;
170 if ( game_status & flag_pondering ) { ply++; }
171 if ( ply < HASH_REG_HIST_LEN )
173 history_book_learn[ ply ].key_book = key;
174 history_book_learn[ ply ].move_probed = move;
175 history_book_learn[ ply ].key_probed = (unsigned int)HASH_KEY;
176 history_book_learn[ ply ].hand_probed = HAND_B;
177 history_book_learn[ ply ].data = (unsigned int)is_flip << 30;
178 if ( game_status & flag_narrow_book )
180 history_book_learn[ ply ].data |= 1U << 29;
184 ptree->current_move[1] = move;
191 book_read( uint64_t key, book_move_t *pbook_move, unsigned int *pposition )
194 const unsigned char *p;
195 unsigned int position, size_section, size, u;
196 int ibook_section, moves;
199 ibook_section = (int)( (unsigned int)key & (unsigned int)( NUM_SECTION-1 ) );
201 if ( fseek( pf_book, BK_SIZE_INDEX*ibook_section, SEEK_SET ) == EOF )
203 str_error = str_io_error;
207 if ( fread( &position, sizeof(int), 1, pf_book ) != 1 )
209 str_error = str_io_error;
213 if ( fread( &s, sizeof(unsigned short), 1, pf_book ) != 1 )
215 str_error = str_io_error;
218 size_section = (unsigned int)s;
219 if ( size_section > MAX_SIZE_SECTION )
221 str_error = str_book_error;
225 if ( fseek( pf_book, (long)position, SEEK_SET ) == EOF )
227 str_error = str_io_error;
230 if ( fread( book_section, sizeof(unsigned char), (size_t)size_section,
231 pf_book ) != (size_t)size_section )
233 str_error = str_io_error;
239 *pposition = position;
240 while ( book_section + size_section > p )
242 size = (unsigned int)p[0];
243 book_key = *(uint64_t *)( p + 1 );
244 if ( book_key == key ) { break; }
248 if ( book_section + size_section <= p ) { return 0; }
250 for ( moves = 0, u = BK_SIZE_HEADER; u < size; moves++, u += BK_SIZE_MOVE )
252 pbook_move[moves].smove = *(unsigned short *)(p+u+0);
253 pbook_move[moves].freq = *(unsigned short *)(p+u+2);
261 flip_ft( ft_t ft, int turn, int is_flip )
263 int ito_rank, ito_file, ifrom_rank, ifrom_file;
265 ito_rank = airank[ft.to];
266 ito_file = aifile[ft.to];
267 if ( ft.from < nsquare )
269 ifrom_rank = airank[ft.from];
270 ifrom_file = aifile[ft.from];
272 else { ifrom_rank = ifrom_file = 0; }
276 ito_rank = rank9 - ito_rank;
277 ito_file = file9 - ito_file;
278 if ( ft.from < nsquare )
280 ifrom_rank = rank9 - ifrom_rank;
281 ifrom_file = file9 - ifrom_file;
287 ito_file = file9 - ito_file;
288 if ( ft.from < nsquare ) { ifrom_file = file9 - ifrom_file; }
291 ft.to = ito_rank * nfile + ito_file;
292 if ( ft.from < nsquare ) { ft.from = ifrom_rank * nfile + ifrom_file; }
299 bm2move( const tree_t * restrict ptree, unsigned int bmove, int is_flip )
306 ft.from = I2From(bmove);
307 ft = flip_ft( ft, root_turn, is_flip );
308 is_promote = I2IsPromote(bmove);
310 move = (unsigned int)( is_promote | From2Move(ft.from) | ft.to );
311 if ( ft.from >= nsquare ) { return move; }
315 move |= Cap2Move(BOARD[ft.to]);
316 move |= Piece2Move(-BOARD[ft.from]);
319 move |= Cap2Move(-BOARD[ft.to]);
320 move |= Piece2Move(BOARD[ft.from]);
328 book_hash_func( const tree_t * restrict ptree, int *pis_flip )
330 uint64_t key, key_flip;
332 int i, iflip, irank, ifile, piece;
335 hand = root_turn ? HAND_W : HAND_B;
336 i = I2HandPawn(hand); if ( i ) { key ^= b_hand_pawn_rand[i-1]; }
337 i = I2HandLance(hand); if ( i ) { key ^= b_hand_lance_rand[i-1]; }
338 i = I2HandKnight(hand); if ( i ) { key ^= b_hand_knight_rand[i-1]; }
339 i = I2HandSilver(hand); if ( i ) { key ^= b_hand_silver_rand[i-1]; }
340 i = I2HandGold(hand); if ( i ) { key ^= b_hand_gold_rand[i-1]; }
341 i = I2HandBishop(hand); if ( i ) { key ^= b_hand_bishop_rand[i-1]; }
342 i = I2HandRook(hand); if ( i ) { key ^= b_hand_rook_rand[i-1]; }
344 hand = root_turn ? HAND_B : HAND_W;
345 i = I2HandPawn(hand); if ( i ) { key ^= w_hand_pawn_rand[i-1]; }
346 i = I2HandLance(hand); if ( i ) { key ^= w_hand_lance_rand[i-1]; }
347 i = I2HandKnight(hand); if ( i ) { key ^= w_hand_knight_rand[i-1]; }
348 i = I2HandSilver(hand); if ( i ) { key ^= w_hand_silver_rand[i-1]; }
349 i = I2HandGold(hand); if ( i ) { key ^= w_hand_gold_rand[i-1]; }
350 i = I2HandBishop(hand); if ( i ) { key ^= w_hand_bishop_rand[i-1]; }
351 i = I2HandRook(hand); if ( i ) { key ^= w_hand_rook_rand[i-1]; }
355 for ( irank = rank1; irank <= rank9; irank++ )
356 for ( ifile = file1; ifile <= file9; ifile++ )
360 i = ( rank9 - irank ) * nfile + file9 - ifile;
361 iflip = ( rank9 - irank ) * nfile + ifile;
362 piece = -(int)BOARD[nsquare-i-1];
365 i = irank * nfile + ifile;
366 iflip = irank * nfile + file9 - ifile;
367 piece = (int)BOARD[i];
370 #define Foo(t_pc) key ^= (t_pc ## _rand)[i]; \
371 key_flip ^= (t_pc ## _rand)[iflip];
374 case pawn: Foo( b_pawn ); break;
375 case lance: Foo( b_lance ); break;
376 case knight: Foo( b_knight ); break;
377 case silver: Foo( b_silver ); break;
378 case gold: Foo( b_gold ); break;
379 case bishop: Foo( b_bishop ); break;
380 case rook: Foo( b_rook ); break;
381 case king: Foo( b_king ); break;
382 case pro_pawn: Foo( b_pro_pawn ); break;
383 case pro_lance: Foo( b_pro_lance ); break;
384 case pro_knight: Foo( b_pro_knight ); break;
385 case pro_silver: Foo( b_pro_silver ); break;
386 case horse: Foo( b_horse ); break;
387 case dragon: Foo( b_dragon ); break;
388 case -pawn: Foo( w_pawn ); break;
389 case -lance: Foo( w_lance ); break;
390 case -knight: Foo( w_knight ); break;
391 case -silver: Foo( w_silver ); break;
392 case -gold: Foo( w_gold ); break;
393 case -bishop: Foo( w_bishop ); break;
394 case -rook: Foo( w_rook ); break;
395 case -king: Foo( w_king ); break;
396 case -pro_pawn: Foo( w_pro_pawn ); break;
397 case -pro_lance: Foo( w_pro_lance ); break;
398 case -pro_knight: Foo( w_pro_knight ); break;
399 case -pro_silver: Foo( w_pro_silver ); break;
400 case -horse: Foo( w_horse ); break;
401 case -dragon: Foo( w_dragon ); break;
406 if ( key > key_flip )
411 else { *pis_flip = 0; }
418 normalize_book_move( book_move_t * restrict pbook_move, int moves )
422 unsigned int u, norm;
425 /* insertion sort by nwin */
426 pbook_move[moves].freq = 0;
427 for ( i = moves-2; i >= 0; i-- )
429 u = pbook_move[i].freq;
430 swap = pbook_move[i];
431 for ( j = i+1; pbook_move[j].freq > u; j++ )
433 pbook_move[j-1] = pbook_move[j];
435 pbook_move[j-1] = swap;
439 for ( norm = 0, i = 0; i < moves; i++ ) { norm += pbook_move[i].freq; }
440 dscale = (double)USHRT_MAX / (double)norm;
441 for ( norm = 0, i = 0; i < moves; i++ )
443 u = (unsigned int)( (double)pbook_move[i].freq * dscale );
444 if ( ! u ) { u = 1U; }
445 if ( u > USHRT_MAX ) { u = USHRT_MAX; }
447 pbook_move[i].freq = (unsigned short)u;
450 if ( norm > (unsigned int)pbook_move[0].freq + USHRT_MAX )
452 str_error = "normalization error";
457 = (unsigned short)( pbook_move[0].freq + USHRT_MAX - norm );
463 #if ! defined(MINIMUM)
465 #define MaxNumCell 0x400000
466 #if defined(BK_SMALL)
467 # define MaxPlyBook 64
469 # define MaxPlyBook 128
473 unsigned int nwin, ngame, nwin_bnz, ngame_bnz, move;
478 unsigned short smove;
479 unsigned char result;
482 static unsigned int move2bm( unsigned int move, int turn, int is_flip );
483 static int find_min_cell( const cell_t *pcell, int ntemp );
484 static int read_a_cell( cell_t *pcell, FILE *pf );
485 static int CONV_CDECL compare( const void * p1, const void *p2 );
486 static int dump_cell( cell_t *pcell, int ncell, int num_tmpfile );
487 static int examine_game( tree_t * restrict ptree, record_t *pr,
488 int *presult, unsigned int *pmoves );
489 static int move_selection( const record_move_t *p, int ngame, int nwin );
490 static int make_cell_csa( tree_t * restrict ptree, record_t *pr,
491 cell_t *pcell, int num_tmpfile );
492 static int merge_cell( record_move_t *precord_move, FILE **ppf,
494 static int read_anti_book( tree_t * restrict ptree, record_t * pr );
497 book_create( tree_t * restrict ptree )
501 char str_filename[SIZE_FILENAME];
502 record_move_t *precord_move;
504 int iret, num_tmpfile, i, j;
509 pcell = memory_alloc( sizeof(cell_t) * MaxNumCell );
510 if ( pcell == NULL ) { return -2; }
512 Out("\n [book.csa]\n");
514 iret = record_open( &record, "book.csa", mode_read, NULL, NULL );
515 if ( iret < 0 ) { return iret; }
517 num_tmpfile = make_cell_csa( ptree, &record, pcell, num_tmpfile );
518 if ( num_tmpfile < 0 )
520 memory_free( pcell );
521 record_close( &record );
525 iret = record_close( &record );
528 memory_free( pcell );
532 memory_free( pcell );
536 str_error = "No book data";
540 if ( num_tmpfile > 100 )
542 str_error = "Number of tmp??.bin files are too large.";
547 if ( iret < 0 ) { return iret; }
549 pf_book = file_open( str_book, "wb" );
550 if ( pf_book == NULL ) { return -2; }
552 precord_move = memory_alloc( sizeof(record_move_t) * (MAX_LEGAL_MOVES+1) );
553 if ( precord_move == NULL ) { return -2; }
555 for ( i = 0; i < num_tmpfile; i++ )
557 snprintf( str_filename, SIZE_FILENAME, "tmp%02d.bin", i );
558 ppf[i] = file_open( str_filename, "rb" );
559 if ( ppf[i] == NULL )
561 memory_free( precord_move );
562 file_close( pf_book );
563 for ( j = 0; j < i; j++ ) { file_close( ppf[j] ); }
568 iret = merge_cell( precord_move, ppf, num_tmpfile );
571 memory_free( precord_move );
572 file_close( pf_book );
573 for ( i = 0; i < num_tmpfile; i++ ) { file_close( ppf[i] ); }
577 memory_free( precord_move );
580 if ( iret < 0 ) { return iret; }
583 iret = record_open( &record, "book_anti.csa", mode_read, NULL, NULL );
584 if ( iret < 0 ) { return iret; }
586 iret = read_anti_book( ptree, &record );
589 record_close( &record );
594 return record_close( &record );
599 read_anti_book( tree_t * restrict ptree, record_t * pr )
602 book_move_t abook_move[ BK_MAX_MOVE+1 ];
604 unsigned int move, position, bm, umoves;
605 int iret, result, istatus, is_flip, i, moves;
609 istatus = examine_game( ptree, pr, &result, &umoves );
610 if ( istatus < 0 ) { return istatus; }
613 str_error = "no result in book_anti.csa";
617 while ( pr->moves < umoves-1U )
619 istatus = in_CSA( ptree, pr, NULL, 0 );
620 if ( istatus != record_misc )
622 str_error = "internal error at book.c";
627 istatus = in_CSA( ptree, pr, &move, flag_nomake_move );
628 if ( istatus < 0 ) { return istatus; }
630 key = book_hash_func( ptree, &is_flip );
632 moves = book_read( key, abook_move, &position );
633 if ( moves < 0 ) { return moves; }
635 bm = move2bm( move, root_turn, is_flip );
636 for ( i = 0; i < moves; i++ )
638 if ( bm == abook_move[i].smove ) { break; }
643 out_board( ptree, stdout, 0, 0 );
644 printf( "%s is not found in the book\n\n", str_CSA_move(move) );
647 abook_move[i].freq = 0;
649 iret = normalize_book_move( abook_move, moves );
650 if ( iret < 0 ) { return iret; }
652 for ( i = 0; i < moves; i++ )
654 *(unsigned short *)( book_section + i*BK_SIZE_MOVE )
655 = abook_move[i].smove;
656 *(unsigned short *)( book_section + i*BK_SIZE_MOVE + 2 )
657 = abook_move[i].freq;
659 size = (size_t)( moves * BK_SIZE_MOVE );
660 if ( fseek( pf_book, (long)(position+BK_SIZE_HEADER), SEEK_SET ) == EOF
661 || fwrite( book_section, sizeof(unsigned char),
662 size, pf_book ) != size )
664 str_error = str_io_error;
668 out_board( ptree, stdout, 0, 0 );
669 printf( "%s is discarded\n\n", str_CSA_move(move) );
672 if ( istatus != record_eof && istatus != record_next )
674 istatus = record_wind( pr );
675 if ( istatus < 0 ) { return istatus; }
677 } while ( istatus != record_eof );
684 make_cell_csa( tree_t * restrict ptree, record_t *pr, cell_t *pcell,
689 unsigned int hand, move;
690 } rep_tbl[MaxPlyBook+1];
692 unsigned int nwhite_win, nblack_win, ndraw, ninvalid, nbnz_black, nbnz_white;
693 unsigned int move, moves, uresult;
694 int icell, result, is_flip, iret, istatus, ply, i, black_bnz, white_bnz;
696 nwhite_win = nblack_win = ndraw = ninvalid = nbnz_white = nbnz_black = 0;
697 icell = black_bnz = white_bnz = 0;
698 istatus = record_next;
700 while ( istatus != record_eof ) {
702 istatus = examine_game( ptree, pr, &result, &moves );
703 if ( istatus < 0 ) { return istatus; }
705 if ( result == -1 ) { nwhite_win++; }
706 else if ( result == 1 ) { nblack_win++; }
707 else if ( result == 0 ) { ndraw++; }
713 if ( moves > MaxPlyBook ) { moves = MaxPlyBook; }
715 for ( ply = 0;; ply++ ) {
716 istatus = in_CSA( ptree, pr, &move, flag_nomake_move );
719 black_bnz = strcmp( pr->str_name1, "Bonanza" ) ? 0 : 1;
720 white_bnz = strcmp( pr->str_name2, "Bonanza" ) ? 0 : 1;
721 if ( ! strcmp( pr->str_name1, "Bonanza" ) )
726 else { black_bnz = 0; }
727 if ( ! strcmp( pr->str_name2, "Bonanza" ) )
732 else { white_bnz = 0; }
734 if ( istatus < 0 ) { return istatus; }
735 if ( istatus == record_resign && ! moves ) { break; }
736 if ( istatus != record_misc )
738 str_error = "internal error at book.c";
742 rep_tbl[ply].hash_key = HASH_KEY;
743 rep_tbl[ply].hand = HAND_B;
744 rep_tbl[ply].move = move;
745 for ( i = ( ply & 1 ); i < ply; i += 2 )
747 if ( rep_tbl[i].hash_key == HASH_KEY
748 && rep_tbl[i].hand == HAND_B
749 && rep_tbl[i].move == move ) { break; }
753 key = book_hash_func( ptree, &is_flip );
754 uresult = (unsigned int)( root_turn ? -1*result+1 : result+1 );
755 if ( ( root_turn == black && black_bnz )
756 || ( root_turn == white && white_bnz ) ) { uresult |= 0x4U; }
758 pcell[icell].key = key;
759 pcell[icell].result = (unsigned char)uresult;
760 pcell[icell].smove = (unsigned short)move2bm( move, root_turn,
763 if ( icell == MaxNumCell ) {
764 iret = dump_cell( pcell, icell, num_tmpfile++ );
765 if ( iret < 0 ) { return iret; }
768 if ( ! ( (icell-1) & 0x1ffff ) ) { Out( "." ); }
771 if ( pr->moves >= moves ) { break; }
773 iret = make_move_root( ptree, move, 0 );
774 if ( iret < 0 ) { return iret; }
777 if ( istatus != record_eof && istatus != record_next )
779 istatus = record_wind( pr );
780 if ( istatus < 0 ) { return istatus; }
784 iret = dump_cell( pcell, icell, num_tmpfile++ );
785 if ( iret < 0 ) { return iret; }
794 " White Bnz: %7u\n", nblack_win + nwhite_win + ndraw + ninvalid,
795 ninvalid, nblack_win, nwhite_win, ndraw, nbnz_black, nbnz_white );
802 merge_cell( record_move_t *precord_move, FILE **ppf, int num_tmpfile )
808 unsigned int book_moves, book_positions, move, size_data, size_section;
809 unsigned int max_size_section, nwin, nwin_bnz, ngame, ngame_bnz, position;
810 unsigned int u, norm;
811 int i, j, iret, ibook_section, imin, nmove;
814 for ( i = 0; i < num_tmpfile; i++ )
816 iret = read_a_cell( acell + i, ppf[i] );
817 if ( iret < 0 ) { return iret; }
820 imin = find_min_cell( acell, num_tmpfile );
821 position = BK_SIZE_INDEX * NUM_SECTION;
822 max_size_section = book_moves = book_positions = 0;
823 for ( ibook_section = 0; ibook_section < NUM_SECTION; ibook_section++ ) {
826 key = acell[imin].key;
827 i = (int)( (unsigned int)key & (unsigned int)(NUM_SECTION-1) );
828 if ( i != ibook_section || key == UINT64_MAX ) { break; }
830 nwin = nmove = nwin_bnz = ngame = ngame_bnz = precord_move[0].move = 0;
832 move = (unsigned int)acell[imin].smove;
833 for ( i = 0; precord_move[i].move && precord_move[i].move != move;
835 if ( ! precord_move[i].move )
837 precord_move[i].nwin = precord_move[i].ngame = 0;
838 precord_move[i].nwin_bnz = precord_move[i].ngame_bnz = 0;
839 precord_move[i].move = move;
840 precord_move[i+1].move = 0;
844 if ( acell[imin].result & b0010 )
846 if ( acell[imin].result & b0100 )
848 precord_move[i].nwin_bnz += 1;
851 precord_move[i].nwin += 1;
855 if ( acell[imin].result & b0100 )
857 precord_move[i].ngame_bnz += 1;
860 precord_move[i].ngame += 1;
863 iret = read_a_cell( acell + imin, ppf[imin] );
864 if ( iret < 0 ) { return iret; }
866 imin = find_min_cell( acell, num_tmpfile );
867 } while ( key == acell[imin].key );
870 while ( nmove > 1 && ngame_bnz >= 128 )
872 double max_rate, rate;
875 for ( i = 0; i < nmove; i++ )
877 rate = ( (double)precord_move[i].nwin_bnz
878 / (double)( precord_move[i].ngame_bnz + 7 ) );
879 if ( rate > max_rate ) { max_rate = rate; }
881 if ( max_rate < 0.1 ) { break; }
886 rate = ( (double)precord_move[i].nwin_bnz
887 / (double)( precord_move[i].ngame_bnz + 7 ) );
889 if ( rate > max_rate ) { i++; }
891 precord_move[i] = precord_move[nmove-1];
894 } while ( i < nmove );
899 if ( ! nmove ) { continue; }
903 if ( move_selection( precord_move + i, ngame, nwin ) ) { i++; }
905 precord_move[i] = precord_move[nmove-1];
908 } while ( i < nmove );
910 if ( ! nmove ) { continue; }
912 size_data = BK_SIZE_HEADER + BK_SIZE_MOVE * nmove;
913 if ( size_section + size_data > MAX_SIZE_SECTION
914 || size_data > UCHAR_MAX )
916 str_error = "book_section buffer overflow";
919 if ( nmove > BK_MAX_MOVE )
921 str_error = "BK_MAX_MOVE is too small";
925 /* insertion sort by nwin */
926 precord_move[nmove].nwin = 0;
927 for ( i = nmove-2; i >= 0; i-- )
929 u = precord_move[i].nwin;
930 swap = precord_move[i];
931 for ( j = i+1; precord_move[j].nwin > u; j++ )
933 precord_move[j-1] = precord_move[j];
935 precord_move[j-1] = swap;
939 for ( norm = 0, i = 0; i < nmove; i++ ) { norm += precord_move[i].nwin; }
940 dscale = (double)USHRT_MAX / (double)norm;
941 for ( norm = 0, i = 0; i < nmove; i++ )
943 u = (unsigned int)( (double)precord_move[i].nwin * dscale );
944 if ( ! u ) { u = 1U; }
945 if ( u > USHRT_MAX ) { u = USHRT_MAX; }
947 precord_move[i].nwin = u;
950 if ( norm > precord_move[0].nwin + USHRT_MAX )
952 str_error = "normalization error\n";
955 precord_move[0].nwin += USHRT_MAX - norm;
957 book_section[size_section+0] = (unsigned char)size_data;
958 *(uint64_t *)(book_section+size_section+1) = key;
960 for ( u = size_section+BK_SIZE_HEADER, i = 0; i < nmove;
961 u += BK_SIZE_MOVE, i++ )
963 *(unsigned short *)(book_section+u)
964 = (unsigned short)precord_move[i].move;
965 *(unsigned short *)(book_section+u+2)
966 = (unsigned short)precord_move[i].nwin;
970 size_section += size_data;
972 if ( fseek( pf_book, BK_SIZE_INDEX * ibook_section, SEEK_SET ) == EOF )
974 str_error = str_io_error;
977 if ( fwrite( &position, sizeof(unsigned int), 1, pf_book ) != 1 )
979 str_error = str_io_error;
982 s = (unsigned short)size_section;
983 if ( fwrite( &s, sizeof(unsigned short), 1, pf_book ) != 1 )
985 str_error = str_io_error;
988 if ( fseek( pf_book, position, SEEK_SET ) == EOF )
990 str_error = str_io_error;
993 if ( fwrite( &book_section, sizeof(unsigned char), (size_t)size_section,
994 pf_book ) != (size_t)size_section )
996 str_error = str_io_error;
1000 if ( size_section > max_size_section ) { max_size_section = size_section; }
1001 position += size_section;
1004 Out( "Positions in the book: %u\n", book_positions );
1005 Out( "Moves in the book: %u\n", book_moves );
1006 Out( "Max. size of a section: %d\n", max_size_section );
1013 move_selection( const record_move_t *p, int ngame, int nwin )
1015 double total_win_norm, win_norm, win, game, win_move, game_move;
1017 #if defined(BK_SMALL)
1018 if ( ! p->nwin || p->ngame < 3 ) { return 0; }
1020 if ( ! p->nwin || p->ngame < 2 ) { return 0; }
1024 game = (double)ngame;
1025 win_move = (double)p->nwin;
1026 game_move = (double)p->ngame;
1028 total_win_norm = win * game_move;
1029 win_norm = win_move * game;
1030 if ( win_norm < total_win_norm * 0.85 ) { return 0; }
1037 find_min_cell( const cell_t *pcell, int num_tmpfile )
1042 for ( i = 1; i < num_tmpfile; i++ )
1044 if ( compare( pcell+imin, pcell+i ) == 1 ) { imin = i; }
1051 read_a_cell( cell_t *pcell, FILE *pf )
1053 if ( fread( &pcell->key, sizeof(uint64_t), 1, pf ) != 1 )
1057 pcell->key = UINT64_MAX;
1060 str_error = str_io_error;
1063 if ( fread( &pcell->smove, sizeof(unsigned short), 1, pf ) != 1 )
1065 str_error = str_io_error;
1068 if ( fread( &pcell->result, sizeof(unsigned char), 1, pf ) != 1 )
1070 str_error = str_io_error;
1079 examine_game( tree_t * restrict ptree, record_t *pr, int *presult,
1080 unsigned int *pmoves )
1083 int iret, istatus, is_lost, is_win;
1088 iret = record_getpos( pr, &rpos );
1089 if ( iret < 0 ) { return iret; }
1091 is_lost = is_win = 0;
1094 istatus = in_CSA( ptree, pr, NULL, flag_detect_hang );
1097 /* the game is end, however the record is invalid */
1098 if ( strstr( str_error, str_bad_record ) != NULL
1099 && ( game_status & mask_game_end ) )
1104 /* a hang-king and a double-pawn are counted as a lost game */
1105 if ( strstr( str_error, str_king_hang ) != NULL
1106 || strstr( str_error, str_double_pawn ) != NULL
1107 || strstr( str_error, str_mate_drppawn ) != NULL )
1115 /* previous move had an error, count as a won game */
1116 else if ( istatus == record_error )
1121 else if ( istatus == record_misc ) { moves++; }
1122 } while ( istatus != record_next && istatus != record_eof );
1124 if ( istatus != record_next && istatus != record_eof )
1126 istatus = record_wind( pr );
1127 if ( istatus < 0 ) { return istatus; }
1130 if ( ! ( is_lost || is_win || ( game_status & mask_game_end ) ) )
1135 if ( is_win ) { *presult = root_turn ? -1 : 1; }
1136 else if ( is_lost || ( game_status & ( flag_mated | flag_resigned ) ) )
1138 *presult = root_turn ? 1 : -1;
1140 else { *presult = 0; }
1144 iret = record_setpos( pr, &rpos );
1145 if ( iret < 0 ) { return iret; }
1152 dump_cell( cell_t *pcell, int ncell, int num_tmpfile )
1154 char str_filename[SIZE_FILENAME];
1159 qsort( pcell, ncell, sizeof(cell_t), compare );
1161 Out( " dump", str_filename );
1162 snprintf( str_filename, SIZE_FILENAME, "tmp%02d.bin", num_tmpfile );
1163 pf = file_open( str_filename, "wb" );
1164 if ( pf == NULL ) { return -2; }
1166 for ( i = 0; i < ncell; i++ )
1168 if ( fwrite( &pcell[i].key, sizeof(uint64_t), 1, pf ) != 1 )
1171 str_error = str_io_error;
1174 if ( fwrite( &pcell[i].smove, sizeof(unsigned short), 1, pf ) != 1 )
1177 str_error = str_io_error;
1180 if ( fwrite( &pcell[i].result, sizeof(unsigned char), 1, pf ) != 1 )
1183 str_error = str_io_error;
1188 iret = file_close( pf );
1189 if ( iret < 0 ) { return iret; }
1191 Out( " done (%s)\n", str_filename );
1197 static int CONV_CDECL
1198 compare( const void * p1, const void * p2 )
1200 const cell_t * pcell1 = p1;
1201 const cell_t * pcell2 = p2;
1202 unsigned int u1, u2;
1204 u1 = (unsigned int)pcell1->key & (unsigned int)(NUM_SECTION-1);
1205 u2 = (unsigned int)pcell2->key & (unsigned int)(NUM_SECTION-1);
1207 if ( u1 < u2 ) { return -1; }
1208 if ( u1 > u2 ) { return 1; }
1209 if ( pcell1->key < pcell2->key ) { return -1; }
1210 if ( pcell1->key > pcell2->key ) { return 1; }
1217 move2bm( unsigned int move, int turn, int is_flip )
1224 ft.from = I2From(move);
1225 is_promote = I2IsPromote(move);
1227 ft = flip_ft( ft, turn, is_flip );
1229 bmove = (unsigned int)( is_promote | From2Move(ft.from) | ft.to );
1235 #endif /* no MINIMUM */