Subversion Repositories Games.Chess Giants

Rev

Rev 33 | Rev 154 | 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/15/14 */
 - 
 
4 
/*
 - 
 
5 
 *******************************************************************************
 - 
 
6 
 *                                                                             *
 - 
 
7 
 *   NextEvasion() is used to select the next move from the current move list  *
 - 
 
8 
 *   when the king is in check.  We use GenerateEvasions() (in movgen.c) to    *
 - 
 
9 
 *   generate a list of moves that get us out of check.  The only unusual      *
 - 
 
10 
 *   feature is that these moves are all legal and do not need to be vetted    *
 - 
 
11 
 *   with the usual Check() function to test for legality.                     *
 - 
 
12 
 *                                                                             *
 - 
 
13 
 *******************************************************************************
 - 
 
14 
 */
 - 
 
15 
int NextEvasion(TREE * RESTRICT tree, int ply, int wtm) {
 - 
 
16 
  int *movep, *sortv;
 - 
 
17 
 
 - 
 
18 
  switch (tree->next_status[ply].phase) {
 - 
 
19 
/*
 - 
 
20 
 ************************************************************
 - 
 
21 
 *                                                          *
 - 
 
22 
 *  First try the transposition table move (which might be  *
 - 
 
23 
 *  the principal variation move as we first move down the  *
 - 
 
24 
 *  tree).  If it is good enough to cause a cutoff, we      *
 - 
 
25 
 *  avoided the overhead of generating legal moves.         *
 - 
 
26 
 *                                                          *
 - 
 
27 
 ************************************************************
 - 
 
28 
 */
 - 
 
29 
    case HASH_MOVE:
 - 
 
30 
      if (tree->hash_move[ply]) {
 - 
 
31 
        tree->next_status[ply].phase = GENERATE_ALL_MOVES;
 - 
 
32 
        tree->curmv[ply] = tree->hash_move[ply];
 - 
 
33 
        if (ValidMove(tree, ply, wtm, tree->curmv[ply]))
 - 
 
34 
          return HASH_MOVE;
 - 
 
35 
#if defined(DEBUG)
 - 
 
36 
        else
 - 
 
37 
          Print(128, "bad move from hash table, ply=%d\n", ply);
 - 
 
38 
#endif
 - 
 
39 
      }
 - 
 
40 
/*
 - 
 
41 
 ************************************************************
 - 
 
42 
 *                                                          *
 - 
 
43 
 *  Now generate all legal moves by using the special       *
 - 
 
44 
 *  GenerateCheckEvasions() procedure.  Then sort the moves *
 - 
 
45 
 *  based on the expected gain or loss.  this is deferred   *
 - 
 
46 
 *  until now to see if the hash move is good enough to     *
 - 
 
47 
 *  produce a cutoff and avoid this effort.                 *
 - 
 
48 
 *                                                          *
 - 
 
49 
 *  Once we confirm that the move does not lose any         *
 - 
 
50 
 *  material, we sort these non-losing moves into MVV/LVA   *
 - 
 
51 
 *  order which appears to be a slightly faster move        *
 - 
 
52 
 *  ordering idea.  Unsafe evasion moves are sorted using   *
 - 
 
53 
 *  the original Swap() score to keep them last in the move *
 - 
 
54 
 *  list.  Note that this move list contains both captures  *
 - 
 
55 
 *  and non-captures.  We try the safe captures first due   *
 - 
 
56 
 *  to the way the sort score is computed.                  *
 - 
 
57 
 *                                                          *
 - 
 
58 
 ************************************************************
 - 
 
59 
 */
 - 
 
60 
    case GENERATE_ALL_MOVES:
 - 
 
61 
      tree->last[ply] =
 - 
 
62 
          GenerateCheckEvasions(tree, ply, wtm, tree->last[ply - 1]);
 - 
 
63 
      tree->next_status[ply].phase = REMAINING_MOVES;
 - 
 
64 
      for (movep = tree->last[ply - 1], sortv = tree->sort_value;
 - 
 
65 
          movep < tree->last[ply]; movep++, sortv++)
 - 
 
66 
        if (tree->hash_move[ply] && *movep == tree->hash_move[ply]) {
 - 
 
67 
          *sortv = -999999;
 - 
 
68 
          *movep = 0;
 - 
 
69 
        } else {
 - 
 
70 
          if (pcval[Piece(*movep)] <= pcval[Captured(*movep)])
 - 
 
71 
            *sortv = 128 * pcval[Captured(*movep)] - pcval[Piece(*movep)];
 - 
 
72 
          else {
 - 
 
73 
            *sortv = Swap(tree, *movep, wtm);
 - 
 
74 
            if (*sortv >= 0)
 - 
 
75 
              *sortv = 128 * pcval[Captured(*movep)] - pcval[Piece(*movep)];
 - 
 
76 
          }
 - 
 
77 
        }
 - 
 
78 
/*
 - 
 
79 
 ************************************************************
 - 
 
80 
 *                                                          *
 - 
 
81 
 *  This is a simple insertion sort algorithm.  It seems be *
 - 
 
82 
 *  be no faster than a normal bubble sort, but using this  *
 - 
 
83 
 *  eliminated a lot of explaining about "why?". :)         *
 - 
 
84 
 *                                                          *
 - 
 
85 
 ************************************************************
 - 
 
86 
 */
 - 
 
87 
      if (tree->last[ply] > tree->last[ply - 1] + 1) {
 - 
 
88 
        int temp1, temp2, *tmovep, *tsortv, *end;
 - 
 
89 
 
 - 
 
90 
        sortv = tree->sort_value + 1;
 - 
 
91 
        end = tree->last[ply];
 - 
 
92 
        for (movep = tree->last[ply - 1] + 1; movep < end; movep++, sortv++) {
 - 
 
93 
          temp1 = *movep;
 - 
 
94 
          temp2 = *sortv;
 - 
 
95 
          tmovep = movep - 1;
 - 
 
96 
          tsortv = sortv - 1;
 - 
 
97 
          while (tmovep >= tree->last[ply - 1] && *tsortv < temp2) {
 - 
 
98 
            *(tsortv + 1) = *tsortv;
 - 
 
99 
            *(tmovep + 1) = *tmovep;
 - 
 
100 
            tmovep--;
 - 
 
101 
            tsortv--;
 - 
 
102 
          }
 - 
 
103 
          *(tmovep + 1) = temp1;
 - 
 
104 
          *(tsortv + 1) = temp2;
 - 
 
105 
        }
 - 
 
106 
      }
 - 
 
107 
      tree->next_status[ply].last = tree->last[ply - 1];
 - 
 
108 
/*
 - 
 
109 
 ************************************************************
 - 
 
110 
 *                                                          *
 - 
 
111 
 *  Now try the moves in sorted order.                      *
 - 
 
112 
 *                                                          *
 - 
 
113 
 ************************************************************
 - 
 
114 
 */
 - 
 
115 
    case REMAINING_MOVES:
 - 
 
116 
      for (; tree->next_status[ply].last < tree->last[ply];
 - 
 
117 
          tree->next_status[ply].last++)
 - 
 
118 
        if (*tree->next_status[ply].last) {
 - 
 
119 
          tree->curmv[ply] = *tree->next_status[ply].last++;
 - 
 
120 
          return REMAINING_MOVES;
 - 
 
121 
        }
 - 
 
122 
      return NONE;
 - 
 
123 
    default:
 - 
 
124 
      printf("oops!  next_status.phase is bad! [evasion %d]\n",
 - 
 
125 
          tree->next_status[ply].phase);
 - 
 
126 
  }
 - 
 
127 
  return NONE;
 - 
 
128 
}
 - 
 
