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