--- /dev/null
+#if defined(DFPN)
+
+#include <limits.h>
+#include <assert.h>
+#include <string.h>
+#include <stdlib.h>
+#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 */
--- /dev/null
+#if defined(DFPN)
+#include <limits.h>
+#include <assert.h>
+#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 */
projects / bonanza.git / commitdiff