129 
 
 - 
 
130 
/* last modified 05/15/14 */
 3 
/* last modified 12/29/15 */
131 
/*
 4 
/*
132 
 *******************************************************************************
 5 
 *******************************************************************************
133 
 *                                                                             *
 6 
 *                                                                             *
134 
 *   NextMove() is used to select the next move from the current move list.    *
 7 
 *   NextMove() is used to select the next move from the current move list.    *
135 
 *                                                                             *
 8 
 *                                                                             *
Line 138... Line 11...
138 
 *   save them in the NEXT structure and make sure to exclude them when        *
 11 
 *   save them in the NEXT structure and make sure to exclude them when        *
139 
 *   searching after a move generation to avoid the duplicated effort.         *
 12 
 *   searching after a move generation to avoid the duplicated effort.         *
140 
 *                                                                             *
 13 
 *                                                                             *
141 
 *******************************************************************************
 14 
 *******************************************************************************
142 
 */
 15 
 */
143 
int NextMove(TREE * RESTRICT tree, int ply, int wtm) {
 16 
int NextMove(TREE * RESTRICT tree, int ply, int depth, int side, int in_check) {
144 
  int *movep, *sortv;
 17 
  unsigned *movep, *bestp;
- 
 
 18 
  int hist, bestval, possible;
145 
 
 19 
 
- 
 
 20 
/*
- 
 
 21 
 ************************************************************
- 
 
 22 
 *                                                          *
- 
 
 23 
 *  The following "big switch" controls the finate state    *
- 
 
 24 
 *  machine that selects moves.  The "phase" value in the   *
- 
 
 25 
 *  next_status[ply] structure is always set after a move   *
- 
 
 26 
 *  is selected, and it defines the next state of the FSM   *
- 
 
 27 
 *  so select the next move in a sequenced order.           *
- 
 
 28 
 *                                                          *
- 
 
 29 
 ************************************************************
- 
 
 30 
 */
146 
  switch (tree->next_status[ply].phase) {
 31 
  switch (tree->next_status[ply].phase) {
147 
/*
 32 
/*
148 
 ************************************************************
 33 
 ************************************************************
149 
 *                                                          *
 34 
 *                                                          *
150 
 *  First, try the transposition table move (which will be  *
 35 
 *  First, try the transposition table move (which will be  *
151 
 *  the principal variation move as we first move down the  *
 36 
 *  the principal variation move as we first move down the  *
- 
 
 37 
 *  tree) or the best move found in this position during a  *
152 
 *  tree).                                                  *
 38 
 *  prior search.                                           *
153 
 *                                                          *
 39 
 *                                                          *
154 
 ************************************************************
 40 
 ************************************************************
155 
 */
 41 
 */
156 
    case HASH_MOVE:
 42 
    case HASH:
157 
      tree->next_status[ply].num_excluded = 0;
 43 
      tree->next_status[ply].order = 0;
- 
 
 44 
      tree->next_status[ply].exclude = &tree->next_status[ply].done[0];
158 
      tree->next_status[ply].phase = GENERATE_CAPTURE_MOVES;
 45 
      tree->next_status[ply].phase = GENERATE_CAPTURES;
159 
      if (tree->hash_move[ply]) {
 46 
      if (tree->hash_move[ply]) {
160 
        tree->curmv[ply] = tree->hash_move[ply];
 47 
        tree->curmv[ply] = tree->hash_move[ply];
161 
        tree->next_status[ply].excluded_moves[tree->next_status[ply].
 48 
        *(tree->next_status[ply].exclude++) = tree->curmv[ply];
162 
            num_excluded++]
 49 
        if (ValidMove(tree, ply, side, tree->curmv[ply])) {
163 
            = tree->curmv[ply];
 50 
          tree->phase[ply] = HASH;
164 
        if (ValidMove(tree, ply, wtm, tree->curmv[ply]))
 51 
          return ++tree->next_status[ply].order;
165 
          return HASH_MOVE;
 52 
        }
166 
#if defined(DEBUG)
 53 
#if defined(DEBUG)
167 
        else
 54 
        else
168 
          Print(128, "bad move from hash table, ply=%d\n", ply);
 55 
          Print(2048, "ERROR:  bad move from hash table, ply=%d\n", ply);
169 
#endif
 56 
#endif
170 
      }
 57 
      }
171 
/*
 58 
/*
172 
 ************************************************************
 59 
 ************************************************************
173 
 *                                                          *
 60 
 *                                                          *
Line 175... Line 62...
175 
 *  MVV/LVA ordering where we try to capture the most       *
 62 
 *  MVV/LVA ordering where we try to capture the most       *
176 
 *  valuable victim piece possible, using the least         *
 63 
 *  valuable victim piece possible, using the least         *
177 
 *  valuable attacking piece possible.  Later we will test  *
 64 
 *  valuable attacking piece possible.  Later we will test  *
178 
 *  to see if the capture appears to lose material and we   *
 65 
 *  to see if the capture appears to lose material and we   *
179 
 *  will defer searching it until later.                    *
 66 
 *  will defer searching it until later.                    *
- 
 
 67 
 *                                                          *
- 
 
 68 
 *  Or, if in check, generate all the legal moves that      *
- 
 
 69 
 *  escape check by using GenerateCheckEvasions().  After   *
- 
 
 70 
 *  we do this, we sort them using MVV/LVA to move captures *
- 
 
 71 
 *  to the front of the list in the correct order.          *
180 
 *                                                          *
 72 
 *                                                          *
181 
 ************************************************************
 73 
 ************************************************************
182 
 */
 74 
 */
183 
    case GENERATE_CAPTURE_MOVES:
 75 
    case GENERATE_CAPTURES:
184 
      tree->next_status[ply].phase = CAPTURE_MOVES;
 76 
      tree->next_status[ply].phase = CAPTURES;
185 
      tree->last[ply] = GenerateCaptures(tree, ply, wtm, tree->last[ply - 1]);
 - 
 
186 
      tree->next_status[ply].remaining = 0;
 - 
 
187 
      for (movep = tree->last[ply - 1], sortv = tree->sort_value;
 - 
 
188 
          movep < tree->last[ply]; movep++, sortv++)
 - 
 
189 
        if (*movep == tree->hash_move[ply]) {
 - 
 
190 
          *sortv = -999999;
 77 
      if (!in_check)
191 
          *movep = 0;
 78 
        tree->last[ply] =
192 
          tree->next_status[ply].num_excluded = 0;
 79 
            GenerateCaptures(tree, ply, side, tree->last[ply - 1]);
193 
        } else {
 80 
      else
194 
          *sortv = 128 * pcval[Captured(*movep)] - pcval[Piece(*movep)];
 81 
        tree->last[ply] =
195 
          tree->next_status[ply].remaining++;
 82 
            GenerateCheckEvasions(tree, ply, side, tree->last[ply - 1]);
196 
        }
 - 
 
197 
/*
 83 
/*
198 
 ************************************************************
 84 
 ************************************************************
199 
 *                                                          *
 85 
 *                                                          *
- 
 
 86 
 *  Now make a pass over the moves to assign the sort value *
200 
 *  This is a simple insertion sort algorithm.  It seems to *
 87 
 *  for each.  We simply use MVV/LVA move order here.  A    *
201 
 *  be no faster than a normal bubble sort, but using this  *
 88 
 *  simple optimization is to use the pre-computed array    *
- 
 
 89 
 *  MVV_LVA[victim][attacker] which returns a simple value  *
202 
 *  eliminated a lot of explaining about "why?". :)         *
 90 
 *  that indicates MVV/LVA order.                           *
203 
 *                                                          *
 91 
 *                                                          *
204 
 ************************************************************
 92 
 ************************************************************
205 
 */
 93 
 */
206 
      if (tree->last[ply] > tree->last[ply - 1] + 1) {
 94 
      tree->next_status[ply].remaining = 0;
207 
        int temp1, temp2, *tmovep, *tsortv, *end;
 - 
 
208 
 
 - 
 
209 
        sortv = tree->sort_value + 1;
 - 
 
210 
        end = tree->last[ply];
 - 
 
211 
        for (movep = tree->last[ply - 1] + 1; movep < end; movep++, sortv++) {
 95 
      for (movep = tree->last[ply - 1]; movep < tree->last[ply]; movep++)
212 
          temp1 = *movep;
 96 
        if (*movep == tree->hash_move[ply]) {
213 
          temp2 = *sortv;
 - 
 
214 
          tmovep = movep - 1;
 97 
          *movep = 0;
215 
          tsortv = sortv - 1;
 - 
 
216 
          while (tmovep >= tree->last[ply - 1] && *tsortv < temp2) {
 98 
          tree->next_status[ply].exclude = &tree->next_status[ply].done[0];
217 
            *(tsortv + 1) = *tsortv;
 - 
 
218 
            *(tmovep + 1) = *tmovep;
 - 
 
219 
            tmovep--;
 - 
 
220 
            tsortv--;
 - 
 
221 
          }
 99 
        } else {
222 
          *(tmovep + 1) = temp1;
 100 
          *movep += MVV_LVA[Captured(*movep)][Piece(*movep)];
223 
          *(tsortv + 1) = temp2;
 101 
          tree->next_status[ply].remaining++;
224 
        }
 102 
        }
225 
      }
 103 
      NextSort(tree, ply);
226 
      tree->next_status[ply].last = tree->last[ply - 1];
 104 
      tree->next_status[ply].last = tree->last[ply - 1];
- 
 
 105 
      if (in_check)
- 
 
 106 
        goto remaining_moves;
227 
/*
 107 
/*
228 
 ************************************************************
 108 
 ************************************************************
229 
 *                                                          *
 109 
 *                                                          *
230 
 *  Try the captures moves, which are in order based on     *
 110 
 *  Try the captures moves, which are in order based on     *
231 
 *  MVV/LVA ordering.  If a larger-valued piece captures a  *
 111 
 *  MVV/LVA ordering.  If a larger-valued piece captures a  *
232 
 *  lesser-valued piece, and Swap() says it loses material, *
 112 
 *  lesser-valued piece, and SEE() says it loses material,  *
233 
 *  this capture will be deferred until later.              *
 113 
 *  this capture will be deferred until later.              *
- 
 
 114 
 *                                                          *
- 
 
 115 
 *  If we are in check, we jump down to the history moves   *
- 
 
 116 
 *  phase (we don't need to generate any more moves as      *
- 
 
 117 
 *  GenerateCheckEvasions has already generated all legal   *
- 
 
 118 
 *  moves.                                                  *
234 
 *                                                          *
 119 
 *                                                          *
235 
 ************************************************************
 120 
 ************************************************************
236 
 */
 121 
 */
237 
    case CAPTURE_MOVES:
 122 
    case CAPTURES:
238 
      while (tree->next_status[ply].remaining) {
 123 
      while (tree->next_status[ply].remaining) {
239 
        tree->curmv[ply] = *(tree->next_status[ply].last++);
 124 
        tree->curmv[ply] = Move(*(tree->next_status[ply].last++));
240 
        if (!--tree->next_status[ply].remaining)
 125 
        if (!--tree->next_status[ply].remaining)
241 
          tree->next_status[ply].phase = KILLER_MOVE_1;
 126 
          tree->next_status[ply].phase = KILLER1;
242 
        if (pcval[Piece(tree->curmv[ply])] > pcval[Captured(tree->curmv[ply])]
 127 
        if (pcval[Piece(tree->curmv[ply])] <=
243 
            && Swap(tree, tree->curmv[ply], wtm) < 0)
 128 
            pcval[Captured(tree->curmv[ply])]
244 
          continue;
 129 
            || SEE(tree, side, tree->curmv[ply]) >= 0) {
245 
        *(tree->next_status[ply].last - 1) = 0;
 130 
          *(tree->next_status[ply].last - 1) = 0;
246 
        return CAPTURE_MOVES;
 131 
          tree->phase[ply] = CAPTURES;
- 
 
 132 
          return ++tree->next_status[ply].order;
- 
 
 133 
        }
247 
      }
 134 
      }
248 
/*
 135 
/*
249 
 ************************************************************
 136 
 ************************************************************
250 
 *                                                          *
 137 
 *                                                          *
251 
 *  Now, try the killer moves.  This phase tries the two    *
 138 
 *  Now, try the killer moves.  This phase tries the two    *
Line 255... Line 142...
255 
 *  back since they have greater depth and might produce a  *
 142 
 *  back since they have greater depth and might produce a  *
256 
 *  cutoff if the current two do not.                       *
 143 
 *  cutoff if the current two do not.                       *
257 
 *                                                          *
 144 
 *                                                          *
258 
 ************************************************************
 145 
 ************************************************************
259 
 */
 146 
 */
260 
    case KILLER_MOVE_1:
 147 
    case KILLER1:
- 
 
 148 
      possible = tree->killers[ply].move1;
261 
      if (!Exclude(tree, ply, tree->killers[ply].move1) &&
 149 
      if (!Exclude(tree, ply, possible) &&
262 
          ValidMove(tree, ply, wtm, tree->killers[ply].move1)) {
 150 
          ValidMove(tree, ply, side, possible)) {
263 
        tree->curmv[ply] = tree->killers[ply].move1;
 151 
        tree->curmv[ply] = possible;
264 
        tree->next_status[ply].excluded_moves[tree->next_status[ply].
 152 
        *(tree->next_status[ply].exclude++) = possible;
265 
            num_excluded++]
 - 
 
266 
            = tree->curmv[ply];
 153 
        tree->next_status[ply].phase = KILLER2;
267 
        tree->next_status[ply].phase = KILLER_MOVE_2;
 154 
        tree->phase[ply] = KILLER1;
268 
        return KILLER_MOVE_1;
 155 
        return ++tree->next_status[ply].order;
269 
      }
 156 
      }
270 
    case KILLER_MOVE_2:
 157 
    case KILLER2:
- 
 
 158 
      possible = tree->killers[ply].move2;
271 
      if (!Exclude(tree, ply, tree->killers[ply].move2) &&
 159 
      if (!Exclude(tree, ply, possible) &&
272 
          ValidMove(tree, ply, wtm, tree->killers[ply].move2)) {
 160 
          ValidMove(tree, ply, side, possible)) {
273 
        tree->curmv[ply] = tree->killers[ply].move2;
 161 
        tree->curmv[ply] = possible;
274 
        tree->next_status[ply].excluded_moves[tree->next_status[ply].
 162 
        *(tree->next_status[ply].exclude++) = possible;
275 
            num_excluded++]
 - 
 
276 
            = tree->curmv[ply];
 - 
 
277 
        if (ply < 3) {
 - 
 
278 
          tree->next_status[ply].phase = GENERATE_ALL_MOVES;
 163 
        tree->next_status[ply].phase = (ply < 3) ? COUNTER_MOVE1 : KILLER3;
279 
        } else
 - 
 
280 
          tree->next_status[ply].phase = KILLER_MOVE_3;
 164 
        tree->phase[ply] = KILLER2;
281 
        return KILLER_MOVE_2;
 165 
        return ++tree->next_status[ply].order;
282 
      }
 166 
      }
283 
    case KILLER_MOVE_3:
 167 
    case KILLER3:
284 
      if (!Exclude(tree, ply, tree->killers[ply - 2].move1) &&
 168 
      possible = tree->killers[ply - 2].move1;
- 
 
 169 
      if (!Exclude(tree, ply, possible) &&
285 
          ValidMove(tree, ply, wtm, tree->killers[ply - 2].move1)) {
 170 
          ValidMove(tree, ply, side, possible)) {
- 
 
 171 
        tree->curmv[ply] = possible;
- 
 
 172 
        *(tree->next_status[ply].exclude++) = possible;
- 
 
 173 
        tree->next_status[ply].phase = KILLER4;
- 
 
 174 
        tree->phase[ply] = KILLER3;
- 
 
 175 
        return ++tree->next_status[ply].order;
- 
 
 176 
      }
- 
 
 177 
    case KILLER4:
286 
        tree->curmv[ply] = tree->killers[ply - 2].move1;
 178 
      possible = tree->killers[ply - 2].move2;
- 
 
 179 
      if (!Exclude(tree, ply, possible) &&
- 
 
 180 
          ValidMove(tree, ply, side, possible)) {
- 
 
 181 
        tree->curmv[ply] = possible;
287 
        tree->next_status[ply].excluded_moves[tree->next_status[ply].
 182 
        *(tree->next_status[ply].exclude++) = possible;
- 
 
 183 
        tree->next_status[ply].phase = COUNTER_MOVE1;
288 
            num_excluded++]
 184 
        tree->phase[ply] = KILLER4;
- 
 
 185 
        return ++tree->next_status[ply].order;
- 
 
 186 
      }
- 
 
 187 
/*
- 
 
 188 
 ************************************************************
- 
 
 189 
 *                                                          *
- 
 
 190 
 *  Now, before we give up and generate moves, try the      *
- 
 
 191 
 *  counter-move which was a move that failed high in the   *
- 
 
 192 
 *  past when the move at the previous ply was played.      *
- 
 
 193 
 *                                                          *
- 
 
 194 
 ************************************************************
- 
 
 195 
 */
- 
 
 196 
    case COUNTER_MOVE1:
- 
 
 197 
      possible = counter_move[tree->curmv[ply - 1] & 4095].move1;
- 
 
 198 
      if (!Exclude(tree, ply, possible) &&
- 
 
 199 
          ValidMove(tree, ply, side, possible)) {
289 
            = tree->curmv[ply];
 200 
        tree->curmv[ply] = possible;
- 
 
 201 
        *(tree->next_status[ply].exclude++) = possible;
290 
        tree->next_status[ply].phase = KILLER_MOVE_4;
 202 
        tree->next_status[ply].phase = COUNTER_MOVE2;
- 
 
 203 
        tree->phase[ply] = COUNTER_MOVE1;
- 
 
 204 
        return ++tree->next_status[ply].order;
- 
 
 205 
      }
291 
        return KILLER_MOVE_3;
 206 
    case COUNTER_MOVE2:
- 
 
 207 
      possible = counter_move[tree->curmv[ply - 1] & 4095].move2;
- 
 
 208 
      if (!Exclude(tree, ply, possible) &&
- 
 
 209 
          ValidMove(tree, ply, side, possible)) {
- 
 
 210 
        tree->curmv[ply] = possible;
- 
 
 211 
        *(tree->next_status[ply].exclude++) = possible;
- 
 
 212 
        tree->next_status[ply].phase = MOVE_PAIR1;
- 
 
 213 
        tree->phase[ply] = COUNTER_MOVE2;
- 
 
 214 
        return ++tree->next_status[ply].order;
- 
 
 215 
      }
- 
 
 216 
/*
- 
 
 217 
 ************************************************************
- 
 
 218 
 *                                                          *
- 
 
 219 
 *  Finally we try paired moves, which are simply moves     *
- 
 
 220 
 *  that were good when played after the other move in the  *
- 
 
 221 
 *  pair was played two plies back.                         *
- 
 
 222 
 *                                                          *
- 
 
 223 
 ************************************************************
- 
 
 224 
 */
- 
 
 225 
    case MOVE_PAIR1:
- 
 
 226 
      possible = move_pair[tree->curmv[ply - 2] & 4095].move1;
- 
 
 227 
      if (!Exclude(tree, ply, possible) &&
- 
 
 228 
          ValidMove(tree, ply, side, possible)) {
- 
 
 229 
        tree->curmv[ply] = possible;
- 
 
 230 
        *(tree->next_status[ply].exclude++) = possible;
- 
 
 231 
        tree->next_status[ply].phase = MOVE_PAIR2;
- 
 
 232 
        tree->phase[ply] = MOVE_PAIR1;
- 
 
 233 
        return ++tree->next_status[ply].order;
292 
      }
 234 
      }
293 
    case KILLER_MOVE_4:
 235 
    case MOVE_PAIR2:
- 
 
 236 
      possible = move_pair[tree->curmv[ply - 2] & 4095].move2;
294 
      if (!Exclude(tree, ply, tree->killers[ply - 2].move2) &&
 237 
      if (!Exclude(tree, ply, possible) &&
295 
          ValidMove(tree, ply, wtm, tree->killers[ply - 2].move2)) {
 238 
          ValidMove(tree, ply, side, possible)) {
296 
        tree->curmv[ply] = tree->killers[ply - 2].move2;
 239 
        tree->curmv[ply] = possible;
297 
        tree->next_status[ply].excluded_moves[tree->next_status[ply].
 240 
        *(tree->next_status[ply].exclude++) = possible;
298 
            num_excluded++]
 - 
 
299 
            = tree->curmv[ply];
 241 
        tree->next_status[ply].phase = GENERATE_QUIET;
300 
        tree->next_status[ply].phase = GENERATE_ALL_MOVES;
 242 
        tree->phase[ply] = MOVE_PAIR2;
301 
        return KILLER_MOVE_4;
 243 
        return ++tree->next_status[ply].order;
302 
      }
 244 
      }
303 
/*
 245 
/*
304 
 ************************************************************
 246 
 ************************************************************
305 
 *                                                          *
 247 
 *                                                          *
306 
 *  Now, generate all non-capturing moves, which get added  *
 248 
 *  Now, generate all non-capturing moves, which get added  *
307 
 *  to the move list behind any captures we did not search. *
 249 
 *  to the move list behind any captures we did not search. *
308 
 *                                                          *
 250 
 *                                                          *
309 
 ************************************************************
 251 
 ************************************************************
310 
 */
 252 
 */
311 
    case GENERATE_ALL_MOVES:
 253 
    case GENERATE_QUIET:
- 
 
 254 
      if (!in_check)
312 
      tree->last[ply] = GenerateNoncaptures(tree, ply, wtm, tree->last[ply]);
 255 
        tree->last[ply] =
313 
      tree->next_status[ply].phase = REMAINING_MOVES;
 256 
            GenerateNoncaptures(tree, ply, side, tree->last[ply]);
314 
      tree->next_status[ply].last = tree->last[ply - 1];
 257 
      tree->next_status[ply].last = tree->last[ply - 1];
315 
/*
 258 
/*
316 
 ************************************************************
 259 
 ************************************************************
317 
 *                                                          *
 260 
 *                                                          *
318 
 *  Then we try the rest of the set of moves, but we use    *
 261 
 *  Now, try the history moves.  This phase takes the       *
- 
 
 262 
 *  complete move list, and passes over them in a classic   *
319 
 *  Exclude() function to skip any moves we have already    *
 263 
 *  selection-sort, choosing the move with the highest      *
- 
 
 264 
 *  history score.  This phase is only done one time, as it *
- 
 
 265 
 *  also purges the hash, killer, counter and paired moves  *
320 
 *  searched (hash or killers).                             *
 266 
 *  from the list.                                          *
321 
 *                                                          *
 267 
 *                                                          *
322 
 ************************************************************
 268 
 ************************************************************
323 
 */
 269 
 */
- 
 
 270 
      tree->next_status[ply].remaining = 0;
- 
 
 271 
      tree->next_status[ply].phase = HISTORY;
- 
 
 272 
      bestval = -99999999;
- 
 
 273 
      bestp = 0;
- 
 
 274 
      for (movep = tree->last[ply - 1]; movep < tree->last[ply]; movep++)
- 
 
 275 
        if (*movep) {
- 
 
 276 
          if (Exclude(tree, ply, *movep))
- 
 
 277 
            *movep = 0;
- 
 
 278 
          else if (depth >= 6) {
- 
 
 279 
            tree->next_status[ply].remaining++;
- 
 
 280 
            hist = history[HistoryIndex(side, *movep)];
- 
 
 281 
            if (hist > bestval) {
- 
 
 282 
              bestval = hist;
- 
 
 283 
              bestp = movep;
- 
 
 284 
            }
- 
 
 285 
          }
- 
 
 286 
        }
- 
 
 287 
      tree->next_status[ply].remaining /= 2;
- 
 
 288 
      if (bestp) {
- 
 
 289 
        tree->curmv[ply] = Move(*bestp);
- 
 
 290 
        *bestp = 0;
- 
 
 291 
        tree->phase[ply] = HISTORY;
- 
 
 292 
        return ++tree->next_status[ply].order;
- 
 
 293 
      }
- 
 
 294 
      goto remaining_moves;
- 
 
 295 
/*
- 
 
 296 
 ************************************************************
- 
 
 297 
 *                                                          *
- 
 
 298 
 *  Now, continue with the history moves, but since one     *
- 
 
 299 
 *  pass has been made over the complete move list, there   *
- 
 
 300 
 *  are no hash/killer moves left in the list, so the tests *
- 
 
 301 
 *  for these can be avoided.                               *
- 
 
 302 
 *                                                          *
- 
 
 303 
 ************************************************************
- 
 
 304 
 */
- 
 
 305 
    case HISTORY:
- 
 
 306 
      if (depth >= 6) {
- 
 
 307 
        bestval = -99999999;
- 
 
 308 
        bestp = 0;
- 
 
 309 
        for (movep = tree->last[ply - 1]; movep < tree->last[ply]; movep++)
- 
 
 310 
          if (*movep) {
- 
 
 311 
            hist = history[HistoryIndex(side, *movep)];
- 
 
 312 
            if (hist > bestval) {
- 
 
 313 
              bestval = hist;
- 
 
 314 
              bestp = movep;
- 
 
 315 
            }
- 
 
 316 
          }
- 
 
 317 
        if (bestp) {
- 
 
 318 
          tree->curmv[ply] = Move(*bestp);
- 
 
 319 
          *bestp = 0;
- 
 
 320 
          if (--(tree->next_status[ply].remaining) <= 0) {
- 
 
 321 
            tree->next_status[ply].phase = REMAINING;
- 
 
 322 
            tree->next_status[ply].last = tree->last[ply - 1];
- 
 
 323 
          }
- 
 
 324 
          tree->phase[ply] = HISTORY;
- 
 
 325 
          return ++tree->next_status[ply].order;
- 
 
 326 
        }
- 
 
 327 
      }
- 
 
 328 
/*
- 
 
 329 
 ************************************************************
- 
 
 330 
 *                                                          *
- 
 
 331 
 *  Then we try the rest of the set of moves, and we do not *
- 
 
 332 
 *  use Exclude() function to skip any moves we have        *
- 
 
 333 
 *  already searched (hash or killers) since the history    *
- 
 
 334 
 *  phase above has already done that.                      *
- 
 
 335 
 *                                                          *
- 
 
 336 
 ************************************************************
- 
 
 337 
 */
- 
 
 338 
    remaining_moves:
- 
 
 339 
      tree->next_status[ply].phase = REMAINING;
- 
 
 340 
      tree->next_status[ply].last = tree->last[ply - 1];
324 
    case REMAINING_MOVES:
 341 
    case REMAINING:
325 
      for (; tree->next_status[ply].last < tree->last[ply];
 342 
      for (; tree->next_status[ply].last < tree->last[ply];
326 
          tree->next_status[ply].last++)
 343 
          tree->next_status[ply].last++)
327 
        if (*tree->next_status[ply].last) {
 344 
        if (*tree->next_status[ply].last) {
328 
          if (!Exclude(tree, ply, *tree->next_status[ply].last)) {
 345 
          tree->curmv[ply] = Move(*tree->next_status[ply].last++);
329 
            tree->curmv[ply] = *tree->next_status[ply].last++;
 346 
          tree->phase[ply] = REMAINING;
330 
            return REMAINING_MOVES;
 347 
          return ++tree->next_status[ply].order;
331 
          }
 - 
 
332 
        }
 348 
        }
333 
      return NONE;
 349 
      return NONE;
334 
    default:
 350 
    default:
335 
      Print(4095, "oops!  next_status.phase is bad! [normal %d]\n",
 351 
      Print(4095, "oops!  next_status.phase is bad! [phase=%d]\n",
336 
          tree->next_status[ply].phase);
 352 
          tree->next_status[ply].phase);
337 
  }
 353 
  }
338 
  return NONE;
 354 
  return NONE;
339 
}
 355 
}
340 
 
 356 
 
