search.c

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