Subversion Repositories Games.Chess Giants

Rev

Rev 33 | Go to most recent revision | Show entire file | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed

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