7 static int CONV save_result( tree_t * restrict ptree, int value, int beta,
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, unsigned int time, int newest );
18 #if defined(NO_STDOUT) && defined(NO_LOGGING)
19 # define NextRootMove(a,b) next_root_move(a)
20 static int CONV next_root_move( tree_t * restrict ptree );
22 # define NextRootMove(a,b) next_root_move(a,b)
23 static int CONV next_root_move( tree_t * restrict ptree, int turn );
27 extern char xboard_mode;
31 search_wrapper( tree_t * restrict ptree, int alpha, int beta, int turn,
32 int depth, int ply, unsigned int state_node )
36 #if defined(DFPN_CLIENT)
37 /* try beta cut using results from DFPN server */
38 if ( root_move_list[root_index].dfpn_cresult == dfpn_client_win )
40 if ( ! root_index ) { Out( "- best move is proofed, skip.\n" ); }
41 ptree->pv[1].a[1] = MOVE_LAST;
42 ptree->pv[1].length = 1;
43 ptree->pv[1].depth = 0;
44 ptree->pv[1].type = no_rep;
46 return score_matelong;
50 value = search( ptree, alpha, beta, turn, depth, ply, state_node );
52 #if defined(DFPN_CLIENT)
53 /* catch a signal, i.e., the first move has to be ignored */
54 if ( game_status & flag_skip_root_move )
58 Out( "- %s is proofed while searching.\n", str_CSA_move(MOVE_LAST) );
61 Out( "- %s (best move) is proofed while searching.\n",
62 str_CSA_move(MOVE_LAST) );
65 game_status &= ~flag_skip_root_move;
68 ptree->pv[1].a[1] = MOVE_LAST;
69 ptree->pv[1].length = 1;
70 ptree->pv[1].depth = 0;
71 ptree->pv[1].type = no_rep;
73 return score_matelong;
82 searchr( tree_t * restrict ptree, int alpha, int beta, int turn, int depth )
84 uint64_t root_nodes_start;
85 int value, first_move;
86 int new_depth, extension, ply, state_node_new;
96 ptree->move_last[1] = ptree->move_last[0];
98 while( NextRootMove( ptree, turn ) )
100 root_nodes_start = ptree->node_searched;
102 if ( usi_mode != usi_off )
104 csa2usi( ptree, str_CSA_move(MOVE_CURR), str_usi );
108 MakeMove( turn, MOVE_CURR, 1 );
110 assert( ! InCheck( turn ) );
112 state_node_new = ( node_do_mate | node_do_null | node_do_futile
113 | node_do_recap | node_do_recursion
115 if ( InCheck(Flip(turn)) )
117 ptree->check_extension_done++;
118 ptree->nsuc_check[2] = (unsigned char)( ptree->nsuc_check[0] + 1U );
119 extension = EXT_CHECK - PLY_INC;
122 extension = - PLY_INC;
123 ptree->nsuc_check[2] = 0;
129 if ( root_mpv ) { bound = alpha; }
131 new_depth = depth + extension;
132 value = -search_wrapper( ptree, -beta, -alpha, Flip(turn),
133 new_depth, 2, state_node_new );
136 UnMakeMove( turn, MOVE_CURR, 1 );
140 if ( value <= alpha )
142 UnMakeMove( turn, MOVE_CURR, 1 );
151 bound = mpv_set_bound( alpha );
152 if ( depth + extension >= PLY_INC || ptree->nsuc_check[2] )
154 new_depth = depth + extension;
156 value = -search_wrapper( ptree, -bound-1, -bound, Flip(turn),
157 new_depth, 2, state_node_new );
158 if ( ! root_abort && bound < value )
160 new_depth = depth + extension;
161 value = -search_wrapper( ptree, -beta, -bound, Flip(turn),
162 new_depth, 2, state_node_new );
166 UnMakeMove( turn, MOVE_CURR, 1 );
171 value = -search_quies( ptree, -beta, -bound, Flip(turn), 2, 1 );
176 int depth_reduced = 0;
177 new_depth = depth + extension;
180 if ( 2*PLY_INC <= new_depth
181 && ! ptree->nsuc_check[ply]
182 && ! UToCap(MOVE_CURR)
183 && ! ( I2IsPromote(MOVE_CURR)
184 && I2PieceMove(MOVE_CURR) != silver ) )
186 unsigned int key = phash( MOVE_CURR, turn );
187 unsigned int good = ptree->hist_good[key] + 1;
188 unsigned int triedx8 = ( ptree->hist_tried[key] + 2 ) * 8U;
190 if ( good *160U < triedx8 ) { depth_reduced = PLY_INC * 3/2; }
191 else if ( good * 50U < triedx8 ) { depth_reduced = PLY_INC * 2/2; }
192 else if ( good * 19U < triedx8 ) { depth_reduced = PLY_INC * 1/2; }
194 depth_reduced = PLY_INC;
195 new_depth -= depth_reduced;
198 value = -search_wrapper( ptree, -alpha-1, -alpha, Flip(turn),
199 new_depth, 2, state_node_new );
200 if ( ! root_abort && alpha < value && depth_reduced )
202 new_depth += depth_reduced;
203 value = -search_wrapper( ptree, -alpha-1, -alpha, Flip(turn),
204 new_depth, 2, state_node_new );
208 UnMakeMove( turn, MOVE_CURR, 1 );
214 #if defined(DFPN_CLIENT)
215 if ( dfpn_client_sckt != SCKT_NULL
216 && 4 < iteration_depth
217 && dfpn_client_best_move != MOVE_CURR )
219 dfpn_client_best_move = MOVE_CURR;
220 lock( &dfpn_client_lock );
221 dfpn_client_out( "BEST MOVE %s\n",
222 str_CSA_move(dfpn_client_best_move) );
223 unlock( &dfpn_client_lock );
226 MnjOut( "pid=%d move=%s v=%dl n=% " PRIu64 "%s\n",
227 mnj_posi_id, str_CSA_move(MOVE_CURR), alpha+1,
228 ptree->node_searched,
229 ( mnj_depth_stable <= iteration_depth ) ? " stable" : "" );
232 if ( usi_mode != usi_off )
234 USIOut( "info depth %d score cp %d nodes %" PRIu64 " pv %s\n",
235 iteration_depth, alpha+1, ptree->node_searched,
240 new_depth = depth + extension;
242 value = -search_wrapper( ptree, -beta, -alpha, Flip(turn),
243 new_depth, 2, state_node_new );
250 UnMakeMove( turn, MOVE_CURR, 1 );
251 pv_close( ptree, 2, pv_fail_high );
252 time_last_result = time_last_check;
253 root_value = alpha+1;
254 ptree->pv[0] = ptree->pv[1];
257 dvalue = -(double)alpha;
264 str = str_CSA_move(MOVE_CURR);
265 Out( " %7.2f 1.%c%s [%c0!]\n",
266 dvalue / 100.0, ch, str, ch );
267 if ( game_status & flag_pondering )
269 OutCsaShogi( "info%+.2f %c%s %c%s [%c0!]\n",
270 dvalue / 100.0, ach_turn[Flip(turn)],
271 str_CSA_move(ponder_move),
275 OutCsaShogi( "info%+.2f %c%s [%c0!]\n",
276 dvalue / 100.0, ch, str, ch );
283 UnMakeMove( turn, MOVE_CURR, 1 );
285 root_move_list[root_index].nodes
286 = ptree->node_searched - root_nodes_start;
289 if ( root_mpv && value < beta )
291 mpv_sub_result( MOVE_CURR );
292 if ( bound < value && mpv_add_result( ptree, value ) < 0 )
294 game_status |= flag_search_error;
302 if ( save_result( ptree, value, beta, turn ) < 0 )
304 game_status |= flag_search_error;
307 if ( beta <= value ) { return value; }
311 if ( root_abort ) { return 0; }
319 out_xboard_move( int move, int tt )
321 int from = I2From(move), to = I2To(move);
322 char inPromoZone = tt > 0 ? from >= 6*9 || to >= 6*9 : to < 3*9|| from < 3*9;
324 Out(" %c@%c%c", "PLNSGBR"[From2Drop(from)-1], 'a'+to%9, '9'-to/9);
326 Out(" %c%c%c%c%s", 'a'+from%9, '9'-from/9, 'a'+to%9, '9'-to/9,
327 inPromoZone ? I2IsPromote(move) ? "+" : "=" : "");
333 out_pv( tree_t * restrict ptree, int value, int turn, unsigned int time )
344 is_out = ( 4 < iteration_depth || abs(value) > score_max_eval ) ? 1 : 0;
347 if ( root_mpv ) { is_out = 0; }
351 if ( usi_mode != usi_off )
361 str = str_time_symple( time );
362 dvalue = (double)( turn ? -value : value ) / 100.0;
363 OutCsaShogi( "info%+.2f", dvalue );
364 if ( game_status & flag_pondering )
366 OutCsaShogi( " %c%s", ach_turn[Flip(turn)],
367 str_CSA_move(ponder_move) );
370 if ( ptree->pv[0].length )
373 if(xboard_mode) Out("%2d %6d %6d %8d ", iteration_depth, value, time/10, 1); else
375 if ( root_move_list[root_index].status & flag_first )
377 Out( " %2d %6s %7.2f ", iteration_depth, str, dvalue );
379 else { Out( " %6s %7.2f ", str, dvalue ); }
383 for ( ply = 1; ply <= ptree->pv[0].length; ply++ )
386 if(xboard_mode && is_out) { // print PV move in WB format
387 out_xboard_move( ptree->pv[0].a[ply], tt );
392 if ( ply > 1 && ! ( (ply-1) % 5 ) )
396 str = str_CSA_move( ptree->pv[0].a[ply] );
397 OutCsaShogi( " %c%s", ach_turn[tt], str );
398 Out( "%2d.%c%-7s", ply, ach_turn[tt], str );
401 if ( usi_mode != usi_off && ply <= 4 )
404 csa2usi( ptree, str_CSA_move(ptree->pv[0].a[ply]), str_usi );
405 ipv += snprintf( str_pv + ipv, 256 - ipv, " %s", str_usi );
410 MakeMove( tt, ptree->pv[0].a[ply], ply );
415 if ( ptree->pv[0].type == hash_hit )
420 for ( ; ply < PLY_MAX; ply++ )
423 ptree->amove_hash[ply] = 0;
424 value_type = hash_probe( ptree, ply, 0, tt, -score_bound,
425 score_bound, &dummy );
426 if ( ! ( value_type == value_exact
427 && value == HASH_VALUE
428 && is_move_valid( ptree, ptree->amove_hash[ply], tt ) ) )
432 ptree->pv[0].a[ply] = ptree->amove_hash[ply];
433 for ( i = 1; i < ply; i++ )
434 if ( ptree->pv[0].a[i] == ptree->pv[0].a[ply] ) { goto rep_esc; }
437 if(xboard_mode && is_out) { // print PV move in WB format
438 out_xboard_move( ptree->pv[0].a[ply], tt );
443 if ( ply > 1 && ! ( (ply-1) % 5 ) )
447 str = str_CSA_move(ptree->pv[0].a[ply]);
448 OutCsaShogi( " %c%s", ach_turn[tt], str );
449 Out( "%2d:%c%-7s", ply, ach_turn[tt], str );
452 if ( usi_mode != usi_off && ply <= 4 )
455 csa2usi( ptree, str_CSA_move(ptree->pv[0].a[ply]), str_usi );
456 ipv += snprintf( str_pv + ipv, 256 - ipv, " %s", str_usi );
461 MakeMove( tt, ptree->pv[0].a[ply], ply );
464 UnMakeMove( tt, ptree->amove_hash[ply], ply );
467 ptree->pv[0].length++;
474 if ( is_out && ptree->pv[0].type != no_rep )
476 if ( (((ply-1) % 5) == 0) && (ply != 1) )
481 switch ( ptree->pv[0].type )
483 case perpetual_check: str = "PER. CHECK"; break;
484 case four_fold_rep: str = "REPETITION"; break;
485 case black_superi_rep:
486 case white_superi_rep: str = "SUPERI. POSI."; break;
487 case prev_solution: str = "PREV. SEARCH"; break;
488 case hash_hit: str = "HASH HIT"; break;
489 case book_hit: str = "BOOK HIT"; break;
490 case pv_fail_high: str = "FAIL HIGH"; break;
491 case mate_search: str = "MATE SEARCH"; break;
493 if ( str != NULL ) { Out( " <%s>", str ); }
495 for ( ply--; ply >= 1; ply-- )
499 UnMakeMove( tt, ptree->pv[0].a[ply], ply );
506 USIOut( "info depth %d score cp %d nodes %" PRIu64 " pv%s\n",
507 iteration_depth, value, ptree->node_searched, str_pv );
513 save_result( tree_t * restrict ptree, int value, int beta, int turn )
515 root_move_t root_move_temp;
518 if ( get_elapsed( &time_last_result ) < 0 ) { return -1; }
523 root_move_temp = root_move_list[index];
524 for ( ; index > 0; index-- )
526 root_move_list[index] = root_move_list[index-1];
528 root_move_list[0] = root_move_temp;
531 if ( beta <= value ) { pv_close( ptree, 2, pv_fail_high ); }
533 ptree->pv[0] = ptree->pv[1];
538 #if defined(DFPN_CLIENT)
539 if ( dfpn_client_sckt != SCKT_NULL
540 && 4 < iteration_depth
541 && dfpn_client_best_move != ptree->pv[1].a[1] )
543 dfpn_client_best_move = ptree->pv[1].a[1];
544 lock( &dfpn_client_lock );
545 dfpn_client_out( "BEST MOVE %s\n",
546 str_CSA_move(dfpn_client_best_move) );
547 unlock( &dfpn_client_lock );
550 MnjOut( "pid=%d move=%s v=%de n=%" PRIu64 "%s\n",
551 mnj_posi_id, str_CSA_move(ptree->pv[1].a[1]), value,
552 ptree->node_searched,
553 ( mnj_depth_stable <= iteration_depth ) ? " stable" : "" );
555 out_pv( ptree, value, turn, time_last_result - time_start );
563 #if defined(NO_STDOUT) && defined(NO_LOGGING)
564 next_root_move( tree_t * restrict ptree )
566 next_root_move( tree_t * restrict ptree, int turn )
572 for ( i = 0; i < n; i++ )
574 if ( root_move_list[i].status & flag_searched ) { continue; }
575 root_move_list[i].status |= flag_searched;
576 ptree->current_move[1] = root_move_list[i].move;
579 #if ! ( defined(NO_STDOUT) && defined(NO_LOGGING) )
583 if ( iteration_depth > 5 )
585 const char *str_move;
588 str_move = str_CSA_move(ptree->current_move[1]);
589 snprintf( str, 9, "%d/%d", i+1, root_nmove );
590 if ( root_move_list[i].status & flag_first )
592 Out( "(%2d) %7s* 1.%c%s \r",
593 iteration_depth, str, ach_turn[turn], str_move );
596 Out( " %7s* 1.%c%s \r",
597 str, ach_turn[turn], str_move );
611 mpv_out( tree_t * restrict ptree, int turn, unsigned int time, int newest )
613 int mpv_out, ipv, best;
615 best = (int)mpv_pv[0].a[0] - 32768;
616 mpv_out = ( iteration_depth > 3 || abs(best) > score_max_eval ) ? 1 : 0;
618 for ( ipv = 0; mpv_pv[ipv].length; ipv++ )
622 int tt, is_out, value, ply;
624 assert( ipv < mpv_num*2 );
626 value = (int)mpv_pv[ipv].a[0] - 32768;
627 if ( mpv_out && value > best - mpv_width && ipv < mpv_num )
635 dvalue = (double)( turn ? -value : value ) / 100.0;
636 if ( is_out && ! ipv ) { OutCsaShogi( "info" ); }
637 if ( is_out && ipv ) { OutCsaShogi( ":" ); }
639 OutCsaShogi( "%+.2f", dvalue );
640 if ( game_status & flag_pondering )
642 OutCsaShogi( " %c%s", ach_turn[Flip(turn)],
643 str_CSA_move(ponder_move) );
646 str = str_time_symple( time );
647 ply = mpv_pv[ipv].depth;
650 if(ipv != newest) continue; // skip all but the newest, to prevent duplicates
651 Out("%2d %6d %6d %8d ", ply, value, time/10, 1);
654 if ( ! ipv ) { Out( "o%2d %6s %7.2f ", ply, str, dvalue ); }
655 else { Out( " %2d %7.2f ", ply, dvalue ); }
658 for ( ply = 1; ply <= mpv_pv[ipv].length; ply++ )
661 if(xboard_mode && is_out) { // print PV move in WB format
662 out_xboard_move( mpv_pv[ipv].a[ply], tt );
667 if ( ply > 1 && ! ( (ply-1) % 5 ) )
671 str = str_CSA_move(mpv_pv[ipv].a[ply]);
672 OutCsaShogi( " %c%s", ach_turn[tt], str );
673 Out( "%2d.%c%-11s", ply, ach_turn[tt], str );
676 assert( is_move_valid( ptree, mpv_pv[ipv].a[ply], tt ) );
677 MakeMove( tt, mpv_pv[ipv].a[ply], ply );
682 if ( mpv_pv[ipv].type == hash_hit )
687 for ( ; ply < PLY_MAX; ply++ )
690 ptree->amove_hash[ply] = 0;
691 value_type = hash_probe( ptree, ply, 0, tt, -score_bound,
692 score_bound, &dummy );
693 if ( ! ( value_type == value_exact
694 && value == HASH_VALUE
695 && is_move_valid(ptree,ptree->amove_hash[ply],tt) ) )
699 mpv_pv[ipv].a[ply] = ptree->amove_hash[ply];
700 for ( i = 1; i < ply; i++ )
701 if ( mpv_pv[ipv].a[i]
702 == mpv_pv[ipv].a[ply] ) { goto rep_esc; }
705 if(xboard_mode && is_out) { // print PV move in WB format
706 out_xboard_move( mpv_pv[ipv].a[ply], tt );
711 if ( ply > 1 && ! ( (ply-1) % 5 ) )
715 str = str_CSA_move(mpv_pv[ipv].a[ply]);
716 OutCsaShogi( " %c%s", ach_turn[tt], str );
717 Out( "%2d:%c%-11s", ply, ach_turn[tt], str );
720 MakeMove( tt, mpv_pv[ipv].a[ply], ply );
723 UnMakeMove( tt, ptree->amove_hash[ply], ply );
726 mpv_pv[ipv].length++;
733 if ( is_out && mpv_pv[ipv].type != no_rep )
735 if ( (((ply-1) % 5) == 0) && (ply != 1) )
740 switch ( mpv_pv[ipv].type )
742 case perpetual_check: str = "PER. CHECK"; break;
743 case four_fold_rep: str = "REPETITION"; break;
744 case black_superi_rep:
745 case white_superi_rep: str = "SUPERI. POSI."; break;
746 case prev_solution: str = "PREV. SEARCH"; break;
747 case hash_hit: str = "HASH HIT"; break;
748 case book_hit: str = "BOOK HIT"; break;
749 case pv_fail_high: str = "FAIL HIGH"; break;
750 case mate_search: str = "MATE SEARCH"; break;
752 if ( str != NULL ) { Out( " <%s>", str ); }
754 for ( ply--; ply >= 1; ply-- )
757 UnMakeMove( tt, mpv_pv[ipv].a[ply], ply );
760 if ( is_out ) { Out( "\n" ); }
763 if ( mpv_out ) { OutCsaShogi( "\n" ); }
768 mpv_sub_result( unsigned int move )
772 for ( i = 0; mpv_pv[i].length; i++ )
774 assert( i < mpv_num*2 );
775 assert( i < root_nmove*2 );
776 assert( mpv_pv[i].depth <= iteration_depth );
777 assert( -score_bound < (int)mpv_pv[i].a[0]-32768 );
778 assert( (int)mpv_pv[i].a[0]-32768 < score_bound );
780 if ( mpv_pv[i].a[1] == move ) { break; }
783 for ( ; mpv_pv[i].length; i++ )
785 assert( i < mpv_num*2 );
786 assert( i < root_nmove*2 );
787 assert( mpv_pv[i].depth <= iteration_depth );
788 assert( -score_bound < (int)mpv_pv[i].a[0]-32768 );
789 assert( (int)mpv_pv[i].a[0]-32768 < score_bound );
791 mpv_pv[i] = mpv_pv[i+1];
797 mpv_add_result( tree_t * restrict ptree, int value )
801 int i, vmin, num, new_pv;
803 vmin = mpv_find_min( &num );
804 assert( num <= mpv_num );
805 assert( num < root_nmove );
806 assert( -score_bound < value );
807 assert( value < score_bound );
809 /* remove the weakest pv if all of slots are full */
810 if ( num == mpv_num )
812 for ( i = 0; mpv_pv[i].length; i++ )
814 assert( i < mpv_num*2 );
815 assert( i < root_nmove*2 );
816 assert( mpv_pv[i].depth <= iteration_depth );
817 assert( -score_bound < (int)mpv_pv[i].a[0]-32768 );
818 assert( (int)mpv_pv[i].a[0]-32768 < score_bound );
820 if ( mpv_pv[i].depth == iteration_depth
821 && mpv_pv[i].a[0] == (unsigned int)(vmin+32768) ) { break; }
823 assert( i != mpv_num*2 );
824 assert( mpv_pv[i].length );
826 assert( i < mpv_num*2 );
827 assert( i < root_nmove*2 );
828 mpv_pv[i] = mpv_pv[i+1];
830 } while ( mpv_pv[i].length );
834 for ( i = 0; mpv_pv[i].length; i++ )
836 assert( i < mpv_num*2 );
837 assert( i < root_nmove*2 );
838 assert( -score_bound < (int)mpv_pv[i].a[0]-32768 );
839 assert( (int)mpv_pv[i].a[0]-32768 < score_bound );
841 if ( mpv_pv[i].a[0] < (unsigned int)(value+32768) ) { break; }
845 pv.a[0] = (unsigned int)(value+32768);
846 new_pv = i; // [HGM] xboard: remember which is the new one, so we can print only that
848 assert( i < mpv_num*2 );
849 assert( i < root_nmove*2 );
854 } while ( pv.length );
856 if ( get_elapsed( &time ) < 0 ) { return -1; }
858 mpv_out( ptree, root_turn, time - time_start, new_pv );
865 mpv_set_bound( int alpha )
867 int bound, num, value;
869 bound = alpha - mpv_width;
870 if ( bound < -score_bound ) { bound = -score_bound; }
872 value = mpv_find_min( &num );
873 assert( num <= mpv_num );
874 assert( num < root_nmove );
876 assert( -score_bound < value );
877 assert( value < score_bound );
878 if ( num == mpv_num && bound < value ) { bound = value; }
885 mpv_find_min( int *pnum )
888 unsigned int a[ MPV_MAX_PV+1 ], u, utemp;
892 for ( i = 0; mpv_pv[i].length; i++ )
894 assert( i < mpv_num*2 );
895 assert( i < root_nmove*2 );
896 assert( mpv_pv[i].depth <= iteration_depth );
898 if ( mpv_pv[i].depth == iteration_depth )
901 assert( -score_bound < (int)u-32768 );
902 assert( (int)u-32768 < score_bound );
904 for ( num = 0; u <= a[num]; num++ );
906 assert( num < mpv_num );
907 assert( num < root_nmove );
917 if ( pnum ) { *pnum = num; }
919 if ( num ) { return (int)a[num-1] - 32768; }