8 static void CONV hist_add( tree_t * restrict ptree, int ply );
9 static void CONV hist_good( tree_t * restrict ptree, unsigned int move,
10 int ply, int depth, int turn );
11 static int CONV detect_rep( tree_t * restrict ptree, int ply, int turn );
12 static int CONV 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++;
115 no repetitions. worst situation of this node is checkmate,
116 and the best is to force checkmate within 1-ply.
119 value = - ( score_mate1ply + 2 - ply );
130 value = score_mate1ply + 1 - ply;
131 if ( value <= alpha ) { return value; }
134 ptree->amove_hash[ply] = 0;
136 #if ! defined(MINIMUM)
137 if ( ! ( game_status & flag_learning ) )
140 /* probe the transposition table */
141 switch ( hash_probe( ptree, ply, depth, turn, alpha, beta,
145 MOVE_CURR = ptree->amove_hash[ply];
146 assert( ! IsMove(MOVE_CURR)
147 || is_move_valid( ptree, MOVE_CURR, turn ) );
148 if ( ( state_node & node_do_hashcut ) && beta == alpha_old + 1 )
150 if ( alpha < HASH_VALUE
151 && HASH_VALUE < beta ) { pv_close( ptree, ply, hash_hit ); }
157 MOVE_CURR = ptree->amove_hash[ply];
158 assert( beta <= HASH_VALUE );
159 assert( ! IsMove(MOVE_CURR)
160 || is_move_valid( ptree, MOVE_CURR, turn ) );
161 if ( ( state_node & node_do_hashcut )
162 && beta == alpha_old + 1 ) { return HASH_VALUE; }
166 assert( HASH_VALUE <= alpha );
167 if ( ( state_node & node_do_hashcut )
168 && beta == alpha_old + 1 ) { return HASH_VALUE; }
173 DOut( "\nhash cut passed" );
176 if ( ! ptree->nsuc_check[ply] )
178 /* detect a move mates in 3-ply */
179 if ( ( state_node & node_do_mate )
180 && is_mate_in3ply( ptree, turn, ply ) )
182 value = score_mate1ply + 1 - ply;
184 hash_store( ptree, ply, depth, turn, value_exact, value,
188 && value < beta ) { pv_close( ptree, ply, mate_search ); }
190 assert( is_move_valid( ptree, MOVE_CURR, turn ) );
195 /* null move pruning */
196 if ( 2*PLY_INC <= depth
197 && ( state_node & node_do_null )
198 && beta == alpha_old + 1
199 && beta <= evaluate( ptree, ply, turn ) )
201 int null_depth, nrep;
203 null_depth = NullDepth(depth);
204 nrep = ptree->nrep + ply - 1;
206 MOVE_CURR = MOVE_PASS;
207 ptree->move_last[ply] = ptree->move_last[ply-1];
208 ptree->save_eval[ply+1] = - ptree->save_eval[ply];
209 ptree->nsuc_check[ply+1] = 0;
210 ptree->rep_board_list[nrep] = HASH_KEY;
211 ptree->rep_hand_list[nrep] = HAND_B;
212 ptree->null_pruning_tried++;
214 value = -search( ptree, -beta, 1-beta, Flip(turn), null_depth, ply+1,
215 node_do_mate | node_do_recap | node_do_futile
216 | node_do_recursion | node_do_hashcut );
217 if ( SEARCH_ABORT ) { return 0; }
221 ptree->null_pruning_done++;
222 if ( null_depth < PLY_INC )
224 hash_store( ptree, ply, depth, turn, value_lower,
225 value, MOVE_NA, state_node );
228 DOut( "\nnull move cut!\n" );
230 assert( ! IsMove(MOVE_CURR)
231 || is_move_valid( ptree, MOVE_CURR, turn ) );
235 DOut( "\nnull passed" );
237 if ( value == - ( score_mate1ply - ply ) )
239 state_node |= node_mate_threat;
244 /* recursive iterative-deepening */
245 if ( ! ptree->amove_hash[ply] && RecursionThreshold <= depth
246 && ( state_node & node_do_recursion ) )
248 int new_depth = RecursionDepth(depth);
249 int state_node_new = state_node & ~( node_do_mate | node_do_null
252 value = search( ptree, alpha, beta, turn, new_depth, ply,
254 if ( SEARCH_ABORT ) { return 0; }
256 if ( beta <= value ) { ptree->amove_hash[ply] = MOVE_CURR; }
257 else if ( alpha < value )
259 assert( ply <= (int)ptree->pv[ply-1].length );
260 assert( -score_bound < value );
261 ptree->amove_hash[ply] = ptree->pv[ply-1].a[ply];
264 assert( ! ptree->amove_hash[ply]
265 || is_move_valid( ptree, ptree->amove_hash[ply], turn ) );
270 int depth_reduced, first_move_expanded, new_depth, extension;
273 ptree->move_last[ply] = ptree->move_last[ply-1];
274 ptree->anext_move[ply].next_phase = next_move_hash;
275 ptree->hist_nmove[ply] = 0;
276 first_move_expanded = 0;
278 evaluate( ptree, ply, turn );
280 /* expand all of off-springs */
281 while ( ptree->nsuc_check[ply]
282 ? gen_next_evasion( ptree, ply, turn )
283 : gen_next_move( ptree, ply, turn ) ) {
285 DOut( "\nexpand %s (%" PRIu64 ")",
286 str_CSA_move(MOVE_CURR), ptree->node_searched );
288 ptree->nsuc_check[ply+1] = 0U;
289 state_node_new = ( node_do_mate | node_do_recap | node_do_null
290 | node_do_futile | node_do_recursion
295 hist_add( ptree, ply );
297 /* decision of extensions */
298 if ( IsMoveCheck( ptree, turn, MOVE_CURR ) )
300 ptree->check_extension_done++;
301 ptree->nsuc_check[ply+1]
302 = (unsigned char)( ptree->nsuc_check[ply-1] + 1U );
303 extension = EXT_CHECK;
305 else if ( ptree->nsuc_check[ply]
306 && ptree->move_last[ply] - ptree->move_last[ply-1] == 1 )
308 ptree->onerp_extension_done++;
309 extension = EXT_ONEREP;
311 else if ( ! ptree->nsuc_check[ply]
312 && ( state_node & node_do_recap )
313 && I2To(MOVE_CURR) == I2To(MOVE_LAST)
314 && ( MOVE_CURR == ptree->anext_move[ply].move_cap1
315 || ( ( ptree->anext_move[ply].value_cap1
316 < ( ptree->anext_move[ply].value_cap2
318 && MOVE_CURR == ptree->anext_move[ply].move_cap2 ))
319 && ( UToCap(MOVE_LAST)
320 || ( I2IsPromote(MOVE_LAST)
321 && I2PieceMove(MOVE_LAST) != silver ) ) )
323 ptree->recap_extension_done++;
324 state_node_new = ( node_do_null | node_do_mate | node_do_futile
325 | node_do_recursion | node_do_hashcut );
326 if ( ! I2IsPromote(MOVE_CURR)
327 && I2PieceMove(MOVE_LAST) == UToCap(MOVE_LAST) )
329 extension = EXT_RECAP2;
331 else { extension = EXT_RECAP1; }
334 LimitExtension( extension, ply );
336 new_depth = depth + extension - PLY_INC;
339 if ( PLY_INC <= new_depth
340 && first_move_expanded
341 && ! ( state_node & node_mate_threat )
342 && ! ptree->nsuc_check[ply]
343 && ! UToCap(MOVE_CURR)
344 && ! ( I2IsPromote(MOVE_CURR) && I2PieceMove(MOVE_CURR) != silver )
345 && ptree->amove_hash[ply] != MOVE_CURR
346 && ptree->killers[ply].no1 != MOVE_CURR
347 && ptree->killers[ply].no2 != MOVE_CURR )
349 unsigned int key = phash( MOVE_CURR, turn );
350 unsigned int good = ptree->hist_good[key] + 1;
351 unsigned int triedx8 = ( ptree->hist_tried[key] + 2 ) * 8U;
353 if ( beta != alpha_old + 1 ) {
355 if ( good *160U < triedx8 ) { depth_reduced = PLY_INC * 3/2; }
356 else if ( good * 50U < triedx8 ) { depth_reduced = PLY_INC * 2/2; }
357 else if ( good * 19U < triedx8 ) { depth_reduced = PLY_INC * 1/2; }
361 if ( good * 75U < triedx8 ) { depth_reduced = PLY_INC * 4/2; }
362 else if ( good * 46U < triedx8 ) { depth_reduced = PLY_INC * 3/2; }
363 else if ( good * 30U < triedx8 ) { depth_reduced = PLY_INC * 2/2; }
364 else if ( good * 12U < triedx8 ) { depth_reduced = PLY_INC * 1/2; }
367 new_depth -= depth_reduced;
370 /* futility pruning */
371 if ( ! ptree->nsuc_check[ply+1]
372 && ! ptree->nsuc_check[ply]
373 && new_depth < 3*PLY_INC )
375 int diff = estimate_score_diff( ptree, MOVE_CURR, turn );
378 if ( 2*PLY_INC <= new_depth ) { bound -= EFUTIL_MG2; }
379 else if ( 1*PLY_INC <= new_depth ) { bound -= EFUTIL_MG1; }
381 if ( eval_max_score( ptree, MOVE_CURR, ptree->save_eval[ply],
382 turn, diff ) <= bound )
384 first_move_expanded += 1;
389 DOut( ", futil passed" );
391 if ( new_depth < 2*PLY_INC
392 && ! ptree->nsuc_check[ply]
393 && ! ptree->nsuc_check[ply+1]
394 && ! UToCap(MOVE_CURR)
395 && ! ( I2IsPromote(MOVE_CURR)
396 && I2PieceMove(MOVE_CURR) != silver )
397 && ptree->amove_hash[ply] != MOVE_CURR
398 && ptree->killers[ply].no1 != MOVE_CURR
399 && ptree->killers[ply].no2 != MOVE_CURR
400 && beta == alpha_old + 1
401 && swap( ptree, MOVE_CURR, -1, 0, turn ) <= -1 )
403 first_move_expanded += 1;
407 MakeMove( turn, MOVE_CURR, ply );
408 if ( I2From(MOVE_CURR) < nsquare
409 && ! ptree->nsuc_check[ply]
412 UnMakeMove( turn, MOVE_CURR, ply );
416 if ( ! ptree->nsuc_check[ply+1] && ! ptree->nsuc_check[ply] )
418 int score = -evaluate( ptree, ply+1, Flip(turn) );
419 assert( ptree->save_eval[ply] != INT_MAX );
421 /* futility pruning */
422 if ( ( new_depth < PLY_INC && score <= alpha )
423 || ( new_depth < 2*PLY_INC && score <= alpha - EFUTIL_MG1 )
424 || ( new_depth < 3*PLY_INC && score <= alpha - EFUTIL_MG2 ) )
426 first_move_expanded += 1;
427 UnMakeMove( turn, MOVE_CURR, ply );
432 if ( ! first_move_expanded )
434 value = -search( ptree, -beta, -alpha, Flip(turn), new_depth, ply+1,
438 value = -search( ptree, -alpha-1, -alpha, Flip(turn), new_depth,
439 ply + 1, state_node_new );
440 if ( ! SEARCH_ABORT && alpha < value && depth_reduced )
442 new_depth += depth_reduced;
443 value = -search( ptree, -alpha-1, -alpha, Flip(turn), new_depth,
444 ply+1, state_node_new );
446 if ( ! SEARCH_ABORT && alpha < value && beta != alpha+1 )
448 value = -search( ptree, -beta, -alpha, Flip(turn), new_depth,
449 ply + 1, state_node_new );
454 UnMakeMove( turn, MOVE_CURR, ply );
458 UnMakeMove( turn, MOVE_CURR, ply );
462 if ( new_depth < PLY_INC
463 && ! ptree->nsuc_check[ply+1]
464 && ptree->save_eval[ply] != INT_MAX )
466 check_futile_score_quies( ptree, MOVE_CURR,
467 ptree->save_eval[ply],
468 -ptree->save_eval[ply+1], turn );
473 DOut( ", beta cut (%" PRIu64 ")\n", ptree->node_searched );
475 hash_store( ptree, ply, depth, turn, value_lower, value,
476 MOVE_CURR, state_node );
477 hist_good( ptree, MOVE_CURR, ply, depth, turn );
480 if ( ! first_move_expanded ) { ptree->fail_high_first++; }
482 assert( is_move_valid( ptree, MOVE_CURR, turn ) );
486 if ( alpha < value ) { alpha = value; }
488 first_move_expanded += 1;
490 if ( ! ( ptree->nsuc_check[ply]
491 && ptree->move_last[ply] - ptree->move_last[ply-1] < 4 )
493 && ( ( iteration_depth < 11 && PLY_INC * 3 <= depth )
494 || PLY_INC * 4 <= depth ) )
496 ptree->tlp_beta = (short)beta;
497 ptree->tlp_best = (short)alpha;
498 ptree->tlp_depth = (unsigned char)depth;
499 ptree->tlp_state_node = (unsigned char)state_node;
500 ptree->tlp_turn = (char)turn;
501 ptree->tlp_ply = (char)ply;
502 if ( tlp_split( ptree ) )
504 if ( SEARCH_ABORT ) { return 0; }
505 value = ptree->tlp_best;
510 hash_store( ptree, ply, depth, turn, value_lower,
511 value, MOVE_CURR, state_node );
513 hist_good( ptree, MOVE_CURR, ply, depth, turn );
517 assert( is_move_valid( ptree, MOVE_CURR, turn ) );
528 DOut( "\nall searched (%" PRIu64 ")\n", ptree->node_searched );
530 if ( ! first_move_expanded )
532 #if ! defined(MINIMUM)
533 if ( (int)I2From( ptree->current_move[ply-1] ) == Drop2From( pawn ) )
535 out_warning( "A checkmate by dropping pawn!!" );
538 if ( alpha != alpha_old ) { pv_close( ptree, ply, 0 ); }
543 if ( alpha <= - ( score_mate1ply + 2 - ply ) )
545 #if ! defined(MINIMUM)
546 out_warning( "A node returns a value lower than mate." );
548 if ( alpha_old < -score_inferior && -score_inferior < beta )
550 pv_close( ptree, ply, turn ? black_superi_rep : white_superi_rep );
553 return -score_inferior;
556 if ( alpha != alpha_old )
558 hist_good( ptree, ptree->pv[ply].a[ply], ply, depth, turn );
560 pv_copy( ptree, ply );
562 #if ! defined(MINIMUM)
563 if ( ! ( game_status & flag_learning ) )
566 hash_store( ptree, ply, depth, turn, value_exact, alpha,
567 ptree->pv[ply].a[ply], state_node );
571 hash_store( ptree, ply, depth, turn, value_upper, alpha, MOVE_NA,
582 tlp_search( tree_t * restrict ptree, int alpha, int beta, int turn,
583 int depth, int ply, unsigned int state_node )
585 int value, new_depth, extension, state_node_new, iret, depth_reduced;
588 assert( depth >= 3*PLY_INC );
593 lock( & ptree->tlp_ptree_parent->tlp_lock );
594 if ( ptree->tlp_abort )
596 unlock( & ptree->tlp_ptree_parent->tlp_lock );
599 if ( ptree->nsuc_check[ply] )
601 iret = gen_next_evasion( ptree->tlp_ptree_parent, ply, turn );
603 else { iret = gen_next_move( ptree->tlp_ptree_parent, ply, turn ); }
605 MOVE_CURR = ptree->tlp_ptree_parent->current_move[ply];
606 hist_add( ptree->tlp_ptree_parent, ply );
607 unlock( & ptree->tlp_ptree_parent->tlp_lock );
608 if ( ! iret ) { break; }
610 ptree->nsuc_check[ply+1] = 0U;
611 state_node_new = ( node_do_mate | node_do_recap | node_do_null
612 | node_do_futile | node_do_recursion
617 if ( IsMoveCheck( ptree, turn, MOVE_CURR ) )
619 ptree->check_extension_done++;
620 ptree->nsuc_check[ply+1]
621 = (unsigned char)( ptree->nsuc_check[ply-1] + 1U );
622 extension = EXT_CHECK;
624 else if ( ! ptree->nsuc_check[ply]
625 && ( state_node & node_do_recap )
626 && I2To(MOVE_CURR) == I2To(MOVE_LAST)
627 && ( MOVE_CURR == ptree->anext_move[ply].move_cap1
628 || ( ( ptree->anext_move[ply].value_cap1
629 < ptree->anext_move[ply].value_cap2 + MT_CAP_PAWN )
630 && MOVE_CURR == ptree->anext_move[ply].move_cap2 ) )
631 && ( UToCap(MOVE_LAST)
632 || ( I2IsPromote(MOVE_LAST)
633 && I2PieceMove(MOVE_LAST) != silver ) ) )
635 ptree->recap_extension_done++;
636 state_node_new = ( node_do_null | node_do_mate | node_do_futile
637 | node_do_recursion | node_do_hashcut );
638 if ( ! I2IsPromote(MOVE_CURR)
639 && I2PieceMove(MOVE_LAST) == UToCap(MOVE_LAST) )
641 extension = EXT_RECAP2;
643 else { extension = EXT_RECAP1; }
646 LimitExtension( extension, ply );
648 new_depth = depth + extension - PLY_INC;
651 if ( ! ( state_node & node_mate_threat )
652 && ! ptree->nsuc_check[ply]
653 && ! UToCap(MOVE_CURR)
654 && ! ( I2IsPromote(MOVE_CURR) && I2PieceMove(MOVE_CURR) != silver )
655 && ptree->killers[ply].no1 != MOVE_CURR
656 && ptree->killers[ply].no2 != MOVE_CURR )
658 unsigned int key = phash( MOVE_CURR, turn );
659 unsigned int good = ptree->hist_good[key] + 1;
660 unsigned int triedx8 = ( ptree->hist_tried[key] + 2 ) * 8U;
662 if ( beta != alpha_old + 1 ) {
664 if ( good *160U < triedx8 ) { depth_reduced = PLY_INC * 3/2; }
665 else if ( good * 50U < triedx8 ) { depth_reduced = PLY_INC * 2/2; }
666 else if ( good * 19U < triedx8 ) { depth_reduced = PLY_INC * 1/2; }
670 if ( good * 75U < triedx8 ) { depth_reduced = PLY_INC * 4/2; }
671 else if ( good * 46U < triedx8 ) { depth_reduced = PLY_INC * 3/2; }
672 else if ( good * 30U < triedx8 ) { depth_reduced = PLY_INC * 2/2; }
673 else if ( good * 12U < triedx8 ) { depth_reduced = PLY_INC * 1/2; }
676 new_depth -= depth_reduced;
679 if ( ! ptree->nsuc_check[ply+1]
680 && ! ptree->nsuc_check[ply]
681 && new_depth < 3*PLY_INC )
683 int diff = estimate_score_diff( ptree, MOVE_CURR, turn );
686 if ( 2*PLY_INC <= new_depth ) { bound -= EFUTIL_MG2; }
687 else if ( 1*PLY_INC <= new_depth ) { bound -= EFUTIL_MG1; }
689 if ( eval_max_score( ptree, MOVE_CURR, ptree->save_eval[ply],
690 turn, diff ) <= bound )
696 MakeMove( turn, MOVE_CURR, ply );
697 if ( I2From(MOVE_CURR) < nsquare
698 && ! ptree->nsuc_check[ply]
701 UnMakeMove( turn, MOVE_CURR, ply );
705 if ( ! ptree->nsuc_check[ply+1] && ! ptree->nsuc_check[ply] )
707 int score = -evaluate( ptree, ply+1, Flip(turn) );
708 assert( ptree->save_eval[ply] != INT_MAX );
710 /* futility pruning */
711 if ( ( new_depth < PLY_INC && score <= alpha )
712 || ( new_depth < 2*PLY_INC && score <= alpha - EFUTIL_MG1 )
713 || ( new_depth < 3*PLY_INC && score <= alpha - EFUTIL_MG2 ) )
715 UnMakeMove( turn, MOVE_CURR, ply );
720 value = -search( ptree, -alpha-1, -alpha, Flip(turn), new_depth,
721 ply + 1, state_node_new );
722 if ( ! SEARCH_ABORT && alpha < value )
724 if ( ! depth_reduced && beta != alpha+1 )
726 value = -search( ptree, -beta, -alpha, Flip(turn), new_depth,
727 ply + 1, state_node_new );
729 else if ( depth_reduced )
731 new_depth += depth_reduced;
732 value = -search( ptree, -beta, -alpha, Flip(turn), new_depth,
733 ply + 1, state_node_new );
737 UnMakeMove( turn, MOVE_CURR, ply );
739 if ( SEARCH_ABORT ) { return 0; }
741 if ( alpha < value ) {
744 if ( beta <= value ) {
748 if ( ptree->tlp_abort )
755 for ( num = 0; num < tlp_max; num++ )
756 if ( ptree->tlp_ptree_parent->tlp_ptrees_sibling[num]
757 && num != ptree->tlp_id )
758 tlp_set_abort( ptree->tlp_ptree_parent->tlp_ptrees_sibling[num] );
772 pv_close( tree_t * restrict ptree, int ply, int type )
774 ptree->pv[ply-1].a[ply-1] = (ptree)->current_move[ply-1];
775 ptree->pv[ply-1].length = (unsigned char)(ply-1);
776 ptree->pv[ply-1].type = (unsigned char)type;
777 ptree->pv[ply-1].depth = (unsigned char)iteration_depth;
781 pv_copy( tree_t * restrict ptree, int ply )
783 memcpy( &(ptree->pv[ply-1].a[ply]), &(ptree->pv[ply].a[ply]),
784 ( ptree->pv[ply].length-ply+1 ) * sizeof(unsigned int) );
785 ptree->pv[ply-1].type = ptree->pv[ply].type;
786 ptree->pv[ply-1].length = ptree->pv[ply].length;
787 ptree->pv[ply-1].depth = ptree->pv[ply].depth;
788 ptree->pv[ply-1].a[ply-1] = ptree->current_move[ply-1];
793 detect_signals( tree_t * restrict ptree )
795 unsigned int tnow, telapsed, tpondered, tsearched, tcount, tlimit, tmax;
796 unsigned int tlimit_count, u;
797 int iret, easy_time, last_value, stable;
799 #if defined(DFPN_CLIENT)
800 int is_first_move_skipped = 0;
803 #if defined(DFPN_CLIENT)
804 /* probe results from DFPN server */
805 if ( dfpn_client_flag_read )
807 dfpn_client_check_results();
808 if ( dfpn_client_move_unlocked != MOVE_NA ) { return 1; }
809 if ( root_move_list[root_index].dfpn_cresult == dfpn_client_win )
811 is_first_move_skipped = 1;
817 if ( ! ( game_status & flag_nopeek ) )
819 /* peek input-buffer to find a command */
820 iret = next_cmdline( 0 );
823 game_status |= flag_search_error;
826 else if ( iret == -2 )
828 out_warning( "%s", str_error );
831 else if ( game_status & flag_quit ) { return 1; } /* EOF */
834 /* a command is found */
835 iret = procedure( ptree );
838 game_status |= flag_search_error;
842 else if ( iret == -2 )
844 out_warning( "%s", str_error );
848 else if ( iret == 1 ) { next_cmdline( 1 ); }
850 if ( game_status & ( flag_quit | flag_quit_ponder
851 | flag_move_now | flag_suspend ) )
858 /* check conditions of search-abortion, and obtain tnow and elapsed */
859 if ( node_limit <= ptree->node_searched ) { return 1; }
861 if ( get_elapsed( &tnow ) < 0 )
863 game_status |= flag_search_error;
867 /* keep my connection alive */
869 if ( sckt_csa != SCKT_NULL
870 && SEC_KEEP_ALIVE * 1000U < tnow - time_last_send
871 && sckt_out( sckt_csa, "\n" ) < 0 )
873 game_status |= flag_search_error;
879 if ( usi_mode != usi_off && 1000U + usi_time_out_last < tnow )
886 nodes = tlp_count_node( tlp_atree_work );
889 nodes = ptree->node_searched;
892 dnps = (double)nodes * 1000.0 / (double)( tnow - time_turn_start );
893 USIOut( "info time %u nodes %" PRIu64 " nps %d\n",
894 tnow, nodes, (unsigned int)dnps );
896 usi_time_out_last = tnow;
901 if ( sckt_mnj != SCKT_NULL && 500U + time_last_send < tnow )
907 nodes = tlp_count_node( tlp_atree_work );
910 nodes = ptree->node_searched;
913 MnjOut( "pid=%d n=%" PRIu64 "\n", mnj_posi_id, nodes );
917 /* shortening the time limit by depth */
918 if ( time_limit != UINT_MAX
919 && sec_limit_depth < PLY_MAX
920 && iteration_depth + 10 >= (int)sec_limit_depth )
922 if ( iteration_depth + 0 >= (int)sec_limit_depth ) { u = 1U; }
923 else if ( iteration_depth + 1 >= (int)sec_limit_depth ) { u = 3U; }
924 else if ( iteration_depth + 2 >= (int)sec_limit_depth ) { u = 7U; }
925 else if ( iteration_depth + 3 >= (int)sec_limit_depth ) { u = 15U; }
926 else if ( iteration_depth + 4 >= (int)sec_limit_depth ) { u = 31U; }
927 else if ( iteration_depth + 5 >= (int)sec_limit_depth ) { u = 63U; }
928 else if ( iteration_depth + 6 >= (int)sec_limit_depth ) { u = 127U; }
929 else if ( iteration_depth + 7 >= (int)sec_limit_depth ) { u = 255U; }
930 else if ( iteration_depth + 8 >= (int)sec_limit_depth ) { u = 511U; }
931 else if ( iteration_depth + 9 >= (int)sec_limit_depth ) { u = 1023U; }
934 tlimit = u * 1000U + 1000U - time_response;
935 tmax = u * 5000U + 1000U - time_response;
936 if ( tlimit > time_limit ) { tlimit = time_limit; }
937 if ( tmax > time_max_limit ) { tmax = time_max_limit; }
941 tmax = time_max_limit;
944 telapsed = tnow - time_turn_start;
945 tpondered = time_turn_start - time_start;
946 tsearched = tnow - time_start;
948 last_value = root_turn ? -last_root_value : last_root_value;
949 stable = ( tlimit != UINT_MAX
950 && ( ( root_alpha == root_value && ! root_nfail_low )
951 || last_pv.type == four_fold_rep
953 && root_value + MT_CAP_DRAGON/8 >= last_value ) ) );
955 if ( tlimit != tmax )
958 tlimit_count = tlimit;
962 tlimit_count = tlimit + tpondered;
965 if ( ! ( game_status & flag_pondering )
967 && telapsed > 2000U - time_response ) { return 1; }
969 if ( tcount > tmax ) { return 1; }
971 if ( stable && tcount > tlimit ) { return 1; }
974 && easy_abs > abs( last_value )
975 && easy_min < last_value - easy_value
976 && easy_max > last_value - easy_value )
978 u = tlimit_count / 5U;
979 if ( u < tpondered ) { ; }
980 else if ( u - tpondered < 2000U - time_response )
982 u = tpondered + 2000U - time_response;
985 u = ( ( u - tpondered ) / 1000U + 1U ) * 1000U
986 + tpondered - time_response;
991 Out( " The root move %s counted as easy!!\n",
992 str_CSA_move(root_move_list[0].move) );
993 #if defined(DBG_EASY)
994 easy_move = ptree->pv[0].a[1];
1000 else if ( tsearched + 500U > u ) { easy_time = 1; }
1003 /* update node_per_second */
1007 dn = (double)node_last_check * 1000.0;
1008 dd = (double)( tnow - time_last_check ) + 0.1;
1009 u = (unsigned int)( dn / dd );
1010 if ( node_per_second > u * 2U ) { node_per_second /= 2U; }
1011 else if ( node_per_second < u / 2U ) { node_per_second *= 2U; }
1012 else { node_per_second = u; }
1015 /* update node_next_signal */
1016 if ( ! ( game_status & flag_pondering ) && root_nmove == 1 )
1018 u = 2000U - time_response;
1020 else { u = tlimit; }
1022 if ( ! ( game_status & ( flag_pondering | flag_puzzling ) )
1024 && u > tcount + 500U )
1026 node_next_signal = node_per_second / 4U;
1028 else { node_next_signal = node_per_second / 32U; }
1030 /* update time_last_check and node_last_check */
1031 time_last_check = tnow;
1032 node_last_check = 0;
1035 #if defined(DFPN_CLIENT)
1036 if ( is_first_move_skipped )
1038 game_status |= flag_skip_root_move;
1048 detect_rep( tree_t * restrict ptree, int ply, int turn )
1050 if ( ply < 4 ) { return detect_repetition( ptree, ply, turn, 2 ); }
1052 int n, i, imin, iret;
1054 n = ptree->nrep + ply - 1;
1055 imin = n - REP_MAX_PLY;
1056 if ( imin < 0 ) { imin = 0; }
1058 for ( i = n-2; i >= imin; i-- )
1059 if ( ptree->rep_board_list[i] == HASH_KEY )
1061 iret = rep_type( ptree, n, i, ply, turn );
1062 if ( iret ) { return iret; }
1071 rep_type( const tree_t * restrict ptree, int n, int i, int ply, int turn )
1073 const unsigned int hand1 = HAND_B;
1074 const unsigned int hand2 = ptree->rep_hand_list[i];
1080 if ( is_hand_eq_supe( hand2, hand1 ) ) { return white_superi_rep; }
1082 else if ( is_hand_eq_supe( hand1, hand2 ) ) { return black_superi_rep; }
1084 else if ( hand1 == hand2 )
1086 const int ncheck = (int)ptree->nsuc_check[ply];
1087 const int nchecked = (int)ptree->nsuc_check[ply-1];
1089 if ( ncheck * 2 - 2 >= n-i ) { return perpetual_check; }
1090 else if ( nchecked * 2 >= n-i ) { return perpetual_check2; }
1091 else { return four_fold_rep; }
1093 else if ( is_hand_eq_supe( hand1, hand2 ) ) { return black_superi_rep; }
1094 else if ( is_hand_eq_supe( hand2, hand1 ) ) { return white_superi_rep; }
1101 hist_add( tree_t * restrict ptree, int ply )
1103 if ( ptree->nsuc_check[ply] ) { return; }
1104 if ( UToCap(MOVE_CURR) ) { return; }
1105 if ( I2IsPromote(MOVE_CURR)
1106 && I2PieceMove(MOVE_CURR) != silver ) { return; }
1108 assert( ptree->hist_nmove[ply] < MAX_LEGAL_MOVES );
1109 ptree->hist_move[ply][ ptree->hist_nmove[ply]++ ] = MOVE_CURR;
1114 hist_good( tree_t * restrict ptree, unsigned int move_good, int ply,
1115 int depth, int turn )
1117 unsigned int key, move;
1118 int i, n, value, value_no1, value_no2;
1120 if ( ptree->nsuc_check[ply] ) { return; }
1122 value = p_value_ex[15+UToCap(move_good)];
1123 value_no1 = p_value_ex[15+BOARD[I2To(ptree->amove_killer[ply].no1)]];
1124 value_no2 = p_value_ex[15+BOARD[I2To(ptree->amove_killer[ply].no2)]];
1125 if ( move_good == ptree->anext_move[ply].move_cap1 )
1127 if ( ( ptree->anext_move[ply].phase_done & phase_killer1 )
1128 && UToFromToPromo(move_good) != ptree->amove_killer[ply].no1 )
1130 ptree->amove_killer[ply].no1_value
1131 = ptree->anext_move[ply].value_cap1 - value - 1;
1133 if ( ( ptree->anext_move[ply].phase_done & phase_killer2 )
1134 && UToFromToPromo(move_good) != ptree->amove_killer[ply].no2 )
1136 ptree->amove_killer[ply].no2_value
1137 = ptree->anext_move[ply].value_cap1 - value - 2;
1140 else if ( UToFromToPromo(move_good) == ptree->amove_killer[ply].no1 )
1142 if ( ( ptree->anext_move[ply].phase_done & phase_cap1 )
1143 && ( ptree->amove_killer[ply].no1_value + value
1144 < ptree->anext_move[ply].value_cap1 + 1 ) )
1146 ptree->amove_killer[ply].no1_value
1147 = ptree->anext_move[ply].value_cap1 - value + 1;
1149 if ( ( ptree->anext_move[ply].phase_done & phase_killer2 )
1150 && ( ptree->amove_killer[ply].no1_value + value
1151 < ptree->amove_killer[ply].no2_value + value_no2 + 1 ) )
1153 ptree->amove_killer[ply].no1_value
1154 = ptree->amove_killer[ply].no2_value + value_no2 - value + 1;
1157 else if ( UToFromToPromo(move_good) == ptree->amove_killer[ply].no2 )
1162 if ( ( ptree->anext_move[ply].phase_done & phase_cap1 )
1163 && ( ptree->amove_killer[ply].no2_value + value
1164 < ptree->anext_move[ply].value_cap1 + 1 ) )
1166 ptree->amove_killer[ply].no2_value
1167 = ptree->anext_move[ply].value_cap1 - value + 1;
1169 if ( ( ptree->anext_move[ply].phase_done & phase_killer1 )
1170 && ( ptree->amove_killer[ply].no2_value + value
1171 < ptree->amove_killer[ply].no1_value + value_no1 + 1 ) )
1173 ptree->amove_killer[ply].no2_value
1174 = ptree->amove_killer[ply].no1_value + value_no1 - value + 1;
1177 uswap = ptree->amove_killer[ply].no1;
1178 ptree->amove_killer[ply].no1 = ptree->amove_killer[ply].no2;
1179 ptree->amove_killer[ply].no2 = uswap;
1181 iswap = ptree->amove_killer[ply].no1_value;
1182 ptree->amove_killer[ply].no1_value = ptree->amove_killer[ply].no2_value;
1183 ptree->amove_killer[ply].no2_value = iswap;
1186 ptree->amove_killer[ply].no2 = ptree->amove_killer[ply].no1;
1187 ptree->amove_killer[ply].no1 = UToFromToPromo(move_good);
1189 if ( ptree->anext_move[ply].phase_done & phase_killer1 )
1191 i = swap( ptree, move_good, -MT_CAP_ROOK, MT_CAP_ROOK, turn );
1194 if ( ptree->amove_killer[ply].no1_value > i )
1196 ptree->amove_killer[ply].no1_value = i;
1199 ptree->amove_killer[ply].no2_value = ptree->amove_killer[ply].no1_value;
1200 ptree->amove_killer[ply].no1_value
1201 = ptree->anext_move[ply].value_cap1 - value + 1;
1205 if ( UToCap(move_good) ) { return; }
1206 if ( I2IsPromote(move_good)
1207 && I2PieceMove(move_good) != silver ) { return; }
1209 if ( ptree->killers[ply].no1 != move_good )
1211 ptree->killers[ply].no2 = ptree->killers[ply].no1;
1212 ptree->killers[ply].no1 = move_good;
1215 if ( depth < 1 ) { depth = 1; }
1217 n = ptree->hist_nmove[ply];
1218 for ( i = 0; i < n; i++ )
1220 move = ptree->hist_move[ply][i];
1221 assert( is_move_valid( ptree, move, turn ) );
1223 key = phash( move, turn );
1224 if ( ptree->hist_tried[key] >= HIST_MAX )
1226 ptree->hist_good[key] /= 2U;
1227 ptree->hist_tried[key] /= 2U;
1230 assert( ptree->hist_tried[key] < HIST_MAX );
1231 ptree->hist_tried[key]
1232 = (unsigned short)( (int)ptree->hist_tried[key] + depth );
1235 assert( is_move_valid( ptree, move_good, turn ) );
1236 key = phash( move_good, turn );
1238 assert( ptree->hist_good[key] < HIST_MAX );
1239 ptree->hist_good[key]
1240 = (unsigned short)( (int)ptree->hist_good[key] + depth );