7 static int find_root_move( unsigned int move );
8 static int save_result( tree_t * restrict ptree, int value, int beta,
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 );
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 );
23 # define NextRootMove(a,b) next_root_move(a,b)
24 static int next_root_move( tree_t * restrict ptree, int turn );
28 extern char xboard_mode;
32 searchr( tree_t * restrict ptree, int alpha, int beta, int turn, int depth )
34 uint64_t root_nodes_start;
35 int value, first_move_expanded, i;
36 int new_depth, extension, ply, state_node_new;
41 first_move_expanded = 1;
43 ptree->move_last[1] = ptree->move_last[0];
45 while( NextRootMove( ptree, turn ) )
47 root_nodes_start = ptree->node_searched;
48 MakeMove( turn, MOVE_CURR, 1 );
50 assert( ! InCheck( turn ) );
52 state_node_new = ( node_do_mate | node_do_null | node_do_futile
54 if ( InCheck(Flip(turn)) )
56 ptree->check_extension_done++;
57 ptree->nsuc_check[2] = (unsigned char)( ptree->nsuc_check[0] + 1U );
58 extension = EXT_CHECK - PLY_INC;
61 extension = - PLY_INC;
62 ptree->nsuc_check[2] = 0;
65 if ( first_move_expanded )
68 if ( root_mpv ) { bound = alpha; }
70 new_depth = depth + extension;
71 value = -search( ptree, -beta, -alpha, Flip(turn), new_depth, 2,
75 UnMakeMove( turn, MOVE_CURR, 1 );
81 UnMakeMove( turn, MOVE_CURR, 1 );
85 first_move_expanded = 0;
90 bound = mpv_set_bound( alpha );
91 if ( depth + extension >= PLY_INC || ptree->nsuc_check[2] )
93 new_depth = depth + extension;
95 value = -search( ptree, -bound-1, -bound, Flip(turn), new_depth,
97 if ( ! root_abort && bound < value )
99 new_depth = depth + extension;
100 value = -search( ptree, -beta, -bound, Flip(turn), new_depth,
105 UnMakeMove( turn, MOVE_CURR, 1 );
110 value = -search_quies( ptree, -beta, -bound, Flip(turn), 2, 1 );
115 new_depth = depth + extension;
117 value = -search( ptree, -alpha-1, -alpha, Flip(turn), new_depth, 2,
121 UnMakeMove( turn, MOVE_CURR, 1 );
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 );
130 new_depth = depth + extension;
132 value = -search( ptree, -beta, -alpha, Flip(turn), new_depth,
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];
148 dvalue = -(double)alpha;
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 )
160 OutCsaShogi( "info%+.2f %c%s %c%s [%c0!]\n",
161 dvalue / 100.0, ach_turn[Flip(turn)],
162 str_CSA_move(ponder_move),
166 OutCsaShogi( "info%+.2f %c%s [%c0!]\n",
167 dvalue / 100.0, ch, str, ch );
174 UnMakeMove( turn, MOVE_CURR, 1 );
176 i = find_root_move( MOVE_CURR );
177 root_move_list[i].nodes = ptree->node_searched - root_nodes_start;
180 if ( root_mpv && value < beta )
182 mpv_sub_result( MOVE_CURR );
183 if ( bound < value && mpv_add_result( ptree, value ) < 0 )
185 game_status |= flag_search_error;
193 if ( save_result( ptree, value, beta, turn ) < 0 )
195 game_status |= flag_search_error;
200 hash_store( ptree, 1, depth, turn, value_lower, value,
207 if ( root_abort ) { return 0; }
209 #if ! defined(MINIMUM)
210 if ( ! ( game_status & flag_learning ) )
213 hash_store( ptree, 1, depth, turn, value_exact, alpha,
214 ptree->pv[1].a[1], 0 );
223 out_xboard_move( int move, int tt )
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;
228 Out(" %c@%c%c", "PLNSGBR"[From2Drop(from)-1], 'a'+to%9, '9'-to/9);
230 Out(" %c%c%c%c%s", 'a'+from%9, '9'-from/9, 'a'+to%9, '9'-to/9,
231 inPromoZone ? I2IsPromote(move) ? "+" : "=" : "");
237 out_pv( tree_t * restrict ptree, int value, int turn, unsigned int time )
244 is_out = ( iteration_depth > 3 || abs(value) > score_max_eval ) ? 1 : 0;
247 if ( root_mpv ) { is_out = 0; }
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 )
257 OutCsaShogi( " %c%s", ach_turn[Flip(turn)],
258 str_CSA_move(ponder_move) );
261 if ( ptree->pv[0].length )
263 int i = find_root_move( ptree->pv[0].a[1] );
265 if(xboard_mode) Out("%2d %6d %6d %8d ", iteration_depth, value, time/10, 1); else
267 if ( root_move_list[i].status & flag_first )
269 Out( " %2d %6s %7.2f ", iteration_depth, str, dvalue );
271 else { Out( " %6s %7.2f ", str, dvalue ); }
275 for ( ply = 1; ply <= ptree->pv[0].length; ply++ )
278 if(xboard_mode && is_out) { // print PV move in WB format
279 out_xboard_move( ptree->pv[0].a[ply], tt );
284 if ( ply > 1 && ! ( (ply-1) % 4 ) )
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 );
293 MakeMove( tt, ptree->pv[0].a[ply], ply );
298 if ( ptree->pv[0].type == hash_hit )
302 for ( ; ply < PLY_MAX; ply++ )
304 ptree->amove_hash[ply] = 0;
305 value_type = hash_probe( ptree, ply, 0, tt, -score_bound,
307 if ( ! ( value_type == value_exact
308 && value == HASH_VALUE
309 && is_move_valid( ptree, ptree->amove_hash[ply], tt ) ) )
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; }
318 if(xboard_mode && is_out) { // print PV move in WB format
319 out_xboard_move( ptree->pv[0].a[ply], tt );
324 if ( ply > 1 && ! ( (ply-1) % 4 ) )
328 str = str_CSA_move_plus( ptree, ptree->pv[0].a[ply], ply,
330 OutCsaShogi( " %c%s", ach_turn[tt], str );
331 Out( "%2d:%c%-11s", ply, ach_turn[tt], str );
334 MakeMove( tt, ptree->pv[0].a[ply], ply );
337 UnMakeMove( tt, ptree->amove_hash[ply], ply );
340 ptree->pv[0].length++;
347 if ( is_out && ptree->pv[0].type != no_rep )
349 if ( (((ply-1) % 4) == 0) && (ply != 1) )
354 switch ( ptree->pv[0].type )
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;
366 if ( str != NULL ) { Out( " <%s>", str ); }
368 for ( ply--; ply >= 1; ply-- )
371 UnMakeMove( tt, ptree->pv[0].a[ply], ply );
383 save_result( tree_t * restrict ptree, int value, int beta, int turn )
385 root_move_t root_move_temp;
388 if ( get_elapsed( &time_last_result ) < 0 ) { return -1; }
390 i = find_root_move( ptree->current_move[1] );
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;
398 if ( beta <= value ) { pv_close( ptree, 2, pv_fail_high ); }
400 if ( ptree->pv[0].a[1] != ptree->pv[1].a[1] )
402 time_last_eff_search = time_last_search;
405 ptree->pv[0] = ptree->pv[1];
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 );
420 #if defined(NO_STDOUT) && defined(NO_LOGGING)
421 next_root_move( tree_t * restrict ptree )
423 next_root_move( tree_t * restrict ptree, int turn )
429 for ( i = 0; i < n; i++ )
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;
435 #if ! ( defined(NO_STDOUT) && defined(NO_LOGGING) )
439 if ( iteration_depth > 5 )
441 const char *str_move;
443 /* check: does this code have small impact on performance? */
444 str_move = str_CSA_move_plus( ptree, ptree->current_move[1], 1,
446 snprintf( str, 9, "%d/%d", i+1, root_nmove );
447 if ( root_move_list[i].status & flag_first )
449 Out( "(%2d) %7s* 1.%c%s \r",
450 iteration_depth, str, ach_turn[turn], str_move );
453 Out( " %7s* 1.%c%s \r",
454 str, ach_turn[turn], str_move );
467 find_root_move( unsigned int move )
472 for ( i = 0; i < n; i++ )
473 if ( root_move_list[i].move == move ) { break; }
481 mpv_out( tree_t * restrict ptree, int turn, unsigned int time, int newest )
483 int mpv_out, ipv, best;
485 best = (int)mpv_pv[0].a[0] - 32768;
486 mpv_out = ( iteration_depth > 3 || abs(best) > score_max_eval ) ? 1 : 0;
488 for ( ipv = 0; mpv_pv[ipv].length; ipv++ )
492 int tt, is_out, value, ply;
494 assert( ipv < mpv_num*2 );
496 value = (int)mpv_pv[ipv].a[0] - 32768;
497 if ( mpv_out && value > best - mpv_width && ipv < mpv_num )
505 dvalue = (double)( turn ? -value : value ) / 100.0;
506 if ( is_out && ! ipv ) { OutCsaShogi( "info" ); }
507 if ( is_out && ipv ) { OutCsaShogi( ":" ); }
509 OutCsaShogi( "%+.2f", dvalue );
510 if ( game_status & flag_pondering )
512 OutCsaShogi( " %c%s", ach_turn[Flip(turn)],
513 str_CSA_move(ponder_move) );
516 str = str_time_symple( time );
517 ply = mpv_pv[ipv].depth;
520 if(ipv != newest) continue; // skip all but the newest, to prevent duplicates
521 Out("%2d %6d %6d %8d ", ply, value, time/10, 1);
524 if ( ! ipv ) { Out( "o%2d %6s %7.2f ", ply, str, dvalue ); }
525 else { Out( " %2d %7.2f ", ply, dvalue ); }
528 for ( ply = 1; ply <= mpv_pv[ipv].length; ply++ )
531 if(xboard_mode && is_out) { // print PV move in WB format
532 out_xboard_move( mpv_pv[ipv].a[ply], tt );
537 if ( ply > 1 && ! ( (ply-1) % 4 ) )
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 );
546 assert( is_move_valid( ptree, mpv_pv[ipv].a[ply], tt ) );
547 MakeMove( tt, mpv_pv[ipv].a[ply], ply );
552 if ( mpv_pv[ipv].type == hash_hit )
556 for ( ; ply < PLY_MAX; ply++ )
558 ptree->amove_hash[ply] = 0;
559 value_type = hash_probe( ptree, ply, 0, tt, -score_bound,
561 if ( ! ( value_type == value_exact
562 && value == HASH_VALUE
563 && is_move_valid(ptree,ptree->amove_hash[ply],tt) ) )
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; }
573 if(xboard_mode && is_out) { // print PV move in WB format
574 out_xboard_move( mpv_pv[ipv].a[ply], tt );
579 if ( ply > 1 && ! ( (ply-1) % 4 ) )
583 str = str_CSA_move_plus( ptree, mpv_pv[ipv].a[ply], ply,
585 OutCsaShogi( " %c%s", ach_turn[tt], str );
586 Out( "%2d:%c%-11s", ply, ach_turn[tt], str );
589 MakeMove( tt, mpv_pv[ipv].a[ply], ply );
592 UnMakeMove( tt, ptree->amove_hash[ply], ply );
595 mpv_pv[ipv].length++;
602 if ( is_out && mpv_pv[ipv].type != no_rep )
604 if ( (((ply-1) % 4) == 0) && (ply != 1) )
609 switch ( mpv_pv[ipv].type )
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;
621 if ( str != NULL ) { Out( " <%s>", str ); }
623 for ( ply--; ply >= 1; ply-- )
626 UnMakeMove( tt, mpv_pv[ipv].a[ply], ply );
629 if ( is_out ) { Out( "\n" ); }
632 if ( mpv_out ) { OutCsaShogi( "\n" ); }
637 mpv_sub_result( unsigned int move )
641 for ( i = 0; mpv_pv[i].length; i++ )
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 );
649 if ( mpv_pv[i].a[1] == move ) { break; }
652 for ( ; mpv_pv[i].length; i++ )
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 );
660 mpv_pv[i] = mpv_pv[i+1];
666 mpv_add_result( tree_t * restrict ptree, int value )
670 int i, vmin, num, new_pv;
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 );
678 /* remove the weakest pv if all of slots are full */
679 if ( num == mpv_num )
681 for ( i = 0; mpv_pv[i].length; i++ )
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 );
689 if ( mpv_pv[i].depth == iteration_depth
690 && mpv_pv[i].a[0] == (unsigned int)(vmin+32768) ) { break; }
692 assert( i != mpv_num*2 );
693 assert( mpv_pv[i].length );
695 assert( i < mpv_num*2 );
696 assert( i < root_nmove*2 );
697 mpv_pv[i] = mpv_pv[i+1];
699 } while ( mpv_pv[i].length );
703 for ( i = 0; mpv_pv[i].length; i++ )
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 );
710 if ( mpv_pv[i].a[0] < (unsigned int)(value+32768) ) { break; }
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
717 assert( i < mpv_num*2 );
718 assert( i < root_nmove*2 );
723 } while ( pv.length );
725 if ( get_elapsed( &time ) < 0 ) { return -1; }
727 mpv_out( ptree, root_turn, time - time_start, new_pv );
734 mpv_set_bound( int alpha )
736 int bound, num, value;
738 bound = alpha - mpv_width;
739 if ( bound < -score_bound ) { bound = -score_bound; }
741 value = mpv_find_min( &num );
742 assert( num <= mpv_num );
743 assert( num < root_nmove );
745 assert( -score_bound < value );
746 assert( value < score_bound );
747 if ( num == mpv_num && bound < value ) { bound = value; }
754 mpv_find_min( int *pnum )
757 unsigned int a[ MPV_MAX_PV+1 ], u, utemp;
761 for ( i = 0; mpv_pv[i].length; i++ )
763 assert( i < mpv_num*2 );
764 assert( i < root_nmove*2 );
765 assert( mpv_pv[i].depth <= iteration_depth );
767 if ( mpv_pv[i].depth == iteration_depth )
770 assert( -score_bound < (int)u-32768 );
771 assert( (int)u-32768 < score_bound );
773 for ( num = 0; u <= a[num]; num++ );
775 assert( num < mpv_num );
776 assert( num < root_nmove );
786 if ( pnum ) { *pnum = num; }
788 if ( num ) { return (int)a[num-1] - 32768; }