iterate.c

   1 #include <assert.h>
   2 #include <limits.h>
   3 #include <string.h>
   4 #include <stdlib.h>
   5 #include "shogi.h"
   6
   7 static void CONV adjust_fmg( void );
   8 static int CONV set_root_alpha( int nfail_low, int root_alpha_old );
   9 static int CONV set_root_beta( int nfail_high, int root_beta_old );
  10 static int CONV is_answer_right( unsigned int move );
  11 static int CONV rep_book_prob( tree_t * restrict ptree );
  12 static const char * CONV str_fail_high( int turn, int nfail_high );
  13
  14
  15 int CONV
  16 iterate( tree_t * restrict ptree )
  17 {
  18   int value, iret, ply;
  19   unsigned int cpu_start;
  20   int right_answer_made;
  21
  22   /* probe the opening book */
  23   if ( pf_book != NULL && ! analyze_mode
  24 #if defined(USI) || defined(MNJ_LAN) || defined(XBOARD)
  25        && moves_ignore[0] == MOVE_NA
  26 #endif
  27        && ! rep_book_prob( ptree ) )
  28     {
  29       int is_book_hit, i;
  30       unsigned int elapsed;
  31
  32       is_book_hit = book_probe( ptree );
  33       if ( is_book_hit < 0 ) { return is_book_hit; }
  34
  35       iret = get_elapsed( &elapsed );
  36       if ( iret < 0 ) { return iret; }
  37
  38       Out( "- opening book is probed. (%ss)\n",
  39            str_time_symple( elapsed - time_start ) );
  40       if ( is_book_hit )
  41         {
  42           pv_close( ptree, 2, book_hit );
  43           last_pv         = ptree->pv[1];
  44           last_root_value = 0;
  45           if ( ! ( game_status & flag_puzzling ) )
  46             {
  47               for ( i = 0; i < (int)HIST_SIZE; i++ )
  48                 {
  49                   ptree->hist_good[i]  /= 256U;
  50                   ptree->hist_tried[i] /= 256U;
  51                 }
  52             }
  53           MnjOut( "pid=%d move=%s n=0 v=0e final%s\n",
  54                   mnj_posi_id, str_CSA_move(ptree->pv[1].a[1]),
  55                   ( mnj_depth_stable == INT_MAX ) ? "" : " stable" );
  56
  57
  58 #if defined(USI)
  59           if ( usi_mode != usi_off )
  60             {
  61               char str_usi[6];
  62               csa2usi( ptree, str_CSA_move(ptree->pv[1].a[1]), str_usi );
  63               USIOut( "info depth 1 score cp 0 nodes 0 pv %s\n", str_usi );
  64             }
  65 #endif
  66
  67           return 1;
  68         }
  69     }
  70
  71   /* detect inaniwa tactics */
  72 #if defined(INANIWA_SHIFT)
  73   if ( ! inaniwa_flag && 19 < ptree->nrep )
  74     {
  75       if ( root_turn == white
  76            && ( BOARD[A7]==-pawn || BOARD[A6]==-pawn || BOARD[A5]==-pawn )
  77            && BOARD[B7] == -pawn && BOARD[C7] == -pawn
  78            && BOARD[D7] == -pawn && BOARD[E7] == -pawn
  79            && BOARD[F7] == -pawn && BOARD[G7] == -pawn
  80            && BOARD[H7] == -pawn
  81            && ( BOARD[I7]==-pawn || BOARD[I6]==-pawn || BOARD[I5]==-pawn ) )
  82         {
  83           Out( "\nINANIWA SHIFT TURNED ON (BLACK)\n\n" );
  84           inaniwa_flag = 1;
  85           ehash_clear();
  86           if ( ini_trans_table() < 0 ) { return -1; }
  87         }
  88
  89       if ( root_turn == black
  90            && ( BOARD[A3]==pawn || BOARD[A4]==pawn || BOARD[A5] == pawn )
  91            && BOARD[B3] == pawn && BOARD[C3] == pawn
  92            && BOARD[D3] == pawn && BOARD[E3] == pawn
  93            && BOARD[F3] == pawn && BOARD[G3] == pawn
  94            && BOARD[H3] == pawn
  95            && ( BOARD[I3]==pawn || BOARD[I4]==pawn || BOARD[I5]==pawn ) )
  96         {
  97           Out( "\nINANIWA SHIFT TURNED ON (WHITE)\n\n" );
  98           inaniwa_flag = 2;
  99           ehash_clear();
 100           if ( ini_trans_table() < 0 ) { return -1; }
 101         }
 102     }
 103 #endif
 104
 105
 106   /* initialize variables */
 107   if ( get_cputime( &cpu_start ) < 0 ) { return -1; }
 108
 109   ptree->node_searched         =  0;
 110   ptree->null_pruning_done     =  0;
 111   ptree->null_pruning_tried    =  0;
 112   ptree->check_extension_done  =  0;
 113   ptree->recap_extension_done  =  0;
 114   ptree->onerp_extension_done  =  0;
 115   ptree->nfour_fold_rep        =  0;
 116   ptree->nperpetual_check      =  0;
 117   ptree->nsuperior_rep         =  0;
 118   ptree->nrep_tried            =  0;
 119   ptree->neval_called          =  0;
 120   ptree->nquies_called         =  0;
 121   ptree->ntrans_always_hit     =  0;
 122   ptree->ntrans_prefer_hit     =  0;
 123   ptree->ntrans_probe          =  0;
 124   ptree->ntrans_exact          =  0;
 125   ptree->ntrans_lower          =  0;
 126   ptree->ntrans_upper          =  0;
 127   ptree->ntrans_superior_hit   =  0;
 128   ptree->ntrans_inferior_hit   =  0;
 129   ptree->fail_high             =  0;
 130   ptree->fail_high_first       =  0;
 131   ptree->current_move[0]       =  0;
 132   ptree->save_eval[0]          =  INT_MAX;
 133   ptree->save_eval[1]          =  INT_MAX;
 134   ptree->pv[0].a[0]            =  0;
 135   ptree->pv[0].a[1]            =  0;
 136   ptree->pv[0].depth           =  0;
 137   ptree->pv[0].length          =  0;
 138   iteration_depth              =  0;
 139   easy_value                   =  0;
 140   easy_abs                     =  0;
 141   right_answer_made            =  0;
 142   root_abort                   =  0;
 143   root_nmove                   =  0;
 144   root_value                   = -score_bound;
 145   root_alpha                   = -score_bound;
 146   root_beta                    =  score_bound;
 147   root_index                   =  0;
 148   root_move_list[0].status     = flag_first;
 149   node_last_check              =  0;
 150   time_last_check              =  time_start;
 151   game_status                 &= ~( flag_move_now | flag_suspend
 152                                     | flag_quit_ponder | flag_search_error );
 153 #if defined(DBG_EASY)
 154   easy_move                    =  0;
 155 #endif
 156
 157 #if defined(USI)
 158   usi_time_out_last            =  time_start;
 159 #endif
 160
 161 #if defined(TLP)
 162   ptree->tlp_abort             = 0;
 163   tlp_nsplit                   = 0;
 164   tlp_nabort                   = 0;
 165   tlp_nslot                    = 0;
 166 #endif
 167
 168 #if defined(MPV)
 169   if ( ! ( game_status & flag_puzzling ) && mpv_num > 1 )
 170     {
 171       int i;
 172
 173       for ( i = 0; i < 2*mpv_num+1; i++ ) { mpv_pv[i].length = 0; }
 174
 175       last_pv.a[0]    = 0;
 176       last_pv.a[1]    = 0;
 177       last_pv.depth   = 0;
 178       last_pv.length  = 0;
 179       last_root_value = 0;
 180
 181       root_mpv = 1;
 182     }
 183   else { root_mpv = 0; }
 184 #endif
 185
 186 #if defined(DFPN_CLIENT)
 187   dfpn_client_rresult_unlocked = dfpn_client_na;
 188   dfpn_client_move_unlocked    = MOVE_NA;
 189   dfpn_client_best_move        = MOVE_NA;
 190   dfpn_client_cresult_index    = 0;
 191 #endif
 192
 193   for ( ply = 0; ply < PLY_MAX; ply++ )
 194     {
 195       ptree->amove_killer[ply].no1 = ptree->amove_killer[ply].no2 = 0U;
 196       ptree->killers[ply].no1 = ptree->killers[ply].no2 = 0x0U;
 197     }
 198
 199   {
 200     unsigned int u =  node_per_second / 16U;
 201     if      ( u > TIME_CHECK_MAX_NODE ) { u = TIME_CHECK_MAX_NODE; }
 202     else if ( u < TIME_CHECK_MIN_NODE ) { u = TIME_CHECK_MIN_NODE; }
 203     node_next_signal = u;
 204   }
 205
 206   set_search_limit_time( root_turn );
 207   adjust_fmg();
 208
 209   Out( "nsuc_check: [0]=%d [1]=%d\n",
 210        (int)ptree->nsuc_check[0], (int)ptree->nsuc_check[1] );
 211
 212   /* look up last pv. */
 213   if ( last_pv.length && ! analyze_mode )
 214     {
 215       Out( "- a pv was found in the previous search result.\n" );
 216
 217       iteration_depth   = ( iteration_depth < 1 ) ? 0 : last_pv.depth - 1;
 218       ptree->pv[0]      = last_pv;
 219       ptree->pv[0].type = prev_solution;
 220       root_value        = root_turn ? -last_root_value : last_root_value;
 221       out_pv( ptree, root_value, root_turn, 0 );
 222       Out( "\n" );
 223     }
 224
 225   /* probe the transposition table, since last pv is not available.  */
 226   if ( ! last_pv.length && ! analyze_mode
 227 #if defined(MPV)
 228        && ! root_mpv
 229 #endif
 230        )
 231     {
 232       unsigned int value_type, dummy;
 233       int alpha, beta;
 234
 235       value = INT_MIN;
 236       for ( ply = 1; ply < PLY_MAX - 10; ply++ )
 237         {
 238           dummy = 0;
 239           alpha = -score_bound;
 240           beta  =  score_bound;
 241
 242           value_type = hash_probe( ptree, 1, ply*PLY_INC+PLY_INC/2,
 243                                    root_turn, alpha, beta, &dummy );
 244           if ( value_type != value_exact )   { break; }
 245           value = HASH_VALUE;
 246       }
 247
 248       if ( -score_bound < value )
 249         {
 250           Out( "- a pv was peeked through the transposition table.\n" );
 251           iteration_depth     = ply-1;
 252           ptree->pv[0].depth  = (unsigned char)(ply-1);
 253           ptree->pv[0].type   = hash_hit;
 254           root_value          = value;
 255           out_pv( ptree, value, root_turn, 0 );
 256           Out( "\n" );
 257
 258           if ( ! ptree->pv[0].length )
 259             {
 260               iteration_depth    = 0;
 261               ptree->pv[0].depth = 0;
 262               root_value         = -score_bound;
 263 #if ! defined(MINIMUM)
 264               out_warning( "PEEK FAILED!!!" );
 265 #endif
 266             }
 267         }
 268     }
 269
 270   /* root move generation */
 271   {
 272     unsigned int elapsed;
 273
 274     Out( "- root move generation" );
 275     value = make_root_move_list( ptree );
 276
 277     if ( ! root_nmove )
 278       {
 279 #if defined(MNJ_LAN) || defined(USI)
 280         if ( moves_ignore[0] != MOVE_NA )
 281           {
 282             MnjOut( "pid=%d move=%%TORYO v=%de n=0 final%s\n",
 283                     mnj_posi_id, -score_bound,
 284                     ( mnj_depth_stable == INT_MAX ) ? "" : " stable" );
 285
 286             return 1;
 287           }
 288 #endif
 289         str_error = str_no_legal_move;
 290         return -2;
 291       }
 292
 293     if ( ! ptree->pv[0].length || ptree->pv[0].a[1] != root_move_list[0].move )
 294       {
 295         iteration_depth     = 0;
 296         ptree->pv[0].a[1]   = root_move_list[0].move;
 297         ptree->pv[0].length = 1;
 298         ptree->pv[0].depth  = 1;
 299         ptree->pv[0].type   = no_rep;
 300         root_value          = value;
 301         root_index          = 0;
 302       }
 303
 304 #if defined(MPV)
 305     if ( root_mpv )
 306       {
 307         if ( root_nmove == 1 ) { root_mpv = 0; }
 308         easy_abs = 0;
 309       }
 310 #endif
 311
 312     if ( get_elapsed( &elapsed ) < 0 ) { return -1; }
 313     Out( " ... done (%d moves, %ss)\n",
 314          root_nmove, str_time_symple( elapsed - time_start ) );
 315   }
 316
 317
 318 #if defined(DFPN_CLIENT)
 319   /* probe results from DFPN searver */
 320   dfpn_client_check_results();
 321   if ( dfpn_client_move_unlocked != MOVE_NA )
 322     {
 323       ptree->pv[0].a[1]   = dfpn_client_move_unlocked;
 324       ptree->pv[0].length = 1;
 325       ptree->pv[0].depth  = 0;
 326       ptree->pv[0].type   = no_rep;
 327       root_value          = score_matelong;
 328     }
 329 #endif
 330
 331
 332   /* save preliminary result */
 333   assert( root_value != -score_bound );
 334   last_root_value = root_turn ? -root_value : root_value;
 335   last_pv         = ptree->pv[0];
 336
 337
 338 #if defined(DFPN_CLIENT)
 339   /* send the best move to DFPN server */
 340   if ( dfpn_client_sckt != SCKT_NULL
 341        && dfpn_client_best_move != ptree->pv[0].a[1] )
 342     {
 343       dfpn_client_best_move = ptree->pv[0].a[1];
 344       lock( &dfpn_client_lock );
 345       dfpn_client_out( "BEST MOVE %s\n", str_CSA_move(dfpn_client_best_move) );
 346       unlock( &dfpn_client_lock );
 347     }
 348 #endif
 349
 350
 351 #if 0 && defined(MNJ_LAN)
 352   /* send the best move to parallel server */
 353   if ( sckt_mnj != SCKT_NULL ) {
 354
 355     if ( moves_ignore[0] == MOVE_NA && root_nmove == 1 ) {
 356     /* only one replay */
 357       MnjOut( "pid=%d move=%s v=%de n=%" PRIu64 " final%s\n",
 358               mnj_posi_id, str_CSA_move(ptree->pv[0].a[1]), root_value,
 359               ptree->node_searched,
 360               ( mnj_depth_stable == INT_MAX ) ? "" : " stable" );
 361
 362       return 1;
 363     }
 364
 365     MnjOut( "pid=%d move=%s v=%de n=%" PRIu64 "\n",
 366             mnj_posi_id, str_CSA_move(ptree->pv[0].a[1]), root_value,
 367             ptree->node_searched );
 368   }
 369 #endif
 370   MnjOut( "pid=%d move=%s v=%de n=%" PRIu64 "\n",
 371           mnj_posi_id, str_CSA_move(ptree->pv[0].a[1]), root_value,
 372           ptree->node_searched );
 373
 374 #if defined(USI)
 375   if ( usi_mode != usi_off )
 376     {
 377       char str_usi[6];
 378       csa2usi( ptree, str_CSA_move(ptree->pv[0].a[1]), str_usi );
 379       USIOut( "info depth %d score cp %d nodes %" PRIu64 " pv %s\n",
 380               iteration_depth, root_value, ptree->node_searched, str_usi );
 381     }
 382 #endif
 383
 384
 385   /* return, if previous pv is long enough */
 386   if ( abs(root_value) > score_max_eval
 387        || iteration_depth >= depth_limit
 388        || ( ( game_status & flag_puzzling )
 389             && ( root_nmove == 1 || ptree->pv[0].depth > 4 ) ) )
 390     {
 391       return 1;
 392     }
 393
 394
 395   /* iterative deepening search */
 396 #if defined(TLP)
 397   iret = tlp_start();
 398   if ( iret < 0 ) { return iret; }
 399 #endif
 400   iteration_depth += 1;
 401   root_beta        = set_root_beta(  0, root_value );
 402   root_alpha       = set_root_alpha( 0, root_value );
 403   root_value       = root_alpha;
 404
 405   Out( "- drive an iterative deepening search starting from depth %d\n",
 406        iteration_depth );
 407
 408   for ( ; iteration_depth < 30/*PLY_MAX-10*/; iteration_depth++ ) {
 409
 410     if ( get_elapsed( &time_last_search ) < 0 ) { return -1; }
 411
 412 #if defined(MPV)
 413     if ( root_mpv )
 414       {
 415         int i;
 416         i = ( root_nmove < mpv_num ) ? root_nmove : mpv_num;
 417         for ( ; i < mpv_num*2; i++ ) { mpv_pv[i].length = 0; }
 418       }
 419 #endif
 420
 421     {
 422       unsigned int move;
 423       int tt, i, n;
 424
 425       tt = root_turn;
 426       for ( ply = 1; ply <= ptree->pv[0].length; ply++ )
 427         {
 428           move = ptree->pv[0].a[ply];
 429           if ( ! is_move_valid( ptree, move, tt ) )
 430             {
 431 #if ! defined(MINIMUM)
 432               out_warning( "Old pv has an illegal move!  ply=%d, move=%s",
 433                            ply, str_CSA_move(move) );
 434 #endif
 435               break;
 436             }
 437           MakeMove( tt, move, ply );
 438           if ( InCheck(tt) )
 439             {
 440 #if ! defined(MINIMUM)
 441               out_warning( "Old pv has an illegal evasion!  ply=%d, move=%s",
 442                            ply, str_CSA_move(move) );
 443 #endif
 444               UnMakeMove( tt, move, ply );
 445               break;
 446             }
 447           tt = Flip(tt);
 448         }
 449       for ( ply--; ply > 0; ply-- )
 450         {
 451           tt   = Flip(tt);
 452           move = ptree->pv[0].a[ply];
 453           UnMakeMove( tt, move, ply );
 454           hash_store_pv( ptree, move, tt );
 455         }
 456
 457       root_nfail_high = 0;
 458       root_nfail_low  = 0;
 459
 460       n = root_nmove;
 461       root_move_list[0].status = flag_first;
 462       for ( i = 1; i < n; i++ ) { root_move_list[i].status = 0; }
 463     }
 464
 465     /*  a trial of searches  */
 466     for ( ;; ) {
 467       value = searchr( ptree, root_alpha, root_beta, root_turn,
 468                        iteration_depth*PLY_INC + PLY_INC/2 );
 469       if ( game_status & flag_search_error ) { return -1; }
 470       if ( root_abort )                      { break; }
 471
 472       assert( abs(value) < score_foul );
 473
 474       if ( root_beta <= value )
 475         {
 476           const char *str_move;
 477           const char *str;
 478           double dvalue;
 479
 480           root_move_list[0].status &= ~flag_searched;
 481           dvalue = (double)( root_turn ? -root_beta : root_beta );
 482
 483           do { root_beta  = set_root_beta( ++root_nfail_high, root_beta ); }
 484           while ( value >= root_beta );
 485
 486 #if defined(DFPN_CLIENT)
 487           if ( dfpn_client_sckt != SCKT_NULL
 488                && 4 < iteration_depth
 489                && dfpn_client_best_move != ptree->pv[1].a[1] )
 490             {
 491               dfpn_client_best_move = ptree->pv[1].a[1];
 492               lock( &dfpn_client_lock );
 493               dfpn_client_out( "BEST MOVE %s\n",
 494                                str_CSA_move(dfpn_client_best_move) );
 495               unlock( &dfpn_client_lock );
 496             }
 497 #endif
 498           MnjOut( "pid=%d move=%s v=%dl n=%" PRIu64 "%s\n",
 499                   mnj_posi_id, str_CSA_move(ptree->pv[1].a[1]),
 500                   root_beta, ptree->node_searched,
 501                   ( mnj_depth_stable <= iteration_depth ) ? " stable" : "" );
 502
 503 #if defined(USI)
 504           if ( usi_mode != usi_off )
 505             {
 506               char str_usi[6];
 507               csa2usi( ptree, str_CSA_move(ptree->pv[1].a[1]), str_usi );
 508               USIOut( "info depth %d score cp %d nodes %" PRIu64 " pv %s\n",
 509                       iteration_depth, root_beta, ptree->node_searched,
 510                       str_usi );
 511             }
 512 #endif
 513
 514           str = str_time_symple( time_last_result - time_start );
 515           if ( root_move_list[0].status & flag_first )
 516             {
 517               Out( "(%2d)%6s %7.2f ", iteration_depth, str, dvalue / 100.0 );
 518             }
 519           else { Out( "    %6s %7.2f ", str, dvalue / 100.0 ); }
 520
 521           str      = str_fail_high( root_turn, root_nfail_high );
 522           str_move = str_CSA_move(ptree->pv[1].a[1]);
 523           Out( " 1.%c%s [%s!]\n", ach_turn[root_turn], str_move, str );
 524
 525
 526           if ( game_status & flag_pondering )
 527             {
 528               OutCsaShogi( "info%+.2f %c%s %c%s [%s!]\n",
 529                            dvalue / 100.0, ach_turn[Flip(root_turn)],
 530                            str_CSA_move(ponder_move),
 531                            ach_turn[root_turn], str_move, str );
 532             }
 533           else {
 534             OutCsaShogi( "info%+.2f %c%s [%s!]\n", dvalue / 100.0,
 535                          ach_turn[root_turn], str_move, str );
 536           }
 537         }
 538       else if ( value <= root_alpha )
 539         {
 540           const char *str_move;
 541           const char *str;
 542           unsigned int time_elapsed;
 543           double dvalue;
 544
 545           if ( ! ( root_move_list[0].status & flag_first ) )
 546             {
 547               root_value = root_alpha;
 548               break;
 549             }
 550
 551           root_move_list[0].status &= ~flag_searched;
 552           dvalue = (double)( root_turn ? -root_alpha : root_alpha );
 553
 554           if ( get_elapsed( &time_elapsed ) < 0 ) { return -1; }
 555
 556           do { root_alpha = set_root_alpha( ++root_nfail_low, root_alpha ); }
 557           while ( value <= root_alpha );
 558           root_value = root_alpha;
 559           str = str_time_symple( time_elapsed - time_start );
 560           Out( "(%2d)%6s %7.2f ", iteration_depth, str, dvalue / 100.0 );
 561
 562           str      = str_fail_high( Flip(root_turn), root_nfail_low );
 563           str_move = str_CSA_move(root_move_list[0].move);
 564           Out( " 1.%c%s [%s?]\n", ach_turn[root_turn], str_move, str );
 565           if ( game_status & flag_pondering )
 566             {
 567               OutCsaShogi( "info%+.2f %c%s %c%s [%s?]\n",
 568                            dvalue / 100.0, ach_turn[Flip(root_turn)],
 569                            str_CSA_move(ponder_move),
 570                            ach_turn[root_turn], str_move, str );
 571             }
 572           else {
 573             OutCsaShogi( "info%+.2f %c%s [%s?]\n", dvalue / 100.0,
 574                          ach_turn[root_turn], str_move, str );
 575           }
 576         }
 577       else { break; }
 578     }
 579
 580     /* the trial of search is finished */
 581     if ( root_alpha < root_value && root_value < root_beta )
 582       {
 583         last_root_value = root_turn ? - root_value : root_value;
 584         last_pv         = ptree->pv[0];
 585       }
 586
 587     if ( root_abort ) { break; }
 588
 589     if ( root_alpha < root_value && root_value < root_beta )
 590       {
 591 #if ! defined(MINIMUM)
 592         {
 593           int i, n;
 594           n = root_nmove;
 595           for ( i = 0; i < n; i++ )
 596             {
 597               if ( root_move_list[i].status & flag_searched ) { continue; }
 598               out_warning( "A root move %s is ignored\n",
 599                            str_CSA_move(root_move_list[i].move) );
 600             }
 601         }
 602 #endif
 603
 604         if ( ( game_status & flag_problem ) && depth_limit == PLY_MAX )
 605           {
 606             if ( is_answer_right( ptree->pv[0].a[1] ) )
 607               {
 608                 if ( right_answer_made > 1 && iteration_depth > 3 ) { break; }
 609                 right_answer_made++;
 610               }
 611             else { right_answer_made = 0; }
 612           }
 613
 614         if ( abs(value)      >  score_max_eval ) { break; }
 615         if ( iteration_depth >= depth_limit )    { break; }
 616
 617         root_beta  = set_root_beta(  0, value );
 618         root_alpha = set_root_alpha( 0, value );
 619         root_value = root_alpha;
 620       }
 621 #if ! defined(MINIMUM)
 622     else { out_warning(( "SEARCH INSTABILITY IS DETECTED!!!" )); }
 623 #endif
 624
 625     /* shell sort */
 626     {
 627       root_move_t root_move_swap;
 628       const int n = root_nmove;
 629       uint64_t sortv;
 630       int i, j, k, h;
 631
 632       for ( k = SHELL_H_LEN - 1; k >= 0; k-- )
 633         {
 634           h = ashell_h[k];
 635           for ( i = n-h-1; i > 0; i-- )
 636             {
 637               root_move_swap = root_move_list[i];
 638               sortv          = root_move_list[i].nodes;
 639               for ( j = i+h; j < n && root_move_list[j].nodes > sortv; j += h )
 640                 {
 641                   root_move_list[j-h] = root_move_list[j];
 642                 }
 643               root_move_list[j-h] = root_move_swap;
 644             }
 645         }
 646     }
 647   }
 648
 649   /* iteration finished */
 650   if ( game_status & flag_problem )
 651     {
 652       if ( is_answer_right( ptree->pv[0].a[1] ) )
 653         {
 654           right_answer_made = 1;
 655         }
 656       else { right_answer_made = 0; }
 657     }
 658
 659   {
 660     int i;
 661
 662     for ( i = 0; i < (int)HIST_SIZE; i++ )
 663       {
 664         ptree->hist_good[i]  /= 256U;
 665         ptree->hist_tried[i] /= 256U;
 666       }
 667   }
 668   /* prunings and extentions-statistics */
 669   {
 670     double drep, dhash, dnull, dfh1st;
 671
 672     drep    = (double)ptree->nperpetual_check;
 673     drep   += (double)ptree->nfour_fold_rep;
 674     drep   += (double)ptree->nsuperior_rep;
 675     drep   *= 100.0 / (double)( ptree->nrep_tried + 1 );
 676
 677     dhash   = (double)ptree->ntrans_exact;
 678     dhash  += (double)ptree->ntrans_inferior_hit;
 679     dhash  += (double)ptree->ntrans_superior_hit;
 680     dhash  += (double)ptree->ntrans_upper;
 681     dhash  += (double)ptree->ntrans_lower;
 682     dhash  *= 100.0 / (double)( ptree->ntrans_probe + 1 );
 683
 684     dnull   = 100.0 * (double)ptree->null_pruning_done;
 685     dnull  /= (double)( ptree->null_pruning_tried + 1 );
 686
 687     dfh1st  = 100.0 * (double)ptree->fail_high_first;
 688     dfh1st /= (double)( ptree->fail_high + 1 );
 689
 690     Out( "    pruning  -> rep=%4.3f%%  hash=%2.0f%%  null=%2.0f%%"
 691          "  fh1st=%4.1f%%\n", drep, dhash, dnull, dfh1st );
 692
 693     Out( "    extension-> chk=%u recap=%u 1rep=%u\n",
 694          ptree->check_extension_done, ptree->recap_extension_done,
 695          ptree->onerp_extension_done );
 696   }
 697
 698   /* futility threashold */
 699 #if ! ( defined(NO_STDOUT) && defined(NO_LOGGING) )
 700   {
 701     int misc   = fmg_misc;
 702     int drop   = fmg_drop;
 703     int cap    = fmg_cap;
 704     int mt     = fmg_mt;
 705     int misc_k = fmg_misc_king;
 706     int cap_k  = fmg_cap_king;
 707     Out( "    futility -> misc=%d drop=%d cap=%d mt=%d misc(k)=%d cap(k)=%d\n",
 708          misc, drop, cap, mt, misc_k, cap_k );
 709   }
 710 #endif
 711
 712   /* hashing-statistics */
 713   {
 714     double dalways, dprefer, dsupe, dinfe;
 715     double dlower, dupper, dsat;
 716     uint64_t word2;
 717     int ntrans_table, i, n;
 718
 719     ntrans_table = 1 << log2_ntrans_table;
 720     if ( ntrans_table > 8192 ) { ntrans_table = 8192; }
 721
 722     for ( i = 0, n = 0; i < ntrans_table; i++ )
 723       {
 724         word2 = ptrans_table[i].prefer.word2;
 725         SignKey( word2, ptrans_table[i].prefer.word1 );
 726         if ( trans_table_age == ( 7 & (int)word2 ) ) { n++; }
 727
 728         word2 = ptrans_table[i].always[0].word2;
 729         SignKey( word2, ptrans_table[i].always[0].word1 );
 730         if ( trans_table_age == ( 7 & (int)word2 ) ) { n++; }
 731
 732         word2 = ptrans_table[i].always[1].word2;
 733         SignKey( word2, ptrans_table[i].always[1].word1 );
 734         if ( trans_table_age == ( 7 & (int)word2 ) ) { n++; }
 735       }
 736
 737     dalways  = 100.0 * (double)ptree->ntrans_always_hit;
 738     dalways /= (double)( ptree->ntrans_probe + 1 );
 739
 740     dprefer  = 100.0 * (double)ptree->ntrans_prefer_hit;
 741     dprefer /= (double)( ptree->ntrans_probe + 1 );
 742
 743     dsupe    = 100.0 * (double)ptree->ntrans_superior_hit;
 744     dsupe   /= (double)( ptree->ntrans_probe + 1 );
 745
 746     dinfe    = 100.0 * (double)ptree->ntrans_inferior_hit;
 747     dinfe   /= (double)( ptree->ntrans_probe + 1 );
 748
 749     Out( "    hashing  -> always=%2.0f%% prefer=%2.0f%% supe=%4.2f%% "
 750          "infe=%4.2f%%\n", dalways, dprefer, dsupe, dinfe );
 751
 752     dlower  = 100.0 * (double)ptree->ntrans_lower;
 753     dlower /= (double)( ptree->ntrans_probe + 1 );
 754
 755     dupper  = 100.0 * (double)ptree->ntrans_upper;
 756     dupper /= (double)( ptree->ntrans_probe + 1 );
 757
 758     dsat    = 100.0 * (double)n;
 759     dsat   /= (double)( 3 * ntrans_table );
 760
 761     OutCsaShogi( "statsatu=%.0f", dsat );
 762     Out( "    hashing  -> "
 763          "exact=%d lower=%2.0f%% upper=%4.2f%% sat=%2.0f%% age=%d\n",
 764          ptree->ntrans_exact, dlower, dupper, dsat, trans_table_age );
 765     if ( dsat > 9.0 ) { trans_table_age  = ( trans_table_age + 1 ) & 0x7; }
 766   }
 767
 768 #if defined(TLP)
 769   if ( tlp_max > 1 )
 770     {
 771       Out( "    threading-> split=%d abort=%d slot=%d\n",
 772            tlp_nsplit, tlp_nabort, tlp_nslot+1 );
 773       if ( tlp_nslot+1 == TLP_NUM_WORK )
 774         {
 775           out_warning( "THREAD WORK AREA IS USED UP!!!" );
 776         }
 777     }
 778 #endif
 779
 780 #if defined(DFPN_CLIENT)
 781   if ( dfpn_client_sckt != SCKT_NULL )
 782     {
 783       int asum[4] = { 0, 0, 0, 0 };
 784       int i, n;
 785
 786       n = root_nmove;
 787       for ( i = 0; i < n; i += 1 )
 788         {
 789           asum[ root_move_list[i].dfpn_cresult ] += 1;
 790         }
 791
 792       switch ( dfpn_client_rresult_unlocked )
 793         {
 794         case dfpn_client_na:
 795           Out( "    dfpn     -> n/a " );
 796           break;
 797
 798         case dfpn_client_win:
 799           if ( dfpn_client_move_unlocked != MOVE_NA )
 800             {
 801               Out( "    dfpn     -> win %s ",
 802                    str_CSA_move(dfpn_client_move_unlocked) );
 803             }
 804           else { Out( "    dfpn     -> win ignore " ); }
 805           break;
 806
 807         case dfpn_client_lose:
 808           Out( "    dfpn     -> lose " );
 809           break;
 810
 811         default:
 812           assert( dfpn_client_misc == dfpn_client_rresult_unlocked );
 813           Out( "    dfpn     -> misc " );
 814           break;
 815         }
 816
 817       Out( "(children win %d, lose %d, misc %d, n/a %d)\n",
 818            asum[dfpn_client_win], asum[dfpn_client_lose],
 819            asum[dfpn_client_misc], asum[dfpn_client_na] );
 820     }
 821   if ( dfpn_client_move_unlocked )
 822     {
 823       last_root_value = root_turn ? -score_matelong : score_matelong;
 824       last_pv.a[1]   = dfpn_client_move_unlocked;
 825       last_pv.length = 1;
 826       last_pv.depth  = 0;
 827       last_pv.type   = no_rep;
 828       MnjOut( "pid=%d move=%s n=0 v=%de final%s\n", mnj_posi_id,
 829               str_CSA_move(last_pv.a[1]), score_matelong,
 830               ( mnj_depth_stable == INT_MAX ) ? "" : " stable" );
 831     }
 832 #endif
 833
 834   {
 835     double dcpu_percent, dnps, dmat;
 836     unsigned int cpu, elapsed;
 837
 838     Out( "    n=%" PRIu64 " quies=%u eval=%u rep=%u %u(chk) %u(supe)\n",
 839          ptree->node_searched, ptree->nquies_called, ptree->neval_called,
 840          ptree->nfour_fold_rep, ptree->nperpetual_check,
 841          ptree->nsuperior_rep );
 842
 843     if ( get_cputime( &cpu )     < 0 ) { return -1; }
 844     if ( get_elapsed( &elapsed ) < 0 ) { return -1; }
 845
 846     cpu             -= cpu_start;
 847     elapsed         -= time_start;
 848
 849     dcpu_percent     = 100.0 * (double)cpu;
 850     dcpu_percent    /= (double)( elapsed + 1U );
 851
 852     dnps             = 1000.0 * (double)ptree->node_searched;
 853     dnps            /= (double)( elapsed + 1U );
 854
 855 #if defined(TLP)
 856     {
 857       double n = (double)tlp_max;
 858       node_per_second  = (unsigned int)( ( dnps + 0.5 ) / n );
 859     }
 860 #else
 861     node_per_second  = (unsigned int)( dnps + 0.5 );
 862 #endif
 863
 864     dmat  = (double)MATERIAL;
 865     dmat /= (double)MT_CAP_PAWN;
 866
 867     OutCsaShogi( " cpu=%.0f nps=%.2f\n", dcpu_percent, dnps / 1e3 );
 868     Out( "    time=%s  ", str_time_symple( elapsed ) );
 869     Out( "cpu=%3.0f%%  mat=%.1f  nps=%.2fK\n", dcpu_percent, dmat, dnps/1e3 );
 870   }
 871
 872   if ( ( game_status & flag_problem ) && ! right_answer_made ) { iret = 0; }
 873   else                                                         { iret = 1; }
 874
 875   return iret;
 876 }
 877
 878
 879 #if defined(USI)
 880 int CONV
 881 usi_root_list( tree_t * restrict ptree )
 882 {
 883 #define SIZE_STR ( MAX_LEGAL_MOVES * 6 + 200 )
 884   char str[ SIZE_STR ];
 885   char str_usi[6];
 886   unsigned int elapsed;
 887   int i, istr;
 888
 889   ptree->node_searched         =  0;
 890   ptree->current_move[0]       =  MOVE_NA;
 891   ptree->save_eval[0]          =  INT_MAX;
 892   ptree->save_eval[1]          =  INT_MAX;
 893   ptree->pv[0].a[0]            =  0;
 894   ptree->pv[0].a[1]            =  0;
 895   ptree->pv[0].depth           =  0;
 896   ptree->pv[0].length          =  0;
 897   easy_value                   =  0;
 898   easy_abs                     =  0;
 899   root_abort                   =  0;
 900   root_nmove                   =  0;
 901   root_value                   = -score_bound;
 902   root_alpha                   = -score_bound;
 903   root_beta                    =  score_bound;
 904   node_last_check              =  0;
 905   game_status                 &= ~( flag_move_now | flag_suspend
 906                                     | flag_quit_ponder | flag_search_error );
 907
 908   Out( "- root move generation" );
 909   make_root_move_list( ptree );
 910
 911   if ( game_status & flag_search_error ) { return -1; }
 912   if ( game_status & ( flag_quit | flag_quit_ponder | flag_suspend ) )
 913     {
 914       return 1;
 915     }
 916
 917   if ( ! root_nmove )
 918     {
 919       str_error = "No legal moves to search";
 920       return -1;
 921     }
 922
 923   if ( get_elapsed( &elapsed ) < 0 ) { return -1; }
 924   Out( " ... done (%d moves, %ss)\n",
 925        root_nmove, str_time_symple( elapsed - time_start ) );
 926
 927   istr = snprintf( str, SIZE_STR, "genmove_probability" );
 928   for ( i = 0; i < root_nmove; i++ )
 929     {
 930       csa2usi( ptree, str_CSA_move(root_move_list[i].move), str_usi );
 931       istr += snprintf( str + istr, SIZE_STR - istr, " %s %d",
 932                         str_usi, i + 1 );
 933     }
 934
 935   USIOut( "%s\n", str );
 936   return 1;
 937 }
 938
 939
 940 int CONV
 941 usi_book( tree_t * restrict ptree )
 942 {
 943   char str_usi[6];
 944   int is_book_hit;
 945
 946   if ( pf_book == NULL || rep_book_prob( ptree  ) )
 947     {
 948       USIOut( "bestmove pass\n" );
 949       return 1;
 950     }
 951
 952   is_book_hit = book_probe( ptree );
 953   if ( is_book_hit < 0 ) { return is_book_hit; }
 954
 955   if ( ! is_book_hit )
 956     {
 957       USIOut( "bestmove pass\n" );
 958       return 1;
 959     }
 960
 961   csa2usi( ptree, str_CSA_move(ptree->current_move[1]), str_usi );
 962   USIOut( "bestmove %s\n", str_usi );
 963   return 1;
 964 }
 965 #endif
 966
 967
 968 #if defined(DFPN_CLIENT)
 969 void CONV
 970 dfpn_client_check_results( void )
 971 {
 972   int i, n, index, num;
 973
 974   n = root_nmove;
 975   lock( &dfpn_client_lock );
 976
 977   if ( dfpn_client_rresult_unlocked == dfpn_client_na )
 978     {
 979       dfpn_client_rresult_unlocked = dfpn_client_rresult;
 980       if ( dfpn_client_rresult == dfpn_client_win
 981            && dfpn_client_move_unlocked == MOVE_NA )
 982         {
 983           for ( i = 0; i < n; i += 1 )
 984             if ( ! strcmp( (const char *)dfpn_client_str_move,
 985                            str_CSA_move(root_move_list[i].move) ) )
 986               {
 987                 dfpn_client_move_unlocked = root_move_list[i].move;
 988                 break;
 989               }
 990         }
 991     }
 992
 993   num = dfpn_client_num_cresult;
 994   for ( index = dfpn_client_cresult_index; index < num; index += 1 )
 995     {
 996       for ( i = 0; i < n; i += 1 ) {
 997
 998         if ( root_move_list[i].dfpn_cresult != dfpn_client_na ) { continue; }
 999
1000         if ( ! strcmp( (const char *)dfpn_client_cresult[index].str_move,
1001                        str_CSA_move(root_move_list[i].move) ) ) {
1002
1003           root_move_list[i].dfpn_cresult
1004             = (int)dfpn_client_cresult[index].result;
1005           break;
1006         }
1007       }
1008     }
1009
1010   dfpn_client_cresult_index = index;
1011   dfpn_client_flag_read     = 0;
1012   unlock( &dfpn_client_lock );
1013 }
1014 #endif
1015
1016
1017 static int CONV rep_book_prob( tree_t * restrict ptree )
1018 {
1019   int i;
1020
1021   for ( i = ptree->nrep - 2; i >= 0; i -= 2 )
1022     if ( ptree->rep_board_list[i] == HASH_KEY
1023          && ptree->rep_hand_list[i] == HAND_B )
1024       {
1025         Out( "- book is ignored due to a repetition.\n" );
1026         return 1;
1027       }
1028
1029   return 0;
1030 }
1031
1032
1033 static void CONV adjust_fmg( void )
1034 {
1035   int misc, cap, drop, mt, misc_king, cap_king;
1036
1037   misc      = fmg_misc      - FMG_MG      / 2;
1038   cap       = fmg_cap       - FMG_MG      / 2;
1039   drop      = fmg_drop      - FMG_MG      / 2;
1040   misc_king = fmg_misc_king - FMG_MG_KING / 2;
1041   cap_king  = fmg_cap_king  - FMG_MG_KING / 2;
1042   mt        = fmg_mt        - FMG_MG_MT   / 2;
1043
1044   fmg_misc      = ( misc      < FMG_MISC      ) ? FMG_MISC      : misc;
1045   fmg_cap       = ( cap       < FMG_CAP       ) ? FMG_CAP       : cap;
1046   fmg_drop      = ( drop      < FMG_DROP      ) ? FMG_DROP      : drop;
1047   fmg_misc_king = ( misc_king < FMG_MISC_KING ) ? FMG_MISC_KING : misc_king;
1048   fmg_cap_king  = ( cap_king  < FMG_CAP_KING  ) ? FMG_CAP_KING  : cap_king;
1049   fmg_mt        = ( mt        < FMG_MT        ) ? FMG_MT        : mt;
1050 }
1051
1052
1053 static int CONV set_root_beta( int nfail_high, int root_beta_old )
1054 {
1055   int aspiration_hwdth, aspiration_fail1;
1056
1057   if ( time_max_limit != time_limit )
1058     {
1059       aspiration_hwdth = MT_CAP_DRAGON / 8;
1060       aspiration_fail1 = MT_CAP_DRAGON / 2;
1061     }
1062   else {
1063     aspiration_hwdth = MT_CAP_DRAGON / 4;
1064     aspiration_fail1 = ( MT_CAP_DRAGON * 3 ) / 4;
1065   }
1066
1067   switch ( nfail_high )
1068     {
1069     case 0:  root_beta_old += aspiration_hwdth;                     break;
1070     case 1:  root_beta_old += aspiration_fail1 - aspiration_hwdth;  break;
1071     case 2:  root_beta_old  = score_bound;                          break;
1072     default:
1073       out_error( "Error at set_root_beta!" );
1074       exit(1);
1075     }
1076   if ( root_beta_old > score_max_eval ) { root_beta_old = score_bound; }
1077
1078   return root_beta_old;
1079 }
1080
1081
1082 static int CONV set_root_alpha( int nfail_low, int root_alpha_old )
1083 {
1084   int aspiration_hwdth, aspiration_fail1;
1085
1086   if ( time_max_limit != time_limit )
1087     {
1088       aspiration_hwdth = MT_CAP_DRAGON / 8;
1089       aspiration_fail1 = MT_CAP_DRAGON / 2;
1090     }
1091   else {
1092     aspiration_hwdth = MT_CAP_DRAGON / 4;
1093     aspiration_fail1 = ( MT_CAP_DRAGON * 3 ) / 4;
1094   }
1095
1096   switch ( nfail_low )
1097     {
1098     case 0:  root_alpha_old -= aspiration_hwdth;                     break;
1099     case 1:  root_alpha_old -= aspiration_fail1 - aspiration_hwdth;  break;
1100     case 2:  root_alpha_old  = -score_bound;                         break;
1101     default:
1102       out_error( "Error at set_root_alpha!" );
1103       exit(1);
1104     }
1105   if ( root_alpha_old < -score_max_eval ) { root_alpha_old = -score_bound; }
1106
1107   return root_alpha_old;
1108 }
1109
1110
1111 static const char * CONV str_fail_high( int turn, int nfail_high )
1112 {
1113   const char *str;
1114
1115   if ( time_max_limit != time_limit )
1116     {
1117       if ( nfail_high == 1 ) { str = turn ? "-1" : "+1"; }
1118       else                   { str = turn ? "-4" : "+4"; }
1119     }
1120   else {
1121     if ( nfail_high == 1 ) { str = turn ? "-2" : "+2"; }
1122     else                   { str = turn ? "-6" : "+6"; }
1123   }
1124   return str;
1125 }
1126
1127
1128 static int CONV is_answer_right( unsigned int move )
1129 {
1130   const char *str_anser;
1131   const char *str_move;
1132   int ianser, iret;
1133
1134   iret     = 0;
1135   str_move = str_CSA_move( move );
1136
1137   for ( ianser = 0; ianser < MAX_ANSWER; ianser++ )
1138     {
1139       str_anser = &( record_problems.info.str_move[ianser][0] );
1140       if ( str_anser[0] == '\0' ) { break; }
1141       if ( ! strcmp( str_anser+1, str_move ) )
1142         {
1143           iret = 1;
1144           break;
1145         }
1146     }
1147
1148   return iret;
1149 }