1 /***************************************************************************
2 search.cpp - description
4 begin : Wed Mar 13 2002
5 copyright : (C) 2002-2005 by Monge Maurizio
6 email : monge@linuz.sns.it
7 ***************************************************************************/
9 /***************************************************************************
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. *
16 ***************************************************************************/
26 Move null_threat
[MAX_PV
];
27 bool null_threat_dangerous
[MAX_PV
];
28 uint8_t escape_from_1
[MAX_PV
];
29 uint8_t escape_from_2
[MAX_PV
];
31 #define HISTORY_SIZE (64*64)
32 uint16_t history_tot
[HISTORY_SIZE
];
33 uint16_t history_hit
[HISTORY_SIZE
];
35 #define HISTORY_INDEX(m) (SQUARE_TO_64(m.from)*64 + SQUARE_TO_64(m.to))
36 #define PROF(f,n) {uint64_t tmp = rdtsc(); f; prof_##n += rdtsc()-tmp; }
38 int stat_early_transp
;
46 int stat_search_moves
;
49 int stat_search_moves0
;
51 int stat_evaluate_cutoff
;
61 S(max_quiesce_nodes); \
65 S(quiesce_best_can_be_first); \
66 S(quiesce_best_was_first); \
68 S(quiesce_cutoff_first); \
71 S(search_best_can_be_first); \
72 S(search_best_was_first); \
74 S(search_cutoff_first); \
78 #define STAT(x) stat_##x++;
80 #define S(x) uint64_t stat_##x;
82 Board max_quiesce_board
;
83 int16_t max_quiesce_alpha
;
84 int16_t max_quiesce_beta
;
89 #define S(x) stat_##x = 0;
96 #define S(x) printf("# " #x " = %llu\n", (unsigned long long)stat_##x);
103 #define NEW_HEURISTIC 1
105 /* enable the quiescence search */
108 /* enable the nega-scout pv-search */
111 /* enable the null move */
114 /* enable hashing the positions */
117 /* use the hastable to detect tranpositions */
118 #define TRANSP_TABLE 1
120 /* SEEMS TO BE QUITE BAD:
121 trust the values from a search at lower depth stored in the hashtable
122 to produce a cutoff, taking the value with a margin of uncertainity */
123 #define APPROX_TRANSP_CUTOFF 0
125 /* before doing the alpha beta search check if any of the following positions
126 can give use an early cutoff thanks to the hashtable */
127 #define EARLY_TRANSP_CUTOFF 1
129 /* SEEMS TO BE A BIT BAD:
130 when the we find that the values stored in the hash (the result of a
131 lighter search) were wrong by a big factor, this means that the node is
132 unstable, so re-search it */
133 #define CONSISTENCY_EXTENSION 0
135 /* SEEMS TO BE A BIT BAD:
136 Extend when there is only one decent move */
137 #define SINGULAR_EXTENSION 0
140 reduce nodes for moves that are not check/captures that are considered
141 bad from the heuristic */
142 #define HISTORY_PRUNING 1
144 /* futility pruning: */
147 /* sort the moves to improve alpha-beta cutoff */
150 /* use the candidate move stored in the hashtable */
151 #define HASH_HEURISTIC 1
153 /* when the hashtable provides no "best" move, do a depth-2 search */
154 #define INTERNAL_ITERATIVE_DEEPENING 0
156 /* use the history sorting heuristic */
157 #define HISTORY_HEURISTIC 1
159 /* improve the sorting heuristic for pawn strikes */
160 #define PAWNSTRIKE_HEURISTIC 1
162 /* improve the sorting heuristic for moves to the center */
163 #define CENTER_HEURISTIC 0
169 int base_depth
; /* depth of the search at this ply */
170 int extensions
; /* global extensions at this node */
171 Move
*moves
; /* all generated moves */
172 int num_moves
; /* num of moves */
173 int curr_move
; /* the move being currently analyzed */
174 int16_t alpha
; /* alpha ans beta when the search started (not improved) */
181 Move mv_stack
[200*MAX_PV
];
182 int mv_stack_top
= 0;
183 SearchStack stack
[MAX_PV
];
186 void Engine::print_stat()
188 if(eng_status
!= ANALYZING
)
190 printf("Thinking: ");
191 for(int i
=0; i
<current_ply
; i
++)
193 if(stack
[i
].curr_move
== -2)
194 continue; //Internal iterative deepening
195 else if(stack
[i
].curr_move
== -1)
198 board
.do_null_move();
203 printf("%s", move_to_alg(buf
, &(stack
[i
].moves
[stack
[i
].curr_move
]) ) );
204 board
.do_move(stack
[i
].moves
[stack
[i
].curr_move
]);
206 printf((i
!= current_ply
-1) ? " " : "\n");
215 output("stat01: %d %llu %d %d %d %s\n",
216 current_time() - start_think_time
,
217 (unsigned long long)processed_nodes
,
218 stack
[0].base_depth
/100,
219 stack
[0].num_moves
-1-stack
[0].curr_move
,
221 move_to_alg(buf
, &(stack
[0].moves
[stack
[0].curr_move
]) ) );
224 output("stat01: 0 0 0 0 0\n");
227 void Engine::rewind_thinking()
229 for(int i
=current_ply
-1; i
>=0; i
--)
231 if(stack
[i
].curr_move
== -2)
233 else if(stack
[i
].curr_move
== -1)
234 board
.undo_null_move();
236 board
.undo_move(stack
[i
].moves
[stack
[i
].curr_move
]);
240 void Engine::restore_thinking()
242 for(int i
=0; i
<current_ply
; i
++)
244 if(stack
[i
].curr_move
== -2)
246 else if(stack
[i
].curr_move
== -1)
247 board
.do_null_move();
249 board
.do_move(stack
[i
].moves
[stack
[i
].curr_move
]);
252 /* regenerate pinning info and under_check var, just to be sure :) */
254 board
.find_moves(mvs
);
258 Engine::moves_heuristic(Move
*mv
, int num_mv
, int ply
, int orig_depth
,
259 Move best_mv_hash
, bool quiesce
, Move
* prev
)
263 for(int i
=0;i
<num_mv
;i
++)
268 #if HASH_TABLE && HASH_HEURISTIC
269 /* give a high bonus to the move stored in the hash, if any.
270 mark only which is, don't continue, because some extensions
271 may be triggered ad added later (ie pawn strike, etc) */
272 if(mv
[i
].as_int
== best_mv_hash
.as_int
)
274 #endif //HASH_HEURISTIC
278 if(PIECE_OF(board
.data
[mv
[i
].from
]) != PAWN
&&
279 (mv
[i
].from
== escape_from_1
[ply
-1] || mv
[i
].from
== escape_from_2
[ply
-1]) )
281 int x
= board
.move_see_val(mv
[i
]);
285 mv
[i
].val
+= 29000 + x
; /* escape */
292 /* process strong pawn moves */
293 if(PIECE_OF(board
.data
[mv
[i
].from
])==PAWN
) /* pawn strike */
295 if( ROW_OF(mv
[i
].to
) == board
.seventh_rank
[IS_WHITE(board
.color_to_move
)] )
297 int x
= board
.move_see_val(mv
[i
]);
301 mv
[i
].val
+= 29599; /* 7th push */
302 mv
[i
].extend
= PLY
; /* extend search */
307 if( mv
[i
].flags
== PROMOTEQUEEN
)
309 int x
= board
.move_see_val(mv
[i
]);
313 mv
[i
].val
+= 29600; /* promote! */
314 mv
[i
].extend
= PLY
; /* extend search */
320 if(orig_depth
>= 2*PLY
)
323 uint8_t up_right
= Board::up_dir
[IS_WHITE(board
.color_to_move
)] + RIGHT
;
324 uint8_t up_left
= Board::up_dir
[IS_WHITE(board
.color_to_move
)] + LEFT
;
325 uint8_t p1
= mv
[i
].to
+ up_right
;
326 uint8_t p2
= mv
[i
].to
+ up_left
;
327 uint8_t a
= OUT_OF_BOARD(p1
) ? 0 : board
.data
[p1
];
328 uint8_t b
= OUT_OF_BOARD(p2
) ? 0 : board
.data
[p2
];
329 if( (COLOR_OF(a
)==board
.other_color
&& PIECE_OF(a
)!=PAWN
)
330 || (COLOR_OF(b
)==board
.other_color
&& PIECE_OF(b
)!=PAWN
) )
332 int x
= board
.move_see_val(mv
[i
]);
336 mv
[i
].val
= 27000; /* pawn strike! */
337 //mv[i].extend = PLY; /* extend search */
347 int x
= board
.move_see_val(mv
[i
]);
349 if(prev
&& prev
->capture
)
351 static const int vallapiglia
[] = { 0, 5, 3, 9, 3, 1, 0 };
353 if( (mv
[i
].to
== prev
->to
) && (x
>= vallapiglia
[PIECE_OF(prev
->capture
)]) )
356 if( (x
== vallapiglia
[PIECE_OF(prev
->capture
)]) )
357 mv
[i
].extend
= /*(x==1) ? (PLY/2) :*/ PLY
;
358 // else if(prev->capture && ABS(x - vallapiglia[PIECE_OF(prev->capture)]) == 1)
359 // mv[i].extend = PLY/2;
366 if(orig_depth
>-7*PLY
&& board
.move_is_check(mv
[i
]) )
372 else if(x
>=0 && orig_depth
>-7*PLY
&& board
.move_is_check(mv
[i
]) )
374 /* = capture but check */
379 else /* add a bonus for checks (but not too deep, or quiescence will get mad) */
380 if(orig_depth
>-3*PLY
&& board
.move_is_check(mv
[i
]) )
382 if(board
.move_see_val(mv
[i
])>=0)
389 /* null-move threat */
390 if(null_threat
[ply
-1] == mv
[i
])
396 mv
[i
].val
+= history_hit
[HISTORY_INDEX(mv
[i
])] * 1024 / (history_tot
[HISTORY_INDEX(mv
[i
])] + 4);
399 static int bof
[128] = {
400 0,0,1,2,2,1,0,0,ENDL
,
401 0,1,2,3,3,2,1,0,ENDL
,
402 0,2,4,5,5,4,2,0,ENDL
,
403 1,2,5,6,6,5,2,1,ENDL
,
404 1,2,5,6,6,5,2,1,ENDL
,
405 0,2,4,5,5,4,2,0,ENDL
,
406 0,1,2,3,3,2,1,0,ENDL
,
410 /* add a bonus for moves towards the center */
411 mv
[i
].val
+= (bof
[mv
[i
].to
] - bof
[mv
[i
].from
]);
412 #endif //CENTER_HEURISTIC
416 mv
[hash_move
].val
= 30000;
421 Engine::moves_quiescence_heuristic(Move
*mv
, int num_mv
, const Move
& best_mv_hash
,
422 int static_eval
, int alpha
, int beta
, int orig_depth
, Move
* prev
)
424 for(int i
=0;i
<num_mv
;i
++)
429 #if HASH_TABLE && HASH_HEURISTIC
430 /* give a high bonus to the move stored in the hash, if any.
431 mark only which is, don't continue, because some extensions
432 may be triggered ad added later (ie pawn strike, etc) */
433 if(mv
[i
].as_int
== best_mv_hash
.as_int
)
438 #endif //HASH_HEURISTIC
441 /* process strong pawn moves */
442 if(PIECE_OF(board
.data
[mv
[i
].from
])==PAWN
) /* pawn strike */
444 if( ROW_OF(mv
[i
].to
) == board
.seventh_rank
[IS_WHITE(board
.color_to_move
)] )
446 int x
= board
.move_see_val(mv
[i
]);
454 mv
[i
].val
+= 29499; /* 7th push */
455 mv
[i
].extend
= PLY
; /* extend search */
459 if( mv
[i
].flags
== PROMOTEQUEEN
)
461 int x
= board
.move_see_val(mv
[i
]);
469 mv
[i
].val
+= 29500; /* promote! */
470 mv
[i
].extend
= PLY
; /* extend search */
476 uint8_t p1
= mv
[i
].to
+ up_right
;
477 uint8_t p2
= mv
[i
].to
+ up_left
;
478 uint8_t a
= OUT_OF_BOARD(p1
) ? 0 : board
.data
[p1
];
479 uint8_t b
= OUT_OF_BOARD(p2
) ? 0 : board
.data
[p2
];
480 if( (COLOR_OF(a
)==board
.other_color
&& PIECE_OF(a
)!=PAWN
)
481 || (COLOR_OF(b
)==board
.other_color
&& PIECE_OF(b
)!=PAWN
) )
483 int x
= board
.move_see_val(mv
[i
]);
490 mv
[i
].val
+= 27000; /* pawn strike! */
491 mv
[i
].extend
= PLY
; /* extend search */
499 int x
= board
.move_see_val(mv
[i
]);
501 if(prev
&& prev
->capture
)
503 static const int vallapiglia
[] = { 0, 5, 3, 9, 3, 1, 0 };
505 if( (mv
[i
].to
== prev
->to
) && (x
>= vallapiglia
[PIECE_OF(prev
->capture
)]) )
508 if( (x
== vallapiglia
[PIECE_OF(prev
->capture
)]) )
509 mv
[i
].extend
= /*(x==1) ? (PLY/2) :*/ PLY
;
510 // else if(prev->capture && ABS(x - vallapiglia[PIECE_OF(prev->capture)]) == 1)
511 // mv[i].extend = PLY/2;
518 if(orig_depth
>-5*PLY
&& board
.move_is_check(mv
[i
]) )
524 else if(x
>=0 && orig_depth
>-5*PLY
&& board
.move_is_check(mv
[i
]) )
526 /* = capture but check */
531 else /* add a bonus for checks (but not too deep, or quiescence will get mad) */
532 if(orig_depth
>-3*PLY
&& board
.move_is_check(mv
[i
]) )
534 if(board
.move_see_val(mv
[i
])>=0)
544 /*******************************************************************************
545 The main alpha-beta recursive search function.
546 It handles both normal search (with or without null move)
547 and quiescence search, because i have having 2 almost identical
549 *******************************************************************************/
550 int16_t Engine::search(int ply
, int depth
, bool pv
, int16_t alpha
, int16_t beta
)
552 SearchStack
*s
= &stack
[ply
];
554 uint16_t cbest_mv_hash
= 0; /* the compressed move from the hash */
555 Move best_mv_hash
= Move::FromInt(0); /* the move from the hash */
556 int best_mv_found
= -1; /* the index of the best move AFTER searching */
558 bool extended
= false;
559 int16_t position_val
;
560 #if CONSISTENCY_EXTENSION
561 int old_hash_lower
= -INF
;
562 int old_hash_upper
= INF
;
563 int old_hash_depth
= 0;
564 #endif //CONSISTENCY_EXTENSION
569 s
->base_depth
= depth
;
575 s
->threat
= Move::FromInt(0);
577 null_threat
[ply
] = Move::FromInt(0);
578 null_threat_dangerous
[ply
] = false;
579 //escape_from_1[ply] = escape_from_2[ply] = INVALID;
581 /* check if time is running out */
585 /* check for a draw for repetition or 50mvs. Of course the draw for
586 repetition must be checked BEFORE probing the hash :)*/
588 return (board
.color_to_move
== st_computer_color
) ? -35 :
589 ((board
.other_color
== st_computer_color
) ? 35 : 0); /* be aggressive! */
592 /*******************************************************************************
594 If the probe is succesful the hashtable will return us value
595 that can be exact, a lower bound or an upper bound, and if the
596 depth of the hashed search is >= the current depth this value
597 will be used to improve alpha and beta and possibly return immediatly.
598 The hastable will also give us a "best" move that will be searched
600 This is the move that caused the "final" cutoff when this position
601 was searched previously. This best move is actually the index of the best
602 move in the array of generated moves (it is supposed to be deterministic :)
603 *******************************************************************************/
605 HashEntry
*h
= probe_hash( board
.hash
);
608 if(h
&& (h
->depth
>= s
->base_depth
))// || ABS(h->value)>INF-1000) )
610 int16_t l
= h
->lower();
611 int16_t u
= h
->upper();
618 alpha
= MAX(alpha
, l
);
621 #if APPROX_TRANSP_CUTOFF
622 /* risky, we are assuming that the result of a search at lower
623 depth will not be very different from the true result */
624 if(h
&& depth
<=300 && (h
->depth
>= depth
-100))
626 if(h
->upper()+350<=alpha
)
628 if(h
->lower()-350>=beta
)
631 #endif //APPROX_TRANSP_CUTOFF
632 #endif //TRANSP_TABLE
636 cbest_mv_hash
= h
->best_mv
;
637 #endif //HASH_HEURISTIC
639 #if CONSISTENCY_EXTENSION
640 /* save the bounds stored in the hash, so we can re-search unstable nodes */
643 old_hash_lower
= h
->lo
;
644 old_hash_upper
= h
->up
;
645 old_hash_depth
= h
->depth
;
647 #endif //CONSISTENCY_EXTENSION
652 /*******************************************************************************
653 Test if we are under check, and if so extend search
654 *******************************************************************************/
656 s
->under_check
= board
.under_attack(board
.king_pos
[IS_WHITE(board
.color_to_move
)],
659 /*******************************************************************************
660 If it is time to quiesce, evaluate and test if we can exit
661 immediately with a beta cut-off (try first a rough eval - delta)
662 *******************************************************************************/
666 quiesce
= ((!s
->under_check
) && (depth
<=0)) || (depth
<-60*PLY
);
670 if(quiesce
&& depth
>=-PLY
)
673 Move
*mv
= mv_stack
+ mv_stack_top
;
674 board
.do_null_move();
675 num_mv
= board
.find_moves(mv
);
676 uint8_t pup
= INVALID
;
678 for(int i
=0;i
<num_mv
;i
++)
680 if(!mv
[i
].capture
|| PIECE_OF(mv
[i
].capture
)==PAWN
)
682 if(mv
[i
].to
!= pup
&& board
.move_see_val(mv
[i
])>0)
692 board
.undo_null_move();
699 best
= board
.evaluate(st_computer_color
, alpha
, beta
);
701 alpha
= MAX(alpha
, best
);
704 stat_evaluate_cutoff
++;
717 /*******************************************************************************
719 *******************************************************************************/
720 if(!s
->under_check
&& (stack
[ply
-1].curr_move
!= -1) && depth
>= 2*PLY
&& beta
<INF
-1000)
723 int sdepth
= depth
-3*PLY
;
728 board
.do_null_move();
729 val
= -search( ply
+1, sdepth
, true, -beta
, -beta
+1);
730 board
.undo_null_move();
741 null_threat_dangerous
[ply
] = true;
743 if(val
<alpha
-100 && /* we are facing a threat*/
744 stack
[ply
+1].best_move
!= -1) /* be sure we aren't reading random memory */
746 /* ok, officially the array stack[ply+1].moves has already
747 been deallocated, but who cares :) */
748 s
->threat
= stack
[ply
+1].moves
[stack
[ply
+1].best_move
];
751 /* Botvinnik-Markoff extension!!! */
752 if(!extended
&& ply
>=3 && (s
->threat
== stack
[ply
-2].threat
) )
765 /*******************************************************************************
766 Now generate the legal moves and look for a check/stalemate
767 *******************************************************************************/
769 /* generate all the legal moves */
770 s
->moves
= &mv_stack
[mv_stack_top
];
771 s
->num_moves
= board
.find_moves(s
->moves
);
772 mv_stack_top
+= s
->num_moves
;
773 s
->under_check
= board
.under_check
;
775 if(s
->under_check
==2) /* double check */
780 else if(s
->under_check
) /* simple check */
783 if(stack
[ply
-1].curr_move
>=0 &&
784 !board
.pins
[stack
[ply
-1].moves
[ /* last moved piece is not attacking the king */
785 stack
[ply
-1].curr_move
].to
]) /* so this is a discover check */
792 /* return now if the positon is terminal */
797 /* while mating, sacrify as much as possible :) */
798 best
= -INF
+ ply
;//*50 + board.material[IS_WHITE(eng_color)]/50;
805 /* single-reply extension */
806 if(s
->num_moves
== 1 && !extended
)
811 else if(s
->num_moves
<= 3 && !extended
)
817 /*******************************************************************************
819 First comes the move from the hashtable, if avalable.
820 The remaining moves are sorted with a heuristic that keeps in account
821 the history heuristic (ie the moves that previously caused an alpha
822 cutoff), a MVV/LVA bonus value and a small bonus for moves that go
824 *******************************************************************************/
829 /* convert the move we got from the hash to the move structure */
832 best_mv_hash
= board
.uncompress_move(cbest_mv_hash
);
833 /* if it happened that the move we got from the hashtable
834 is not valid, simply no move will get the high
835 heuristic bonus value */
837 #if INTERNAL_ITERATIVE_DEEPENING
838 else if(s
->base_depth
>3*PLY
&& pv
) /* don't do it only on the pv, or it will be useless :) */
842 int val
= search(ply
+1, s
->base_depth
-2*PLY
, true, alpha
, beta
);
845 HashEntry
*h2
= probe_hash( board
.hash
);
846 if(h2
&& h2
->best_mv
)
848 cbest_mv_hash
= h2
->best_mv
;
849 best_mv_hash
= board
.uncompress_move(cbest_mv_hash
);
852 #endif //INTERNAL_ITERATIVE_DEEPENING
853 #endif //HASH_HEURISTIC
855 /* for each move calculate the heuristic goodness value */
857 Move
*prev
= (stack
[ply
-1].curr_move
>=0) ? &stack
[ply
-1].moves
[stack
[ply
-1].curr_move
] : NULL
;
859 moves_quiescence_heuristic( s
->moves
, s
->num_moves
, best_mv_hash
,
860 best
, alpha
, beta
, s
->base_depth
, prev
);
862 moves_heuristic( s
->moves
, s
->num_moves
, ply
, s
->base_depth
,
863 best_mv_hash
, quiesce
, prev
);
866 /* if quiesce rip-off the "non-critical" moves */
870 for(int i
=0;i
<s
->num_moves
;i
++)
871 if(s
->moves
[i
].val
>0)
872 s
->moves
[n
++] = s
->moves
[i
];
873 mv_stack_top
-= s
->num_moves
-n
;
877 //sort_moves( s->moves, s->num_moves );
882 #if EARLY_TRANSP_CUTOFF && HASH_TABLE
883 /*******************************************************************************
884 Try to get an early beta cutoff using the hash table values
885 of the following moves, and improve alpha too.
886 Try on the first 6 value of the ordered moves (argh, looking into the
887 hashtable is very expensive because of the cache!!!!!!!!)
888 *******************************************************************************/
892 HashKey hk
= board
.move_hash(s
->moves
[0]);
893 for(int i
=1;i
<s
->num_moves
;i
++)
896 HashKey newhk
= board
.move_hash(s
->moves
[i
]);
897 HashEntry
*h2
= probe_hash( hk
);
900 if(h2
&& h2
->depth
>= depth
-100)
907 alpha
= MAX(alpha
, (int16_t)-h2
->up
);
911 HashEntry
*h2
= probe_hash( hk
);
912 if(h2
&& h2
->depth
>= depth
-100)
919 alpha
= MAX(alpha
, (int16_t)-h2
->up
);
922 #endif //EARLY_TRANSP_CUTOFF && HASH_TABLE
925 /* set the current best move index (as will be saved in the hash) */
928 /*******************************************************************************
929 It is now time to loop all the successor moves and search recursively.
930 *******************************************************************************/
933 /* calcluate the evaluation (required by fitility pruning) */
934 position_val
= quiesce
? best
: board
.evaluate( st_computer_color
, -INF
, INF
);
937 for(int i
=0;i
<s
->num_moves
;i
++)
940 int sdepth
= depth
-100;
943 /* sort moves incrementally, in the hope of a beta cut */
944 incremental_sort_moves(s
->moves
+i
, s
->num_moves
-i
);
947 if(depth
< s
->base_depth
+100)
948 sdepth
+= s
->moves
[i
].extend
; /* extensions calculated during the heuristic sort */
951 /* futility pruning, it is done only if we are no under check
952 and the move is not a "critical" move */
953 if(depth
>0 && depth
<3*PLY
&& !s
->under_check
&& s
->moves
[i
].val
< 28000)
955 static const int mavala
[] = { 0, 490, 315, 980, 315, 100, 0 };
957 int16_t fmargin
= (depth
<= PLY
? 420 : 950);
958 int16_t fval
= position_val
+ mavala
[PIECE_OF(s
->moves
[i
].capture
)];
959 if(fval
< alpha
-fmargin
)
964 if(s
->moves
[i
].val
<28000)
966 int ix
= HISTORY_INDEX(s
->moves
[i
]);
967 if(history_tot
[ix
] > 1024)
969 history_tot
[ix
] >>= 1;
970 history_hit
[ix
] >>= 1;
976 if(!quiesce
&& PIECE_OF(board
.data
[s
->moves
[i
].from
]) == PAWN
&& s
->moves
[i
].val
== 27000) //FIXME, UGLY
978 escape_from_1
[ply
] = s
->moves
[i
].to
+ Board::up_dir
[IS_WHITE(board
.color_to_move
)] + RIGHT
;
979 escape_from_2
[ply
] = s
->moves
[i
].to
+ Board::up_dir
[IS_WHITE(board
.color_to_move
)] + LEFT
;
983 escape_from_1
[ply
] = escape_from_2
[ply
] = 0;
989 board
.do_move(s
->moves
[i
]);
993 if(s
->base_depth
> 0 && sdepth
<= 0)
995 STAT(quiesce_called
);
996 q
= stat_quiesce_nodes
;
999 #if NEGA_SCOUT /* use negascout, (null window search for nodes that are not in the pv) */
1000 if(i
== 0) // || depth<200)
1001 val
= -search( ply
+1, sdepth
, pv
, -beta
, -alpha
);
1005 /* history pruning, if this is not a "critical" move and the failhigh
1006 stats are too low, try a reduced depth search (if it returns >alpha,
1007 re-do the full depth search) */
1008 if( !quiesce
&& !s
->under_check
&& depth
<=3*PLY
&& s
->moves
[i
].val
<28000 &&
1009 (history_hit
[HISTORY_INDEX(s
->moves
[i
])]+1)*3
1010 < (history_tot
[HISTORY_INDEX(s
->moves
[i
])]+1) )
1012 val
= -search( ply
+1, sdepth
- 100, false, -alpha
-1, -alpha
);
1014 goto skip_search
; /* reduced search was effective */
1017 val
= -search( ply
+1, sdepth
, false, -alpha
-1, -alpha
);
1018 if((val
>alpha
) && pv
)
1019 val
= -search( ply
+1, sdepth
, true, -beta
, -alpha
);
1022 /* normal full width alpha-beta */
1023 val
= -search( ply
+1, sdepth
, pv
, -beta
, -alpha
);
1026 if(s
->base_depth
> 0 && sdepth
<= 0)
1028 q
= stat_quiesce_nodes
-q
;
1029 if(q
> stat_max_quiesce_nodes
)
1031 stat_max_quiesce_nodes
= q
;
1032 max_quiesce_board
= board
;
1037 board
.undo_move(s
->moves
[i
]);
1040 /* update the current best value and check for and alpha cut */
1041 best
= MAX(best
, val
);
1055 /* update a few stats */
1058 if(best_mv_found
==0)
1065 stat_search_moves
++;
1066 if(ply
==0 && depth
>100)
1068 if(best_mv_found
==0)
1075 stat_search_moves0
++;
1080 !s
->moves
[best_mv_found
].capture
&&
1081 !(s
->moves
[best_mv_found
].flags
>=PROMOTE_FIRST
))
1083 history_hit
[HISTORY_INDEX(s
->moves
[best_mv_found
])]++;
1084 history_tot
[HISTORY_INDEX(s
->moves
[best_mv_found
])]++;
1088 mv_stack_top
-= s
->num_moves
; /* free the moves we allocated */
1089 /*if(best_mv_found>=0 && skip_null)
1090 strong_reply[ply] = mv[best_mv_found];
1092 strong_reply[ply] = Move::FromInt(0);*/
1094 if(stack
[ply
-1].curr_move
== -1 && best_mv_found
>= 0)
1095 null_threat
[ply
-1] = s
->moves
[best_mv_found
];
1098 /* if we found a best move searching, that move will be saved.
1099 if we did no search (ie quiescence), save the old hash value,
1100 or -1 if no hash entry had been found */
1101 int bestmv
= cbest_mv_hash
;
1102 if(best_mv_found
>= 0)
1103 bestmv
= board
.compress_move(s
->moves
[best_mv_found
]);
1105 /* write the value in the hash, with the index of the best move */
1106 write_hash( best
> s
->alpha
? best
: -INF
,
1107 best
< beta
? best
: +INF
,
1108 MAX(s
->base_depth
,-500), bestmv
);
1111 #if CONSISTENCY_EXTENSION
1112 /* instability re-search, ie search deeper the nodes whose value
1113 change a lot since last evaluation */
1115 if(s
->base_depth
< stack
[ply
-1].base_depth
)
1117 if( ((best
< old_hash_lower
-150) ||
1118 (best
> old_hash_upper
+150) )
1119 && old_hash_depth
>=s
->base_depth
-100
1120 && s
->base_depth
<=400 && s
->base_depth
>0)// && !skip_null )
1121 return search(ply
, s
->base_depth
+100, pv
, alpha
, beta
);
1123 #endif //CONSISTENCY_EXTENSION
1129 Move
Engine::find_best_move()
1131 SearchStack
*s
= &stack
[0];
1137 /* initialize the root node */
1139 s
->base_depth
= 100;
1144 s
->threat
= Move::FromInt(0);
1147 s
->moves
= mv_stack
;
1148 s
->num_moves
= mv_stack_top
= board
.find_moves(s
->moves
);
1150 /* to print the analysis */
1152 output("\tply\tscore\ttime\tnodes\tpv\n");
1154 /* return immediatly if the move is forced. */
1158 /* probe the play lines */
1159 if( eng_status
== PLAYING
1160 && st_computer_color
== board
.color_to_move
1161 && probe_lines( board
.hash
, &retv
))
1167 /* probe the book */
1168 if(probe_book( board
.hash
, &retv
)) {
1169 for(int i
=0;i
<s
->num_moves
++;i
++)
1170 if(retv
.as_int
== s
->moves
[i
].as_int
)
1175 output("Error!!! invalid move in the book!!!\n");
1180 prof_find_moves
= 0;
1181 prof_find_captures
= 0;
1183 prof_sort_moves
= 0;
1184 prof_move_is_check
= 0;
1185 prof_move_see_val
= 0;
1189 stat_early_transp
= 0;
1194 stat_best_first
= 0;
1196 stat_search_moves
= 0;
1197 stat_best_first0
= 0;
1199 stat_search_moves0
= 0;
1201 stat_evaluate_cutoff
= 0;
1204 stat_hash_write
= 0;
1209 /* calculate how much time we will think*/
1210 start_think_time
= current_time();
1211 if( analysis_limit
== TIME_LIMIT
)
1213 if(board
.color_to_move
== st_computer_color
)
1215 else /* pondering? analysing? */
1216 time_best_csec
= 99999999;
1217 max_think_time
= start_think_time
+ time_best_csec
- 2;
1220 //analysis_color = board.color_to_move;
1221 processed_nodes
= 0;
1222 int16_t best_guess
= 0;
1226 /* set the back jump for the quick thinking exit */
1230 /* start with a guess of 0 */
1231 s
->moves
[0].val
= 0;
1234 /* do the iterative deepening thing. */
1237 int16_t alpha
= -INF
;
1240 memset( history_tot
, 0, HISTORY_SIZE
*sizeof(uint16_t));
1241 memset( history_hit
, 0, HISTORY_SIZE
*sizeof(uint16_t));
1243 /* save the result of the previous search */
1244 result
[s
->base_depth
/PLY
-1] = s
->moves
[0];
1246 /* for each move call the alpha-beta search function */
1248 for(i
=0;i
<s
->num_moves
;i
++)
1252 board
.do_move(s
->moves
[i
]);
1256 s
->moves
[i
].val
= -search( 1, s
->base_depth
-PLY
, true, -INF
, -alpha
);
1260 s
->moves
[i
].val
= -search( 1, s
->base_depth
-PLY
, false, -alpha
-1, -alpha
);
1261 if(s
->moves
[i
].val
> alpha
)
1262 s
->moves
[i
].val
= -search( 1, s
->base_depth
-PLY
, true, -INF
, -alpha
);
1265 s
->moves
[i
].val
= -search( 1, s
->base_depth
-100, true, -INF
, -alpha
);
1267 board
.undo_move(s
->moves
[i
]);
1272 if(s
->moves
[i
].val
> alpha
)
1274 alpha
= s
->moves
[i
].val
;
1279 /* this move caused an alpha cut, so print the new line */
1280 if( post
/*&& processed_nodes>100000*/)
1282 output("\t%d\t%d\t%d\t%llu\t", s
->base_depth
/100,
1283 s
->moves
[i
].val
, current_time() - start_think_time
, processed_nodes
);
1284 print_moves(&s
->moves
[i
], 1, true);
1291 /* the search is done, sort the moves so that best is searched first */
1294 s
->moves
[best_mv
].val
++;
1295 sort_moves(s
->moves
, i
); /* sort i moves (those that we where able to search) */
1299 /* print the result of the analysis at this depth */
1300 if( post
/*&& processed_nodes>100000*/)
1302 output("\t%d\t%d\t%d\t%llu\t", s
->base_depth
/100,
1303 s
->moves
[0].val
, current_time() - start_think_time
, processed_nodes
);
1304 print_moves(&s
->moves
[0], 1, true);
1308 if( s
->base_depth
>= 40*PLY
)
1311 /* return in case of fixed depth search */
1312 if( eng_status
== PLAYING
&& st_computer_color
== board
.color_to_move
&&
1313 analysis_limit
== DEPTH_LIMIT
&& s
->base_depth
== st_depth
*PLY
)
1316 /* return if 3/5 of time is gone (we can't search another ply anyway) */
1317 if( eng_status
== PLAYING
&& st_computer_color
== board
.color_to_move
&&
1318 analysis_limit
== TIME_LIMIT
&&
1319 (current_time()-start_think_time
) >= (time_best_csec
*3/5) )
1322 /* if a checkmate was detected return immediately */
1323 if( ABS(alpha
) > INF
-1000)
1326 s
->base_depth
+= PLY
;
1334 prof_tot
= rdtsc() - prof_tot
;
1335 #define SHOW_PROF(a) output("@"#a": %llu (%llu%%)\n", \
1336 prof_##a, prof_##a*100/prof_tot);
1340 SHOW_PROF(find_moves
);
1341 SHOW_PROF(find_captures
);
1342 SHOW_PROF(heuristic
);
1343 SHOW_PROF(move_is_check
);
1344 SHOW_PROF(move_see_val
);
1345 SHOW_PROF(sort_moves
);
1347 output("#nodes: %llu (~%llu nps)\n", processed_nodes
, (processed_nodes
*100)/
1348 MAX(current_time()-start_think_time
,1) );
1349 output("# %d times all the moves were seached (non-leaf non-quiesce node)\n",
1351 output("# of which %d times first move caused a cutoff\n", stat_best_cut
);
1352 output("# of the remaining %d times first move was really best (%02d%%)\n",
1353 stat_best_first
, (stat_best_first
*100)/MAX(stat_search_moves
-stat_best_cut
, 1));
1354 output("# evaluate was called %d times (quiescence node)\n", stat_evaluate
);
1355 output("# of which %d times caused an early cutoff (leaf node)\n",
1356 stat_evaluate_cutoff
);
1357 output("#hash: %d writes, %d probes (%d succesful, =%d, >%d, <%d)\n",
1358 stat_hash_write
, stat_hash_tot
, stat_hash_ex
+stat_hash_low
+stat_hash_upp
,
1359 stat_hash_ex
, stat_hash_low
, stat_hash_upp
);
1360 output("#etc: %d\n", stat_early_transp
);
1361 output("#null move: %d (%d succesful)\n", stat_null_move
, stat_null_cut
);
1365 max_quiesce_board
.write_board(buf
);
1366 output("#max quiesce board: %s [%d %d]\n", buf
, max_quiesce_alpha
, max_quiesce_beta
);