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 );
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 );
222 out_pv( tree_t * restrict ptree, int value, int turn, unsigned int time )
229 is_out = ( iteration_depth > 3 || abs(value) > score_max_eval ) ? 1 : 0;
232 if ( root_mpv ) { is_out = 0; }
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 )
242 OutCsaShogi( " %c%s", ach_turn[Flip(turn)],
243 str_CSA_move(ponder_move) );
246 if ( ptree->pv[0].length )
248 int i = find_root_move( ptree->pv[0].a[1] );
250 if(xboard_mode) Out("%2d %6d %6d %8d ", iteration_depth, value, time/10, 1); else
252 if ( root_move_list[i].status & flag_first )
254 Out( " %2d %6s %7.2f ", iteration_depth, str, dvalue );
256 else { Out( " %6s %7.2f ", str, dvalue ); }
260 for ( ply = 1; ply <= ptree->pv[0].length; ply++ )
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;
267 Out(" %c@%c%c", "PLNSGBR"[From2Drop(from)-1], 'a'+to%9, '9'-to/9);
269 Out(" %c%c%c%c%s", 'a'+from%9, '9'-from/9, 'a'+to%9, '9'-to/9,
270 inPromoZone ? I2IsPromote(move) ? "+" : "=" : "");
275 if ( ply > 1 && ! ( (ply-1) % 4 ) )
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 );
284 MakeMove( tt, ptree->pv[0].a[ply], ply );
289 if ( ptree->pv[0].type == hash_hit )
293 for ( ; ply < PLY_MAX; ply++ )
295 ptree->amove_hash[ply] = 0;
296 value_type = hash_probe( ptree, ply, 0, tt, -score_bound,
298 if ( ! ( value_type == value_exact
299 && value == HASH_VALUE
300 && is_move_valid( ptree, ptree->amove_hash[ply], tt ) ) )
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; }
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;
313 Out(" %c@%c%c", "PLNSGBR"[From2Drop(from)-1], 'a'+to%9, '9'-to/9);
315 Out(" %c%c%c%c%s", 'a'+from%9, '9'-from/9, 'a'+to%9, '9'-to/9,
316 inPromoZone ? I2IsPromote(move) ? "+" : "=" : "");
321 if ( ply > 1 && ! ( (ply-1) % 4 ) )
325 str = str_CSA_move_plus( ptree, ptree->pv[0].a[ply], ply,
327 OutCsaShogi( " %c%s", ach_turn[tt], str );
328 Out( "%2d:%c%-11s", ply, ach_turn[tt], str );
331 MakeMove( tt, ptree->pv[0].a[ply], ply );
334 UnMakeMove( tt, ptree->amove_hash[ply], ply );
337 ptree->pv[0].length++;
344 if ( is_out && ptree->pv[0].type != no_rep )
346 if ( (((ply-1) % 4) == 0) && (ply != 1) )
351 switch ( ptree->pv[0].type )
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;
363 if ( str != NULL ) { Out( " <%s>", str ); }
365 for ( ply--; ply >= 1; ply-- )
368 UnMakeMove( tt, ptree->pv[0].a[ply], ply );
380 save_result( tree_t * restrict ptree, int value, int beta, int turn )
382 root_move_t root_move_temp;
385 if ( get_elapsed( &time_last_result ) < 0 ) { return -1; }
387 i = find_root_move( ptree->current_move[1] );
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;
395 if ( beta <= value ) { pv_close( ptree, 2, pv_fail_high ); }
397 if ( ptree->pv[0].a[1] != ptree->pv[1].a[1] )
399 time_last_eff_search = time_last_search;
402 ptree->pv[0] = ptree->pv[1];
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 );
417 #if defined(NO_STDOUT) && defined(NO_LOGGING)
418 next_root_move( tree_t * restrict ptree )
420 next_root_move( tree_t * restrict ptree, int turn )
426 for ( i = 0; i < n; i++ )
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;
432 #if ! ( defined(NO_STDOUT) && defined(NO_LOGGING) )
436 if ( iteration_depth > 5 )
438 const char *str_move;
440 /* check: does this code have small impact on performance? */
441 str_move = str_CSA_move_plus( ptree, ptree->current_move[1], 1,
443 snprintf( str, 9, "%d/%d", i+1, root_nmove );
444 if ( root_move_list[i].status & flag_first )
446 Out( "(%2d) %7s* 1.%c%s \r",
447 iteration_depth, str, ach_turn[turn], str_move );
450 Out( " %7s* 1.%c%s \r",
451 str, ach_turn[turn], str_move );
464 find_root_move( unsigned int move )
469 for ( i = 0; i < n; i++ )
470 if ( root_move_list[i].move == move ) { break; }
478 mpv_out( tree_t * restrict ptree, int turn, unsigned int time )
480 int mpv_out, ipv, best;
482 best = (int)mpv_pv[0].a[0] - 32768;
483 mpv_out = ( iteration_depth > 3 || abs(best) > score_max_eval ) ? 1 : 0;
485 for ( ipv = 0; mpv_pv[ipv].length; ipv++ )
489 int tt, is_out, value, ply;
491 assert( ipv < mpv_num*2 );
493 value = (int)mpv_pv[ipv].a[0] - 32768;
494 if ( mpv_out && value > best - mpv_width && ipv < mpv_num )
502 dvalue = (double)( turn ? -value : value ) / 100.0;
503 if ( is_out && ! ipv ) { OutCsaShogi( "info" ); }
504 if ( is_out && ipv ) { OutCsaShogi( ":" ); }
506 OutCsaShogi( "%+.2f", dvalue );
507 if ( game_status & flag_pondering )
509 OutCsaShogi( " %c%s", ach_turn[Flip(turn)],
510 str_CSA_move(ponder_move) );
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 ); }
519 for ( ply = 1; ply <= mpv_pv[ipv].length; ply++ )
523 if ( ply > 1 && ! ( (ply-1) % 4 ) )
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 );
532 assert( is_move_valid( ptree, mpv_pv[ipv].a[ply], tt ) );
533 MakeMove( tt, mpv_pv[ipv].a[ply], ply );
538 if ( mpv_pv[ipv].type == hash_hit )
542 for ( ; ply < PLY_MAX; ply++ )
544 ptree->amove_hash[ply] = 0;
545 value_type = hash_probe( ptree, ply, 0, tt, -score_bound,
547 if ( ! ( value_type == value_exact
548 && value == HASH_VALUE
549 && is_move_valid(ptree,ptree->amove_hash[ply],tt) ) )
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; }
560 if ( ply > 1 && ! ( (ply-1) % 4 ) )
564 str = str_CSA_move_plus( ptree, mpv_pv[ipv].a[ply], ply,
566 OutCsaShogi( " %c%s", ach_turn[tt], str );
567 Out( "%2d:%c%-11s", ply, ach_turn[tt], str );
570 MakeMove( tt, mpv_pv[ipv].a[ply], ply );
573 UnMakeMove( tt, ptree->amove_hash[ply], ply );
576 mpv_pv[ipv].length++;
583 if ( is_out && mpv_pv[ipv].type != no_rep )
585 if ( (((ply-1) % 4) == 0) && (ply != 1) )
590 switch ( mpv_pv[ipv].type )
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;
602 if ( str != NULL ) { Out( " <%s>", str ); }
604 for ( ply--; ply >= 1; ply-- )
607 UnMakeMove( tt, mpv_pv[ipv].a[ply], ply );
610 if ( is_out ) { Out( "\n" ); }
613 if ( mpv_out ) { OutCsaShogi( "\n" ); }
618 mpv_sub_result( unsigned int move )
622 for ( i = 0; mpv_pv[i].length; i++ )
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 );
630 if ( mpv_pv[i].a[1] == move ) { break; }
633 for ( ; mpv_pv[i].length; i++ )
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 );
641 mpv_pv[i] = mpv_pv[i+1];
647 mpv_add_result( tree_t * restrict ptree, int value )
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 );
659 /* remove the weakest pv if all of slots are full */
660 if ( num == mpv_num )
662 for ( i = 0; mpv_pv[i].length; i++ )
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 );
670 if ( mpv_pv[i].depth == iteration_depth
671 && mpv_pv[i].a[0] == (unsigned int)(vmin+32768) ) { break; }
673 assert( i != mpv_num*2 );
674 assert( mpv_pv[i].length );
676 assert( i < mpv_num*2 );
677 assert( i < root_nmove*2 );
678 mpv_pv[i] = mpv_pv[i+1];
680 } while ( mpv_pv[i].length );
684 for ( i = 0; mpv_pv[i].length; i++ )
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 );
691 if ( mpv_pv[i].a[0] < (unsigned int)(value+32768) ) { break; }
695 pv.a[0] = (unsigned int)(value+32768);
697 assert( i < mpv_num*2 );
698 assert( i < root_nmove*2 );
703 } while ( pv.length );
705 if ( get_elapsed( &time ) < 0 ) { return -1; }
707 mpv_out( ptree, root_turn, time - time_start );
714 mpv_set_bound( int alpha )
716 int bound, num, value;
718 bound = alpha - mpv_width;
719 if ( bound < -score_bound ) { bound = -score_bound; }
721 value = mpv_find_min( &num );
722 assert( num <= mpv_num );
723 assert( num < root_nmove );
725 assert( -score_bound < value );
726 assert( value < score_bound );
727 if ( num == mpv_num && bound < value ) { bound = value; }
734 mpv_find_min( int *pnum )
737 unsigned int a[ MPV_MAX_PV+1 ], u, utemp;
741 for ( i = 0; mpv_pv[i].length; i++ )
743 assert( i < mpv_num*2 );
744 assert( i < root_nmove*2 );
745 assert( mpv_pv[i].depth <= iteration_depth );
747 if ( mpv_pv[i].depth == iteration_depth )
750 assert( -score_bound < (int)u-32768 );
751 assert( (int)u-32768 < score_bound );
753 for ( num = 0; u <= a[num]; num++ );
755 assert( num < mpv_num );
756 assert( num < root_nmove );
766 if ( pnum ) { *pnum = num; }
768 if ( num ) { return (int)a[num-1] - 32768; }