7 /* #define DBG_QSEARCH */
8 #if defined(DBG_QSEARCH)
9 # define DOut( ... ) if ( dbg_flag ) { out( __VA_ARGS__ ); }
14 static int 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,
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 value = evaluate( ptree, ply, turn );
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 ( ( qui_ply == 1 && ! ( ply == 2 && InCheck( turn ) ) )
71 || ( 1 < qui_ply && qui_ply < QUIES_PLY_LIMIT && ! InCheck( turn ) ) )
73 MOVE_CURR = IsMateIn1Ply( turn );
76 value = score_mate1ply + 1 - ply;
79 && value < beta ) { pv_close( ptree, ply, mate_search ); }
81 DOut( "mate found\n" );
83 assert( is_move_valid( ptree, MOVE_CURR, turn ) );
89 ptree->anext_move[ply].next_phase = next_quies_gencap;
90 while ( gen_next_quies( ptree, alpha, turn, ply, qui_ply ) )
92 DOut( "\nexpand %s (%" PRIu64 ")",
93 str_CSA_move(MOVE_CURR), ptree->node_searched );
95 MakeMove( turn, MOVE_CURR, ply );
98 UnMakeMove( turn, MOVE_CURR, ply );
102 value = -search_quies( ptree, -beta, -alpha, Flip(turn), ply+1,
105 UnMakeMove( turn, MOVE_CURR, ply );
109 check_futile_score_quies( ptree, MOVE_CURR, ptree->stand_pat[ply],
110 -ptree->stand_pat[ply+1], turn );
113 DOut( ", beta cut (%" PRIu64 ")\n", ptree->node_searched );
115 assert( ! IsMove(MOVE_CURR)
116 || is_move_valid( ptree, MOVE_CURR, turn ) );
120 DOut( ", renew alpha=%d (%" PRIu64 ")\n",
121 value, ptree->node_searched );
126 DOut( "\nall searched (%" PRIu64 ")\n", ptree->node_searched );
128 if ( qui_ply < QUIES_PLY_LIMIT && is_mate_in3ply( ptree, turn, ply ) )
130 value = score_mate1ply + 1 - ply;
133 && value < beta ) { pv_close( ptree, ply, mate_search ); }
135 assert( is_move_valid( ptree, MOVE_CURR, turn ) );
139 if ( alpha_old != alpha )
141 if ( alpha == ptree->stand_pat[ply] ) { pv_close( ptree, ply, no_rep ); }
142 else { pv_copy( ptree, ply ); }
150 gen_next_quies( tree_t * restrict ptree, int alpha, int turn, int ply,
153 switch ( ptree->anext_move[ply].next_phase )
155 case next_quies_gencap:
157 unsigned int * restrict pmove;
158 int * restrict psortv;
159 int i, j, n, nqmove, value, min_score, diff;
162 ptree->move_last[ply] = GenCaptures( turn, ptree->move_last[ply-1] );
164 /* set sort values */
165 pmove = ptree->move_last[ply-1];
166 psortv = ptree->sort_value;
168 n = (int)( ptree->move_last[ply] - pmove );
170 for ( i = 0; i < n; i++ )
174 if ( qui_ply >= QUIES_PLY_LIMIT
175 && ( ( UToCap(move) == pawn && ! I2IsPromote(move) )
176 || ( ! UToCap(move) && I2PieceMove(move) != pawn ) ) )
181 diff = estimate_score_diff( ptree, move, turn );
182 min_score = eval_max_score( ptree, move, ptree->stand_pat[ply],
185 if ( alpha < min_score )
187 value = swap( ptree, move, -1, MT_CAP_SILVER, turn );
190 psortv[nqmove] = value + diff;
191 pmove[nqmove++] = move;
197 psortv[nqmove] = INT_MIN;
198 for ( i = nqmove-2; i >= 0; i-- )
200 value = psortv[i]; move = pmove[i];
201 for ( j = i+1; psortv[j] > value; j++ )
203 psortv[j-1] = psortv[j]; pmove[j-1] = pmove[j];
205 psortv[j-1] = value; pmove[j-1] = move;
208 ptree->move_last[ply] = ptree->move_last[ply-1] + nqmove;
209 ptree->anext_move[ply].move_last = pmove;
210 ptree->anext_move[ply].next_phase = next_quies_captures;
213 case next_quies_captures:
214 if ( ptree->anext_move[ply].move_last != ptree->move_last[ply] )
216 MOVE_CURR = *ptree->anext_move[ply].move_last++;