1 #include "chess.h"
2 #include "data.h"
3 /* last modified 08/03/16 */
4 /*
5 *******************************************************************************
6 * *
7 * Quiece() is the recursive routine used to implement the quiescence *
8 * search part of the alpha/beta negamax search. It performs the following *
9 * functions: *
10 * *
11 * (1) It computes a stand-pat score, which gives the side-on-move the *
12 * choice of standing pat and not playing any move at all and just accepting *
13 * the current static evaluation, or else it may try captures and/or *
14 * checking moves to see if it can improve the stand-pat score by making a *
15 * move that leads to some sort of positional or material gain. *
16 * *
17 * (2) The first phase is to generate all possible capture moves and then *
18 * sort them into descending using the value of the captured piece and the *
19 * complemented value of the capturing piece. This is the classic MVV/LVA *
20 * ordering approach that removes heavy pieces first in an attempt to reduce *
21 * the size of the sub-tree these pieces produce. *
22 * *
23 * (3) When we get ready to actually search each capture, we analyze each *
24 * move to see if it appears reasonable. Small pieces can capture larger *
25 * ones safely, ditto for equal exchanges. For the rest, we use SEE() to *
26 * compute the SEE score. If this is less than zero, we do not search this *
27 * move at all to avoid wasting time, since a losing capture rarely helps *
28 * improve the score in the q-search. The goal here is to find a capture *
29 * that improves on the stand-pat score and gets us closer to a position *
30 * that we would describe as "quiet" or "static". *
31 * *
32 * (4) If the parameter "checks" is non-zero, then after searching the *
33 * captures, we generate checking moves and search those. This value also *
34 * slightly changes the way captures are searched, since those that are also *
35 * checks result in calling QuiesceEvasions() which evades checks to see if *
36 * the check is actually a mate. This means that we have one layer of full- *
37 * width search to escape checks and do not allow a stand-pat which would *
38 * hide the effect of the check completely. *
39 * *
40 *******************************************************************************
41 */
Quiesce(TREE * RESTRICT tree,int ply,int wtm,int alpha,int beta,int checks)42 int Quiesce(TREE * RESTRICT tree, int ply, int wtm, int alpha, int beta,
43 int checks) {
44 unsigned *next, *movep;
45 int original_alpha = alpha, value, repeat;
46
47 /*
48 ************************************************************
49 * *
50 * Initialize. *
51 * *
52 ************************************************************
53 */
54 if (ply >= MAXPLY - 1)
55 return beta;
56 #if defined(NODES)
57 if (search_nodes && --temp_search_nodes <= 0) {
58 abort_search = 1;
59 return 0;
60 }
61 #endif
62 if (tree->thread_id == 0)
63 next_time_check--;
64 /*
65 ************************************************************
66 * *
67 * Check for draw by repetition, which includes 50 move *
68 * draws also. This is only done at the first ply of the *
69 * quiescence search since we are following checking moves *
70 * as well. The parameter "checks" passed in is "1" for *
71 * that particular case only (when called from Search()). *
72 * all other calls (from inside Quiesce()) pass a value of *
73 * zero so that additional plies of checks are not tried. *
74 * *
75 ************************************************************
76 */
77 if (checks) {
78 repeat = Repeat(tree, ply);
79 if (repeat) {
80 value = DrawScore(wtm);
81 if (value < beta)
82 SavePV(tree, ply, repeat);
83 #if defined(TRACE)
84 if (ply <= trace_level)
85 printf("draw by repetition detected, ply=%d.\n", ply);
86 #endif
87 return value;
88 }
89 }
90 /*
91 ************************************************************
92 * *
93 * Now call Evaluate() to produce the "stand-pat" score *
94 * that will be returned if no capture is acceptable. If *
95 * this score is > alpha and < beta, then we also have to *
96 * save the path to this node as it is the PV that leads *
97 * to this score. *
98 * *
99 ************************************************************
100 */
101 value = Evaluate(tree, ply, wtm, alpha, beta);
102 #if defined(TRACE)
103 if (ply <= trace_level)
104 Trace(tree, ply, value, wtm, alpha, beta, "Quiesce", serial, EVALUATION,
105 0);
106 #endif
107 if (value > alpha) {
108 if (value >= beta)
109 return value;
110 alpha = value;
111 tree->pv[ply].pathl = ply;
112 tree->pv[ply].pathh = 0;
113 tree->pv[ply].pathd = iteration;
114 }
115 /*
116 ************************************************************
117 * *
118 * Generate captures and sort them based on simple MVV/LVA *
119 * order. We simply try to capture the most valuable *
120 * piece possible, using the least valuable attacker *
121 * possible, to get rid of heavy pieces quickly and reduce *
122 * the overall size of the tree. *
123 * *
124 * Note that later we use the value of the capturing *
125 * piece, the value of the captured piece, and possibly *
126 * SEE() to exclude captures that appear to lose material, *
127 * but we delay expending this effort as long as possible, *
128 * since beta cutoffs make it unnecessary to search all of *
129 * these moves anyway. *
130 * *
131 ************************************************************
132 */
133 tree->last[ply] = GenerateCaptures(tree, ply, wtm, tree->last[ply - 1]);
134 for (movep = tree->last[ply - 1]; movep < tree->last[ply]; movep++) {
135 if (Captured(*movep) == king)
136 return beta;
137 *movep += MVV_LVA[Captured(*movep)][Piece(*movep)];
138 }
139 if (!checks && tree->last[ply] == tree->last[ply - 1]) {
140 if (alpha != original_alpha) {
141 tree->pv[ply - 1] = tree->pv[ply];
142 tree->pv[ply - 1].path[ply - 1] = tree->curmv[ply - 1];
143 }
144 return value;
145 }
146 NextSort(tree, ply);
147 /*
148 ************************************************************
149 * *
150 * Iterate through the move list and search the resulting *
151 * positions. Now that we are ready to actually search *
152 * the set of capturing moves, we try three quick tests to *
153 * see if the move should be excluded because it appears *
154 * to lose material. *
155 * *
156 * (1) If the capturing piece is not more valuable than *
157 * the captured piece, then the move can't lose material *
158 * and should be searched. *
159 * *
160 * (2) If the capture removes the last opponent piece, we *
161 * always search this kind of capture since this can be *
162 * the move the allows a passed pawn to promote when the *
163 * opponent has no piece to catch it. *
164 * *
165 * (3) Otherwise, If the capturing piece is more valuable *
166 * than the captured piece, we use SEE() to determine if *
167 * the capture is losing or not so that we don't search *
168 * hopeless moves. *
169 * *
170 ************************************************************
171 */
172 for (next = tree->last[ply - 1]; next < tree->last[ply]; next++) {
173 tree->curmv[ply] = Move(*next);
174 if (pcval[Piece(tree->curmv[ply])] > pcval[Captured(tree->curmv[ply])] &&
175 TotalPieces(Flip(wtm), occupied)
176 - p_vals[Captured(tree->curmv[ply])] > 0 &&
177 SEE(tree, wtm, tree->curmv[ply]) < 0)
178 continue;
179 #if defined(TRACE)
180 if (ply <= trace_level)
181 Trace(tree, ply, 0, wtm, alpha, beta, "Quiesce", serial, CAPTURES,
182 next - tree->last[ply - 1] + 1);
183 #endif
184 MakeMove(tree, ply, wtm, tree->curmv[ply]);
185 tree->nodes_searched++;
186 if (!checks)
187 value = -Quiesce(tree, ply + 1, Flip(wtm), -beta, -alpha, 0);
188 else if (!Check(wtm)) {
189 if (Check(Flip(wtm))) {
190 tree->qchecks_done++;
191 value = -QuiesceEvasions(tree, ply + 1, Flip(wtm), -beta, -alpha);
192 } else
193 value = -Quiesce(tree, ply + 1, Flip(wtm), -beta, -alpha, 0);
194 }
195 UnmakeMove(tree, ply, wtm, tree->curmv[ply]);
196 if (abort_search || tree->stop)
197 return 0;
198 if (value > alpha) {
199 if (value >= beta)
200 return value;
201 alpha = value;
202 }
203 }
204 /*
205 ************************************************************
206 * *
207 * The next block of code is only executed if the checks *
208 * parameter is non-zero, otherwise we skip this and exit *
209 * with no further searching. *
210 * *
211 * Generate just the moves (non-captures) that give check *
212 * and search the ones that SEE() says are safe. Subtle *
213 * trick: we discard the captures left over from the *
214 * above search since we labeled them "losing moves." *
215 * *
216 ************************************************************
217 */
218 if (checks) {
219 tree->last[ply] = GenerateChecks(tree, wtm, tree->last[ply - 1]);
220 /*
221 ************************************************************
222 * *
223 * Iterate through the move list and search the resulting *
224 * positions. We take them in the normal order that *
225 * GenerateChecks() provides. *
226 * *
227 ************************************************************
228 */
229 for (next = tree->last[ply - 1]; next < tree->last[ply]; next++) {
230 tree->curmv[ply] = Move(*next);
231 if (SEE(tree, wtm, tree->curmv[ply]) >= 0) {
232 #if defined(TRACE)
233 if (ply <= trace_level)
234 Trace(tree, ply, 0, wtm, alpha, beta, "Quiesce+checks", serial,
235 REMAINING, next - tree->last[ply - 1] + 1);
236 #endif
237 MakeMove(tree, ply, wtm, tree->curmv[ply]);
238 tree->nodes_searched++;
239 if (!Check(wtm)) {
240 tree->qchecks_done++;
241 value = -QuiesceEvasions(tree, ply + 1, Flip(wtm), -beta, -alpha);
242 }
243 UnmakeMove(tree, ply, wtm, tree->curmv[ply]);
244 if (abort_search || tree->stop)
245 return 0;
246 if (value > alpha) {
247 if (value >= beta)
248 return value;
249 alpha = value;
250 }
251 }
252 }
253 }
254 /*
255 ************************************************************
256 * *
257 * All moves have been searched. Return the search result *
258 * that was found. If the result is not the original *
259 * alpha score, then we need to back up the PV that is *
260 * associated with this score. *
261 * *
262 ************************************************************
263 */
264 if (alpha != original_alpha) {
265 tree->pv[ply - 1] = tree->pv[ply];
266 tree->pv[ply - 1].path[ply - 1] = tree->curmv[ply - 1];
267 }
268 return alpha;
269 }
270
271 /* last modified 08/03/16 */
272 /*
273 *******************************************************************************
274 * *
275 * QuiesceEvasions() is the recursive routine used to implement the alpha/ *
276 * beta negamax quiescence search. The primary function here is to escape a *
277 * check that was delivered by Quiesce() at the previous ply. We do not *
278 * have the usual "stand pat" option because we have to find a legal move to *
279 * prove we have not been checkmated. *
280 * *
281 * QuiesceEvasions() uses the legal move generator (GenerateCheckEvasions()) *
282 * to produce only the set of legal moves that escape check. We try those *
283 * in the the order they are generated since we are going to try them all *
284 * unless we get a fail-high. *
285 * *
286 *******************************************************************************
287 */
QuiesceEvasions(TREE * RESTRICT tree,int ply,int wtm,int alpha,int beta)288 int QuiesceEvasions(TREE * RESTRICT tree, int ply, int wtm, int alpha,
289 int beta) {
290 int original_alpha, value, moves_searched = 0, order, repeat;
291
292 /*
293 ************************************************************
294 * *
295 * Initialize. *
296 * *
297 ************************************************************
298 */
299 if (ply >= MAXPLY - 1)
300 return beta;
301 #if defined(NODES)
302 if (search_nodes && --temp_search_nodes <= 0) {
303 abort_search = 1;
304 return 0;
305 }
306 if (tree->thread_id == 0)
307 next_time_check--;
308 #endif
309 /*
310 ************************************************************
311 * *
312 * Check for draw by repetition, which includes 50 move *
313 * draws also. *
314 * *
315 ************************************************************
316 */
317 repeat = Repeat(tree, ply);
318 if (repeat) {
319 value = DrawScore(wtm);
320 if (value < beta)
321 SavePV(tree, ply, repeat);
322 #if defined(TRACE)
323 if (ply <= trace_level)
324 printf("draw by repetition detected, ply=%d.\n", ply);
325 #endif
326 return value;
327 }
328 original_alpha = alpha;
329 /*
330 ************************************************************
331 * *
332 * Iterate through the move list and search the resulting *
333 * positions. These moves are searched in the order that *
334 * GenerateEvasions() produces them. No hash move is *
335 * possible since we don't do probes in Quiesce(). We do *
336 * clear the hash move before we start selecting moves so *
337 * that we don't search a bogus move from a different *
338 * position. *
339 * *
340 ************************************************************
341 */
342 tree->hash_move[ply] = 0;
343 tree->next_status[ply].phase = HASH;
344 while ((order = NextMove(tree, ply, 0, wtm, 1))) {
345 #if defined(TRACE)
346 if (ply <= trace_level)
347 Trace(tree, ply, 0, wtm, alpha, beta, "QuiesceEvasions", serial,
348 tree->phase[ply], order);
349 #endif
350 moves_searched++;
351 MakeMove(tree, ply, wtm, tree->curmv[ply]);
352 tree->nodes_searched++;
353 value = -Quiesce(tree, ply + 1, Flip(wtm), -beta, -alpha, 0);
354 UnmakeMove(tree, ply, wtm, tree->curmv[ply]);
355 if (abort_search || tree->stop)
356 return 0;
357 if (value > alpha) {
358 if (value >= beta)
359 return value;
360 alpha = value;
361 }
362 }
363 /*
364 ************************************************************
365 * *
366 * All moves have been searched. If none were legal, it *
367 * must be a mate since we have to be in check to reach *
368 * QuiesceEvasions(). *
369 * *
370 ************************************************************
371 */
372 if (moves_searched == 0) {
373 value = -(MATE - ply);
374 if (value >= alpha && value < beta) {
375 SavePV(tree, ply, 0);
376 #if defined(TRACE)
377 if (ply <= trace_level)
378 printf("Search() no moves! ply=%d\n", ply);
379 #endif
380 }
381 return value;
382 } else if (alpha != original_alpha) {
383 tree->pv[ply - 1] = tree->pv[ply];
384 tree->pv[ply - 1].path[ply - 1] = tree->curmv[ply - 1];
385 }
386 return alpha;
387 }
388