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