341 
/* last modified 05/15/14 */
 357 
/* last modified 07/03/14 */
342 
/*
 358 
/*
343 
 *******************************************************************************
 359 
 *******************************************************************************
344 
 *                                                                             *
 360 
 *                                                                             *
345 
 *   NextRootMove() is used to select the next move from the root move list.   *
 361 
 *   NextRootMove() is used to select the next move from the root move list.   *
- 
 
 362 
 *                                                                             *
- 
 
 363 
 *   There is one subtle trick here that must not be broken.  Crafty does LMR  *
- 
 
 364 
 *   at the root, and the reduction amount is dependent on the order in which  *
- 
 
 365 
 *   a specific move is searched.  With the recent changes dealing with this   *
- 
 
 366 
 *   issue in non-root moves, NextRootMove() now simply returns the move's     *
- 
 
 367 
 *   order within the move list.  This might be a problem if the last move in  *
- 
 
 368 
 *   the list fails high, because it would be reduced on the re-search, which  *
- 
 
 369 
 *   is something we definitely don't want.  The solution is found in the code *
- 
 
 370 
 *   inside Iterate().  When a move fails high, it is moved to the top of the  *
- 
 
 371 
 *   move list so that (a) it is searched first on the re-search (more on this *
- 
 
 372 
 *   in a moment) and (b) since its position in the move list is now #1, it    *
- 
 
 373 
 *   will get an order value of 1 which is never reduced.  The only warning is *
- 
 
 374 
 *   that Iterate() MUST re-sort the ply-1 move list after a fail high, even   *
- 
 
 375 
 *   though it seems like a very tiny computational waste.                     *
- 
 
 376 
 *                                                                             *
- 
 
 377 
 *   The other reason for doing the re-sort has to do with the parallel search *
- 
 
 378 
 *   algorithm.  When one thread fails high at the root, it stops the others.  *
- 
 
 379 
 *   they have to carefully undo the "this move has been searched" flag since  *
- 
 
 380 
 *   these incomplete searches need to be re-done after the fail-high move is  *
- 
 
 381 
 *   finished.  But it is possible some of those interrupted moves appear      *
- 
 
 382 
 *   before the fail high move in the move list.  Which would lead Crafty to   *
- 
 
 383 
 *   fail high, then produce a different best move's PV.  By re-sorting, now   *
- 
 
 384 
 *   the fail-high move is always searched first since here we just start at   *
- 
 
 385 
 *   the top of the move list and look for the first "not yet searched" move   *
- 
 
 386 
 *   to return.  It solves several problems, but if that re-sort is not done,  *
- 
 
 387 
 *   things go south quickly.  The voice of experience is all I will say here. *
346 
 *                                                                             *
 388 
 *                                                                             *
347 
 *******************************************************************************
 389 
 *******************************************************************************
348 
 */
 390 
 */
