searchr.c

   1 #include <assert.h>
   2 #include <stdlib.h>
   3 #include <string.h>
   4 #include <limits.h>
   5 #include "shogi.h"
   6
   7 static int CONV save_result( tree_t * restrict ptree, int value, int beta,
   8                              int turn );
   9
  10 #if defined(MPV)
  11 static int CONV mpv_set_bound( int alpha );
  12 static int CONV mpv_find_min( int *pnum );
  13 static int CONV mpv_add_result( tree_t * restrict ptree, int value );
  14 static void CONV mpv_sub_result( unsigned int move );
  15 static void CONV mpv_out( tree_t * restrict ptree, int turn,
  16                           unsigned int time );
  17 #endif
  18
  19 #if defined(NO_STDOUT) && defined(NO_LOGGING)
  20 #  define NextRootMove(a,b) next_root_move(a)
  21 static int CONV next_root_move( tree_t * restrict ptree );
  22 #else
  23 #  define NextRootMove(a,b) next_root_move(a,b)
  24 static int CONV next_root_move( tree_t * restrict ptree, int turn );
  25 #endif
  26
  27 #ifdef XBOARD
  28 extern char xboard_mode;
  29 #endif
  30
  31 static int CONV
  32 search_wrapper( tree_t * restrict ptree, int alpha, int beta, int turn,
  33                 int depth, int ply, unsigned int state_node )
  34 {
  35   int value;
  36
  37 #if defined(DFPN_CLIENT)
  38   /* try beta cut using results from DFPN server */
  39   if ( root_move_list[root_index].dfpn_cresult == dfpn_client_win )
  40     {
  41       if ( ! root_index ) { Out( "- best move is proofed, skip.\n" ); }
  42       ptree->pv[1].a[1]   = MOVE_LAST;
  43       ptree->pv[1].length = 1;
  44       ptree->pv[1].depth  = 0;
  45       ptree->pv[1].type   = no_rep;
  46       MOVE_CURR           = MOVE_NA;
  47       return score_matelong;
  48     }
  49 #endif
  50
  51   value = search( ptree, alpha, beta, turn, depth, ply, state_node );
  52
  53 #if defined(DFPN_CLIENT)
  54   /* catch a signal, i.e., the first move has to be ignored */
  55   if ( game_status & flag_skip_root_move )
  56     {
  57       if ( root_index )
  58         {
  59           Out( "- %s is proofed while searching.\n", str_CSA_move(MOVE_LAST) );
  60         }
  61       else {
  62         Out( "- %s (best move) is proofed while searching.\n",
  63              str_CSA_move(MOVE_LAST) );
  64       }
  65
  66       game_status &= ~flag_skip_root_move;
  67       root_abort          = 0;
  68
  69       ptree->pv[1].a[1]   = MOVE_LAST;
  70       ptree->pv[1].length = 1;
  71       ptree->pv[1].depth  = 0;
  72       ptree->pv[1].type   = no_rep;
  73       MOVE_CURR           = MOVE_NA;
  74       return score_matelong;
  75     }
  76 #endif
  77
  78   return value;
  79 }
  80
  81
  82 int CONV
  83 searchr( tree_t * restrict ptree, int alpha, int beta, int turn, int depth )
  84 {
  85   uint64_t root_nodes_start;
  86   int value, first_move;
  87   int new_depth, extension, ply, state_node_new;
  88 #if defined(MPV)
  89   int bound = INT_MIN;
  90 #endif
  91 #if defined(USI)
  92   char str_usi[6];
  93 #endif
  94
  95   first_move          = 1;
  96   ply                 = 1;
  97   ptree->move_last[1] = ptree->move_last[0];
  98
  99   while( NextRootMove( ptree, turn ) )
 100     {
 101       root_nodes_start = ptree->node_searched;
 102 #if defined(USI)
 103       if ( usi_mode != usi_off )
 104         {
 105           csa2usi( ptree, str_CSA_move(MOVE_CURR), str_usi );
 106         }
 107 #endif
 108
 109       MakeMove( turn, MOVE_CURR, 1 );
 110
 111       assert( ! InCheck( turn ) );
 112
 113       state_node_new = ( node_do_mate | node_do_null | node_do_futile
 114                          | node_do_recap | node_do_recursion
 115                          | node_do_hashcut );
 116       if ( InCheck(Flip(turn)) )
 117         {
 118           ptree->check_extension_done++;
 119           ptree->nsuc_check[2] = (unsigned char)( ptree->nsuc_check[0] + 1U );
 120           extension            = EXT_CHECK - PLY_INC;
 121         }
 122       else {
 123         extension            = - PLY_INC;
 124         ptree->nsuc_check[2] = 0;
 125       }
 126
 127       if ( first_move )
 128         {
 129 #if defined(MPV)
 130           if ( root_mpv ) { bound = alpha; }
 131 #endif
 132           new_depth = depth + extension;
 133           value = -search_wrapper( ptree, -beta, -alpha, Flip(turn),
 134                                    new_depth, 2, state_node_new );
 135           if ( root_abort )
 136             {
 137               UnMakeMove( turn, MOVE_CURR, 1 );
 138               return 0;
 139             }
 140
 141           if ( value <= alpha )
 142             {
 143               UnMakeMove( turn, MOVE_CURR, 1 );
 144               return value;
 145             }
 146
 147           first_move = 0;
 148         }
 149 #if defined(MPV)
 150       else if ( root_mpv )
 151         {
 152           bound = mpv_set_bound( alpha );
 153           if ( depth + extension >= PLY_INC || ptree->nsuc_check[2] )
 154             {
 155               new_depth = depth + extension;
 156
 157               value = -search_wrapper( ptree, -bound-1, -bound, Flip(turn),
 158                                        new_depth, 2, state_node_new );
 159               if ( ! root_abort && bound < value )
 160                 {
 161                   new_depth = depth + extension;
 162                   value = -search_wrapper( ptree, -beta, -bound, Flip(turn),
 163                                            new_depth, 2, state_node_new );
 164                 }
 165               if ( root_abort )
 166                 {
 167                   UnMakeMove( turn, MOVE_CURR, 1 );
 168                   return 0;
 169                 }
 170             }
 171           else {
 172             value = -search_quies( ptree, -beta, -bound, Flip(turn), 2, 1 );
 173           }
 174         }
 175 #endif /* MPV */
 176       else {
 177         int depth_reduced = 0;
 178         new_depth = depth + extension;
 179
 180         /* reductions */
 181         if ( 2*PLY_INC <= new_depth
 182              && ! ptree->nsuc_check[ply]
 183              && ! UToCap(MOVE_CURR)
 184              && ! ( I2IsPromote(MOVE_CURR)
 185                     && I2PieceMove(MOVE_CURR) != silver ) )
 186           {
 187             unsigned int key     = phash( MOVE_CURR, turn );
 188             unsigned int good    = ptree->hist_good[key]  + 1;
 189             unsigned int triedx8 = ( ptree->hist_tried[key] + 2 ) * 8U;
 190
 191             if      ( good *160U < triedx8 ) { depth_reduced = PLY_INC * 3/2; }
 192             else if ( good * 50U < triedx8 ) { depth_reduced = PLY_INC * 2/2; }
 193             else if ( good * 19U < triedx8 ) { depth_reduced = PLY_INC * 1/2; }
 194
 195             depth_reduced = PLY_INC;
 196             new_depth    -= depth_reduced;
 197           }
 198
 199         value = -search_wrapper( ptree, -alpha-1, -alpha, Flip(turn),
 200                                  new_depth, 2, state_node_new );
 201         if ( ! root_abort && alpha < value && depth_reduced )
 202           {
 203             new_depth += depth_reduced;
 204             value = -search_wrapper( ptree, -alpha-1, -alpha, Flip(turn),
 205                                      new_depth, 2, state_node_new );
 206           }
 207         if ( root_abort )
 208           {
 209             UnMakeMove( turn, MOVE_CURR, 1 );
 210             return 0;
 211           }
 212
 213         if ( alpha < value )
 214           {
 215 #if defined(DFPN_CLIENT)
 216             if ( dfpn_client_sckt != SCKT_NULL
 217                  && 4 < iteration_depth
 218                  && dfpn_client_best_move != MOVE_CURR )
 219               {
 220                 dfpn_client_best_move = MOVE_CURR;
 221                 lock( &dfpn_client_lock );
 222                 dfpn_client_out( "BEST MOVE %s\n",
 223                                  str_CSA_move(dfpn_client_best_move) );
 224                 unlock( &dfpn_client_lock );
 225               }
 226 #endif
 227             MnjOut( "pid=%d move=%s v=%dl n=% " PRIu64 "%s\n",
 228                     mnj_posi_id, str_CSA_move(MOVE_CURR), alpha+1,
 229                     ptree->node_searched,
 230                     ( mnj_depth_stable <= iteration_depth ) ? " stable" : "" );
 231
 232 #if defined(USI)
 233             if ( usi_mode != usi_off )
 234               {
 235                 USIOut( "info depth %d score cp %d nodes %" PRIu64 " pv %s\n",
 236                         iteration_depth, alpha+1, ptree->node_searched,
 237                         str_usi );
 238               }
 239 #endif
 240
 241             new_depth = depth + extension;
 242             easy_abs  = 0;
 243             value = -search_wrapper( ptree, -beta, -alpha, Flip(turn),
 244                                      new_depth, 2, state_node_new );
 245             if ( root_abort )
 246               {
 247                 const char *str;
 248                 double dvalue;
 249                 char ch;
 250
 251                 UnMakeMove( turn, MOVE_CURR, 1 );
 252                 pv_close( ptree, 2, pv_fail_high );
 253                 time_last_result     = time_last_check;
 254                 root_value           = alpha+1;
 255                 ptree->pv[0]         = ptree->pv[1];
 256                 if ( turn )
 257                   {
 258                     dvalue = -(double)alpha;
 259                     ch     = '-';
 260                   }
 261                 else {
 262                   dvalue = alpha;
 263                   ch     = '+';
 264                 }
 265                 str = str_CSA_move(MOVE_CURR);
 266                 Out( "           %7.2f  1.%c%s [%c0!]\n",
 267                      dvalue / 100.0, ch, str, ch );
 268                 if ( game_status & flag_pondering )
 269                   {
 270                     OutCsaShogi( "info%+.2f %c%s %c%s [%c0!]\n",
 271                                  dvalue / 100.0, ach_turn[Flip(turn)],
 272                                  str_CSA_move(ponder_move),
 273                                  ch, str, ch );
 274                   }
 275                 else {
 276                   OutCsaShogi( "info%+.2f %c%s [%c0!]\n",
 277                                dvalue / 100.0, ch, str, ch );
 278                 }
 279                 return 0;
 280               }
 281           }
 282       }
 283
 284       UnMakeMove( turn, MOVE_CURR, 1 );
 285
 286       root_move_list[root_index].nodes
 287         = ptree->node_searched - root_nodes_start;
 288
 289 #if defined(MPV)
 290       if ( root_mpv && value < beta )
 291         {
 292           mpv_sub_result( MOVE_CURR );
 293           if ( bound < value && mpv_add_result( ptree, value ) < 0 )
 294             {
 295               game_status |= flag_search_error;
 296               return 0;
 297             }
 298         }
 299 #endif
 300
 301       if ( alpha < value )
 302         {
 303           if ( save_result( ptree, value, beta, turn ) < 0 )
 304             {
 305               game_status |= flag_search_error;
 306               return 0;
 307             }
 308           if ( beta <= value ) { return value; }
 309           alpha = value;
 310         }
 311     }
 312   if ( root_abort ) { return 0; }
 313
 314   return alpha;
 315 }
 316
 317
 318 void CONV
 319 out_pv( tree_t * restrict ptree, int value, int turn, unsigned int time )
 320 {
 321 #if defined(USI)
 322   char str_pv[256];
 323   int ipv;
 324 #endif
 325   const char *str;
 326   double dvalue;
 327   int ply, tt, is_out;
 328
 329   tt     = turn;
 330   is_out = ( 4 < iteration_depth || abs(value) > score_max_eval ) ? 1 : 0;
 331
 332 #if defined(MPV)
 333   if ( root_mpv ) { is_out = 0; }
 334 #endif
 335
 336 #if defined(USI)
 337   if ( usi_mode != usi_off )
 338     {
 339       is_out    = 1;
 340       ipv       = 0;
 341       str_pv[0] = '\0';
 342     }
 343 #endif
 344
 345   if ( is_out )
 346     {
 347       str    = str_time_symple( time );
 348       dvalue = (double)( turn ? -value : value ) / 100.0;
 349       OutCsaShogi( "info%+.2f", dvalue );
 350       if ( game_status & flag_pondering )
 351         {
 352           OutCsaShogi( " %c%s", ach_turn[Flip(turn)],
 353                        str_CSA_move(ponder_move) );
 354         }
 355
 356       if ( ptree->pv[0].length )
 357         {
 358 #ifdef XBOARD
 359           if(xboard_mode) Out("%2d %6d %6d %8d ", iteration_depth, value, time/10, 1); else
 360 #endif
 361           if ( root_move_list[root_index].status & flag_first )
 362             {
 363               Out( " %2d %6s %7.2f ", iteration_depth, str, dvalue );
 364             }
 365           else { Out( "    %6s %7.2f ", str, dvalue ); }
 366         }
 367     }
 368
 369   for ( ply = 1; ply <= ptree->pv[0].length; ply++ )
 370     {
 371 #ifdef XBOARD
 372       if(xboard_mode && is_out) { // print PV move in WB format
 373         int move = ptree->pv[0].a[ply], from = I2From(move), to = I2To(move);
 374         char inPromoZone = tt > 0 ? from >= 6*9 || to >= 6*9 : to < 3*9|| from < 3*9;
 375         if(from >= nsquare)
 376           Out(" %c@%c%c", "PLNSGBR"[From2Drop(from)-1], 'a'+to%9, '9'-to/9);
 377         else
 378           Out(" %c%c%c%c%s", 'a'+from%9, '9'-from/9, 'a'+to%9, '9'-to/9,
 379               inPromoZone ? I2IsPromote(move) ? "+" : "=" : "");
 380       } else
 381 #endif
 382       if ( is_out )
 383         {
 384           if ( ply > 1 && ! ( (ply-1) % 5 ) )
 385             {
 386               Out( "\n                   " );
 387             }
 388           str = str_CSA_move( ptree->pv[0].a[ply] );
 389           OutCsaShogi( " %c%s", ach_turn[tt], str );
 390           Out( "%2d.%c%-7s", ply, ach_turn[tt], str );
 391
 392 #if defined(USI)
 393           if ( usi_mode != usi_off && ply <= 4 )
 394             {
 395               char str_usi[6];
 396               csa2usi( ptree, str_CSA_move(ptree->pv[0].a[ply]), str_usi );
 397               ipv += snprintf( str_pv + ipv, 256 - ipv, " %s", str_usi );
 398             }
 399 #endif
 400         }
 401
 402       MakeMove( tt, ptree->pv[0].a[ply], ply );
 403       tt    = Flip(tt);
 404       value = -value;
 405     }
 406
 407   if ( ptree->pv[0].type == hash_hit )
 408     {
 409       unsigned int dummy;
 410       int i, value_type;
 411
 412       for ( ; ply < PLY_MAX; ply++ )
 413         {
 414           dummy = 0;
 415           ptree->amove_hash[ply] = 0;
 416           value_type = hash_probe( ptree, ply, 0, tt, -score_bound,
 417                                    score_bound, &dummy );
 418           if ( ! ( value_type == value_exact
 419                    && value   == HASH_VALUE
 420                    && is_move_valid( ptree, ptree->amove_hash[ply], tt ) ) )
 421             {
 422               break;
 423             }
 424           ptree->pv[0].a[ply] = ptree->amove_hash[ply];
 425           for ( i = 1; i < ply; i++ )
 426             if ( ptree->pv[0].a[i] == ptree->pv[0].a[ply] ) { goto rep_esc; }
 427
 428 #ifdef XBOARD
 429       if(xboard_mode && is_out) { // print PV move in WB format
 430         int move = ptree->pv[0].a[ply], from = I2From(move), to = I2To(move);
 431         char inPromoZone = tt > 0 ? from >= 6*9 || to >= 6*9 : to < 3*9|| from < 3*9;
 432         if(from >= nsquare)
 433           Out(" %c@%c%c", "PLNSGBR"[From2Drop(from)-1], 'a'+to%9, '9'-to/9);
 434         else
 435           Out(" %c%c%c%c%s", 'a'+from%9, '9'-from/9, 'a'+to%9, '9'-to/9,
 436               inPromoZone ? I2IsPromote(move) ? "+" : "=" : "");
 437       } else
 438 #endif
 439           if ( is_out )
 440             {
 441               if ( ply > 1 && ! ( (ply-1) % 5 ) )
 442                 {
 443                   Out( "\n                   " );
 444                 }
 445               str = str_CSA_move(ptree->pv[0].a[ply]);
 446               OutCsaShogi( " %c%s", ach_turn[tt], str );
 447               Out( "%2d:%c%-7s", ply, ach_turn[tt], str );
 448
 449 #if defined(USI)
 450               if ( usi_mode != usi_off && ply <= 4 )
 451                 {
 452                   char str_usi[6];
 453                   csa2usi( ptree, str_CSA_move(ptree->pv[0].a[ply]), str_usi );
 454                   ipv += snprintf( str_pv + ipv, 256 - ipv, " %s", str_usi );
 455                 }
 456 #endif
 457             }
 458
 459           MakeMove( tt, ptree->pv[0].a[ply], ply );
 460           if ( InCheck(tt) )
 461             {
 462               UnMakeMove( tt, ptree->amove_hash[ply], ply );
 463               break;
 464             }
 465           ptree->pv[0].length++;
 466           tt    = Flip(tt);
 467           value = -value;
 468         }
 469     }
 470  rep_esc:
 471
 472   if ( is_out && ptree->pv[0].type != no_rep )
 473     {
 474       if ( (((ply-1) % 5) == 0) && (ply != 1) )
 475         {
 476           Out( "\n                   " );
 477         }
 478       str = NULL;
 479       switch ( ptree->pv[0].type )
 480         {
 481         case perpetual_check:  str = "PER. CHECK";     break;
 482         case four_fold_rep:    str = "REPETITION";     break;
 483         case black_superi_rep:
 484         case white_superi_rep: str = "SUPERI. POSI.";  break;
 485         case prev_solution:    str = "PREV. SEARCH";   break;
 486         case hash_hit:         str = "HASH HIT";       break;
 487         case book_hit:         str = "BOOK HIT";       break;
 488         case pv_fail_high:     str = "FAIL HIGH";      break;
 489         case mate_search:      str = "MATE SEARCH";    break;
 490         }
 491       if ( str != NULL ) { Out( " <%s>", str ); }
 492     }
 493   for ( ply--; ply >= 1; ply-- )
 494     {
 495       tt    = Flip(tt);
 496       value = -value;
 497       UnMakeMove( tt, ptree->pv[0].a[ply], ply );
 498     }
 499
 500   if ( is_out )
 501     {
 502       OutCsaShogi( "\n" );
 503       Out( "\n" );
 504       USIOut( "info depth %d score cp %d nodes %" PRIu64 " pv%s\n",
 505               iteration_depth, value, ptree->node_searched, str_pv );
 506     }
 507 }
 508
 509
 510 static int CONV
 511 save_result( tree_t * restrict ptree, int value, int beta, int turn )
 512 {
 513   root_move_t root_move_temp;
 514   int index;
 515
 516   if ( get_elapsed( &time_last_result ) < 0 ) { return -1; }
 517
 518   index = root_index;
 519   if ( index )
 520     {
 521       root_move_temp = root_move_list[index];
 522       for ( ; index > 0; index-- )
 523         {
 524           root_move_list[index] = root_move_list[index-1];
 525         }
 526       root_move_list[0] = root_move_temp;
 527     }
 528   root_index = 0;
 529   if ( beta <= value ) { pv_close( ptree, 2, pv_fail_high ); }
 530
 531   ptree->pv[0] = ptree->pv[1];
 532   root_value   = value;
 533
 534   if ( value < beta )
 535     {
 536 #if defined(DFPN_CLIENT)
 537       if ( dfpn_client_sckt != SCKT_NULL
 538            && 4 < iteration_depth
 539            && dfpn_client_best_move != ptree->pv[1].a[1] )
 540         {
 541           dfpn_client_best_move = ptree->pv[1].a[1];
 542           lock( &dfpn_client_lock );
 543           dfpn_client_out( "BEST MOVE %s\n",
 544                            str_CSA_move(dfpn_client_best_move) );
 545           unlock( &dfpn_client_lock );
 546         }
 547 #endif
 548       MnjOut( "pid=%d move=%s v=%de n=%" PRIu64 "%s\n",
 549               mnj_posi_id, str_CSA_move(ptree->pv[1].a[1]), value,
 550               ptree->node_searched,
 551               ( mnj_depth_stable <= iteration_depth ) ? " stable" : "" );
 552
 553       out_pv( ptree, value, turn, time_last_result - time_start );
 554     }
 555
 556   return 1;
 557 }
 558
 559
 560 static int CONV
 561 #if defined(NO_STDOUT) && defined(NO_LOGGING)
 562 next_root_move( tree_t * restrict ptree )
 563 #else
 564 next_root_move( tree_t * restrict ptree, int turn )
 565 #endif
 566 {
 567   int i, n;
 568
 569   n = root_nmove;
 570   for ( i = 0; i < n; i++ )
 571     {
 572       if ( root_move_list[i].status & flag_searched ) { continue; }
 573       root_move_list[i].status |= flag_searched;
 574       ptree->current_move[1]    = root_move_list[i].move;
 575       root_index                = i;
 576
 577 #if ! ( defined(NO_STDOUT) && defined(NO_LOGGING) )
 578 #ifdef XBOARD
 579       if(!xboard_mode)
 580 #endif
 581       if ( iteration_depth > 5 )
 582         {
 583           const char *str_move;
 584           char str[9];
 585
 586           str_move = str_CSA_move(ptree->current_move[1]);
 587           snprintf( str, 9, "%d/%d", i+1, root_nmove );
 588           if ( root_move_list[i].status & flag_first )
 589             {
 590               Out( "(%2d)       %7s* 1.%c%s     \r",
 591                    iteration_depth, str, ach_turn[turn], str_move );
 592             }
 593           else {
 594             Out( "           %7s* 1.%c%s     \r",
 595                  str, ach_turn[turn], str_move );
 596           }
 597         }
 598 #endif
 599
 600       return 1;
 601     }
 602
 603   return 0;
 604 }
 605
 606
 607 #if defined(MPV)
 608 static void CONV
 609 mpv_out( tree_t * restrict ptree, int turn, unsigned int time )
 610 {
 611   int mpv_out, ipv, best;
 612
 613   best    = (int)mpv_pv[0].a[0] - 32768;
 614   mpv_out = ( iteration_depth > 3 || abs(best) > score_max_eval ) ? 1 : 0;
 615
 616   for ( ipv = 0; mpv_pv[ipv].length; ipv++ )
 617     {
 618       const char *str;
 619       double dvalue;
 620       int tt, is_out, value, ply;
 621
 622       assert( ipv < mpv_num*2 );
 623       tt     = turn;
 624       value  = (int)mpv_pv[ipv].a[0] - 32768;
 625       if ( mpv_out && value > best - mpv_width && ipv < mpv_num )
 626         {
 627           is_out = 1;
 628         }
 629       else { is_out = 0; }
 630
 631       if ( is_out )
 632         {
 633           dvalue = (double)( turn ? -value : value ) / 100.0;
 634           if ( is_out && ! ipv ) { OutCsaShogi( "info" ); }
 635           if ( is_out && ipv )   { OutCsaShogi( ":" ); }
 636
 637           OutCsaShogi( "%+.2f", dvalue );
 638           if ( game_status & flag_pondering )
 639             {
 640               OutCsaShogi( " %c%s", ach_turn[Flip(turn)],
 641                            str_CSA_move(ponder_move) );
 642             }
 643
 644           str = str_time_symple( time );
 645           ply = mpv_pv[ipv].depth;
 646           if ( ! ipv ) { Out( "o%2d %6s %7.2f ", ply, str, dvalue ); }
 647           else         { Out( " %2d        %7.2f ", ply, dvalue ); }
 648         }
 649
 650       for ( ply = 1; ply <= mpv_pv[ipv].length; ply++ )
 651         {
 652           if ( is_out )
 653             {
 654               if ( ply > 1 && ! ( (ply-1) % 5 ) )
 655                 {
 656                   Out( "\n                   " );
 657                 }
 658               str = str_CSA_move(mpv_pv[ipv].a[ply]);
 659               OutCsaShogi( " %c%s", ach_turn[tt], str );
 660               Out( "%2d.%c%-11s", ply, ach_turn[tt], str );
 661             }
 662
 663           assert( is_move_valid( ptree, mpv_pv[ipv].a[ply], tt ) );
 664           MakeMove( tt, mpv_pv[ipv].a[ply], ply );
 665           tt    = Flip(tt);
 666           value = -value;
 667         }
 668
 669       if ( mpv_pv[ipv].type == hash_hit )
 670         {
 671           unsigned int dummy;
 672           int i, value_type;
 673
 674           for ( ; ply < PLY_MAX; ply++ )
 675             {
 676               dummy = 0;
 677               ptree->amove_hash[ply] = 0;
 678               value_type = hash_probe( ptree, ply, 0, tt, -score_bound,
 679                                        score_bound, &dummy );
 680               if ( ! ( value_type == value_exact
 681                        && value   == HASH_VALUE
 682                        && is_move_valid(ptree,ptree->amove_hash[ply],tt) ) )
 683                 {
 684                   break;
 685                 }
 686               mpv_pv[ipv].a[ply] = ptree->amove_hash[ply];
 687               for ( i = 1; i < ply; i++ )
 688                 if ( mpv_pv[ipv].a[i]
 689                      == mpv_pv[ipv].a[ply] ) { goto rep_esc; }
 690
 691               if ( is_out )
 692                 {
 693                   if ( ply > 1 && ! ( (ply-1) % 5 ) )
 694                     {
 695                       Out( "\n                   " );
 696                     }
 697                   str = str_CSA_move(mpv_pv[ipv].a[ply]);
 698                   OutCsaShogi( " %c%s", ach_turn[tt], str );
 699                   Out( "%2d:%c%-11s", ply, ach_turn[tt], str );
 700                 }
 701
 702               MakeMove( tt, mpv_pv[ipv].a[ply], ply );
 703               if ( InCheck(tt) )
 704                 {
 705                   UnMakeMove( tt, ptree->amove_hash[ply], ply );
 706                   break;
 707                 }
 708               mpv_pv[ipv].length++;
 709               tt    = Flip(tt);
 710               value = -value;
 711             }
 712         }
 713     rep_esc:
 714
 715       if ( is_out && mpv_pv[ipv].type != no_rep )
 716         {
 717           if ( (((ply-1) % 5) == 0) && (ply != 1) )
 718             {
 719               Out( "\n                   " );
 720             }
 721           str = NULL;
 722           switch ( mpv_pv[ipv].type )
 723             {
 724             case perpetual_check:  str = "PER. CHECK";     break;
 725             case four_fold_rep:    str = "REPETITION";     break;
 726             case black_superi_rep:
 727             case white_superi_rep: str = "SUPERI. POSI.";  break;
 728             case prev_solution:    str = "PREV. SEARCH";   break;
 729             case hash_hit:         str = "HASH HIT";       break;
 730             case book_hit:         str = "BOOK HIT";       break;
 731             case pv_fail_high:     str = "FAIL HIGH";      break;
 732             case mate_search:      str = "MATE SEARCH";    break;
 733             }
 734           if ( str != NULL ) { Out( " <%s>", str ); }
 735         }
 736       for ( ply--; ply >= 1; ply-- )
 737         {
 738           tt = Flip(tt);
 739           UnMakeMove( tt, mpv_pv[ipv].a[ply], ply );
 740         }
 741
 742       if ( is_out ) { Out( "\n" ); }
 743     }
 744
 745   if ( mpv_out ) { OutCsaShogi( "\n" ); }
 746 }
 747
 748
 749 static void CONV
 750 mpv_sub_result( unsigned int move )
 751 {
 752   int i;
 753
 754   for ( i = 0; mpv_pv[i].length; i++ )
 755     {
 756       assert( i < mpv_num*2 );
 757       assert( i < root_nmove*2 );
 758       assert( mpv_pv[i].depth <= iteration_depth );
 759       assert( -score_bound < (int)mpv_pv[i].a[0]-32768 );
 760       assert( (int)mpv_pv[i].a[0]-32768 < score_bound );
 761
 762       if ( mpv_pv[i].a[1] == move ) { break; }
 763     }
 764
 765   for ( ; mpv_pv[i].length; i++ )
 766     {
 767       assert( i < mpv_num*2 );
 768       assert( i < root_nmove*2 );
 769       assert( mpv_pv[i].depth <= iteration_depth );
 770       assert( -score_bound < (int)mpv_pv[i].a[0]-32768 );
 771       assert( (int)mpv_pv[i].a[0]-32768 < score_bound );
 772
 773       mpv_pv[i] = mpv_pv[i+1];
 774     }
 775 }
 776
 777
 778 static int CONV
 779 mpv_add_result( tree_t * restrict ptree, int value )
 780 {
 781   pv_t pv_tmp, pv;
 782   unsigned int time;
 783   int i, vmin, num;
 784
 785   vmin = mpv_find_min( &num );
 786   assert( num <= mpv_num );
 787   assert( num < root_nmove );
 788   assert( -score_bound < value );
 789   assert( value < score_bound  );
 790
 791   /* remove the weakest pv if all of slots are full */
 792   if ( num == mpv_num )
 793     {
 794       for ( i = 0; mpv_pv[i].length; i++ )
 795         {
 796           assert( i < mpv_num*2 );
 797           assert( i < root_nmove*2 );
 798           assert( mpv_pv[i].depth <= iteration_depth );
 799           assert( -score_bound < (int)mpv_pv[i].a[0]-32768 );
 800           assert( (int)mpv_pv[i].a[0]-32768 < score_bound );
 801
 802           if ( mpv_pv[i].depth == iteration_depth
 803                && mpv_pv[i].a[0] == (unsigned int)(vmin+32768) ) { break; }
 804         }
 805       assert( i != mpv_num*2 );
 806       assert( mpv_pv[i].length );
 807       do {
 808         assert( i < mpv_num*2 );
 809         assert( i < root_nmove*2 );
 810         mpv_pv[i] = mpv_pv[i+1];
 811         i++;
 812       } while ( mpv_pv[i].length );
 813     }
 814
 815   /* add a pv */
 816   for ( i = 0; mpv_pv[i].length; i++ )
 817     {
 818       assert( i < mpv_num*2 );
 819       assert( i < root_nmove*2 );
 820       assert( -score_bound < (int)mpv_pv[i].a[0]-32768 );
 821       assert( (int)mpv_pv[i].a[0]-32768 < score_bound );
 822
 823       if ( mpv_pv[i].a[0] < (unsigned int)(value+32768) ) { break; }
 824     }
 825
 826   pv      = ptree->pv[1];
 827   pv.a[0] = (unsigned int)(value+32768);
 828   do {
 829     assert( i < mpv_num*2 );
 830     assert( i < root_nmove*2 );
 831     pv_tmp      = mpv_pv[i];
 832     mpv_pv[i] = pv;
 833     pv          = pv_tmp;
 834     i          += 1;
 835   } while ( pv.length );
 836
 837   if ( get_elapsed( &time ) < 0 ) { return -1; }
 838
 839   mpv_out( ptree, root_turn, time - time_start );
 840
 841   return 1;
 842 }
 843
 844
 845 static int CONV
 846 mpv_set_bound( int alpha )
 847 {
 848   int bound, num, value;
 849
 850   bound = alpha - mpv_width;
 851   if ( bound < -score_bound ) { bound = -score_bound; }
 852
 853   value = mpv_find_min( &num );
 854   assert( num <= mpv_num );
 855   assert( num < root_nmove );
 856   assert( num );
 857   assert( -score_bound < value );
 858   assert( value < score_bound  );
 859   if ( num == mpv_num && bound < value ) { bound = value; }
 860
 861   return bound;
 862 }
 863
 864
 865 static int CONV
 866 mpv_find_min( int *pnum )
 867 {
 868   int i, num;
 869   unsigned int a[ MPV_MAX_PV+1 ], u, utemp;
 870
 871   a[0] = 0;
 872   num  = 0;
 873   for ( i = 0; mpv_pv[i].length; i++ )
 874     {
 875       assert( i < mpv_num*2 );
 876       assert( i < root_nmove*2 );
 877       assert( mpv_pv[i].depth <= iteration_depth );
 878
 879       if ( mpv_pv[i].depth == iteration_depth )
 880         {
 881           u = mpv_pv[i].a[0];
 882           assert( -score_bound < (int)u-32768 );
 883           assert( (int)u-32768 < score_bound );
 884
 885           for ( num = 0; u <= a[num]; num++ );
 886           do {
 887             assert( num < mpv_num );
 888             assert( num < root_nmove );
 889             utemp  = a[num];
 890             a[num] = u;
 891             u      = utemp;
 892             num   += 1;
 893           } while ( u );
 894           a[num] = 0;
 895         }
 896     }
 897
 898   if ( pnum ) { *pnum = num; }
 899
 900   if ( num ) { return (int)a[num-1] - 32768; }
 901
 902   return 0;
 903 }
 904 #endif