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,
19 #if defined(NO_STDOUT) && defined(NO_LOGGING)
20 # define NextRootMove(a,b) next_root_move(a)
21 static int CONV next_root_move( tree_t * restrict ptree );
23 # define NextRootMove(a,b) next_root_move(a,b)
24 static int CONV next_root_move( tree_t * restrict ptree, int turn );
28 extern char xboard_mode;
32 search_wrapper( tree_t * restrict ptree, int alpha, int beta, int turn,
33 int depth, int ply, unsigned int state_node )
37 #if defined(DFPN_CLIENT)
38 /* try beta cut using results from DFPN server */
39 if ( root_move_list[root_index].dfpn_cresult == dfpn_client_win )
41 if ( ! root_index ) { Out( "- best move is proofed, skip.\n" ); }
42 ptree->pv[1].a[1] = MOVE_LAST;
43 ptree->pv[1].length = 1;
44 ptree->pv[1].depth = 0;
45 ptree->pv[1].type = no_rep;
47 return score_matelong;
51 value = search( ptree, alpha, beta, turn, depth, ply, state_node );
53 #if defined(DFPN_CLIENT)
54 /* catch a signal, i.e., the first move has to be ignored */
55 if ( game_status & flag_skip_root_move )
59 Out( "- %s is proofed while searching.\n", str_CSA_move(MOVE_LAST) );
62 Out( "- %s (best move) is proofed while searching.\n",
63 str_CSA_move(MOVE_LAST) );
66 game_status &= ~flag_skip_root_move;
69 ptree->pv[1].a[1] = MOVE_LAST;
70 ptree->pv[1].length = 1;
71 ptree->pv[1].depth = 0;
72 ptree->pv[1].type = no_rep;
74 return score_matelong;
83 searchr( tree_t * restrict ptree, int alpha, int beta, int turn, int depth )
85 uint64_t root_nodes_start;
86 int value, first_move;
87 int new_depth, extension, ply, state_node_new;
97 ptree->move_last[1] = ptree->move_last[0];
99 while( NextRootMove( ptree, turn ) )
101 root_nodes_start = ptree->node_searched;
103 if ( usi_mode != usi_off )
105 csa2usi( ptree, str_CSA_move(MOVE_CURR), str_usi );
109 MakeMove( turn, MOVE_CURR, 1 );
111 assert( ! InCheck( turn ) );
113 state_node_new = ( node_do_mate | node_do_null | node_do_futile
114 | node_do_recap | node_do_recursion
116 if ( InCheck(Flip(turn)) )
118 ptree->check_extension_done++;
119 ptree->nsuc_check[2] = (unsigned char)( ptree->nsuc_check[0] + 1U );
120 extension = EXT_CHECK - PLY_INC;
123 extension = - PLY_INC;
124 ptree->nsuc_check[2] = 0;
130 if ( root_mpv ) { bound = alpha; }
132 new_depth = depth + extension;
133 value = -search_wrapper( ptree, -beta, -alpha, Flip(turn),
134 new_depth, 2, state_node_new );
137 UnMakeMove( turn, MOVE_CURR, 1 );
141 if ( value <= alpha )
143 UnMakeMove( turn, MOVE_CURR, 1 );
152 bound = mpv_set_bound( alpha );
153 if ( depth + extension >= PLY_INC || ptree->nsuc_check[2] )
155 new_depth = depth + extension;
157 value = -search_wrapper( ptree, -bound-1, -bound, Flip(turn),
158 new_depth, 2, state_node_new );
159 if ( ! root_abort && bound < value )
161 new_depth = depth + extension;
162 value = -search_wrapper( ptree, -beta, -bound, Flip(turn),
163 new_depth, 2, state_node_new );
167 UnMakeMove( turn, MOVE_CURR, 1 );
172 value = -search_quies( ptree, -beta, -bound, Flip(turn), 2, 1 );
177 int depth_reduced = 0;
178 new_depth = depth + extension;
181 if ( 2*PLY_INC <= new_depth
182 && ! ptree->nsuc_check[ply]
183 && ! UToCap(MOVE_CURR)
184 && ! ( I2IsPromote(MOVE_CURR)
185 && I2PieceMove(MOVE_CURR) != silver ) )
187 unsigned int key = phash( MOVE_CURR, turn );
188 unsigned int good = ptree->hist_good[key] + 1;
189 unsigned int triedx8 = ( ptree->hist_tried[key] + 2 ) * 8U;
191 if ( good *160U < triedx8 ) { depth_reduced = PLY_INC * 3/2; }
192 else if ( good * 50U < triedx8 ) { depth_reduced = PLY_INC * 2/2; }
193 else if ( good * 19U < triedx8 ) { depth_reduced = PLY_INC * 1/2; }
195 depth_reduced = PLY_INC;
196 new_depth -= depth_reduced;
199 value = -search_wrapper( ptree, -alpha-1, -alpha, Flip(turn),
200 new_depth, 2, state_node_new );
201 if ( ! root_abort && alpha < value && depth_reduced )
203 new_depth += depth_reduced;
204 value = -search_wrapper( ptree, -alpha-1, -alpha, Flip(turn),
205 new_depth, 2, state_node_new );
209 UnMakeMove( turn, MOVE_CURR, 1 );
215 #if defined(DFPN_CLIENT)
216 if ( dfpn_client_sckt != SCKT_NULL
217 && 4 < iteration_depth
218 && dfpn_client_best_move != MOVE_CURR )
220 dfpn_client_best_move = MOVE_CURR;
221 lock( &dfpn_client_lock );
222 dfpn_client_out( "BEST MOVE %s\n",
223 str_CSA_move(dfpn_client_best_move) );
224 unlock( &dfpn_client_lock );
227 MnjOut( "pid=%d move=%s v=%dl n=% " PRIu64 "%s\n",
228 mnj_posi_id, str_CSA_move(MOVE_CURR), alpha+1,
229 ptree->node_searched,
230 ( mnj_depth_stable <= iteration_depth ) ? " stable" : "" );
233 if ( usi_mode != usi_off )
235 USIOut( "info depth %d score cp %d nodes %" PRIu64 " pv %s\n",
236 iteration_depth, alpha+1, ptree->node_searched,
241 new_depth = depth + extension;
243 value = -search_wrapper( ptree, -beta, -alpha, Flip(turn),
244 new_depth, 2, state_node_new );
251 UnMakeMove( turn, MOVE_CURR, 1 );
252 pv_close( ptree, 2, pv_fail_high );
253 time_last_result = time_last_check;
254 root_value = alpha+1;
255 ptree->pv[0] = ptree->pv[1];
258 dvalue = -(double)alpha;
265 str = str_CSA_move(MOVE_CURR);
266 Out( " %7.2f 1.%c%s [%c0!]\n",
267 dvalue / 100.0, ch, str, ch );
268 if ( game_status & flag_pondering )
270 OutCsaShogi( "info%+.2f %c%s %c%s [%c0!]\n",
271 dvalue / 100.0, ach_turn[Flip(turn)],
272 str_CSA_move(ponder_move),
276 OutCsaShogi( "info%+.2f %c%s [%c0!]\n",
277 dvalue / 100.0, ch, str, ch );
284 UnMakeMove( turn, MOVE_CURR, 1 );
286 root_move_list[root_index].nodes
287 = ptree->node_searched - root_nodes_start;
290 if ( root_mpv && value < beta )
292 mpv_sub_result( MOVE_CURR );
293 if ( bound < value && mpv_add_result( ptree, value ) < 0 )
295 game_status |= flag_search_error;
303 if ( save_result( ptree, value, beta, turn ) < 0 )
305 game_status |= flag_search_error;
308 if ( beta <= value ) { return value; }
312 if ( root_abort ) { return 0; }
319 out_pv( tree_t * restrict ptree, int value, int turn, unsigned int time )
330 is_out = ( 4 < iteration_depth || abs(value) > score_max_eval ) ? 1 : 0;
333 if ( root_mpv ) { is_out = 0; }
337 if ( usi_mode != usi_off )
347 str = str_time_symple( time );
348 dvalue = (double)( turn ? -value : value ) / 100.0;
349 OutCsaShogi( "info%+.2f", dvalue );
350 if ( game_status & flag_pondering )
352 OutCsaShogi( " %c%s", ach_turn[Flip(turn)],
353 str_CSA_move(ponder_move) );
356 if ( ptree->pv[0].length )
359 if(xboard_mode) Out("%2d %6d %6d %8d ", iteration_depth, value, time/10, 1); else
361 if ( root_move_list[root_index].status & flag_first )
363 Out( " %2d %6s %7.2f ", iteration_depth, str, dvalue );
365 else { Out( " %6s %7.2f ", str, dvalue ); }
369 for ( ply = 1; ply <= ptree->pv[0].length; ply++ )
372 if(xboard_mode && is_out) { // print PV move in WB format
373 int move = ptree->pv[0].a[ply], from = I2From(move), to = I2To(move);
374 char inPromoZone = tt > 0 ? from >= 6*9 || to >= 6*9 : to < 3*9|| from < 3*9;
376 Out(" %c@%c%c", "PLNSGBR"[From2Drop(from)-1], 'a'+to%9, '9'-to/9);
378 Out(" %c%c%c%c%s", 'a'+from%9, '9'-from/9, 'a'+to%9, '9'-to/9,
379 inPromoZone ? I2IsPromote(move) ? "+" : "=" : "");
384 if ( ply > 1 && ! ( (ply-1) % 5 ) )
388 str = str_CSA_move( ptree->pv[0].a[ply] );
389 OutCsaShogi( " %c%s", ach_turn[tt], str );
390 Out( "%2d.%c%-7s", ply, ach_turn[tt], str );
393 if ( usi_mode != usi_off && ply <= 4 )
396 csa2usi( ptree, str_CSA_move(ptree->pv[0].a[ply]), str_usi );
397 ipv += snprintf( str_pv + ipv, 256 - ipv, " %s", str_usi );
402 MakeMove( tt, ptree->pv[0].a[ply], ply );
407 if ( ptree->pv[0].type == hash_hit )
412 for ( ; ply < PLY_MAX; ply++ )
415 ptree->amove_hash[ply] = 0;
416 value_type = hash_probe( ptree, ply, 0, tt, -score_bound,
417 score_bound, &dummy );
418 if ( ! ( value_type == value_exact
419 && value == HASH_VALUE
420 && is_move_valid( ptree, ptree->amove_hash[ply], tt ) ) )
424 ptree->pv[0].a[ply] = ptree->amove_hash[ply];
425 for ( i = 1; i < ply; i++ )
426 if ( ptree->pv[0].a[i] == ptree->pv[0].a[ply] ) { goto rep_esc; }
429 if(xboard_mode && is_out) { // print PV move in WB format
430 int move = ptree->pv[0].a[ply], from = I2From(move), to = I2To(move);
431 char inPromoZone = tt > 0 ? from >= 6*9 || to >= 6*9 : to < 3*9|| from < 3*9;
433 Out(" %c@%c%c", "PLNSGBR"[From2Drop(from)-1], 'a'+to%9, '9'-to/9);
435 Out(" %c%c%c%c%s", 'a'+from%9, '9'-from/9, 'a'+to%9, '9'-to/9,
436 inPromoZone ? I2IsPromote(move) ? "+" : "=" : "");
441 if ( ply > 1 && ! ( (ply-1) % 5 ) )
445 str = str_CSA_move(ptree->pv[0].a[ply]);
446 OutCsaShogi( " %c%s", ach_turn[tt], str );
447 Out( "%2d:%c%-7s", ply, ach_turn[tt], str );
450 if ( usi_mode != usi_off && ply <= 4 )
453 csa2usi( ptree, str_CSA_move(ptree->pv[0].a[ply]), str_usi );
454 ipv += snprintf( str_pv + ipv, 256 - ipv, " %s", str_usi );
459 MakeMove( tt, ptree->pv[0].a[ply], ply );
462 UnMakeMove( tt, ptree->amove_hash[ply], ply );
465 ptree->pv[0].length++;
472 if ( is_out && ptree->pv[0].type != no_rep )
474 if ( (((ply-1) % 5) == 0) && (ply != 1) )
479 switch ( ptree->pv[0].type )
481 case perpetual_check: str = "PER. CHECK"; break;
482 case four_fold_rep: str = "REPETITION"; break;
483 case black_superi_rep:
484 case white_superi_rep: str = "SUPERI. POSI."; break;
485 case prev_solution: str = "PREV. SEARCH"; break;
486 case hash_hit: str = "HASH HIT"; break;
487 case book_hit: str = "BOOK HIT"; break;
488 case pv_fail_high: str = "FAIL HIGH"; break;
489 case mate_search: str = "MATE SEARCH"; break;
491 if ( str != NULL ) { Out( " <%s>", str ); }
493 for ( ply--; ply >= 1; ply-- )
497 UnMakeMove( tt, ptree->pv[0].a[ply], ply );
504 USIOut( "info depth %d score cp %d nodes %" PRIu64 " pv%s\n",
505 iteration_depth, value, ptree->node_searched, str_pv );
511 save_result( tree_t * restrict ptree, int value, int beta, int turn )
513 root_move_t root_move_temp;
516 if ( get_elapsed( &time_last_result ) < 0 ) { return -1; }
521 root_move_temp = root_move_list[index];
522 for ( ; index > 0; index-- )
524 root_move_list[index] = root_move_list[index-1];
526 root_move_list[0] = root_move_temp;
529 if ( beta <= value ) { pv_close( ptree, 2, pv_fail_high ); }
531 ptree->pv[0] = ptree->pv[1];
536 #if defined(DFPN_CLIENT)
537 if ( dfpn_client_sckt != SCKT_NULL
538 && 4 < iteration_depth
539 && dfpn_client_best_move != ptree->pv[1].a[1] )
541 dfpn_client_best_move = ptree->pv[1].a[1];
542 lock( &dfpn_client_lock );
543 dfpn_client_out( "BEST MOVE %s\n",
544 str_CSA_move(dfpn_client_best_move) );
545 unlock( &dfpn_client_lock );
548 MnjOut( "pid=%d move=%s v=%de n=%" PRIu64 "%s\n",
549 mnj_posi_id, str_CSA_move(ptree->pv[1].a[1]), value,
550 ptree->node_searched,
551 ( mnj_depth_stable <= iteration_depth ) ? " stable" : "" );
553 out_pv( ptree, value, turn, time_last_result - time_start );
561 #if defined(NO_STDOUT) && defined(NO_LOGGING)
562 next_root_move( tree_t * restrict ptree )
564 next_root_move( tree_t * restrict ptree, int turn )
570 for ( i = 0; i < n; i++ )
572 if ( root_move_list[i].status & flag_searched ) { continue; }
573 root_move_list[i].status |= flag_searched;
574 ptree->current_move[1] = root_move_list[i].move;
577 #if ! ( defined(NO_STDOUT) && defined(NO_LOGGING) )
581 if ( iteration_depth > 5 )
583 const char *str_move;
586 str_move = str_CSA_move(ptree->current_move[1]);
587 snprintf( str, 9, "%d/%d", i+1, root_nmove );
588 if ( root_move_list[i].status & flag_first )
590 Out( "(%2d) %7s* 1.%c%s \r",
591 iteration_depth, str, ach_turn[turn], str_move );
594 Out( " %7s* 1.%c%s \r",
595 str, ach_turn[turn], str_move );
609 mpv_out( tree_t * restrict ptree, int turn, unsigned int time )
611 int mpv_out, ipv, best;
613 best = (int)mpv_pv[0].a[0] - 32768;
614 mpv_out = ( iteration_depth > 3 || abs(best) > score_max_eval ) ? 1 : 0;
616 for ( ipv = 0; mpv_pv[ipv].length; ipv++ )
620 int tt, is_out, value, ply;
622 assert( ipv < mpv_num*2 );
624 value = (int)mpv_pv[ipv].a[0] - 32768;
625 if ( mpv_out && value > best - mpv_width && ipv < mpv_num )
633 dvalue = (double)( turn ? -value : value ) / 100.0;
634 if ( is_out && ! ipv ) { OutCsaShogi( "info" ); }
635 if ( is_out && ipv ) { OutCsaShogi( ":" ); }
637 OutCsaShogi( "%+.2f", dvalue );
638 if ( game_status & flag_pondering )
640 OutCsaShogi( " %c%s", ach_turn[Flip(turn)],
641 str_CSA_move(ponder_move) );
644 str = str_time_symple( time );
645 ply = mpv_pv[ipv].depth;
646 if ( ! ipv ) { Out( "o%2d %6s %7.2f ", ply, str, dvalue ); }
647 else { Out( " %2d %7.2f ", ply, dvalue ); }
650 for ( ply = 1; ply <= mpv_pv[ipv].length; ply++ )
654 if ( ply > 1 && ! ( (ply-1) % 5 ) )
658 str = str_CSA_move(mpv_pv[ipv].a[ply]);
659 OutCsaShogi( " %c%s", ach_turn[tt], str );
660 Out( "%2d.%c%-11s", ply, ach_turn[tt], str );
663 assert( is_move_valid( ptree, mpv_pv[ipv].a[ply], tt ) );
664 MakeMove( tt, mpv_pv[ipv].a[ply], ply );
669 if ( mpv_pv[ipv].type == hash_hit )
674 for ( ; ply < PLY_MAX; ply++ )
677 ptree->amove_hash[ply] = 0;
678 value_type = hash_probe( ptree, ply, 0, tt, -score_bound,
679 score_bound, &dummy );
680 if ( ! ( value_type == value_exact
681 && value == HASH_VALUE
682 && is_move_valid(ptree,ptree->amove_hash[ply],tt) ) )
686 mpv_pv[ipv].a[ply] = ptree->amove_hash[ply];
687 for ( i = 1; i < ply; i++ )
688 if ( mpv_pv[ipv].a[i]
689 == mpv_pv[ipv].a[ply] ) { goto rep_esc; }
693 if ( ply > 1 && ! ( (ply-1) % 5 ) )
697 str = str_CSA_move(mpv_pv[ipv].a[ply]);
698 OutCsaShogi( " %c%s", ach_turn[tt], str );
699 Out( "%2d:%c%-11s", ply, ach_turn[tt], str );
702 MakeMove( tt, mpv_pv[ipv].a[ply], ply );
705 UnMakeMove( tt, ptree->amove_hash[ply], ply );
708 mpv_pv[ipv].length++;
715 if ( is_out && mpv_pv[ipv].type != no_rep )
717 if ( (((ply-1) % 5) == 0) && (ply != 1) )
722 switch ( mpv_pv[ipv].type )
724 case perpetual_check: str = "PER. CHECK"; break;
725 case four_fold_rep: str = "REPETITION"; break;
726 case black_superi_rep:
727 case white_superi_rep: str = "SUPERI. POSI."; break;
728 case prev_solution: str = "PREV. SEARCH"; break;
729 case hash_hit: str = "HASH HIT"; break;
730 case book_hit: str = "BOOK HIT"; break;
731 case pv_fail_high: str = "FAIL HIGH"; break;
732 case mate_search: str = "MATE SEARCH"; break;
734 if ( str != NULL ) { Out( " <%s>", str ); }
736 for ( ply--; ply >= 1; ply-- )
739 UnMakeMove( tt, mpv_pv[ipv].a[ply], ply );
742 if ( is_out ) { Out( "\n" ); }
745 if ( mpv_out ) { OutCsaShogi( "\n" ); }
750 mpv_sub_result( unsigned int move )
754 for ( i = 0; mpv_pv[i].length; i++ )
756 assert( i < mpv_num*2 );
757 assert( i < root_nmove*2 );
758 assert( mpv_pv[i].depth <= iteration_depth );
759 assert( -score_bound < (int)mpv_pv[i].a[0]-32768 );
760 assert( (int)mpv_pv[i].a[0]-32768 < score_bound );
762 if ( mpv_pv[i].a[1] == move ) { break; }
765 for ( ; mpv_pv[i].length; i++ )
767 assert( i < mpv_num*2 );
768 assert( i < root_nmove*2 );
769 assert( mpv_pv[i].depth <= iteration_depth );
770 assert( -score_bound < (int)mpv_pv[i].a[0]-32768 );
771 assert( (int)mpv_pv[i].a[0]-32768 < score_bound );
773 mpv_pv[i] = mpv_pv[i+1];
779 mpv_add_result( tree_t * restrict ptree, int value )
785 vmin = mpv_find_min( &num );
786 assert( num <= mpv_num );
787 assert( num < root_nmove );
788 assert( -score_bound < value );
789 assert( value < score_bound );
791 /* remove the weakest pv if all of slots are full */
792 if ( num == mpv_num )
794 for ( i = 0; mpv_pv[i].length; i++ )
796 assert( i < mpv_num*2 );
797 assert( i < root_nmove*2 );
798 assert( mpv_pv[i].depth <= iteration_depth );
799 assert( -score_bound < (int)mpv_pv[i].a[0]-32768 );
800 assert( (int)mpv_pv[i].a[0]-32768 < score_bound );
802 if ( mpv_pv[i].depth == iteration_depth
803 && mpv_pv[i].a[0] == (unsigned int)(vmin+32768) ) { break; }
805 assert( i != mpv_num*2 );
806 assert( mpv_pv[i].length );
808 assert( i < mpv_num*2 );
809 assert( i < root_nmove*2 );
810 mpv_pv[i] = mpv_pv[i+1];
812 } while ( mpv_pv[i].length );
816 for ( i = 0; mpv_pv[i].length; i++ )
818 assert( i < mpv_num*2 );
819 assert( i < root_nmove*2 );
820 assert( -score_bound < (int)mpv_pv[i].a[0]-32768 );
821 assert( (int)mpv_pv[i].a[0]-32768 < score_bound );
823 if ( mpv_pv[i].a[0] < (unsigned int)(value+32768) ) { break; }
827 pv.a[0] = (unsigned int)(value+32768);
829 assert( i < mpv_num*2 );
830 assert( i < root_nmove*2 );
835 } while ( pv.length );
837 if ( get_elapsed( &time ) < 0 ) { return -1; }
839 mpv_out( ptree, root_turn, time - time_start );
846 mpv_set_bound( int alpha )
848 int bound, num, value;
850 bound = alpha - mpv_width;
851 if ( bound < -score_bound ) { bound = -score_bound; }
853 value = mpv_find_min( &num );
854 assert( num <= mpv_num );
855 assert( num < root_nmove );
857 assert( -score_bound < value );
858 assert( value < score_bound );
859 if ( num == mpv_num && bound < value ) { bound = value; }
866 mpv_find_min( int *pnum )
869 unsigned int a[ MPV_MAX_PV+1 ], u, utemp;
873 for ( i = 0; mpv_pv[i].length; i++ )
875 assert( i < mpv_num*2 );
876 assert( i < root_nmove*2 );
877 assert( mpv_pv[i].depth <= iteration_depth );
879 if ( mpv_pv[i].depth == iteration_depth )
882 assert( -score_bound < (int)u-32768 );
883 assert( (int)u-32768 < score_bound );
885 for ( num = 0; u <= a[num]; num++ );
887 assert( num < mpv_num );
888 assert( num < root_nmove );
898 if ( pnum ) { *pnum = num; }
900 if ( num ) { return (int)a[num-1] - 32768; }