| blob | 2b2f4b63ab9e2fda67f354768d7722b7eda77a8b |
1 /***************************************************************************
2 search.cpp - description
3 -------------------
4 begin : Wed Mar 13 2002
5 copyright : (C) 2002-2005 by Monge Maurizio
6 email : monge@linuz.sns.it
7 ***************************************************************************/
9 /***************************************************************************
10 * *
11 * This program is free software; you can redistribute it and/or modify *
12 * it under the terms of the GNU General Public License as published by *
13 * the Free Software Foundation; either version 2 of the License, or *
14 * (at your option) any later version. *
15 * *
16 ***************************************************************************/
18 #include "engine.h"
19 #include "utils.h"
20 #include <string.h>
21 #include <stdlib.h>
22 #include <math.h>
24 #define MAX_PV 80
25 #define PLY 100
28 // uint16_t killers[MAX_PV][64*64];
29 //
30 // #define HISTORY_INDEX(m) (SQUARE_TO_64(m.from)*64 + SQUARE_TO_64(m.to))
34 /* enable the nega-scout pv-search */
35 #define NEGA_SCOUT 0
37 /* enable the null move */
38 #define NULL_MOVE 0
40 /* before doing the alpha beta search check if any of the following positions
41 can give use an early cutoff thanks to the hashtable */
42 #define EARLY_TRANSP_CUTOFF 0
44 /* when the hashtable provides no "best" move, do a depth-2 search */
45 #define INTERNAL_ITERATIVE_DEEPENING 0
47 /* use the history sorting heuristic */
48 #define HISTORY_HEURISTIC 1
50 /* improve the sorting heuristic for moves to the center */
51 #define CENTER_HEURISTIC 0
53 class SearchStack
54 {
55 public:
56 int base_depth; /* depth of the search at this ply */
57 int extensions; /* global extensions at this node */
58 Move *moves; /* all generated moves */
59 int num_moves; /* num of moves */
60 int curr_move; /* the move being currently analyzed */
61 int16_t alpha; /* alpha ans beta when the search started (not improved) */
62 int16_t beta;
63 bool under_check;
64 Move threat;
65 int best_move;
66 };
68 Move mv_stack[200*MAX_PV];
69 int mv_stack_top = 0;
70 SearchStack stack[MAX_PV];
71 int current_ply = 0;
73 #if 0
74 #define STAT(x)
75 #else
76 #define STAT(x) stat_##x++;
78 #define S(x) uint64_t stat_##x;
79 S(quiesce_nodes);
80 S(quiesce_hash);
81 S(quiesce_called);
82 S(quiesce_best_can_be_first);
83 S(quiesce_best_was_first);
84 S(quiesce_cutoff);
85 S(quiesce_cutoff_first);
86 S(search_nodes);
87 S(search_hash);
88 S(search_best_can_be_first);
89 S(search_best_was_first);
90 S(search_cutoff);
91 S(search_cutoff_first);
92 S(null_tried);
93 S(null_successful);
94 #undef S
96 void reset_stats()
97 {
98 #define S(x) stat_##x = 0;
99 S(quiesce_nodes);
100 S(quiesce_hash);
101 S(quiesce_called);
102 S(quiesce_best_can_be_first);
103 S(quiesce_best_was_first);
104 S(quiesce_cutoff);
105 S(quiesce_cutoff_first);
106 S(search_nodes);
107 S(search_hash);
108 S(search_best_can_be_first);
109 S(search_best_was_first);
110 S(search_cutoff);
111 S(search_cutoff_first);
112 S(null_tried);
113 S(null_successful);
114 #undef S
115 }
117 void print_stats()
118 {
119 #define S(x) printf("# " #x " = "U64F"\n", stat_##x);
120 S(quiesce_nodes);
121 S(quiesce_hash);
122 S(quiesce_called);
123 S(quiesce_best_can_be_first);
124 S(quiesce_best_was_first);
125 S(quiesce_cutoff);
126 S(quiesce_cutoff_first);
127 S(search_nodes);
128 S(search_hash);
129 S(search_best_can_be_first);
130 S(search_best_was_first);
131 S(search_cutoff);
132 S(search_cutoff_first);
133 S(null_tried);
134 S(null_successful);
135 #undef S
136 }
138 #endif
140 void Engine::print_stat()
141 {
142 if(eng_status != ANALYZING)
143 {
144 printf("Thinking: ");
145 for(int i=0; i<current_ply; i++)
146 {
147 if(stack[i].curr_move == -2)
148 {
149 continue;
150 } //Internal iterative deepening
151 else if(stack[i].curr_move == -1)
152 {
153 printf("<NULL>");
154 board.do_null_move();
155 }
156 else
157 {
158 char buf[32];
159 printf("%s", move_to_alg(buf, &(stack[i].moves[stack[i].curr_move]) ) );
160 board.do_move(stack[i].moves[stack[i].curr_move]);
161 }
162 printf((i != current_ply-1) ? " " : "\n");
163 }
164 rewind_thinking();
165 return;
166 }
168 if(thinking)
169 {
170 char buf[32];
171 output("stat01: %d "U64F" %d %d %d %s\n",
172 current_time() - start_think_time,
173 processed_nodes,
174 stack[0].base_depth/100,
175 stack[0].num_moves-1-stack[0].curr_move,
176 stack[0].num_moves,
177 move_to_alg(buf, &(stack[0].moves[stack[0].curr_move]) ) );
178 }
179 else
180 output("stat01: 0 0 0 0 0\n");
181 }
183 void Engine::rewind_thinking()
184 {
185 for(int i=current_ply-1; i>=0; i--)
186 {
187 if(stack[i].curr_move == -2)
188 { } //Internal iterative deepening
189 else if(stack[i].curr_move == -1)
190 board.undo_null_move();
191 else
192 board.undo_move(stack[i].moves[stack[i].curr_move]);
193 }
194 }
196 void Engine::restore_thinking()
197 {
198 for(int i=0; i<current_ply; i++)
199 {
200 if(stack[i].curr_move == -2)
201 { } //Internal iterative deepening
202 else if(stack[i].curr_move == -1)
203 board.do_null_move();
204 else
205 board.do_move(stack[i].moves[stack[i].curr_move]);
206 }
208 /* regenerate pinning info and under_check var, just to be sure :) */
209 Move mvs[250];
210 board.find_moves(mvs);
211 }
213 #if 0
214 void
215 Engine::moves_heuristic(Move *mv, int num_mv, int ply, int orig_depth,
216 Move best_mv_hash, bool quiesce)
217 {
218 /*uint8_t up_right = Board::up_dir[IS_WHITE(board.color_to_move)] + RIGHT;
219 uint8_t up_left = Board::up_dir[IS_WHITE(board.color_to_move)] + LEFT;*/
220 int hash_move = -1;
222 for(int i=0;i<num_mv;i++)
223 {
224 mv[i].val = 0;
225 mv[i].extend = 0;
227 /* give a high bonus to the move stored in the hash, if any.
228 mark only which is, don't continue, because some extensions
229 may be triggered ad added later (ie pawn strike, etc) */
230 if(mv[i].as_int == best_mv_hash.as_int)
231 hash_move = i;
233 if(board.move_is_check(mv[i]) )
234 {
235 int see = board.move_see_val(mv[i]);
236 if(orig_depth>-5*PLY && see >= 0)
237 mv[i].val = 25000 + see*64;
238 else
239 mv[i].val = 15000;
240 }
241 else if(mv[i].capture)
242 {
243 int see = board.move_see_val(mv[i]);
244 if(see > 0 || (orig_depth>-5*PLY && see==0) )
245 mv[i].val = 20000 + see*64;
246 else
247 mv[i].val = 10000;
248 }
249 }
251 if(hash_move!=-1)
252 mv[hash_move].val = 30000;
253 }
254 #else
255 void
256 Engine::moves_heuristic(Move *mv, int num_mv, int ply, int orig_depth,
257 Move best_mv_hash, bool quiesce)
258 {
259 /*uint8_t up_right = Board::up_dir[IS_WHITE(board.color_to_move)] + RIGHT;
260 uint8_t up_left = Board::up_dir[IS_WHITE(board.color_to_move)] + LEFT;*/
261 int hash_move = -1;
263 for(int i=0;i<num_mv;i++)
264 {
265 mv[i].val = 0;
266 mv[i].extend = 0;
268 /* give a high bonus to the move stored in the hash, if any.
269 mark only which is, don't continue, because some extensions
270 may be triggered ad added later (ie pawn strike, etc) */
271 if(mv[i].as_int == best_mv_hash.as_int)
272 hash_move = i;
274 /* process strong pawn moves */
275 if(PIECE_OF(board.data[mv[i].from])==PAWN) /* pawn strike */
276 {
277 if( ROW_OF(mv[i].to) == board.seventh_rank[IS_WHITE(board.color_to_move)] )
278 {
279 int x = board.move_see_val(mv[i]);
281 if(x<0)
282 {
283 mv[i].val += -15000;
284 continue;
285 }
287 mv[i].val += 29499; /* 7th push */
288 mv[i].extend = 1; /* extend search */
289 continue;
290 }
292 if( mv[i].flags == PROMOTEQUEEN )
293 {
294 int x = board.move_see_val(mv[i]);
296 if(x<0)
297 {
298 mv[i].val += -15000;
299 continue;
300 }
302 mv[i].val += 29500; /* promote! */
303 mv[i].extend = 1; /* extend search */
304 continue;
305 }
307 #if 0
308 /* pawn strike */
309 uint8_t p1 = mv[i].to + up_right;
310 uint8_t p2 = mv[i].to + up_left;
311 uint8_t a = OUT_OF_BOARD(p1) ? 0 : board.data[p1];
312 uint8_t b = OUT_OF_BOARD(p2) ? 0 : board.data[p2];
313 if( (COLOR_OF(a)==board.other_color && PIECE_OF(a)!=PAWN)
314 || (COLOR_OF(b)==board.other_color && PIECE_OF(b)!=PAWN) )
315 {
316 int x = board.move_see_val(mv[i]);
317 if(x<0)
318 {
319 mv[i].val += -15000;
320 continue;
321 }
323 mv[i].val += 27000; /* pawn strike! */
324 mv[i].extend = 1; /* extend search */
325 continue;
326 }
327 #endif
328 }
330 if(mv[i].capture)
331 {
332 int x = board.move_see_val(mv[i]);
334 if(x>0)
335 {
336 if(orig_depth>-7*PLY && board.move_is_check(mv[i]) )
337 {
338 mv[i].val += 29800+x;
339 //mv[i].extend = 1;
340 }
341 else
342 mv[i].val += 29000+x;
343 continue;
344 }
345 else if(x<0)
346 {
347 mv[i].val += -15000+x;
348 continue;
349 }
350 else if(orig_depth>-7*PLY && board.move_is_check(mv[i]) )
351 {
352 /* = capture but check */
353 mv[i].val += 29800;
354 continue;
355 }
356 }
357 else /* add a bonus for checks (but not too deep, or quiescence will get mad) */
358 if(0 && orig_depth>-3*PLY && board.move_is_check(mv[i]) )
359 {
360 if(board.move_see_val(mv[i])>=0)
361 {
362 mv[i].val += 28799;
363 continue;
364 }
365 }
367 if(quiesce)
368 continue;
370 #if HISTORY_HEURISTIC
371 /* add the value depending on the heuristic */
372 // mv[i].val += killers[ply][HISTORY_INDEX(mv[i])];
373 // if(ply>=2)
374 // mv[i].val += killers[ply-2][HISTORY_INDEX(mv[i])];
375 #endif //HISTORY_HEURISTIC
377 #if CENTER_HEURISTIC
378 static int bof[128] = {
379 0,0,1,2,2,1,0,0,ENDL,
380 0,1,2,3,3,2,1,0,ENDL,
381 0,2,4,5,5,4,2,0,ENDL,
382 1,2,5,6,6,5,2,1,ENDL,
383 1,2,5,6,6,5,2,1,ENDL,
384 0,2,4,5,5,4,2,0,ENDL,
385 0,1,2,3,3,2,1,0,ENDL,
386 0,0,1,2,2,1,0,0,ENDL
387 };
389 /* add a bonus for moves towards the center */
390 mv[i].val += (bof[mv[i].to] - bof[mv[i].from]);
391 #endif //CENTER_HEURISTIC
392 }
394 if(hash_move!=-1)
395 mv[hash_move].val = 30000;
396 }
397 #endif
400 void
401 Engine::moves_quiescence_heuristic(Move *mv, int num_mv, const Move& best_mv_hash, int static_eval, int alpha, int beta)
402 {
403 for(int i=0;i<num_mv;i++)
404 {
405 mv[i].val = -30000;
406 mv[i].cost = 0;
408 /* give a high bonus to the move stored in the hash, if any. */
409 if(mv[i].as_int == best_mv_hash.as_int)
410 {
411 mv[i].val = 30000;
412 continue;
413 }
415 if( mv[i].flags == PROMOTEQUEEN )
416 {
417 mv[i].val = 20000;
418 continue;
419 }
421 if(mv[i].capture)
422 {
423 int x = board.move_see_val(mv[i]);
425 if((static_eval == -INF && x>0)
426 || (static_eval + x*100 + 100 > alpha))
427 {
428 if( board.move_is_check(mv[i]) )
429 mv[i].val = 15000 + x*64;
430 else
431 mv[i].val = 10000 + x*64;
432 continue;
433 }
434 else
435 {
436 if(board.move_is_check(mv[i]))
437 {
438 mv[i].val = 5000 + x*64;
439 mv[i].cost = 20 + MAX(0, -x*8);
440 }
441 else
442 {
443 mv[i].val = x*64;
444 mv[i].cost = 40 + MAX(0, -x*12);
445 }
446 continue;
447 }
448 }
450 if( board.move_is_check(mv[i]) )
451 {
452 A88 atk = IS_WHITE(board.other_color) ? board.w_attacks : board.b_attacks;
453 A88 def = IS_WHITE(board.color_to_move) ? board.w_attacks : board.b_attacks;
455 if(atk[mv[i].to] && !def[mv[i].to])
456 {
457 mv[i].val = -5000;
458 mv[i].cost = 50;
459 }
460 else
461 {
462 mv[i].val = -2000;
463 mv[i].cost = 30;
464 }
465 }
466 }
467 }
471 int16_t
472 Engine::quiesce(int ply, int depth, int16_t alpha, int16_t beta)
473 {
474 SearchStack *s = &stack[ply];
475 int16_t static_eval = -INF;
476 int16_t best = -INF;
477 int16_t best_guessed = alpha;
478 uint16_t cbest_mv_hash = 0; /* the compressed move from the hash */
479 Move best_mv_hash = Move::FromInt(0); /* the move from the hash */
480 int best_mv_found = -1; /* the index of the best move AFTER searching */
481 bool dangerous_position = false;
483 STAT(quiesce_nodes);
485 s->base_depth = 0;
486 s->extensions = 0;
487 s->num_moves = 0;
488 s->curr_move = -3;
489 s->alpha = alpha;
490 s->beta = beta;
491 s->threat = Move::FromInt(0);
492 s->best_move = -1;
494 prefetch_hash( board.hash );
496 /* check if time is running out */
497 if(check_time())
498 return 0;
500 /* check for a draw for repetition or 50mvs. Of course the draw for
501 repetition must be checked BEFORE probing the hash :)*/
502 if(check_draw())
503 return (board.color_to_move == st_computer_color) ? v_eval_draw :
504 ((board.other_color == st_computer_color) ? -v_eval_draw : 0); /* be aggressive! */
507 /*******************************************************************************
508 Probe the hashtable.
509 If the probe is succesful the hashtable will return us value
510 that can be exact, a lower bound or an upper bound, and if the
511 depth of the hashed search is >= the current depth this value
512 will be used to improve alpha and beta and possibly return immediatly.
513 The hastable will also give us a "best" move that will be searched
514 first.
515 This is the move that caused the "final" cutoff when this position
516 was searched previously. This best move is actually the index of the best
517 move in the array of generated moves (it is supposed to be deterministic :)
518 *******************************************************************************/
520 HashEntry *h = probe_hash( board.hash );
522 if(h)
523 {
524 int16_t l = h->lower();
525 int16_t u = h->upper();
527 if(l>=beta || u==l)
528 {
529 STAT(quiesce_hash);
530 return l;
531 }
532 if(u<=alpha)
533 {
534 STAT(quiesce_hash);
535 return u;
536 }
538 beta = MIN(beta, u);
539 alpha = MAX(alpha, l);
541 cbest_mv_hash = h->best_mv;
542 best_guessed = MAX(best_guessed, h->lower());
543 }
546 /*******************************************************************************
547 Test if we are under check, and if so extend search
548 *******************************************************************************/
550 s->under_check = board.under_attack(board.king_pos[IS_WHITE(board.color_to_move)],
551 board.other_color);
553 if(s->under_check)
554 dangerous_position = true;
555 // else
556 // {
557 // int d = 0;
558 // int num_mv;
559 // Move *mv = mv_stack + mv_stack_top;
560 // board.do_null_move();
561 // num_mv = board.find_moves(mv);
562 //
563 // for(int i=0;i<num_mv;i++)
564 // {
565 // if(!mv[i].capture)
566 // continue;
567 // if(board.move_see_val(mv[i])>0)
568 // d++;
569 // }
570 //
571 // board.undo_null_move();
572 // if(d >= 2)
573 // dangerous_position = true;
574 // }
576 if(ply > 40)
577 dangerous_position = false;
579 if(!dangerous_position)
580 {
581 best = static_eval = board.evaluate(st_computer_color, alpha, beta);
583 alpha = MAX(alpha, best);
584 if(best >= beta)
585 goto qsearch_done;
587 if(ply>40)
588 goto qsearch_done;
589 }
592 /*******************************************************************************
593 Now generate the legal moves and look for a check/stalemate
594 *******************************************************************************/
596 /* generate all the legal moves */
597 s->moves = &mv_stack[mv_stack_top];
598 s->num_moves = board.find_moves(s->moves);
599 mv_stack_top += s->num_moves;
600 s->under_check = board.under_check;
602 /* return now if the positon is terminal */
603 if(!s->num_moves)
604 {
605 if(s->under_check)
606 /* while mating, sacrify as much as possible :) */
607 best = -INF + ply;//*50 + board.material[IS_WHITE(eng_color)]/50;
608 else
609 best = 0;
610 goto qsearch_done;
611 }
614 /*******************************************************************************
615 Sort the moves.
616 First comes the move from the hashtable, if avalable.
617 The remaining moves are sorted with a heuristic that keeps in account
618 the history heuristic (ie the moves that previously caused an alpha
619 cutoff), a MVV/LVA bonus value and a small bonus for moves that go
620 toward the center.
621 *******************************************************************************/
623 /* convert the move we got from the hash to the move structure */
624 if(cbest_mv_hash)
625 {
626 best_mv_hash = board.uncompress_move(cbest_mv_hash);
627 /* if it happened that the move we got from the hashtable
628 is not valid, simply no move will get the high
629 heuristic bonus value */
630 }
632 /* for each move calculate the heuristic goodness value */
633 moves_quiescence_heuristic(s->moves, s->num_moves, best_mv_hash, static_eval, alpha, beta);
635 /* if quiesce rip-off bad moves */
636 if(!dangerous_position)
637 {
638 int n = 0;
639 for(int i=0;i<s->num_moves;i++)
640 if(s->moves[i].val>=10000 ||
641 (s->moves[i].val>=-10000 && depth>s->moves[i].cost) )
642 s->moves[n++] = s->moves[i];
643 mv_stack_top -= s->num_moves-n;
644 s->num_moves = n;
645 }
647 /* sort the moves using the heuristic values */
648 sort_moves( s->moves, s->num_moves );
650 /* set the current best move index (as will be saved in the hash) */
651 best_mv_found = 0;
653 /*******************************************************************************
654 It is now time to loop all the successor moves and search recursively.
655 *******************************************************************************/
657 for(int i=0;i<s->num_moves;i++)
658 {
659 int16_t val;
661 /* sort moves incrementally, in the hope of a beta cut */
662 //incremental_sort_moves(s->moves+i, s->num_moves-i);
664 s->curr_move = i;
665 current_ply++;
666 board.do_move(s->moves[i]);
667 val = -quiesce( ply+1, depth - s->moves[i].cost, -beta, -alpha);
668 board.undo_move(s->moves[i]);
669 current_ply--;
671 /* update the current best value and check for and alpha cut */
672 best = MAX(best, val);
673 if(best > alpha)
674 {
675 best_mv_found = i;
676 s->best_move = i;
678 /* alpha cut! */
679 alpha = best;
680 }
682 /* beta cut! */
683 if(best >= beta)
684 {
685 STAT(quiesce_cutoff);
686 if(i==0)
687 STAT(quiesce_cutoff_first);
688 break;
689 }
690 }
693 qsearch_done:
694 mv_stack_top -= s->num_moves; /* free the moves we allocated */
696 /* if we found a best move searching, that move will be saved.
697 if we did no search (ie quiescence), save the old hash value,
698 or -1 if no hash entry had been found */
699 int bestmv = cbest_mv_hash;
700 if(best_mv_found >= 0)
701 {
702 bestmv = board.compress_move(s->moves[best_mv_found]);
703 STAT(quiesce_best_can_be_first);
704 if(best_mv_found == 0)
705 STAT(quiesce_best_was_first);
706 }
708 /* write the value in the hash, with the index of the best move */
709 write_hash( best > s->alpha ? best : -INF,
710 best < beta ? best : +INF, 0, bestmv);
712 return best;
713 }
716 /*******************************************************************************
717 The main alpha-beta recursive search function.
718 It handles both normal search (with or without null move)
719 and quiescence search, because i have having 2 almost identical
720 function around.
721 *******************************************************************************/
723 int16_t
724 Engine::search(int ply, int depth, bool pv, int16_t alpha, int16_t beta, bool inner)
725 {
726 SearchStack *s = &stack[ply];
727 int null_value = INF;
728 int16_t best = -INF;
729 int16_t best_guessed = alpha;
730 uint16_t cbest_mv_hash = 0; /* the compressed move from the hash */
731 Move best_mv_hash = Move::FromInt(0); /* the move from the hash */
732 int best_mv_found = -1; /* the index of the best move AFTER searching */
733 bool extended = false;
735 STAT(search_nodes);
737 s->base_depth = depth;
738 s->extensions = 0;
739 s->num_moves = 0;
740 s->curr_move = -3;
741 s->alpha = alpha;
742 s->beta = beta;
743 s->threat = Move::FromInt(0);
744 s->best_move = -1;
746 prefetch_hash( board.hash );
748 /* check if time is running out */
749 if(check_time())
750 return 0;
752 /* check for a draw for repetition or 50mvs. Of course the draw for
753 repetition must be checked BEFORE probing the hash :)*/
754 if(check_draw())
755 return (board.color_to_move == st_computer_color) ? v_eval_draw :
756 ((board.other_color == st_computer_color) ? -v_eval_draw : 0); /* be aggressive! */
758 /*******************************************************************************
759 Probe the hashtable.
760 If the probe is succesful the hashtable will return us value
761 that can be exact, a lower bound or an upper bound, and if the
762 depth of the hashed search is >= the current depth this value
763 will be used to improve alpha and beta and possibly return immediatly.
764 The hastable will also give us a "best" move that will be searched
765 first.
766 This is the move that caused the "final" cutoff when this position
767 was searched previously. This best move is actually the index of the best
768 move in the array of generated moves (it is supposed to be deterministic :)
769 *******************************************************************************/
770 HashEntry *h = probe_hash( board.hash );
772 if(h && (h->depth >= s->base_depth))// || ABS(h->value)>INF-1000) )
773 {
774 int16_t l = h->lower();
775 int16_t u = h->upper();
778 if(l>=beta || u==l)
779 {
780 STAT(search_hash);
781 return l;
782 }
783 if(u<=alpha)
784 {
785 STAT(search_hash);
786 return u;
787 }
789 beta = MIN(beta, u);
790 alpha = MAX(alpha, l);
791 }
793 if(h) {
794 cbest_mv_hash = h->best_mv;
795 best_guessed = MAX(best_guessed, h->lower());
796 }
799 /*******************************************************************************
800 Test if we are under check, and if so extend search
801 *******************************************************************************/
803 s->under_check = board.under_attack(board.king_pos[IS_WHITE(board.color_to_move)],
804 board.other_color);
806 /*******************************************************************************
807 If it is time to quiesce, evaluate and test if we can exit
808 immediately with a beta cut-off (try first a rough eval - delta)
809 *******************************************************************************/
810 //s quiesce = (!s->under_check) && (depth<=0);
811 #if 0
812 if(quiesce && depth>=-100)
813 {
814 int num_mv;
815 Move *mv = mv_stack + mv_stack_top;
816 board.do_null_move();
817 num_mv = board.find_moves(mv);
819 for(int i=0;i<num_mv;i++)
820 {
821 if(!mv[i].capture)
822 continue;
823 if(board.move_see_val(mv[i])>0)
824 {
825 quiesce = false;
826 break;
827 }
828 }
830 board.undo_null_move();
831 }
832 #endif
835 #if NULL_MOVE
836 /*******************************************************************************
837 Try the null move.
838 *******************************************************************************/
839 if(!s->under_check && (stack[ply-1].curr_move!=-1) && depth >= 2*PLY && beta<INF-1000)
840 {
841 s->curr_move = -1;
842 current_ply++;
843 board.do_null_move();
844 null_value = -search( ply+1, depth-v_search_null_reduction, true, -beta, -beta+1);
845 //null_value = -search( ply+1, depth-v_search_null_reduction, true, -beta, -INF);
846 board.undo_null_move();
847 current_ply--;
849 STAT(null_tried);
851 /* null move cut! */
852 if(null_value >= beta)
853 {
854 STAT(null_successful);
855 return null_value;
856 }
858 // if(val<alpha-100 && /* we are facing a threat*/
859 // stack[ply+1].best_move != -1) /* be sure we aren't reading random memory */
860 // {
861 // /* ok, officially the array stack[ply+1].moves has already
862 // been deallocated, but who cares :) */
863 // s->threat = stack[ply+1].moves[stack[ply+1].best_move];
864 //
865 // #if 0
866 // /* Botvinnik-Markoff extension!!! */
867 // if(!extended && ply>=3 && (s->threat == stack[ply-2].threat) )
868 // {
869 // depth += 80;
870 // extended = true;
871 // }
872 // #endif
873 // }
874 }
875 #endif
879 /*******************************************************************************
880 Now generate the legal moves and look for a check/stalemate
881 *******************************************************************************/
883 /* generate all the legal moves */
884 s->moves = &mv_stack[mv_stack_top];
885 s->num_moves = board.find_moves(s->moves);
886 mv_stack_top += s->num_moves;
887 s->under_check = board.under_check;
889 if(s->under_check==2) /* double check */
890 {
891 depth += 200;
892 extended = true;
893 }
894 else if(s->under_check) /* simple check */
895 {
896 depth += 100;
897 if(stack[ply-1].curr_move!=-1 &&
898 !board.pins[stack[ply-1].moves[ /* last moved piece is not attacking the king */
899 stack[ply-1].curr_move].to]) /* so this is a discover check */
900 {
901 depth += 50;
902 }
903 extended = true;
904 }
906 /* return now if the positon is terminal */
907 if(!s->num_moves)
908 {
909 if(s->under_check)
910 /* while mating, sacrify as much as possible :) */
911 best = -INF + ply;//*50 + board.material[IS_WHITE(eng_color)]/50;
912 else
913 best = 0;
914 goto search_done;
915 }
917 /* single-reply extension */
918 if(s->num_moves == 1 && !extended)
919 {
920 depth += 100;
921 extended = true;
922 }
923 else if(s->num_moves <= 3 && !extended)
924 {
925 depth += 50;
926 extended = true;
927 }
931 /*******************************************************************************
932 Try to get an early beta cutoff using the hash table values
933 of the following moves, and improve alpha too.
934 Try only the first 6 value of the ordered moves (argh, looking into the
935 hashtable is very expensive because of the cache!!!!!!!!)
936 *******************************************************************************/
937 #if EARLY_TRANSP_CUTOFF
938 if(depth >= 2*PLY)
939 {
940 HashKey hk = board.move_hash(s->moves[0]);
941 for(int i=1;i<s->num_moves;i++)
942 {
943 prefetch_hash(hk);
944 HashKey newhk = board.move_hash(s->moves[i]);
945 HashEntry *h2 = probe_hash( hk );
946 hk = newhk;
948 if(h2 && h2->depth >= depth-100)
949 {
950 if(-h2->up >= beta)
951 {
952 best = -h2->up;
953 goto search_done;
954 }
955 alpha = MAX(alpha, (int16_t)-h2->up);
956 }
957 }
959 HashEntry *h2 = probe_hash( hk );
960 if(h2 && h2->depth >= depth-100)
961 {
962 if(-h2->up >= beta)
963 {
964 best = -h2->up;
965 goto search_done;
966 }
967 alpha = MAX(alpha, (int16_t)-h2->up);
968 }
969 }
970 #endif //EARLY_TRANSP_CUTOFF
973 /*******************************************************************************
974 Sort the moves.
975 First comes the move from the hashtable, if avalable.
976 The remaining moves are sorted with a heuristic that keeps in account
977 the history heuristic (ie the moves that previously caused an alpha
978 cutoff), a MVV/LVA bonus value and a small bonus for moves that go
979 toward the center.
980 *******************************************************************************/
982 /* convert the move we got from the hash to the move structure */
983 if(cbest_mv_hash)
984 {
985 best_mv_hash = board.uncompress_move(cbest_mv_hash);
986 /* if it happened that the move we got from the hashtable
987 is not valid, simply no move will get the high
988 heuristic bonus value */
989 }
990 #if INTERNAL_ITERATIVE_DEEPENING
991 else if(s->base_depth>=3*PLY && pv) /* don't do it only on the pv, or it will be useless :) */
992 {
993 s->curr_move = -2;
994 current_ply++;
995 int val = search(ply+1, s->base_depth-2*PLY, true, alpha, beta);
996 current_ply--;
998 HashEntry *h2 = probe_hash( board.hash );
999 if(h2 && h2->best_mv)
1000 {
1001 cbest_mv_hash = h2->best_mv;
1002 best_mv_hash = board.uncompress_move(cbest_mv_hash);
1004 best_guessed = MAX(best_guessed, h2->lower());
1005 }
1006 }
1007 #endif //INTERNAL_ITERATIVE_DEEPENING
1010 /* for each move calculate the heuristic goodness value */
1011 moves_heuristic( s->moves, s->num_moves, ply, s->base_depth,
1012 best_mv_hash, false );
1014 /* sort the moves using the heuristic values */
1015 sort_moves( s->moves, s->num_moves );
1017 /* mh threat extension, unluckily does not seam to work well */
1018 // if(!extended && ply<7 && (null_value < best_guessed-v_search_threat_threshold))
1019 // {
1020 // extended = true;
1021 // depth += v_search_threat_extension;
1022 // }
1025 /* set the current best move index (as will be saved in the hash) */
1026 best_mv_found = 0;
1028 /*******************************************************************************
1029 It is now time to loop all the successor moves and search recursively.
1030 *******************************************************************************/
1032 for(int i=0;i<s->num_moves;i++)
1033 {
1034 int16_t val;
1035 int sdepth = depth-100;
1037 /* sort moves incrementally, in the hope of a beta cut */
1038 //incremental_sort_moves(s->moves+i, s->num_moves-i);
1040 s->curr_move = i;
1041 current_ply++;
1042 board.do_move(s->moves[i]);
1044 if(sdepth > 0)
1045 {
1046 #ifdef NEGA_SCOUT
1047 if(i == 0)
1048 val = -search( ply+1, sdepth, pv, -beta, -alpha);
1049 else
1050 {
1051 val = -search( ply+1, sdepth, false, -alpha-1, -alpha );
1052 if((val>alpha) && pv)
1053 val = -search( ply+1, sdepth, true, -beta, -alpha );
1054 }
1055 #else //NEGA_SCOUT
1056 val = -search( ply+1, sdepth, pv, -beta, -alpha);
1057 #endif //NEGA_SCOUT
1058 }
1059 else
1060 {
1061 val = -quiesce( ply+1, 100, -beta, -alpha);
1062 STAT(quiesce_called);
1063 }
1065 board.undo_move(s->moves[i]);
1066 current_ply--;
1068 /* update the current best value and check for and alpha cut */
1069 best = MAX(best, val);
1070 if(best > alpha)
1071 {
1072 best_mv_found = i;
1073 s->best_move = i;
1075 /* alpha cut! */
1076 alpha = best;
1077 }
1079 /* beta cut! */
1080 if(best >= beta)
1081 {
1082 STAT(search_cutoff);
1083 if(i==0)
1084 STAT(search_cutoff_first);
1085 break;
1086 }
1087 }
1090 // for(int i=0;i<best_mv_found;i++)
1091 // {
1092 // uint16_t& val = killers[0][HISTORY_INDEX(s->moves[i])];
1093 // val = MAX(val-1, 0);
1094 // }
1095 // {uint16_t& kval = killers[0][HISTORY_INDEX(s->moves[best_mv_found])];
1096 // kval = MIN(kval+16, 29000);}
1099 search_done:
1100 mv_stack_top -= s->num_moves; /* free the moves we allocated */
1102 /* if we found a best move searching, that move will be saved.
1103 if we did no search (ie quiescence), save the old hash value,
1104 or -1 if no hash entry had been found */
1105 int bestmv = cbest_mv_hash;
1106 if(best_mv_found >= 0)
1107 {
1108 bestmv = board.compress_move(s->moves[best_mv_found]);
1109 STAT(search_best_can_be_first);
1110 if(best_mv_found == 0)
1111 STAT(search_best_was_first);
1112 }
1114 /* write the value in the hash, with the index of the best move */
1115 write_hash( best > s->alpha ? best : -INF,
1116 best < beta ? best : +INF,
1117 s->base_depth, bestmv);
1119 return best;
1120 }
1123 Move
1124 Engine::find_best_move()
1125 {
1126 SearchStack *s = &stack[0];
1127 Move retv;
1129 ASSERT(!thinking);
1131 reset_stats();
1133 /* initialize the root node */
1134 current_ply = 0;
1135 s->base_depth = 2*PLY;
1136 s->extensions = 0;
1137 s->curr_move = -1;
1138 s->alpha = -INF;
1139 s->beta = INF;
1140 s->threat = Move::FromInt(0);
1141 s->best_move = -1;
1143 s->moves = mv_stack;
1144 s->num_moves = mv_stack_top = board.find_moves(s->moves);
1146 /* to print the analysis */
1147 if(post)
1148 output("\tply\tscore\ttime\tnodes\tpv\n");
1150 /* return immediatly if the move is forced. */
1151 if(s->num_moves==1)
1152 return s->moves[0];
1154 /* probe the play lines */
1155 if( eng_status == PLAYING
1156 && st_computer_color == board.color_to_move
1157 && probe_lines( board.hash, &retv))
1158 {
1159 retv.val = 0;
1160 return retv;
1161 }
1163 /* probe the book */
1164 if(probe_book( board.hash, &retv) ) {
1165 for(int i=0;i<s->num_moves++;i++)
1166 if(retv.as_int == s->moves[i].as_int)
1167 {
1168 retv.val = 0;
1169 return retv;
1170 }
1171 output("ERROR! Got an invalid move from the book!\n");
1172 }
1174 /* calculate how much time we will think*/
1175 start_think_time = current_time();
1176 if( analysis_limit == TIME_LIMIT )
1177 {
1178 if(board.color_to_move == st_computer_color)
1179 calc_best_time();
1180 else /* pondering? analysing? */
1181 time_best_csec = 99999999;
1182 max_think_time = start_think_time + time_best_csec - 2;
1183 }
1185 processed_nodes = 0;
1186 thinking = true;
1187 make_old_hash();
1189 /* set the back jump for the quick thinking exit */
1190 if(setjmp(back))
1191 goto exit_thinking;
1193 /* start with a guess of 0 */
1194 s->moves[0].val = 0;
1195 retv = s->moves[0];
1197 /* do the iterative deepening thing. */
1198 while(1)
1199 {
1200 int16_t alpha = -INF;
1201 int i=0;
1203 // for(int i=0;i<40;i++)
1204 // memset( &killers[i], 0, 64*64*sizeof(uint16_t));
1206 /* for each move call the alpha-beta search function */
1207 int best_mv = 0;
1209 for(i=0;i<s->num_moves;i++)
1210 {
1211 s->curr_move = i;
1212 current_ply++;
1213 board.do_move(s->moves[i]);
1214 #if NEGA_SCOUT
1215 if(i == 0)
1216 {
1217 s->moves[i].val = -search( 1, s->base_depth-100, true,
1218 -INF, -alpha );
1219 }
1220 else
1221 {
1222 s->moves[i].val = -search( 1, s->base_depth-100, false,
1223 -alpha-1, -alpha );
1224 if(s->moves[i].val > alpha)
1225 s->moves[i].val = -search( 1, s->base_depth-100, true,
1226 -INF, -alpha );
1227 }
1228 #else //NEGA_SCOUT
1229 s->moves[i].val = -search( 1, s->base_depth-100, true, -INF, -alpha);
1230 #endif //NEGA_SCOUT
1231 board.undo_move(s->moves[i]);
1232 current_ply--;
1234 /* cut alpha */
1235 if(s->moves[i].val > alpha)
1236 {
1237 alpha = s->moves[i].val;
1238 retv = s->moves[i];
1239 best_mv = i;
1240 s->best_move = i;
1242 /* this move caused an alpha cut, so print the new line */
1243 if( post /*&& processed_nodes>100000*/)
1244 {
1245 output("\t%d\t%d\t%d\t"U64F"\t", s->base_depth/100,
1246 s->moves[i].val, current_time() - start_think_time, processed_nodes);
1247 print_moves(&s->moves[i], 1, true);
1248 }
1249 }
1250 }
1252 /* the search is done, sort the moves so that best is searched first */
1253 if(i>1)
1254 {
1255 s->moves[best_mv].val++;
1256 sort_moves(s->moves, i); /* sort i moves (those that we where able to search) */
1257 s->moves[0].val--;
1258 }
1260 /* print the result of the analysis at this depth */
1261 if( post /*&& processed_nodes>100000*/)
1262 {
1263 output("\t%d\t%d\t%d\t"U64F"\t", s->base_depth/100,
1264 s->moves[0].val, current_time() - start_think_time, processed_nodes);
1265 print_moves(&s->moves[0], 1, true);
1266 }
1268 /* max depth */
1269 if( s->base_depth >= 40*PLY )
1270 break;
1272 /* return in case of fixed depth search */
1273 if( eng_status == PLAYING && st_computer_color == board.color_to_move &&
1274 analysis_limit == DEPTH_LIMIT && s->base_depth == st_depth*PLY)
1275 break;
1277 /* return if 3/5 of time is gone (we can't search another ply anyway) */
1278 if( eng_status == PLAYING && st_computer_color == board.color_to_move &&
1279 analysis_limit == TIME_LIMIT &&
1280 (current_time()-start_think_time) >= (time_best_csec*3/5) )
1281 break;
1283 /* if a checkmate was detected return immediately */
1284 if( ABS(alpha) > INF-1000)
1285 break;
1287 s->base_depth += PLY;
1288 }
1290 exit_thinking:
1292 if(post)
1293 {
1294 output("#nodes: "U64F" (~"U64F" nps)\n", processed_nodes, (processed_nodes*100)/
1295 MAX(current_time()-start_think_time,1) );
1296 print_stats();
1297 }
1299 thinking = false;
1300 return retv;
1301 }