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