7 /* #define DBG_QSEARCH */
8 #if defined(DBG_QSEARCH)
9 # define DOut( ... ) if ( dbg_flag ) { out( __VA_ARGS__ ); }
14 static int CONV gen_next_quies( tree_t * restrict ptree, int alpha, int turn,
15 int ply, int qui_ply );
18 search_quies( tree_t * restrict ptree, int alpha, int beta, int turn, int ply,
21 int value, alpha_old, stand_pat;
23 #if defined(DBG_QSEARCH)
26 if ( iteration_depth == 2 && ply == 4
27 && ! strcmp( str_CSA_move(ptree->current_move[1]), "7776FU" )
28 && ! strcmp( str_CSA_move(ptree->current_move[2]), "3334FU" )
29 && ! strcmp( str_CSA_move(ptree->current_move[3]), "8822UM" ) )
32 Out( "qsearch start (alpha=%d beta=%d sp=%d %" PRIu64 ")",
33 alpha, beta, value, ptree->node_searched );
39 if ( ! ptree->tlp_id )
44 ptree->node_searched += 1;
45 ptree->nquies_called += 1;
48 stand_pat = evaluate( ptree, ply, turn );
51 if ( alpha < stand_pat )
53 if ( beta <= stand_pat )
55 DOut( ", cut by stand-pat\n" );
56 MOVE_CURR = MOVE_PASS;
62 if ( ply >= PLY_MAX-1 )
64 if ( alpha_old != alpha ) { pv_close( ptree, ply, no_rep ); }
70 if ( is_mate_in3ply( ptree, turn, ply ) )
72 value = score_mate1ply + 1 - ply;
75 && value < beta ) { pv_close( ptree, ply, mate_search ); }
77 assert( is_move_valid( ptree, MOVE_CURR, turn ) );
82 ptree->anext_move[ply].next_phase = next_quies_gencap;
83 while ( gen_next_quies( ptree, alpha, turn, ply, qui_ply ) )
85 DOut( "\nexpand %s (%" PRIu64 ")",
86 str_CSA_move(MOVE_CURR), ptree->node_searched );
88 MakeMove( turn, MOVE_CURR, ply );
91 UnMakeMove( turn, MOVE_CURR, ply );
95 value = -search_quies( ptree, -beta, -alpha, Flip(turn), ply+1,
98 UnMakeMove( turn, MOVE_CURR, ply );
102 check_futile_score_quies( ptree, MOVE_CURR, ptree->save_eval[ply],
103 -ptree->save_eval[ply+1], turn );
106 DOut( ", beta cut (%" PRIu64 ")\n", ptree->node_searched );
108 assert( ! IsMove(MOVE_CURR)
109 || is_move_valid( ptree, MOVE_CURR, turn ) );
113 DOut( ", renew alpha=%d (%" PRIu64 ")\n",
114 value, ptree->node_searched );
119 DOut( "\nall searched (%" PRIu64 ")\n", ptree->node_searched );
121 if ( alpha_old != alpha )
123 if ( alpha == stand_pat ) { pv_close( ptree, ply, no_rep ); }
124 else { pv_copy( ptree, ply ); }
132 gen_next_quies( tree_t * restrict ptree, int alpha, int turn, int ply,
135 switch ( ptree->anext_move[ply].next_phase )
137 case next_quies_gencap:
139 unsigned int * restrict pmove;
140 int * restrict psortv;
141 int i, j, n, nqmove, value, min_score, diff;
144 ptree->move_last[ply] = GenCaptures( turn, ptree->move_last[ply-1] );
146 /* set sort values */
147 pmove = ptree->move_last[ply-1];
148 psortv = ptree->sort_value;
150 n = (int)( ptree->move_last[ply] - pmove );
152 for ( i = 0; i < n; i++ )
156 if ( qui_ply >= QUIES_PLY_LIMIT
157 && ( ( UToCap(move) == pawn && ! I2IsPromote(move) )
158 || ( ! UToCap(move) && I2PieceMove(move) != pawn ) ) )
163 diff = estimate_score_diff( ptree, move, turn );
164 min_score = eval_max_score( ptree, move, ptree->save_eval[ply],
167 if ( alpha < min_score )
169 value = swap( ptree, move, -1, MT_CAP_SILVER, turn );
172 psortv[nqmove] = value + diff;
173 pmove[nqmove++] = move;
179 psortv[nqmove] = INT_MIN;
180 for ( i = nqmove-2; i >= 0; i-- )
182 value = psortv[i]; move = pmove[i];
183 for ( j = i+1; psortv[j] > value; j++ )
185 psortv[j-1] = psortv[j]; pmove[j-1] = pmove[j];
187 psortv[j-1] = value; pmove[j-1] = move;
190 ptree->move_last[ply] = ptree->move_last[ply-1] + nqmove;
191 ptree->anext_move[ply].move_last = pmove;
192 ptree->anext_move[ply].next_phase = next_quies_captures;
195 case next_quies_captures:
196 if ( ptree->anext_move[ply].move_last != ptree->move_last[ply] )
198 MOVE_CURR = *ptree->anext_move[ply].move_last++;