From: H.G. Muller Date: Wed, 30 Oct 2013 09:04:44 +0000 (+0100) Subject: Add forgotten dfpn files X-Git-Url: http://winboard.nl/cgi-bin?p=bonanza.git;a=commitdiff_plain;h=f6f230d5a10864715c8ec866aec516a27535b17d Add forgotten dfpn files These files were new in v6.0 and not automatically checked into git on the update. They are needed even when building without the -DDFPN* switches because of a deficiency in the Makefile. --- diff --git a/dfpn.c b/dfpn.c new file mode 100644 index 0000000..b735b73 --- /dev/null +++ b/dfpn.c @@ -0,0 +1,870 @@ +#if defined(DFPN) + +#include +#include +#include +#include +#include "shogi.h" +#include "dfpn.h" + +dfpn_hash_entry_t * restrict dfpn_hash_tbl = NULL; +unsigned int dfpn_hash_age; +unsigned int dfpn_hash_mask; + +#if defined(DFPN_DBG) +int dbg_flag = 1; +static void CONV dbg_out_move_seq( const node_t * restrict nodes, int ply ); +static void CONV dbg_min_delta_c( const node_t * restrict pnode, int ply ); +static void CONV dbg_sum_phi_c( const node_t * restrict pnode, int ply ); +static void CONV dbg_nodes( const node_t * restrict pnode, int ply ); +#endif + + +static int CONV useless_delta_ticking( node_t * restrict pnode ); +static unsigned int CONV min_delta_c( const node_t * restrict pnode ); +static unsigned int CONV sum_phi_c( const node_t * restrict pnode ); +static int CONV init_children( tree_t * restrict ptree, + dfpn_tree_t * restrict pdfpn_tree, int ply ); +static int CONV mid( tree_t * restrict ptree, + dfpn_tree_t * restrict pdfpn_tree, int ply ); +static void CONV select_child( const tree_t * restrict ptree, + node_t * restrict pnode_c, + unsigned int * restrict pphi_c, + unsigned int * restrict pdelta_c, + unsigned int * restrict pdelta_2 ); +static void CONV num2str( char buf[16], unsigned int num ); + +#if defined(TLP) +static dfpn_tree_t dfpn_tree[ TLP_MAX_THREADS ]; +#else +static dfpn_tree_t dfpn_tree; +#endif + +int CONV +dfpn( tree_t * restrict ptree, int turn, int ply ) +{ + dfpn_tree_t * restrict pdfpn_tree; + node_t * restrict pnode; + float fcpu_percent, fnps, fsat; + unsigned int cpu0, cpu1, elapse0, elapse1, u; + int iret, i; + + if ( get_cputime( &cpu0 ) < 0 ) { return -1; } + if ( get_elapsed( &elapse0 ) < 0 ) { return -1; } + + u = node_per_second / 16U; + if ( u > TIME_CHECK_MAX_NODE ) { u = TIME_CHECK_MAX_NODE; } + else if ( u < TIME_CHECK_MIN_NODE ) { u = TIME_CHECK_MIN_NODE; } + node_next_signal = u; + node_last_check = 0; + root_abort = 0; + time_max_limit = UINT_MAX; + time_limit = UINT_MAX; + game_status &= ~( flag_move_now | flag_suspend | flag_search_error ); + game_status |= flag_thinking; + +#if defined(TLP) + pdfpn_tree = &dfpn_tree[ptree->tlp_id]; +#else + pdfpn_tree = &dfpn_tree; +#endif + ptree->node_searched = 0; + + pdfpn_tree->root_ply = ply; + pdfpn_tree->turn_or = turn; + pdfpn_tree->sum_phi_max = 0; + pdfpn_tree->node_limit = 50000000; + + pnode = pdfpn_tree->anode + ply; + pnode->phi = INF_1; + pnode->delta = INF_1; + pnode->turn = turn; + pnode->children = pdfpn_tree->child_tbl; + pnode->new_expansion = 1; + + assert( 1 <= ply ); + assert( pdfpn_tree->node_limit < DFPN_NODES_MASK ); + iret = mid( ptree, pdfpn_tree, ply ); + if ( 0 <= iret + && pnode->phi != INF + && pnode->delta != INF ) + { + char buf1[16], buf2[16]; + + num2str( buf1, pnode->phi ); + num2str( buf2, pnode->delta ); + Out( "Research [%s:%s]\n", buf1, buf2 ); + pnode->phi = INF; + pnode->delta = INF; + iret = mid( ptree, pdfpn_tree, ply ); + } + + game_status &= ~flag_thinking; + + if ( game_status & flag_search_error ) { return -1; } + + if ( iret < 0 ) + { + DFPNOut( "UNSOLVED %d\n", iret ); + switch ( iret ) { + case DFPN_ERRNO_MAXNODE: Out( "RESULT: MAX NODE\n" ); break; + case DFPN_ERRNO_MAXPLY: Out( "RESULT: MAX PLY\n" ); break; + case DFPN_ERRNO_SUMPHI: Out( "RESULT: MAX SUM_PHI\n" ); break; + case DFPN_ERRNO_DELTA2P: Out( "RESULT: MAX DELTA2+1\n" ); break; + default: + assert( DFPN_ERRNO_SIGNAL == iret ); + Out( "RESULT: SIGNAL\n" ); + break; + } + } + else if ( pnode->delta == INF ) + { + const char *str; + for ( i = 0; i < pnode->nmove && pnode->children[i].phi != INF; i++ ); + assert( i < pnode->nmove ); + str = str_CSA_move(pnode->children[i].move); + Out( "RESULT: WIN %s\n", str ); + DFPNOut( "WIN %s\n", str ); + } + else { + Out( "RESULT: LOSE\n" ); + DFPNOut( "LOSE\n" ); + } + + fsat = dfpn_hash_sat(); + if ( 3.0 < fsat ) + { + dfpn_hash_age += 1U; + dfpn_hash_age &= DFPN_AGE_MASK; + } + + if ( get_cputime( &cpu1 ) < 0 ) { return -1; } + if ( get_elapsed( &elapse1 ) < 0 ) { return -1; } + fcpu_percent = 100.0F * (float)( cpu1 - cpu0 ); + fcpu_percent /= (float)( elapse1 - elapse0 + 1U ); + fnps = 1000.0F * (float)ptree->node_searched; + fnps /= (float)( elapse1 - elapse0 + 1U ); + node_per_second = (unsigned int)( fnps + 0.5 ); + + Out( "n=%" PRIu64 " sat=%3.1f%%", ptree->node_searched, fsat ); + Out( " age=%u sum_phi=%u", dfpn_hash_age, pdfpn_tree->sum_phi_max ); + Out( " time=%.2f cpu=%.1f%% nps=%.2fK\n", + (float)( elapse1 - elapse0 + 1U ) / 1000.0F, + fcpu_percent, fnps / 1e3F ); + + Out( "\n" ); + + return 1; +} + + +static void CONV +num2str( char buf[16], unsigned int num ) +{ + if ( num == INF ) { snprintf( buf, 16, "inf" ); } + else if ( num == INF_1 ) { snprintf( buf, 16, "inf-1" ); } + else { snprintf( buf, 16, "%u", num ); } + buf[15] = '\0'; +} + + +static int CONV +mid( tree_t * restrict ptree, dfpn_tree_t * restrict pdfpn_tree, int ply ) +{ + node_t * restrict pnode = pdfpn_tree->anode + ply; + uint64_t node_searched0; + +#if defined(DFPN_DBG) + if ( ptree->node_searched >= 1000000 ) { dbg_flag = 1; } + DOut( ply, "MID START [%u,%u]", + pnode->phi, pnode->delta ); + dbg_out_move_seq( pdfpn_tree->anode, ply ); +#endif + + node_searched0 = ptree->node_searched; + + if ( pdfpn_tree->node_limit + <= ++ptree->node_searched ) { return DFPN_ERRNO_MAXNODE; } + +#if ! defined(MINIMUM) + if ( ! ( game_status & flag_learning ) ) +#endif +#if defined(TLP) + if ( ! ptree->tlp_id ) +#endif + if ( node_next_signal < ++node_last_check && detect_signals( ptree ) ) + { + return DFPN_ERRNO_SIGNAL; + } + + if ( PLY_MAX-4 < ply ) { return DFPN_ERRNO_MAXPLY; } + + if ( init_children( ptree, pdfpn_tree, ply ) ) + { + pnode->phi = 0; + pnode->delta = INF; + pnode->nodes = 1; + dfpn_hash_store( ptree, pdfpn_tree, ply ); + DOut( ply, "MID END: WIN\n" ); + return 1; + } + else if ( ! pnode->nmove ) + { + pnode->phi = INF; + pnode->delta = 0; + pnode->nodes = 1; + dfpn_hash_store( ptree, pdfpn_tree, ply ); + DOut( ply, "MID END: LOSE\n" ); + return 1; + } + + DOut( ply, "NMOVE: %d", pnode->nmove ); + pnode->hash_key = HASH_KEY; + pnode->hand_b = HAND_B; + + for ( ;; ) { + + node_t * restrict pnode_c = pdfpn_tree->anode + ply + 1; + unsigned int delta_c, phi_c, delta_2; + unsigned int delta_2p1; + int iret; + + pnode->min_delta = min_delta_c( pnode ); + pnode->sum_phi = sum_phi_c( pnode ); + if ( pnode->sum_phi == UINT_MAX ) { return DFPN_ERRNO_SUMPHI; } + + if ( pdfpn_tree->sum_phi_max < pnode->sum_phi && pnode->sum_phi < INF_1 ) + { + pdfpn_tree->sum_phi_max = pnode->sum_phi; + } + +#if defined(DFPN_DBG) + dbg_nodes( pnode, ply ); + dbg_min_delta_c( pnode, ply ); + dbg_sum_phi_c( pnode, ply ); +#endif + + if ( pnode->phi <= pnode->min_delta + || pnode->delta <= pnode->sum_phi ) { break; } + + + DOut( ply, "PROGRESS: [%u/%u,%u/%u] %u\n", + pnode->min_delta, pnode->phi, pnode->sum_phi, pnode->delta, INF ); + + select_child( ptree, pnode, &phi_c, &delta_c, &delta_2 ); + assert( pdfpn_tree->root_ply == ply + || ! pnode->children[pnode->icurr_c].is_loop ); + + if ( useless_delta_ticking( pnode ) ) + { + DOut( ply, "USELESS DELTA TICKING, DELTA_2=%u", pnode->phi ); + delta_2 = pnode->phi; + } + + if ( phi_c == INF_1 ) { pnode_c->phi = INF; } + else if ( pnode->delta >= INF_1 ) { pnode_c->phi = INF_1; } + else { + assert( phi_c != INF && pnode->sum_phi <= pnode->delta + phi_c ); + pnode_c->phi = pnode->delta + phi_c - pnode->sum_phi; + } + + if ( delta_c == INF_1 ) { pnode_c->delta = INF; } + else { + if ( INF_1 - 1 == delta_2 ) { return DFPN_ERRNO_DELTA2P; } + else if ( INF_1 <= delta_2 ) { delta_2p1 = delta_2; } + else { delta_2p1 = delta_2 + 1; } + + pnode_c->delta = delta_2p1 < pnode->phi ? delta_2p1 : pnode->phi; + } + + pnode_c->turn = Flip(pnode->turn); + pnode_c->children = pnode->children + pnode->nmove; + + if ( pnode->children[pnode->icurr_c].nodes == 0 ) + { + pnode_c->new_expansion = 1; + } + else { pnode_c->new_expansion = 0; } + + MakeMove( pnode->turn, pnode->children[pnode->icurr_c].move, ply ); + + iret = mid( ptree, pdfpn_tree, ply+1 ); + + UnMakeMove( pnode->turn, pnode->children[pnode->icurr_c].move, ply ); + + if ( SEARCH_ABORT ) { return iret; } + if ( iret < 0 ) { return iret; } + + pnode->new_expansion += pnode_c->new_expansion; + pnode->children[pnode->icurr_c].expanded = pnode_c->new_expansion; + + dfpn_hash_probe( pdfpn_tree, &pnode->children[pnode->icurr_c], ply, + Flip(pnode->turn) ); + } + + pnode->phi = pnode->min_delta; + pnode->delta = pnode->sum_phi; + pnode->nodes = ptree->node_searched - node_searched0; + dfpn_hash_store( ptree, pdfpn_tree, ply ); + + DOut( ply, "MID END [%u,%u]\n", pnode->min_delta, pnode->sum_phi ); + return 1; +} + + +static int CONV +useless_delta_ticking( node_t * restrict pnode ) +{ + int i, n; + + n = pnode->nmove; + for ( i = 0; i < n; i++ ) + { + if ( pnode->phi <= pnode->children[i].delta ) { continue; } + if ( pnode->children[i].is_weak == weak_chuai ) { continue; } + if ( pnode->children[i].is_delta_loop ) { continue; } + if ( pnode->children[i].expanded == 0 ) { continue; } + if ( 2000U < pnode->children[i].delta ) { continue; } + + return 0; + } + + return 1; +} + + +static int CONV +init_children( tree_t * restrict ptree, dfpn_tree_t * restrict pdfpn_tree, + int ply ) +{ + node_t * restrict pnode = pdfpn_tree->anode + ply; + const unsigned int *plast, *pmove; + unsigned int amove[MAX_NMOVE]; + int ip, sq_king, n; + + n = 0; + + if ( pdfpn_tree->turn_or == pnode->turn ) { + + sq_king = pnode->turn ? SQ_BKING : SQ_WKING; + plast = GenCheck( pnode->turn, amove ); + + for ( pmove = amove; pmove != plast; pmove++ ) + { + int from = I2From(*pmove); + int to = I2To(*pmove); + assert( is_move_valid( ptree, *pmove, pnode->turn ) ); + + MakeMove( pnode->turn, *pmove, ply ); + + if ( InCheck(pnode->turn) ) + { + UnMakeMove( pnode->turn, *pmove, ply ); + continue; + } + + if ( pnode->new_expansion + && ! ( pnode->turn ? b_have_evasion(ptree) + : w_have_evasion(ptree) ) ) + { + pnode->children[0].move = *pmove; + pnode->children[0].phi = INF; + pnode->children[0].delta = 0; + pnode->icurr_c = 0; + pnode->nmove = 1; + pnode->children[0].min_hand_b + = pnode->turn ? dfpn_max_hand_b( HAND_B, HAND_W ) + : dfpn_max_hand_w( HAND_B, HAND_W ); + + UnMakeMove( pnode->turn, *pmove, ply ); + return 1; + } + + + if ( from < nsquare ) + { + pnode->children[n].is_weak = 0; + pnode->children[n].priority = 1U; + } + /* drop to next square of the king */ + else if ( From2Drop(from) == knight + || BBContract( abb_king_attacks[sq_king], abb_mask[to] ) ) + { + pnode->children[n].is_weak = 0; + pnode->children[n].priority = 1U; + } + /* check by piece drop from far way */ + else { + pnode->children[n].is_weak + = weak_drop + ( adirec[sq_king][to] << 1 ) + ( sq_king < to ); + pnode->children[n].priority = 1U; + } + + pnode->children[n].nodes = 0; + pnode->children[n].phi = 1U; + pnode->children[n].delta = 1U; + pnode->children[n].is_loop = 0; + pnode->children[n].is_phi_loop = 0; + pnode->children[n].is_delta_loop = 0; + pnode->children[n].hash_key = HASH_KEY; + pnode->children[n].hand_b = HAND_B; + pnode->children[n].min_hand_b = HAND_B; + pnode->children[n].move = *pmove; + pnode->children[n].expanded = UINT64_MAX; + switch( dfpn_detect_rep( pdfpn_tree, HASH_KEY, HAND_B, ply-3, &ip ) ) + { + case 1: + DOut( ply, "LOOP DELTA: %s", str_CSA_move(*pmove) ); + pnode->children[n].is_loop = 1; + pnode->children[n].is_delta_loop = 1; + pnode->children[n].delta = pdfpn_tree->anode[ip].delta; + assert( pnode->phi <= pdfpn_tree->anode[ip].delta ); + break; + + default: + dfpn_hash_probe( pdfpn_tree, &pnode->children[n], ply, + Flip(pnode->turn) ); + } + + UnMakeMove( pnode->turn, *pmove, ply ); + n += 1; + } + + } else { + + bitboard_t bb_intercept; + unsigned int to; + + assert( InCheck(pnode->turn) ); + plast = GenEvasion( pnode->turn, amove ); + BBIni( bb_intercept ); + + sq_king = pnode->turn ? SQ_WKING : SQ_BKING; + + for ( pmove = amove; pmove != plast; pmove++ ) + { + assert( is_move_valid( ptree, *pmove, pnode->turn ) ); + + MakeMove( pnode->turn, *pmove, ply ); + + pnode->children[n].is_weak = 0; + to = I2To(*pmove); + + /* capture or king move */ + if ( I2PieceMove(*pmove) == king || UToCap(*pmove) ) + { + if ( I2PieceMove(*pmove) == king && UToCap(*pmove) ) + { + pnode->children[n].priority = 2U; + } + else if ( UToCap(*pmove) ) + { + pnode->children[n].priority = 3U; + } + else { pnode->children[n].priority = 4U; } + + /* non-intercepts may disproof this node easily. */ + if ( pnode->new_expansion + && ! ( pnode->turn ? b_have_checks(ptree) + : w_have_checks(ptree) ) ) + { + pnode->children[0].move = *pmove; + pnode->children[0].phi = INF; + pnode->children[0].delta = 0; + pnode->icurr_c = 0; + pnode->nmove = 1; + pnode->children[0].min_hand_b + = pnode->turn ? dfpn_max_hand_b( HAND_B, HAND_W ) + : dfpn_max_hand_w( HAND_B, HAND_W ); + UnMakeMove( pnode->turn, *pmove, ply ); + return 1; + } + } + + /* interseptions by move */ + else if ( I2From(*pmove) < nsquare ) + { + pnode->children[n].priority = 4U; + BBOr( bb_intercept, bb_intercept, abb_mask[to] ); + } + /* interseptions by drop */ + else if ( BBContract( bb_intercept, abb_mask[to] ) + || BBContract( abb_king_attacks[sq_king], + abb_mask[to] ) ) + { + pnode->children[n].priority = 5U; + pnode->children[n].is_weak = weak_drop + to; + } + /* 'chuai' interseptions */ + else { + pnode->children[n].priority = 6U; + pnode->children[n].is_weak = weak_chuai; + } + + pnode->children[n].is_loop = 0; + pnode->children[n].is_phi_loop = 0; + pnode->children[n].is_delta_loop = 0; + pnode->children[n].hash_key = HASH_KEY; + pnode->children[n].hand_b = HAND_B; + pnode->children[n].min_hand_b = HAND_B; + pnode->children[n].nodes = 0; + pnode->children[n].phi = 1U; + pnode->children[n].delta = 1U; + pnode->children[n].move = *pmove; + pnode->children[n].expanded = UINT64_MAX; + switch( dfpn_detect_rep( pdfpn_tree, HASH_KEY, HAND_B, ply-3, &ip ) ) + { + case 1: + DOut( ply, "LOOP PHI: %s", str_CSA_move(*pmove) ); + pnode->children[n].is_loop = 1; + pnode->children[n].is_phi_loop = 1; + pnode->children[n].phi = pdfpn_tree->anode[ip].phi; + assert( pnode->delta <= pdfpn_tree->anode[ip].phi ); + break; + + default: + dfpn_hash_probe( pdfpn_tree, &pnode->children[n], ply, + Flip(pnode->turn) ); + } + + if ( pnode->children[n].nodes == 0 + && ! pnode->children[n].is_loop + && ! InCheck(Flip(pnode->turn)) ) { + unsigned int move = IsMateIn1Ply(Flip(pnode->turn)); + if ( move ) { + + unsigned int from = I2From(move); + unsigned int min_hand_b = pnode->turn ? 0 : HAND_B + HAND_W; + if ( nsquare <= from ) { + unsigned int pc = From2Drop(from); + if ( pnode->turn ) { min_hand_b += hand_tbl[pc]; } + else { min_hand_b -= hand_tbl[pc]; } + } + pnode->children[n].min_hand_b = min_hand_b; + pnode->children[n].nodes = 1; + pnode->children[n].phi = 0; + pnode->children[n].delta = INF; + } + } + + UnMakeMove( pnode->turn, *pmove, ply ); + n += 1; + } + } + + pnode->nmove = n; + + return 0; +} + + +/* Select the most promising child */ +static void CONV +select_child( const tree_t * restrict ptree, + node_t * restrict pnode, + unsigned int * restrict pphi_c, + unsigned int * restrict pdelta_c, + unsigned int * restrict pdelta_2 ) +{ + int n = pnode->nmove; + int i, sq_king, dist, drank, dfile, to, dist_c; + uint64_t nodes, nodes_c; + unsigned int phi, delta, priori, priori_c; + + *pdelta_c = INF; + *pdelta_2 = INF; + *pphi_c = INF; + priori_c = UINT_MAX; + nodes_c = UINT64_MAX; + + for ( i = 0; i < n; i++ ) + { + if ( pnode->children[i].is_weak == weak_chuai) { continue; } + + phi = pnode->children[i].phi; + delta = pnode->children[i].delta; + nodes = pnode->children[i].nodes; + priori = pnode->children[i].priority; + assert( phi <= INF && delta <= INF ); + + /* Store the smallest and second smallest delta in delta_c and delta_2 */ + if ( delta < *pdelta_c + || ( delta == *pdelta_c && nodes < nodes_c ) + || ( delta == *pdelta_c && nodes == nodes_c && phi < *pphi_c ) + || ( delta == *pdelta_c && nodes == nodes_c && phi == *pphi_c + && priori < priori_c ) ) + { + pnode->icurr_c = i; + + *pdelta_2 = *pdelta_c; + *pphi_c = phi; + *pdelta_c = delta; + priori_c = priori; + nodes_c = nodes; + } + else if ( delta < *pdelta_2 ) { *pdelta_2 = delta; } + + assert( phi != INF ); + } + + + if ( *pdelta_c < INF_1 ) { return; } + + + /* expand chuai moves, or current node loses */ + dist_c = INT_MAX; + sq_king = pnode->turn ? SQ_WKING : SQ_BKING; + for ( i = 0; i < n; i++ ) + { + if ( pnode->children[i].is_weak != weak_chuai ) { continue; } + + to = I2To(pnode->children[i].move); + drank = abs( (int)airank[to] - (int)airank[sq_king] ); + dfile = abs( (int)aifile[to] - (int)aifile[sq_king] ); + dist = drank < dfile ? dfile : drank; + phi = pnode->children[i].phi; + delta = pnode->children[i].delta; + assert( phi <= INF && delta <= INF ); + + if ( pnode->phi <= delta ) { continue; } + + if ( dist_c == INT_MAX || dist < dist_c ) + { + pnode->icurr_c = i; + *pphi_c = phi; + *pdelta_c = delta; + dist_c = dist; + } + + assert( phi != INF ); + } + + *pdelta_2 = INF; + pnode->children[pnode->icurr_c].is_weak = 0; +} + + +static unsigned int CONV +min_delta_c( const node_t * restrict pnode ) +{ + int n = pnode->nmove; + unsigned int min = UINT_MAX; + int i; + + for ( i = 0; i < n; i++ ) + { + if ( pnode->children[i].is_weak == weak_chuai ) { continue; } + if ( pnode->children[i].delta < min ) { min = pnode->children[i].delta; } + } + if ( min < INF_1 ) { return min; } + + for ( i = 0; i < n; i++ ) + { + if ( pnode->children[i].is_weak != weak_chuai ) { continue; } + if ( pnode->children[i].delta < min ) { min = pnode->children[i].delta; } + } + + assert( min <= INF ); + return min; +} + + +static unsigned int CONV +sum_phi_c( const node_t * restrict pnode ) +{ + int n = pnode->nmove; + unsigned int sum = 0; + unsigned int value, type, value_chuai; + int i, j, have_inf_1, ntype; + struct { unsigned int value, type; } aphi[ MAX_NMOVE+1 ]; + + ntype = 0; + have_inf_1 = 0; + value_chuai = 0; + sum = 0; + for ( i = 0; i < n; i++ ) + { + type = pnode->children[i].is_weak; + value = pnode->children[i].phi; + + if ( value == INF ) { return INF; } + + if ( value == INF_1 ) { have_inf_1 = 1; } + + if ( have_inf_1 ) { continue; } + if ( value == 0 ) { continue; } + + if ( type == weak_chuai ) + { + if ( value_chuai < value ) { value_chuai = value; } + continue; + } + + if ( type == 0 || value != 1 ) + { + sum += value; + continue; + } + + /* find type in aphi[j].type */ + for ( j = 0, aphi[ntype].type = type; aphi[j].type != type; j++ ); + + + if ( j == ntype ) /* not found */ + { + aphi[j].value = value; + ntype += 1; + } + else if ( aphi[j].value < value ) { aphi[j].value = value; } + } + + + if ( have_inf_1 ) { return INF_1; } + + for ( i = ntype-1; i >= 0; i-- ) { sum += aphi[i].value; } + + if ( INF_1 <= sum ) { sum = UINT_MAX; } + else if ( sum == 0 ) { sum = value_chuai; } + + return sum; +} + + +# if defined(DFPN_DBG) +static void CONV dbg_nodes( const node_t * restrict pnode, int ply ) +{ + char buf[65536]; + int n = pnode->nmove; + int i; + + buf[0] = '\0'; + for ( i = 0; i < n; i++ ) + { + snprintf( buf, 65536, "%s %" PRIu64 "%c ", buf, pnode->children[i].nodes, + pnode->children[i].expanded != 0 ? 'o' : 'x' ); + } + DOut( ply, "NODES:%s", buf ); +} + + +static void CONV dbg_min_delta_c( const node_t * restrict pnode, int ply ) +{ + unsigned int value; + char buf[65536]; + int n = pnode->nmove; + int i; + + buf[0] = '\0'; + for ( i = 0; i < n; i++ ) + { + value = pnode->children[i].delta; + if ( value == INF ) { snprintf( buf, 65536, "%s inf", buf ); } + else if ( value == INF_1 ) { snprintf( buf, 65536, "%s inf-1", buf ); } + else { + snprintf( buf, 65536, "%s %u%s", buf, value, + pnode->children[i].is_delta_loop ? "l" : "" ); + } + } + DOut( ply, "DELTA_C=%u:%s", pnode->min_delta, buf ); +} + + +static void CONV dbg_sum_phi_c( const node_t * restrict pnode, int ply ) +{ + int n = pnode->nmove; + unsigned int value, type, value_chuai; + int i, j, have_inf_1, ntype, iinf_1; + struct { + unsigned int value, type, move; + int is_loop; + } aphi[ MAX_NMOVE+1 ]; + + ntype = 0; + have_inf_1 = 0; + value_chuai = 0; + iinf_1 = 0; + for ( i = 0; i < n; i++ ) + { + type = pnode->children[i].is_weak; + value = pnode->children[i].phi; + + if ( value == INF ) + { + DOut( ply, "PHI_C=inf: %s", + str_CSA_move(pnode->children[i].move) ); + return; + } + + if ( value == INF_1 ) { have_inf_1 = 1; iinf_1 = i; } + + if ( have_inf_1 ) { continue; } + + if ( type == weak_chuai ) + { + if ( value_chuai < value ) { value_chuai = value; } + continue; + } + if ( type == 0 || value != 1 ) { type = UINT_MAX - i; } + + /* find type in aphi[j].type */ + for ( j = 0, aphi[ntype].type = type; type != aphi[j].type; j++ ); + + + if ( j == ntype ) /* not found */ + { + aphi[j].value = value; + aphi[j].move = pnode->children[i].move; + aphi[j].is_loop = pnode->children[i].is_phi_loop; + ntype += 1; + } + else if ( aphi[j].value < value ) + { + aphi[j].value = value; + aphi[j].move = pnode->children[i].move; + aphi[j].is_loop &= pnode->children[i].is_phi_loop; + } + } + + if ( have_inf_1 ) + { + DOut( ply, "PHI_C=inf-1: %s", + str_CSA_move(pnode->children[iinf_1].move) ); + } + else { + char buf[65536]; + + buf[0] = '\0'; + for ( i = 0; i < ntype; i++ ) + { + snprintf ( buf, 65536, "%s %s(%u%s)", buf, + str_CSA_move(aphi[i].move), aphi[i].value, + aphi[i].is_loop ? "l" : "" ); + } + + if ( value_chuai ) + { + snprintf( buf, 65536, "%s CHUAI(%u)", buf, value_chuai ); + } + DOut( ply, "PHI_C=%u:%s", pnode->sum_phi, buf ); + } +} + + +static void CONV +dbg_out_move_seq( const node_t * restrict nodes, int ply ) +{ + char buf[65536]; + int i; + + buf[0] = '\0'; + for ( i = 1; i < ply; i++ ) + { + unsigned int move = nodes[i].children[nodes[i].icurr_c].move; + snprintf( buf, 65536, "%s %s", buf, str_CSA_move(move) ); + } + DOut( ply, "HIST:%s", buf ); +} + +# endif + +#endif /* DFPN */ diff --git a/dfpn.h b/dfpn.h new file mode 100644 index 0000000..f3695ac --- /dev/null +++ b/dfpn.h @@ -0,0 +1,106 @@ +#if defined(DFPN) +#ifndef DFPN_H +#define DFPN_H + +/* #define DFPN_DBG */ + +#define DFPN_AGE_MASK 0xffU +#define INF 0x7fffffU +#define INF_1 0x7ffffeU +#define MAX_NMOVE 256 + +#define DFPN_ERRNO_MAXNODE -101 +#define DFPN_ERRNO_MAXPLY -102 +#define DFPN_ERRNO_SUMPHI -103 +#define DFPN_ERRNO_DELTA2P -104 +#define DFPN_ERRNO_SIGNAL -105 + +/* #define DFPN_HASH_MASK 0x00fffffU */ /* 24MByte */ +/* #define DFPN_HASH_MASK 0x01fffffU */ /* 48MByte */ +/* #define DFPN_HASH_MASK 0x03fffffU */ /* 96MByte */ +/* #define DFPN_HASH_MASK 0x07fffffU */ /* 192MByte */ +/* #define DFPN_HASH_MASK 0x0ffffffU */ /* 384MByte */ +/* #define DFPN_HASH_MASK 0x1ffffffU */ /* 768MByte */ +/* #define DFPN_HASH_MASK 0x3ffffffU */ /* 1536MByte */ +#define DFPN_NODES_MASK UINT64_C(0x1fffffffffff) +#define DFPN_NUM_REHASH 32 + + +#if defined(DFPN_DBG) +extern int dbg_flag; +# define DOut(ply,fmt,...) if ( dbg_flag && ply <= 64 ) out( "%-*d" fmt "\n", 2*ply, ply, __VA_ARGS__ ) +#else +# define DOut( ... ) +#endif + +/*#define DFPNSignKey(word1, word2, word3) word1 = ( word1 ^ word2 ^ word3 )*/ +#define DFPNSignKey(word1, word2, word3) + +typedef struct { uint64_t word1, word2, word3; } dfpn_hash_entry_t; + +typedef struct { + uint64_t hash_key; + uint64_t nodes; + uint64_t expanded; + unsigned int hand_b; + unsigned int min_hand_b; + unsigned int move; + unsigned int phi; + unsigned int delta; + unsigned int priority; + int is_delta_loop; + int is_phi_loop; + int is_loop; + int is_weak; +} child_t; + + +typedef struct { + child_t * restrict children; + uint64_t hash_key; + uint64_t nodes; + uint64_t new_expansion; + unsigned int min_hand_b; + unsigned int hand_b; + unsigned int phi; + unsigned int delta; + unsigned int sum_phi; + unsigned int min_delta; + int is_delta_loop; + int is_phi_loop; + int nmove, turn, icurr_c; +} node_t; + + +typedef struct { + uint64_t node_limit; + int turn_or; + int root_ply; + unsigned int sum_phi_max; + child_t child_tbl[ MAX_NMOVE * PLY_MAX ]; + node_t anode[ PLY_MAX ]; +} dfpn_tree_t; + + +enum { weak_chuai = 1, weak_drop = 100 }; + + +void CONV dfpn_hash_probe( const dfpn_tree_t * restrict pdfpn_tree, + child_t * restrict pchild, int ply, int turn ); +void CONV dfpn_hash_store( const tree_t * restrict ptree, + dfpn_tree_t * restrict pdfpn_tree, + int ply ); +int CONV dfpn_detect_rep( const dfpn_tree_t * restrict pdfpn_tree, + uint64_t hash_key, unsigned int hand_b, + int ply, int * restrict ip ); +unsigned int CONV dfpn_max_hand_b( unsigned int hand_b, unsigned hand_w ); +unsigned int CONV dfpn_max_hand_w( unsigned int hand_b, unsigned hand_w ); +float CONV dfpn_hash_sat( void ); + +extern dfpn_hash_entry_t * restrict dfpn_hash_tbl; +extern unsigned int dfpn_hash_mask; +extern unsigned int dfpn_hash_age; +extern const unsigned int hand_tbl[16]; + +#endif /* DFPN_H */ +#endif /* DFPN */ diff --git a/dfpnhash.c b/dfpnhash.c new file mode 100644 index 0000000..a82d86f --- /dev/null +++ b/dfpnhash.c @@ -0,0 +1,623 @@ +#if defined(DFPN) +#include +#include +#include "shogi.h" +#include "dfpn.h" + +#if defined(DEBUG) +static int CONV dbg_is_hand_valid( unsigned int hand ); +#endif + +static unsigned int CONV calc_hand_win( const node_t *pnode, + unsigned int hand_b, + unsigned int hand_w ); +static unsigned int CONV calc_hand_lose( const node_t * restrict pnode, + unsigned int hand_b, + unsigned int hand_w ); +static unsigned int CONV hand_or( unsigned int a, unsigned int b ); +static unsigned int CONV hand_and( unsigned int a, unsigned int b ); +static int CONV dfpn_hand_supe( unsigned int u, unsigned int uref ); + +const unsigned int hand_tbl[16] = { + 0, flag_hand_pawn, flag_hand_lance, flag_hand_knight, + flag_hand_silver, flag_hand_gold, flag_hand_bishop, flag_hand_rook, + 0, flag_hand_pawn, flag_hand_lance, flag_hand_knight, + flag_hand_silver, 0, flag_hand_bishop, flag_hand_rook }; + +static const unsigned int hand_mask[16] = { + 0, 0x00001fU, 0x0000e0U, 0x000700U, + 0x003800U, 0x01c000U, 0x060000U, 0x180000U, + 0, 0x00001fU, 0x0000e0U, 0x000700U, + 0x003800U, 0, 0x060000U, 0x180000U }; + + +int CONV dfpn_ini_hash( void ) +{ + size_t size; + unsigned int u, n2; + + if ( dfpn_hash_tbl != NULL ) { memory_free( dfpn_hash_tbl ); } + n2 = 1U << dfpn_hash_log2; + size = sizeof( dfpn_hash_entry_t ) * ( n2 + 1 + DFPN_NUM_REHASH ); + + dfpn_hash_tbl = memory_alloc( size ); + if ( dfpn_hash_tbl == NULL ) { return -1; } + + dfpn_hash_mask = n2 -1; + dfpn_hash_age = 0; + for ( u = 0; u < n2 + 1 + DFPN_NUM_REHASH; u++ ) + { + dfpn_hash_tbl[u].word3 = 0; + } + + Out( "DFPN Table Entries = %uk (%uMB)\n", + ( dfpn_hash_mask + 1U ) / 1024U, size / ( 1024U * 1024U ) ); + + return 1; +} + + +float CONV dfpn_hash_sat( void ) +{ + uint64_t nodes; + unsigned int u, n, used, age; + + if ( dfpn_hash_mask >= 0x10000U ) { n = 0x10000U; } + else { n = dfpn_hash_mask + 1U; } + + used = 0; + for ( u = 0; u < n; u++ ) + { + nodes = dfpn_hash_tbl[u].word3 & DFPN_NODES_MASK; + age = (unsigned int)( dfpn_hash_tbl[u].word2 >> 46 ) & DFPN_AGE_MASK; + if ( nodes != 0 && age == dfpn_hash_age ) { used += 1; } + } + + return (float)( used * 100U ) / (float)n; +} + + +# if defined(_MSC_VER) +# pragma warning(disable:4100) +# elif defined(__ICC) +# pragma warning(disable:869) +# endif +void CONV dfpn_hash_probe( const dfpn_tree_t * restrict pdfpn_tree, + child_t * restrict pchild, int ply, int turn ) +{ + uint64_t hash_key_curr, word1, word2, word3, hash_key, nodes; + unsigned int index, hand_b, phi, delta, u, offset, hand_b_curr; + int relation, is_phi_loop, is_delta_loop; + +#define REL_SUPE 0 +#define REL_INFE 1 + + if ( pdfpn_tree->turn_or == turn ) { hash_key_curr = pchild->hash_key; } + else { hash_key_curr = ~pchild->hash_key; } + hand_b_curr = pchild->hand_b; + + index = (unsigned int)hash_key_curr & dfpn_hash_mask; + for ( u = index; u < index + DFPN_NUM_REHASH; u++ ) { + + word1 = dfpn_hash_tbl[u].word1; + word2 = dfpn_hash_tbl[u].word2; + word3 = dfpn_hash_tbl[u].word3; + DFPNSignKey( word1, word2, word3 ); + + hash_key = word1 & ~UINT64_C(0x1fffff); + hand_b = (unsigned int)word1 & 0x1fffffU; + delta = (unsigned int)word2 & INF; + phi = (unsigned int)( word2 >> 23 ) & INF; + offset = (unsigned int)( word2 >> 54 ) & 0xffU; + is_phi_loop = (int)( word2 >> 63 ); + is_delta_loop = (int)( word2 >> 62 ) & 1; + nodes = word3 & DFPN_NODES_MASK; + assert( offset <= u ); + + if ( nodes == 0 ) { break; } + if ( index + offset < u ) { break; } + if ( index + offset > u ) { continue; } + if ( hash_key != ( hash_key_curr & ~UINT64_C(0x1fffff) ) ) { continue; } + + if ( hand_b_curr == hand_b ) + { + pchild->phi = phi; + pchild->delta = delta; + pchild->nodes = nodes; + pchild->min_hand_b = hand_b; + pchild->is_phi_loop = is_phi_loop; + pchild->is_delta_loop = is_delta_loop; + DOut( ply, "HASH EXACT at %u+%u, %x, %x: [%u,%u] %u %x %c %c", + index, offset, (unsigned int)hash_key_curr, hand_b_curr, phi, + delta, (unsigned int)nodes, pchild->min_hand_b, + is_phi_loop ? 'y' : 'n', is_delta_loop ? 'y' : 'n' ); + return; + } + + if ( dfpn_hand_supe( hand_b_curr, hand_b ) ) { relation = REL_SUPE; } + else if ( dfpn_hand_supe( hand_b, hand_b_curr ) ) { relation = REL_INFE; } + else continue; + + if ( turn ) { relation = relation ^ 1; } + + if ( relation == REL_SUPE && phi == 0 && delta == INF ) + { + pchild->phi = phi; + pchild->delta = delta; + pchild->nodes = nodes; + pchild->min_hand_b = hand_b; + pchild->is_phi_loop = is_phi_loop; + pchild->is_delta_loop = is_delta_loop; + DOut( ply, "HASH SUPE at %u+%u, %x, %x: [%u,%u] %u %x n n", index, + offset, (unsigned int)hash_key_curr, hand_b_curr, phi, delta, + (unsigned int)nodes, pchild->min_hand_b ); + return; + } + + if ( relation == REL_INFE && phi == INF && delta == 0 ) + { + pchild->phi = phi; + pchild->delta = delta; + pchild->nodes = nodes; + pchild->min_hand_b = hand_b; + pchild->is_phi_loop = is_phi_loop; + pchild->is_delta_loop = is_delta_loop; + DOut( ply, "HASH INFE at %u+%u, %x, %x: [%u,%u] %u %x n n", index, + offset, (unsigned int)hash_key_curr, hand_b_curr, phi, delta, + (unsigned int)nodes, pchild->min_hand_b ); + return; + } + } +} +# if defined(_MSC_VER) +# pragma warning(default:4100) +# elif defined(__ICC) +# pragma warning(default:869) +# endif + + +void CONV dfpn_hash_store( const tree_t * restrict ptree, + dfpn_tree_t * restrict pdfpn_tree, int ply ) +{ + node_t * restrict pnode = pdfpn_tree->anode + ply; + uint64_t word1, word2, word3, min_nodes, nodes, hash_key; + uint64_t tmp1, tmp2, tmp3; + unsigned int index, min_u, u, u1, hand_b, min_hand_b, offset, age; + int turn_win, i, n, is_phi_loop, is_delta_loop; + + assert( pnode->phi != INF || pnode->delta != INF ); + + if ( pdfpn_tree->turn_or == pnode->turn ) { hash_key = HASH_KEY; } + else { hash_key = ~HASH_KEY; } + + word1 = ( hash_key & ~UINT64_C(0x1fffff) ); + index = (unsigned int)hash_key & dfpn_hash_mask; + + if ( pnode->phi == 0 && pnode->delta == INF ) + { + min_hand_b = calc_hand_win( pnode, HAND_B, HAND_W ); + turn_win = pnode->turn; + is_phi_loop = 0; + is_delta_loop = 0; + word1 |= (uint64_t)min_hand_b; + } + else if ( pnode->phi == INF && pnode->delta == 0 ) + { + min_hand_b = calc_hand_lose( pnode, HAND_B, HAND_W ); + turn_win = Flip(pnode->turn); + is_phi_loop = 0; + is_delta_loop = 0; + word1 |= (uint64_t)min_hand_b; + } + else { + min_hand_b = HAND_B; + word1 |= (uint64_t)min_hand_b; + is_phi_loop = 1; + is_delta_loop = 0; + n = pnode->nmove; + for ( i = 0; i < n; i++ ) + { + if ( pnode->phi == pnode->children[i].delta ) + { + is_phi_loop &= pnode->children[i].is_delta_loop; + } + is_delta_loop |= pnode->children[i].is_phi_loop; + } + + goto skip; + } + + for ( u = index; u < index + DFPN_NUM_REHASH; u++ ) { + + tmp1 = dfpn_hash_tbl[u].word1; + tmp2 = dfpn_hash_tbl[u].word2; + tmp3 = dfpn_hash_tbl[u].word3; + DFPNSignKey( tmp1, tmp2, tmp3 ); + + nodes = tmp3 & DFPN_NODES_MASK; + offset = ( tmp2 >> 54 ) & 0xffU; + + if ( nodes == 0 ) { continue; } + if ( u != index + offset ) { continue; } + if ( word1 == tmp1 ) { continue; } + if ( ( word1 & ~UINT64_C(0x1fffff) ) != ( tmp1 & ~UINT64_C(0x1fffff) ) ) + { + continue; + } + + hand_b = (unsigned int)tmp1 & 0x1fffffU; + assert( min_hand_b != hand_b ); + + if ( ! turn_win && ! dfpn_hand_supe( hand_b, min_hand_b ) ) { continue; } + if ( turn_win && ! dfpn_hand_supe( min_hand_b, hand_b ) ) { continue; } + + /* sort by index */ + for ( u1 = u+1;; u1++ ) { + + tmp1 = dfpn_hash_tbl[u1].word1; + tmp2 = dfpn_hash_tbl[u1].word2; + tmp3 = dfpn_hash_tbl[u1].word3; + DFPNSignKey( tmp1, tmp2, tmp3 ); + + nodes = tmp3 & DFPN_NODES_MASK; + if ( nodes == 0 ) { break; } + + assert( u1 < DFPN_NUM_REHASH + 1 + dfpn_hash_mask ); + offset = (unsigned int)( tmp2 >> 54 ) & 0xffU; + if ( offset == 0 ) { break; } + + tmp2 &= ~( (uint64_t)0xffU << 54 ); + tmp2 |= (uint64_t)( offset - 1U ) << 54; + + DFPNSignKey( tmp1, tmp2, tmp3 ); + dfpn_hash_tbl[u1-1].word1 = tmp1; + dfpn_hash_tbl[u1-1].word2 = tmp2; + dfpn_hash_tbl[u1-1].word3 = tmp3; + } + + dfpn_hash_tbl[u1-1].word3 = 0; + } + + skip: + + min_nodes = UINT64_MAX; + min_u = UINT_MAX; + for ( u = index; u < index + DFPN_NUM_REHASH * 3U; u++ ) + { + if ( u == dfpn_hash_mask + 2 + DFPN_NUM_REHASH ) { break; } + + tmp1 = dfpn_hash_tbl[u].word1; + tmp2 = dfpn_hash_tbl[u].word2; + tmp3 = dfpn_hash_tbl[u].word3; + DFPNSignKey( tmp1, tmp2, tmp3 ); + + offset = ( tmp2 >> 54 ) & 0xffU; + age = (unsigned int)( tmp2 >> 46 ) & DFPN_AGE_MASK; + nodes = tmp3 & DFPN_NODES_MASK; + + assert( offset <= u ); + + if ( nodes == 0 + || age != dfpn_hash_age + || ( index == u - offset && word1 == tmp1 ) ) + { + min_u = u; + break; + } + + if ( index <= u - offset && offset == DFPN_NUM_REHASH - 1 ) { break; } + + if ( nodes < min_nodes ) + { + min_nodes = nodes; + min_u = u; + } + } + + if ( min_u == UINT_MAX ) + { + out_warning( "HASH ERROR in $s line %d", __FILE__, __LINE__ ); + min_u = index; + } + + /* sort by index */ + tmp1 = dfpn_hash_tbl[min_u].word1; + tmp2 = dfpn_hash_tbl[min_u].word2; + tmp3 = dfpn_hash_tbl[min_u].word3; + DFPNSignKey( tmp1, tmp2, tmp3 ); + offset = (unsigned int)( tmp2 >> 54 ) & 0xffU; + min_nodes = tmp3 & DFPN_NODES_MASK; + age = (unsigned int)(tmp2 >> 46) & DFPN_AGE_MASK; + + if ( min_nodes == 0 + || age != dfpn_hash_age + || index <= min_u - offset ) { + + for ( ; index < min_u; min_u -= 1 ) { + + assert( dfpn_hash_tbl[min_u-1].word2 != 0 ); + tmp1 = dfpn_hash_tbl[min_u-1].word1; + tmp2 = dfpn_hash_tbl[min_u-1].word2; + tmp3 = dfpn_hash_tbl[min_u-1].word3; + DFPNSignKey( tmp1, tmp2, tmp3 ); + + offset = (unsigned int)( tmp2 >> 54 ) & 0xffU; + assert( offset <= min_u - 1 ); + if ( min_u - 1 - offset <= index ) { break; } + + assert( offset + 1U < DFPN_NUM_REHASH ); + + dfpn_hash_tbl[min_u-1].word3 = 0; + + tmp2 &= ~( (uint64_t)0xffU << 54 ); + tmp2 |= (uint64_t)( offset + 1U ) << 54; + + DFPNSignKey( tmp1, tmp2, tmp3 ); + dfpn_hash_tbl[min_u].word1 = tmp1; + dfpn_hash_tbl[min_u].word2 = tmp2; + dfpn_hash_tbl[min_u].word3 = tmp3; + } + + } else { + + for ( ; min_u < index + DFPN_NUM_REHASH - 1; min_u += 1 ) { + + assert( dfpn_hash_tbl[min_u+1].word2 != 0 ); + tmp1 = dfpn_hash_tbl[min_u+1].word1; + tmp2 = dfpn_hash_tbl[min_u+1].word2; + tmp3 = dfpn_hash_tbl[min_u+1].word3; + DFPNSignKey( tmp1, tmp2, tmp3 ); + + offset = (unsigned int)( tmp2 >> 54 ) & 0xffU; + assert( offset <= min_u + 1 ); + if ( index <= min_u + 1 - offset ) { break; } + + assert( offset != 0 ); + + dfpn_hash_tbl[min_u+1].word3 = 0; + + tmp2 &= ~( (uint64_t)0xffU << 54 ); + tmp2 |= (uint64_t)( offset - 1U ) << 54; + + DFPNSignKey( tmp1, tmp2, tmp3 ); + dfpn_hash_tbl[min_u].word1 = tmp1; + dfpn_hash_tbl[min_u].word2 = tmp2; + dfpn_hash_tbl[min_u].word3 = tmp3; + } + } + + assert( min_nodes != UINT_MAX ); + assert( pnode->phi <= INF && pnode->delta <= INF ); + assert( index <= min_u && min_u - index < DFPN_NUM_REHASH ); + + offset = min_u - index; + pnode->is_phi_loop = is_phi_loop; + pnode->is_delta_loop = is_delta_loop; + pnode->min_hand_b = min_hand_b; + + word2 = (uint64_t)is_phi_loop << 63; + word2 |= (uint64_t)is_delta_loop << 62; + word2 |= (uint64_t)offset << 54; + word2 |= (uint64_t)dfpn_hash_age << 46; + word2 |= (uint64_t)pnode->phi << 23; + word2 |= (uint64_t)pnode->delta << 0; + word3 = pnode->nodes; + + DFPNSignKey( word1, word2, word3 ); + dfpn_hash_tbl[min_u].word1 = word1; + dfpn_hash_tbl[min_u].word2 = word2; + dfpn_hash_tbl[min_u].word3 = word3; + + DOut( ply, "STORE[%u+%u] %x, %x: [%d,%d] %c %c", + index, offset, (unsigned int)hash_key, min_hand_b, pnode->phi, + pnode->delta, is_phi_loop ? 'y': 'n', is_delta_loop ? 'y' : 'n' ); +} + + +unsigned int CONV +dfpn_max_hand_b( unsigned int hand_b, unsigned hand_w ) +{ + unsigned hand_tot = hand_b + hand_w; + unsigned hand = 0; + int i; + + for ( i = pawn; i <= rook; i++ ) + if ( hand_b & hand_mask[i] ) { hand += hand_tot & hand_mask[i]; } + + return hand; +} + + +unsigned int CONV +dfpn_max_hand_w( unsigned int hand_b, unsigned hand_w ) +{ + unsigned hand_tot = hand_b + hand_w; + unsigned hand = hand_b + hand_w; + int i; + + for ( i = pawn; i <= rook; i++ ) + if ( hand_w & hand_mask[i] ) { hand -= hand_tot & hand_mask[i]; } + + return hand; +} + + +int CONV +dfpn_detect_rep( const dfpn_tree_t * restrict pdfpn_tree, uint64_t hash_key, + unsigned int hand_b, int ply, int * restrict ip ) +{ + const node_t * restrict pnode; + + for ( *ip = ply; *ip >= pdfpn_tree->root_ply; *ip -=2 ) + { + pnode = pdfpn_tree->anode + *ip; + if ( pnode->hash_key == hash_key + && pnode->hand_b == hand_b ) { return 1; } + } + + return 0; +} + + +static int CONV +dfpn_hand_supe( unsigned int u, unsigned int uref ) +{ + if ( IsHandPawn(u) >= IsHandPawn(uref) + && IsHandLance(u) >= IsHandLance(uref) + && IsHandKnight(u) >= IsHandKnight(uref) + && IsHandSilver(u) >= IsHandSilver(uref) + && IsHandGold(u) >= IsHandGold(uref) + && IsHandBishop(u) >= IsHandBishop(uref) + && IsHandRook(u) >= IsHandRook(uref) ) { return 1; } + + return 0; +} + + +static unsigned int CONV +calc_hand_lose( const node_t * restrict pnode, + unsigned int hand_b, unsigned int hand_w ) +{ + int i, n; + unsigned int hand_tot = hand_b + hand_w; + unsigned int hand; + + n = pnode->nmove; + + if ( pnode->turn ) { + + hand = dfpn_max_hand_w( hand_b, hand_w ); + + for ( i = 0; i < n; i++ ) { + hand = hand_or( hand, pnode->children[i].min_hand_b ); + } + hand = hand_and( hand_tot, hand ); + + assert( dbg_is_hand_valid( hand ) && dfpn_hand_supe( hand_b, hand ) ); + + } else { + + hand = dfpn_max_hand_b( hand_b, hand_w ); + + for ( i = 0; i < n; i++ ) { + + unsigned int h0 = pnode->children[i].min_hand_b; + int from = (int)I2From(pnode->children[i].move); + int pc_cap = (int)UToCap(pnode->children[i].move); + + if ( from >= nsquare ) { h0 += hand_tbl[From2Drop(from)]; } + else if ( h0 & hand_mask[pc_cap] ) { h0 -= hand_tbl[pc_cap]; } + + hand = hand_and( hand, h0 ); + } + + assert( dbg_is_hand_valid( hand ) && dfpn_hand_supe( hand, hand_b ) ); + } + + return hand; +} + + +static unsigned int CONV +calc_hand_win( const node_t *pnode, unsigned int hand_b, unsigned int hand_w ) +{ + int i, n; + unsigned int hand, h0; + + n = pnode->nmove; + + if ( pnode->turn ) { + + hand = hand_b + hand_w; + + for ( i = 0; i < n; i++ ) { + + if ( pnode->children[i].phi != INF ) { continue; } + if ( pnode->children[i].delta != 0 ) { continue; } + + h0 = hand_and( hand_b + hand_w, pnode->children[i].min_hand_b ); + if ( dfpn_hand_supe( hand, h0 ) ) { hand = h0; } + } + + assert( dbg_is_hand_valid(hand) && dfpn_hand_supe(hand, hand_b) ); + + } else { + + hand = 0; + + for ( i = 0; i < n; i++ ) { + + int from, pc_cap; + + if ( pnode->children[i].phi != INF ) { continue; } + if ( pnode->children[i].delta != 0 ) { continue; } + + h0 = pnode->children[i].min_hand_b; + from = (int)I2From(pnode->children[i].move); + pc_cap = (int)UToCap(pnode->children[i].move); + + if ( from >= nsquare ) { h0 += hand_tbl[From2Drop(from)]; } + else if ( h0 & hand_mask[pc_cap] ) { h0 -= hand_tbl[pc_cap]; } + + h0 = hand_and( hand_b + hand_w, h0 ); + + if ( dfpn_hand_supe( h0, hand ) ) { hand = h0; } + } + + assert( dbg_is_hand_valid( hand ) && dfpn_hand_supe( hand_b, hand ) ); + } + + return hand; +} + + +static unsigned int CONV +hand_or( unsigned int a, unsigned int b ) +{ + unsigned int c, u1, u2; + int i; + + c = 0; + for ( i = pawn; i <= rook; i++ ) + { + u1 = hand_mask[i] & a; + u2 = hand_mask[i] & b; + c += u2 < u1 ? u1 : u2; + } + + return c; +} + + +static unsigned int CONV +hand_and( unsigned int a, unsigned int b ) +{ + unsigned int c, u1, u2; + int i; + + c = 0; + for ( i = pawn; i <= rook; i++ ) + { + u1 = hand_mask[i] & a; + u2 = hand_mask[i] & b; + c += u1 < u2 ? u1 : u2; + } + + return c; +} + +#if defined(DEBUG) +static int CONV +dbg_is_hand_valid( unsigned int hand ) +{ + return ( I2HandPawn(hand) <= 18U + && I2HandLance(hand) <= 4U + && I2HandKnight(hand) <= 4U + && I2HandSilver(hand) <= 4U + && I2HandGold(hand) <= 4U + && I2HandBishop(hand) <= 2U + && I2HandRook(hand) <= 2U ); +} +#endif + +#endif /* DFPN */