1 #include "chess.h"
2 #include "data.h"
3 #if defined(SYZYGY)
4 # include "tbprobe.h"
5 #endif
6 /* last modified 08/03/16 */
7 /*
8 *******************************************************************************
9 * *
10 * Search() is the recursive routine used to implement the alpha/beta *
11 * negamax search (similar to minimax but simpler to code.) Search() is *
12 * called whenever there is "depth" remaining so that all moves are subject *
13 * to searching. Search() recursively calls itself so long as there is at *
14 * least one ply of depth left, otherwise it calls Quiesce() instead. *
15 * *
16 *******************************************************************************
17 */
Search(TREE * RESTRICT tree,int ply,int depth,int wtm,int alpha,int beta,int in_check,int do_null)18 int Search(TREE * RESTRICT tree, int ply, int depth, int wtm, int alpha,
19 int beta, int in_check, int do_null) {
20 int repeat = 0, value = 0, pv_node = alpha != beta - 1, n_depth;
21 int searched[256];
22
23 /*
24 ************************************************************
25 * *
26 * Timeout. Check to see if we have searched enough nodes *
27 * that it is time to peek at how much time has been used, *
28 * or if is time to check for operator keyboard input. *
29 * This is usually enough nodes to force a time/input *
30 * check about once per second, except when the target *
31 * time per move is very small, in which case we try to *
32 * check the time more frequently. *
33 * *
34 * Note that we check input or time-out in thread 0. This *
35 * makes the code simpler and eliminates some problematic *
36 * race conditions. *
37 * *
38 ************************************************************
39 */
40 #if defined(NODES)
41 if (search_nodes && --temp_search_nodes <= 0) {
42 abort_search = 1;
43 return 0;
44 }
45 #endif
46 if (tree->thread_id == 0) {
47 if (--next_time_check <= 0) {
48 next_time_check = nodes_between_time_checks;
49 if (TimeCheck(tree, 1)) {
50 abort_search = 1;
51 return 0;
52 }
53 if (CheckInput()) {
54 Interrupt(ply);
55 if (abort_search)
56 return 0;
57 }
58 }
59 }
60 if (ply >= MAXPLY - 1)
61 return beta;
62 /*
63 ************************************************************
64 * *
65 * Draws. Check for draw by repetition, which includes *
66 * 50 move draws also. This is the quickest way to get *
67 * out of further searching, with minimal effort. This *
68 * and the next four steps are skipped for moves at the *
69 * root (ply = 1). *
70 * *
71 ************************************************************
72 */
73 if (ply > 1) {
74 if ((repeat = Repeat(tree, ply))) {
75 if (repeat == 2 || !in_check) {
76 value = DrawScore(wtm);
77 if (value < beta)
78 SavePV(tree, ply, repeat);
79 #if defined(TRACE)
80 if (ply <= trace_level)
81 printf("draw by %s detected, ply=%d.\n",
82 (repeat == 3) ? "50-move" : "repetition", ply);
83 #endif
84 return value;
85 }
86 }
87 /*
88 ************************************************************
89 * *
90 * Mate distance pruning. If we have found a mate, we can *
91 * stop if we are too deep to find a shorter mate. This *
92 * only affects the size of the tree in positions where *
93 * there are forced mates. It does not change the outcome *
94 * of the search at all, just the time it takes. *
95 * *
96 ************************************************************
97 */
98 alpha = Max(alpha, -MATE + ply - 1);
99 beta = Min(beta, MATE - ply);
100 if (alpha >= beta)
101 return alpha;
102 /*
103 ************************************************************
104 * *
105 * Trans/Ref. Check the transposition/refutation (hash) *
106 * table to see if we have searched this position *
107 * previously and still have the results available. We *
108 * might get a real score, or a bound, or perhaps only a *
109 * good move to try first. The possible results are: *
110 * *
111 * 1. HashProbe() returns "HASH_HIT". This terminates the *
112 * search instantly and we simply return the value found *
113 * in the hash table. This value is simply the value we *
114 * found when we did a real search in this position *
115 * previously, and ProbeTransRef() verifies that the value *
116 * is useful based on draft and current bounds. *
117 * *
118 * 2. HashProbe() returns "AVOID_NULL_MOVE" which means *
119 * the hashed score/bound was no good, but it indicated *
120 * that trying a null-move in this position would be a *
121 * waste of time since it will likely fail low, not high. *
122 * *
123 * 3. HashProbe() returns "HASH_MISS" when forces us to do *
124 * a normal search to resolve this node. *
125 * *
126 ************************************************************
127 */
128 switch (HashProbe(tree, ply, depth, wtm, alpha, beta, &value)) {
129 case HASH_HIT:
130 return value;
131 case AVOID_NULL_MOVE:
132 do_null = 0;
133 case HASH_MISS:
134 break;
135 }
136 /*
137 ************************************************************
138 * *
139 * EGTBs. Now it's time to try a probe into the endgame *
140 * tablebase files. This is done if we notice that there *
141 * are 6 or fewer pieces left on the board AND the 50 move *
142 * counter is zero which enables probing the WDL EGTBs *
143 * correctly. Probing after a capture won't work as it is *
144 * possible that there is a necessary pawn push here and *
145 * there to reset the 50 move counter, otherwise we could *
146 * think we were following a winning path but heading to a *
147 * draw. *
148 * *
149 * This is another way to get out of the search quickly, *
150 * but not as quickly as the previous steps since this can *
151 * result in an I/O operation. *
152 * *
153 * Note that in "swindle mode" this can be turned off by *
154 * Iterate() setting "EGTB_use = 0" so that we won't probe *
155 * the EGTBs since we are searching only the root moves *
156 * that lead to a draw and we want to play the move that *
157 * makes the draw more difficult to reach by the opponent *
158 * to give him a chance to make a mistake. *
159 * *
160 * Another special case is that we slightly fudge the *
161 * score for draws. The scores are -0.03 for a "blessed *
162 * loss", 0.0 for a pure draw, and +0.03 for a "cursed *
163 * win". These are then modified by adding 0.01 if the *
164 * side on move is ahead in material, and subtracting 0.01 *
165 * if the side on move is behind material. This creates *
166 * the following inequality: *
167 * *
168 * BL- < BL= < BL+ < D- < D= < D+ < CW- < CW= <CW+ *
169 * *
170 * Where BL=blessed loss, D = draw, and CW = cursed win, *
171 * and - means behind in material, = means equal material, *
172 * and + means ahead in material. *
173 * *
174 ************************************************************
175 */
176 #if defined(SYZYGY)
177 if (depth > EGTB_depth && TotalAllPieces <= EGTB_use &&
178 !Castle(ply, white) && !Castle(ply, black) && Reversible(ply) == 0) {
179 int tb_result;
180
181 tree->egtb_probes++;
182 tb_result =
183 tb_probe_wdl(Occupied(white), Occupied(black),
184 Kings(white) | Kings(black), Queens(white) | Queens(black),
185 Rooks(white) | Rooks(black), Bishops(white) | Bishops(black),
186 Knights(white) | Knights(black), Pawns(white) | Pawns(black),
187 Reversible(ply), 0, EnPassant(ply), wtm, HashKey);
188 if (tb_result != TB_RESULT_FAILED) {
189 tree->egtb_hits++;
190 switch (tb_result) {
191 case TB_LOSS:
192 alpha = -TBWIN;
193 break;
194 case TB_BLESSED_LOSS:
195 alpha = -3;
196 break;
197 case TB_DRAW:
198 alpha = 0;
199 break;
200 case TB_CURSED_WIN:
201 alpha = 3;
202 break;
203 case TB_WIN:
204 alpha = TBWIN;
205 break;
206 }
207 if (tb_result != TB_LOSS && tb_result != TB_WIN) {
208 if (MaterialSTM(wtm) > 0)
209 alpha += 1;
210 else if (MaterialSTM(wtm) < 0)
211 alpha -= 1;
212 }
213 if (alpha < beta)
214 SavePV(tree, ply, 4);
215 return alpha;
216 }
217 }
218 #endif
219 /*
220 ************************************************************
221 * *
222 * Null-move. We now know there is no quick way to get *
223 * out of here, which leaves one more possibility, *
224 * although it does require a search, but to a reduced *
225 * depth. We try a null move to see if we can get a quick *
226 * cutoff with only a little work. This operates as *
227 * follows. Instead of making a legal move, the side on *
228 * move passes and does nothing. The resulting position *
229 * is searched to a shallower depth than normal (see *
230 * below). This will result in a cutoff if our position *
231 * is very good, but it produces the cutoff much quicker *
232 * since the search is far shallower than a normal search *
233 * that would also be likely to fail high. *
234 * *
235 * The reduction amount starts off at null_depth (normally *
236 * set to 3 but the user can change this via the crafty *
237 * personality command) but is then increased as follows: *
238 * *
239 * R = null_depth + depth / null_divisor *
240 * *
241 * null_divisor defaults to 6, but this can also be set *
242 * by the user to try more/less aggressive settings. *
243 * *
244 * This is skipped for any of the following reasons: *
245 * *
246 * 1. The side on move is in check. The null move *
247 * results in an illegal position. *
248 * 2. No more than one null move can appear in succession *
249 * as all this does is burn 2x plies of depth. *
250 * 3. The side on move has only pawns left, which makes *
251 * zugzwang positions more likely. *
252 * 4. The transposition table probe found an entry that *
253 * indicates that a null-move search will not fail *
254 * high, so we avoid the wasted effort. *
255 * *
256 ************************************************************
257 */
258
259 tree->last[ply] = tree->last[ply - 1];
260 n_depth = (TotalPieces(wtm, occupied) > 9 || n_root_moves > 17 ||
261 depth > 3) ? 1 : 3;
262 if (do_null && !pv_node && depth > n_depth && !in_check &&
263 TotalPieces(wtm, occupied)) {
264 uint64_t save_hash_key;
265 int R = null_depth + depth / null_divisor;
266
267 tree->curmv[ply] = 0;
268 #if defined(TRACE)
269 if (ply <= trace_level)
270 Trace(tree, ply, depth, wtm, value - 1, value, "SearchNull", serial,
271 NULL_MOVE, 0);
272 #endif
273 tree->status[ply + 1] = tree->status[ply];
274 Reversible(ply + 1) = 0;
275 save_hash_key = HashKey;
276 if (EnPassant(ply + 1)) {
277 HashEP(EnPassant(ply + 1));
278 EnPassant(ply + 1) = 0;
279 }
280 tree->null_done[Min(R, 15)]++;
281 if (depth - R - 1 > 0)
282 value =
283 -Search(tree, ply + 1, depth - R - 1, Flip(wtm), -beta, -beta + 1,
284 0, NO_NULL);
285 else
286 value = -Quiesce(tree, ply + 1, Flip(wtm), -beta, -beta + 1, 1);
287 HashKey = save_hash_key;
288 if (abort_search || tree->stop)
289 return 0;
290 if (value >= beta) {
291 HashStore(tree, ply, depth, wtm, LOWER, value, tree->hash_move[ply]);
292 return value;
293 }
294 }
295 /*
296 ************************************************************
297 * *
298 * IID. This step is rarely executed. It is used when *
299 * there is no best move from the hash table, and this is *
300 * a PV node, since we need a good move to search first. *
301 * While killers moves are good, they are not quite good *
302 * enough. the simplest solution is to try a shallow *
303 * search (depth-2) to get a move. note that when we call *
304 * Search() with depth-2, it, too, will not have a hash *
305 * move, and will therefore recursively continue this *
306 * process, hence the name "internal iterative deepening." *
307 * *
308 ************************************************************
309 */
310 tree->next_status[ply].phase = HASH;
311 if (!tree->hash_move[ply] && depth >= 6 && do_null && ply > 1 && pv_node) {
312 tree->curmv[ply] = 0;
313 if (depth - 2 > 0)
314 value =
315 Search(tree, ply, depth - 2, wtm, alpha, beta, in_check, DO_NULL);
316 else
317 value = Quiesce(tree, ply, wtm, alpha, beta, 1);
318 if (abort_search || tree->stop)
319 return 0;
320 if (value > alpha) {
321 if (value < beta) {
322 if ((int) tree->pv[ply - 1].pathl > ply)
323 tree->hash_move[ply] = tree->pv[ply - 1].path[ply];
324 } else
325 tree->hash_move[ply] = tree->curmv[ply];
326 tree->last[ply] = tree->last[ply - 1];
327 tree->next_status[ply].phase = HASH;
328 }
329 }
330 }
331 /*
332 ************************************************************
333 * *
334 * Search moves. Now we call SearchMoveList() to interate *
335 * through the move list and search each new position. *
336 * Note that this is done in a separate procedure because *
337 * this is also the code that is used to do the parallel *
338 * search. *
339 * *
340 ************************************************************
341 */
342 searched[0] = 0;
343 value =
344 SearchMoveList(tree, ply, depth, wtm, alpha, beta, searched, in_check,
345 repeat, serial);
346 return value;
347 }
348
349 /* last modified 08/03/16 */
350 /*
351 *******************************************************************************
352 * *
353 * SearchMoveList() is the recursive routine used to implement the main *
354 * search loop. This code is responsible for iterating through the move *
355 * list until it encounters a condition that ends the search at this ply. *
356 * At that point it simply returns the current negamax value to the caller *
357 * to handle as necessary. *
358 * *
359 * The "mode" flag indicates which of the following conditions apply here *
360 * which directly controls parts of the search. *
361 * *
362 * mode = serial -> this is a serial search. *
363 * *
364 * mode = parallel -> this is a parallel search, which implies that this *
365 * is a partial search which means we do NOT want to *
366 * do any trans/ref updating and we also need to take *
367 * care about locking things that are being updated *
368 * by more than one thread in parallel. *
369 * *
370 * When mode = parallel, this code performs the same function as the old *
371 * SearchParallel() code, except that it is the main search loop for the *
372 * program, there is no longer any duplicated code. This is called by the *
373 * normal Search() function and by ThreadWait() where idle processes wait *
374 * for work and then call this procedure to search a subset of the moves at *
375 * this ply (in parallel with other threads). *
376 * *
377 *******************************************************************************
378 */
SearchMoveList(TREE * RESTRICT tree,int ply,int depth,int wtm,int alpha,int beta,int searched[],int in_check,int repeat,int mode)379 int SearchMoveList(TREE * RESTRICT tree, int ply, int depth, int wtm,
380 int alpha, int beta, int searched[], int in_check, int repeat, int mode) {
381 TREE *current;
382 int extend, reduce, check, original_alpha = alpha, t_beta;
383 int i, j, value = 0, pv_node = alpha != beta - 1, search_result, order;
384 int moves_done = 0, bestmove, type;
385
386 /*
387 ************************************************************
388 * *
389 * Basic initialization before we begin the loop through *
390 * the move list. If this is a parallel search, we have *
391 * already searched one move, so we set t_beta to alpha+1 *
392 * to set up for a normal PVS search (for moves 2-n) *
393 * instead of using alpha,beta for the first move as we do *
394 * in a normal search. Also, if this is a serial search, *
395 * we are fixing to search the first move so we set the *
396 * searched move counter to zero, where in a parallel *
397 * search this has already been done and we leave it alone *
398 * here. *
399 * *
400 * We also set <current> to tree for a serial search, and *
401 * to tree->parent for a parallel search since we need to *
402 * share the move list at split nodes. *
403 * *
404 ************************************************************
405 */
406 tree->next_status[ply].phase = HASH;
407 if (mode == parallel) {
408 current = tree->parent;
409 t_beta = alpha + 1;
410 } else {
411 current = tree;
412 t_beta = beta;
413 }
414 /*
415 ************************************************************
416 * *
417 * Iterate. Now iterate through the move list and search *
418 * the resulting positions. Note that Search() culls any *
419 * move that is not legal by using Check(). The special *
420 * case is that we must find one legal move to search to *
421 * confirm that it's not a mate or draw. *
422 * *
423 * We call NextMove() which will generate moves in the *
424 * normal way (captures, killers, etc) or it will use the *
425 * GenerateEvasions() generator if we are in check. For *
426 * the special case of ply=1, we use NextRootMove() since *
427 * the ply=1 move list has been generated and the order is *
428 * updated as each search iteration is executed. *
429 * *
430 ************************************************************
431 */
432 while (1) {
433 if (ply == 1 && moves_done == 1 && alpha == original_alpha &&
434 mode == serial)
435 break;
436 if (mode == parallel)
437 Lock(current->lock);
438 order = (ply > 1) ? NextMove(current, ply, depth, wtm, in_check)
439 : NextRootMove(current, tree, wtm);
440 if (mode == parallel) {
441 tree->curmv[ply] = current->curmv[ply];
442 Unlock(current->lock);
443 }
444 if (!order)
445 break;
446 #if defined(TRACE)
447 if (ply <= trace_level)
448 Trace(tree, ply, depth, wtm, alpha, beta, "SearchMoveList", mode,
449 current->phase[ply], order);
450 #endif
451 MakeMove(tree, ply, wtm, tree->curmv[ply]);
452 tree->nodes_searched++;
453 search_result = ILLEGAL;
454 if (in_check || !Check(wtm))
455 do {
456 searched[0]++;
457 moves_done++;
458 search_result = LEGAL;
459 searched[searched[0]] = tree->curmv[ply];
460 /*
461 ************************************************************
462 * *
463 * Check. If the move to be made checks the opponent, *
464 * then we need to remember that he's in check and also *
465 * extend the depth by one ply for him to get out. *
466 * *
467 * We do not extend unsafe checking moves (as indicated by *
468 * the SEE algorithm), since these are usually a waste of *
469 * time and simply blow up the tree search space. *
470 * *
471 * Note that extending here disables any potential foward *
472 * pruning or reductions for this move. *
473 * *
474 ************************************************************
475 */
476 extend = 0;
477 reduce = 0;
478 if (Check(Flip(wtm))) {
479 check = 1;
480 if (SEEO(tree, wtm,
481 tree->curmv[ply]) - pcval[Captured(tree->curmv[ply])] <=
482 0) {
483 extend = check_depth;
484 tree->extensions_done++;
485 }
486 } else
487 check = 0;
488 /*
489 ************************************************************
490 * *
491 * Futility. First attempt at forward pruning based on *
492 * the futility idea. *
493 * *
494 * We have an array of pruning margin values that are *
495 * indexed by depth (remaining plies left until we drop *
496 * into the quiescence search) and which increase with *
497 * depth since more depth means a greater chance of *
498 * bringing the score back up to alpha or beyond. If the *
499 * current material + the bonus is less than alpha, we *
500 * simply avoid searching this move at all, and skip to *
501 * the next move without expending any more effort. Note *
502 * that this is classic forward-pruning and can certainly *
503 * introduce errors into the search. However, cluster *
504 * testing has shown that this improves play in real *
505 * games. The current implementation only prunes in the *
506 * last 6 plies before quiescence, although this can be *
507 * tuned with the "eval" command changing the "pruning *
508 * depth" value to something other than 7 (test is for *
509 * depth < pruning depth, current value is 7 which prunes *
510 * in last 6 plies only). Testing shows no benefit in *
511 * larger values than 7, although this might change in *
512 * future versions as other things are modified. *
513 * *
514 * Exception: *
515 * *
516 * We do not prune if we are safely pushing a passed *
517 * pawn to the 6th rank, where it becomes very dangerous *
518 * since it can promote in two more moves. *
519 * *
520 * All pruning and reduction code is skipped if any of the *
521 * following are true: *
522 * *
523 * (1) side on move is in check. *
524 * *
525 * (2) move has not already been flagged for a search *
526 * extension. *
527 * *
528 * (3) this is not the first move at this ply. *
529 * *
530 ************************************************************
531 */
532 if (!in_check && (!extend || !pv_node) && order > 1 &&
533 !(PawnPush(wtm, tree->curmv[ply]))) {
534 if (depth < FP_depth && !check &&
535 MaterialSTM(wtm) + FP_margin[depth] <= alpha && !pv_node) {
536 tree->moves_fpruned++;
537 break;
538 }
539 /*
540 ************************************************************
541 * *
542 * LMP. Final attempt at forward pruning based on the *
543 * "late move pruning" idea (a take-off on LMR). *
544 * *
545 * The basic idea here is that once we have searched a *
546 * significant number of moves at a ply, it becomes less *
547 * and less likely that any of the moves left will produce *
548 * a cutoff. If the move appears to be simple (not a *
549 * check, etc) then we simply skip it, once the move count *
550 * has been satisfied. At present, we only do this in the *
551 * last 16 plies although this might be changed in the *
552 * future. If you look at the LMP array after it has been *
553 * initialized, you will notice that it is unlikely that *
554 * LMP can be triggered much beyond depth 8 as you have to *
555 * have a BUNCH of moves to search to reach those limits. *
556 * *
557 ************************************************************
558 */
559 if (order > LMP[depth] && depth < LMP_depth && !pv_node && !check &&
560 alpha > -MATE + 300 && !CaptureOrPromote(tree->curmv[ply])) {
561 tree->moves_mpruned++;
562 break;
563 }
564 /*
565 ************************************************************
566 * *
567 * LMR. Now it's time to try to reduce the search depth *
568 * if the move appears to be "poor" because it appears *
569 * later in the move list. *
570 * *
571 * The reduction is variable and is done via a table look- *
572 * up that uses a function based on remaining depth (more *
573 * depth remaining, the larger the reduction) and the *
574 * number of moves searched (more moves searched, the *
575 * larger the reduction). The "shape" of this reduction *
576 * formula is user-settable via the "lmr" command. *
577 * *
578 ************************************************************
579 */
580 reduce = LMR[Min(depth, 31)][Min(order, 63)];
581 if (reduce && (pv_node || extend))
582 reduce--;
583 tree->LMR_done[reduce]++;
584 }
585 /*
586 ************************************************************
587 * *
588 * Now do the PVS search on the current move. *
589 * *
590 * Note that we do the usual alpha/beta cutoff tests here *
591 * but we only set an indicator that is used after we have *
592 * called Unmake(). This cleaned up the exit from search *
593 * and makes it easier to understand when there is only *
594 * one point where this is done, without needing multiple *
595 * Unmake() calls when there are different exit points. *
596 * *
597 **************************************************************
598 */
599 value =
600 SearchMove(tree, ply, depth, wtm, alpha, t_beta, beta, extend,
601 reduce, check);
602 if (value > alpha) {
603 search_result = IN_WINDOW;
604 if (value >= beta)
605 search_result = FAIL_HIGH;
606 if (mode == parallel && ply == 1)
607 search_result = FAIL_HIGH;
608 }
609 } while (0);
610 UnmakeMove(tree, ply, wtm, tree->curmv[ply]);
611 if (abort_search || tree->stop)
612 break;
613 /*
614 ************************************************************
615 * *
616 * Test 1. When we get here, we have made a move, *
617 * searched it (and re-searched if necessary/appropriate), *
618 * and the move has been unmade so that the board is in a *
619 * correct state. *
620 * *
621 * If search_result = FAIL_HIGH, the search failed high. *
622 * The first thing to handle is the case where we are at *
623 * ply=1, which is a special case. If we are going to *
624 * fail high here and terminate the search immediately, we *
625 * need to build the fail-high PV to back up to Iterate() *
626 * so it will produce the correct output and widen the *
627 * alpha/beta window. *
628 * *
629 * We then check to see if this is a parallel search. If *
630 * so then we are done here, but we need to tell all of *
631 * the siblings that are helping at this split point that *
632 * they should immediately stop searching here since we *
633 * don't need their results. *
634 * *
635 * Otherwise we update the killer moves and history *
636 * counters and store the fail-high information in the *
637 * trans/ref table for future use if we happen to reach *
638 * this position again. *
639 * *
640 ************************************************************
641 */
642 if (search_result == FAIL_HIGH) {
643 if (ply == 1) {
644 if (!tree->stop) {
645 tree->pv[1].path[1] = tree->curmv[1];
646 tree->pv[1].pathl = 2;
647 tree->pv[1].pathh = 0;
648 tree->pv[1].pathd = iteration;
649 tree->pv[0] = tree->pv[1];
650 }
651 }
652 #if (CPUS > 1)
653 if (mode == parallel) {
654 Lock(lock_smp);
655 Lock(tree->parent->lock);
656 if (!tree->stop) {
657 int proc;
658
659 parallel_aborts++;
660 for (proc = 0; proc < smp_max_threads; proc++)
661 if (tree->parent->siblings[proc] && proc != tree->thread_id)
662 ThreadStop(tree->parent->siblings[proc]);
663 }
664 Unlock(tree->parent->lock);
665 Unlock(lock_smp);
666 return beta;
667 }
668 #endif
669 tree->fail_highs++;
670 if (order == 1)
671 tree->fail_high_first_move++;
672 HashStore(tree, ply, depth, wtm, LOWER, value, tree->curmv[ply]);
673 History(tree, ply, depth, wtm, tree->curmv[ply], searched);
674 return beta;
675 /*
676 ************************************************************
677 * *
678 * Test 2. If search_result = IN_WINDOW, this is a search *
679 * that improved alpha without failing high. We simply *
680 * update alpha and continue searching moves. *
681 * *
682 * Special case: If ply = 1 in a normal search, we have *
683 * a best move and score that just changed. We need to *
684 * update the root move list by adding the PV and the *
685 * score, and then we look to make sure this new "best *
686 * move" is not actually worse than the best we have found *
687 * so far this iteration. If it is worse, we restore the *
688 * best move and score from the real best move so our *
689 * search window won't be out of whack, which would let *
690 * moves with scores in between this bad move and the best *
691 * move fail high, cause re-searches, and waste time. We *
692 * also need to restore the root move list so that the *
693 * best move (the one we just used to replace the move *
694 * with a worse score) is first so it is searched first on *
695 * the next iteration. *
696 * *
697 * If this is ply = 1, we display the PV to keep the user *
698 * informed. *
699 * *
700 ************************************************************
701 */
702 } else if (search_result == IN_WINDOW) {
703 alpha = value;
704 if (ply == 1 && mode == serial) {
705 int best;
706
707 //
708 // update path/score for this move
709 //
710 tree->pv[1].pathv = value;
711 tree->pv[0] = tree->pv[1];
712 for (best = 0; best < n_root_moves; best++)
713 if (root_moves[best].move == tree->pv[1].path[1]) {
714 root_moves[best].path = tree->pv[1];
715 root_moves[best].path.pathv = alpha;
716 break;
717 }
718 //
719 // if this move is not #1 in root list, move it there
720 //
721 if (best != 0) {
722 ROOT_MOVE t;
723 t = root_moves[best];
724 for (i = best; i > 0; i--)
725 root_moves[i] = root_moves[i - 1];
726 root_moves[0] = t;
727 }
728 //
729 // if a better score has already been found then move that
730 // move to the front of the list and update alpha bound.
731 //
732 for (i = 0; i < n_root_moves; i++) {
733 if (value <= root_moves[i].path.pathv) {
734 ROOT_MOVE t;
735 value = root_moves[i].path.pathv;
736 alpha = value;
737 tree->pv[0] = root_moves[i].path;
738 tree->pv[1] = tree->pv[0];
739 t = root_moves[i];
740 for (j = i; j > 0; j--)
741 root_moves[j] = root_moves[j - 1];
742 root_moves[0] = t;
743 }
744 }
745 Output(tree);
746 failhi_delta = 16;
747 faillo_delta = 16;
748 }
749 }
750 /*
751 ************************************************************
752 * *
753 * Test 3. If search_result = ILLEGAL, this search was *
754 * given an illegal move and no search was done, we skip *
755 * any updating and simply select the next move to search. *
756 * *
757 ************************************************************
758 */
759 else if (search_result == ILLEGAL)
760 continue;
761 t_beta = alpha + 1;
762 /*
763 ************************************************************
764 * *
765 * SMP. If are doing an SMP search, and we have idle *
766 * processors, now is the time to get them involved. We *
767 * have now satisfied the "young brothers wait" condition *
768 * since we have searched at least one move. All that is *
769 * left is to check the split constraints to see if this *
770 * is an acceptable split point. *
771 * *
772 * (1) We can't split within N plies of the frontier *
773 * nodes to avoid excessive split overhead. *
774 * *
775 * (2) We can't split until at least N nodes have been *
776 * searched since this thread was last split, to *
777 * avoid splitting too often, mainly in endgames. *
778 * *
779 * (3) We have to have searched one legal move to avoid *
780 * splitting at a node where we have no legal moves *
781 * (the first move tried might have been illegal as *
782 * in when we encounter a stalemate). *
783 * *
784 * (4) If we are at ply=1, we can't split unless the *
785 * smp_split_at_root flag is set to 1, AND the next *
786 * move in the ply=1 move list is not flagged as *
787 * "do not search in parallel" which happens when *
788 * this move was a best move in the last couple of *
789 * searches and we want all processors on it at once *
790 * to get a score back quicker. *
791 * *
792 * (5) if the variable smp_split is != 0, we have idle *
793 * threads that can help, which means we want to get *
794 * them involved quickly, OR if this node is an *
795 * acceptable "gratuitous-split" point by being far *
796 * enough from the tips of the tree to avoid *
797 * excessive overhead. *
798 * *
799 * We use this code recursively to perform a parallel *
800 * search at this ply. But when we finish a partial piece *
801 * of the search in parallel, we don't need to update any *
802 * search data structures, we will defer that until all of *
803 * parallel threads complete and return back into this *
804 * code after the parallel search has been collapsed back *
805 * to one instance of search at this ply. *
806 * *
807 * Special case: we do not split if we are at ply=1 and *
808 * alpha == original_alpha. That means the first move *
809 * failed low, and we are going to exit search and return *
810 * to Iterate() to report this. *
811 * *
812 * In Generation II, multiple threads can reach this point *
813 * at the same time. We allow multiple threads to split *
814 * at the same time, but then the idle threads will choose *
815 * to join the thread with the most attractive split point *
816 * rather than just taking pot-luck. The only limitation *
817 * on a thread adding a split point here is that if the *
818 * thread already has enough joinable split points that *
819 * have not been joined yet, we do not incur the overhead *
820 * of creating another split point until one of the *
821 * existing split points has been completed or a thread *
822 * joins at at one of those available split points. *
823 * *
824 * We do not lock anything here, as the split operation *
825 * only affects thread-local data. When the split is done *
826 * then the ThreadJoin() function will acquire the lock *
827 * needed to avoid race conditions during the join op- *
828 * eration. *
829 * *
830 ************************************************************
831 */
832 #if (CPUS > 1)
833 if (mode == serial && moves_done && smp_threads &&
834 ThreadSplit(tree, ply, depth, alpha, original_alpha, moves_done))
835 do {
836 tree->alpha = alpha;
837 tree->beta = beta;
838 tree->value = alpha;
839 tree->wtm = wtm;
840 tree->ply = ply;
841 tree->depth = depth;
842 tree->in_check = in_check;
843 tree->searched = searched;
844 if (Split(tree)) {
845 if (abort_search || tree->stop)
846 return 0;
847 value = tree->value;
848 if (value > alpha) {
849 if (ply == 1)
850 tree->pv[0] = tree->pv[1];
851 if (value >= beta) {
852 HashStore(tree, ply, depth, wtm, LOWER, value, tree->cutmove);
853 return value;
854 }
855 alpha = value;
856 break;
857 }
858 }
859 } while (0);
860 #endif
861 }
862 /*
863 ************************************************************
864 * *
865 * SMP Cleanup. If we are doing an SMP search, there are *
866 * no "end-of-search" things to do. We have searched all *
867 * the remaining moves at this ply in parallel, and now *
868 * return and let the original search that started this *
869 * sub-tree clean up, do the tests for mate/stalemate, *
870 * update the hash table, etc. *
871 * *
872 * As we return, we end back up in Thread() where we *
873 * started, which then copies the best score/etc back to *
874 * the parent thread. *
875 * *
876 ************************************************************
877 */
878 if (abort_search || tree->stop || mode == parallel)
879 return alpha;
880 /*
881 ************************************************************
882 * *
883 * Search completed. All moves have been searched. If *
884 * none were legal, return either MATE or DRAW depending *
885 * on whether the side to move is in check or not. *
886 * *
887 ************************************************************
888 */
889 if (moves_done == 0) {
890 value = (Check(wtm)) ? -(MATE - ply) : DrawScore(wtm);
891 if (value >= alpha && value < beta) {
892 SavePV(tree, ply, 0);
893 #if defined(TRACE)
894 if (ply <= trace_level)
895 printf("Search() no moves! ply=%d\n", ply);
896 #endif
897 }
898 return value;
899 } else {
900 bestmove =
901 (alpha ==
902 original_alpha) ? tree->hash_move[ply] : tree->pv[ply].path[ply];
903 type = (alpha == original_alpha) ? UPPER : EXACT;
904 if (repeat == 2 && alpha != -(MATE - ply - 1)) {
905 value = DrawScore(wtm);
906 if (value < beta)
907 SavePV(tree, ply, 3);
908 #if defined(TRACE)
909 if (ply <= trace_level)
910 printf("draw by 50 move rule detected, ply=%d.\n", ply);
911 #endif
912 return value;
913 } else if (alpha != original_alpha) {
914 tree->pv[ply - 1] = tree->pv[ply];
915 tree->pv[ply - 1].path[ply - 1] = tree->curmv[ply - 1];
916 }
917 HashStore(tree, ply, depth, wtm, type, alpha, bestmove);
918 return alpha;
919 }
920 }
921
922 /* last modified 08/03/16 */
923 /*
924 *******************************************************************************
925 * *
926 * SearchMove() implements the PVS search and returns the value. We do a *
927 * null-window search with the window (alpha, t_beta) and if that fails high *
928 * we repeat the search with the window {alpha, beta} assuming that beta != *
929 * t_beta. *
930 * *
931 *******************************************************************************
932 */
SearchMove(TREE * RESTRICT tree,int ply,int depth,int wtm,int alpha,int t_beta,int beta,int extend,int reduce,int check)933 int SearchMove(TREE * RESTRICT tree, int ply, int depth, int wtm, int alpha,
934 int t_beta, int beta, int extend, int reduce, int check) {
935 int value;
936 /*
937 ************************************************************
938 * *
939 * PVS search. We have determined whether the depth is to *
940 * be changed by an extension or a reduction. If we get *
941 * to this point, then the move is not being pruned. So *
942 * off we go to a recursive search/quiescence call to work *
943 * our way toward a terminal node. *
944 * *
945 * There is one special-case to handle. If the depth was *
946 * reduced, and Search() returns a value >= beta then *
947 * accepting that is risky (we reduced the move as we *
948 * thought it was bad and expected it to fail low) so we *
949 * repeat the search using the original (non-reduced) *
950 * depth to see if the fail-high happens again. *
951 * *
952 ************************************************************
953 */
954 if (depth + extend - reduce - 1 > 0) {
955 value =
956 -Search(tree, ply + 1, depth + extend - reduce - 1, Flip(wtm),
957 -t_beta, -alpha, check, DO_NULL);
958 if (value > alpha && reduce) {
959 value =
960 -Search(tree, ply + 1, depth - 1, Flip(wtm), -t_beta, -alpha, check,
961 DO_NULL);
962 }
963 } else
964 value = -Quiesce(tree, ply + 1, Flip(wtm), -t_beta, -alpha, 1);
965 if (abort_search || tree->stop)
966 return 0;
967 /*
968 ************************************************************
969 * *
970 * PVS re-search. This is the PVS re-search code. If we *
971 * reach this point and value > alpha and value < beta, *
972 * then this can not be a null-window search. We have to *
973 * re-search the position with the original beta value *
974 * to see if it still fails high before we treat this as a *
975 * real fail-high and back up the value to the previous *
976 * ply. *
977 * *
978 ************************************************************
979 */
980 if (value > alpha && value < beta && t_beta < beta) {
981 if (ply == 1)
982 return beta;
983 if (depth + extend - 1 > 0)
984 value =
985 -Search(tree, ply + 1, depth + extend - 1, Flip(wtm), -beta, -alpha,
986 check, DO_NULL);
987 else
988 value = -Quiesce(tree, ply + 1, Flip(wtm), -beta, -alpha, 1);
989 if (abort_search || tree->stop)
990 return 0;
991 }
992 return value;
993 }
994