349 
int NextRootMove(TREE * RESTRICT tree, TREE * RESTRICT mytree, int wtm) {
 391 
int NextRootMove(TREE * RESTRICT tree, TREE * RESTRICT mytree, int side) {
350 
  int which, i;
 - 
 
351 
  uint64_t total_nodes;
 392 
  uint64_t total_nodes;
- 
 
 393 
  int which, i, t;
352 
 
 394 
 
353 
/*
 395 
/*
354 
 ************************************************************
 396 
 ************************************************************
355 
 *                                                          *
 397 
 *                                                          *
356 
 *  First, we check to see if we only have one legal move.  *
 398 
 *  First, we check to see if we only have one legal move.  *
Line 359... Line 401...
359 
 *  to ponder.                                              *
 401 
 *  to ponder.                                              *
360 
 *                                                          *
 402 
 *                                                          *
361 
 ************************************************************
 403 
 ************************************************************
362 
 */
 404 
 */
363 
  if (!annotate_mode && !pondering && !booking && n_root_moves == 1 &&
 405 
  if (!annotate_mode && !pondering && !booking && n_root_moves == 1 &&
364 
      iteration_depth > 4) {
 406 
      iteration > 10) {
365 
    abort_search = 1;
 407 
    abort_search = 1;
366 
    return NONE;
 408 
    return NONE;
367 
  }
 409 
  }
368 
/*
 410 
/*
369 
 ************************************************************
 411 
 ************************************************************
Line 377... Line 419...
377 
 *  return so that it won't be searched again in another    *
 419 
 *  return so that it won't be searched again in another    *
378 
 *  thread.                                                 *
 420 
 *  thread.                                                 *
379 
 *                                                          *
 421 
 *                                                          *
380 
 ************************************************************
 422 
 ************************************************************
381 
 */
 423 
 */
382 
  for (which = 0; which < n_root_moves; which++)
 424 
  for (which = 0; which < n_root_moves; which++) {
383 
    if (!(root_moves[which].status & 8)) {
 425 
    if (!(root_moves[which].status & 8)) {
384 
      if (search_move) {
 426 
      if (search_move) {
385 
        if (root_moves[which].move != search_move) {
 427 
        if (root_moves[which].move != search_move) {
386 
          root_moves[which].status |= 8;
 428 
          root_moves[which].status |= 8;
387 
          continue;
 429 
          continue;
Line 403... Line 445...
403 
 *  the search, simply for information about how fast the   *
 445 
 *  the search, simply for information about how fast the   *
404 
 *  machine is running.                                     *
 446 
 *  machine is running.                                     *
405 
 *                                                          *
 447 
 *                                                          *
406 
 ************************************************************
 448 
 ************************************************************
407 
 */
 449 
 */
408 
      if (tree->nodes_searched > noise_level && display_options & 32) {
 450 
      if (ReadClock() - start_time > noise_level && display_options & 16) {
409 
        Lock(lock_io);
 - 
 
410 
        sprintf_s(mytree->remaining_moves_text, sizeof (mytree->remaining_moves_text), "%d/%d", which + 1, // Pierre-Marie Baty -- use safe version
 451 
        sprintf(mytree->remaining_moves_text, "%d/%d", which + 1,
411 
            n_root_moves);
 452 
            n_root_moves);
412 
        end_time = ReadClock();
 453 
        end_time = ReadClock();
- 
 
 454 
        Lock(lock_io);
413 
        if (pondering)
 455 
        if (pondering)
414 
          printf("         %2i   %s%7s?  ", iteration_depth,
 456 
          printf("         %2i   %s%7s?  ", iteration,
415 
              Display2Times(end_time - start_time),
 457 
              Display2Times(end_time - start_time),
416 
              mytree->remaining_moves_text);
 458 
              mytree->remaining_moves_text);
417 
        else
 459 
        else
418 
          printf("         %2i   %s%7s*  ", iteration_depth,
 460 
          printf("         %2i   %s%7s*  ", iteration,
419 
              Display2Times(end_time - start_time),
 461 
              Display2Times(end_time - start_time),
420 
              mytree->remaining_moves_text);
 462 
              mytree->remaining_moves_text);
421 
        if (display_options & 32 && display_options & 64)
 - 
 
422 
          printf("%d. ", move_number);
 463 
        printf("%d. ", move_number);
423 
        if (display_options & 32 && display_options & 64 && Flip(wtm))
 464 
        if (Flip(side))
424 
          printf("... ");
 465 
          printf("... ");
425 
        strcpy_s(mytree->root_move_text, sizeof (mytree->root_move_text), OutputMove(tree, tree->curmv[1], 1, // Pierre-Marie Baty -- use safe version
 466 
        strcpy(mytree->root_move_text, OutputMove(tree, 1, side,
426 
                wtm));
 467 
                tree->curmv[1]));
427 
        total_nodes = block[0]->nodes_searched;
 468 
        total_nodes = block[0]->nodes_searched;
- 
 
 469 
        for (t = 0; t < (int) smp_max_threads; t++) // Pierre-Marie Baty -- added type cast
428 
        for (i = 1; i < MAX_BLOCKS; i++)
 470 
          for (i = 0; i < 64; i++)
429 
          if (block[i] && block[i]->used)
 471 
            if (!(thread[t].blocks & SetMask(i)))
430 
            total_nodes += block[i]->nodes_searched;
 472 
              total_nodes += block[t * 64 + 1 + i]->nodes_searched;
431 
        nodes_per_second = (unsigned int) (total_nodes * 100 / Max(end_time - start_time, 1)); // Pierre-Marie Baty -- added type cast
 473 
        nodes_per_second = (unsigned int) (total_nodes * 100 / Max(end_time - start_time, 1)); // Pierre-Marie Baty -- added type cast
432 
        i = strlen(mytree->root_move_text);
 474 
        i = strlen(mytree->root_move_text);
433 
        i = (i < 8) ? i : 8;
 475 
        i = (i < 8) ? i : 8;
434 
        strncat_s(mytree->root_move_text, sizeof (mytree->root_move_text), "          ", 8 - i); // Pierre-Marie Baty -- use safe version
 476 
        strncat(mytree->root_move_text, "          ", 8 - i);
435 
        printf("%s", mytree->root_move_text);
 477 
        printf("%s", mytree->root_move_text);
436 
        printf("(%snps)             \r", DisplayKMB(nodes_per_second));
 478 
        printf("(%snps)             \r", DisplayKMB(nodes_per_second, 0));
437 
        fflush(stdout);
 479 
        fflush(stdout);
438 
        Unlock(lock_io);
 480 
        Unlock(lock_io);
439 
      }
 481 
      }
440 
/*
 482 
/*
441 
 ************************************************************
 483 
 ************************************************************
442 
 *                                                          *
 484 
 *                                                          *
443 
 *  Bit of a tricky exit.  If the move is not flagged as    *
 485 
 *  Bit of a tricky exit.  If the move is not flagged as    *
444 
 *  "OK to search in parallel or reduce" then we return     *
 486 
 *  "OK to search in parallel or reduce" then we return     *
445 
 *  "HASH_MOVE" which will prevent Search() from reducing   *
 487 
 *  "DO_NOT_REDUCE" which will prevent Search() from        *
446 
 *  the move (LMR).  Otherwise we return the more common    *
 488 
 *  reducing the move (LMR).  Otherwise we return the more  *
447 
 *  "REMAINING_MOVES" value which allows LMR to be used on  *
 489 
 *  common "REMAINING" value which allows LMR to be used on *
448 
 *  those root moves.                                       *
 490 
 *  those root moves.                                       *
449 
 *                                                          *
 491 
 *                                                          *
450 
 ************************************************************
 492 
 ************************************************************
451 
 */
 493 
 */
452 
      if ((root_moves[which].status & 4) == 0)
 494 
      if (root_moves[which].status & 4)
453 
        return HASH_MOVE;
 495 
        tree->phase[1] = DO_NOT_REDUCE;
454 
      else
 496 
      else
455 
        return REMAINING_MOVES;
 497 
        tree->phase[1] = REMAINING;
- 
 
 498 
      return which + 1;
456 
    }
 499 
    }
- 
 
 500 
  }
457 
  return NONE;
 501 
  return NONE;
458 
}
 502 
}
459 
 
 503 
 
460 
/* last modified 05/15/14 */
 504 
/* last modified 11/13/14 */
461 
/*
 505 
/*
462 
 *******************************************************************************
 506 
 *******************************************************************************
463 
 *                                                                             *
 507 
 *                                                                             *
464 
 *   NextRootMoveParallel() is used to determine if the next root move can be  *
 508 
 *   NextRootMoveParallel() is used to determine if the next root move can be  *
465 
 *   searched in parallel.  If it appears to Iterate() that one of the moves   *
 509 
 *   searched in parallel.  If it appears to Iterate() that one of the moves   *
466 
 *   following the first move might become the best move, the 'no parallel'    *
 510 
 *   following the first move might become the best move, the 'no parallel'    *
467 
 *   flag is set to speed up finding the new best move.  This flag is set if   *
 511 
 *   flag is set to speed up finding the new best move.  This flag is set if   *
468 
 *   this root move has an "age" value > 0 which indicates this move was the   *
 512 
 *   this root move has an "age" value > 0 which indicates this move was the   *
469 
 *   "best move" within the previous 3 search depths.  We want to search such  *
 513 
 *   "best move" within the previous 3 search iterations.  We want to search   *
470 
 *   moves as quickly as possible, prior to starting a parallel search at the  *
 514 
 *   such moves as quickly as possible, prior to starting a parallel search at *
471 
 *   root, in case this move once again becomes the best move and provides a   *
 515 
 *   the root, in case this move once again becomes the best move and provides *
472 
 *   better alpha bound.                                                       *
 516 
 *   a better alpha bound.                                                     *
473 
 *                                                                             *
 517 
 *                                                                             *
474 
 *******************************************************************************
 518 
 *******************************************************************************
475 
 */
 519 
 */
476 
int NextRootMoveParallel(void) {
 520 
int NextRootMoveParallel(void) {
477 
  int which;
 521 
  int which;
Line 480... Line 524...
480 
 ************************************************************
 524 
 ************************************************************
481 
 *                                                          *
 525 
 *                                                          *
482 
 *  Here we simply check the root_move status flag that is  *
 526 
 *  Here we simply check the root_move status flag that is  *
483 
 *  set in Iterate() after each iteration is completed.  A  *
 527 
 *  set in Iterate() after each iteration is completed.  A  *
484 
 *  value of "1" indicates this move has to be searched by  *
 528 
 *  value of "1" indicates this move has to be searched by  *
485 
 *  all processors, splitting must wait until after all     *
 529 
 *  all processors together, splitting at the root must     *
486 
 *  such moves have been searched individually.             *
 530 
 *  wait until we have searched all moves that have been    *
- 
 
 531 
 *  "best" during the previous three plies.                 *
- 
 
 532 
 *                                                          *
- 
 
 533 
 *  The root move list has a flag, bit 3, used to indicate  *
- 
 
 534 
 *  that this move has been best recently.  If this bit is  *
- 
 
 535 
 *  set, we are forced to use all processors to search this *
- 
 
 536 
 *  move so that it is completed quickly rather than being  *
- 
 
 537 
 *  searched by just one processor, and taking much longer  *
- 
 
 538 
 *  to get a score back.  We do this to give the search the *
- 
 
 539 
 *  best opportunity to fail high on this move before we    *
- 
 
 540 
 *  run out of time.                                        *
487 
 *                                                          *
 541 
 *                                                          *
488 
 ************************************************************
 542 
 ************************************************************
489 
 */
 543 
 */
490 
  for (which = 0; which < n_root_moves; which++)
 544 
  for (which = 0; which < n_root_moves; which++)
491 
    if (!(root_moves[which].status & 8))
 545 
    if (!(root_moves[which].status & 8))
492 
      break;
 546 
      break;
493 
  if (which < n_root_moves && root_moves[which].status & 4)
 547 
  if (which < n_root_moves && !(root_moves[which].status & 4))
494 
    return 1;
 548 
    return 1;
495 
  return 0;
 549 
  return 0;
496 
}
 550 
}
497 
 
 551 
 
498 
/* last modified 05/15/14 */
 552 
/* last modified 09/11/15 */
499 
/*
 553 
/*
500 
 *******************************************************************************
 554 
 *******************************************************************************
501 
 *                                                                             *
 555 
 *                                                                             *
502 
 *   Exclude() searches the list of moves searched prior to generating a move  *
 556 
 *   Exclude() searches the list of moves searched prior to generating a move  *
503 
 *   list to exclude those that were searched via a hash table best move or    *
 557 
 *   list to exclude those that were searched via a hash table best move or    *
504 
 *   through the killer moves for the current ply and two plies back.          *
 558 
 *   through the killer moves for the current ply and two plies back.          *
505 
 *                                                                             *
 559 
 *                                                                             *
506 
 *   The variable next_status[].num_excluded is the total number of non-       *
 560 
 *   The variable next_status[].excluded is the total number of non-generated  *
507 
 *   generated moves we searched.  next_status[].remaining is initially set to *
 561 
 *   moves we searched.  next_status[].remaining is initially set to excluded, *
508 
 *   num_excluded, but each time an excluded move is found, the counter is     *
 562 
 *   but each time an excluded move is found, the counter is decremented.      *
509 
 *   decremented.  Once all excluded moves have been found, we avoid running   *
 563 
 *   Once all excluded moves have been found, we avoid running through the     *
510 
 *   through the list of excluded moves on each call and simply return.        *
 564 
 *   list of excluded moves on each call and simply return.                    *
511 
 *                                                                             *
 565 
 *                                                                             *
512 
 *******************************************************************************
 566 
 *******************************************************************************
513 
 */
 567 
 */
514 
int Exclude(TREE * RESTRICT tree, int ply, int move) {
 568 
int Exclude(TREE * RESTRICT tree, int ply, int move) {
515 
  int i;
 569 
  unsigned *i;
516 
 
 570 
 
517 
  if (tree->next_status[ply].num_excluded)
 571 
  if (tree->next_status[ply].exclude > &tree->next_status[ply].done[0])
518 
    for (i = 0; i < tree->next_status[ply].num_excluded; i++)
 572 
    for (i = &tree->next_status[ply].done[0];
519 
      if (move == tree->next_status[ply].excluded_moves[i]) {
 573 
        i < tree->next_status[ply].exclude; i++)
520 
        tree->next_status[ply].remaining--;
 574 
      if (move == *i)
521 
        return 1;
 575 
        return 1;
522 
      }
 - 
 
523 
  return 0;
 576 
  return 0;
- 
 
 577 
}
- 
 
 578 
 
- 
 
 579 
/* last modified 05/20/15 */
- 
 
 580 
/*
- 
 
 581 
 *******************************************************************************
- 
 
 582 
 *                                                                             *
- 
 
 583 
 *   NextSort() is used to sort the move list.  This is a list of 32 bit       *
- 
 
 584 
 *   values where the rightmost 21 bits is the compressed move, and the left-  *
- 
 
 585 
 *   most 11 bits are the sort key (MVV/LVA values).                           *
- 
 
 586 
 *                                                                             *
- 
 
 587 
 *******************************************************************************
- 
 
 588 
 */
- 
 
 589 
void NextSort(TREE * RESTRICT tree, int ply) {
- 
 
 590 
  unsigned temp, *movep, *tmovep;
- 
 
 591 
 
- 
 
 592 
/*
- 
 
 593 
 ************************************************************
- 
 
 594 
 *                                                          *
- 
 
 595 
 *  This is a simple insertion sort algorithm.              *
- 
 
 596 
 *                                                          *
- 
 
 597 
 ************************************************************
- 
 
 598 
 */
- 
 
 599 
  if (tree->last[ply] > tree->last[ply - 1] + 1) {
- 
 
 600 
    for (movep = tree->last[ply - 1] + 1; movep < tree->last[ply]; movep++) {
- 
 
 601 
      temp = *movep;
- 
 
 602 
      tmovep = movep - 1;
- 
 
 603 
      while (tmovep >= tree->last[ply - 1] && SortV(*tmovep) < SortV(temp)) {
- 
 
 604 
        *(tmovep + 1) = *tmovep;
- 
 
 605 
        tmovep--;
- 
 
 606 
      }
- 
 
 607 
      *(tmovep + 1) = temp;
- 
 
 608 
    }
- 
 
 609 
  }
524 
}
 610 
}