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 searchr( tree_t * restrict ptree, int alpha, int beta, int turn, int depth )
30 uint64_t root_nodes_start;
31 int value, first_move_expanded, i;
32 int new_depth, extension, ply, state_node_new;
37 first_move_expanded = 1;
39 ptree->move_last[1] = ptree->move_last[0];
41 while( NextRootMove( ptree, turn ) )
43 root_nodes_start = ptree->node_searched;
44 MakeMove( turn, MOVE_CURR, 1 );
46 assert( ! InCheck( turn ) );
48 state_node_new = ( node_do_mate | node_do_null | node_do_futile
50 if ( InCheck(Flip(turn)) )
52 ptree->check_extension_done++;
53 ptree->nsuc_check[2] = (unsigned char)( ptree->nsuc_check[0] + 1U );
54 extension = EXT_CHECK - PLY_INC;
57 extension = - PLY_INC;
58 ptree->nsuc_check[2] = 0;
61 if ( first_move_expanded )
64 if ( root_mpv ) { bound = alpha; }
66 new_depth = depth + extension;
67 value = -search( ptree, -beta, -alpha, Flip(turn), new_depth, 2,
71 UnMakeMove( turn, MOVE_CURR, 1 );
77 UnMakeMove( turn, MOVE_CURR, 1 );
81 first_move_expanded = 0;
86 bound = mpv_set_bound( alpha );
87 if ( depth + extension >= PLY_INC || ptree->nsuc_check[2] )
89 new_depth = depth + extension;
91 value = -search( ptree, -bound-1, -bound, Flip(turn), new_depth,
93 if ( ! root_abort && bound < value )
95 new_depth = depth + extension;
96 value = -search( ptree, -beta, -bound, Flip(turn), new_depth,
101 UnMakeMove( turn, MOVE_CURR, 1 );
106 value = -search_quies( ptree, -beta, -bound, Flip(turn), 2, 1 );
111 new_depth = depth + extension;
113 value = -search( ptree, -alpha-1, -alpha, Flip(turn), new_depth, 2,
117 UnMakeMove( turn, MOVE_CURR, 1 );
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 );
126 new_depth = depth + extension;
128 value = -search( ptree, -beta, -alpha, Flip(turn), new_depth,
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];
144 dvalue = -(double)alpha;
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 )
156 OutCsaShogi( "info%+.2f %c%s %c%s [%c0!]\n",
157 dvalue / 100.0, ach_turn[Flip(turn)],
158 str_CSA_move(ponder_move),
162 OutCsaShogi( "info%+.2f %c%s [%c0!]\n",
163 dvalue / 100.0, ch, str, ch );
170 UnMakeMove( turn, MOVE_CURR, 1 );
172 i = find_root_move( MOVE_CURR );
173 root_move_list[i].nodes = ptree->node_searched - root_nodes_start;
176 if ( root_mpv && value < beta )
178 mpv_sub_result( MOVE_CURR );
179 if ( bound < value && mpv_add_result( ptree, value ) < 0 )
181 game_status |= flag_search_error;
189 if ( save_result( ptree, value, beta, turn ) < 0 )
191 game_status |= flag_search_error;
196 hash_store( ptree, 1, depth, turn, value_lower, value,
203 if ( root_abort ) { return 0; }
205 #if ! defined(MINIMUM)
206 if ( ! ( game_status & flag_learning ) )
209 hash_store( ptree, 1, depth, turn, value_exact, alpha,
210 ptree->pv[1].a[1], 0 );
218 out_pv( tree_t * restrict ptree, int value, int turn, unsigned int time )
225 is_out = ( iteration_depth > 3 || abs(value) > score_max_eval ) ? 1 : 0;
228 if ( root_mpv ) { is_out = 0; }
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 )
238 OutCsaShogi( " %c%s", ach_turn[Flip(turn)],
239 str_CSA_move(ponder_move) );
242 if ( ptree->pv[0].length )
244 int i = find_root_move( ptree->pv[0].a[1] );
245 if ( root_move_list[i].status & flag_first )
247 Out( " %2d %6s %7.2f ", iteration_depth, str, dvalue );
249 else { Out( " %6s %7.2f ", str, dvalue ); }
253 for ( ply = 1; ply <= ptree->pv[0].length; ply++ )
257 if ( ply > 1 && ! ( (ply-1) % 4 ) )
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 );
266 MakeMove( tt, ptree->pv[0].a[ply], ply );
271 if ( ptree->pv[0].type == hash_hit )
275 for ( ; ply < PLY_MAX; ply++ )
277 ptree->amove_hash[ply] = 0;
278 value_type = hash_probe( ptree, ply, 0, tt, -score_bound,
280 if ( ! ( value_type == value_exact
281 && value == HASH_VALUE
282 && is_move_valid( ptree, ptree->amove_hash[ply], tt ) ) )
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; }
292 if ( ply > 1 && ! ( (ply-1) % 4 ) )
296 str = str_CSA_move_plus( ptree, ptree->pv[0].a[ply], ply,
298 OutCsaShogi( " %c%s", ach_turn[tt], str );
299 Out( "%2d:%c%-11s", ply, ach_turn[tt], str );
302 MakeMove( tt, ptree->pv[0].a[ply], ply );
305 UnMakeMove( tt, ptree->amove_hash[ply], ply );
308 ptree->pv[0].length++;
315 if ( is_out && ptree->pv[0].type != no_rep )
317 if ( (((ply-1) % 4) == 0) && (ply != 1) )
322 switch ( ptree->pv[0].type )
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;
334 if ( str != NULL ) { Out( " <%s>", str ); }
336 for ( ply--; ply >= 1; ply-- )
339 UnMakeMove( tt, ptree->pv[0].a[ply], ply );
351 save_result( tree_t * restrict ptree, int value, int beta, int turn )
353 root_move_t root_move_temp;
356 if ( get_elapsed( &time_last_result ) < 0 ) { return -1; }
358 i = find_root_move( ptree->current_move[1] );
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;
366 if ( beta <= value ) { pv_close( ptree, 2, pv_fail_high ); }
368 if ( ptree->pv[0].a[1] != ptree->pv[1].a[1] )
370 time_last_eff_search = time_last_search;
373 ptree->pv[0] = ptree->pv[1];
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 );
388 #if defined(NO_STDOUT) && defined(NO_LOGGING)
389 next_root_move( tree_t * restrict ptree )
391 next_root_move( tree_t * restrict ptree, int turn )
397 for ( i = 0; i < n; i++ )
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;
403 #if ! ( defined(NO_STDOUT) && defined(NO_LOGGING) )
404 if ( iteration_depth > 5 )
406 const char *str_move;
408 /* check: does this code have small impact on performance? */
409 str_move = str_CSA_move_plus( ptree, ptree->current_move[1], 1,
411 snprintf( str, 9, "%d/%d", i+1, root_nmove );
412 if ( root_move_list[i].status & flag_first )
414 Out( "(%2d) %7s* 1.%c%s \r",
415 iteration_depth, str, ach_turn[turn], str_move );
418 Out( " %7s* 1.%c%s \r",
419 str, ach_turn[turn], str_move );
432 find_root_move( unsigned int move )
437 for ( i = 0; i < n; i++ )
438 if ( root_move_list[i].move == move ) { break; }
446 mpv_out( tree_t * restrict ptree, int turn, unsigned int time )
448 int mpv_out, ipv, best;
450 best = (int)mpv_pv[0].a[0] - 32768;
451 mpv_out = ( iteration_depth > 3 || abs(best) > score_max_eval ) ? 1 : 0;
453 for ( ipv = 0; mpv_pv[ipv].length; ipv++ )
457 int tt, is_out, value, ply;
459 assert( ipv < mpv_num*2 );
461 value = (int)mpv_pv[ipv].a[0] - 32768;
462 if ( mpv_out && value > best - mpv_width && ipv < mpv_num )
470 dvalue = (double)( turn ? -value : value ) / 100.0;
471 if ( is_out && ! ipv ) { OutCsaShogi( "info" ); }
472 if ( is_out && ipv ) { OutCsaShogi( ":" ); }
474 OutCsaShogi( "%+.2f", dvalue );
475 if ( game_status & flag_pondering )
477 OutCsaShogi( " %c%s", ach_turn[Flip(turn)],
478 str_CSA_move(ponder_move) );
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 ); }
487 for ( ply = 1; ply <= mpv_pv[ipv].length; ply++ )
491 if ( ply > 1 && ! ( (ply-1) % 4 ) )
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 );
500 assert( is_move_valid( ptree, mpv_pv[ipv].a[ply], tt ) );
501 MakeMove( tt, mpv_pv[ipv].a[ply], ply );
506 if ( mpv_pv[ipv].type == hash_hit )
510 for ( ; ply < PLY_MAX; ply++ )
512 ptree->amove_hash[ply] = 0;
513 value_type = hash_probe( ptree, ply, 0, tt, -score_bound,
515 if ( ! ( value_type == value_exact
516 && value == HASH_VALUE
517 && is_move_valid(ptree,ptree->amove_hash[ply],tt) ) )
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; }
528 if ( ply > 1 && ! ( (ply-1) % 4 ) )
532 str = str_CSA_move_plus( ptree, mpv_pv[ipv].a[ply], ply,
534 OutCsaShogi( " %c%s", ach_turn[tt], str );
535 Out( "%2d:%c%-11s", ply, ach_turn[tt], str );
538 MakeMove( tt, mpv_pv[ipv].a[ply], ply );
541 UnMakeMove( tt, ptree->amove_hash[ply], ply );
544 mpv_pv[ipv].length++;
551 if ( is_out && mpv_pv[ipv].type != no_rep )
553 if ( (((ply-1) % 4) == 0) && (ply != 1) )
558 switch ( mpv_pv[ipv].type )
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;
570 if ( str != NULL ) { Out( " <%s>", str ); }
572 for ( ply--; ply >= 1; ply-- )
575 UnMakeMove( tt, mpv_pv[ipv].a[ply], ply );
578 if ( is_out ) { Out( "\n" ); }
581 if ( mpv_out ) { OutCsaShogi( "\n" ); }
586 mpv_sub_result( unsigned int move )
590 for ( i = 0; mpv_pv[i].length; i++ )
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 );
598 if ( mpv_pv[i].a[1] == move ) { break; }
601 for ( ; mpv_pv[i].length; i++ )
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 );
609 mpv_pv[i] = mpv_pv[i+1];
615 mpv_add_result( tree_t * restrict ptree, int value )
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 );
627 /* remove the weakest pv if all of slots are full */
628 if ( num == mpv_num )
630 for ( i = 0; mpv_pv[i].length; i++ )
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 );
638 if ( mpv_pv[i].depth == iteration_depth
639 && mpv_pv[i].a[0] == (unsigned int)(vmin+32768) ) { break; }
641 assert( i != mpv_num*2 );
642 assert( mpv_pv[i].length );
644 assert( i < mpv_num*2 );
645 assert( i < root_nmove*2 );
646 mpv_pv[i] = mpv_pv[i+1];
648 } while ( mpv_pv[i].length );
652 for ( i = 0; mpv_pv[i].length; i++ )
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 );
659 if ( mpv_pv[i].a[0] < (unsigned int)(value+32768) ) { break; }
663 pv.a[0] = (unsigned int)(value+32768);
665 assert( i < mpv_num*2 );
666 assert( i < root_nmove*2 );
671 } while ( pv.length );
673 if ( get_elapsed( &time ) < 0 ) { return -1; }
675 mpv_out( ptree, root_turn, time - time_start );
682 mpv_set_bound( int alpha )
684 int bound, num, value;
686 bound = alpha - mpv_width;
687 if ( bound < -score_bound ) { bound = -score_bound; }
689 value = mpv_find_min( &num );
690 assert( num <= mpv_num );
691 assert( num < root_nmove );
693 assert( -score_bound < value );
694 assert( value < score_bound );
695 if ( num == mpv_num && bound < value ) { bound = value; }
702 mpv_find_min( int *pnum )
705 unsigned int a[ MPV_MAX_PV+1 ], u, utemp;
709 for ( i = 0; mpv_pv[i].length; i++ )
711 assert( i < mpv_num*2 );
712 assert( i < root_nmove*2 );
713 assert( mpv_pv[i].depth <= iteration_depth );
715 if ( mpv_pv[i].depth == iteration_depth )
718 assert( -score_bound < (int)u-32768 );
719 assert( (int)u-32768 < score_bound );
721 for ( num = 0; u <= a[num]; num++ );
723 assert( num < mpv_num );
724 assert( num < root_nmove );
734 if ( pnum ) { *pnum = num; }
736 if ( num ) { return (int)a[num-1] - 32768; }