dfpn.c

   1 #if defined(DFPN)
   2
   3 #include <limits.h>
   4 #include <assert.h>
   5 #include <string.h>
   6 #include <stdlib.h>
   7 #include "shogi.h"
   8 #include "dfpn.h"
   9
  10 dfpn_hash_entry_t * restrict dfpn_hash_tbl = NULL;
  11 unsigned int dfpn_hash_age;
  12 unsigned int dfpn_hash_mask;
  13
  14 #if defined(DFPN_DBG)
  15 int dbg_flag = 1;
  16 static void CONV dbg_out_move_seq( const node_t * restrict nodes, int ply );
  17 static void CONV dbg_min_delta_c( const node_t * restrict pnode, int ply );
  18 static void CONV dbg_sum_phi_c( const node_t * restrict pnode, int ply );
  19 static void CONV dbg_nodes( const node_t * restrict pnode, int ply );
  20 #endif
  21
  22
  23 static int CONV useless_delta_ticking( node_t * restrict pnode );
  24 static unsigned int CONV min_delta_c( const node_t * restrict pnode );
  25 static unsigned int CONV sum_phi_c( const node_t * restrict pnode );
  26 static int CONV init_children( tree_t * restrict ptree,
  27                                dfpn_tree_t * restrict pdfpn_tree, int ply );
  28 static int CONV mid( tree_t * restrict ptree,
  29                      dfpn_tree_t * restrict pdfpn_tree, int ply );
  30 static void CONV select_child( const tree_t * restrict ptree,
  31                                node_t * restrict pnode_c,
  32                                unsigned int * restrict pphi_c,
  33                                unsigned int * restrict pdelta_c,
  34                                unsigned int * restrict pdelta_2 );
  35 static void CONV num2str( char buf[16], unsigned int num );
  36
  37 #if defined(TLP)
  38 static dfpn_tree_t dfpn_tree[ TLP_MAX_THREADS ];
  39 #else
  40 static dfpn_tree_t dfpn_tree;
  41 #endif
  42
  43 int CONV
  44 dfpn( tree_t * restrict ptree, int turn, int ply )
  45 {
  46   dfpn_tree_t * restrict pdfpn_tree;
  47   node_t * restrict pnode;
  48   float fcpu_percent, fnps, fsat;
  49   unsigned int cpu0, cpu1, elapse0, elapse1, u;
  50   int iret, i;
  51
  52   if ( get_cputime( &cpu0 )    < 0 ) { return -1; }
  53   if ( get_elapsed( &elapse0 ) < 0 ) { return -1; }
  54
  55   u =  node_per_second / 16U;
  56   if      ( u > TIME_CHECK_MAX_NODE ) { u = TIME_CHECK_MAX_NODE; }
  57   else if ( u < TIME_CHECK_MIN_NODE ) { u = TIME_CHECK_MIN_NODE; }
  58   node_next_signal = u;
  59   node_last_check  = 0;
  60   root_abort       = 0;
  61   time_max_limit   = UINT_MAX;
  62   time_limit       = UINT_MAX;
  63   game_status     &= ~( flag_move_now | flag_suspend | flag_search_error );
  64   game_status     |= flag_thinking;
  65
  66 #if defined(TLP)
  67   pdfpn_tree = &dfpn_tree[ptree->tlp_id];
  68 #else
  69   pdfpn_tree = &dfpn_tree;
  70 #endif
  71   ptree->node_searched = 0;
  72
  73   pdfpn_tree->root_ply     = ply;
  74   pdfpn_tree->turn_or      = turn;
  75   pdfpn_tree->sum_phi_max  = 0;
  76   pdfpn_tree->node_limit   = 50000000;
  77
  78   pnode = pdfpn_tree->anode + ply;
  79   pnode->phi           = INF_1;
  80   pnode->delta         = INF_1;
  81   pnode->turn          = turn;
  82   pnode->children      = pdfpn_tree->child_tbl;
  83   pnode->new_expansion = 1;
  84
  85   assert( 1 <= ply );
  86   assert( pdfpn_tree->node_limit < DFPN_NODES_MASK );
  87   iret = mid( ptree, pdfpn_tree, ply );
  88   if ( 0 <= iret
  89        && pnode->phi   != INF
  90        && pnode->delta != INF )
  91     {
  92       char buf1[16], buf2[16];
  93
  94       num2str( buf1, pnode->phi );
  95       num2str( buf2, pnode->delta );
  96       Out( "Research [%s:%s]\n", buf1, buf2 );
  97       pnode->phi   = INF;
  98       pnode->delta = INF;
  99       iret = mid( ptree, pdfpn_tree, ply );
 100     }
 101
 102   game_status &= ~flag_thinking;
 103
 104   if ( game_status & flag_search_error ) { return -1; }
 105
 106   if  ( iret < 0 )
 107     {
 108       DFPNOut( "UNSOLVED %d\n", iret );
 109       switch ( iret ) {
 110       case DFPN_ERRNO_MAXNODE:  Out( "RESULT: MAX NODE\n" );      break;
 111       case DFPN_ERRNO_MAXPLY:   Out( "RESULT: MAX PLY\n" );       break;
 112       case DFPN_ERRNO_SUMPHI:   Out( "RESULT: MAX SUM_PHI\n" );   break;
 113       case DFPN_ERRNO_DELTA2P:  Out( "RESULT: MAX DELTA2+1\n" );  break;
 114       default:
 115         assert( DFPN_ERRNO_SIGNAL == iret );
 116         Out( "RESULT: SIGNAL\n" );
 117         break;
 118       }
 119     }
 120   else if ( pnode->delta == INF )
 121     {
 122       const char *str;
 123       for ( i = 0; i < pnode->nmove && pnode->children[i].phi != INF; i++ );
 124       assert( i < pnode->nmove );
 125       str = str_CSA_move(pnode->children[i].move);
 126       Out( "RESULT: WIN %s\n", str );
 127       DFPNOut( "WIN %s\n", str );
 128     }
 129   else {
 130     Out( "RESULT: LOSE\n" );
 131     DFPNOut( "LOSE\n" );
 132   }
 133
 134   fsat = dfpn_hash_sat();
 135   if ( 3.0 < fsat )
 136     {
 137       dfpn_hash_age += 1U;
 138       dfpn_hash_age &= DFPN_AGE_MASK;
 139     }
 140
 141   if ( get_cputime( &cpu1 )    < 0 ) { return -1; }
 142   if ( get_elapsed( &elapse1 ) < 0 ) { return -1; }
 143   fcpu_percent     = 100.0F * (float)( cpu1 - cpu0 );
 144   fcpu_percent    /= (float)( elapse1 - elapse0 + 1U );
 145   fnps             = 1000.0F * (float)ptree->node_searched;
 146   fnps            /= (float)( elapse1 - elapse0 + 1U );
 147   node_per_second  = (unsigned int)( fnps + 0.5 );
 148
 149   Out( "n=%" PRIu64 " sat=%3.1f%%", ptree->node_searched, fsat );
 150   Out( " age=%u sum_phi=%u", dfpn_hash_age, pdfpn_tree->sum_phi_max );
 151   Out( " time=%.2f cpu=%.1f%% nps=%.2fK\n",
 152        (float)( elapse1 - elapse0 + 1U ) / 1000.0F,
 153        fcpu_percent, fnps / 1e3F );
 154
 155   Out( "\n" );
 156
 157   return 1;
 158 }
 159
 160
 161 static void CONV
 162 num2str( char buf[16], unsigned int num )
 163 {
 164   if      ( num == INF )   { snprintf( buf, 16, "inf" ); }
 165   else if ( num == INF_1 ) { snprintf( buf, 16, "inf-1" ); }
 166   else                     { snprintf( buf, 16, "%u", num ); }
 167   buf[15] = '\0';
 168 }
 169
 170
 171 static int CONV
 172 mid( tree_t * restrict ptree, dfpn_tree_t * restrict pdfpn_tree, int ply )
 173 {
 174   node_t * restrict pnode = pdfpn_tree->anode + ply;
 175   uint64_t node_searched0;
 176
 177 #if defined(DFPN_DBG)
 178   if ( ptree->node_searched >= 1000000 ) { dbg_flag = 1; }
 179   DOut( ply, "MID START [%u,%u]",
 180         pnode->phi, pnode->delta );
 181   dbg_out_move_seq( pdfpn_tree->anode, ply );
 182 #endif
 183
 184   node_searched0 = ptree->node_searched;
 185
 186   if ( pdfpn_tree->node_limit
 187        <= ++ptree->node_searched ) { return DFPN_ERRNO_MAXNODE; }
 188
 189 #if ! defined(MINIMUM)
 190   if ( ! ( game_status & flag_learning ) )
 191 #endif
 192 #if defined(TLP)
 193     if ( ! ptree->tlp_id )
 194 #endif
 195       if ( node_next_signal < ++node_last_check && detect_signals( ptree ) )
 196         {
 197           return DFPN_ERRNO_SIGNAL;
 198         }
 199
 200   if ( PLY_MAX-4 < ply ) { return DFPN_ERRNO_MAXPLY; }
 201
 202   if ( init_children( ptree, pdfpn_tree, ply ) )
 203     {
 204       pnode->phi   = 0;
 205       pnode->delta = INF;
 206       pnode->nodes = 1;
 207       dfpn_hash_store( ptree, pdfpn_tree, ply );
 208       DOut( ply, "MID END: WIN\n" );
 209       return 1;
 210     }
 211   else if ( ! pnode->nmove )
 212     {
 213       pnode->phi   = INF;
 214       pnode->delta = 0;
 215       pnode->nodes = 1;
 216       dfpn_hash_store( ptree, pdfpn_tree, ply );
 217       DOut( ply, "MID END: LOSE\n" );
 218       return 1;
 219     }
 220
 221   DOut( ply, "NMOVE: %d", pnode->nmove );
 222   pnode->hash_key = HASH_KEY;
 223   pnode->hand_b   = HAND_B;
 224
 225   for ( ;; ) {
 226
 227     node_t * restrict pnode_c = pdfpn_tree->anode + ply + 1;
 228     unsigned int delta_c, phi_c, delta_2;
 229     unsigned int delta_2p1;
 230     int iret;
 231
 232     pnode->min_delta = min_delta_c( pnode );
 233     pnode->sum_phi   = sum_phi_c( pnode );
 234     if ( pnode->sum_phi == UINT_MAX ) { return DFPN_ERRNO_SUMPHI; }
 235
 236     if ( pdfpn_tree->sum_phi_max < pnode->sum_phi && pnode->sum_phi < INF_1 )
 237       {
 238         pdfpn_tree->sum_phi_max = pnode->sum_phi;
 239       }
 240
 241 #if defined(DFPN_DBG)
 242     dbg_nodes( pnode, ply );
 243     dbg_min_delta_c( pnode, ply );
 244     dbg_sum_phi_c( pnode, ply );
 245 #endif
 246
 247     if ( pnode->phi <= pnode->min_delta
 248          || pnode->delta <= pnode->sum_phi ) { break; }
 249
 250
 251     DOut( ply, "PROGRESS: [%u/%u,%u/%u] %u\n",
 252           pnode->min_delta, pnode->phi, pnode->sum_phi, pnode->delta, INF );
 253
 254     select_child( ptree, pnode, &phi_c, &delta_c, &delta_2 );
 255     assert( pdfpn_tree->root_ply == ply
 256             || ! pnode->children[pnode->icurr_c].is_loop );
 257
 258     if ( useless_delta_ticking( pnode ) )
 259       {
 260         DOut( ply, "USELESS DELTA TICKING, DELTA_2=%u", pnode->phi );
 261         delta_2 = pnode->phi;
 262       }
 263
 264     if      ( phi_c        == INF_1 ) { pnode_c->phi = INF; }
 265     else if ( pnode->delta >= INF_1 ) { pnode_c->phi = INF_1; }
 266     else {
 267       assert( phi_c != INF && pnode->sum_phi <= pnode->delta + phi_c );
 268       pnode_c->phi = pnode->delta + phi_c - pnode->sum_phi;
 269     }
 270
 271     if ( delta_c == INF_1 ) { pnode_c->delta = INF; }
 272     else {
 273       if      ( INF_1 - 1 == delta_2 ) { return DFPN_ERRNO_DELTA2P; }
 274       else if ( INF_1     <= delta_2 ) { delta_2p1 = delta_2; }
 275       else                             { delta_2p1 = delta_2 + 1; }
 276
 277       pnode_c->delta = delta_2p1 < pnode->phi ? delta_2p1 : pnode->phi;
 278     }
 279
 280     pnode_c->turn          = Flip(pnode->turn);
 281     pnode_c->children      = pnode->children + pnode->nmove;
 282
 283     if ( pnode->children[pnode->icurr_c].nodes == 0 )
 284       {
 285         pnode_c->new_expansion = 1;
 286       }
 287     else { pnode_c->new_expansion = 0; }
 288
 289     MakeMove( pnode->turn, pnode->children[pnode->icurr_c].move, ply );
 290
 291     iret = mid( ptree, pdfpn_tree, ply+1 );
 292
 293     UnMakeMove( pnode->turn, pnode->children[pnode->icurr_c].move, ply );
 294
 295     if ( SEARCH_ABORT ) { return iret; }
 296     if ( iret < 0 )     { return iret; }
 297
 298     pnode->new_expansion                     += pnode_c->new_expansion;
 299     pnode->children[pnode->icurr_c].expanded  = pnode_c->new_expansion;
 300
 301     dfpn_hash_probe( pdfpn_tree, &pnode->children[pnode->icurr_c], ply,
 302                      Flip(pnode->turn) );
 303   }
 304
 305   pnode->phi   = pnode->min_delta;
 306   pnode->delta = pnode->sum_phi;
 307   pnode->nodes = ptree->node_searched - node_searched0;
 308   dfpn_hash_store( ptree, pdfpn_tree, ply );
 309
 310   DOut( ply, "MID END [%u,%u]\n", pnode->min_delta, pnode->sum_phi );
 311   return 1;
 312 }
 313
 314
 315 static int CONV
 316 useless_delta_ticking( node_t * restrict pnode )
 317 {
 318   int i, n;
 319
 320   n = pnode->nmove;
 321   for ( i = 0; i < n; i++ )
 322     {
 323       if ( pnode->phi <= pnode->children[i].delta )   { continue; }
 324       if ( pnode->children[i].is_weak == weak_chuai ) { continue; }
 325       if ( pnode->children[i].is_delta_loop )         { continue; }
 326       if ( pnode->children[i].expanded == 0 )         { continue; }
 327       if ( 2000U < pnode->children[i].delta )         { continue; }
 328
 329       return 0;
 330     }
 331
 332   return 1;
 333 }
 334
 335
 336 static int CONV
 337 init_children( tree_t * restrict ptree, dfpn_tree_t * restrict pdfpn_tree,
 338                int ply )
 339 {
 340   node_t * restrict pnode = pdfpn_tree->anode + ply;
 341   const unsigned int *plast, *pmove;
 342   unsigned int amove[MAX_NMOVE];
 343   int ip, sq_king, n;
 344
 345   n = 0;
 346
 347   if ( pdfpn_tree->turn_or == pnode->turn ) {
 348
 349     sq_king = pnode->turn ? SQ_BKING : SQ_WKING;
 350     plast   = GenCheck( pnode->turn, amove );
 351
 352     for ( pmove = amove; pmove != plast; pmove++ )
 353       {
 354         int from = I2From(*pmove);
 355         int to   = I2To(*pmove);
 356         assert( is_move_valid( ptree, *pmove, pnode->turn ) );
 357
 358         MakeMove( pnode->turn, *pmove, ply );
 359
 360         if ( InCheck(pnode->turn) )
 361           {
 362             UnMakeMove( pnode->turn, *pmove, ply );
 363             continue;
 364           }
 365
 366         if ( pnode->new_expansion
 367              && ! ( pnode->turn ? b_have_evasion(ptree)
 368                                 : w_have_evasion(ptree) ) )
 369           {
 370             pnode->children[0].move  = *pmove;
 371             pnode->children[0].phi   = INF;
 372             pnode->children[0].delta = 0;
 373             pnode->icurr_c           = 0;
 374             pnode->nmove             = 1;
 375             pnode->children[0].min_hand_b
 376               = pnode->turn ? dfpn_max_hand_b( HAND_B, HAND_W )
 377                             : dfpn_max_hand_w( HAND_B, HAND_W );
 378
 379             UnMakeMove( pnode->turn, *pmove, ply );
 380             return 1;
 381           }
 382
 383
 384         if ( from < nsquare )
 385           {
 386             pnode->children[n].is_weak  = 0;
 387             pnode->children[n].priority = 1U;
 388           }
 389         /* drop to next square of the king */
 390         else if ( From2Drop(from) == knight
 391                   || BBContract( abb_king_attacks[sq_king], abb_mask[to] ) )
 392           {
 393             pnode->children[n].is_weak  = 0;
 394             pnode->children[n].priority = 1U;
 395           }
 396         /* check by piece drop from far way */
 397         else {
 398           pnode->children[n].is_weak
 399             = weak_drop + ( adirec[sq_king][to] << 1 ) + ( sq_king < to );
 400           pnode->children[n].priority = 1U;
 401         }
 402
 403         pnode->children[n].nodes         = 0;
 404         pnode->children[n].phi           = 1U;
 405         pnode->children[n].delta         = 1U;
 406         pnode->children[n].is_loop       = 0;
 407         pnode->children[n].is_phi_loop   = 0;
 408         pnode->children[n].is_delta_loop = 0;
 409         pnode->children[n].hash_key      = HASH_KEY;
 410         pnode->children[n].hand_b        = HAND_B;
 411         pnode->children[n].min_hand_b    = HAND_B;
 412         pnode->children[n].move          = *pmove;
 413         pnode->children[n].expanded      = UINT64_MAX;
 414         switch( dfpn_detect_rep( pdfpn_tree, HASH_KEY, HAND_B, ply-3, &ip ) )
 415           {
 416           case 1:
 417             DOut( ply, "LOOP DELTA: %s", str_CSA_move(*pmove) );
 418             pnode->children[n].is_loop       = 1;
 419             pnode->children[n].is_delta_loop = 1;
 420             pnode->children[n].delta = pdfpn_tree->anode[ip].delta;
 421             assert( pnode->phi <= pdfpn_tree->anode[ip].delta );
 422             break;
 423
 424           default:
 425             dfpn_hash_probe( pdfpn_tree, &pnode->children[n], ply,
 426                              Flip(pnode->turn) );
 427           }
 428
 429         UnMakeMove( pnode->turn, *pmove, ply );
 430         n += 1;
 431       }
 432
 433   } else {
 434
 435     bitboard_t bb_intercept;
 436     unsigned int to;
 437
 438     assert( InCheck(pnode->turn) );
 439     plast = GenEvasion( pnode->turn, amove );
 440     BBIni( bb_intercept );
 441
 442     sq_king = pnode->turn ? SQ_WKING : SQ_BKING;
 443
 444     for ( pmove  = amove; pmove != plast; pmove++ )
 445       {
 446         assert( is_move_valid( ptree, *pmove, pnode->turn ) );
 447
 448         MakeMove( pnode->turn, *pmove, ply );
 449
 450         pnode->children[n].is_weak = 0;
 451         to                         = I2To(*pmove);
 452
 453         /* capture or king move */
 454         if ( I2PieceMove(*pmove) == king || UToCap(*pmove) )
 455           {
 456             if ( I2PieceMove(*pmove) == king && UToCap(*pmove) )
 457               {
 458                 pnode->children[n].priority = 2U;
 459               }
 460             else if ( UToCap(*pmove) )
 461               {
 462                 pnode->children[n].priority = 3U;
 463               }
 464             else { pnode->children[n].priority = 4U; }
 465
 466             /* non-intercepts may disproof this node easily. */
 467             if ( pnode->new_expansion
 468                  && ! ( pnode->turn ? b_have_checks(ptree)
 469                                     : w_have_checks(ptree) ) )
 470               {
 471                 pnode->children[0].move  = *pmove;
 472                 pnode->children[0].phi   = INF;
 473                 pnode->children[0].delta = 0;
 474                 pnode->icurr_c           = 0;
 475                 pnode->nmove             = 1;
 476                 pnode->children[0].min_hand_b
 477                   = pnode->turn ? dfpn_max_hand_b( HAND_B, HAND_W )
 478                                 : dfpn_max_hand_w( HAND_B, HAND_W );
 479                 UnMakeMove( pnode->turn, *pmove, ply );
 480                 return 1;
 481               }
 482           }
 483
 484         /* interseptions by move */
 485         else if ( I2From(*pmove) < nsquare )
 486           {
 487             pnode->children[n].priority = 4U;
 488             BBOr( bb_intercept, bb_intercept, abb_mask[to] );
 489           }
 490         /* interseptions by drop */
 491         else if ( BBContract( bb_intercept, abb_mask[to] )
 492                   || BBContract( abb_king_attacks[sq_king],
 493                                  abb_mask[to] ) )
 494           {
 495             pnode->children[n].priority = 5U;
 496             pnode->children[n].is_weak  = weak_drop + to;
 497           }
 498         /* 'chuai' interseptions */
 499         else {
 500           pnode->children[n].priority = 6U;
 501           pnode->children[n].is_weak  = weak_chuai;
 502         }
 503
 504         pnode->children[n].is_loop       = 0;
 505         pnode->children[n].is_phi_loop   = 0;
 506         pnode->children[n].is_delta_loop = 0;
 507         pnode->children[n].hash_key      = HASH_KEY;
 508         pnode->children[n].hand_b        = HAND_B;
 509         pnode->children[n].min_hand_b    = HAND_B;
 510         pnode->children[n].nodes         = 0;
 511         pnode->children[n].phi           = 1U;
 512         pnode->children[n].delta         = 1U;
 513         pnode->children[n].move          = *pmove;
 514         pnode->children[n].expanded      = UINT64_MAX;
 515         switch( dfpn_detect_rep( pdfpn_tree, HASH_KEY, HAND_B, ply-3, &ip ) )
 516           {
 517           case 1:
 518             DOut( ply, "LOOP PHI: %s", str_CSA_move(*pmove) );
 519             pnode->children[n].is_loop     = 1;
 520             pnode->children[n].is_phi_loop = 1;
 521             pnode->children[n].phi = pdfpn_tree->anode[ip].phi;
 522             assert( pnode->delta <= pdfpn_tree->anode[ip].phi );
 523             break;
 524
 525           default:
 526             dfpn_hash_probe( pdfpn_tree, &pnode->children[n], ply,
 527                              Flip(pnode->turn) );
 528           }
 529
 530         if ( pnode->children[n].nodes == 0
 531              && ! pnode->children[n].is_loop
 532              && ! InCheck(Flip(pnode->turn)) ) {
 533           unsigned int move = IsMateIn1Ply(Flip(pnode->turn));
 534           if ( move ) {
 535
 536             unsigned int from       = I2From(move);
 537             unsigned int min_hand_b = pnode->turn ? 0 : HAND_B + HAND_W;
 538             if ( nsquare <= from ) {
 539               unsigned int pc = From2Drop(from);
 540               if ( pnode->turn ) { min_hand_b += hand_tbl[pc]; }
 541               else               { min_hand_b -= hand_tbl[pc]; }
 542             }
 543             pnode->children[n].min_hand_b = min_hand_b;
 544             pnode->children[n].nodes      = 1;
 545             pnode->children[n].phi        = 0;
 546             pnode->children[n].delta      = INF;
 547           }
 548         }
 549
 550         UnMakeMove( pnode->turn, *pmove, ply );
 551         n += 1;
 552       }
 553   }
 554
 555   pnode->nmove = n;
 556
 557   return 0;
 558 }
 559
 560
 561 /* Select the most promising child */
 562 static void CONV
 563 select_child( const tree_t * restrict ptree,
 564               node_t * restrict pnode,
 565               unsigned int * restrict pphi_c,
 566               unsigned int * restrict pdelta_c,
 567               unsigned int * restrict pdelta_2 )
 568 {
 569   int n = pnode->nmove;
 570   int i, sq_king, dist, drank, dfile, to, dist_c;
 571   uint64_t nodes, nodes_c;
 572   unsigned int phi, delta, priori, priori_c;
 573
 574   *pdelta_c = INF;
 575   *pdelta_2 = INF;
 576   *pphi_c   = INF;
 577   priori_c  = UINT_MAX;
 578   nodes_c   = UINT64_MAX;
 579
 580   for ( i = 0; i < n; i++ )
 581     {
 582       if ( pnode->children[i].is_weak == weak_chuai) { continue; }
 583
 584       phi    = pnode->children[i].phi;
 585       delta  = pnode->children[i].delta;
 586       nodes  = pnode->children[i].nodes;
 587       priori = pnode->children[i].priority;
 588       assert( phi <= INF && delta <= INF );
 589
 590       /* Store the smallest and second smallest delta in delta_c and delta_2 */
 591       if ( delta < *pdelta_c
 592            || ( delta == *pdelta_c && nodes < nodes_c )
 593            || ( delta == *pdelta_c && nodes == nodes_c && phi < *pphi_c )
 594            || ( delta == *pdelta_c && nodes == nodes_c && phi == *pphi_c
 595                 && priori < priori_c ) )
 596         {
 597           pnode->icurr_c = i;
 598
 599           *pdelta_2 = *pdelta_c;
 600           *pphi_c   = phi;
 601           *pdelta_c = delta;
 602           priori_c  = priori;
 603           nodes_c   = nodes;
 604         }
 605       else if ( delta < *pdelta_2 ) { *pdelta_2 = delta; }
 606
 607       assert( phi != INF );
 608     }
 609
 610
 611   if ( *pdelta_c < INF_1 ) { return; }
 612
 613
 614   /* expand chuai moves, or current node loses */
 615   dist_c  = INT_MAX;
 616   sq_king = pnode->turn ? SQ_WKING : SQ_BKING;
 617   for ( i = 0; i < n; i++ )
 618     {
 619       if ( pnode->children[i].is_weak != weak_chuai ) { continue; }
 620
 621       to       = I2To(pnode->children[i].move);
 622       drank    = abs( (int)airank[to] - (int)airank[sq_king] );
 623       dfile    = abs( (int)aifile[to] - (int)aifile[sq_king] );
 624       dist     = drank < dfile ? dfile : drank;
 625       phi      = pnode->children[i].phi;
 626       delta    = pnode->children[i].delta;
 627       assert( phi <= INF && delta <= INF );
 628
 629       if ( pnode->phi <= delta ) { continue; }
 630
 631       if ( dist_c == INT_MAX || dist < dist_c )
 632         {
 633           pnode->icurr_c = i;
 634           *pphi_c        = phi;
 635           *pdelta_c      = delta;
 636           dist_c         = dist;
 637         }
 638
 639       assert( phi != INF );
 640     }
 641
 642   *pdelta_2 = INF;
 643   pnode->children[pnode->icurr_c].is_weak = 0;
 644 }
 645
 646
 647 static unsigned int CONV
 648 min_delta_c( const node_t * restrict pnode )
 649 {
 650   int n            = pnode->nmove;
 651   unsigned int min = UINT_MAX;
 652   int i;
 653
 654   for ( i = 0; i < n; i++ )
 655     {
 656       if ( pnode->children[i].is_weak == weak_chuai ) { continue; }
 657       if ( pnode->children[i].delta < min ) { min = pnode->children[i].delta; }
 658     }
 659   if ( min < INF_1 ) { return min; }
 660
 661   for ( i = 0; i < n; i++ )
 662     {
 663       if ( pnode->children[i].is_weak != weak_chuai ) { continue; }
 664       if ( pnode->children[i].delta < min ) { min = pnode->children[i].delta; }
 665     }
 666
 667   assert( min <= INF );
 668   return min;
 669 }
 670
 671
 672 static unsigned int CONV
 673 sum_phi_c( const node_t * restrict pnode )
 674 {
 675   int n            = pnode->nmove;
 676   unsigned int sum = 0;
 677   unsigned int value, type, value_chuai;
 678   int i, j, have_inf_1, ntype;
 679   struct { unsigned int value, type; } aphi[ MAX_NMOVE+1 ];
 680
 681   ntype       = 0;
 682   have_inf_1  = 0;
 683   value_chuai = 0;
 684   sum         = 0;
 685   for ( i = 0; i < n; i++ )
 686     {
 687       type  = pnode->children[i].is_weak;
 688       value = pnode->children[i].phi;
 689
 690       if ( value == INF ) { return INF; }
 691
 692       if ( value == INF_1 ) { have_inf_1 = 1; }
 693
 694       if ( have_inf_1 ) { continue; }
 695       if ( value == 0 ) { continue; }
 696
 697       if ( type == weak_chuai )
 698         {
 699           if ( value_chuai < value ) { value_chuai = value; }
 700           continue;
 701         }
 702
 703       if ( type == 0 || value != 1 )
 704         {
 705           sum += value;
 706           continue;
 707         }
 708
 709       /* find type in aphi[j].type */
 710       for ( j = 0, aphi[ntype].type = type; aphi[j].type != type; j++ );
 711
 712
 713       if ( j == ntype )  /* not found */
 714         {
 715           aphi[j].value  = value;
 716           ntype         += 1;
 717         }
 718       else if ( aphi[j].value < value ) { aphi[j].value = value; }
 719     }
 720
 721
 722   if ( have_inf_1 ) { return INF_1; }
 723
 724   for ( i = ntype-1; i >= 0; i-- ) { sum += aphi[i].value; }
 725
 726   if      ( INF_1 <= sum ) { sum = UINT_MAX; }
 727   else if ( sum == 0 )     { sum = value_chuai; }
 728
 729   return sum;
 730 }
 731
 732
 733 #  if defined(DFPN_DBG)
 734 static void CONV dbg_nodes( const node_t * restrict pnode, int ply )
 735 {
 736   char buf[65536];
 737   int n = pnode->nmove;
 738   int i;
 739
 740   buf[0] = '\0';
 741   for ( i = 0; i < n; i++ )
 742     {
 743       snprintf( buf, 65536, "%s %" PRIu64 "%c ", buf, pnode->children[i].nodes,
 744                 pnode->children[i].expanded != 0 ? 'o' : 'x' );
 745     }
 746   DOut( ply, "NODES:%s", buf );
 747 }
 748
 749
 750 static void CONV dbg_min_delta_c( const node_t * restrict pnode, int ply )
 751 {
 752   unsigned int value;
 753   char buf[65536];
 754   int n = pnode->nmove;
 755   int i;
 756
 757   buf[0] = '\0';
 758   for ( i = 0; i < n; i++ )
 759     {
 760       value = pnode->children[i].delta;
 761       if      ( value == INF )   { snprintf( buf, 65536, "%s inf", buf ); }
 762       else if ( value == INF_1 ) { snprintf( buf, 65536, "%s inf-1", buf ); }
 763       else {
 764         snprintf( buf, 65536, "%s %u%s", buf, value,
 765                   pnode->children[i].is_delta_loop ? "l" : "" );
 766       }
 767     }
 768   DOut( ply, "DELTA_C=%u:%s", pnode->min_delta, buf );
 769 }
 770
 771
 772 static void CONV dbg_sum_phi_c( const node_t * restrict pnode, int ply )
 773 {
 774   int n = pnode->nmove;
 775   unsigned int value, type, value_chuai;
 776   int i, j, have_inf_1, ntype, iinf_1;
 777   struct {
 778     unsigned int value, type, move;
 779     int is_loop;
 780   } aphi[ MAX_NMOVE+1 ];
 781
 782   ntype       = 0;
 783   have_inf_1  = 0;
 784   value_chuai = 0;
 785   iinf_1      = 0;
 786   for ( i = 0; i < n; i++ )
 787     {
 788       type  = pnode->children[i].is_weak;
 789       value = pnode->children[i].phi;
 790
 791       if ( value == INF )
 792         {
 793           DOut( ply, "PHI_C=inf: %s",
 794                  str_CSA_move(pnode->children[i].move) );
 795           return;
 796         }
 797
 798       if ( value == INF_1 ) { have_inf_1 = 1;  iinf_1 = i; }
 799
 800       if ( have_inf_1 ) { continue; }
 801
 802       if ( type == weak_chuai )
 803         {
 804           if ( value_chuai < value ) { value_chuai = value; }
 805           continue;
 806         }
 807       if ( type == 0 || value != 1 ) { type  = UINT_MAX - i; }
 808
 809       /* find type in aphi[j].type */
 810       for ( j = 0, aphi[ntype].type = type; type != aphi[j].type; j++ );
 811
 812
 813       if ( j == ntype )  /* not found */
 814         {
 815           aphi[j].value   = value;
 816           aphi[j].move    = pnode->children[i].move;
 817           aphi[j].is_loop = pnode->children[i].is_phi_loop;
 818           ntype          += 1;
 819         }
 820       else if ( aphi[j].value < value )
 821         {
 822           aphi[j].value    = value;
 823           aphi[j].move     = pnode->children[i].move;
 824           aphi[j].is_loop &= pnode->children[i].is_phi_loop;
 825         }
 826     }
 827
 828   if ( have_inf_1 )
 829     {
 830       DOut( ply, "PHI_C=inf-1: %s",
 831             str_CSA_move(pnode->children[iinf_1].move) );
 832     }
 833   else {
 834     char buf[65536];
 835
 836     buf[0] = '\0';
 837     for ( i = 0; i < ntype; i++ )
 838       {
 839         snprintf ( buf, 65536, "%s %s(%u%s)", buf,
 840                    str_CSA_move(aphi[i].move), aphi[i].value,
 841                    aphi[i].is_loop ? "l" : "" );
 842       }
 843
 844     if ( value_chuai )
 845       {
 846         snprintf( buf, 65536, "%s CHUAI(%u)", buf, value_chuai );
 847       }
 848     DOut( ply, "PHI_C=%u:%s", pnode->sum_phi, buf );
 849   }
 850 }
 851
 852
 853 static void CONV
 854 dbg_out_move_seq( const node_t * restrict nodes, int ply )
 855 {
 856   char buf[65536];
 857   int i;
 858
 859   buf[0] = '\0';
 860   for ( i = 1; i < ply; i++ )
 861     {
 862       unsigned int move = nodes[i].children[nodes[i].icurr_c].move;
 863       snprintf( buf, 65536, "%s %s", buf, str_CSA_move(move) );
 864     }
 865   DOut( ply, "HIST:%s", buf );
 866 }
 867
 868 #  endif
 869
 870 #endif /* DFPN */