8 static int CONV dbg_is_hand_valid( unsigned int hand );
11 static unsigned int CONV calc_hand_win( const node_t *pnode,
13 unsigned int hand_w );
14 static unsigned int CONV calc_hand_lose( const node_t * restrict pnode,
16 unsigned int hand_w );
17 static unsigned int CONV hand_or( unsigned int a, unsigned int b );
18 static unsigned int CONV hand_and( unsigned int a, unsigned int b );
19 static int CONV dfpn_hand_supe( unsigned int u, unsigned int uref );
21 const unsigned int hand_tbl[16] = {
22 0, flag_hand_pawn, flag_hand_lance, flag_hand_knight,
23 flag_hand_silver, flag_hand_gold, flag_hand_bishop, flag_hand_rook,
24 0, flag_hand_pawn, flag_hand_lance, flag_hand_knight,
25 flag_hand_silver, 0, flag_hand_bishop, flag_hand_rook };
27 static const unsigned int hand_mask[16] = {
28 0, 0x00001fU, 0x0000e0U, 0x000700U,
29 0x003800U, 0x01c000U, 0x060000U, 0x180000U,
30 0, 0x00001fU, 0x0000e0U, 0x000700U,
31 0x003800U, 0, 0x060000U, 0x180000U };
34 int CONV dfpn_ini_hash( void )
39 if ( dfpn_hash_tbl != NULL ) { memory_free( dfpn_hash_tbl ); }
40 n2 = 1U << dfpn_hash_log2;
41 size = sizeof( dfpn_hash_entry_t ) * ( n2 + 1 + DFPN_NUM_REHASH );
43 dfpn_hash_tbl = memory_alloc( size );
44 if ( dfpn_hash_tbl == NULL ) { return -1; }
46 dfpn_hash_mask = n2 -1;
48 for ( u = 0; u < n2 + 1 + DFPN_NUM_REHASH; u++ )
50 dfpn_hash_tbl[u].word3 = 0;
53 Out( "DFPN Table Entries = %uk (%uMB)\n",
54 ( dfpn_hash_mask + 1U ) / 1024U, size / ( 1024U * 1024U ) );
60 float CONV dfpn_hash_sat( void )
63 unsigned int u, n, used, age;
65 if ( dfpn_hash_mask >= 0x10000U ) { n = 0x10000U; }
66 else { n = dfpn_hash_mask + 1U; }
69 for ( u = 0; u < n; u++ )
71 nodes = dfpn_hash_tbl[u].word3 & DFPN_NODES_MASK;
72 age = (unsigned int)( dfpn_hash_tbl[u].word2 >> 46 ) & DFPN_AGE_MASK;
73 if ( nodes != 0 && age == dfpn_hash_age ) { used += 1; }
76 return (float)( used * 100U ) / (float)n;
80 # if defined(_MSC_VER)
81 # pragma warning(disable:4100)
83 # pragma warning(disable:869)
85 void CONV dfpn_hash_probe( const dfpn_tree_t * restrict pdfpn_tree,
86 child_t * restrict pchild, int ply, int turn )
88 uint64_t hash_key_curr, word1, word2, word3, hash_key, nodes;
89 unsigned int index, hand_b, phi, delta, u, offset, hand_b_curr;
90 int relation, is_phi_loop, is_delta_loop;
95 if ( pdfpn_tree->turn_or == turn ) { hash_key_curr = pchild->hash_key; }
96 else { hash_key_curr = ~pchild->hash_key; }
97 hand_b_curr = pchild->hand_b;
99 index = (unsigned int)hash_key_curr & dfpn_hash_mask;
100 for ( u = index; u < index + DFPN_NUM_REHASH; u++ ) {
102 word1 = dfpn_hash_tbl[u].word1;
103 word2 = dfpn_hash_tbl[u].word2;
104 word3 = dfpn_hash_tbl[u].word3;
105 DFPNSignKey( word1, word2, word3 );
107 hash_key = word1 & ~UINT64_C(0x1fffff);
108 hand_b = (unsigned int)word1 & 0x1fffffU;
109 delta = (unsigned int)word2 & INF;
110 phi = (unsigned int)( word2 >> 23 ) & INF;
111 offset = (unsigned int)( word2 >> 54 ) & 0xffU;
112 is_phi_loop = (int)( word2 >> 63 );
113 is_delta_loop = (int)( word2 >> 62 ) & 1;
114 nodes = word3 & DFPN_NODES_MASK;
115 assert( offset <= u );
117 if ( nodes == 0 ) { break; }
118 if ( index + offset < u ) { break; }
119 if ( index + offset > u ) { continue; }
120 if ( hash_key != ( hash_key_curr & ~UINT64_C(0x1fffff) ) ) { continue; }
122 if ( hand_b_curr == hand_b )
125 pchild->delta = delta;
126 pchild->nodes = nodes;
127 pchild->min_hand_b = hand_b;
128 pchild->is_phi_loop = is_phi_loop;
129 pchild->is_delta_loop = is_delta_loop;
130 DOut( ply, "HASH EXACT at %u+%u, %x, %x: [%u,%u] %u %x %c %c",
131 index, offset, (unsigned int)hash_key_curr, hand_b_curr, phi,
132 delta, (unsigned int)nodes, pchild->min_hand_b,
133 is_phi_loop ? 'y' : 'n', is_delta_loop ? 'y' : 'n' );
137 if ( dfpn_hand_supe( hand_b_curr, hand_b ) ) { relation = REL_SUPE; }
138 else if ( dfpn_hand_supe( hand_b, hand_b_curr ) ) { relation = REL_INFE; }
141 if ( turn ) { relation = relation ^ 1; }
143 if ( relation == REL_SUPE && phi == 0 && delta == INF )
146 pchild->delta = delta;
147 pchild->nodes = nodes;
148 pchild->min_hand_b = hand_b;
149 pchild->is_phi_loop = is_phi_loop;
150 pchild->is_delta_loop = is_delta_loop;
151 DOut( ply, "HASH SUPE at %u+%u, %x, %x: [%u,%u] %u %x n n", index,
152 offset, (unsigned int)hash_key_curr, hand_b_curr, phi, delta,
153 (unsigned int)nodes, pchild->min_hand_b );
157 if ( relation == REL_INFE && phi == INF && delta == 0 )
160 pchild->delta = delta;
161 pchild->nodes = nodes;
162 pchild->min_hand_b = hand_b;
163 pchild->is_phi_loop = is_phi_loop;
164 pchild->is_delta_loop = is_delta_loop;
165 DOut( ply, "HASH INFE at %u+%u, %x, %x: [%u,%u] %u %x n n", index,
166 offset, (unsigned int)hash_key_curr, hand_b_curr, phi, delta,
167 (unsigned int)nodes, pchild->min_hand_b );
172 # if defined(_MSC_VER)
173 # pragma warning(default:4100)
174 # elif defined(__ICC)
175 # pragma warning(default:869)
179 void CONV dfpn_hash_store( const tree_t * restrict ptree,
180 dfpn_tree_t * restrict pdfpn_tree, int ply )
182 node_t * restrict pnode = pdfpn_tree->anode + ply;
183 uint64_t word1, word2, word3, min_nodes, nodes, hash_key;
184 uint64_t tmp1, tmp2, tmp3;
185 unsigned int index, min_u, u, u1, hand_b, min_hand_b, offset, age;
186 int turn_win, i, n, is_phi_loop, is_delta_loop;
188 assert( pnode->phi != INF || pnode->delta != INF );
190 if ( pdfpn_tree->turn_or == pnode->turn ) { hash_key = HASH_KEY; }
191 else { hash_key = ~HASH_KEY; }
193 word1 = ( hash_key & ~UINT64_C(0x1fffff) );
194 index = (unsigned int)hash_key & dfpn_hash_mask;
196 if ( pnode->phi == 0 && pnode->delta == INF )
198 min_hand_b = calc_hand_win( pnode, HAND_B, HAND_W );
199 turn_win = pnode->turn;
202 word1 |= (uint64_t)min_hand_b;
204 else if ( pnode->phi == INF && pnode->delta == 0 )
206 min_hand_b = calc_hand_lose( pnode, HAND_B, HAND_W );
207 turn_win = Flip(pnode->turn);
210 word1 |= (uint64_t)min_hand_b;
214 word1 |= (uint64_t)min_hand_b;
218 for ( i = 0; i < n; i++ )
220 if ( pnode->phi == pnode->children[i].delta )
222 is_phi_loop &= pnode->children[i].is_delta_loop;
224 is_delta_loop |= pnode->children[i].is_phi_loop;
230 for ( u = index; u < index + DFPN_NUM_REHASH; u++ ) {
232 tmp1 = dfpn_hash_tbl[u].word1;
233 tmp2 = dfpn_hash_tbl[u].word2;
234 tmp3 = dfpn_hash_tbl[u].word3;
235 DFPNSignKey( tmp1, tmp2, tmp3 );
237 nodes = tmp3 & DFPN_NODES_MASK;
238 offset = ( tmp2 >> 54 ) & 0xffU;
240 if ( nodes == 0 ) { continue; }
241 if ( u != index + offset ) { continue; }
242 if ( word1 == tmp1 ) { continue; }
243 if ( ( word1 & ~UINT64_C(0x1fffff) ) != ( tmp1 & ~UINT64_C(0x1fffff) ) )
248 hand_b = (unsigned int)tmp1 & 0x1fffffU;
249 assert( min_hand_b != hand_b );
251 if ( ! turn_win && ! dfpn_hand_supe( hand_b, min_hand_b ) ) { continue; }
252 if ( turn_win && ! dfpn_hand_supe( min_hand_b, hand_b ) ) { continue; }
255 for ( u1 = u+1;; u1++ ) {
257 tmp1 = dfpn_hash_tbl[u1].word1;
258 tmp2 = dfpn_hash_tbl[u1].word2;
259 tmp3 = dfpn_hash_tbl[u1].word3;
260 DFPNSignKey( tmp1, tmp2, tmp3 );
262 nodes = tmp3 & DFPN_NODES_MASK;
263 if ( nodes == 0 ) { break; }
265 assert( u1 < DFPN_NUM_REHASH + 1 + dfpn_hash_mask );
266 offset = (unsigned int)( tmp2 >> 54 ) & 0xffU;
267 if ( offset == 0 ) { break; }
269 tmp2 &= ~( (uint64_t)0xffU << 54 );
270 tmp2 |= (uint64_t)( offset - 1U ) << 54;
272 DFPNSignKey( tmp1, tmp2, tmp3 );
273 dfpn_hash_tbl[u1-1].word1 = tmp1;
274 dfpn_hash_tbl[u1-1].word2 = tmp2;
275 dfpn_hash_tbl[u1-1].word3 = tmp3;
278 dfpn_hash_tbl[u1-1].word3 = 0;
283 min_nodes = UINT64_MAX;
285 for ( u = index; u < index + DFPN_NUM_REHASH * 3U; u++ )
287 if ( u == dfpn_hash_mask + 2 + DFPN_NUM_REHASH ) { break; }
289 tmp1 = dfpn_hash_tbl[u].word1;
290 tmp2 = dfpn_hash_tbl[u].word2;
291 tmp3 = dfpn_hash_tbl[u].word3;
292 DFPNSignKey( tmp1, tmp2, tmp3 );
294 offset = ( tmp2 >> 54 ) & 0xffU;
295 age = (unsigned int)( tmp2 >> 46 ) & DFPN_AGE_MASK;
296 nodes = tmp3 & DFPN_NODES_MASK;
298 assert( offset <= u );
301 || age != dfpn_hash_age
302 || ( index == u - offset && word1 == tmp1 ) )
308 if ( index <= u - offset && offset == DFPN_NUM_REHASH - 1 ) { break; }
310 if ( nodes < min_nodes )
317 if ( min_u == UINT_MAX )
319 out_warning( "HASH ERROR in $s line %d", __FILE__, __LINE__ );
324 tmp1 = dfpn_hash_tbl[min_u].word1;
325 tmp2 = dfpn_hash_tbl[min_u].word2;
326 tmp3 = dfpn_hash_tbl[min_u].word3;
327 DFPNSignKey( tmp1, tmp2, tmp3 );
328 offset = (unsigned int)( tmp2 >> 54 ) & 0xffU;
329 min_nodes = tmp3 & DFPN_NODES_MASK;
330 age = (unsigned int)(tmp2 >> 46) & DFPN_AGE_MASK;
333 || age != dfpn_hash_age
334 || index <= min_u - offset ) {
336 for ( ; index < min_u; min_u -= 1 ) {
338 assert( dfpn_hash_tbl[min_u-1].word2 != 0 );
339 tmp1 = dfpn_hash_tbl[min_u-1].word1;
340 tmp2 = dfpn_hash_tbl[min_u-1].word2;
341 tmp3 = dfpn_hash_tbl[min_u-1].word3;
342 DFPNSignKey( tmp1, tmp2, tmp3 );
344 offset = (unsigned int)( tmp2 >> 54 ) & 0xffU;
345 assert( offset <= min_u - 1 );
346 if ( min_u - 1 - offset <= index ) { break; }
348 assert( offset + 1U < DFPN_NUM_REHASH );
350 dfpn_hash_tbl[min_u-1].word3 = 0;
352 tmp2 &= ~( (uint64_t)0xffU << 54 );
353 tmp2 |= (uint64_t)( offset + 1U ) << 54;
355 DFPNSignKey( tmp1, tmp2, tmp3 );
356 dfpn_hash_tbl[min_u].word1 = tmp1;
357 dfpn_hash_tbl[min_u].word2 = tmp2;
358 dfpn_hash_tbl[min_u].word3 = tmp3;
363 for ( ; min_u < index + DFPN_NUM_REHASH - 1; min_u += 1 ) {
365 assert( dfpn_hash_tbl[min_u+1].word2 != 0 );
366 tmp1 = dfpn_hash_tbl[min_u+1].word1;
367 tmp2 = dfpn_hash_tbl[min_u+1].word2;
368 tmp3 = dfpn_hash_tbl[min_u+1].word3;
369 DFPNSignKey( tmp1, tmp2, tmp3 );
371 offset = (unsigned int)( tmp2 >> 54 ) & 0xffU;
372 assert( offset <= min_u + 1 );
373 if ( index <= min_u + 1 - offset ) { break; }
375 assert( offset != 0 );
377 dfpn_hash_tbl[min_u+1].word3 = 0;
379 tmp2 &= ~( (uint64_t)0xffU << 54 );
380 tmp2 |= (uint64_t)( offset - 1U ) << 54;
382 DFPNSignKey( tmp1, tmp2, tmp3 );
383 dfpn_hash_tbl[min_u].word1 = tmp1;
384 dfpn_hash_tbl[min_u].word2 = tmp2;
385 dfpn_hash_tbl[min_u].word3 = tmp3;
389 assert( min_nodes != UINT_MAX );
390 assert( pnode->phi <= INF && pnode->delta <= INF );
391 assert( index <= min_u && min_u - index < DFPN_NUM_REHASH );
393 offset = min_u - index;
394 pnode->is_phi_loop = is_phi_loop;
395 pnode->is_delta_loop = is_delta_loop;
396 pnode->min_hand_b = min_hand_b;
398 word2 = (uint64_t)is_phi_loop << 63;
399 word2 |= (uint64_t)is_delta_loop << 62;
400 word2 |= (uint64_t)offset << 54;
401 word2 |= (uint64_t)dfpn_hash_age << 46;
402 word2 |= (uint64_t)pnode->phi << 23;
403 word2 |= (uint64_t)pnode->delta << 0;
404 word3 = pnode->nodes;
406 DFPNSignKey( word1, word2, word3 );
407 dfpn_hash_tbl[min_u].word1 = word1;
408 dfpn_hash_tbl[min_u].word2 = word2;
409 dfpn_hash_tbl[min_u].word3 = word3;
411 DOut( ply, "STORE[%u+%u] %x, %x: [%d,%d] %c %c",
412 index, offset, (unsigned int)hash_key, min_hand_b, pnode->phi,
413 pnode->delta, is_phi_loop ? 'y': 'n', is_delta_loop ? 'y' : 'n' );
418 dfpn_max_hand_b( unsigned int hand_b, unsigned hand_w )
420 unsigned hand_tot = hand_b + hand_w;
424 for ( i = pawn; i <= rook; i++ )
425 if ( hand_b & hand_mask[i] ) { hand += hand_tot & hand_mask[i]; }
432 dfpn_max_hand_w( unsigned int hand_b, unsigned hand_w )
434 unsigned hand_tot = hand_b + hand_w;
435 unsigned hand = hand_b + hand_w;
438 for ( i = pawn; i <= rook; i++ )
439 if ( hand_w & hand_mask[i] ) { hand -= hand_tot & hand_mask[i]; }
446 dfpn_detect_rep( const dfpn_tree_t * restrict pdfpn_tree, uint64_t hash_key,
447 unsigned int hand_b, int ply, int * restrict ip )
449 const node_t * restrict pnode;
451 for ( *ip = ply; *ip >= pdfpn_tree->root_ply; *ip -=2 )
453 pnode = pdfpn_tree->anode + *ip;
454 if ( pnode->hash_key == hash_key
455 && pnode->hand_b == hand_b ) { return 1; }
463 dfpn_hand_supe( unsigned int u, unsigned int uref )
465 if ( IsHandPawn(u) >= IsHandPawn(uref)
466 && IsHandLance(u) >= IsHandLance(uref)
467 && IsHandKnight(u) >= IsHandKnight(uref)
468 && IsHandSilver(u) >= IsHandSilver(uref)
469 && IsHandGold(u) >= IsHandGold(uref)
470 && IsHandBishop(u) >= IsHandBishop(uref)
471 && IsHandRook(u) >= IsHandRook(uref) ) { return 1; }
477 static unsigned int CONV
478 calc_hand_lose( const node_t * restrict pnode,
479 unsigned int hand_b, unsigned int hand_w )
482 unsigned int hand_tot = hand_b + hand_w;
489 hand = dfpn_max_hand_w( hand_b, hand_w );
491 for ( i = 0; i < n; i++ ) {
492 hand = hand_or( hand, pnode->children[i].min_hand_b );
494 hand = hand_and( hand_tot, hand );
496 assert( dbg_is_hand_valid( hand ) && dfpn_hand_supe( hand_b, hand ) );
500 hand = dfpn_max_hand_b( hand_b, hand_w );
502 for ( i = 0; i < n; i++ ) {
504 unsigned int h0 = pnode->children[i].min_hand_b;
505 int from = (int)I2From(pnode->children[i].move);
506 int pc_cap = (int)UToCap(pnode->children[i].move);
508 if ( from >= nsquare ) { h0 += hand_tbl[From2Drop(from)]; }
509 else if ( h0 & hand_mask[pc_cap] ) { h0 -= hand_tbl[pc_cap]; }
511 hand = hand_and( hand, h0 );
514 assert( dbg_is_hand_valid( hand ) && dfpn_hand_supe( hand, hand_b ) );
521 static unsigned int CONV
522 calc_hand_win( const node_t *pnode, unsigned int hand_b, unsigned int hand_w )
525 unsigned int hand, h0;
531 hand = hand_b + hand_w;
533 for ( i = 0; i < n; i++ ) {
535 if ( pnode->children[i].phi != INF ) { continue; }
536 if ( pnode->children[i].delta != 0 ) { continue; }
538 h0 = hand_and( hand_b + hand_w, pnode->children[i].min_hand_b );
539 if ( dfpn_hand_supe( hand, h0 ) ) { hand = h0; }
542 assert( dbg_is_hand_valid(hand) && dfpn_hand_supe(hand, hand_b) );
548 for ( i = 0; i < n; i++ ) {
552 if ( pnode->children[i].phi != INF ) { continue; }
553 if ( pnode->children[i].delta != 0 ) { continue; }
555 h0 = pnode->children[i].min_hand_b;
556 from = (int)I2From(pnode->children[i].move);
557 pc_cap = (int)UToCap(pnode->children[i].move);
559 if ( from >= nsquare ) { h0 += hand_tbl[From2Drop(from)]; }
560 else if ( h0 & hand_mask[pc_cap] ) { h0 -= hand_tbl[pc_cap]; }
562 h0 = hand_and( hand_b + hand_w, h0 );
564 if ( dfpn_hand_supe( h0, hand ) ) { hand = h0; }
567 assert( dbg_is_hand_valid( hand ) && dfpn_hand_supe( hand_b, hand ) );
574 static unsigned int CONV
575 hand_or( unsigned int a, unsigned int b )
577 unsigned int c, u1, u2;
581 for ( i = pawn; i <= rook; i++ )
583 u1 = hand_mask[i] & a;
584 u2 = hand_mask[i] & b;
585 c += u2 < u1 ? u1 : u2;
592 static unsigned int CONV
593 hand_and( unsigned int a, unsigned int b )
595 unsigned int c, u1, u2;
599 for ( i = pawn; i <= rook; i++ )
601 u1 = hand_mask[i] & a;
602 u2 = hand_mask[i] & b;
603 c += u1 < u2 ? u1 : u2;
611 dbg_is_hand_valid( unsigned int hand )
613 return ( I2HandPawn(hand) <= 18U
614 && I2HandLance(hand) <= 4U
615 && I2HandKnight(hand) <= 4U
616 && I2HandSilver(hand) <= 4U
617 && I2HandGold(hand) <= 4U
618 && I2HandBishop(hand) <= 2U
619 && I2HandRook(hand) <= 2U );