7 static int CONV eval_supe( unsigned int hand_current, unsigned int hand_hash,
8 int turn_current, int turn_hash,
9 int * restrict pvalue_hash,
10 int * restrict ptype_hash );
13 ini_trans_table( void )
16 unsigned int ntrans_table;
18 ntrans_table = 1U << log2_ntrans_table;
19 size = sizeof( trans_table_t ) * ntrans_table + 15U;
20 ptrans_table_orig = memory_alloc( size );
21 if ( ptrans_table_orig == NULL ) { return -1; }
22 ptrans_table = (trans_table_t *)( ((ptrdiff_t)ptrans_table_orig+15)
24 hash_mask = ntrans_table - 1;
25 Out( "Trans. Table Entries = %dK (%dMB)\n",
26 ( ntrans_table * 3U ) / 1024U, size / (1024U * 1024U ) );
28 return clear_trans_table();
32 #define Foo( PIECE, piece ) bb = BB_B ## PIECE; \
33 while( BBTest(bb) ) { \
34 sq = FirstOne( bb ); \
36 key ^= ( b_ ## piece ## _rand )[sq]; \
39 while( BBTest(bb) ) { \
40 sq = FirstOne( bb ); \
42 key ^= ( w_ ## piece ## _rand )[sq]; \
46 hash_func( const tree_t * restrict ptree )
52 key ^= b_king_rand[SQ_BKING];
53 key ^= w_king_rand[SQ_WKING];
57 Foo( KNIGHT, knight );
58 Foo( SILVER, silver );
60 Foo( BISHOP, bishop );
62 Foo( PRO_PAWN, pro_pawn );
63 Foo( PRO_LANCE, pro_lance );
64 Foo( PRO_KNIGHT, pro_knight );
65 Foo( PRO_SILVER, pro_silver );
67 Foo( DRAGON, dragon );
89 hash_store( const tree_t * restrict ptree, int ply, int depth, int turn,
90 int value_type, int value, unsigned int move,
91 unsigned int state_node )
93 uint64_t word1, word2, hash_word1, hash_word2;
94 unsigned int index, slot;
95 int depth_hash, age_hash;
97 #if ! defined(MINIMUM)
98 if ( game_status & flag_learning ) { return; }
100 assert( depth <= 0xff );
102 if ( depth < 0 ) { depth = 0; }
103 if ( abs(value) > score_max_eval )
105 if ( abs(value) > score_mate1ply ) { return; }
106 if ( value > 0 ) { value += ply-1; }
107 else { value -= ply-1; }
108 #if ! defined(MINIMUM)
109 if ( abs(value) > score_mate1ply )
111 out_warning( "A stored hash value is out of bounce!" );
115 word2 = ( ( HASH_KEY & ~(uint64_t)0x7fU )
116 | (uint64_t)( (turn<<6) | ( state_node & node_mate_threat )
117 | (value_type<<3) | trans_table_age ) );
118 word1 = ( ( (uint64_t)( depth<<16 | (value+32768) ) << 40 )
119 | ( (uint64_t)( move & 0x7ffffU ) << 21 )
122 index = (unsigned int)HASH_KEY & hash_mask;
123 hash_word1 = ptrans_table[index].prefer.word1;
124 hash_word2 = ptrans_table[index].prefer.word2;
125 SignKey( hash_word2, hash_word1 );
126 age_hash = (int)((unsigned int)(hash_word2 ) & 0x07U);
127 depth_hash = (int)((unsigned int)(hash_word1>>56) & 0xffU);
129 SignKey( word2, word1 );
131 if ( age_hash != trans_table_age || depth_hash <= depth )
133 ptrans_table[index].prefer.word1 = word1;
134 ptrans_table[index].prefer.word2 = word2;
137 slot = (unsigned int)HASH_KEY >> 31;
138 ptrans_table[index].always[slot].word1 = word1;
139 ptrans_table[index].always[slot].word2 = word2;
145 hash_store_pv( const tree_t * restrict ptree, unsigned int move, int turn )
147 uint64_t key_turn_pv, word1, word2;
150 key_turn_pv = ( HASH_KEY & ~(uint64_t)0x7fU ) | (unsigned int)( turn << 6 );
151 index = (unsigned int)HASH_KEY & hash_mask;
153 word1 = ptrans_table[index].prefer.word1;
154 word2 = ptrans_table[index].prefer.word2;
155 SignKey( word2, word1 );
157 if ( ( (unsigned int)word1 & 0x1fffffU ) == HAND_B
158 && ( word2 & ~(uint64_t)0x3fU ) == key_turn_pv )
160 if ( ( (unsigned int)(word1>>21) & 0x7ffffU ) != ( move & 0x7ffffU ) )
162 word1 &= ~((uint64_t)0x7ffffU << 21);
163 word1 |= (uint64_t)( move & 0x7ffffU ) << 21;
164 word2 &= ~((uint64_t)0x3U << 3);
165 SignKey( word2, word1 );
166 ptrans_table[index].prefer.word1 = word1;
167 ptrans_table[index].prefer.word2 = word2;
173 slot = (unsigned int)HASH_KEY >> 31;
174 word1 = ptrans_table[index].always[slot].word1;
175 word2 = ptrans_table[index].always[slot].word2;
176 SignKey( word2, word1 );
177 if ( ( (unsigned int)word1 & 0x1fffffU ) == HAND_B
178 && ( word2 & ~(uint64_t)0x3fU ) == key_turn_pv )
180 if ( ( (unsigned int)(word1>>21) & 0x7ffffU )
181 != ( move & 0x7ffffU ) )
183 word1 &= ~((uint64_t)0x7ffffU << 21);
184 word1 |= (uint64_t)( move & 0x7ffffU ) << 21;
185 word2 &= ~((uint64_t)0x3U << 3);
186 SignKey( word2, word1 );
187 ptrans_table[index].always[slot].word1 = word1;
188 ptrans_table[index].always[slot].word2 = word2;
192 word1 = (uint64_t)32768U << 40;
193 word1 |= (uint64_t)( move & 0x7ffffU ) << 21;
195 word2 = key_turn_pv | trans_table_age;
196 SignKey( word2, word1 );
197 ptrans_table[index].prefer.word1 = word1;
198 ptrans_table[index].prefer.word2 = word2;
205 hash_probe( tree_t * restrict ptree, int ply, int depth_current,
206 int turn_current, int alpha, int beta, unsigned int *pstate_node )
208 uint64_t word1, word2, key_current, key_hash;
209 unsigned int hand_hash, move_hash, move_supe, slot, utemp;
210 unsigned int state_node_hash, index;
211 int null_depth, value_hash, ifrom;
212 int turn_hash, depth_hash, type_hash, is_superior;
214 ptree->ntrans_probe++;
217 if ( depth_current < 0 ) { depth_current = 0; }
218 null_depth = NullDepth( depth_current );
219 if ( null_depth < PLY_INC ) { null_depth = 0; }
221 key_current = HASH_KEY & ~(uint64_t)0x7fU;
223 index = (unsigned int)HASH_KEY & hash_mask;
224 word1 = ptrans_table[index].prefer.word1;
225 word2 = ptrans_table[index].prefer.word2;
226 SignKey( word2, word1 );
227 key_hash = word2 & ~(uint64_t)0x7fU;
229 if ( key_hash == key_current ) {
231 ptree->ntrans_prefer_hit++;
233 depth_hash = (int)((unsigned int)(word1>>56) & 0x00ffU);
234 value_hash = (int)((unsigned int)(word1>>40) & 0xffffU) - 32768;
235 move_hash = (unsigned int)(word1>>21) & 0x7ffffU;
236 hand_hash = (unsigned int)word1 & 0x1fffffU;
238 utemp = (unsigned int)word2;
239 state_node_hash = utemp & node_mate_threat;
240 turn_hash = (int)((utemp>>6) & 0x1U);
241 type_hash = (int)((utemp>>3) & 0x3U);
243 if ( abs(value_hash) > score_max_eval )
245 if ( value_hash > 0 ) { value_hash -= ply-1; }
246 else { value_hash += ply-1; }
248 #if ! defined(MINIMUM)
249 if ( abs(value_hash) > score_mate1ply )
251 out_warning( "Hash value is out of bounce!!" );
256 if ( RecursionThreshold <= depth_current
257 && depth_hash < RecursionDepth(depth_current) ) { move_hash = 0; }
258 else if ( move_hash )
260 move_hash |= turn_current ? Cap2Move( BOARD[I2To(move_hash)])
261 : Cap2Move(-BOARD[I2To(move_hash)]);
264 if ( turn_hash == turn_current && hand_hash == HAND_B ) {
266 assert( ! move_hash || is_move_valid( ptree, move_hash, turn_current ) );
267 ptree->amove_hash[ply] = move_hash;
269 *pstate_node |= state_node_hash;
271 if ( value_hash <= score_max_eval ) { *pstate_node &= ~node_do_mate; }
273 if ( ( type_hash & flag_value_up_exact )
275 && null_depth <= depth_hash )
277 *pstate_node &= ~node_do_null;
280 if ( ( type_hash & flag_value_up_exact )
281 && value_hash <= alpha
282 && RecursionDepth(depth_current) <= depth_hash )
284 *pstate_node &= ~node_do_recursion;
287 if ( type_hash == value_lower
288 && beta <= value_hash
289 && ( depth_hash >= depth_current || value_hash > score_max_eval ) )
291 HASH_VALUE = value_hash;
292 ptree->ntrans_lower++;
296 if ( type_hash == value_upper
297 && value_hash <= alpha
298 && ( depth_hash >= depth_current || value_hash < -score_max_eval ) )
300 HASH_VALUE = value_hash;
301 ptree->ntrans_upper++;
305 if ( type_hash == value_exact
306 && ( depth_hash >= depth_current
307 || abs(value_hash) > score_max_eval ) )
309 HASH_VALUE = value_hash;
310 ptree->ntrans_upper++;
314 if ( ( type_hash & flag_value_low_exact )
315 && ! ptree->nsuc_check[ply]
316 && ! ptree->nsuc_check[ply-1]
317 && ( ( depth_current < 2*PLY_INC
318 && beta+EFUTIL_MG1 <= value_hash )
319 || ( depth_current < 3*PLY_INC
320 && beta+EFUTIL_MG2 <= value_hash ) ) )
323 ptree->ntrans_lower++;
329 is_superior = eval_supe( HAND_B, hand_hash, turn_current, turn_hash,
330 &value_hash, &type_hash );
332 if ( is_superior == 1 ) {
334 if ( turn_hash == turn_current ) { move_supe = move_hash; }
336 if ( type_hash & flag_value_low_exact )
338 if ( ! ptree->nsuc_check[ply]
339 && ! ptree->nsuc_check[ply-1]
340 && ( ( depth_current < 2*PLY_INC
341 && beta+EFUTIL_MG1 <= value_hash )
342 || ( depth_current < 3*PLY_INC
343 && beta+EFUTIL_MG2 <= value_hash ) ) )
346 ptree->ntrans_lower++;
350 if ( beta <= value_hash
351 && ( depth_current <= depth_hash
352 || score_max_eval < value_hash
353 || ( turn_current != turn_hash
354 && depth_hash >= null_depth
355 && ( *pstate_node & node_do_null ) ) ) )
357 HASH_VALUE = value_hash;
358 ptree->ntrans_superior_hit++;
363 } else if ( is_superior == -1 ) {
365 *pstate_node |= state_node_hash;
367 if ( value_hash <= score_max_eval )
369 *pstate_node &= ~node_do_mate;
372 if ( ( type_hash & flag_value_up_exact )
373 && value_hash <= alpha
374 && RecursionDepth(depth_current) <= depth_hash )
376 *pstate_node &= ~node_do_recursion;
379 if ( type_hash & flag_value_up_exact )
381 if ( value_hash < beta && null_depth <= depth_hash )
383 *pstate_node &= ~node_do_null;
385 if ( value_hash <= alpha
386 && ( depth_current <= depth_hash
387 || value_hash < -score_max_eval ) )
389 HASH_VALUE = value_hash;
390 ptree->ntrans_inferior_hit++;
398 slot = (unsigned int)HASH_KEY >> 31;
399 word1 = ptrans_table[index].always[slot].word1;
400 word2 = ptrans_table[index].always[slot].word2;
402 SignKey( word2, word1 );
403 key_hash = word2 & ~(uint64_t)0x7fU;
405 if ( key_hash == key_current ) {
407 ptree->ntrans_always_hit++;
409 depth_hash = (int)((unsigned int)(word1>>56) & 0x00ffU);
410 value_hash = (int)((unsigned int)(word1>>40) & 0xffffU) - 32768;
411 move_hash = (unsigned int)(word1>>21) & 0x7ffffU;
412 hand_hash = (unsigned int)word1 & 0x1fffffU;
414 utemp = (unsigned int)word2;
415 state_node_hash = utemp & node_mate_threat;
416 turn_hash = (int)((utemp>>6) & 0x1U);
417 type_hash = (int)((utemp>>3) & 0x3U);
419 if ( abs(value_hash) > score_max_eval )
421 if ( value_hash > 0 ) { value_hash -= ply-1; }
422 else { value_hash += ply-1; }
424 #if ! defined(MINIMUM)
425 if ( abs(value_hash) > score_mate1ply )
427 out_warning( "Hash value is out of bounce!!" );
432 if ( RecursionThreshold <= depth_current
433 && depth_hash < RecursionDepth(depth_current) ) { move_hash = 0; }
434 else if ( move_hash )
436 move_hash |= turn_current ? Cap2Move( BOARD[I2To(move_hash)])
437 : Cap2Move(-BOARD[I2To(move_hash)]);
440 if ( turn_hash == turn_current && hand_hash == HAND_B ) {
442 if ( ! ptree->amove_hash[ply] )
445 || is_move_valid( ptree, move_hash, turn_current ) );
446 ptree->amove_hash[ply] = move_hash;
449 *pstate_node |= state_node_hash;
451 if ( value_hash <= score_max_eval ) { *pstate_node &= ~node_do_mate; }
453 if ( ( type_hash & flag_value_up_exact )
454 && value_hash <= alpha
455 && RecursionDepth(depth_current) <= depth_hash )
457 *pstate_node &= ~node_do_recursion;
460 if ( ( type_hash & flag_value_up_exact )
462 && null_depth <= depth_hash )
464 *pstate_node &= ~node_do_null;
467 if ( type_hash == value_lower
468 && value_hash >= beta
469 && ( depth_hash >= depth_current || value_hash > score_max_eval ) )
471 HASH_VALUE = value_hash;
472 ptree->ntrans_lower++;
476 if ( type_hash == value_upper
477 && value_hash <= alpha
478 && ( depth_hash >= depth_current || value_hash < -score_max_eval ) )
480 HASH_VALUE = value_hash;
481 ptree->ntrans_upper++;
485 if ( type_hash == value_exact
486 && ( depth_hash >= depth_current
487 || abs(value_hash) > score_max_eval ) )
489 HASH_VALUE = value_hash;
490 ptree->ntrans_upper++;
495 if ( ( type_hash & flag_value_low_exact )
496 && ! ptree->nsuc_check[ply]
497 && ! ptree->nsuc_check[ply-1]
498 && ( ( depth_current < 2*PLY_INC
499 && beta+EFUTIL_MG1 <= value_hash )
500 || ( depth_current < 3*PLY_INC
501 && beta+EFUTIL_MG2 <= value_hash ) ) )
504 ptree->ntrans_lower++;
510 is_superior = eval_supe( HAND_B, hand_hash, turn_current, turn_hash,
511 &value_hash, &type_hash );
513 if ( is_superior == 1 ) {
515 if ( ( turn_hash == turn_current ) && ! move_supe )
517 move_supe = move_hash;
520 if ( type_hash & flag_value_low_exact )
522 if ( ! ptree->nsuc_check[ply]
523 && ! ptree->nsuc_check[ply-1]
524 && ( ( depth_current < 2*PLY_INC
525 && beta+EFUTIL_MG1 <= value_hash )
526 || ( depth_current < 3*PLY_INC
527 && beta+EFUTIL_MG2 <= value_hash ) ) )
530 ptree->ntrans_lower++;
534 if ( value_hash >= beta
535 && ( depth_hash >= depth_current
536 || score_max_eval < value_hash
537 || ( turn_current != turn_hash
538 && depth_hash >= null_depth
539 && ( *pstate_node & node_do_null ) ) ) )
541 HASH_VALUE = value_hash;
542 ptree->ntrans_superior_hit++;
547 } else if ( is_superior == -1 ) {
549 *pstate_node |= state_node_hash;
551 if ( value_hash <= score_max_eval )
553 *pstate_node &= ~node_do_mate;
556 if ( ( type_hash & flag_value_up_exact )
557 && value_hash <= alpha
558 && RecursionDepth(depth_current) <= depth_hash )
560 *pstate_node &= ~node_do_recursion;
563 if ( type_hash & flag_value_up_exact )
565 if ( value_hash < beta && null_depth <= depth_hash )
567 *pstate_node &= ~node_do_null;
569 if ( value_hash <= alpha
570 && ( depth_hash >= depth_current
571 || value_hash < -score_max_eval ) )
573 HASH_VALUE = value_hash;
574 ptree->ntrans_inferior_hit++;
582 if ( ! ptree->amove_hash[ply] )
586 ifrom = (int)I2From(move_supe);
587 if ( ifrom >= nsquare )
589 unsigned int hand = turn_current ? HAND_W : HAND_B;
590 switch( From2Drop(ifrom) )
593 if ( ! IsHandPawn(hand) ) {
594 move_supe = To2Move(I2To(move_supe));
595 if ( IsHandLance(hand) )
597 move_supe |= Drop2Move(lance);
599 else if ( IsHandSilver(hand))
601 move_supe |= Drop2Move(silver);
603 else if ( IsHandGold(hand) )
605 move_supe |= Drop2Move(gold);
607 else { move_supe |= Drop2Move(rook); }
612 if ( ! IsHandLance(hand) )
614 move_supe = To2Move(I2To(move_supe)) | Drop2Move(rook);
620 assert( is_move_valid( ptree, move_supe, turn_current ) );
621 ptree->amove_hash[ply] = move_supe;
630 eval_supe( unsigned int hand_current, unsigned int hand_hash,
631 int turn_current, int turn_hash,
632 int * restrict pvalue_hash, int * restrict ptype_hash )
636 if ( hand_current == hand_hash ) { is_superior = 0; }
637 else if ( is_hand_eq_supe( hand_current, hand_hash ) )
639 is_superior = turn_current ? -1 : 1;
641 else if ( is_hand_eq_supe( hand_hash, hand_current ) )
643 is_superior = turn_current ? 1 : -1;
647 if ( turn_hash != turn_current )
649 if ( is_superior == -1 ) { is_superior = 0; }
653 switch ( *ptype_hash )
655 case value_lower: *ptype_hash=value_upper; break;
656 case value_upper: *ptype_hash=value_lower; break;
666 clear_trans_table( void )
668 unsigned int elapsed_start, elapsed_end;
671 if ( get_elapsed( &elapsed_start ) < 0 ) { return -1; }
673 Out( "cleanning the transposition table ..." );
676 ntrans_table = 1 << log2_ntrans_table;
677 for ( i = 0; i < ntrans_table; i++ )
679 ptrans_table[i].prefer.word1 = 0;
680 ptrans_table[i].prefer.word2 = 0;
681 ptrans_table[i].always[0].word1 = 0;
682 ptrans_table[i].always[0].word2 = 0;
683 ptrans_table[i].always[1].word1 = 0;
684 ptrans_table[i].always[1].word2 = 0;
687 if ( get_elapsed( &elapsed_end ) < 0 ) { return -1; }
688 Out( " done (%ss)\n", str_time_symple( elapsed_end - elapsed_start ) );