1
2 // search.cpp
3
4 // includes
5
6 #include <csetjmp>
7 #include <cstring>
8
9 #include "attack.h"
10 #include "board.h"
11 #include "book.h"
12 #include "colour.h"
13 #include "list.h"
14 #include "material.h"
15 #include "move.h"
16 #include "move_do.h"
17 #include "move_gen.h"
18 #include "option.h"
19 #include "pawn.h"
20 #include "protocol.h"
21 #include "pv.h"
22 #include "search.h"
23 #include "search_full.h"
24 #include "sort.h"
25 #include "trans.h"
26 #include "util.h"
27 #include "value.h"
28
29 // constants
30
31 static const bool UseCpuTime = false; // false
32 static const bool UseEvent = true; // true
33
34 static const bool UseShortSearch = true;
35 static const int ShortSearchDepth = 1;
36
37 static const bool DispBest = true; // true
38 static const bool DispDepthStart = true; // true
39 static const bool DispDepthEnd = true; // true
40 static const bool DispRoot = true; // true
41 static const bool DispStat = true; // true
42
43 static const bool UseEasy = true; // singular move
44 static const int EasyThreshold = 150;
45 static const double EasyRatio = 0.20;
46
47 static const bool UseEarly = true; // early iteration end
48 static const double EarlyRatio = 0.60;
49
50 static const bool UseBad = true;
51 static const int BadThreshold = 50; // 50
52 static const bool UseExtension = true;
53
54 // variables
55
56 static search_multipv_t save_multipv[MultiPVMax];
57
58 bool trans_endgame;
59 search_param_t SearchStack[HeightMax];
60
61 search_input_t SearchInput[1];
62 search_info_t SearchInfo[1];
63 search_root_t SearchRoot[1];
64 search_current_t SearchCurrent[1];
65 search_best_t SearchBest[MultiPVMax];
66
67 // prototypes
68
69 static void search_send_stat ();
70
71 // functions
72
73 // depth_is_ok()
74
depth_is_ok(int depth)75 bool depth_is_ok(int depth) {
76
77 return depth > -128 && depth < DepthMax;
78 }
79
80 // height_is_ok()
81
height_is_ok(int height)82 bool height_is_ok(int height) {
83
84 return height >= 0 && height < HeightMax;
85 }
86
87 // search_clear()
88
search_clear()89 void search_clear() {
90
91 // SearchInput
92
93 SearchInput->infinite = false;
94 SearchInput->depth_is_limited = false;
95 SearchInput->depth_limit = 0;
96 SearchInput->time_is_limited = false;
97 SearchInput->time_limit_1 = 0.0;
98 SearchInput->time_limit_2 = 0.0;
99
100 // SearchInfo
101
102 SearchInfo->can_stop = false;
103 SearchInfo->stop = false;
104 SearchInfo->check_nb = 10000; // was 100000
105 SearchInfo->check_inc = 10000; // was 100000
106 SearchInfo->last_time = 0.0;
107
108 // SearchBest
109
110 SearchBest[SearchCurrent->multipv].move = MoveNone;
111 SearchBest[SearchCurrent->multipv].value = 0;
112 SearchBest[SearchCurrent->multipv].flags = SearchUnknown;
113 PV_CLEAR(SearchBest[SearchCurrent->multipv].pv);
114
115 // SearchRoot
116
117 SearchRoot->depth = 0;
118 SearchRoot->move = MoveNone;
119 SearchRoot->move_pos = 0;
120 SearchRoot->move_nb = 0;
121 SearchRoot->last_value = 0;
122 SearchRoot->bad_1 = false;
123 SearchRoot->bad_2 = false;
124 SearchRoot->change = false;
125 SearchRoot->easy = false;
126 SearchRoot->flag = false;
127
128 // SearchCurrent
129
130 SearchCurrent->max_depth = 0;
131 SearchCurrent->node_nb = 0;
132 SearchCurrent->time = 0.0;
133 SearchCurrent->speed = 0.0;
134 SearchCurrent->cpu = 0.0;
135 }
136
137 // search()
138
search()139 void search() {
140
141 int move;
142 int depth;
143 int i;
144 bool search_ready;
145
146
147 for (i = 0; i < MultiPVMax; i++){
148 save_multipv[SearchCurrent->multipv].mate = 0;
149 save_multipv[SearchCurrent->multipv].depth = 0;
150 save_multipv[SearchCurrent->multipv].max_depth = 0;
151 save_multipv[SearchCurrent->multipv].value = 0;
152 save_multipv[SearchCurrent->multipv].time = 0;
153 save_multipv[SearchCurrent->multipv].node_nb = 0;
154 strcpy(save_multipv[SearchCurrent->multipv].pv_string,"");
155 }
156
157 SearchInput->multipv = option_get_int("MultiPV")-1;
158 SearchCurrent->multipv = 0;
159
160
161 ASSERT(board_is_ok(SearchInput->board));
162
163 // opening book
164
165 if (option_get_bool("OwnBook") && !SearchInput->infinite) {
166
167 move = book_move(SearchInput->board);
168
169 if (move != MoveNone) {
170
171 // play book move
172
173 SearchBest[SearchCurrent->multipv].move = move;
174 SearchBest[SearchCurrent->multipv].value = 1;
175 SearchBest[SearchCurrent->multipv].flags = SearchExact;
176 SearchBest[SearchCurrent->multipv].depth = 1;
177 SearchBest[SearchCurrent->multipv].pv[0] = move;
178 SearchBest[SearchCurrent->multipv].pv[1] = MoveNone;
179
180 search_update_best();
181
182 return;
183 }
184 }
185
186 // SearchInput
187
188 gen_legal_moves(SearchInput->list,SearchInput->board);
189
190 if (LIST_SIZE(SearchInput->list) < SearchInput->multipv+1){
191 SearchInput->multipv = LIST_SIZE(SearchInput->list)-1;
192 }
193
194 if (LIST_SIZE(SearchInput->list) <= 1) {
195 SearchInput->depth_is_limited = true;
196 SearchInput->depth_limit = 4; // was 1
197 }
198
199 // SearchInfo
200
201 if (setjmp(SearchInfo->buf) != 0) {
202 ASSERT(SearchInfo->can_stop);
203 ASSERT(SearchBest->move!=MoveNone);
204 search_update_current();
205 return;
206 }
207
208 // SearchRoot
209
210 list_copy(SearchRoot->list,SearchInput->list);
211
212 // SearchCurrent
213
214 board_copy(SearchCurrent->board,SearchInput->board);
215 my_timer_reset(SearchCurrent->timer);
216 my_timer_start(SearchCurrent->timer);
217
218 // init
219
220 trans_inc_date(Trans);
221
222 sort_init();
223 search_full_init(SearchRoot->list,SearchCurrent->board);
224
225 // analyze game for evaluation
226
227 if (SearchCurrent->board->piece_size[White] < 3 && SearchCurrent->board->piece_size[Black] < 3){
228 trans_endgame = true;
229 }
230 else{
231 trans_endgame = false;
232 }
233
234
235 // iterative deepening
236
237 search_ready = false;
238
239 for (depth = 1; depth < DepthMax; depth++) {
240 for (SearchCurrent->multipv = 0; SearchCurrent->multipv <= SearchInput->multipv; SearchCurrent->multipv++){
241
242 if (DispDepthStart && SearchCurrent->multipv == 0) send("info depth %d",depth);
243
244 SearchCurrent->max_extensions = depth;
245 SearchRoot->bad_1 = false;
246 SearchRoot->change = false;
247
248 board_copy(SearchCurrent->board,SearchInput->board);
249
250 if (UseShortSearch && depth <= ShortSearchDepth) {
251 search_full_root(SearchRoot->list,SearchCurrent->board,depth,SearchShort);
252 } else {
253 search_full_root(SearchRoot->list,SearchCurrent->board,depth,SearchNormal);
254 }
255
256 search_update_current();
257
258 if (DispDepthEnd && SearchCurrent->multipv == SearchInput->multipv) {
259 send("info depth %d seldepth %d time %.0f nodes " S64_FORMAT " nps %.0f",depth,SearchCurrent->max_depth,SearchCurrent->time*1000.0,SearchCurrent->node_nb,SearchCurrent->speed);
260 }
261
262 // update search info
263
264 if (depth >= 1) SearchInfo->can_stop = true;
265
266 if (depth == 1
267 && LIST_SIZE(SearchRoot->list) >= 2
268 && LIST_VALUE(SearchRoot->list,0) >= LIST_VALUE(SearchRoot->list,1) + EasyThreshold) {
269 SearchRoot->easy = true;
270 }
271
272 if (UseBad && depth > 1) {
273 SearchRoot->bad_2 = SearchRoot->bad_1;
274 SearchRoot->bad_1 = false;
275 ASSERT(SearchRoot->bad_2==(SearchBest->value<=SearchRoot->last_value-BadThreshold));
276 }
277
278 SearchRoot->last_value = SearchBest[0].value;
279
280 // stop search?
281 if (SearchInput->nodes_is_limited //&& SearchCurrent->multipv >= SearchInput->multipv
282 && SearchCurrent->node_nb >= SearchInput->nodes_limit) {
283 SearchRoot->flag = true;
284 }
285
286 if (SearchInput->depth_is_limited && SearchCurrent->multipv >= SearchInput->multipv
287 && depth >= SearchInput->depth_limit) {
288 SearchRoot->flag = true;
289 }
290
291 if (SearchInput->time_is_limited
292 && SearchCurrent->time >= SearchInput->time_limit_1
293 && !SearchRoot->bad_2) {
294 SearchRoot->flag = true;
295 }
296
297 if (UseEasy
298 && SearchInput->time_is_limited
299 && SearchCurrent->time >= SearchInput->time_limit_1 * EasyRatio
300 && SearchRoot->easy) {
301 ASSERT(!SearchRoot->bad_2);
302 ASSERT(!SearchRoot->change);
303 SearchRoot->flag = true;
304 }
305
306 if (UseEarly
307 && SearchInput->time_is_limited
308 && SearchCurrent->time >= SearchInput->time_limit_1 * EarlyRatio
309 && !SearchRoot->bad_2
310 && !SearchRoot->change) {
311 SearchRoot->flag = true;
312 }
313
314 if (SearchInfo->can_stop
315 && (SearchInfo->stop || (SearchRoot->flag && !SearchInput->infinite))) {
316 search_ready = true;
317 break;
318 }
319 }
320 if (search_ready)
321 break;
322 }
323 }
324
325 // search_update_best()
326
search_update_best()327 void search_update_best() {
328
329 int move, value, flags, depth, max_depth;
330 const mv_t * pv;
331 double time;
332 sint64 node_nb;
333 int mate, i, z;
334 bool found;
335 char move_string[256], pv_string[512];
336
337 search_update_current();
338
339 if (DispBest) {
340
341 move = SearchBest[SearchCurrent->multipv].move;
342 value = SearchBest[SearchCurrent->multipv].value;
343 flags = SearchBest[SearchCurrent->multipv].flags;
344 depth = SearchBest[SearchCurrent->multipv].depth;
345 pv = SearchBest[SearchCurrent->multipv].pv;
346
347 max_depth = SearchCurrent->max_depth;
348 time = SearchCurrent->time;
349 node_nb = SearchCurrent->node_nb;
350
351 move_to_string(move,move_string,256);
352 pv_to_string(pv,pv_string,512);
353
354 mate = value_to_mate(value);
355
356 if (SearchCurrent->multipv == 0){
357 save_multipv[SearchCurrent->multipv].mate = mate;
358 save_multipv[SearchCurrent->multipv].depth = depth;
359 save_multipv[SearchCurrent->multipv].max_depth = max_depth;
360 save_multipv[SearchCurrent->multipv].value = value;
361 save_multipv[SearchCurrent->multipv].time = time*1000.0;
362 save_multipv[SearchCurrent->multipv].node_nb = node_nb;
363 strcpy(save_multipv[SearchCurrent->multipv].pv_string,pv_string);
364 }
365 else{
366 found = false;
367 for (i = 0; i < SearchCurrent->multipv; i++){
368 if (save_multipv[i].value < value){
369 found = true;
370 break;
371 }
372 }
373 if (found){
374
375 for (z = SearchCurrent->multipv; z > i; z--){
376 save_multipv[z].mate = save_multipv[z-1].mate;
377 save_multipv[z].depth = save_multipv[z-1].depth;
378 save_multipv[z].max_depth = save_multipv[z-1].max_depth;
379 save_multipv[z].value = save_multipv[z-1].value;
380 save_multipv[z].time = save_multipv[z-1].time;
381 save_multipv[z].node_nb = save_multipv[z-1].node_nb;
382 strcpy(save_multipv[z].pv_string,save_multipv[z-1].pv_string);
383 }
384
385 save_multipv[i].mate = mate;
386 save_multipv[i].depth = depth;
387 save_multipv[i].max_depth = max_depth;
388 save_multipv[i].value = value;
389 save_multipv[i].time = time*1000.0;
390 save_multipv[i].node_nb = node_nb;
391 strcpy(save_multipv[i].pv_string,pv_string);
392
393 }
394 else{
395 save_multipv[SearchCurrent->multipv].mate = mate;
396 save_multipv[SearchCurrent->multipv].depth = depth;
397 save_multipv[SearchCurrent->multipv].max_depth = max_depth;
398 save_multipv[SearchCurrent->multipv].value = value;
399 save_multipv[SearchCurrent->multipv].time = time*1000.0;
400 save_multipv[SearchCurrent->multipv].node_nb = node_nb;
401 strcpy(save_multipv[SearchCurrent->multipv].pv_string,pv_string);
402 }
403 }
404
405 if (depth > 1 || (depth == 1 && SearchCurrent->multipv == SearchInput->multipv)){
406 for (i = 0; i <= SearchInput->multipv; i++){
407
408 if (save_multipv[i].mate == 0) {
409
410 // normal evaluation
411
412 if (false) {
413 } else if (flags == SearchExact) {
414 send("info multipv %d depth %d seldepth %d score cp %d time %.0f nodes " S64_FORMAT " pv %s",i+1,save_multipv[i].depth,save_multipv[i].max_depth,save_multipv[i].value,save_multipv[i].time,save_multipv[i].node_nb,save_multipv[i].pv_string);
415 } else if (flags == SearchLower) {
416 send("info multipv %d depth %d seldepth %d score cp %d lowerbound time %.0f nodes " S64_FORMAT " pv %s",i+1,save_multipv[i].depth,save_multipv[i].max_depth,save_multipv[i].value,save_multipv[i].time,save_multipv[i].node_nb,save_multipv[i].pv_string);
417 } else if (flags == SearchUpper) {
418 send("info multipv %d depth %d seldepth %d score cp %d upperbound time %.0f nodes " S64_FORMAT " pv %s",i+1,save_multipv[i].depth,save_multipv[i].max_depth,save_multipv[i].value,save_multipv[i].time,save_multipv[i].node_nb,save_multipv[i].pv_string);
419 }
420
421 } else {
422
423 // mate announcement
424
425 if (false) {
426 } else if (flags == SearchExact) {
427 send("info multipv %d depth %d seldepth %d score mate %d time %.0f nodes " S64_FORMAT " pv %s",i+1,save_multipv[i].depth,save_multipv[i].max_depth,save_multipv[i].mate,save_multipv[i].time,save_multipv[i].node_nb,save_multipv[i].pv_string);
428 } else if (flags == SearchLower) {
429 send("info multipv %d depth %d seldepth %d score mate %d lowerbound time %.0f nodes " S64_FORMAT " pv %s",i+1,save_multipv[i].depth,save_multipv[i].max_depth,save_multipv[i].mate,save_multipv[i].time,save_multipv[i].node_nb,save_multipv[i].pv_string);
430 } else if (flags == SearchUpper) {
431 send("info multipv %d depth %d seldepth %d score mate %d upperbound time %.0f nodes " S64_FORMAT " pv %s",i+1,save_multipv[i].depth,save_multipv[i].max_depth,save_multipv[i].mate,save_multipv[i].time,save_multipv[i].node_nb,save_multipv[i].pv_string);
432 }
433 }
434 }
435 }
436 }
437
438 // update time-management info
439
440 if (UseBad && SearchBest[SearchCurrent->multipv].depth > 1) {
441 if (SearchBest[SearchCurrent->multipv].value <= SearchRoot->last_value - BadThreshold) {
442 SearchRoot->bad_1 = true;
443 SearchRoot->easy = false;
444 SearchRoot->flag = false;
445 } else {
446 SearchRoot->bad_1 = false;
447 }
448 }
449 }
450
451 // search_update_root()
452
search_update_root()453 void search_update_root() {
454
455 int move, move_pos, move_nb;
456 double time;
457 sint64 node_nb;
458 char move_string[256];
459
460 if (DispRoot) {
461
462 search_update_current();
463
464 if (SearchCurrent->time >= 1.0) {
465
466 move = SearchRoot->move;
467 move_pos = SearchRoot->move_pos;
468 move_nb = SearchRoot->move_nb;
469
470 time = SearchCurrent->time;
471 node_nb = SearchCurrent->node_nb;
472
473 move_to_string(move,move_string,256);
474
475 send("info currmove %s currmovenumber %d",move_string,move_pos+1);
476 }
477 }
478 }
479
480 // search_update_current()
481
search_update_current()482 void search_update_current() {
483
484 my_timer_t *timer;
485 sint64 node_nb;
486 double time, speed, cpu;
487
488 timer = SearchCurrent->timer;
489
490 node_nb = SearchCurrent->node_nb;
491 time = (UseCpuTime) ? my_timer_elapsed_cpu(timer) : my_timer_elapsed_real(timer);
492 speed = (time >= 1.0) ? double(node_nb) / time : 0.0;
493 cpu = my_timer_cpu_usage(timer);
494
495 SearchCurrent->time = time;
496 SearchCurrent->speed = speed;
497 SearchCurrent->cpu = cpu;
498 }
499
500 // search_check()
501
search_check()502 void search_check() {
503
504 search_send_stat();
505
506 if (UseEvent) event();
507
508 if (SearchInput->depth_is_limited
509 && SearchRoot->depth > SearchInput->depth_limit) {
510 SearchRoot->flag = true;
511 }
512
513 if (SearchInput->time_is_limited
514 && SearchCurrent->time >= SearchInput->time_limit_2) {
515 SearchRoot->flag = true;
516 }
517
518 if (SearchInput->time_is_limited
519 && SearchCurrent->time >= SearchInput->time_limit_1
520 && !SearchRoot->bad_1
521 && !SearchRoot->bad_2
522 && (!UseExtension || SearchRoot->move_pos == 0)) {
523 SearchRoot->flag = true;
524 }
525
526 if (SearchInfo->can_stop
527 && (SearchInfo->stop || (SearchRoot->flag && !SearchInput->infinite))) {
528 longjmp(SearchInfo->buf,1);
529 }
530 }
531
532 // search_send_stat()
533
search_send_stat()534 static void search_send_stat() {
535
536 double time, speed, cpu;
537 sint64 node_nb;
538
539 search_update_current();
540
541 if (DispStat && SearchCurrent->time >= SearchInfo->last_time + 1.0) { // at least one-second gap
542
543 SearchInfo->last_time = SearchCurrent->time;
544
545 time = SearchCurrent->time;
546 speed = SearchCurrent->speed;
547 cpu = SearchCurrent->cpu;
548 node_nb = SearchCurrent->node_nb;
549
550 send("info time %.0f nodes " S64_FORMAT " nps %.0f cpuload %.0f",time*1000.0,node_nb,speed,cpu*1000.0);
551
552 trans_stats(Trans);
553 }
554 }
555
556 // end of search.cpp
557
558