1 #include <math.h>
2 #include "chess.h"
3 #include "data.h"
4 /* last modified 02/23/14 */
5 /*
6 *******************************************************************************
7 * *
8 * TimeAdjust() is called to adjust timing variables after each program move *
9 * is made. It simply increments the number of moves made, decrements the *
10 * amount of time used, and then makes any necessary adjustments based on *
11 * the time controls. *
12 * *
13 *******************************************************************************
14 */
TimeAdjust(int side,int time_used)15 void TimeAdjust(int side, int time_used) {
16 /*
17 ************************************************************
18 * *
19 * Decrement the number of moves remaining to the next *
20 * time control. Then subtract the time the program took *
21 * to choose its move from the time remaining. *
22 * *
23 ************************************************************
24 */
25 tc_moves_remaining[side]--;
26 tc_time_remaining[side] -=
27 (tc_time_remaining[side] >
28 time_used) ? time_used : tc_time_remaining[side];
29 if (!tc_moves_remaining[side]) {
30 if (tc_sudden_death == 2)
31 tc_sudden_death = 1;
32 tc_moves_remaining[side] += tc_secondary_moves;
33 tc_time_remaining[side] += tc_secondary_time;
34 Print(4095, "time control reached (%s)\n", (side) ? "white" : "black");
35 }
36 if (tc_increment)
37 tc_time_remaining[side] += tc_increment;
38 }
39
40 /* last modified 10/01/14 */
41 /*
42 *******************************************************************************
43 * *
44 * TimeCheck() is used to determine when the search should stop. It uses *
45 * several conditions to make this determination: (1) The search time has *
46 * exceeded the time per move limit; (2) The value at the root of the tree *
47 * has not dropped too low. *
48 * *
49 * We use one additional trick here to avoid stopping the search just before *
50 * we change to a better move. We simply do our best to complete the *
51 * iteration which means we have searched every move to this same depth. *
52 * *
53 * This is implemented by having Search() call TimeCheck() passing it a *
54 * value of one (1) for the parameter busy. TimeCheck() will only end the *
55 * search if we have exceeded the max time limit. Otherwise, we continue. *
56 * Iterate() calls TimeCheck() passing it a value of "0" for busy, which *
57 * simply says "now, if we have used the target time limit (which can be *
58 * modified by the "difficulty value), we will stop and not try another *
59 * iteration." *
60 * *
61 * The "difficulty" value is used to implement the concept of an "easy move" *
62 * or a "hard move". With an easy move, we want to spend less time since *
63 * the easy move is obvious. The opposite idea is a hard move, where we *
64 * actually want to spend more time to be sure we don't make a mistake by` *
65 * moving too quickly. *
66 * *
67 * The basic methodology revolves around how many times we change our mind *
68 * on the best move at the root of the tree. *
69 * *
70 * The "difficulty" variable is initially set to 100, which represents a *
71 * percentage of the actual target time we should spend on this move. If *
72 * we end an iteration without having changed our mind at all, difficulty *
73 * is reduced by multiplying by .9, with a lower bound of 60%. *
74 * *
75 * If we change our mind during an iteration, there are two cases. (1) If *
76 * difficulty is < 100%, we set it back to 100% +20% for each time we *
77 * changed the best move. (2) if difficulty is already at 100% or higher, *
78 * we multiply difficulty by .80, then add 20% for each root move change. *
79 * For example, suppose we are at difficulty=60%, and we suddenly change our *
80 * mind twice this iteration (3 different best moves). *
81 * *
82 * difficulty = 100 + 3*20 = 160% of the actual target time will be used. *
83 * *
84 * Suppose we change back and forth between two best moves multiple times, *
85 * with difficulty currently at 100%. The first time: *
86 * *
87 * difficulty = .80 * 100 + 2*20 = 120% *
88 * *
89 * The next iteration: *
90 * *
91 * difficulty = .80 * 120 + 2 * 20 = 96% _ 40% = 136% *
92 * *
93 * The next iteration: *
94 * *
95 * difficulty = .80 * 136% + 40% = 149% *
96 * *
97 * If we stop changing our mind, then difficulty starts on a downward trend. *
98 * The basic idea is that if we are locked in on a move, we can make it a *
99 * bit quicker, but if we are changing back and forth, we are going to spend *
100 * more time to try to choose the best move. *
101 * *
102 *******************************************************************************
103 */
TimeCheck(TREE * RESTRICT tree,int busy)104 int TimeCheck(TREE * RESTRICT tree, int busy) {
105 int time_used;
106 int i, ndone;
107
108 /*
109 ************************************************************
110 * *
111 * Check to see if we need to "burp" the time to let the *
112 * operator know the search is progressing and how much *
113 * time has been used so far. *
114 * *
115 ************************************************************
116 */
117 time_used = (ReadClock() - start_time);
118 if (time_used >= noise_level && display_options & 16 && time_used > burp) {
119 Lock(lock_io);
120 if (pondering)
121 printf(" %2i %s%7s? ", iteration, Display2Times(time_used),
122 tree->remaining_moves_text);
123 else
124 printf(" %2i %s%7s* ", iteration, Display2Times(time_used),
125 tree->remaining_moves_text);
126 if (display_options & 16)
127 printf("%d. ", move_number);
128 if ((display_options & 16) && Flip(root_wtm))
129 printf("... ");
130 printf("%s(%snps) \r", tree->root_move_text,
131 DisplayKMB(nodes_per_second, 0));
132 burp = (time_used / 1500) * 1500 + 1500;
133 fflush(stdout);
134 Unlock(lock_io);
135 }
136 /*
137 ************************************************************
138 * *
139 * First, check to see if there is only one root move. If *
140 * so, and we are not pondering, searching a book move or *
141 * or annotating a game, we can return and make this move *
142 * instantly. We do need to finish iteration 1 so that we *
143 * actually back up a move to play. *
144 * *
145 ************************************************************
146 */
147 if (n_root_moves == 1 && !booking && !annotate_mode && !pondering &&
148 iteration > 1 && (time_used > time_limit || time_used > 100))
149 return 1;
150 if (iteration <= 2)
151 return 0;
152 /*
153 ************************************************************
154 * *
155 * If we are pondering or in analyze mode, we do not *
156 * terminate on time since there is no time limit placed *
157 * on these searches. If we have reached the absolute *
158 * time limit, we stop the search instantly. *
159 * *
160 ************************************************************
161 */
162 if (pondering || analyze_mode)
163 return 0;
164 if (time_used > absolute_time_limit)
165 return 1;
166 /*
167 ************************************************************
168 * *
169 * If the operator has specified a specific time limit, we *
170 * stop when we hit that regardless of any other tests *
171 * used during normal timeing. *
172 * *
173 ************************************************************
174 */
175 if (search_time_limit) {
176 if (time_used < time_limit)
177 return 0;
178 else
179 return 1;
180 }
181 /*
182 ************************************************************
183 * *
184 * If we are under the time limit already set, we do not *
185 * terminate the search. Once we reach that limit, we *
186 * abort the search if we are fixing to start another *
187 * iteration, otherwise we keep searching to try to *
188 * complete the current iteration. *
189 * *
190 ************************************************************
191 */
192 if (time_used < (difficulty * time_limit) / 100)
193 return 0;
194 if (!busy)
195 return 1;
196 /*
197 ************************************************************
198 * *
199 * We have reached the target time limit. If we are in *
200 * the middle of an iteration, we keep going unless we are *
201 * stuck on the first move, where there is no benefit to *
202 * continuing and this will just burn clock time away. *
203 * *
204 * This is a bit tricky, because if we are on the first *
205 * move AND we have failed low, we want to continue the *
206 * search to find something better, if we have not failed *
207 * low, we will abort the search in the test that follows *
208 * this one. *
209 * *
210 ************************************************************
211 */
212 ndone = 0;
213 for (i = 0; i < n_root_moves; i++)
214 if (root_moves[i].status & 8)
215 ndone++;
216 if (ndone == 1 && !(root_moves[0].status & 1))
217 return 1;
218 /*
219 ************************************************************
220 * *
221 * We are in the middle of an iteration, we have used the *
222 * allocated time limit, but we have more moves left to *
223 * search. We forge on until we complete the iteration *
224 * which will terminate the search, or until we reach the *
225 * "absolute_time_limit" where we terminate the search no *
226 * matter what is going on. *
227 * *
228 ************************************************************
229 */
230 if (time_used + 300 > tc_time_remaining[root_wtm])
231 return 1;
232 return 0;
233 }
234
235 /* last modified 09/30/14 */
236 /*
237 *******************************************************************************
238 * *
239 * TimeSet() is called to set the two variables "time_limit" and *
240 * "absolute_time_limit" which controls the amount of time taken by the *
241 * iterated search. It simply takes the timing controls as set by the user *
242 * and uses these values to calculate how much time should be spent on the *
243 * next search. *
244 * *
245 *******************************************************************************
246 */
TimeSet(int search_type)247 void TimeSet(int search_type) {
248 int mult = 0, extra = 0;
249 int surplus, average;
250 int simple_average;
251
252 surplus = 0;
253 average = 0;
254 /*
255 ************************************************************
256 * *
257 * Check to see if we are in a sudden-death type of time *
258 * control. If so, we have a fixed amount of time *
259 * remaining. Set the search time accordingly and exit. *
260 * *
261 * The basic algorithm is to divide the remaining time *
262 * left on the clock by a constant (that is larger for *
263 * ponder=off games since we don't get to ponder and save *
264 * time as the game progresses) and add the increment. *
265 * *
266 * Set our MAX search time to the smaller of 5 * the time *
267 * limit or 1/2 of the time left on the clock. *
268 * *
269 ************************************************************
270 */
271 if (tc_sudden_death == 1) {
272 time_limit =
273 (tc_time_remaining[root_wtm] -
274 tc_safety_margin) / (ponder ? 20 : 26) + tc_increment;
275 absolute_time_limit =
276 Min(time_limit * 5, tc_time_remaining[root_wtm] / 2);
277 }
278 /*
279 ************************************************************
280 * *
281 * We are not in a sudden_death situation. We now have *
282 * two choices: If the program has saved enough time to *
283 * meet the surplus requirement, then we simply divide *
284 * the time left evenly among the moves left. If we *
285 * haven't yet saved up a cushion so that "hard-moves" *
286 * can be searched more thoroughly, we simply take the *
287 * number of moves divided into the total time as the *
288 * target. *
289 * *
290 ************************************************************
291 */
292 else {
293 if (move_number <= tc_moves)
294 simple_average = (tc_time - tc_safety_margin) / tc_moves;
295 else
296 simple_average =
297 (tc_secondary_time - tc_safety_margin) / tc_secondary_moves;
298 surplus =
299 Max(tc_time_remaining[root_wtm] - tc_safety_margin -
300 simple_average * tc_moves_remaining[root_wtm], 0);
301 average =
302 (tc_time_remaining[root_wtm] - tc_safety_margin +
303 tc_moves_remaining[root_wtm] * tc_increment)
304 / tc_moves_remaining[root_wtm];
305 if (surplus < tc_safety_margin)
306 time_limit = (average < simple_average) ? average : simple_average;
307 else
308 time_limit =
309 (average < 2.0 * simple_average) ? average : 2.0 * simple_average;
310 }
311 if (tc_increment > 200 && moves_out_of_book < 2)
312 time_limit *= 1.2;
313 if (time_limit <= 0)
314 time_limit = 5;
315 absolute_time_limit =
316 time_limit + surplus / 2 + (tc_time_remaining[root_wtm] -
317 tc_safety_margin) / 4;
318 if (absolute_time_limit > 5 * time_limit)
319 absolute_time_limit = 5 * time_limit;
320 if (absolute_time_limit > tc_time_remaining[root_wtm] / 2)
321 absolute_time_limit = tc_time_remaining[root_wtm] / 2;
322 /*
323 ************************************************************
324 * *
325 * The "usage" option can be used to force the time limit *
326 * higher or lower than normal. The new "timebook" *
327 * command can also modify the target time making the *
328 * program use more time early in the game as it exits the *
329 * book, knowing it will save time later on by ponder hits *
330 * and instant moves. *
331 * *
332 ************************************************************
333 */
334 if (usage_level)
335 time_limit *= 1.0 + usage_level / 100.0;
336 if (first_nonbook_factor && moves_out_of_book < first_nonbook_span) {
337 mult =
338 (first_nonbook_span - moves_out_of_book + 1) * first_nonbook_factor;
339 extra = time_limit * mult / first_nonbook_span / 100;
340 time_limit += extra;
341 }
342 /*
343 ************************************************************
344 * *
345 * If the operator has set an absolute search time limit *
346 * already, then we simply copy this value and return. *
347 * *
348 ************************************************************
349 */
350 if (search_time_limit) {
351 time_limit = search_time_limit;
352 absolute_time_limit = time_limit;
353 }
354 if (search_type == puzzle || search_type == booking) {
355 time_limit /= 10;
356 absolute_time_limit = time_limit * 3;
357 }
358 if (!tc_sudden_death && !search_time_limit &&
359 time_limit > 3 * tc_time / tc_moves)
360 time_limit = 3 * tc_time / tc_moves;
361 time_limit = Min(time_limit, absolute_time_limit);
362 if (search_type != puzzle) {
363 if (!tc_sudden_death)
364 Print(32, " time surplus %s ", DisplayTime(surplus));
365 else
366 Print(32, " ");
367 Print(32, "time limit %s", DisplayTimeKibitz(time_limit));
368 Print(32, " (%s)\n", DisplayTimeKibitz(absolute_time_limit));
369 }
370 if (time_limit <= 1) {
371 time_limit = 1;
372 usage_level = 0;
373 }
374 }
375