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) {
 374             Out("%2d %6d %6d %8d ", iteration_depth, value, time/10, 1);
 375             if(game_status & flag_pondering && ! analyze_mode) {
 376               Out("("); out_xboard_move( ponder_move, 1-tt ); Out(") ");
 377             }
 378           } else
 379 #endif
 380           if ( root_move_list[root_index].status & flag_first )
 381             {
 382               Out( " %2d %6s %7.2f ", iteration_depth, str, dvalue );
 383             }
 384           else { Out( "    %6s %7.2f ", str, dvalue ); }
 385         }
 386     }
 387
 388   for ( ply = 1; ply <= ptree->pv[0].length; ply++ )
 389     {
 390 #ifdef XBOARD
 391       if(xboard_mode && is_out) { // print PV move in WB format
 392         out_xboard_move( ptree->pv[0].a[ply], tt );
 393       } else
 394 #endif
 395       if ( is_out )
 396         {
 397           if ( ply > 1 && ! ( (ply-1) % 5 ) )
 398             {
 399               Out( "\n                   " );
 400             }
 401           str = str_CSA_move( ptree->pv[0].a[ply] );
 402           OutCsaShogi( " %c%s", ach_turn[tt], str );
 403           Out( "%2d.%c%-7s", ply, ach_turn[tt], str );
 404
 405 #if defined(USI)
 406           if ( usi_mode != usi_off && ply <= 4 )
 407             {
 408               char str_usi[6];
 409               csa2usi( ptree, str_CSA_move(ptree->pv[0].a[ply]), str_usi );
 410               ipv += snprintf( str_pv + ipv, 256 - ipv, " %s", str_usi );
 411             }
 412 #endif
 413         }
 414
 415       MakeMove( tt, ptree->pv[0].a[ply], ply );
 416       tt    = Flip(tt);
 417       value = -value;
 418     }
 419
 420   if ( ptree->pv[0].type == hash_hit )
 421     {
 422       unsigned int dummy;
 423       int i, value_type;
 424
 425       for ( ; ply < PLY_MAX; ply++ )
 426         {
 427           dummy = 0;
 428           ptree->amove_hash[ply] = 0;
 429           value_type = hash_probe( ptree, ply, 0, tt, -score_bound,
 430                                    score_bound, &dummy );
 431           if ( ! ( value_type == value_exact
 432                    && value   == HASH_VALUE
 433                    && is_move_valid( ptree, ptree->amove_hash[ply], tt ) ) )
 434             {
 435               break;
 436             }
 437           ptree->pv[0].a[ply] = ptree->amove_hash[ply];
 438           for ( i = 1; i < ply; i++ )
 439             if ( ptree->pv[0].a[i] == ptree->pv[0].a[ply] ) { goto rep_esc; }
 440
 441 #ifdef XBOARD
 442       if(xboard_mode && is_out) { // print PV move in WB format
 443         out_xboard_move( ptree->pv[0].a[ply], tt );
 444       } else
 445 #endif
 446           if ( is_out )
 447             {
 448               if ( ply > 1 && ! ( (ply-1) % 5 ) )
 449                 {
 450                   Out( "\n                   " );
 451                 }
 452               str = str_CSA_move(ptree->pv[0].a[ply]);
 453               OutCsaShogi( " %c%s", ach_turn[tt], str );
 454               Out( "%2d:%c%-7s", ply, ach_turn[tt], str );
 455
 456 #if defined(USI)
 457               if ( usi_mode != usi_off && ply <= 4 )
 458                 {
 459                   char str_usi[6];
 460                   csa2usi( ptree, str_CSA_move(ptree->pv[0].a[ply]), str_usi );
 461                   ipv += snprintf( str_pv + ipv, 256 - ipv, " %s", str_usi );
 462                 }
 463 #endif
 464             }
 465
 466           MakeMove( tt, ptree->pv[0].a[ply], ply );
 467           if ( InCheck(tt) )
 468             {
 469               UnMakeMove( tt, ptree->amove_hash[ply], ply );
 470               break;
 471             }
 472           ptree->pv[0].length++;
 473           tt    = Flip(tt);
 474           value = -value;
 475         }
 476     }
 477  rep_esc:
 478
 479   if ( is_out && ptree->pv[0].type != no_rep )
 480     {
 481       if ( (((ply-1) % 5) == 0) && (ply != 1) )
 482         {
 483           Out( "\n                   " );
 484         }
 485       str = NULL;
 486       switch ( ptree->pv[0].type )
 487         {
 488         case perpetual_check:  str = "PER. CHECK";     break;
 489         case four_fold_rep:    str = "REPETITION";     break;
 490         case black_superi_rep:
 491         case white_superi_rep: str = "SUPERI. POSI.";  break;
 492         case prev_solution:    str = "PREV. SEARCH";   break;
 493         case hash_hit:         str = "HASH HIT";       break;
 494         case book_hit:         str = "BOOK HIT";       break;
 495         case pv_fail_high:     str = "FAIL HIGH";      break;
 496         case mate_search:      str = "MATE SEARCH";    break;
 497         }
 498       if ( str != NULL ) { Out( " <%s>", str ); }
 499     }
 500   for ( ply--; ply >= 1; ply-- )
 501     {
 502       tt    = Flip(tt);
 503       value = -value;
 504       UnMakeMove( tt, ptree->pv[0].a[ply], ply );
 505     }
 506
 507   if ( is_out )
 508     {
 509       OutCsaShogi( "\n" );
 510       Out( "\n" );
 511       USIOut( "info depth %d score cp %d nodes %" PRIu64 " pv%s\n",
 512               iteration_depth, value, ptree->node_searched, str_pv );
 513     }
 514 }
 515
 516
 517 static int CONV
 518 save_result( tree_t * restrict ptree, int value, int beta, int turn )
 519 {
 520   root_move_t root_move_temp;
 521   int index;
 522
 523   if ( get_elapsed( &time_last_result ) < 0 ) { return -1; }
 524
 525   index = root_index;
 526   if ( index )
 527     {
 528       root_move_temp = root_move_list[index];
 529       for ( ; index > 0; index-- )
 530         {
 531           root_move_list[index] = root_move_list[index-1];
 532         }
 533       root_move_list[0] = root_move_temp;
 534     }
 535   root_index = 0;
 536   if ( beta <= value ) { pv_close( ptree, 2, pv_fail_high ); }
 537
 538   ptree->pv[0] = ptree->pv[1];
 539   root_value   = value;
 540
 541   if ( value < beta )
 542     {
 543 #if defined(DFPN_CLIENT)
 544       if ( dfpn_client_sckt != SCKT_NULL
 545            && 4 < iteration_depth
 546            && dfpn_client_best_move != ptree->pv[1].a[1] )
 547         {
 548           dfpn_client_best_move = ptree->pv[1].a[1];
 549           lock( &dfpn_client_lock );
 550           dfpn_client_out( "BEST MOVE %s\n",
 551                            str_CSA_move(dfpn_client_best_move) );
 552           unlock( &dfpn_client_lock );
 553         }
 554 #endif
 555       MnjOut( "pid=%d move=%s v=%de n=%" PRIu64 "%s\n",
 556               mnj_posi_id, str_CSA_move(ptree->pv[1].a[1]), value,
 557               ptree->node_searched,
 558               ( mnj_depth_stable <= iteration_depth ) ? " stable" : "" );
 559
 560       out_pv( ptree, value, turn, time_last_result - time_start );
 561     }
 562
 563   return 1;
 564 }
 565
 566
 567 static int CONV
 568 #if defined(NO_STDOUT) && defined(NO_LOGGING)
 569 next_root_move( tree_t * restrict ptree )
 570 #else
 571 next_root_move( tree_t * restrict ptree, int turn )
 572 #endif
 573 {
 574   int i, n;
 575
 576   n = root_nmove;
 577   for ( i = 0; i < n; i++ )
 578     {
 579       if ( root_move_list[i].status & flag_searched ) { continue; }
 580       root_move_list[i].status |= flag_searched;
 581       ptree->current_move[1]    = root_move_list[i].move;
 582       root_index                = i;
 583
 584 #if ! ( defined(NO_STDOUT) && defined(NO_LOGGING) )
 585 #ifdef XBOARD
 586       if(!xboard_mode)
 587 #endif
 588       if ( iteration_depth > 5 )
 589         {
 590           const char *str_move;
 591           char str[9];
 592
 593           str_move = str_CSA_move(ptree->current_move[1]);
 594           snprintf( str, 9, "%d/%d", i+1, root_nmove );
 595           if ( root_move_list[i].status & flag_first )
 596             {
 597               Out( "(%2d)       %7s* 1.%c%s     \r",
 598                    iteration_depth, str, ach_turn[turn], str_move );
 599             }
 600           else {
 601             Out( "           %7s* 1.%c%s     \r",
 602                  str, ach_turn[turn], str_move );
 603           }
 604         }
 605 #endif
 606
 607       return 1;
 608     }
 609
 610   return 0;
 611 }
 612
 613
 614 #if defined(MPV)
 615 static void CONV
 616 mpv_out( tree_t * restrict ptree, int turn, unsigned int time, int newest )
 617 {
 618   int mpv_out, ipv, best;
 619
 620   best    = (int)mpv_pv[0].a[0] - 32768;
 621   mpv_out = ( iteration_depth > 3 || abs(best) > score_max_eval ) ? 1 : 0;
 622
 623   for ( ipv = 0; mpv_pv[ipv].length; ipv++ )
 624     {
 625       const char *str;
 626       double dvalue;
 627       int tt, is_out, value, ply;
 628
 629       assert( ipv < mpv_num*2 );
 630       tt     = turn;
 631       value  = (int)mpv_pv[ipv].a[0] - 32768;
 632       if ( mpv_out && value > best - mpv_width && ipv < mpv_num )
 633         {
 634           is_out = 1;
 635         }
 636       else { is_out = 0; }
 637
 638       if ( is_out )
 639         {
 640           dvalue = (double)( turn ? -value : value ) / 100.0;
 641           if ( is_out && ! ipv ) { OutCsaShogi( "info" ); }
 642           if ( is_out && ipv )   { OutCsaShogi( ":" ); }
 643
 644           OutCsaShogi( "%+.2f", dvalue );
 645           if ( game_status & flag_pondering )
 646             {
 647               OutCsaShogi( " %c%s", ach_turn[Flip(turn)],
 648                            str_CSA_move(ponder_move) );
 649             }
 650
 651           str = str_time_symple( time );
 652           ply = mpv_pv[ipv].depth;
 653 #ifdef XBOARD
 654           if(xboard_mode) {
 655             if(ipv != newest) continue; // skip all but the newest, to prevent duplicates
 656             Out("%2d %6d %6d %8d ", ply, value, time/10, 1);
 657           } else
 658 #endif
 659           if ( ! ipv ) { Out( "o%2d %6s %7.2f ", ply, str, dvalue ); }
 660           else         { Out( " %2d        %7.2f ", ply, dvalue ); }
 661         }
 662
 663       for ( ply = 1; ply <= mpv_pv[ipv].length; ply++ )
 664         {
 665 #ifdef XBOARD
 666       if(xboard_mode && is_out) { // print PV move in WB format
 667         out_xboard_move( mpv_pv[ipv].a[ply], tt );
 668       } else
 669 #endif
 670           if ( is_out )
 671             {
 672               if ( ply > 1 && ! ( (ply-1) % 5 ) )
 673                 {
 674                   Out( "\n                   " );
 675                 }
 676               str = str_CSA_move(mpv_pv[ipv].a[ply]);
 677               OutCsaShogi( " %c%s", ach_turn[tt], str );
 678               Out( "%2d.%c%-11s", ply, ach_turn[tt], str );
 679             }
 680
 681           assert( is_move_valid( ptree, mpv_pv[ipv].a[ply], tt ) );
 682           MakeMove( tt, mpv_pv[ipv].a[ply], ply );
 683           tt    = Flip(tt);
 684           value = -value;
 685         }
 686
 687       if ( mpv_pv[ipv].type == hash_hit )
 688         {
 689           unsigned int dummy;
 690           int i, value_type;
 691
 692           for ( ; ply < PLY_MAX; ply++ )
 693             {
 694               dummy = 0;
 695               ptree->amove_hash[ply] = 0;
 696               value_type = hash_probe( ptree, ply, 0, tt, -score_bound,
 697                                        score_bound, &dummy );
 698               if ( ! ( value_type == value_exact
 699                        && value   == HASH_VALUE
 700                        && is_move_valid(ptree,ptree->amove_hash[ply],tt) ) )
 701                 {
 702                   break;
 703                 }
 704               mpv_pv[ipv].a[ply] = ptree->amove_hash[ply];
 705               for ( i = 1; i < ply; i++ )
 706                 if ( mpv_pv[ipv].a[i]
 707                      == mpv_pv[ipv].a[ply] ) { goto rep_esc; }
 708
 709 #ifdef XBOARD
 710       if(xboard_mode && is_out) { // print PV move in WB format
 711         out_xboard_move( mpv_pv[ipv].a[ply], tt );
 712       } else
 713 #endif
 714               if ( is_out )
 715                 {
 716                   if ( ply > 1 && ! ( (ply-1) % 5 ) )
 717                     {
 718                       Out( "\n                   " );
 719                     }
 720                   str = str_CSA_move(mpv_pv[ipv].a[ply]);
 721                   OutCsaShogi( " %c%s", ach_turn[tt], str );
 722                   Out( "%2d:%c%-11s", ply, ach_turn[tt], str );
 723                 }
 724
 725               MakeMove( tt, mpv_pv[ipv].a[ply], ply );
 726               if ( InCheck(tt) )
 727                 {
 728                   UnMakeMove( tt, ptree->amove_hash[ply], ply );
 729                   break;
 730                 }
 731               mpv_pv[ipv].length++;
 732               tt    = Flip(tt);
 733               value = -value;
 734             }
 735         }
 736     rep_esc:
 737
 738       if ( is_out && mpv_pv[ipv].type != no_rep )
 739         {
 740           if ( (((ply-1) % 5) == 0) && (ply != 1) )
 741             {
 742               Out( "\n                   " );
 743             }
 744           str = NULL;
 745           switch ( mpv_pv[ipv].type )
 746             {
 747             case perpetual_check:  str = "PER. CHECK";     break;
 748             case four_fold_rep:    str = "REPETITION";     break;
 749             case black_superi_rep:
 750             case white_superi_rep: str = "SUPERI. POSI.";  break;
 751             case prev_solution:    str = "PREV. SEARCH";   break;
 752             case hash_hit:         str = "HASH HIT";       break;
 753             case book_hit:         str = "BOOK HIT";       break;
 754             case pv_fail_high:     str = "FAIL HIGH";      break;
 755             case mate_search:      str = "MATE SEARCH";    break;
 756             }
 757           if ( str != NULL ) { Out( " <%s>", str ); }
 758         }
 759       for ( ply--; ply >= 1; ply-- )
 760         {
 761           tt = Flip(tt);
 762           UnMakeMove( tt, mpv_pv[ipv].a[ply], ply );
 763         }
 764
 765       if ( is_out ) { Out( "\n" ); }
 766     }
 767
 768   if ( mpv_out ) { OutCsaShogi( "\n" ); }
 769 }
 770
 771
 772 static void CONV
 773 mpv_sub_result( unsigned int move )
 774 {
 775   int i;
 776
 777   for ( i = 0; mpv_pv[i].length; i++ )
 778     {
 779       assert( i < mpv_num*2 );
 780       assert( i < root_nmove*2 );
 781       assert( mpv_pv[i].depth <= iteration_depth );
 782       assert( -score_bound < (int)mpv_pv[i].a[0]-32768 );
 783       assert( (int)mpv_pv[i].a[0]-32768 < score_bound );
 784
 785       if ( mpv_pv[i].a[1] == move ) { break; }
 786     }
 787
 788   for ( ; mpv_pv[i].length; i++ )
 789     {
 790       assert( i < mpv_num*2 );
 791       assert( i < root_nmove*2 );
 792       assert( mpv_pv[i].depth <= iteration_depth );
 793       assert( -score_bound < (int)mpv_pv[i].a[0]-32768 );
 794       assert( (int)mpv_pv[i].a[0]-32768 < score_bound );
 795
 796       mpv_pv[i] = mpv_pv[i+1];
 797     }
 798 }
 799
 800
 801 static int CONV
 802 mpv_add_result( tree_t * restrict ptree, int value )
 803 {
 804   pv_t pv_tmp, pv;
 805   unsigned int time;
 806   int i, vmin, num, new_pv;
 807
 808   vmin = mpv_find_min( &num );
 809   assert( num <= mpv_num );
 810   assert( num < root_nmove );
 811   assert( -score_bound < value );
 812   assert( value < score_bound  );
 813
 814   /* remove the weakest pv if all of slots are full */
 815   if ( num == mpv_num )
 816     {
 817       for ( i = 0; mpv_pv[i].length; i++ )
 818         {
 819           assert( i < mpv_num*2 );
 820           assert( i < root_nmove*2 );
 821           assert( mpv_pv[i].depth <= iteration_depth );
 822           assert( -score_bound < (int)mpv_pv[i].a[0]-32768 );
 823           assert( (int)mpv_pv[i].a[0]-32768 < score_bound );
 824
 825           if ( mpv_pv[i].depth == iteration_depth
 826                && mpv_pv[i].a[0] == (unsigned int)(vmin+32768) ) { break; }
 827         }
 828       assert( i != mpv_num*2 );
 829       assert( mpv_pv[i].length );
 830       do {
 831         assert( i < mpv_num*2 );
 832         assert( i < root_nmove*2 );
 833         mpv_pv[i] = mpv_pv[i+1];
 834         i++;
 835       } while ( mpv_pv[i].length );
 836     }
 837
 838   /* add a pv */
 839   for ( i = 0; mpv_pv[i].length; i++ )
 840     {
 841       assert( i < mpv_num*2 );
 842       assert( i < root_nmove*2 );
 843       assert( -score_bound < (int)mpv_pv[i].a[0]-32768 );
 844       assert( (int)mpv_pv[i].a[0]-32768 < score_bound );
 845
 846       if ( mpv_pv[i].a[0] < (unsigned int)(value+32768) ) { break; }
 847     }
 848
 849   pv      = ptree->pv[1];
 850   pv.a[0] = (unsigned int)(value+32768);
 851   new_pv = i; // [HGM] xboard: remember which is the new one, so we can print only that
 852   do {
 853     assert( i < mpv_num*2 );
 854     assert( i < root_nmove*2 );
 855     pv_tmp      = mpv_pv[i];
 856     mpv_pv[i] = pv;
 857     pv          = pv_tmp;
 858     i          += 1;
 859   } while ( pv.length );
 860
 861   if ( get_elapsed( &time ) < 0 ) { return -1; }
 862
 863   mpv_out( ptree, root_turn, time - time_start, new_pv );
 864
 865   return 1;
 866 }
 867
 868
 869 static int CONV
 870 mpv_set_bound( int alpha )
 871 {
 872   int bound, num, value;
 873
 874   bound = alpha - mpv_width;
 875   if ( bound < -score_bound ) { bound = -score_bound; }
 876
 877   value = mpv_find_min( &num );
 878   assert( num <= mpv_num );
 879   assert( num < root_nmove );
 880   assert( num );
 881   assert( -score_bound < value );
 882   assert( value < score_bound  );
 883   if ( num == mpv_num && bound < value ) { bound = value; }
 884
 885   return bound;
 886 }
 887
 888
 889 static int CONV
 890 mpv_find_min( int *pnum )
 891 {
 892   int i, num;
 893   unsigned int a[ MPV_MAX_PV+1 ], u, utemp;
 894
 895   a[0] = 0;
 896   num  = 0;
 897   for ( i = 0; mpv_pv[i].length; i++ )
 898     {
 899       assert( i < mpv_num*2 );
 900       assert( i < root_nmove*2 );
 901       assert( mpv_pv[i].depth <= iteration_depth );
 902
 903       if ( mpv_pv[i].depth == iteration_depth )
 904         {
 905           u = mpv_pv[i].a[0];
 906           assert( -score_bound < (int)u-32768 );
 907           assert( (int)u-32768 < score_bound );
 908
 909           for ( num = 0; u <= a[num]; num++ );
 910           do {
 911             assert( num < mpv_num );
 912             assert( num < root_nmove );
 913             utemp  = a[num];
 914             a[num] = u;
 915             u      = utemp;
 916             num   += 1;
 917           } while ( u );
 918           a[num] = 0;
 919         }
 920     }
 921
 922   if ( pnum ) { *pnum = num; }
 923
 924   if ( num ) { return (int)a[num-1] - 32768; }
 925
 926   return 0;
 927 }
 928 #endif