7 static void hist_add( tree_t * restrict ptree, int ply );
8 static void hist_good( tree_t * restrict ptree, unsigned int move, int ply,
10 static int detect_signals( tree_t * restrict ptree );
11 static int detect_rep( tree_t * restrict ptree, int ply, int turn );
12 static int rep_type( const tree_t * restrict ptree, int n, int i, int ply,
15 /* #define DBG_SEARCH */
16 #if defined(DBG_SEARCH)
17 # define DOut( ... ) if ( dbg_flag ) { out( __VA_ARGS__ ); }
23 search( tree_t * restrict ptree, int alpha, int beta, int turn, int depth,
24 int ply, unsigned int state_node )
28 if ( ! ptree->nsuc_check[ply] && depth < PLY_INC )
30 return search_quies( ptree, alpha, beta, turn, ply, 1 );
34 #if defined(DBG_SEARCH)
36 if ( iteration_depth == 3 && ply == 3
37 && ! strcmp( str_CSA_move(ptree->current_move[1]), "7776FU" )
38 && ! strcmp( str_CSA_move(ptree->current_move[2]), "3334FU" ) )
41 Out( "search start (d%.1f %" PRIu64 ")\n",
42 (double)depth / (double)PLY_INC, ptree->node_searched );
46 ptree->node_searched++;
48 if ( ply >= PLY_MAX-1 )
50 value = evaluate( ptree, ply, turn );
51 if ( alpha < value && value < beta ) { pv_close( ptree, ply, no_rep ); }
57 #if ! defined(MINIMUM)
58 if ( ! ( game_status & flag_learning ) )
61 /* check time and input */
63 if ( ! ptree->tlp_id )
65 if ( node_next_signal < ++node_last_check && detect_signals( ptree ) )
73 switch ( detect_rep( ptree, ply, turn ) )
75 case black_superi_rep:
76 value = turn ? -score_inferior : score_inferior;
78 && value < beta ) { pv_close( ptree, ply, black_superi_rep ); }
79 ptree->nsuperior_rep++;
83 case white_superi_rep:
84 value = turn ? score_inferior : -score_inferior;
86 && value < beta ) { pv_close( ptree, ply, white_superi_rep ); }
87 ptree->nsuperior_rep++;
92 if ( alpha < score_draw
93 && score_draw < beta ) { pv_close( ptree, ply, four_fold_rep );}
94 ptree->nfour_fold_rep++;
99 ptree->nperpetual_check++;
103 case perpetual_check2:
106 ptree->nperpetual_check++;
113 ptree->nreject_tried++;
114 if ( rejections_probe( ptree, turn, ply ) )
116 ptree->nreject_done++;
117 if ( alpha < score_inferior && score_inferior < beta )
119 pv_close( ptree, ply, turn ? white_superi_rep:black_superi_rep );
122 return score_inferior;
127 no repetitions. worst situation of this node is checkmate,
128 and the best is to force checkmate within 1-ply.
131 value = - ( score_mate1ply + 2 - ply );
142 value = score_mate1ply + 1 - ply;
143 if ( value <= alpha ) { return value; }
146 #if defined(NO_NULL_PRUNE)
147 state_node &= ~node_do_null;
150 ptree->amove_hash[ply] = 0;
151 #if ! defined(MINIMUM)
152 if ( ! ( game_status & flag_learning ) )
155 /* probe the transposition table */
156 int tv = hash_probe( ptree, ply, depth, turn, alpha, beta, state_node );
160 if ( alpha < HASH_VALUE )
162 if ( HASH_VALUE < beta ) { pv_close( ptree, ply, hash_hit ); }
164 MOVE_CURR = ptree->amove_hash[ply];
165 assert( is_move_valid( ptree, MOVE_CURR, turn ) );
171 MOVE_CURR = ptree->amove_hash[ply];
172 assert( beta <= HASH_VALUE );
173 assert( ! IsMove(MOVE_CURR)
174 || is_move_valid( ptree, MOVE_CURR, turn ) );
175 if ( beta == alpha_old + 1 ) { return HASH_VALUE; }
179 assert( HASH_VALUE <= alpha );
180 if ( beta == alpha_old + 1 ) { return HASH_VALUE; }
188 DOut( "\nhash cut passed" );
190 if ( depth >= REJEC_MIN_DEPTH ) { add_rejections( ptree, turn, ply ); }
193 if ( ! ptree->nsuc_check[ply] )
195 /* detect a move mates in 3-ply */
196 if ( ( state_node & node_do_mate )
197 && is_mate_in3ply( ptree, turn, ply ) )
199 value = score_mate1ply + 1 - ply;
201 hash_store( ptree, ply, depth, turn, value_exact, value,
205 && value < beta ) { pv_close( ptree, ply, mate_search ); }
207 if ( depth >= REJEC_MIN_DEPTH )
209 sub_rejections( ptree, turn, ply );
211 assert( is_move_valid( ptree, MOVE_CURR, turn ) );
216 /* null move pruning */
217 if ( 2*PLY_INC <= depth
218 && ( state_node & node_do_null )
219 && beta == alpha_old + 1
220 && beta <= evaluate( ptree, ply, turn ) )
222 int null_depth, nrep;
224 null_depth = NullDepth(depth);
225 nrep = root_nrep + ply - 1;
227 MOVE_CURR = MOVE_PASS;
228 ptree->move_last[ply] = ptree->move_last[ply-1];
229 ptree->stand_pat[ply+1] = (short)( - ptree->stand_pat[ply] );
230 ptree->nsuc_check[ply+1] = 0;
231 ptree->rep_board_list[nrep] = HASH_KEY;
232 ptree->rep_hand_list[nrep] = HAND_B;
233 ptree->null_pruning_tried++;
235 value = -search( ptree, -beta, 1-beta, Flip(turn), null_depth, ply+1,
236 node_do_mate | node_do_recap | node_do_futile );
239 if ( depth >= REJEC_MIN_DEPTH )
241 sub_rejections( ptree, turn, ply );
248 ptree->null_pruning_done++;
249 if ( null_depth < PLY_INC )
251 hash_store( ptree, ply, depth, turn, value_lower,
252 value, MOVE_NA, state_node );
254 if ( depth >= REJEC_MIN_DEPTH )
256 sub_rejections( ptree, turn, ply );
259 DOut( "\nnull move cut!\n" );
261 assert( ! IsMove(MOVE_CURR)
262 || is_move_valid( ptree, MOVE_CURR, turn ) );
266 DOut( "\nnull passed" );
268 if ( value == - ( score_mate1ply - ply ) )
270 state_node |= node_mate_threat;
275 /* recursive iterative-deepening for pv nodes */
276 if ( ! ptree->amove_hash[ply]
277 && depth >= 3*PLY_INC
278 && ( ( alpha == root_alpha && beta == root_beta )
279 || ( alpha == -root_beta && beta == -root_alpha ) ) )
281 if ( depth >= REJEC_MIN_DEPTH ) { sub_rejections( ptree, turn, ply ); }
282 value = search( ptree, -score_bound, beta, turn, depth-2*PLY_INC, ply,
283 node_do_mate | node_do_recap );
284 if ( SEARCH_ABORT ) { return 0; }
286 if ( beta <= value && IsMove(MOVE_CURR) )
288 ptree->amove_hash[ply] = MOVE_CURR;
290 else if ( value < beta && ply <= (int)ptree->pv[ply-1].length )
292 assert( -score_bound < value );
293 ptree->amove_hash[ply] = ptree->pv[ply-1].a[ply];
295 assert( ! ptree->amove_hash[ply]
296 || is_move_valid( ptree, ptree->amove_hash[ply], turn ) );
298 if ( depth >= REJEC_MIN_DEPTH ) { add_rejections( ptree, turn, ply ); }
302 int depth_reduced, first_move_expanded, new_depth, extension;
305 ptree->move_last[ply] = ptree->move_last[ply-1];
306 ptree->anext_move[ply].next_phase = next_move_hash;
307 ptree->hist_nmove[ply] = 0;
308 first_move_expanded = 0;
310 evaluate( ptree, ply, turn );
312 /* expand all of off-springs */
313 while ( ptree->nsuc_check[ply]
314 ? gen_next_evasion( ptree, ply, turn )
315 : gen_next_move( ptree, ply, turn ) ) {
317 DOut( "\nexpand %s (%" PRIu64 ")",
318 str_CSA_move(MOVE_CURR), ptree->node_searched );
320 ptree->nsuc_check[ply+1] = 0U;
321 state_node_new = ( node_do_mate | node_do_recap | node_do_null
326 hist_add( ptree, ply );
328 /* decision of extensions */
329 if ( turn ? is_move_check_w( ptree, MOVE_CURR )
330 : is_move_check_b( ptree, MOVE_CURR ) )
332 ptree->check_extension_done++;
333 ptree->nsuc_check[ply+1]
334 = (unsigned char)( ptree->nsuc_check[ply-1] + 1U );
335 extension = EXT_CHECK;
337 else if ( ptree->nsuc_check[ply]
338 && ptree->move_last[ply] - ptree->move_last[ply-1] == 1 )
340 ptree->onerp_extension_done++;
341 extension = EXT_ONEREP;
343 else if ( ! ptree->nsuc_check[ply]
344 && ( state_node & node_do_recap )
345 && I2To(MOVE_CURR) == I2To(MOVE_LAST)
346 && ( MOVE_CURR == ptree->anext_move[ply].move_cap1
347 || ( ( ptree->anext_move[ply].value_cap1
348 < ( ptree->anext_move[ply].value_cap2
350 && MOVE_CURR == ptree->anext_move[ply].move_cap2 ))
351 && ( UToCap(MOVE_LAST)
352 || ( I2IsPromote(MOVE_LAST)
353 && I2PieceMove(MOVE_LAST) != silver ) ) )
355 ptree->recap_extension_done++;
356 state_node_new = node_do_null | node_do_mate | node_do_futile;
357 if ( ! I2IsPromote(MOVE_CURR)
358 && I2PieceMove(MOVE_LAST) == UToCap(MOVE_LAST) )
360 extension = EXT_RECAP2;
362 else { extension = EXT_RECAP1; }
365 LimitExtension( extension, ply );
367 new_depth = depth + extension - PLY_INC;
370 if ( PLY_INC <= new_depth
371 && ! ( state_node & node_mate_threat )
372 && ! ptree->nsuc_check[ply]
373 && ! UToCap(MOVE_CURR)
374 && ! ( I2IsPromote(MOVE_CURR) && I2PieceMove(MOVE_CURR) != silver )
375 && ptree->amove_hash[ply] != MOVE_CURR
376 && ptree->killers[ply].no1 != MOVE_CURR
377 && ptree->killers[ply].no2 != MOVE_CURR )
379 unsigned int key = phash( MOVE_CURR, turn );
380 unsigned int good = ptree->hist_good[key] + 1;
381 unsigned int triedx8 = ( ptree->hist_tried[key] + 2 ) * 8U;
383 if ( beta != alpha_old + 1 ) {
385 if ( good * 62U < triedx8 ) { depth_reduced = PLY_INC * 4/2; }
386 else if ( good * 46U < triedx8 ) { depth_reduced = PLY_INC * 3/2; }
387 else if ( good * 34U < triedx8 ) { depth_reduced = PLY_INC * 2/2; }
388 else if ( good * 19U < triedx8 ) { depth_reduced = PLY_INC * 1/2; }
392 if ( good * 62U < triedx8 ) { depth_reduced = PLY_INC * 4/2; }
393 else if ( good * 46U < triedx8 ) { depth_reduced = PLY_INC * 3/2; }
394 else if ( good * 30U < triedx8 ) { depth_reduced = PLY_INC * 2/2; }
395 else if ( good * 12U < triedx8 ) { depth_reduced = PLY_INC * 1/2; }
398 new_depth -= depth_reduced;
401 /* futility pruning */
402 if ( ! ptree->nsuc_check[ply+1]
403 && ! ptree->nsuc_check[ply]
404 && new_depth < 3*PLY_INC )
406 int diff = estimate_score_diff( ptree, MOVE_CURR, turn );
409 if ( 2*PLY_INC <= new_depth ) { bound -= EFUTIL_MG2; }
410 else if ( 1*PLY_INC <= new_depth ) { bound -= EFUTIL_MG1; }
412 if ( eval_max_score( ptree, MOVE_CURR, ptree->stand_pat[ply],
413 turn, diff ) <= bound )
415 first_move_expanded += 1;
420 DOut( ", futil passed" );
422 MakeMove( turn, MOVE_CURR, ply );
423 if ( I2From(MOVE_CURR) < nsquare
424 && ! ptree->nsuc_check[ply]
427 UnMakeMove( turn, MOVE_CURR, ply );
431 if ( ! ptree->nsuc_check[ply+1] && ! ptree->nsuc_check[ply] )
433 evaluate( ptree, ply+1, Flip(turn) );
434 assert( ptree->stand_pat[ply] != score_bound );
436 /* futility pruning */
437 if ( ( new_depth < PLY_INC && - ptree->stand_pat[ply+1] <= alpha )
438 || ( new_depth < 2*PLY_INC
439 && - ptree->stand_pat[ply+1] <= alpha - EFUTIL_MG1 )
440 || ( new_depth < 3*PLY_INC
441 && - ptree->stand_pat[ply+1] <= alpha - EFUTIL_MG2 ) )
443 first_move_expanded += 1;
444 UnMakeMove( turn, MOVE_CURR, ply );
451 value = -search( ptree, -alpha-1, -alpha, Flip(turn), new_depth,
452 ply + 1, state_node_new );
453 if ( ! SEARCH_ABORT && alpha < value )
455 new_depth += depth_reduced;
456 value = -search( ptree, -beta, -alpha, Flip(turn), new_depth,
457 ply+1, state_node_new );
460 else if ( ! first_move_expanded )
462 value = -search( ptree, -beta, -alpha, Flip(turn), new_depth, ply+1,
466 value = -search( ptree, -alpha-1, -alpha, Flip(turn), new_depth,
467 ply + 1, state_node_new );
468 if ( ! SEARCH_ABORT && alpha < value && beta != alpha+1 )
470 value = -search( ptree, -beta, -alpha, Flip(turn), new_depth,
471 ply + 1, state_node_new );
477 UnMakeMove( turn, MOVE_CURR, ply );
478 if ( depth >= REJEC_MIN_DEPTH )
480 sub_rejections( ptree, turn, ply );
485 UnMakeMove( turn, MOVE_CURR, ply );
489 if ( new_depth < PLY_INC
490 && ! ptree->nsuc_check[ply+1]
491 && ptree->stand_pat[ply] != score_bound )
493 check_futile_score_quies( ptree, MOVE_CURR,
494 ptree->stand_pat[ply],
495 -ptree->stand_pat[ply+1], turn );
500 DOut( ", beta cut (%" PRIu64 ")\n", ptree->node_searched );
502 hash_store( ptree, ply, depth, turn, value_lower, value,
503 MOVE_CURR, state_node );
504 hist_good( ptree, MOVE_CURR, ply, depth, turn );
507 if ( ! first_move_expanded ) { ptree->fail_high_first++; }
509 if ( depth >= REJEC_MIN_DEPTH )
511 sub_rejections( ptree, turn, ply );
514 assert( is_move_valid( ptree, MOVE_CURR, turn ) );
518 if ( alpha < value ) { alpha = value; }
520 first_move_expanded += 1;
522 if ( ! ( ptree->nsuc_check[ply]
523 && ptree->move_last[ply] - ptree->move_last[ply-1] < 4 )
525 && ( ( iteration_depth < 11 && PLY_INC * 3 <= depth )
526 || PLY_INC * 4 <= depth ) )
528 ptree->tlp_beta = (short)beta;
529 ptree->tlp_best = (short)alpha;
530 ptree->tlp_depth = (unsigned char)depth;
531 ptree->tlp_state_node = (unsigned char)state_node;
532 ptree->tlp_turn = (char)turn;
533 ptree->tlp_ply = (char)ply;
534 if ( tlp_split( ptree ) )
536 if ( SEARCH_ABORT ) { return 0; }
537 value = ptree->tlp_best;
542 if ( depth >= REJEC_MIN_DEPTH )
544 sub_rejections( ptree, turn, ply );
547 hash_store( ptree, ply, depth, turn, value_lower,
548 value, MOVE_CURR, state_node );
550 hist_good( ptree, MOVE_CURR, ply, depth, turn );
554 assert( is_move_valid( ptree, MOVE_CURR, turn ) );
565 DOut( "\nall searched (%" PRIu64 ")\n", ptree->node_searched );
567 if ( depth >= REJEC_MIN_DEPTH ) { sub_rejections( ptree, turn, ply ); }
569 if ( ! first_move_expanded )
571 #if ! defined(MINIMUM)
572 if ( (int)I2From( ptree->current_move[ply-1] ) == Drop2From( pawn ) )
574 out_warning( "A checkmate by dropping pawn!!" );
577 if ( alpha != alpha_old ) { pv_close( ptree, ply, 0 ); }
582 if ( alpha <= - ( score_mate1ply + 2 - ply ) )
584 #if ! defined(MINIMUM)
585 out_warning( "A node returns a value lower than mate." );
587 if ( alpha_old < -score_inferior && -score_inferior < beta )
589 pv_close( ptree, ply, turn ? black_superi_rep : white_superi_rep );
592 return -score_inferior;
595 if ( alpha != alpha_old )
597 hist_good( ptree, ptree->pv[ply].a[ply], ply, depth, turn );
599 pv_copy( ptree, ply );
601 #if ! defined(MINIMUM)
602 if ( ! ( game_status & flag_learning ) )
605 hash_store( ptree, ply, depth, turn, value_exact, alpha,
606 ptree->pv[ply].a[ply], state_node );
610 hash_store( ptree, ply, depth, turn, value_upper, alpha, MOVE_NA,
621 tlp_search( tree_t * restrict ptree, int alpha, int beta, int turn,
622 int depth, int ply, unsigned int state_node )
624 int value, new_depth, extension, state_node_new, iret, depth_reduced;
627 assert( depth >= 3*PLY_INC );
632 lock( & ptree->tlp_ptree_parent->tlp_lock );
633 if ( ptree->nsuc_check[ply] )
635 iret = gen_next_evasion( ptree->tlp_ptree_parent, ply, turn );
637 else { iret = gen_next_move( ptree->tlp_ptree_parent, ply, turn ); }
638 MOVE_CURR = ptree->tlp_ptree_parent->current_move[ply];
639 hist_add( ptree->tlp_ptree_parent, ply );
640 unlock( & ptree->tlp_ptree_parent->tlp_lock );
641 if ( ! iret ) { break; }
643 ptree->nsuc_check[ply+1] = 0U;
644 state_node_new = ( node_do_mate | node_do_recap | node_do_null
649 if ( turn ? is_move_check_w( ptree, MOVE_CURR )
650 : is_move_check_b( ptree, MOVE_CURR ) )
652 ptree->check_extension_done++;
653 ptree->nsuc_check[ply+1]
654 = (unsigned char)( ptree->nsuc_check[ply-1] + 1U );
655 extension = EXT_CHECK;
657 else if ( ! ptree->nsuc_check[ply]
658 && ( state_node & node_do_recap )
659 && I2To(MOVE_CURR) == I2To(MOVE_LAST)
660 && ( MOVE_CURR == ptree->anext_move[ply].move_cap1
661 || ( ( ptree->anext_move[ply].value_cap1
662 < ptree->anext_move[ply].value_cap2 + MT_CAP_PAWN )
663 && MOVE_CURR == ptree->anext_move[ply].move_cap2 ) )
664 && ( UToCap(MOVE_LAST)
665 || ( I2IsPromote(MOVE_LAST)
666 && I2PieceMove(MOVE_LAST) != silver ) ) )
668 ptree->recap_extension_done++;
669 state_node_new = node_do_null | node_do_mate | node_do_futile;
670 if ( ! I2IsPromote(MOVE_CURR)
671 && I2PieceMove(MOVE_LAST) == UToCap(MOVE_LAST) )
673 extension = EXT_RECAP2;
675 else { extension = EXT_RECAP1; }
678 LimitExtension( extension, ply );
680 new_depth = depth + extension - PLY_INC;
683 if ( ! ( state_node & node_mate_threat )
684 && ! ptree->nsuc_check[ply]
685 && ! UToCap(MOVE_CURR)
686 && ! ( I2IsPromote(MOVE_CURR) && I2PieceMove(MOVE_CURR) != silver )
687 && ptree->killers[ply].no1 != MOVE_CURR
688 && ptree->killers[ply].no2 != MOVE_CURR )
690 unsigned int key = phash( MOVE_CURR, turn );
691 unsigned int good = ptree->hist_good[key] + 1;
692 unsigned int triedx8 = ( ptree->hist_tried[key] + 2 ) * 8U;
694 if ( beta != alpha_old + 1 ) {
696 if ( good * 62U < triedx8 ) { depth_reduced = PLY_INC * 4/2; }
697 else if ( good * 46U < triedx8 ) { depth_reduced = PLY_INC * 3/2; }
698 else if ( good * 34U < triedx8 ) { depth_reduced = PLY_INC * 2/2; }
699 else if ( good * 19U < triedx8 ) { depth_reduced = PLY_INC * 1/2; }
703 if ( good * 62U < triedx8 ) { depth_reduced = PLY_INC * 4/2; }
704 else if ( good * 46U < triedx8 ) { depth_reduced = PLY_INC * 3/2; }
705 else if ( good * 30U < triedx8 ) { depth_reduced = PLY_INC * 2/2; }
706 else if ( good * 12U < triedx8 ) { depth_reduced = PLY_INC * 1/2; }
709 new_depth -= depth_reduced;
712 if ( ! ptree->nsuc_check[ply+1]
713 && ! ptree->nsuc_check[ply]
714 && new_depth < 3*PLY_INC )
716 int diff = estimate_score_diff( ptree, MOVE_CURR, turn );
719 if ( 2*PLY_INC <= new_depth ) { bound -= EFUTIL_MG2; }
720 else if ( 1*PLY_INC <= new_depth ) { bound -= EFUTIL_MG1; }
722 if ( eval_max_score( ptree, MOVE_CURR, ptree->stand_pat[ply],
723 turn, diff ) <= bound )
729 MakeMove( turn, MOVE_CURR, ply );
730 if ( I2From(MOVE_CURR) < nsquare
731 && ! ptree->nsuc_check[ply]
734 UnMakeMove( turn, MOVE_CURR, ply );
738 if ( ! ptree->nsuc_check[ply+1] && ! ptree->nsuc_check[ply] )
740 evaluate( ptree, ply+1, Flip(turn) );
741 assert( ptree->stand_pat[ply] != score_bound );
743 /* futility pruning */
744 if ( ( new_depth < PLY_INC && - ptree->stand_pat[ply+1] <= alpha )
745 || ( new_depth < 2*PLY_INC
746 && - ptree->stand_pat[ply+1] <= alpha - EFUTIL_MG1 )
747 || ( new_depth < 3*PLY_INC
748 && - ptree->stand_pat[ply+1] <= alpha - EFUTIL_MG2 ) )
750 UnMakeMove( turn, MOVE_CURR, ply );
755 value = -search( ptree, -alpha-1, -alpha, Flip(turn), new_depth,
756 ply + 1, state_node_new );
757 if ( ! SEARCH_ABORT && alpha < value )
759 if ( ! depth_reduced && beta != alpha+1 )
761 value = -search( ptree, -beta, -alpha, Flip(turn), new_depth,
762 ply + 1, state_node_new );
764 else if ( depth_reduced )
766 new_depth += depth_reduced;
767 value = -search( ptree, -beta, -alpha, Flip(turn), new_depth,
768 ply + 1, state_node_new );
772 UnMakeMove( turn, MOVE_CURR, ply );
774 if ( SEARCH_ABORT ) { return 0; }
776 if ( alpha < value ) {
779 if ( beta <= value ) {
783 if ( ptree->tlp_abort )
790 for ( num = 0; num < tlp_max; num++ )
791 if ( ptree->tlp_ptree_parent->tlp_ptrees_sibling[num]
792 && num != ptree->tlp_id )
793 tlp_set_abort( ptree->tlp_ptree_parent->tlp_ptrees_sibling[num] );
808 detect_signals( tree_t * restrict ptree )
810 unsigned int tnow, telapsed, tpondered, tsearched, tcount, tlimit, tmax;
811 unsigned int tmax_limit_count, tlimit_count, u;
812 int iret, easy_time, last_value, stable;
814 if ( ! ( game_status & flag_nopeek ) )
816 /* peek input-buffer to find a command */
817 iret = next_cmdline( 0 );
820 game_status |= flag_search_error;
823 else if ( iret == -2 )
825 out_warning( "%s", str_error );
828 else if ( game_status & flag_quit ) { return 1; } /* EOF */
831 /* a command is found */
832 iret = procedure( ptree );
835 game_status |= flag_search_error;
839 else if ( iret == -2 )
841 out_warning( "%s", str_error );
845 else if ( iret == 1 ) { next_cmdline( 1 ); }
847 if ( game_status & ( flag_quit | flag_quit_ponder
848 | flag_move_now | flag_suspend ) )
855 /* check conditions of search-abortion, and obtain tnow and elapsed */
856 if ( node_limit <= ptree->node_searched ) { return 1; }
858 if ( get_elapsed( &tnow ) < 0 )
860 game_status |= flag_search_error;
864 /* keep my connection alive */
866 if ( sckt_csa != SCKT_NULL
867 && SEC_KEEP_ALIVE * 1000U < tnow - time_last_send
868 && sckt_out( sckt_csa, "\n" ) < 0 )
870 game_status |= flag_search_error;
876 if ( sckt_mnj != SCKT_NULL && 500U < tnow - time_last_send )
882 nodes = tlp_count_node( tlp_atree_work );
885 nodes = ptree->node_searched;
888 if ( sckt_out( sckt_mnj, "pid=%d n=%" PRIu64 "\n", mnj_posi_id,
891 game_status |= flag_search_error;
897 /* shortening the time limit by depth */
898 if ( time_limit != UINT_MAX
899 && sec_limit_depth < PLY_MAX
900 && iteration_depth + 10 >= (int)sec_limit_depth )
902 if ( iteration_depth + 0 >= (int)sec_limit_depth ) { u = 1U; }
903 else if ( iteration_depth + 1 >= (int)sec_limit_depth ) { u = 3U; }
904 else if ( iteration_depth + 2 >= (int)sec_limit_depth ) { u = 7U; }
905 else if ( iteration_depth + 3 >= (int)sec_limit_depth ) { u = 15U; }
906 else if ( iteration_depth + 4 >= (int)sec_limit_depth ) { u = 31U; }
907 else if ( iteration_depth + 5 >= (int)sec_limit_depth ) { u = 63U; }
908 else if ( iteration_depth + 6 >= (int)sec_limit_depth ) { u = 127U; }
909 else if ( iteration_depth + 7 >= (int)sec_limit_depth ) { u = 255U; }
910 else if ( iteration_depth + 8 >= (int)sec_limit_depth ) { u = 511U; }
911 else if ( iteration_depth + 9 >= (int)sec_limit_depth ) { u = 1023U; }
914 tlimit = u * 1000U + 1000U - time_response;
915 tmax = u * 5000U + 1000U - time_response;
916 if ( tlimit > time_limit ) { tlimit = time_limit; }
917 if ( tmax > time_max_limit ) { tmax = time_max_limit; }
921 tmax = time_max_limit;
924 telapsed = tnow - time_turn_start;
925 tpondered = time_turn_start - time_start;
926 tsearched = tnow - time_start;
928 last_value = root_turn ? -last_root_value : last_root_value;
929 stable = ( tlimit != UINT_MAX
930 && ( ( root_alpha == root_value && ! root_nfail_low )
931 || last_pv.type == four_fold_rep
933 && root_value + MT_CAP_DRAGON/8 >= last_value ) ) );
935 if ( tlimit != tmax )
938 tmax_limit_count = tmax;
939 tlimit_count = tlimit;
943 tmax_limit_count = tmax + tpondered;
944 tlimit_count = tlimit + tpondered;
947 if ( ! ( game_status & flag_pondering )
949 && telapsed > 2000U - time_response ) { return 1; }
951 if ( tcount > tmax ) { return 1; }
953 if ( stable && tcount > tlimit ) { return 1; }
956 && ( tmax_limit_count * 3U < ( time_last_search - time_start ) * 5U ) )
958 #if defined(DBG_EASY)
961 Out( " The search can be terminated "
962 "before it reaches time-limit.\n" );
963 easy_move = ptree->pv[0].a[1];
966 Out( " The search is terminated before it reaches time-limit.\n" );
972 && easy_abs > abs( last_value )
973 && easy_min < last_value - easy_value
974 && easy_max > last_value - easy_value )
976 u = tlimit_count / 5U;
977 if ( u < tpondered ) { ; }
978 else if ( u - tpondered < 2000U - time_response )
980 u = tpondered + 2000U - time_response;
983 u = ( ( u - tpondered ) / 1000U + 1U ) * 1000U
984 + tpondered - time_response;
989 Out( " The root move %s counted as easy!!\n",
990 str_CSA_move(root_move_list[0].move) );
991 #if defined(DBG_EASY)
992 easy_move = ptree->pv[0].a[1];
998 else if ( tsearched + 500U > u ) { easy_time = 1; }
1001 /* renew node_per_second */
1005 dn = (double)node_last_check * 1000.0;
1006 dd = (double)( tnow - time_last_check ) + 0.1;
1007 u = (unsigned int)( dn / dd );
1008 if ( node_per_second > u * 2U ) { node_per_second /= 2U; }
1009 else if ( node_per_second < u / 2U ) { node_per_second *= 2U; }
1010 else { node_per_second = u; }
1013 /* renew node_next_signal */
1014 if ( ! ( game_status & flag_pondering ) && root_nmove == 1 )
1016 u = 2000U - time_response;
1018 else { u = tlimit; }
1020 if ( ! ( game_status & ( flag_pondering | flag_puzzling ) )
1022 && u > tcount + 500U )
1024 node_next_signal = node_per_second / 4U;
1026 else { node_next_signal = node_per_second / 32U; }
1028 /* renew time_last_check and node_last_check */
1029 time_last_check = tnow;
1030 node_last_check = 0;
1038 is_move_check_b( const tree_t * restrict ptree, unsigned int move )
1040 const int from = (int)I2From(move);
1041 const int to = (int)I2To(move);
1042 int is_check, ipiece_move, idirec;
1047 if ( from >= nsquare ) { ipiece_move = From2Drop(from); }
1049 ipiece_move = (int)I2PieceMove(move);
1050 if ( I2IsPromote(move) ) { ipiece_move += promote; }
1052 idirec = (int)adirec[SQ_WKING][from];
1053 if ( idirec && idirec != (int)adirec[SQ_WKING][to]
1054 && is_pinned_on_white_king( ptree, from, idirec ) )
1061 switch ( ipiece_move )
1064 if ( BOARD[to-nfile] == -king ) { is_check = 1; }
1068 AttackBLance( bb, to );
1069 if ( BBContract( bb, BB_WKING ) ) { is_check = 1; }
1073 if ( BBContract(abb_b_knight_attacks[to],BB_WKING) ) { is_check = 1; }
1077 if ( BBContract(abb_b_silver_attacks[to],BB_WKING) ) { is_check = 1; }
1080 case gold: case pro_pawn:
1081 case pro_lance: case pro_knight:
1083 if ( BBContract(abb_b_gold_attacks[to],BB_WKING) ) { is_check = 1; }
1087 AttackBishop( bb, to );
1088 if ( BBContract( bb, BB_WKING ) ) { is_check = 1; }
1092 AttackRook( bb, to );
1093 if ( BBContract( bb, BB_WKING ) ) { is_check = 1; }
1100 AttackHorse( bb, to );
1101 if ( BBContract( bb, BB_WKING ) ) { is_check = 1; }
1105 assert( ipiece_move == dragon );
1106 AttackDragon( bb, to );
1107 if ( BBContract( bb, BB_WKING ) ) { is_check = 1; }
1117 is_move_check_w( const tree_t * restrict ptree, unsigned int move )
1119 const int from = (int)I2From(move);
1120 const int to = (int)I2To(move);
1121 int is_check, ipiece_move, idirec;
1126 if ( from >= nsquare ) { ipiece_move = From2Drop(from); }
1128 ipiece_move = (int)I2PieceMove(move);
1129 if ( I2IsPromote(move) ) { ipiece_move += promote; }
1131 idirec = (int)adirec[SQ_BKING][from];
1132 if ( idirec && idirec != (int)adirec[SQ_BKING][to]
1133 && is_pinned_on_black_king( ptree, from, idirec ) )
1140 switch ( ipiece_move )
1143 if ( BOARD[to+nfile] == king ) { is_check = 1; }
1147 AttackWLance( bb, to );
1148 if ( BBContract( bb, BB_BKING ) ) { is_check = 1; }
1152 if ( BBContract(abb_w_knight_attacks[to],BB_BKING) ) { is_check = 1; }
1156 if ( BBContract(abb_w_silver_attacks[to],BB_BKING) ) { is_check = 1; }
1159 case gold: case pro_pawn:
1160 case pro_lance: case pro_knight:
1162 if ( BBContract(abb_w_gold_attacks[to],BB_BKING) ) { is_check = 1; }
1166 AttackBishop( bb, to );
1167 if ( BBContract( bb, BB_BKING ) ) { is_check = 1; }
1171 AttackRook( bb, to );
1172 if ( BBContract( bb, BB_BKING ) ) { is_check = 1; }
1179 AttackHorse( bb, to );
1180 if ( BBContract( bb, BB_BKING ) ) { is_check = 1; }
1184 assert( ipiece_move == dragon );
1185 AttackDragon( bb, to );
1186 if ( BBContract( bb, BB_BKING ) ) { is_check = 1; }
1196 pv_close( tree_t * restrict ptree, int ply, int type )
1198 ptree->pv[ply-1].a[ply-1] = (ptree)->current_move[ply-1];
1199 ptree->pv[ply-1].length = (unsigned char)(ply-1);
1200 ptree->pv[ply-1].type = (unsigned char)type;
1201 ptree->pv[ply-1].depth = (unsigned char)iteration_depth;
1206 pv_copy( tree_t * restrict ptree, int ply )
1208 memcpy( &(ptree->pv[ply-1].a[ply]), &(ptree->pv[ply].a[ply]),
1209 ( ptree->pv[ply].length-ply+1 ) * sizeof(unsigned int) );
1210 ptree->pv[ply-1].type = ptree->pv[ply].type;
1211 ptree->pv[ply-1].length = ptree->pv[ply].length;
1212 ptree->pv[ply-1].depth = ptree->pv[ply].depth;
1213 ptree->pv[ply-1].a[ply-1] = ptree->current_move[ply-1];
1218 detect_rep( tree_t * restrict ptree, int ply, int turn )
1220 if ( ply < 4 ) { return detect_repetition( ptree, ply, turn, 2 ); }
1222 int n, i, imin, iret;
1224 n = root_nrep + ply - 1;
1225 imin = n - REP_MAX_PLY;
1226 if ( imin < 0 ) { imin = 0; }
1228 for ( i = n-2; i >= imin; i-- )
1229 if ( ptree->rep_board_list[i] == HASH_KEY )
1231 iret = rep_type( ptree, n, i, ply, turn );
1232 if ( iret ) { return iret; }
1241 rep_type( const tree_t * restrict ptree, int n, int i, int ply, int turn )
1243 const unsigned int hand1 = HAND_B;
1244 const unsigned int hand2 = ptree->rep_hand_list[i];
1250 if ( is_hand_eq_supe( hand2, hand1 ) ) { return white_superi_rep; }
1252 else if ( is_hand_eq_supe( hand1, hand2 ) ) { return black_superi_rep; }
1254 else if ( hand1 == hand2 )
1256 const int ncheck = (int)ptree->nsuc_check[ply];
1257 const int nchecked = (int)ptree->nsuc_check[ply-1];
1259 if ( ncheck * 2 - 2 >= n-i ) { return perpetual_check; }
1260 else if ( nchecked * 2 >= n-i ) { return perpetual_check2; }
1261 else { return four_fold_rep; }
1263 else if ( is_hand_eq_supe( hand1, hand2 ) ) { return black_superi_rep; }
1264 else if ( is_hand_eq_supe( hand2, hand1 ) ) { return white_superi_rep; }
1271 hist_add( tree_t * restrict ptree, int ply )
1273 if ( ptree->nsuc_check[ply] ) { return; }
1274 if ( UToCap(MOVE_CURR) ) { return; }
1275 if ( I2IsPromote(MOVE_CURR)
1276 && I2PieceMove(MOVE_CURR) != silver ) { return; }
1278 assert( ptree->hist_nmove[ply] < MAX_LEGAL_MOVES );
1279 ptree->hist_move[ply][ ptree->hist_nmove[ply]++ ] = MOVE_CURR;
1284 hist_good( tree_t * restrict ptree, unsigned int move_good, int ply,
1285 int depth, int turn )
1287 unsigned int key, move;
1288 int i, n, value, value_no1, value_no2;
1290 if ( ptree->nsuc_check[ply] ) { return; }
1292 value = p_value_ex[15+UToCap(move_good)];
1293 value_no1 = p_value_ex[15+BOARD[I2To(ptree->amove_killer[ply].no1)]];
1294 value_no2 = p_value_ex[15+BOARD[I2To(ptree->amove_killer[ply].no2)]];
1295 if ( move_good == ptree->anext_move[ply].move_cap1 )
1297 if ( ( ptree->anext_move[ply].phase_done & phase_killer1 )
1298 && UToFromToPromo(move_good) != ptree->amove_killer[ply].no1 )
1300 ptree->amove_killer[ply].no1_value
1301 = ptree->anext_move[ply].value_cap1 - value - 1;
1303 if ( ( ptree->anext_move[ply].phase_done & phase_killer2 )
1304 && UToFromToPromo(move_good) != ptree->amove_killer[ply].no2 )
1306 ptree->amove_killer[ply].no2_value
1307 = ptree->anext_move[ply].value_cap1 - value - 2;
1310 else if ( UToFromToPromo(move_good) == ptree->amove_killer[ply].no1 )
1312 if ( ( ptree->anext_move[ply].phase_done & phase_cap1 )
1313 && ( ptree->amove_killer[ply].no1_value + value
1314 < ptree->anext_move[ply].value_cap1 + 1 ) )
1316 ptree->amove_killer[ply].no1_value
1317 = ptree->anext_move[ply].value_cap1 - value + 1;
1319 if ( ( ptree->anext_move[ply].phase_done & phase_killer2 )
1320 && ( ptree->amove_killer[ply].no1_value + value
1321 < ptree->amove_killer[ply].no2_value + value_no2 + 1 ) )
1323 ptree->amove_killer[ply].no1_value
1324 = ptree->amove_killer[ply].no2_value + value_no2 - value + 1;
1327 else if ( UToFromToPromo(move_good) == ptree->amove_killer[ply].no2 )
1332 if ( ( ptree->anext_move[ply].phase_done & phase_cap1 )
1333 && ( ptree->amove_killer[ply].no2_value + value
1334 < ptree->anext_move[ply].value_cap1 + 1 ) )
1336 ptree->amove_killer[ply].no2_value
1337 = ptree->anext_move[ply].value_cap1 - value + 1;
1339 if ( ( ptree->anext_move[ply].phase_done & phase_killer1 )
1340 && ( ptree->amove_killer[ply].no2_value + value
1341 < ptree->amove_killer[ply].no1_value + value_no1 + 1 ) )
1343 ptree->amove_killer[ply].no2_value
1344 = ptree->amove_killer[ply].no1_value + value_no1 - value + 1;
1347 uswap = ptree->amove_killer[ply].no1;
1348 ptree->amove_killer[ply].no1 = ptree->amove_killer[ply].no2;
1349 ptree->amove_killer[ply].no2 = uswap;
1351 iswap = ptree->amove_killer[ply].no1_value;
1352 ptree->amove_killer[ply].no1_value = ptree->amove_killer[ply].no2_value;
1353 ptree->amove_killer[ply].no2_value = iswap;
1356 ptree->amove_killer[ply].no2 = ptree->amove_killer[ply].no1;
1357 ptree->amove_killer[ply].no1 = UToFromToPromo(move_good);
1359 if ( ptree->anext_move[ply].phase_done & phase_killer1 )
1361 i = swap( ptree, move_good, -MT_CAP_ROOK, MT_CAP_ROOK, turn );
1364 if ( ptree->amove_killer[ply].no1_value > i )
1366 ptree->amove_killer[ply].no1_value = i;
1369 ptree->amove_killer[ply].no2_value = ptree->amove_killer[ply].no1_value;
1370 ptree->amove_killer[ply].no1_value
1371 = ptree->anext_move[ply].value_cap1 - value + 1;
1375 if ( UToCap(move_good) ) { return; }
1376 if ( I2IsPromote(move_good)
1377 && I2PieceMove(move_good) != silver ) { return; }
1379 if ( ptree->killers[ply].no1 != move_good )
1381 ptree->killers[ply].no2 = ptree->killers[ply].no1;
1382 ptree->killers[ply].no1 = move_good;
1385 if ( depth < 1 ) { depth = 1; }
1387 n = ptree->hist_nmove[ply];
1388 for ( i = 0; i < n; i++ )
1390 move = ptree->hist_move[ply][i];
1391 assert( is_move_valid( ptree, move, turn ) );
1393 key = phash( move, turn );
1394 if ( ptree->hist_tried[key] >= HIST_MAX )
1396 ptree->hist_good[key] /= 2U;
1397 ptree->hist_tried[key] /= 2U;
1400 assert( ptree->hist_tried[key] < HIST_MAX );
1401 ptree->hist_tried[key]
1402 = (unsigned short)( (int)ptree->hist_tried[key] + depth );
1405 assert( is_move_valid( ptree, move_good, turn ) );
1406 key = phash( move_good, turn );
1408 assert( ptree->hist_good[key] < HIST_MAX );
1409 ptree->hist_good[key]
1410 = (unsigned short)( (int)ptree->hist_good[key] + depth );