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
];
29 #define HISTORY_SIZE (64*64)
30 uint16_t history_tot
[HISTORY_SIZE
];
31 uint16_t history_hit
[HISTORY_SIZE
];
33 #define HISTORY_INDEX(m) (SQUARE_TO_64(m.from)*64 + SQUARE_TO_64(m.to))
34 #define PROF(f,n) {uint64_t tmp = rdtsc(); f; prof_##n += rdtsc()-tmp; }
37 uint64_t prof_find_moves;
38 uint64_t prof_find_captures;
39 uint64_t prof_heuristic;
40 uint64_t prof_sort_moves;
41 uint64_t prof_do_move;
42 uint64_t prof_move_is_check;
43 uint64_t prof_move_see_val;
46 int stat_early_transp
;
54 int stat_search_moves
;
57 int stat_search_moves0
;
59 int stat_evaluate_cutoff
;
77 void print(int depth
= 0);
78 void print_root(int depth
= 0);
81 void QNode::del_children()
83 for(int i
=0;i
<num_children
;i
++)
84 children
[i
].del_children();
88 void QNode::print_root(int depth
)
90 for(int i
=0;i
<num_children
;i
++)
91 children
[i
].print(depth
);
94 void QNode::print(int depth
)
97 static const char* types
[] = { "zero??", "DRAW", "HASH_LOW", "HASH_HIGH", "EVAL", "MATE", "SEARCH", };
99 Engine::eng()->move_to_alg(buf
, &move
);
100 //printf("%d ", depth);
101 for(int i
=0;i
<depth
;i
++)printf("| ");
102 printf("|%s (weight=%d guess=%d value=%d depth=%d window=[%d %d] type=%s)\n", buf
, weight
,
103 move
.val
, value
, this->depth
, alpha
, beta
, types
[type
]);
105 Engine::eng()->board
.do_move(move
);
107 Engine::eng()->board
.undo_move(move
);
115 S(max_quiesce_nodes); \
119 S(quiesce_best_can_be_first); \
120 S(quiesce_best_was_first); \
122 S(quiesce_cutoff_first); \
125 S(search_best_can_be_first); \
126 S(search_best_was_first); \
128 S(search_cutoff_first); \
132 #define STAT(x) stat_##x++;
134 #define S(x) uint64_t stat_##x;
136 Board max_quiesce_board
;
137 int16_t max_quiesce_alpha
;
138 int16_t max_quiesce_beta
;
143 #define S(x) stat_##x = 0;
150 #define S(x) printf("# " #x " = %llu\n", (unsigned long long)stat_##x);
157 #define NEW_HEURISTIC 1
159 #define NEW_QUIESCENCE 0
161 /* enable the quiescence search */
164 /* enable the nega-scout pv-search */
167 /* enable the null move */
170 /* enable hashing the positions */
173 /* use the hastable to detect tranpositions */
174 #define TRANSP_TABLE 1
176 /* SEEMS TO BE QUITE BAD:
177 trust the values from a search at lower depth stored in the hashtable
178 to produce a cutoff, taking the value with a margin of uncertainity */
179 #define APPROX_TRANSP_CUTOFF 0
181 /* before doing the alpha beta search check if any of the following positions
182 can give use an early cutoff thanks to the hashtable */
183 #define EARLY_TRANSP_CUTOFF 1
185 /* SEEMS TO BE A BIT BAD:
186 when the we find that the values stored in the hash (the result of a
187 lighter search) were wrong by a big factor, this means that the node is
188 unstable, so re-search it */
189 #define CONSISTENCY_EXTENSION 0
191 /* SEEMS TO BE A BIT BAD:
192 Extend when there is only one decent move */
193 #define SINGULAR_EXTENSION 0
196 reduce nodes for moves that are not check/captures that are considered
197 bad from the heuristic */
198 #define HISTORY_PRUNING 1
200 /* futility pruning: */
203 /* sort the moves to improve alpha-beta cutoff */
206 /* use the candidate move stored in the hashtable */
207 #define HASH_HEURISTIC 1
209 /* when the hashtable provides no "best" move, do a depth-2 search */
210 #define INTERNAL_ITERATIVE_DEEPENING 0
212 /* use the history sorting heuristic */
213 #define HISTORY_HEURISTIC 0
215 /* use the Max Value Victim/Least Value Attacker sorting heuristic */
216 #define MVV_LVA_HEURISTIC 1
218 /* improve the sorting heuristic for pawn strikes */
219 #define PAWNSTRIKE_HEURISTIC 1
221 /* improve the sorting heuristic for moves to the center */
222 #define CENTER_HEURISTIC 0
224 /* search 2 times per ply, to compare our move sorting to the perfect move sorting */
231 int base_depth
; /* depth of the search at this ply */
232 int extensions
; /* global extensions at this node */
233 Move
*moves
; /* all generated moves */
234 int num_moves
; /* num of moves */
235 int curr_move
; /* the move being currently analyzed */
236 int16_t alpha
; /* alpha ans beta when the search started (not improved) */
243 Move mv_stack
[200*MAX_PV
];
244 int mv_stack_top
= 0;
245 SearchStack stack
[MAX_PV
];
248 void Engine::print_stat()
250 if(eng_status
!= ANALYZING
)
252 printf("Thinking: ");
253 for(int i
=0; i
<current_ply
; i
++)
255 if(stack
[i
].curr_move
== -2)
258 } //Internal iterative deepening
259 else if(stack
[i
].curr_move
== -1)
262 board
.do_null_move();
267 printf("%s", move_to_alg(buf
, &(stack
[i
].moves
[stack
[i
].curr_move
]) ) );
268 board
.do_move(stack
[i
].moves
[stack
[i
].curr_move
]);
270 printf((i
!= current_ply
-1) ? " " : "\n");
279 output("stat01: %d %llu %d %d %d %s\n",
280 current_time() - start_think_time
,
281 (unsigned long long)processed_nodes
,
282 stack
[0].base_depth
/100,
283 stack
[0].num_moves
-1-stack
[0].curr_move
,
285 move_to_alg(buf
, &(stack
[0].moves
[stack
[0].curr_move
]) ) );
288 output("stat01: 0 0 0 0 0\n");
291 void Engine::rewind_thinking()
293 for(int i
=current_ply
-1; i
>=0; i
--)
295 if(stack
[i
].curr_move
== -2)
297 else if(stack
[i
].curr_move
== -1)
298 board
.undo_null_move();
300 board
.undo_move(stack
[i
].moves
[stack
[i
].curr_move
]);
304 void Engine::restore_thinking()
306 for(int i
=0; i
<current_ply
; i
++)
308 if(stack
[i
].curr_move
== -2)
310 else if(stack
[i
].curr_move
== -1)
311 board
.do_null_move();
313 board
.do_move(stack
[i
].moves
[stack
[i
].curr_move
]);
316 /* regenerate pinning info and under_check var, just to be sure :) */
318 board
.find_moves(mvs
);
322 Engine::moves_heuristic(Move
*mv
, int num_mv
, int ply
, int orig_depth
,
323 Move best_mv_hash
, bool quiesce
, Move
* prev
)
325 /*uint8_t up_right = Board::up_dir[IS_WHITE(board.color_to_move)] + RIGHT;
326 uint8_t up_left = Board::up_dir[IS_WHITE(board.color_to_move)] + LEFT;*/
329 for(int i
=0;i
<num_mv
;i
++)
334 #if HASH_TABLE && HASH_HEURISTIC
335 /* give a high bonus to the move stored in the hash, if any.
336 mark only which is, don't continue, because some extensions
337 may be triggered ad added later (ie pawn strike, etc) */
338 if(mv
[i
].as_int
== best_mv_hash
.as_int
)
340 #endif //HASH_HEURISTIC
343 /* process strong pawn moves */
344 if(PIECE_OF(board
.data
[mv
[i
].from
])==PAWN
) /* pawn strike */
346 if( ROW_OF(mv
[i
].to
) == board
.seventh_rank
[IS_WHITE(board
.color_to_move
)] )
348 int x
= board
.move_see_val(mv
[i
]);
356 mv
[i
].val
+= 29499; /* 7th push */
357 mv
[i
].extend
= 1; /* extend search */
361 if( mv
[i
].flags
== PROMOTEQUEEN
)
363 int x
= board
.move_see_val(mv
[i
]);
371 mv
[i
].val
+= 29500; /* promote! */
372 mv
[i
].extend
= 1; /* extend search */
378 uint8_t p1
= mv
[i
].to
+ up_right
;
379 uint8_t p2
= mv
[i
].to
+ up_left
;
380 uint8_t a
= OUT_OF_BOARD(p1
) ? 0 : board
.data
[p1
];
381 uint8_t b
= OUT_OF_BOARD(p2
) ? 0 : board
.data
[p2
];
382 if( (COLOR_OF(a
)==board
.other_color
&& PIECE_OF(a
)!=PAWN
)
383 || (COLOR_OF(b
)==board
.other_color
&& PIECE_OF(b
)!=PAWN
) )
385 int x
= board
.move_see_val(mv
[i
]);
392 mv
[i
].val
+= 27000; /* pawn strike! */
393 mv
[i
].extend
= 1; /* extend search */
401 int x
= board
.move_see_val(mv
[i
]);
405 static const int vallapiglia
[] = { 0, 5, 3, 9, 3, 1, 0 };
407 if(mv
[i
].to
== prev
->to
)
408 if(x
>= vallapiglia
[PIECE_OF(prev
->capture
)])
417 if(orig_depth
>-7*PLY
&& board
.move_is_check(mv
[i
]) )
423 else if(x
>=0 && orig_depth
>-7*PLY
&& board
.move_is_check(mv
[i
]) )
425 /* = capture but check */
430 else /* add a bonus for checks (but not too deep, or quiescence will get mad) */
431 if(orig_depth
>-3*PLY
&& board
.move_is_check(mv
[i
]) )
433 if(board
.move_see_val(mv
[i
])>=0)
440 if(null_threat
[ply
-1] == mv
[i
])
446 mv
[i
].val
+= history_hit
[HISTORY_INDEX(mv
[i
])] * 512 / (history_tot
[HISTORY_INDEX(mv
[i
])] + 4);
449 static int bof
[128] = {
450 0,0,1,2,2,1,0,0,ENDL
,
451 0,1,2,3,3,2,1,0,ENDL
,
452 0,2,4,5,5,4,2,0,ENDL
,
453 1,2,5,6,6,5,2,1,ENDL
,
454 1,2,5,6,6,5,2,1,ENDL
,
455 0,2,4,5,5,4,2,0,ENDL
,
456 0,1,2,3,3,2,1,0,ENDL
,
460 /* add a bonus for moves towards the center */
461 mv
[i
].val
+= (bof
[mv
[i
].to
] - bof
[mv
[i
].from
]);
462 #endif //CENTER_HEURISTIC
466 mv
[hash_move
].val
= 30000;
472 Engine::moves_quiescence_heuristic(Move
*mv
, int num_mv
, const Move
& best_mv_hash
,
473 int static_eval
, int alpha
, int beta
, int orig_depth
, Move
* prev
)
475 for(int i
=0;i
<num_mv
;i
++)
480 #if HASH_TABLE && HASH_HEURISTIC
481 /* give a high bonus to the move stored in the hash, if any.
482 mark only which is, don't continue, because some extensions
483 may be triggered ad added later (ie pawn strike, etc) */
484 if(mv
[i
].as_int
== best_mv_hash
.as_int
)
489 #endif //HASH_HEURISTIC
492 /* process strong pawn moves */
493 if(PIECE_OF(board
.data
[mv
[i
].from
])==PAWN
) /* pawn strike */
495 if( ROW_OF(mv
[i
].to
) == board
.seventh_rank
[IS_WHITE(board
.color_to_move
)] )
497 int x
= board
.move_see_val(mv
[i
]);
505 mv
[i
].val
+= 29499; /* 7th push */
506 mv
[i
].extend
= 1; /* extend search */
510 if( mv
[i
].flags
== PROMOTEQUEEN
)
512 int x
= board
.move_see_val(mv
[i
]);
520 mv
[i
].val
+= 29500; /* promote! */
521 mv
[i
].extend
= 1; /* extend search */
527 uint8_t p1
= mv
[i
].to
+ up_right
;
528 uint8_t p2
= mv
[i
].to
+ up_left
;
529 uint8_t a
= OUT_OF_BOARD(p1
) ? 0 : board
.data
[p1
];
530 uint8_t b
= OUT_OF_BOARD(p2
) ? 0 : board
.data
[p2
];
531 if( (COLOR_OF(a
)==board
.other_color
&& PIECE_OF(a
)!=PAWN
)
532 || (COLOR_OF(b
)==board
.other_color
&& PIECE_OF(b
)!=PAWN
) )
534 int x
= board
.move_see_val(mv
[i
]);
541 mv
[i
].val
+= 27000; /* pawn strike! */
542 mv
[i
].extend
= 1; /* extend search */
550 int x
= board
.move_see_val(mv
[i
]);
554 static const int vallapiglia
[] = { 0, 5, 3, 9, 3, 1, 0 };
556 if(mv
[i
].to
== prev
->to
)
557 if(x
>= vallapiglia
[PIECE_OF(prev
->capture
)])
566 if(orig_depth
>-5*PLY
&& board
.move_is_check(mv
[i
]) )
572 else if(x
>=0 && orig_depth
>-5*PLY
&& board
.move_is_check(mv
[i
]) )
574 /* = capture but check */
579 else /* add a bonus for checks (but not too deep, or quiescence will get mad) */
580 if(orig_depth
>-3*PLY
&& board
.move_is_check(mv
[i
]) )
582 if(board
.move_see_val(mv
[i
])>=0)
594 Engine::moves_quiescence_heuristic(Move
*mv
, int num_mv
, const Move
& best_mv_hash
,
595 int static_eval
, int alpha
, int beta
, int depth
, Move
* prev
)
597 for(int i
=0;i
<num_mv
;i
++)
602 /* give a high bonus to the move stored in the hash, if any. */
603 if(mv
[i
].as_int
== best_mv_hash
.as_int
)
609 if( mv
[i
].flags
== PROMOTEQUEEN
)
617 int x
= board
.move_see_val(mv
[i
]);
619 if( (static_eval
== -INF
&& x
>0)
620 || (static_eval
+ x
*100 + 100 > alpha
) )
622 if( board
.move_is_check(mv
[i
]) )
623 mv
[i
].val
= 15000 + x
*64;
625 mv
[i
].val
= 10000 + x
*64;
630 if( (depth
>= -7*PLY
) && board
.move_is_check(mv
[i
]))
631 mv
[i
].val
= 5000 + x
*64;
632 else if( (depth
>= -2*PLY
) && (x
>= 0) )
633 mv
[i
].val
= 1000 + x
*64;
638 if( (depth
>= -3*PLY
) && board
.move_is_check(mv
[i
]) )
641 A88 atk
= IS_WHITE(board
.other_color
) ? board
.w_attacks
: board
.b_attacks
;
642 A88 def
= IS_WHITE(board
.color_to_move
) ? board
.w_attacks
: board
.b_attacks
;
644 if(atk
[mv
[i
].to
] && !def
[mv
[i
].to
])
664 QNode
* quiescence_node
= NULL
;
666 //r1b3k1/2p2rpp/p1P5/1p2N3/6nq/N1P5/PP1P1bPP/R1BQR1K1 w - - 0 1
668 Engine::test_quiescence(int16_t alpha
, int16_t beta
)
671 quiescence_node
= &qroot
;
674 quiesce(0, 100, alpha
, beta
);
676 qroot
.del_children();
678 quiescence_node
= NULL
;
682 Engine::quiesce(int ply
, int depth
, int16_t alpha
, int16_t beta
)
684 SearchStack
*s
= &stack
[ply
];
685 int16_t static_eval
= -INF
;
687 int16_t best_guessed
= alpha
;
688 uint16_t cbest_mv_hash
= 0; /* the compressed move from the hash */
689 Move best_mv_hash
= Move::FromInt(0); /* the move from the hash */
690 int best_mv_found
= -1; /* the index of the best move AFTER searching */
691 bool dangerous_position
= false;
693 QNode
*info_node
= quiescence_node
;
694 if(info_node
)info_node
->children
= 0;
695 if(info_node
)info_node
->num_children
= 0;
696 if(info_node
)info_node
->type
= 0;
697 if(info_node
)info_node
->depth
= depth
;
698 if(info_node
)info_node
->alpha
= alpha
;
699 if(info_node
)info_node
->beta
= beta
;
716 s
->threat
= Move::FromInt(0);
719 prefetch_hash( board
.hash
);
721 /* check if time is running out */
725 /* check for a draw for repetition or 50mvs. Of course the draw for
726 repetition must be checked BEFORE probing the hash :)*/
729 int16_t draw
= (board
.color_to_move
== st_computer_color
) ? v_eval_draw
:
730 ((board
.other_color
== st_computer_color
) ? -v_eval_draw
: 0); /* be aggressive! */
731 if(info_node
)info_node
->value
= draw
;
732 if(info_node
)info_node
->type
= 1;
737 /*******************************************************************************
739 If the probe is succesful the hashtable will return us value
740 that can be exact, a lower bound or an upper bound, and if the
741 depth of the hashed search is >= the current depth this value
742 will be used to improve alpha and beta and possibly return immediatly.
743 The hastable will also give us a "best" move that will be searched
745 This is the move that caused the "final" cutoff when this position
746 was searched previously. This best move is actually the index of the best
747 move in the array of generated moves (it is supposed to be deterministic :)
748 *******************************************************************************/
750 HashEntry
*h
= probe_hash( board
.hash
);
754 int16_t l
= h
->lower();
755 int16_t u
= h
->upper();
760 if(info_node
)info_node
->value
= l
;
761 if(info_node
)info_node
->type
= 2;
767 if(info_node
)info_node
->value
= u
;
768 if(info_node
)info_node
->type
= 3;
773 alpha
= MAX(alpha
, l
);
775 cbest_mv_hash
= h
->best_mv
;
776 best_guessed
= MAX(best_guessed
, h
->lower());
780 /*******************************************************************************
781 Test if we are under check, and if so extend search
782 *******************************************************************************/
784 s
->under_check
= board
.under_attack(board
.king_pos
[IS_WHITE(board
.color_to_move
)],
788 dangerous_position
= true;
793 // Move *mv = mv_stack + mv_stack_top;
794 // board.do_null_move();
795 // num_mv = board.find_moves(mv);
797 // for(int i=0;i<num_mv;i++)
799 // if(!mv[i].capture)
801 // if(board.move_see_val(mv[i])>0)
805 // board.undo_null_move();
807 // dangerous_position = true;
811 dangerous_position
= false;
813 if(!dangerous_position
)
815 best
= static_eval
= board
.evaluate(st_computer_color
, alpha
, beta
);
817 alpha
= MAX(alpha
, best
);
820 if(info_node
)info_node
->value
= best
;
821 if(info_node
)info_node
->type
= 4;
830 /*******************************************************************************
831 Now generate the legal moves and look for a check/stalemate
832 *******************************************************************************/
834 /* generate all the legal moves */
835 s
->moves
= &mv_stack
[mv_stack_top
];
836 s
->num_moves
= board
.find_moves(s
->moves
);
837 mv_stack_top
+= s
->num_moves
;
838 s
->under_check
= board
.under_check
;
840 /* return now if the positon is terminal */
844 /* while mating, sacrify as much as possible :) */
845 best
= -INF
+ ply
;//*50 + board.material[IS_WHITE(eng_color)]/50;
848 if(info_node
)info_node
->value
= best
;
849 if(info_node
)info_node
->type
= 5;
854 /*******************************************************************************
856 First comes the move from the hashtable, if avalable.
857 The remaining moves are sorted with a heuristic that keeps in account
858 the history heuristic (ie the moves that previously caused an alpha
859 cutoff), a MVV/LVA bonus value and a small bonus for moves that go
861 *******************************************************************************/
863 /* convert the move we got from the hash to the move structure */
866 best_mv_hash
= board
.uncompress_move(cbest_mv_hash
);
867 /* if it happened that the move we got from the hashtable
868 is not valid, simply no move will get the high
869 heuristic bonus value */
872 /* for each move calculate the heuristic goodness value */
873 moves_quiescence_heuristic(s
->moves
, s
->num_moves
, best_mv_hash
, static_eval
, alpha
, beta
, depth
, NULL
);
875 /* if quiesce rip-off bad moves */
876 if(!dangerous_position
)
879 for(int i
=0;i
<s
->num_moves
;i
++)
880 if(s
->moves
[i
].val
>=0)
881 s
->moves
[n
++] = s
->moves
[i
];
882 mv_stack_top
-= s
->num_moves
-n
;
886 /* sort the moves using the heuristic values */
888 sort_moves( s
->moves
, s
->num_moves
);
890 /* set the current best move index (as will be saved in the hash) */
893 /*******************************************************************************
894 It is now time to loop all the successor moves and search recursively.
895 *******************************************************************************/
897 if(info_node
)info_node
->children
= (QNode
*)malloc(sizeof(QNode
)*s
->num_moves
);
899 for(int i
=0;i
<s
->num_moves
;i
++)
903 /* sort moves incrementally, in the hope of a beta cut */
904 //incremental_sort_moves(s->moves+i, s->num_moves-i);
906 uint64_t w
= stat_quiesce_nodes
;
907 if(info_node
)info_node
->num_children
++;
908 if(info_node
)quiescence_node
= &info_node
->children
[i
];
909 if(info_node
)quiescence_node
->move
= s
->moves
[i
];
913 board
.do_move(s
->moves
[i
]);
914 val
= -quiesce( ply
+1, depth
- 100, -beta
, -alpha
);
915 board
.undo_move(s
->moves
[i
]);
918 if(info_node
)info_node
->children
[i
].weight
= stat_quiesce_nodes
-w
;
920 /* update the current best value and check for and alpha cut */
921 best
= MAX(best
, val
);
934 STAT(quiesce_cutoff
);
936 STAT(quiesce_cutoff_first
);
941 if(info_node
)info_node
->value
= best
;
942 if(info_node
)info_node
->type
= 6;
945 mv_stack_top
-= s
->num_moves
; /* free the moves we allocated */
947 /* if we found a best move searching, that move will be saved.
948 if we did no search (ie quiescence), save the old hash value,
949 or -1 if no hash entry had been found */
950 int bestmv
= cbest_mv_hash
;
951 if(best_mv_found
>= 0)
953 bestmv
= board
.compress_move(s
->moves
[best_mv_found
]);
954 STAT(quiesce_best_can_be_first
);
955 if(best_mv_found
== 0)
956 STAT(quiesce_best_was_first
);
959 /* write the value in the hash, with the index of the best move */
960 write_hash( best
> s
->alpha
? best
: -INF
,
961 best
< beta
? best
: +INF
, 0, bestmv
);
967 /*******************************************************************************
968 The main alpha-beta recursive search function.
969 It handles both normal search (with or without null move)
970 and quiescence search, because i have having 2 almost identical
972 *******************************************************************************/
973 int16_t Engine::search(int ply
, int depth
, bool pv
, int16_t alpha
, int16_t beta
)
975 SearchStack
*s
= &stack
[ply
];
977 uint16_t cbest_mv_hash
= 0; /* the compressed move from the hash */
978 Move best_mv_hash
= Move::FromInt(0); /* the move from the hash */
979 int best_mv_found
= -1; /* the index of the best move AFTER searching */
981 bool extended
= false;
982 int16_t position_val
;
983 #if CONSISTENCY_EXTENSION
984 int old_hash_lower
= -INF
;
985 int old_hash_upper
= INF
;
986 int old_hash_depth
= 0;
987 #endif //CONSISTENCY_EXTENSION
992 s
->base_depth
= depth
;
998 s
->threat
= Move::FromInt(0);
1000 null_threat
[ply
] = Move::FromInt(0);
1001 null_threat_dangerous
[ply
] = false;
1003 /* check if time is running out */
1007 /* check for a draw for repetition or 50mvs. Of course the draw for
1008 repetition must be checked BEFORE probing the hash :)*/
1010 return (board
.color_to_move
== st_computer_color
) ? -35 :
1011 ((board
.other_color
== st_computer_color
) ? 35 : 0); /* be aggressive! */
1014 /*******************************************************************************
1015 Probe the hashtable.
1016 If the probe is succesful the hashtable will return us value
1017 that can be exact, a lower bound or an upper bound, and if the
1018 depth of the hashed search is >= the current depth this value
1019 will be used to improve alpha and beta and possibly return immediatly.
1020 The hastable will also give us a "best" move that will be searched
1022 This is the move that caused the "final" cutoff when this position
1023 was searched previously. This best move is actually the index of the best
1024 move in the array of generated moves (it is supposed to be deterministic :)
1025 *******************************************************************************/
1027 HashEntry
*h
= probe_hash( board
.hash
);
1030 if(h
&& (h
->depth
>= s
->base_depth
))// || ABS(h->value)>INF-1000) )
1032 int16_t l
= h
->lower();
1033 int16_t u
= h
->upper();
1039 beta
= MIN(beta
, u
);
1040 alpha
= MAX(alpha
, l
);
1043 #if APPROX_TRANSP_CUTOFF
1044 /* risky, we are assuming that the result of a search at lower
1045 depth will not be very different from the true result */
1046 if(h
&& depth
<=300 && (h
->depth
>= depth
-100))
1048 if(h
->upper()+350<=alpha
)
1050 if(h
->lower()-350>=beta
)
1053 #endif //APPROX_TRANSP_CUTOFF
1054 #endif //TRANSP_TABLE
1058 cbest_mv_hash
= h
->best_mv
;
1059 #endif //HASH_HEURISTIC
1061 #if CONSISTENCY_EXTENSION
1062 /* save the bounds stored in the hash, so we can re-search unstable nodes */
1065 old_hash_lower
= h
->lo
;
1066 old_hash_upper
= h
->up
;
1067 old_hash_depth
= h
->depth
;
1069 #endif //CONSISTENCY_EXTENSION
1074 /*******************************************************************************
1075 Test if we are under check, and if so extend search
1076 *******************************************************************************/
1078 s
->under_check
= board
.under_attack(board
.king_pos
[IS_WHITE(board
.color_to_move
)],
1088 /*******************************************************************************
1089 If it is time to quiesce, evaluate and test if we can exit
1090 immediately with a beta cut-off (try first a rough eval - delta)
1091 *******************************************************************************/
1095 quiesce
= ((!s
->under_check
) && (depth
<=0)) || (depth
<-60*PLY
);
1099 if(quiesce
&& depth
>=-100)
1102 Move
*mv
= mv_stack
+ mv_stack_top
;
1103 board
.do_null_move();
1104 num_mv
= board
.find_moves(mv
);
1106 for(int i
=0;i
<num_mv
;i
++)
1110 if(board
.move_see_val(mv
[i
])>0)
1117 board
.undo_null_move();
1124 best
= board
.evaluate(st_computer_color
, alpha
, beta
);
1126 alpha
= MAX(alpha
, best
);
1129 stat_evaluate_cutoff
++;
1142 /*******************************************************************************
1144 *******************************************************************************/
1145 if(!s
->under_check
&& (stack
[ply
-1].curr_move
!= -1) && depth
>= 2*PLY
&& beta
<INF
-1000)
1148 int sdepth
= depth
-3*PLY
;
1153 board
.do_null_move();
1154 val
= -search( ply
+1, sdepth
, true, -beta
, -beta
+1);
1155 board
.undo_null_move();
1158 /* null move cut! */
1166 null_threat_dangerous
[ply
] = true;
1168 if(val
<alpha
-100 && /* we are facing a threat*/
1169 stack
[ply
+1].best_move
!= -1) /* be sure we aren't reading random memory */
1171 /* ok, officially the array stack[ply+1].moves has already
1172 been deallocated, but who cares :) */
1173 s
->threat
= stack
[ply
+1].moves
[stack
[ply
+1].best_move
];
1176 /* Botvinnik-Markoff extension!!! */
1177 if(!extended
&& ply
>=3 && (s
->threat
== stack
[ply
-2].threat
) )
1190 /*******************************************************************************
1191 Now generate the legal moves and look for a check/stalemate
1192 *******************************************************************************/
1194 /* generate all the legal moves */
1195 s
->moves
= &mv_stack
[mv_stack_top
];
1196 s
->num_moves
= board
.find_moves(s
->moves
);
1197 mv_stack_top
+= s
->num_moves
;
1198 s
->under_check
= board
.under_check
;
1200 if(s
->under_check
==2) /* double check */
1205 else if(s
->under_check
) /* simple check */
1208 if(stack
[ply
-1].curr_move
>=0 &&
1209 !board
.pins
[stack
[ply
-1].moves
[ /* last moved piece is not attacking the king */
1210 stack
[ply
-1].curr_move
].to
]) /* so this is a discover check */
1217 /* return now if the positon is terminal */
1222 /* while mating, sacrify as much as possible :) */
1223 best
= -INF
+ ply
;//*50 + board.material[IS_WHITE(eng_color)]/50;
1230 /* single-reply extension */
1231 if(s
->num_moves
== 1 && !extended
)
1236 else if(s
->num_moves
<= 3 && !extended
)
1242 /*******************************************************************************
1244 First comes the move from the hashtable, if avalable.
1245 The remaining moves are sorted with a heuristic that keeps in account
1246 the history heuristic (ie the moves that previously caused an alpha
1247 cutoff), a MVV/LVA bonus value and a small bonus for moves that go
1249 *******************************************************************************/
1254 /* convert the move we got from the hash to the move structure */
1257 best_mv_hash
= board
.uncompress_move(cbest_mv_hash
);
1258 /* if it happened that the move we got from the hashtable
1259 is not valid, simply no move will get the high
1260 heuristic bonus value */
1262 #if INTERNAL_ITERATIVE_DEEPENING
1263 else if(s
->base_depth
>3*PLY
&& pv
) /* don't do it only on the pv, or it will be useless :) */
1267 int val
= search(ply
+1, s
->base_depth
-2*PLY
, true, alpha
, beta
);
1270 HashEntry
*h2
= probe_hash( board
.hash
);
1271 if(h2
&& h2
->best_mv
)
1273 cbest_mv_hash
= h2
->best_mv
;
1274 best_mv_hash
= board
.uncompress_move(cbest_mv_hash
);
1277 #endif //INTERNAL_ITERATIVE_DEEPENING
1278 #endif //HASH_HEURISTIC
1280 /* for each move calculate the heuristic goodness value */
1282 Move
*prev
= (stack
[ply
-1].curr_move
>=0) ? &stack
[ply
-1].moves
[stack
[ply
-1].curr_move
] : NULL
;
1285 moves_quiescence_heuristic( s
->moves
, s
->num_moves
, best_mv_hash
,
1286 best
, alpha
, beta
, s
->base_depth
, prev
);
1289 moves_heuristic( s
->moves
, s
->num_moves
, ply
, s
->base_depth
,
1290 best_mv_hash
, quiesce
, prev
);
1293 /* if quiesce rip-off the "non-critical" moves */
1297 for(int i
=0;i
<s
->num_moves
;i
++)
1298 if(s
->moves
[i
].val
>0)
1299 s
->moves
[n
++] = s
->moves
[i
];
1300 mv_stack_top
-= s
->num_moves
-n
;
1304 //sort_moves( s->moves, s->num_moves );
1309 #if EARLY_TRANSP_CUTOFF && HASH_TABLE
1310 /*******************************************************************************
1311 Try to get an early beta cutoff using the hash table values
1312 of the following moves, and improve alpha too.
1313 Try on the first 6 value of the ordered moves (argh, looking into the
1314 hashtable is very expensive because of the cache!!!!!!!!)
1315 *******************************************************************************/
1317 for(int i
=MIN(s
->num_moves
-1,10);i
>0;i
--)
1319 HashKey hk
= board
.move_hash(s
->moves
[i
]);
1320 HashEntry
*h2
= probe_hash( hk
);
1323 if(h2
&& h2
->depth
>= depth
-100)
1325 int16_t u
= h2
->upper();
1328 /* increase the node count to simulate calling
1329 the search function for this move */
1330 stat_early_transp
++;
1338 #endif //EARLY_TRANSP_CUTOFF && HASH_TABLE
1341 /* set the current best move index (as will be saved in the hash) */
1344 /*******************************************************************************
1345 It is now time to loop all the successor moves and search recursively.
1346 *******************************************************************************/
1348 /* calcluate the evaluation (required by fitility pruning) */
1349 position_val
= quiesce
? best
: board
.evaluate( st_computer_color
, -INF
, INF
);
1351 for(int i
=0;i
<s
->num_moves
;i
++)
1354 int sdepth
= depth
-100;
1357 /* sort moves incrementally, in the hope of a beta cut */
1358 incremental_sort_moves(s
->moves
+i
, s
->num_moves
-i
);
1361 if(s
->moves
[i
].extend
) /* extensions calculated during the heuristic sort */
1365 /* recapture extension */
1366 static const int vallapiglia
[] = { 0, 5, 3, 9, 3, 1, 0 };
1367 if(s
->moves
[i
].capture
&& stack
[ply
-1].curr_move
>=0)
1369 Move
& prev
= stack
[ply
-1].moves
[stack
[ply
-1].curr_move
];
1371 if(s
->moves
[i
].to
== prev
.to
)
1373 if(vallapiglia
[PIECE_OF(board
.data
[s
->moves
[i
].to
])]
1374 == vallapiglia
[PIECE_OF(prev
.capture
)]
1375 && board
.move_see_val(s
->moves
[i
]) == vallapiglia
[PIECE_OF(prev
.capture
)] )
1376 sdepth
+= PIECE_OF(s
->moves
[i
].capture
) == PAWN
? 50 : 100;
1382 /* futility pruning, it is done only if we are no under check
1383 and the move is not a "critical" move */
1384 if(depth
>0 && depth
<3*PLY
&& !s
->under_check
&& s
->moves
[i
].val
< 28000)
1386 static const int mavala
[] = { 0, 490, 315, 980, 315, 100, 0 };
1388 int16_t fmargin
= (depth
<= PLY
? 420 : 950);
1389 int16_t fval
= position_val
+ mavala
[PIECE_OF(s
->moves
[i
].capture
)];
1390 if(fval
< alpha
-fmargin
)
1395 if((!s
->moves
[i
].capture
|| PIECE_OF(s
->moves
[i
].capture
)==PAWN
) && !(s
->moves
[i
].flags
>=PROMOTE_FIRST
))
1397 int ix
= HISTORY_INDEX(s
->moves
[i
]);
1398 if(history_tot
[ix
] > 1024)
1400 history_tot
[ix
] >>= 1;
1401 history_hit
[ix
] >>= 1;
1408 board
.do_move(s
->moves
[i
]);
1413 uint64_t q
= stat_quiesce_nodes
;
1414 STAT(quiesce_called
);
1415 val
= -this->quiesce( ply
+1, 0, -beta
, -alpha
);
1416 q
= stat_quiesce_nodes
-q
;
1417 if(q
> stat_max_quiesce_nodes
)
1419 stat_max_quiesce_nodes
= q
;
1420 max_quiesce_board
= board
;
1421 max_quiesce_alpha
= -beta
;
1422 max_quiesce_beta
= -alpha
;
1429 if(s
->base_depth
> 0 && sdepth
<= 0)
1431 STAT(quiesce_called
);
1432 q
= stat_quiesce_nodes
;
1435 #if NEGA_SCOUT /* use negascout, (null window search for nodes that are not in the pv) */
1436 if(quiesce
|| i
== 0) // || depth<200)
1437 val
= -search( ply
+1, sdepth
, pv
, -beta
, -alpha
);
1441 /* history pruning, if this is not a "critical" move and the failhigh
1442 stats are too low, try a reduced depth search (if it returns >alpha,
1443 re-do the full depth search) */
1444 if( !quiesce
&& !s
->under_check
&& depth
<=3*PLY
&& s
->moves
[i
].val
<28000 &&
1445 (history_hit
[HISTORY_INDEX(s
->moves
[i
])]+1)*3
1446 < (history_tot
[HISTORY_INDEX(s
->moves
[i
])]+1) )
1448 val
= -search( ply
+1, sdepth
- 100, false, -alpha
-1, -alpha
);
1450 goto skip_search
; /* reduced search was effective */
1453 val
= -search( ply
+1, sdepth
, false, -alpha
-1, -alpha
);
1454 if((val
>alpha
) && pv
)
1455 val
= -search( ply
+1, sdepth
, true, -beta
, -alpha
);
1458 /* normal full width alpha-beta */
1459 val
= -search( ply
+1, sdepth
, pv
, -beta
, -alpha
);
1462 if(s
->base_depth
> 0 && sdepth
<= 0)
1464 q
= stat_quiesce_nodes
-q
;
1465 if(q
> stat_max_quiesce_nodes
)
1467 stat_max_quiesce_nodes
= q
;
1468 max_quiesce_board
= board
;
1473 board
.undo_move(s
->moves
[i
]);
1476 /* update the current best value and check for and alpha cut */
1477 best
= MAX(best
, val
);
1491 /* update a few stats */
1494 if(best_mv_found
==0)
1501 stat_search_moves
++;
1502 if(ply
==0 && depth
>100)
1504 if(best_mv_found
==0)
1511 stat_search_moves0
++;
1516 !s
->moves
[best_mv_found
].capture
&&
1517 !(s
->moves
[best_mv_found
].flags
>=PROMOTE_FIRST
))
1519 history_hit
[HISTORY_INDEX(s
->moves
[best_mv_found
])]++;
1520 history_tot
[HISTORY_INDEX(s
->moves
[best_mv_found
])]++;
1524 mv_stack_top
-= s
->num_moves
; /* free the moves we allocated */
1525 /*if(best_mv_found>=0 && skip_null)
1526 strong_reply[ply] = mv[best_mv_found];
1528 strong_reply[ply] = Move::FromInt(0);*/
1530 if(stack
[ply
-1].curr_move
== -1 && best_mv_found
>= 0)
1531 null_threat
[ply
-1] = s
->moves
[best_mv_found
];
1534 /* if we found a best move searching, that move will be saved.
1535 if we did no search (ie quiescence), save the old hash value,
1536 or -1 if no hash entry had been found */
1537 int bestmv
= cbest_mv_hash
;
1538 if(best_mv_found
>= 0)
1539 bestmv
= board
.compress_move(s
->moves
[best_mv_found
]);
1541 /* write the value in the hash, with the index of the best move */
1542 write_hash( best
> s
->alpha
? best
: -INF
,
1543 best
< beta
? best
: +INF
,
1544 MAX(s
->base_depth
,-500), bestmv
);
1547 #if CONSISTENCY_EXTENSION
1548 /* instability re-search, ie search deeper the nodes whose value
1549 change a lot since last evaluation */
1551 if(s
->base_depth
< stack
[ply
-1].base_depth
)
1553 if( ((best
< old_hash_lower
-150) ||
1554 (best
> old_hash_upper
+150) )
1555 && old_hash_depth
>=s
->base_depth
-100
1556 && s
->base_depth
<=400 && s
->base_depth
>0)// && !skip_null )
1557 return search(ply
, s
->base_depth
+100, pv
, alpha
, beta
);
1559 #endif //CONSISTENCY_EXTENSION
1564 //r1b3k1/2p2rpp/p1P5/1p2N3/6nq/N1P5/PP1P1bPP/R1BQR1K1 w - - 0 14
1565 Move
Engine::find_best_move()
1567 SearchStack
*s
= &stack
[0];
1571 bool research
= true;
1576 /* initialize the root node */
1578 s
->base_depth
= 100;
1583 s
->threat
= Move::FromInt(0);
1586 s
->moves
= mv_stack
;
1587 s
->num_moves
= mv_stack_top
= board
.find_moves(s
->moves
);
1589 /* to print the analysis */
1591 output("\tply\tscore\ttime\tnodes\tpv\n");
1593 /* return immediatly if the move is forced. */
1597 /* probe the play lines */
1598 if( eng_status
== PLAYING
1599 && st_computer_color
== board
.color_to_move
1600 && probe_lines( board
.hash
, &retv
))
1606 /* probe the book */
1607 if(probe_book( board
.hash
, &retv
)) {
1608 for(int i
=0;i
<s
->num_moves
++;i
++)
1609 if(retv
.as_int
== s
->moves
[i
].as_int
)
1614 output("Error!!! invalid move in the book!!!\n");
1619 prof_find_moves
= 0;
1620 prof_find_captures
= 0;
1622 prof_sort_moves
= 0;
1623 prof_move_is_check
= 0;
1624 prof_move_see_val
= 0;
1628 stat_early_transp
= 0;
1633 stat_best_first
= 0;
1635 stat_search_moves
= 0;
1636 stat_best_first0
= 0;
1638 stat_search_moves0
= 0;
1640 stat_evaluate_cutoff
= 0;
1643 stat_hash_write
= 0;
1648 /* calculate how much time we will think*/
1649 start_think_time
= current_time();
1650 if( analysis_limit
== TIME_LIMIT
)
1652 if(board
.color_to_move
== st_computer_color
)
1654 else /* pondering? analysing? */
1655 time_best_csec
= 99999999;
1656 max_think_time
= start_think_time
+ time_best_csec
- 2;
1659 //analysis_color = board.color_to_move;
1660 processed_nodes
= 0;
1661 int16_t best_guess
= 0;
1665 /* set the back jump for the quick thinking exit */
1669 /* start with a guess of 0 */
1670 s
->moves
[0].val
= 0;
1673 /* do the iterative deepening thing. */
1676 int16_t alpha
= -INF
;
1679 memset( history_tot
, 0, HISTORY_SIZE
*sizeof(uint16_t));
1680 memset( history_hit
, 0, HISTORY_SIZE
*sizeof(uint16_t));
1682 /* save the result of the previous search */
1683 result
[s
->base_depth
/PLY
-1] = s
->moves
[0];
1685 /* for each move call the alpha-beta search function */
1687 for(i
=0;i
<s
->num_moves
;i
++)
1691 board
.do_move(s
->moves
[i
]);
1695 s
->moves
[i
].val
= -search( 1, s
->base_depth
-PLY
, true, -INF
, -alpha
);
1699 s
->moves
[i
].val
= -search( 1, s
->base_depth
-PLY
, false, -alpha
-1, -alpha
);
1700 if(s
->moves
[i
].val
> alpha
)
1701 s
->moves
[i
].val
= -search( 1, s
->base_depth
-PLY
, true, -INF
, -alpha
);
1704 s
->moves
[i
].val
= -search( 1, s
->base_depth
-100, true, -INF
, -alpha
);
1706 board
.undo_move(s
->moves
[i
]);
1711 if(s
->moves
[i
].val
> alpha
)
1713 alpha
= s
->moves
[i
].val
;
1718 /* this move caused an alpha cut, so print the new line */
1719 if( post
/*&& processed_nodes>100000*/)
1721 output("\t%d\t%d\t%d\t%llu\t", s
->base_depth
/100,
1722 s
->moves
[i
].val
, current_time() - start_think_time
, processed_nodes
);
1723 print_moves(&s
->moves
[i
], 1, true);
1730 /* the search is done, sort the moves so that best is searched first */
1733 s
->moves
[best_mv
].val
++;
1734 sort_moves(s
->moves
, i
); /* sort i moves (those that we where able to search) */
1738 /* print the result of the analysis at this depth */
1739 if( post
/*&& processed_nodes>100000*/)
1741 output("\t%d\t%d\t%d\t%llu\t", s
->base_depth
/100,
1742 s
->moves
[0].val
, current_time() - start_think_time
, processed_nodes
);
1743 print_moves(&s
->moves
[0], 1, true);
1747 if( s
->base_depth
>= 40*PLY
)
1750 /* return in case of fixed depth search */
1751 if( eng_status
== PLAYING
&& st_computer_color
== board
.color_to_move
&&
1752 analysis_limit
== DEPTH_LIMIT
&& s
->base_depth
== st_depth
*PLY
)
1755 /* return if 3/5 of time is gone (we can't search another ply anyway) */
1756 if( eng_status
== PLAYING
&& st_computer_color
== board
.color_to_move
&&
1757 analysis_limit
== TIME_LIMIT
&&
1758 (current_time()-start_think_time
) >= (time_best_csec
*3/5) )
1761 /* if a checkmate was detected return immediately */
1762 if( ABS(alpha
) > INF
-1000)
1767 s
->base_depth
+= PLY
;
1770 for(int i
=0;i
<(1<<21);i
++)
1772 HashEntry
* h
= &hash_table
[i
];
1775 output(" -> (Hash purged)\n");
1777 research
= !research
;
1779 s
->base_depth
+= PLY
;
1788 prof_tot
= rdtsc() - prof_tot
;
1789 #define SHOW_PROF(a) output("@"#a": %llu (%llu%%)\n", \
1790 prof_##a, prof_##a*100/prof_tot);
1794 SHOW_PROF(find_moves
);
1795 SHOW_PROF(find_captures
);
1796 SHOW_PROF(heuristic
);
1797 SHOW_PROF(move_is_check
);
1798 SHOW_PROF(move_see_val
);
1799 SHOW_PROF(sort_moves
);
1801 output("#nodes: %llu (~%llu nps)\n", processed_nodes
, (processed_nodes
*100)/
1802 MAX(current_time()-start_think_time
,1) );
1803 output("# %d times all the moves were seached (non-leaf non-quiesce node)\n",
1805 output("# of which %d times first move caused a cutoff\n", stat_best_cut
);
1806 output("# of the remaining %d times first move was really best (%02d%%)\n",
1807 stat_best_first
, (stat_best_first
*100)/MAX(stat_search_moves
-stat_best_cut
, 1));
1808 output("# evaluate was called %d times (quiescence node)\n", stat_evaluate
);
1809 output("# of which %d times caused an early cutoff (leaf node)\n",
1810 stat_evaluate_cutoff
);
1811 output("#hash: %d writes, %d probes (%d succesful, =%d, >%d, <%d)\n",
1812 stat_hash_write
, stat_hash_tot
, stat_hash_ex
+stat_hash_low
+stat_hash_upp
,
1813 stat_hash_ex
, stat_hash_low
, stat_hash_upp
);
1814 output("#etc: %d\n", stat_early_transp
);
1815 output("#null move: %d (%d succesful)\n", stat_null_move
, stat_null_cut
);
1819 max_quiesce_board
.write_board(buf
);
1820 output("#max quiesce board: %s [%d %d]\n", buf
, max_quiesce_alpha
, max_quiesce_beta
);