search.c

   1 #include <limits.h>
   2 #include <stdlib.h>
   3 #include <string.h>
   4 #include <assert.h>
   5 #include "shogi.h"
   6
   7 static void hist_add( tree_t * restrict ptree, int ply );
   8 static void hist_good( tree_t * restrict ptree, unsigned int move, int ply,
   9                        int depth, int turn );
  10 static int detect_signals( tree_t * restrict ptree );
  11 static int detect_rep( tree_t * restrict ptree, int ply, int turn );
  12 static int rep_type( const tree_t * restrict ptree, int n, int i, int ply,
  13                      int turn );
  14
  15 /* #define DBG_SEARCH */
  16 #if defined(DBG_SEARCH)
  17 #  define DOut( ... )  if ( dbg_flag ) { out( __VA_ARGS__ ); }
  18 #else
  19 #  define DOut( ... )
  20 #endif
  21
  22 int
  23 search( tree_t * restrict ptree, int alpha, int beta, int turn, int depth,
  24         int ply, unsigned int state_node )
  25 {
  26   int value, alpha_old;
  27
  28   if ( ! ptree->nsuc_check[ply] && depth < PLY_INC )
  29     {
  30       return search_quies( ptree, alpha, beta, turn, ply, 1 );
  31     }
  32
  33
  34 #if defined(DBG_SEARCH)
  35   int dbg_flag = 0;
  36   if ( iteration_depth == 3 && ply == 3
  37        && ! strcmp( str_CSA_move(ptree->current_move[1]),  "7776FU" )
  38        && ! strcmp( str_CSA_move(ptree->current_move[2]),  "3334FU" ) )
  39     {
  40       dbg_flag = 1;
  41       Out( "search start (d%.1f %" PRIu64 ")\n",
  42            (double)depth / (double)PLY_INC, ptree->node_searched );
  43     }
  44 #endif
  45
  46   ptree->node_searched++;
  47
  48   if ( ply >= PLY_MAX-1 )
  49     {
  50       value = evaluate( ptree, ply, turn );
  51       if ( alpha < value && value < beta ) { pv_close( ptree, ply, no_rep ); }
  52       MOVE_CURR = MOVE_NA;
  53       return value;
  54     }
  55
  56
  57 #if ! defined(MINIMUM)
  58   if ( ! ( game_status & flag_learning ) )
  59 #endif
  60     {
  61       /* check time and input */
  62 #if defined(TLP)
  63       if ( ! ptree->tlp_id )
  64 #endif
  65         if ( node_next_signal < ++node_last_check && detect_signals( ptree ) )
  66           {
  67             root_abort = 1;
  68             return 0;
  69           }
  70
  71       /* repetitions */
  72       ptree->nrep_tried++;
  73       switch ( detect_rep( ptree, ply, turn ) )
  74         {
  75         case black_superi_rep:
  76           value = turn ? -score_inferior : score_inferior;
  77           if ( alpha < value
  78                && value < beta ) { pv_close( ptree, ply, black_superi_rep ); }
  79           ptree->nsuperior_rep++;
  80           MOVE_CURR = MOVE_NA;
  81           return value;
  82
  83         case white_superi_rep:
  84           value = turn ? score_inferior : -score_inferior;
  85           if ( alpha < value
  86                && value < beta ) { pv_close( ptree, ply, white_superi_rep ); }
  87           ptree->nsuperior_rep++;
  88           MOVE_CURR = MOVE_NA;
  89           return value;
  90
  91         case four_fold_rep:
  92           if ( alpha < score_draw
  93                && score_draw < beta ) { pv_close( ptree, ply, four_fold_rep );}
  94           ptree->nfour_fold_rep++;
  95           MOVE_CURR = MOVE_NA;
  96           return score_draw;
  97
  98         case perpetual_check:
  99           ptree->nperpetual_check++;
 100           MOVE_CURR = MOVE_NA;
 101           return score_foul;
 102
 103         case perpetual_check2:
 104           if ( ply > 4 )
 105             {
 106               ptree->nperpetual_check++;
 107               MOVE_CURR = MOVE_NA;
 108               return -score_foul;
 109             }
 110           break;
 111         }
 112
 113       ptree->nreject_tried++;
 114       if ( rejections_probe( ptree, turn, ply ) )
 115         {
 116           ptree->nreject_done++;
 117           if ( alpha < score_inferior && score_inferior < beta )
 118             {
 119               pv_close( ptree, ply, turn ? white_superi_rep:black_superi_rep );
 120             }
 121           MOVE_CURR = MOVE_NA;
 122           return score_inferior;
 123         }
 124     }
 125
 126   /*
 127     no repetitions.  worst situation of this node is checkmate,
 128     and the best is to force checkmate within 1-ply.
 129   */
 130   alpha_old = alpha;
 131   value = - ( score_mate1ply + 2 - ply );
 132   if ( alpha < value )
 133     {
 134       if ( beta <= value )
 135         {
 136           MOVE_CURR = MOVE_NA;
 137           return value;
 138         }
 139       alpha = value;
 140     }
 141   else {
 142     value = score_mate1ply + 1 - ply;
 143     if ( value <= alpha ) { return value; }
 144   }
 145
 146 #if defined(NO_NULL_PRUNE)
 147   state_node &= ~node_do_null;
 148 #endif
 149
 150   ptree->amove_hash[ply] = 0;
 151 #if ! defined(MINIMUM)
 152   if ( ! ( game_status & flag_learning ) )
 153 #endif
 154     {
 155       /* probe the transposition table */
 156       int tv = hash_probe( ptree, ply, depth, turn, alpha, beta, state_node );
 157       switch ( tv )
 158         {
 159         case value_exact:
 160           if ( alpha < HASH_VALUE )
 161             {
 162               if ( HASH_VALUE < beta ) { pv_close( ptree, ply, hash_hit ); }
 163               else {
 164                 MOVE_CURR = ptree->amove_hash[ply];
 165                 assert( is_move_valid( ptree, MOVE_CURR, turn ) );
 166               }
 167             }
 168           return HASH_VALUE;
 169
 170         case value_lower:
 171           MOVE_CURR = ptree->amove_hash[ply];
 172           assert( beta <= HASH_VALUE );
 173           assert( ! IsMove(MOVE_CURR)
 174                   || is_move_valid( ptree, MOVE_CURR, turn ) );
 175           if ( beta == alpha_old + 1 ) { return HASH_VALUE; }
 176           break;
 177
 178         case value_upper:
 179           assert( HASH_VALUE <= alpha );
 180           if ( beta == alpha_old + 1 ) { return HASH_VALUE; }
 181           break;
 182
 183         default:
 184           state_node = tv;
 185         }
 186     }
 187
 188   DOut( "\nhash cut passed" );
 189
 190   if ( depth >= REJEC_MIN_DEPTH ) { add_rejections( ptree, turn, ply ); }
 191
 192
 193   if ( ! ptree->nsuc_check[ply] )
 194     {
 195       /* detect a move mates in 3-ply */
 196       if ( ( state_node & node_do_mate )
 197            && is_mate_in3ply( ptree, turn, ply ) )
 198         {
 199           value = score_mate1ply + 1 - ply;
 200
 201           hash_store( ptree, ply, depth, turn, value_exact, value,
 202                       MOVE_CURR, 0 );
 203
 204           if ( alpha < value
 205                && value < beta ) { pv_close( ptree, ply, mate_search ); }
 206
 207           if ( depth >= REJEC_MIN_DEPTH )
 208             {
 209               sub_rejections( ptree, turn, ply );
 210             }
 211           assert( is_move_valid( ptree, MOVE_CURR, turn ) );
 212           return value;
 213         }
 214
 215
 216       /* null move pruning */
 217       if ( 2*PLY_INC <= depth
 218            && ( state_node & node_do_null )
 219            && beta == alpha_old + 1
 220            && beta <= evaluate( ptree, ply, turn ) )
 221         {
 222           int null_depth, nrep;
 223
 224           null_depth = NullDepth(depth);
 225           nrep       = root_nrep + ply - 1;
 226
 227           MOVE_CURR                   = MOVE_PASS;
 228           ptree->move_last[ply]       = ptree->move_last[ply-1];
 229           ptree->stand_pat[ply+1]     = (short)( - ptree->stand_pat[ply] );
 230           ptree->nsuc_check[ply+1]    = 0;
 231           ptree->rep_board_list[nrep] = HASH_KEY;
 232           ptree->rep_hand_list[nrep]  = HAND_B;
 233           ptree->null_pruning_tried++;
 234
 235           value = -search( ptree, -beta, 1-beta, Flip(turn), null_depth, ply+1,
 236                            node_do_mate | node_do_recap | node_do_futile );
 237           if ( SEARCH_ABORT )
 238             {
 239               if ( depth >= REJEC_MIN_DEPTH )
 240                 {
 241                   sub_rejections( ptree, turn, ply );
 242                 }
 243               return 0;
 244             }
 245
 246           if ( beta <= value )
 247             {
 248               ptree->null_pruning_done++;
 249               if ( null_depth < PLY_INC )
 250                 {
 251                   hash_store( ptree, ply, depth, turn, value_lower,
 252                               value, MOVE_NA, state_node );
 253                 }
 254               if ( depth >= REJEC_MIN_DEPTH )
 255                 {
 256                   sub_rejections( ptree, turn, ply );
 257                 }
 258
 259               DOut( "\nnull move cut!\n" );
 260
 261               assert( ! IsMove(MOVE_CURR)
 262                       || is_move_valid( ptree, MOVE_CURR, turn ) );
 263               return value;
 264             }
 265
 266           DOut( "\nnull passed" );
 267
 268           if ( value == - ( score_mate1ply - ply ) )
 269             {
 270               state_node |= node_mate_threat;
 271             }
 272         }
 273     }
 274
 275   /* recursive iterative-deepening for pv nodes */
 276   if ( ! ptree->amove_hash[ply]
 277        && depth >= 3*PLY_INC
 278        && ( ( alpha == root_alpha && beta == root_beta )
 279             || ( alpha == -root_beta && beta == -root_alpha ) ) )
 280     {
 281       if ( depth >= REJEC_MIN_DEPTH ) { sub_rejections( ptree, turn, ply ); }
 282       value = search( ptree, -score_bound, beta, turn, depth-2*PLY_INC, ply,
 283                       node_do_mate | node_do_recap );
 284       if ( SEARCH_ABORT ) { return 0; }
 285
 286       if ( beta <= value && IsMove(MOVE_CURR) )
 287         {
 288           ptree->amove_hash[ply] = MOVE_CURR;
 289         }
 290       else if ( value < beta && ply <= (int)ptree->pv[ply-1].length )
 291         {
 292           assert( -score_bound < value );
 293           ptree->amove_hash[ply] = ptree->pv[ply-1].a[ply];
 294         }
 295       assert( ! ptree->amove_hash[ply]
 296               || is_move_valid( ptree, ptree->amove_hash[ply], turn ) );
 297
 298       if ( depth >= REJEC_MIN_DEPTH ) { add_rejections( ptree, turn, ply ); }
 299     }
 300
 301   {
 302     int depth_reduced, first_move_expanded, new_depth, extension;
 303     int state_node_new;
 304
 305     ptree->move_last[ply]             = ptree->move_last[ply-1];
 306     ptree->anext_move[ply].next_phase = next_move_hash;
 307     ptree->hist_nmove[ply]            = 0;
 308     first_move_expanded               = 0;
 309
 310     evaluate( ptree, ply, turn );
 311
 312     /* expand all of off-springs */
 313     while ( ptree->nsuc_check[ply]
 314             ? gen_next_evasion( ptree, ply, turn )
 315             : gen_next_move( ptree, ply, turn ) ) {
 316
 317       DOut( "\nexpand %s (%" PRIu64 ")",
 318             str_CSA_move(MOVE_CURR), ptree->node_searched );
 319
 320       ptree->nsuc_check[ply+1] = 0U;
 321       state_node_new           = ( node_do_mate | node_do_recap | node_do_null
 322                                    | node_do_futile );
 323       extension                = 0;
 324       depth_reduced            = 0;
 325
 326       hist_add( ptree, ply );
 327
 328       /* decision of extensions */
 329       if ( turn ? is_move_check_w( ptree, MOVE_CURR )
 330                 : is_move_check_b( ptree, MOVE_CURR ) )
 331         {
 332           ptree->check_extension_done++;
 333           ptree->nsuc_check[ply+1]
 334             = (unsigned char)( ptree->nsuc_check[ply-1] + 1U );
 335           extension = EXT_CHECK;
 336         }
 337       else if ( ptree->nsuc_check[ply]
 338                 && ptree->move_last[ply] - ptree->move_last[ply-1] == 1 )
 339         {
 340           ptree->onerp_extension_done++;
 341           extension = EXT_ONEREP;
 342         }
 343       else if ( ! ptree->nsuc_check[ply]
 344                 && ( state_node & node_do_recap )
 345                 && I2To(MOVE_CURR) == I2To(MOVE_LAST)
 346                 && ( MOVE_CURR == ptree->anext_move[ply].move_cap1
 347                      || ( ( ptree->anext_move[ply].value_cap1
 348                             < ( ptree->anext_move[ply].value_cap2
 349                                 + MT_CAP_PAWN ) )
 350                           && MOVE_CURR == ptree->anext_move[ply].move_cap2 ))
 351                 && ( UToCap(MOVE_LAST)
 352                      || ( I2IsPromote(MOVE_LAST)
 353                           && I2PieceMove(MOVE_LAST) != silver ) ) )
 354         {
 355           ptree->recap_extension_done++;
 356           state_node_new = node_do_null | node_do_mate | node_do_futile;
 357           if ( ! I2IsPromote(MOVE_CURR)
 358                && I2PieceMove(MOVE_LAST) == UToCap(MOVE_LAST) )
 359             {
 360               extension = EXT_RECAP2;
 361             }
 362           else { extension = EXT_RECAP1; }
 363         }
 364
 365       LimitExtension( extension, ply );
 366
 367       new_depth = depth + extension - PLY_INC;
 368
 369       /* reductions */
 370       if ( PLY_INC <= new_depth
 371            && ! ( state_node & node_mate_threat )
 372            && ! ptree->nsuc_check[ply]
 373            && ! UToCap(MOVE_CURR)
 374            && ! ( I2IsPromote(MOVE_CURR) && I2PieceMove(MOVE_CURR) != silver )
 375            && ptree->amove_hash[ply]  != MOVE_CURR
 376            && ptree->killers[ply].no1 != MOVE_CURR
 377            && ptree->killers[ply].no2 != MOVE_CURR )
 378         {
 379           unsigned int key     = phash( MOVE_CURR, turn );
 380           unsigned int good    = ptree->hist_good[key]  + 1;
 381           unsigned int triedx8 = ( ptree->hist_tried[key] + 2 ) * 8U;
 382
 383           if ( beta != alpha_old + 1 ) {
 384
 385             if      ( good * 62U < triedx8 ) { depth_reduced = PLY_INC * 4/2; }
 386             else if ( good * 46U < triedx8 ) { depth_reduced = PLY_INC * 3/2; }
 387             else if ( good * 34U < triedx8 ) { depth_reduced = PLY_INC * 2/2; }
 388             else if ( good * 19U < triedx8 ) { depth_reduced = PLY_INC * 1/2; }
 389
 390           } else {
 391
 392             if      ( good * 62U < triedx8 ) { depth_reduced = PLY_INC * 4/2; }
 393             else if ( good * 46U < triedx8 ) { depth_reduced = PLY_INC * 3/2; }
 394             else if ( good * 30U < triedx8 ) { depth_reduced = PLY_INC * 2/2; }
 395             else if ( good * 12U < triedx8 ) { depth_reduced = PLY_INC * 1/2; }
 396           }
 397
 398           new_depth -= depth_reduced;
 399         }
 400
 401       /* futility pruning */
 402       if ( ! ptree->nsuc_check[ply+1]
 403            && ! ptree->nsuc_check[ply]
 404            && new_depth < 3*PLY_INC )
 405         {
 406           int diff  = estimate_score_diff( ptree, MOVE_CURR, turn );
 407           int bound = alpha;
 408
 409           if      ( 2*PLY_INC <= new_depth ) { bound -= EFUTIL_MG2; }
 410           else if ( 1*PLY_INC <= new_depth ) { bound -= EFUTIL_MG1; }
 411
 412           if ( eval_max_score( ptree, MOVE_CURR, ptree->stand_pat[ply],
 413                                turn, diff ) <= bound )
 414             {
 415               first_move_expanded += 1;
 416               continue;
 417             }
 418         }
 419
 420       DOut( ", futil passed" );
 421
 422       MakeMove( turn, MOVE_CURR, ply );
 423       if ( I2From(MOVE_CURR) < nsquare
 424            && ! ptree->nsuc_check[ply]
 425            && InCheck(turn) )
 426         {
 427           UnMakeMove( turn, MOVE_CURR, ply );
 428           continue;
 429         }
 430
 431       if ( ! ptree->nsuc_check[ply+1] && ! ptree->nsuc_check[ply] )
 432         {
 433           evaluate( ptree, ply+1, Flip(turn) );
 434           assert( ptree->stand_pat[ply] != score_bound );
 435
 436           /* futility pruning */
 437           if ( ( new_depth < PLY_INC && - ptree->stand_pat[ply+1] <= alpha )
 438                || ( new_depth < 2*PLY_INC
 439                     && - ptree->stand_pat[ply+1] <= alpha - EFUTIL_MG1 )
 440                || ( new_depth < 3*PLY_INC
 441                     && - ptree->stand_pat[ply+1] <= alpha - EFUTIL_MG2 ) )
 442             {
 443               first_move_expanded += 1;
 444               UnMakeMove( turn, MOVE_CURR, ply );
 445               continue;
 446             }
 447         }
 448
 449       if ( depth_reduced )
 450         {
 451           value = -search( ptree, -alpha-1, -alpha, Flip(turn), new_depth,
 452                            ply + 1, state_node_new );
 453           if ( ! SEARCH_ABORT && alpha < value )
 454             {
 455               new_depth += depth_reduced;
 456               value = -search( ptree, -beta, -alpha, Flip(turn), new_depth,
 457                                ply+1, state_node_new );
 458             }
 459         }
 460       else if ( ! first_move_expanded )
 461         {
 462           value = -search( ptree, -beta, -alpha, Flip(turn), new_depth, ply+1,
 463                            state_node_new );
 464         }
 465       else {
 466         value = -search( ptree, -alpha-1, -alpha, Flip(turn), new_depth,
 467                          ply + 1, state_node_new );
 468         if ( ! SEARCH_ABORT && alpha < value && beta != alpha+1 )
 469           {
 470             value = -search( ptree, -beta, -alpha, Flip(turn), new_depth,
 471                              ply + 1, state_node_new );
 472           }
 473       }
 474
 475       if ( SEARCH_ABORT )
 476         {
 477           UnMakeMove( turn, MOVE_CURR, ply );
 478           if ( depth >= REJEC_MIN_DEPTH )
 479             {
 480               sub_rejections( ptree, turn, ply );
 481             }
 482           return 0;
 483         }
 484
 485       UnMakeMove( turn, MOVE_CURR, ply );
 486
 487       if ( alpha < value )
 488         {
 489           if ( new_depth < PLY_INC
 490                && ! ptree->nsuc_check[ply+1]
 491                && ptree->stand_pat[ply] != score_bound )
 492             {
 493               check_futile_score_quies( ptree, MOVE_CURR,
 494                                         ptree->stand_pat[ply],
 495                                         -ptree->stand_pat[ply+1], turn );
 496             }
 497
 498           if ( beta <= value )
 499             {
 500               DOut( ", beta cut (%" PRIu64 ")\n", ptree->node_searched );
 501
 502               hash_store( ptree, ply, depth, turn, value_lower, value,
 503                           MOVE_CURR, state_node );
 504               hist_good( ptree, MOVE_CURR, ply, depth, turn );
 505
 506               ptree->fail_high++;
 507               if ( ! first_move_expanded ) { ptree->fail_high_first++; }
 508
 509               if ( depth >= REJEC_MIN_DEPTH )
 510                 {
 511                   sub_rejections( ptree, turn, ply );
 512                 }
 513
 514               assert( is_move_valid( ptree, MOVE_CURR, turn ) );
 515               return value;
 516             }
 517         }
 518       if ( alpha < value ) { alpha = value; }
 519
 520       first_move_expanded += 1;
 521 #if defined(TLP)
 522       if ( ! ( ptree->nsuc_check[ply]
 523                && ptree->move_last[ply] - ptree->move_last[ply-1] < 4 )
 524            && tlp_idle
 525            && ( ( iteration_depth < 11 && PLY_INC * 3 <= depth )
 526                 || PLY_INC * 4 <= depth ) )
 527         {
 528           ptree->tlp_beta       = (short)beta;
 529           ptree->tlp_best       = (short)alpha;
 530           ptree->tlp_depth      = (unsigned char)depth;
 531           ptree->tlp_state_node = (unsigned char)state_node;
 532           ptree->tlp_turn       = (char)turn;
 533           ptree->tlp_ply        = (char)ply;
 534           if ( tlp_split( ptree ) )
 535             {
 536               if ( SEARCH_ABORT ) { return 0; }
 537               value = ptree->tlp_best;
 538               if ( alpha < value )
 539                 {
 540                   if ( beta <= value )
 541                     {
 542                       if ( depth >= REJEC_MIN_DEPTH )
 543                         {
 544                           sub_rejections( ptree, turn, ply );
 545                         }
 546
 547                       hash_store( ptree, ply, depth, turn, value_lower,
 548                                   value, MOVE_CURR, state_node );
 549
 550                       hist_good( ptree, MOVE_CURR, ply, depth, turn );
 551
 552                       ptree->fail_high++;
 553
 554                       assert( is_move_valid( ptree, MOVE_CURR, turn ) );
 555                       return value;
 556                     }
 557                   alpha = value;
 558                 }
 559               break;
 560             }
 561         }
 562 #endif
 563     }
 564
 565     DOut( "\nall searched (%" PRIu64 ")\n", ptree->node_searched );
 566
 567     if ( depth >= REJEC_MIN_DEPTH ) { sub_rejections( ptree, turn, ply ); }
 568
 569     if ( ! first_move_expanded )
 570       {
 571 #if ! defined(MINIMUM)
 572         if ( (int)I2From( ptree->current_move[ply-1] ) == Drop2From( pawn ) )
 573           {
 574             out_warning( "A checkmate by dropping pawn!!" );
 575           }
 576 #endif
 577         if ( alpha != alpha_old ) { pv_close( ptree, ply, 0 ); }
 578         return alpha;
 579       }
 580
 581
 582     if ( alpha <= - ( score_mate1ply + 2 - ply ) )
 583       {
 584 #if ! defined(MINIMUM)
 585         out_warning( "A node returns a value lower than mate." );
 586 #endif
 587         if ( alpha_old < -score_inferior && -score_inferior < beta )
 588           {
 589             pv_close( ptree, ply, turn ? black_superi_rep : white_superi_rep );
 590           }
 591         MOVE_CURR = MOVE_NA;
 592         return -score_inferior;
 593       }
 594
 595     if ( alpha != alpha_old )
 596       {
 597         hist_good( ptree, ptree->pv[ply].a[ply], ply, depth, turn );
 598
 599         pv_copy( ptree, ply );
 600
 601 #if ! defined(MINIMUM)
 602         if ( ! ( game_status & flag_learning ) )
 603 #endif
 604           {
 605             hash_store( ptree, ply, depth, turn, value_exact, alpha,
 606                         ptree->pv[ply].a[ply], state_node );
 607           }
 608       }
 609     else {
 610       hash_store( ptree, ply, depth, turn, value_upper, alpha, MOVE_NA,
 611                   state_node );
 612     }
 613   }
 614
 615   return alpha;
 616 }
 617
 618
 619 #if defined(TLP)
 620 int
 621 tlp_search( tree_t * restrict ptree, int alpha, int beta, int turn,
 622             int depth, int ply, unsigned int state_node )
 623 {
 624   int value, new_depth, extension, state_node_new, iret, depth_reduced;
 625   int alpha_old;
 626
 627   assert( depth >= 3*PLY_INC );
 628
 629   alpha_old = alpha;
 630
 631   for ( ;; ) {
 632     lock( & ptree->tlp_ptree_parent->tlp_lock );
 633     if ( ptree->nsuc_check[ply] )
 634       {
 635         iret = gen_next_evasion( ptree->tlp_ptree_parent, ply, turn );
 636       }
 637     else { iret = gen_next_move( ptree->tlp_ptree_parent, ply, turn ); }
 638     MOVE_CURR = ptree->tlp_ptree_parent->current_move[ply];
 639     hist_add( ptree->tlp_ptree_parent, ply );
 640     unlock( & ptree->tlp_ptree_parent->tlp_lock );
 641     if ( ! iret ) { break; }
 642
 643     ptree->nsuc_check[ply+1] = 0U;
 644     state_node_new           = ( node_do_mate | node_do_recap | node_do_null
 645                                  | node_do_futile );
 646     extension                = 0;
 647     depth_reduced            = 0;
 648
 649     if ( turn ? is_move_check_w( ptree, MOVE_CURR )
 650               : is_move_check_b( ptree, MOVE_CURR ) )
 651       {
 652         ptree->check_extension_done++;
 653         ptree->nsuc_check[ply+1]
 654           = (unsigned char)( ptree->nsuc_check[ply-1] + 1U );
 655         extension = EXT_CHECK;
 656       }
 657     else if ( ! ptree->nsuc_check[ply]
 658               && ( state_node & node_do_recap )
 659               && I2To(MOVE_CURR) == I2To(MOVE_LAST)
 660               && ( MOVE_CURR == ptree->anext_move[ply].move_cap1
 661                    || ( ( ptree->anext_move[ply].value_cap1
 662                           < ptree->anext_move[ply].value_cap2 + MT_CAP_PAWN )
 663                         && MOVE_CURR == ptree->anext_move[ply].move_cap2 ) )
 664               && ( UToCap(MOVE_LAST)
 665                    || ( I2IsPromote(MOVE_LAST)
 666                         && I2PieceMove(MOVE_LAST) != silver ) ) )
 667       {
 668         ptree->recap_extension_done++;
 669         state_node_new = node_do_null | node_do_mate | node_do_futile;
 670         if ( ! I2IsPromote(MOVE_CURR)
 671              && I2PieceMove(MOVE_LAST) == UToCap(MOVE_LAST) )
 672           {
 673             extension = EXT_RECAP2;
 674           }
 675         else { extension = EXT_RECAP1; }
 676       }
 677
 678     LimitExtension( extension, ply );
 679
 680     new_depth = depth + extension - PLY_INC;
 681
 682     /* reductions */
 683     if ( ! ( state_node & node_mate_threat )
 684          && ! ptree->nsuc_check[ply]
 685          && ! UToCap(MOVE_CURR)
 686          && ! ( I2IsPromote(MOVE_CURR) && I2PieceMove(MOVE_CURR) != silver )
 687          && ptree->killers[ply].no1 != MOVE_CURR
 688          && ptree->killers[ply].no2 != MOVE_CURR )
 689       {
 690           unsigned int key     = phash( MOVE_CURR, turn );
 691           unsigned int good    = ptree->hist_good[key]  + 1;
 692           unsigned int triedx8 = ( ptree->hist_tried[key] + 2 ) * 8U;
 693
 694           if ( beta != alpha_old + 1 ) {
 695
 696             if      ( good * 62U < triedx8 ) { depth_reduced = PLY_INC * 4/2; }
 697             else if ( good * 46U < triedx8 ) { depth_reduced = PLY_INC * 3/2; }
 698             else if ( good * 34U < triedx8 ) { depth_reduced = PLY_INC * 2/2; }
 699             else if ( good * 19U < triedx8 ) { depth_reduced = PLY_INC * 1/2; }
 700
 701           } else {
 702
 703             if      ( good * 62U < triedx8 ) { depth_reduced = PLY_INC * 4/2; }
 704             else if ( good * 46U < triedx8 ) { depth_reduced = PLY_INC * 3/2; }
 705             else if ( good * 30U < triedx8 ) { depth_reduced = PLY_INC * 2/2; }
 706             else if ( good * 12U < triedx8 ) { depth_reduced = PLY_INC * 1/2; }
 707           }
 708
 709           new_depth -= depth_reduced;
 710       }
 711
 712     if ( ! ptree->nsuc_check[ply+1]
 713          && ! ptree->nsuc_check[ply]
 714          && new_depth < 3*PLY_INC )
 715       {
 716         int diff  = estimate_score_diff( ptree, MOVE_CURR, turn );
 717         int bound = alpha;
 718
 719         if      ( 2*PLY_INC <= new_depth ) { bound -= EFUTIL_MG2; }
 720         else if ( 1*PLY_INC <= new_depth ) { bound -= EFUTIL_MG1; }
 721
 722         if ( eval_max_score( ptree, MOVE_CURR, ptree->stand_pat[ply],
 723                              turn, diff ) <= bound )
 724           {
 725             continue;
 726           }
 727       }
 728
 729     MakeMove( turn, MOVE_CURR, ply );
 730     if ( I2From(MOVE_CURR) < nsquare
 731          && ! ptree->nsuc_check[ply]
 732          && InCheck(turn) )
 733       {
 734         UnMakeMove( turn, MOVE_CURR, ply );
 735         continue;
 736       }
 737
 738     if ( ! ptree->nsuc_check[ply+1] && ! ptree->nsuc_check[ply] )
 739       {
 740         evaluate( ptree, ply+1, Flip(turn) );
 741         assert( ptree->stand_pat[ply] != score_bound );
 742
 743         /* futility pruning */
 744         if ( ( new_depth < PLY_INC && - ptree->stand_pat[ply+1] <= alpha )
 745              || ( new_depth < 2*PLY_INC
 746                   && - ptree->stand_pat[ply+1] <= alpha - EFUTIL_MG1 )
 747              || ( new_depth < 3*PLY_INC
 748                   && - ptree->stand_pat[ply+1] <= alpha - EFUTIL_MG2 ) )
 749           {
 750             UnMakeMove( turn, MOVE_CURR, ply );
 751             continue;
 752           }
 753       }
 754
 755     value = -search( ptree, -alpha-1, -alpha, Flip(turn), new_depth,
 756                      ply + 1, state_node_new );
 757     if ( ! SEARCH_ABORT && alpha < value )
 758       {
 759         if ( ! depth_reduced && beta != alpha+1 )
 760           {
 761             value = -search( ptree, -beta, -alpha, Flip(turn), new_depth,
 762                              ply + 1, state_node_new );
 763           }
 764         else if ( depth_reduced )
 765           {
 766             new_depth += depth_reduced;
 767             value = -search( ptree, -beta, -alpha, Flip(turn), new_depth,
 768                              ply + 1, state_node_new );
 769           }
 770       }
 771
 772     UnMakeMove( turn, MOVE_CURR, ply );
 773
 774     if ( SEARCH_ABORT ) { return 0; }
 775
 776     if ( alpha < value ) {
 777
 778       alpha = value;
 779       if ( beta <= value ) {
 780         int num;
 781
 782         lock( &tlp_lock );
 783         if ( ptree->tlp_abort )
 784           {
 785             unlock( &tlp_lock );
 786             return 0;
 787           }
 788         tlp_nabort += 1;
 789
 790         for ( num = 0; num < tlp_max; num++ )
 791           if ( ptree->tlp_ptree_parent->tlp_ptrees_sibling[num]
 792                && num != ptree->tlp_id )
 793             tlp_set_abort( ptree->tlp_ptree_parent->tlp_ptrees_sibling[num] );
 794
 795         unlock( &tlp_lock );
 796
 797         return value;
 798       }
 799     }
 800   }
 801
 802   return alpha;
 803 }
 804 #endif /* TLP */
 805
 806
 807 static int
 808 detect_signals( tree_t * restrict ptree )
 809 {
 810   unsigned int tnow, telapsed, tpondered, tsearched, tcount, tlimit, tmax;
 811   unsigned int tmax_limit_count, tlimit_count, u;
 812   int iret, easy_time, last_value, stable;
 813
 814   if ( ! ( game_status & flag_nopeek ) )
 815     {
 816       /* peek input-buffer to find a command */
 817       iret = next_cmdline( 0 );
 818       if ( iret == -1 )
 819         {
 820           game_status |= flag_search_error;
 821           return 1;
 822         }
 823       else if ( iret == -2 )
 824         {
 825           out_warning( "%s", str_error );
 826           ShutdownClient;
 827         }
 828       else if ( game_status & flag_quit ) { return 1; } /* EOF */
 829       else if ( iret )
 830         {
 831           /* a command is found */
 832           iret = procedure( ptree );
 833           if ( iret == -1 )
 834             {
 835               game_status |= flag_search_error;
 836               next_cmdline( 1 );
 837               return 1;
 838             }
 839           else if ( iret == -2 )
 840             {
 841               out_warning( "%s", str_error );
 842               next_cmdline( 1 );
 843               ShutdownClient;
 844             }
 845           else if ( iret == 1 ) { next_cmdline( 1 ); }
 846
 847           if ( game_status & ( flag_quit | flag_quit_ponder
 848                                | flag_move_now | flag_suspend ) )
 849             {
 850               return 1;
 851             }
 852         }
 853     }
 854
 855   /* check conditions of search-abortion, and obtain tnow and elapsed */
 856   if ( node_limit <= ptree->node_searched ) { return 1; }
 857
 858   if ( get_elapsed( &tnow ) < 0 )
 859     {
 860       game_status |= flag_search_error;
 861       return 1;
 862     }
 863
 864   /* keep my connection alive */
 865 #if defined(CSA_LAN)
 866   if ( sckt_csa != SCKT_NULL
 867        && SEC_KEEP_ALIVE * 1000U < tnow - time_last_send
 868        && sckt_out( sckt_csa, "\n" ) < 0 )
 869     {
 870       game_status |= flag_search_error;
 871       return 1;
 872     }
 873 #endif
 874
 875 #if defined(MNJ_LAN)
 876   if ( sckt_mnj != SCKT_NULL && 500U < tnow - time_last_send )
 877     {
 878       uint64_t nodes;
 879
 880 #  if defined(TLP)
 881       lock( &tlp_lock );
 882       nodes = tlp_count_node( tlp_atree_work );
 883       unlock( &tlp_lock );
 884 #  else
 885       nodes = ptree->node_searched;
 886 #  endif
 887
 888       if ( sckt_out( sckt_mnj, "pid=%d n=%" PRIu64 "\n", mnj_posi_id,
 889                      nodes ) < 0 )
 890         {
 891           game_status |= flag_search_error;
 892           return 1;
 893         }
 894     }
 895 #endif
 896
 897   /* shortening the time limit by depth */
 898   if (  time_limit != UINT_MAX
 899         && sec_limit_depth < PLY_MAX
 900         && iteration_depth + 10 >= (int)sec_limit_depth )
 901     {
 902       if      ( iteration_depth + 0 >= (int)sec_limit_depth ) { u =    1U; }
 903       else if ( iteration_depth + 1 >= (int)sec_limit_depth ) { u =    3U; }
 904       else if ( iteration_depth + 2 >= (int)sec_limit_depth ) { u =    7U; }
 905       else if ( iteration_depth + 3 >= (int)sec_limit_depth ) { u =   15U; }
 906       else if ( iteration_depth + 4 >= (int)sec_limit_depth ) { u =   31U; }
 907       else if ( iteration_depth + 5 >= (int)sec_limit_depth ) { u =   63U; }
 908       else if ( iteration_depth + 6 >= (int)sec_limit_depth ) { u =  127U; }
 909       else if ( iteration_depth + 7 >= (int)sec_limit_depth ) { u =  255U; }
 910       else if ( iteration_depth + 8 >= (int)sec_limit_depth ) { u =  511U; }
 911       else if ( iteration_depth + 9 >= (int)sec_limit_depth ) { u = 1023U; }
 912       else                                                    { u = 2047U; }
 913
 914       tlimit = u * 1000U + 1000U - time_response;
 915       tmax   = u * 5000U + 1000U - time_response;
 916       if ( tlimit > time_limit )     { tlimit = time_limit; }
 917       if ( tmax   > time_max_limit ) { tmax   = time_max_limit; }
 918     }
 919   else {
 920     tlimit = time_limit;
 921     tmax   = time_max_limit;
 922   }
 923
 924   telapsed   = tnow            - time_turn_start;
 925   tpondered  = time_turn_start - time_start;
 926   tsearched  = tnow            - time_start;
 927   easy_time  = 0;
 928   last_value = root_turn ? -last_root_value : last_root_value;
 929   stable     = ( tlimit != UINT_MAX
 930                  && ( ( root_alpha == root_value && ! root_nfail_low )
 931                       || last_pv.type == four_fold_rep
 932                       || ( root_nfail_high
 933                            && root_value + MT_CAP_DRAGON/8 >= last_value ) ) );
 934
 935   if ( tlimit != tmax )
 936     {
 937       tcount           = tsearched;
 938       tmax_limit_count = tmax;
 939       tlimit_count     = tlimit;
 940     }
 941   else {
 942     tcount           = telapsed;
 943     tmax_limit_count = tmax   + tpondered;
 944     tlimit_count     = tlimit + tpondered;
 945   }
 946
 947   if ( ! ( game_status & flag_pondering )
 948        && root_nmove == 1
 949        && telapsed > 2000U - time_response ) { return 1; }
 950
 951   if ( tcount > tmax ) { return 1; }
 952
 953   if ( stable && tcount > tlimit ) { return 1; }
 954
 955   if ( stable
 956        && ( tmax_limit_count * 3U < ( time_last_search - time_start ) * 5U ) )
 957     {
 958 #if defined(DBG_EASY)
 959       if ( ! easy_move )
 960         {
 961           Out( "  The search can be terminated "
 962                "before it reaches time-limit.\n" );
 963           easy_move = ptree->pv[0].a[1];
 964         }
 965 #else
 966       Out( "  The search is terminated before it reaches time-limit.\n" );
 967       return 1;
 968 #endif
 969     }
 970
 971   if ( stable
 972        && easy_abs > abs( last_value )
 973        && easy_min < last_value - easy_value
 974        && easy_max > last_value - easy_value )
 975     {
 976       u = tlimit_count / 5U;
 977       if ( u < tpondered ) { ; }
 978       else if ( u - tpondered < 2000U - time_response )
 979         {
 980           u = tpondered + 2000U - time_response;
 981         }
 982       else {
 983         u = ( ( u - tpondered ) / 1000U + 1U ) * 1000U
 984           + tpondered - time_response;
 985       }
 986
 987       if ( tsearched > u )
 988         {
 989           Out( "  The root move %s counted as easy!!\n",
 990                str_CSA_move(root_move_list[0].move) );
 991 #if defined(DBG_EASY)
 992           easy_move = ptree->pv[0].a[1];
 993           easy_abs  = 0;
 994 #else
 995           return 1;
 996 #endif
 997         }
 998       else if ( tsearched + 500U > u ) { easy_time = 1; }
 999     }
1000
1001   /* renew node_per_second */
1002   {
1003     double dn, dd;
1004
1005     dn = (double)node_last_check * 1000.0;
1006     dd = (double)( tnow - time_last_check ) + 0.1;
1007     u  = (unsigned int)( dn / dd );
1008     if      ( node_per_second > u * 2U ) { node_per_second /= 2U; }
1009     else if ( node_per_second < u / 2U ) { node_per_second *= 2U; }
1010     else                                 { node_per_second  = u; }
1011   }
1012
1013   /* renew node_next_signal */
1014   if ( ! ( game_status & flag_pondering ) && root_nmove == 1 )
1015     {
1016       u = 2000U - time_response;
1017     }
1018   else { u = tlimit; }
1019
1020   if ( ! ( game_status & ( flag_pondering | flag_puzzling ) )
1021        && ! easy_time
1022        && u > tcount + 500U )
1023     {
1024       node_next_signal = node_per_second / 4U;
1025     }
1026   else { node_next_signal = node_per_second / 32U; }
1027
1028   /* renew time_last_check and node_last_check */
1029   time_last_check = tnow;
1030   node_last_check = 0;
1031
1032
1033   return 0;
1034 }
1035
1036
1037 int
1038 is_move_check_b( const tree_t * restrict ptree, unsigned int move )
1039 {
1040   const int from = (int)I2From(move);
1041   const int to   = (int)I2To(move);
1042   int is_check, ipiece_move, idirec;
1043   bitboard_t bb;
1044
1045   is_check = 0;
1046
1047   if ( from >= nsquare ) { ipiece_move = From2Drop(from); }
1048   else {
1049     ipiece_move = (int)I2PieceMove(move);
1050     if ( I2IsPromote(move) ) { ipiece_move += promote; }
1051
1052     idirec = (int)adirec[SQ_WKING][from];
1053     if ( idirec && idirec != (int)adirec[SQ_WKING][to]
1054          && is_pinned_on_white_king( ptree, from, idirec ) )
1055       {
1056         is_check = 1;
1057         goto end;
1058       }
1059   }
1060
1061   switch ( ipiece_move )
1062     {
1063     case pawn:
1064       if ( BOARD[to-nfile] == -king ) { is_check = 1; }
1065       break;
1066
1067     case lance:
1068       AttackBLance( bb, to );
1069       if ( BBContract( bb, BB_WKING ) ) { is_check = 1; }
1070       break;
1071
1072     case knight:
1073       if ( BBContract(abb_b_knight_attacks[to],BB_WKING) ) { is_check = 1; }
1074       break;
1075
1076     case silver:
1077       if ( BBContract(abb_b_silver_attacks[to],BB_WKING) ) { is_check = 1; }
1078       break;
1079
1080     case gold:         case pro_pawn:
1081     case pro_lance:    case pro_knight:
1082     case pro_silver:
1083       if ( BBContract(abb_b_gold_attacks[to],BB_WKING) ) { is_check = 1; }
1084       break;
1085
1086     case bishop:
1087       AttackBishop( bb, to );
1088       if ( BBContract( bb, BB_WKING ) ) { is_check = 1; }
1089       break;
1090
1091     case rook:
1092       AttackRook( bb, to );
1093       if ( BBContract( bb, BB_WKING ) ) { is_check = 1; }
1094       break;
1095
1096     case king:
1097       break;
1098
1099     case horse:
1100       AttackHorse( bb, to );
1101       if ( BBContract( bb, BB_WKING ) ) { is_check = 1; }
1102       break;
1103
1104     default:
1105       assert( ipiece_move == dragon );
1106       AttackDragon( bb, to );
1107       if ( BBContract( bb, BB_WKING ) ) { is_check = 1; }
1108       break;
1109     }
1110
1111  end:
1112   return is_check;
1113 }
1114
1115
1116 int
1117 is_move_check_w( const tree_t * restrict ptree, unsigned int move )
1118 {
1119   const int from = (int)I2From(move);
1120   const int to   = (int)I2To(move);
1121   int is_check, ipiece_move, idirec;
1122   bitboard_t bb;
1123
1124   is_check = 0;
1125
1126   if ( from >= nsquare ) { ipiece_move = From2Drop(from); }
1127   else {
1128     ipiece_move = (int)I2PieceMove(move);
1129     if ( I2IsPromote(move) ) { ipiece_move += promote; }
1130
1131     idirec = (int)adirec[SQ_BKING][from];
1132     if ( idirec && idirec != (int)adirec[SQ_BKING][to]
1133          && is_pinned_on_black_king( ptree, from, idirec ) )
1134       {
1135         is_check = 1;
1136         goto end;
1137       }
1138   }
1139
1140   switch ( ipiece_move )
1141     {
1142     case pawn:
1143       if ( BOARD[to+nfile] == king ) { is_check = 1; }
1144       break;
1145
1146     case lance:
1147       AttackWLance( bb, to );
1148       if ( BBContract( bb, BB_BKING ) ) { is_check = 1; }
1149       break;
1150
1151     case knight:
1152       if ( BBContract(abb_w_knight_attacks[to],BB_BKING) ) { is_check = 1; }
1153       break;
1154
1155     case silver:
1156       if ( BBContract(abb_w_silver_attacks[to],BB_BKING) ) { is_check = 1; }
1157       break;
1158
1159     case gold:        case pro_pawn:
1160     case pro_lance:   case pro_knight:
1161     case pro_silver:
1162       if ( BBContract(abb_w_gold_attacks[to],BB_BKING) ) { is_check = 1; }
1163       break;
1164
1165     case bishop:
1166       AttackBishop( bb, to );
1167       if ( BBContract( bb, BB_BKING ) ) { is_check = 1; }
1168       break;
1169
1170     case rook:
1171       AttackRook( bb, to );
1172       if ( BBContract( bb, BB_BKING ) ) { is_check = 1; }
1173       break;
1174
1175     case king:
1176       break;
1177
1178     case horse:
1179       AttackHorse( bb, to );
1180       if ( BBContract( bb, BB_BKING ) ) { is_check = 1; }
1181       break;
1182
1183     default:
1184       assert( ipiece_move == dragon );
1185       AttackDragon( bb, to );
1186       if ( BBContract( bb, BB_BKING ) ) { is_check = 1; }
1187       break;
1188     }
1189
1190  end:
1191   return is_check;
1192 }
1193
1194
1195 void
1196 pv_close( tree_t * restrict ptree, int ply, int type )
1197 {
1198   ptree->pv[ply-1].a[ply-1] = (ptree)->current_move[ply-1];
1199   ptree->pv[ply-1].length   = (unsigned char)(ply-1);
1200   ptree->pv[ply-1].type     = (unsigned char)type;
1201   ptree->pv[ply-1].depth    = (unsigned char)iteration_depth;
1202 }
1203
1204
1205 void
1206 pv_copy( tree_t * restrict ptree, int ply )
1207 {
1208   memcpy( &(ptree->pv[ply-1].a[ply]), &(ptree->pv[ply].a[ply]),
1209           ( ptree->pv[ply].length-ply+1 ) * sizeof(unsigned int) );
1210   ptree->pv[ply-1].type     = ptree->pv[ply].type;
1211   ptree->pv[ply-1].length   = ptree->pv[ply].length;
1212   ptree->pv[ply-1].depth    = ptree->pv[ply].depth;
1213   ptree->pv[ply-1].a[ply-1] = ptree->current_move[ply-1];
1214 }
1215
1216
1217 static int
1218 detect_rep( tree_t * restrict ptree, int ply, int turn )
1219 {
1220   if ( ply < 4 ) { return detect_repetition( ptree, ply, turn, 2 ); }
1221   else {
1222     int n, i, imin, iret;
1223
1224     n    = root_nrep + ply - 1;
1225     imin = n - REP_MAX_PLY;
1226     if ( imin < 0 ) { imin = 0; }
1227
1228     for ( i = n-2; i >= imin; i-- )
1229       if ( ptree->rep_board_list[i] == HASH_KEY )
1230         {
1231           iret = rep_type( ptree, n, i, ply, turn );
1232           if ( iret ) { return iret; }
1233         }
1234   }
1235
1236   return no_rep;
1237 }
1238
1239
1240 static int
1241 rep_type( const tree_t * restrict ptree, int n, int i, int ply, int turn )
1242 {
1243   const unsigned int hand1 = HAND_B;
1244   const unsigned int hand2 = ptree->rep_hand_list[i];
1245
1246   if ( (n-i) & 1 )
1247     {
1248       if ( turn )
1249         {
1250           if ( is_hand_eq_supe( hand2, hand1 ) )  { return white_superi_rep; }
1251         }
1252       else if ( is_hand_eq_supe( hand1, hand2 ) ) { return black_superi_rep; }
1253     }
1254   else if ( hand1 == hand2 )
1255     {
1256       const int ncheck   = (int)ptree->nsuc_check[ply];
1257       const int nchecked = (int)ptree->nsuc_check[ply-1];
1258
1259       if      ( ncheck   * 2 - 2 >= n-i ) { return perpetual_check; }
1260       else if ( nchecked * 2     >= n-i ) { return perpetual_check2; }
1261       else                                { return four_fold_rep; }
1262     }
1263   else if ( is_hand_eq_supe( hand1, hand2 ) ) { return black_superi_rep; }
1264   else if ( is_hand_eq_supe( hand2, hand1 ) ) { return white_superi_rep; }
1265
1266   return no_rep;
1267 }
1268
1269
1270 static void
1271 hist_add( tree_t * restrict ptree, int ply )
1272 {
1273   if ( ptree->nsuc_check[ply] ) { return; }
1274   if ( UToCap(MOVE_CURR) )      { return; }
1275   if ( I2IsPromote(MOVE_CURR)
1276        && I2PieceMove(MOVE_CURR) != silver ) { return; }
1277
1278   assert( ptree->hist_nmove[ply] < MAX_LEGAL_MOVES );
1279   ptree->hist_move[ply][ ptree->hist_nmove[ply]++ ] = MOVE_CURR;
1280 }
1281
1282
1283 static void
1284 hist_good( tree_t * restrict ptree, unsigned int move_good, int ply,
1285            int depth, int turn )
1286 {
1287   unsigned int key, move;
1288   int i, n, value, value_no1, value_no2;
1289
1290   if ( ptree->nsuc_check[ply] ) { return; }
1291
1292   value     = p_value_ex[15+UToCap(move_good)];
1293   value_no1 = p_value_ex[15+BOARD[I2To(ptree->amove_killer[ply].no1)]];
1294   value_no2 = p_value_ex[15+BOARD[I2To(ptree->amove_killer[ply].no2)]];
1295   if ( move_good == ptree->anext_move[ply].move_cap1 )
1296     {
1297       if ( ( ptree->anext_move[ply].phase_done & phase_killer1 )
1298            && UToFromToPromo(move_good) != ptree->amove_killer[ply].no1 )
1299         {
1300           ptree->amove_killer[ply].no1_value
1301             = ptree->anext_move[ply].value_cap1 - value - 1;
1302         }
1303       if ( ( ptree->anext_move[ply].phase_done & phase_killer2 )
1304            && UToFromToPromo(move_good) != ptree->amove_killer[ply].no2 )
1305         {
1306           ptree->amove_killer[ply].no2_value
1307             = ptree->anext_move[ply].value_cap1 - value - 2;
1308         }
1309     }
1310   else if ( UToFromToPromo(move_good) == ptree->amove_killer[ply].no1 )
1311     {
1312       if ( ( ptree->anext_move[ply].phase_done & phase_cap1 )
1313            && ( ptree->amove_killer[ply].no1_value + value
1314                 < ptree->anext_move[ply].value_cap1 + 1 ) )
1315         {
1316           ptree->amove_killer[ply].no1_value
1317             = ptree->anext_move[ply].value_cap1 - value + 1;
1318         }
1319       if ( ( ptree->anext_move[ply].phase_done & phase_killer2 )
1320            && ( ptree->amove_killer[ply].no1_value + value
1321                 < ptree->amove_killer[ply].no2_value + value_no2 + 1 ) )
1322         {
1323           ptree->amove_killer[ply].no1_value
1324             = ptree->amove_killer[ply].no2_value + value_no2 - value + 1;
1325         }
1326     }
1327   else if ( UToFromToPromo(move_good) == ptree->amove_killer[ply].no2 )
1328     {
1329       unsigned int uswap;
1330       int iswap;
1331
1332       if ( ( ptree->anext_move[ply].phase_done & phase_cap1 )
1333            && ( ptree->amove_killer[ply].no2_value + value
1334                 < ptree->anext_move[ply].value_cap1 + 1 ) )
1335         {
1336           ptree->amove_killer[ply].no2_value
1337             = ptree->anext_move[ply].value_cap1 - value + 1;
1338         }
1339       if ( ( ptree->anext_move[ply].phase_done & phase_killer1 )
1340            && ( ptree->amove_killer[ply].no2_value + value
1341                 < ptree->amove_killer[ply].no1_value + value_no1 + 1 ) )
1342         {
1343           ptree->amove_killer[ply].no2_value
1344             = ptree->amove_killer[ply].no1_value + value_no1 - value + 1;
1345         }
1346
1347       uswap = ptree->amove_killer[ply].no1;
1348       ptree->amove_killer[ply].no1 = ptree->amove_killer[ply].no2;
1349       ptree->amove_killer[ply].no2 = uswap;
1350
1351       iswap = ptree->amove_killer[ply].no1_value;
1352       ptree->amove_killer[ply].no1_value = ptree->amove_killer[ply].no2_value;
1353       ptree->amove_killer[ply].no2_value = iswap;
1354     }
1355   else {
1356     ptree->amove_killer[ply].no2 = ptree->amove_killer[ply].no1;
1357     ptree->amove_killer[ply].no1 = UToFromToPromo(move_good);
1358
1359     if ( ptree->anext_move[ply].phase_done & phase_killer1 )
1360       {
1361         i  = swap( ptree, move_good, -MT_CAP_ROOK, MT_CAP_ROOK, turn );
1362         i -= value + 1;
1363
1364         if ( ptree->amove_killer[ply].no1_value > i )
1365           {
1366             ptree->amove_killer[ply].no1_value = i;
1367           }
1368       }
1369     ptree->amove_killer[ply].no2_value = ptree->amove_killer[ply].no1_value;
1370     ptree->amove_killer[ply].no1_value
1371       = ptree->anext_move[ply].value_cap1 - value + 1;
1372   }
1373
1374
1375   if ( UToCap(move_good) ) { return; }
1376   if ( I2IsPromote(move_good)
1377        && I2PieceMove(move_good) != silver ) { return; }
1378
1379   if ( ptree->killers[ply].no1 != move_good )
1380     {
1381       ptree->killers[ply].no2 = ptree->killers[ply].no1;
1382       ptree->killers[ply].no1 = move_good;
1383     }
1384
1385   if ( depth < 1 ) { depth = 1; }
1386
1387   n = ptree->hist_nmove[ply];
1388   for ( i = 0; i < n; i++ )
1389     {
1390       move = ptree->hist_move[ply][i];
1391       assert( is_move_valid( ptree, move, turn ) );
1392
1393       key = phash( move, turn );
1394       if ( ptree->hist_tried[key] >= HIST_MAX )
1395         {
1396           ptree->hist_good[key]  /= 2U;
1397           ptree->hist_tried[key] /= 2U;
1398         }
1399
1400       assert( ptree->hist_tried[key] < HIST_MAX );
1401       ptree->hist_tried[key]
1402         = (unsigned short)( (int)ptree->hist_tried[key] + depth );
1403     }
1404
1405   assert( is_move_valid( ptree, move_good, turn ) );
1406   key = phash( move_good, turn );
1407
1408   assert( ptree->hist_good[key] < HIST_MAX );
1409   ptree->hist_good[key]
1410     = (unsigned short)( (int)ptree->hist_good[key] + depth );
1411 }