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 );
  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 void
 222 out_pv( tree_t * restrict ptree, int value, int turn, unsigned int time )
 223 {
 224   const char *str;
 225   double dvalue;
 226   int ply, tt, is_out;
 227
 228   tt     = turn;
 229   is_out = ( iteration_depth > 3 || abs(value) > score_max_eval ) ? 1 : 0;
 230
 231 #if defined(MPV)
 232   if ( root_mpv ) { is_out = 0; }
 233 #endif
 234
 235   if ( is_out )
 236     {
 237       str    = str_time_symple( time );
 238       dvalue = (double)( turn ? -value : value ) / 100.0;
 239       OutCsaShogi( "info%+.2f", dvalue );
 240       if ( game_status & flag_pondering )
 241         {
 242           OutCsaShogi( " %c%s", ach_turn[Flip(turn)],
 243                        str_CSA_move(ponder_move) );
 244         }
 245
 246       if ( ptree->pv[0].length )
 247         {
 248           int i = find_root_move( ptree->pv[0].a[1] );
 249 #ifdef XBOARD
 250         if(xboard_mode) Out("%2d %6d %6d %8d ", iteration_depth, value, time/10, 1); else
 251 #endif
 252           if ( root_move_list[i].status & flag_first )
 253             {
 254               Out( " %2d %6s %7.2f ", iteration_depth, str, dvalue );
 255             }
 256           else { Out( "    %6s %7.2f ", str, dvalue ); }
 257         }
 258     }
 259
 260   for ( ply = 1; ply <= ptree->pv[0].length; ply++ )
 261     {
 262 #ifdef XBOARD
 263       if(xboard_mode && is_out) { // print PV move in WB format
 264         int move = ptree->pv[0].a[ply], from = I2From(move), to = I2To(move);
 265         char inPromoZone = tt > 0 ? from >= 6*9 || to >= 6*9 : to < 3*9|| from < 3*9;
 266         if(from >= nsquare)
 267           Out(" %c@%c%c", "PLNSGBR"[From2Drop(from)-1], 'a'+to%9, '9'-to/9);
 268         else
 269           Out(" %c%c%c%c%s", 'a'+from%9, '9'-from/9, 'a'+to%9, '9'-to/9,
 270               inPromoZone ? I2IsPromote(move) ? "+" : "=" : "");
 271       } else
 272 #endif
 273       if ( is_out )
 274         {
 275           if ( ply > 1 && ! ( (ply-1) % 4 ) )
 276             {
 277               Out( "\n                   " );
 278             }
 279           str = str_CSA_move_plus( ptree, ptree->pv[0].a[ply], ply, tt );
 280           OutCsaShogi( " %c%s", ach_turn[tt], str );
 281           Out( "%2d.%c%-11s", ply, ach_turn[tt], str );
 282         }
 283
 284       MakeMove( tt, ptree->pv[0].a[ply], ply );
 285       tt    = Flip(tt);
 286       value = -value;
 287     }
 288
 289   if ( ptree->pv[0].type == hash_hit )
 290     {
 291       int i, value_type;
 292
 293       for ( ; ply < PLY_MAX; ply++ )
 294         {
 295           ptree->amove_hash[ply] = 0;
 296           value_type = hash_probe( ptree, ply, 0, tt, -score_bound,
 297                                    score_bound, 0 );
 298           if ( ! ( value_type == value_exact
 299                    && value   == HASH_VALUE
 300                    && is_move_valid( ptree, ptree->amove_hash[ply], tt ) ) )
 301             {
 302               break;
 303             }
 304           ptree->pv[0].a[ply] = ptree->amove_hash[ply];
 305           for ( i = 1; i < ply; i++ )
 306             if ( ptree->pv[0].a[i] == ptree->pv[0].a[ply] ) { goto rep_esc; }
 307
 308 #ifdef XBOARD
 309       if(xboard_mode && is_out) { // print PV move in WB format
 310         int move = ptree->pv[0].a[ply], from = I2From(move), to = I2To(move);
 311         char inPromoZone = tt > 0 ? from >= 6*9 || to >= 6*9 : to < 3*9|| from < 3*9;
 312         if(from >= nsquare)
 313           Out(" %c@%c%c", "PLNSGBR"[From2Drop(from)-1], 'a'+to%9, '9'-to/9);
 314         else
 315           Out(" %c%c%c%c%s", 'a'+from%9, '9'-from/9, 'a'+to%9, '9'-to/9,
 316               inPromoZone ? I2IsPromote(move) ? "+" : "=" : "");
 317       } else
 318 #endif
 319           if ( is_out )
 320             {
 321               if ( ply > 1 && ! ( (ply-1) % 4 ) )
 322                 {
 323                   Out( "\n                   " );
 324                 }
 325               str = str_CSA_move_plus( ptree, ptree->pv[0].a[ply], ply,
 326                                        tt );
 327               OutCsaShogi( " %c%s", ach_turn[tt], str );
 328               Out( "%2d:%c%-11s", ply, ach_turn[tt], str );
 329             }
 330
 331           MakeMove( tt, ptree->pv[0].a[ply], ply );
 332           if ( InCheck(tt) )
 333             {
 334               UnMakeMove( tt, ptree->amove_hash[ply], ply );
 335               break;
 336             }
 337           ptree->pv[0].length++;
 338           tt    = Flip(tt);
 339           value = -value;
 340         }
 341     }
 342  rep_esc:
 343
 344   if ( is_out && ptree->pv[0].type != no_rep )
 345     {
 346       if ( (((ply-1) % 4) == 0) && (ply != 1) )
 347         {
 348           Out( "\n                   " );
 349         }
 350       str = NULL;
 351       switch ( ptree->pv[0].type )
 352         {
 353         case perpetual_check:  str = "PER. CHECK";     break;
 354         case four_fold_rep:    str = "REPETITION";     break;
 355         case black_superi_rep:
 356         case white_superi_rep: str = "SUPERI. POSI.";  break;
 357         case prev_solution:    str = "PREV. SEARCH";   break;
 358         case hash_hit:         str = "HASH HIT";       break;
 359         case book_hit:         str = "BOOK HIT";       break;
 360         case pv_fail_high:     str = "FAIL HIGH";      break;
 361         case mate_search:      str = "MATE SEARCH";    break;
 362         }
 363       if ( str != NULL ) { Out( " <%s>", str ); }
 364     }
 365   for ( ply--; ply >= 1; ply-- )
 366     {
 367       tt = Flip(tt);
 368       UnMakeMove( tt, ptree->pv[0].a[ply], ply );
 369     }
 370
 371   if ( is_out )
 372     {
 373       OutCsaShogi( "\n" );
 374       Out( "\n" );
 375     }
 376 }
 377
 378
 379 static int
 380 save_result( tree_t * restrict ptree, int value, int beta, int turn )
 381 {
 382   root_move_t root_move_temp;
 383   int i;
 384
 385   if ( get_elapsed( &time_last_result ) < 0 ) { return -1; }
 386
 387   i = find_root_move( ptree->current_move[1] );
 388   if ( i )
 389     {
 390       root_move_temp = root_move_list[i];
 391       for ( ; i > 0; i-- ) { root_move_list[i] = root_move_list[i-1]; }
 392       root_move_list[0] = root_move_temp;
 393     }
 394
 395   if ( beta <= value ) { pv_close( ptree, 2, pv_fail_high ); }
 396
 397   if ( ptree->pv[0].a[1] != ptree->pv[1].a[1] )
 398     {
 399       time_last_eff_search = time_last_search;
 400     }
 401
 402   ptree->pv[0] = ptree->pv[1];
 403   root_value   = value;
 404
 405   if ( value < beta )
 406     {
 407       MnjOut( "pid=%d move=%s v=%de n=%" PRIu64 "\n", mnj_posi_id,
 408               str_CSA_move(ptree->pv[1].a[1]), value, ptree->node_searched );
 409       out_pv( ptree, value, turn, time_last_result - time_start );
 410     }
 411
 412   return 1;
 413 }
 414
 415
 416 static int
 417 #if defined(NO_STDOUT) && defined(NO_LOGGING)
 418 next_root_move( tree_t * restrict ptree )
 419 #else
 420 next_root_move( tree_t * restrict ptree, int turn )
 421 #endif
 422 {
 423   int i, n;
 424
 425   n = root_nmove;
 426   for ( i = 0; i < n; i++ )
 427     {
 428       if ( root_move_list[i].status & flag_searched ) { continue; }
 429       root_move_list[i].status |= flag_searched;
 430       ptree->current_move[1]    = root_move_list[i].move;
 431
 432 #if ! ( defined(NO_STDOUT) && defined(NO_LOGGING) )
 433 #ifdef XBOARD
 434       if(!xboard_mode)
 435 #endif
 436       if ( iteration_depth > 5 )
 437         {
 438           const char *str_move;
 439           char str[9];
 440           /* check: does this code have small impact on performance? */
 441           str_move = str_CSA_move_plus( ptree, ptree->current_move[1], 1,
 442                                         turn);
 443           snprintf( str, 9, "%d/%d", i+1, root_nmove );
 444           if ( root_move_list[i].status & flag_first )
 445             {
 446               Out( "(%2d)       %7s* 1.%c%s     \r",
 447                    iteration_depth, str, ach_turn[turn], str_move );
 448             }
 449           else {
 450             Out( "           %7s* 1.%c%s     \r",
 451                  str, ach_turn[turn], str_move );
 452           }
 453         }
 454 #endif
 455
 456       return 1;
 457     }
 458
 459   return 0;
 460 }
 461
 462
 463 static int
 464 find_root_move( unsigned int move )
 465 {
 466   int i, n;
 467
 468   n = root_nmove;
 469   for ( i = 0; i < n; i++ )
 470     if ( root_move_list[i].move == move ) { break; }
 471
 472   return i;
 473 }
 474
 475
 476 #if defined(MPV)
 477 static void
 478 mpv_out( tree_t * restrict ptree, int turn, unsigned int time )
 479 {
 480   int mpv_out, ipv, best;
 481
 482   best    = (int)mpv_pv[0].a[0] - 32768;
 483   mpv_out = ( iteration_depth > 3 || abs(best) > score_max_eval ) ? 1 : 0;
 484
 485   for ( ipv = 0; mpv_pv[ipv].length; ipv++ )
 486     {
 487       const char *str;
 488       double dvalue;
 489       int tt, is_out, value, ply;
 490
 491       assert( ipv < mpv_num*2 );
 492       tt     = turn;
 493       value  = (int)mpv_pv[ipv].a[0] - 32768;
 494       if ( mpv_out && value > best - mpv_width && ipv < mpv_num )
 495         {
 496           is_out = 1;
 497         }
 498       else { is_out = 0; }
 499
 500       if ( is_out )
 501         {
 502           dvalue = (double)( turn ? -value : value ) / 100.0;
 503           if ( is_out && ! ipv ) { OutCsaShogi( "info" ); }
 504           if ( is_out && ipv )   { OutCsaShogi( ":" ); }
 505
 506           OutCsaShogi( "%+.2f", dvalue );
 507           if ( game_status & flag_pondering )
 508             {
 509               OutCsaShogi( " %c%s", ach_turn[Flip(turn)],
 510                            str_CSA_move(ponder_move) );
 511             }
 512
 513           str = str_time_symple( time );
 514           ply = mpv_pv[ipv].depth;
 515           if ( ! ipv ) { Out( "o%2d %6s %7.2f ", ply, str, dvalue ); }
 516           else         { Out( " %2d        %7.2f ", ply, dvalue ); }
 517         }
 518
 519       for ( ply = 1; ply <= mpv_pv[ipv].length; ply++ )
 520         {
 521           if ( is_out )
 522             {
 523               if ( ply > 1 && ! ( (ply-1) % 4 ) )
 524                 {
 525                   Out( "\n                   " );
 526                 }
 527               str = str_CSA_move_plus( ptree, mpv_pv[ipv].a[ply], ply, tt );
 528               OutCsaShogi( " %c%s", ach_turn[tt], str );
 529               Out( "%2d.%c%-11s", ply, ach_turn[tt], str );
 530             }
 531
 532           assert( is_move_valid( ptree, mpv_pv[ipv].a[ply], tt ) );
 533           MakeMove( tt, mpv_pv[ipv].a[ply], ply );
 534           tt    = Flip(tt);
 535           value = -value;
 536         }
 537
 538       if ( mpv_pv[ipv].type == hash_hit )
 539         {
 540           int i, value_type;
 541
 542           for ( ; ply < PLY_MAX; ply++ )
 543             {
 544               ptree->amove_hash[ply] = 0;
 545               value_type = hash_probe( ptree, ply, 0, tt, -score_bound,
 546                                        score_bound, 0 );
 547               if ( ! ( value_type == value_exact
 548                        && value   == HASH_VALUE
 549                        && is_move_valid(ptree,ptree->amove_hash[ply],tt) ) )
 550                 {
 551                   break;
 552                 }
 553               mpv_pv[ipv].a[ply] = ptree->amove_hash[ply];
 554               for ( i = 1; i < ply; i++ )
 555                 if ( mpv_pv[ipv].a[i]
 556                      == mpv_pv[ipv].a[ply] ) { goto rep_esc; }
 557
 558               if ( is_out )
 559                 {
 560                   if ( ply > 1 && ! ( (ply-1) % 4 ) )
 561                     {
 562                       Out( "\n                   " );
 563                     }
 564                   str = str_CSA_move_plus( ptree, mpv_pv[ipv].a[ply], ply,
 565                                            tt );
 566                   OutCsaShogi( " %c%s", ach_turn[tt], str );
 567                   Out( "%2d:%c%-11s", ply, ach_turn[tt], str );
 568                 }
 569
 570               MakeMove( tt, mpv_pv[ipv].a[ply], ply );
 571               if ( InCheck(tt) )
 572                 {
 573                   UnMakeMove( tt, ptree->amove_hash[ply], ply );
 574                   break;
 575                 }
 576               mpv_pv[ipv].length++;
 577               tt    = Flip(tt);
 578               value = -value;
 579             }
 580         }
 581     rep_esc:
 582
 583       if ( is_out && mpv_pv[ipv].type != no_rep )
 584         {
 585           if ( (((ply-1) % 4) == 0) && (ply != 1) )
 586             {
 587               Out( "\n                   " );
 588             }
 589           str = NULL;
 590           switch ( mpv_pv[ipv].type )
 591             {
 592             case perpetual_check:  str = "PER. CHECK";     break;
 593             case four_fold_rep:    str = "REPETITION";     break;
 594             case black_superi_rep:
 595             case white_superi_rep: str = "SUPERI. POSI.";  break;
 596             case prev_solution:    str = "PREV. SEARCH";   break;
 597             case hash_hit:         str = "HASH HIT";       break;
 598             case book_hit:         str = "BOOK HIT";       break;
 599             case pv_fail_high:     str = "FAIL HIGH";      break;
 600             case mate_search:      str = "MATE SEARCH";    break;
 601             }
 602           if ( str != NULL ) { Out( " <%s>", str ); }
 603         }
 604       for ( ply--; ply >= 1; ply-- )
 605         {
 606           tt = Flip(tt);
 607           UnMakeMove( tt, mpv_pv[ipv].a[ply], ply );
 608         }
 609
 610       if ( is_out ) { Out( "\n" ); }
 611     }
 612
 613   if ( mpv_out ) { OutCsaShogi( "\n" ); }
 614 }
 615
 616
 617 static void
 618 mpv_sub_result( unsigned int move )
 619 {
 620   int i;
 621
 622   for ( i = 0; mpv_pv[i].length; i++ )
 623     {
 624       assert( i < mpv_num*2 );
 625       assert( i < root_nmove*2 );
 626       assert( mpv_pv[i].depth <= iteration_depth );
 627       assert( -score_bound < (int)mpv_pv[i].a[0]-32768 );
 628       assert( (int)mpv_pv[i].a[0]-32768 < score_bound );
 629
 630       if ( mpv_pv[i].a[1] == move ) { break; }
 631     }
 632
 633   for ( ; mpv_pv[i].length; i++ )
 634     {
 635       assert( i < mpv_num*2 );
 636       assert( i < root_nmove*2 );
 637       assert( mpv_pv[i].depth <= iteration_depth );
 638       assert( -score_bound < (int)mpv_pv[i].a[0]-32768 );
 639       assert( (int)mpv_pv[i].a[0]-32768 < score_bound );
 640
 641       mpv_pv[i] = mpv_pv[i+1];
 642     }
 643 }
 644
 645
 646 static int
 647 mpv_add_result( tree_t * restrict ptree, int value )
 648 {
 649   pv_t pv_tmp, pv;
 650   unsigned int time;
 651   int i, vmin, num;
 652
 653   vmin = mpv_find_min( &num );
 654   assert( num <= mpv_num );
 655   assert( num < root_nmove );
 656   assert( -score_bound < value );
 657   assert( value < score_bound  );
 658
 659   /* remove the weakest pv if all of slots are full */
 660   if ( num == mpv_num )
 661     {
 662       for ( i = 0; mpv_pv[i].length; i++ )
 663         {
 664           assert( i < mpv_num*2 );
 665           assert( i < root_nmove*2 );
 666           assert( mpv_pv[i].depth <= iteration_depth );
 667           assert( -score_bound < (int)mpv_pv[i].a[0]-32768 );
 668           assert( (int)mpv_pv[i].a[0]-32768 < score_bound );
 669
 670           if ( mpv_pv[i].depth == iteration_depth
 671                && mpv_pv[i].a[0] == (unsigned int)(vmin+32768) ) { break; }
 672         }
 673       assert( i != mpv_num*2 );
 674       assert( mpv_pv[i].length );
 675       do {
 676         assert( i < mpv_num*2 );
 677         assert( i < root_nmove*2 );
 678         mpv_pv[i] = mpv_pv[i+1];
 679         i++;
 680       } while ( mpv_pv[i].length );
 681     }
 682
 683   /* add a pv */
 684   for ( i = 0; mpv_pv[i].length; i++ )
 685     {
 686       assert( i < mpv_num*2 );
 687       assert( i < root_nmove*2 );
 688       assert( -score_bound < (int)mpv_pv[i].a[0]-32768 );
 689       assert( (int)mpv_pv[i].a[0]-32768 < score_bound );
 690
 691       if ( mpv_pv[i].a[0] < (unsigned int)(value+32768) ) { break; }
 692     }
 693
 694   pv      = ptree->pv[1];
 695   pv.a[0] = (unsigned int)(value+32768);
 696   do {
 697     assert( i < mpv_num*2 );
 698     assert( i < root_nmove*2 );
 699     pv_tmp      = mpv_pv[i];
 700     mpv_pv[i] = pv;
 701     pv          = pv_tmp;
 702     i          += 1;
 703   } while ( pv.length );
 704
 705   if ( get_elapsed( &time ) < 0 ) { return -1; }
 706
 707   mpv_out( ptree, root_turn, time - time_start );
 708
 709   return 1;
 710 }
 711
 712
 713 static int
 714 mpv_set_bound( int alpha )
 715 {
 716   int bound, num, value;
 717
 718   bound = alpha - mpv_width;
 719   if ( bound < -score_bound ) { bound = -score_bound; }
 720
 721   value = mpv_find_min( &num );
 722   assert( num <= mpv_num );
 723   assert( num < root_nmove );
 724   assert( num );
 725   assert( -score_bound < value );
 726   assert( value < score_bound  );
 727   if ( num == mpv_num && bound < value ) { bound = value; }
 728
 729   return bound;
 730 }
 731
 732
 733 static int
 734 mpv_find_min( int *pnum )
 735 {
 736   int i, num;
 737   unsigned int a[ MPV_MAX_PV+1 ], u, utemp;
 738
 739   a[0] = 0;
 740   num  = 0;
 741   for ( i = 0; mpv_pv[i].length; i++ )
 742     {
 743       assert( i < mpv_num*2 );
 744       assert( i < root_nmove*2 );
 745       assert( mpv_pv[i].depth <= iteration_depth );
 746
 747       if ( mpv_pv[i].depth == iteration_depth )
 748         {
 749           u = mpv_pv[i].a[0];
 750           assert( -score_bound < (int)u-32768 );
 751           assert( (int)u-32768 < score_bound );
 752
 753           for ( num = 0; u <= a[num]; num++ );
 754           do {
 755             assert( num < mpv_num );
 756             assert( num < root_nmove );
 757             utemp  = a[num];
 758             a[num] = u;
 759             u      = utemp;
 760             num   += 1;
 761           } while ( u );
 762           a[num] = 0;
 763         }
 764     }
 765
 766   if ( pnum ) { *pnum = num; }
 767
 768   if ( num ) { return (int)a[num-1] - 32768; }
 769
 770   return 0;
 771 }
 772 #endif