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