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))
37 #define WORST_MATE (INF-2500)
39 int stat_early_transp
;
47 int stat_search_moves
;
50 int stat_search_moves0
;
52 int stat_evaluate_cutoff
;
62 S(max_quiesce_nodes); \
66 S(quiesce_best_can_be_first); \
67 S(quiesce_best_was_first); \
69 S(quiesce_cutoff_first); \
72 S(search_best_can_be_first); \
73 S(search_best_was_first); \
75 S(search_cutoff_first); \
79 #define STAT(x) stat_##x++;
81 #define S(x) uint64_t stat_##x;
83 Board max_quiesce_board
;
84 int16_t max_quiesce_alpha
;
85 int16_t max_quiesce_beta
;
90 #define S(x) stat_##x = 0;
97 #define S(x) printf("# " #x " = %llu\n", (unsigned long long)stat_##x);
104 /* enable the quiescence search */
107 /* enable the nega-scout pv-search */
110 /* enable the null move */
113 /* before doing the alpha beta search check if any of the following positions
114 can give use an early cutoff thanks to the hashtable */
115 #define EARLY_TRANSP_CUTOFF 1
117 /* SEEMS TO BE A BIT BAD:
118 Extend when there is only one decent move */
119 #define SINGULAR_EXTENSION 0
121 /* reduce nodes for moves that are not check/captures that are considered
122 bad from the heuristic */
123 #define LATE_MOVE_REDUCTION 1
125 /* futility pruning: */
128 /* when the hashtable provides no "best" move, do a depth-2 search */
129 #define INTERNAL_ITERATIVE_DEEPENING 0
131 /* use the history sorting heuristic */
132 #define HISTORY_HEURISTIC 1
134 /* improve the sorting heuristic for pawn strikes */
135 #define PAWNSTRIKE_HEURISTIC 1
137 /* improve the sorting heuristic for moves to the center */
138 #define CENTER_HEURISTIC 0
144 int base_depth
; /* depth of the search at this ply */
145 int extensions
; /* global extensions at this node */
146 Move
*moves
; /* all generated moves */
147 int num_moves
; /* num of moves */
148 int curr_move
; /* the move being currently analyzed */
149 int16_t alpha
; /* alpha ans beta when the search started (not improved) */
156 Move mv_stack
[200*MAX_PV
];
157 int mv_stack_top
= 0;
158 SearchStack stack
[MAX_PV
];
161 void Engine::print_stat()
163 if(eng_status
!= ANALYZING
)
165 printf("Thinking: ");
166 for(int i
=0; i
<current_ply
; i
++)
168 if(stack
[i
].curr_move
== -2)
169 continue; //Internal iterative deepening
170 else if(stack
[i
].curr_move
== -1)
173 board
.do_null_move();
178 printf("%s", move_to_alg(buf
, &(stack
[i
].moves
[stack
[i
].curr_move
]) ) );
179 board
.do_move(stack
[i
].moves
[stack
[i
].curr_move
]);
181 printf((i
!= current_ply
-1) ? " " : "\n");
190 output("stat01: %d %llu %d %d %d %s\n",
191 current_time() - start_think_time
,
192 (unsigned long long)processed_nodes
,
193 stack
[0].base_depth
/100,
194 stack
[0].num_moves
-1-stack
[0].curr_move
,
196 move_to_alg(buf
, &(stack
[0].moves
[stack
[0].curr_move
]) ) );
199 output("stat01: 0 0 0 0 0\n");
202 void Engine::rewind_thinking()
204 for(int i
=current_ply
-1; i
>=0; i
--)
206 if(stack
[i
].curr_move
== -2)
208 else if(stack
[i
].curr_move
== -1)
209 board
.undo_null_move();
211 board
.undo_move(stack
[i
].moves
[stack
[i
].curr_move
]);
215 bool Engine::null_move_ok()
217 int c
= IS_WHITE(board
.color_to_move
) ? 5 : -1;
218 int numpawns
= board
.mat_tracking
[c
+PAWN
].count
;
219 int numpieces
= board
.mat_tracking
[c
+KNIGHT
].count
+ board
.mat_tracking
[c
+BISHOP
].count
220 + board
.mat_tracking
[c
+ROOK
].count
+ board
.mat_tracking
[c
+QUEEN
].count
;
223 if(numpieces
>= 1 && numpawns
>= 2)
228 void Engine::restore_thinking()
230 for(int i
=0; i
<current_ply
; i
++)
232 if(stack
[i
].curr_move
== -2)
234 else if(stack
[i
].curr_move
== -1)
235 board
.do_null_move();
237 board
.do_move(stack
[i
].moves
[stack
[i
].curr_move
]);
240 /* regenerate pinning info and under_check var, just to be sure :) */
242 board
.find_moves(mvs
);
246 Engine::moves_heuristic(Move
*mv
, int num_mv
, int ply
, int orig_depth
,
247 Move best_mv_hash
, bool quiesce
, Move
* prev
)
251 for(int i
=0;i
<num_mv
;i
++)
256 /* give a high bonus to the move stored in the hash, if any.
257 mark only which is, don't continue, because some extensions
258 may be triggered ad added later (ie pawn strike, etc) */
259 if(mv
[i
].as_int
== best_mv_hash
.as_int
)
264 if(PIECE_OF(board
.data
[mv
[i
].from
]) != PAWN
&&
265 (mv
[i
].from
== escape_from_1
[ply
-1] || mv
[i
].from
== escape_from_2
[ply
-1]) )
267 int x
= board
.move_see_val(mv
[i
]);
274 /* process strong pawn moves */
275 if(PIECE_OF(board
.data
[mv
[i
].from
])==PAWN
) /* pawn strike */
277 if( ROW_OF(mv
[i
].to
) == board
.seventh_rank
[IS_WHITE(board
.color_to_move
)] )
279 int x
= board
.move_see_val(mv
[i
]);
283 mv
[i
].val
+= 29599; /* 7th push */
284 mv
[i
].extend
= PLY
; /* extend search */
289 if( mv
[i
].flags
== PROMOTEQUEEN
)
291 int x
= board
.move_see_val(mv
[i
]);
295 mv
[i
].val
+= 29600; /* promote! */
296 mv
[i
].extend
= PLY
; /* extend search */
302 if(orig_depth
>= 2*PLY
)
305 uint8_t up_right
= Board::up_dir
[IS_WHITE(board
.color_to_move
)] + RIGHT
;
306 uint8_t up_left
= Board::up_dir
[IS_WHITE(board
.color_to_move
)] + LEFT
;
307 uint8_t p1
= mv
[i
].to
+ up_right
;
308 uint8_t p2
= mv
[i
].to
+ up_left
;
309 uint8_t a
= OUT_OF_BOARD(p1
) ? 0 : board
.data
[p1
];
310 uint8_t b
= OUT_OF_BOARD(p2
) ? 0 : board
.data
[p2
];
311 if( (COLOR_OF(a
)==board
.other_color
&& PIECE_OF(a
)!=PAWN
)
312 || (COLOR_OF(b
)==board
.other_color
&& PIECE_OF(b
)!=PAWN
) )
314 int x
= board
.move_see_val(mv
[i
]);
318 mv
[i
].val
= 27000; /* pawn strike! */
319 //mv[i].extend = PLY; /* extend search */
329 int x
= board
.move_see_val(mv
[i
]);
331 if(prev
&& prev
->capture
&&
332 (mv
[i
].to
== prev
->to
) && (x
>= Board::simple_values
[PIECE_OF(prev
->capture
)]) )
335 if( (x
== Board::simple_values
[PIECE_OF(prev
->capture
)]) )
336 mv
[i
].extend
= /*(x==1) ? (PLY/2) :*/ PLY
;
337 // else if(prev->capture && ABS(x - Board::simple_values[PIECE_OF(prev->capture)]) == 1)
338 // mv[i].extend = PLY/2;
344 if(orig_depth
>-7*PLY
&& board
.move_is_check(mv
[i
]) )
350 else if(x
>=0 && orig_depth
>-7*PLY
&& board
.move_is_check(mv
[i
]) )
352 /* = capture but check */
357 else /* add a bonus for checks (but not too deep, or quiescence will get mad) */
358 if(orig_depth
>-3*PLY
&& board
.move_is_check(mv
[i
]) )
360 if(board
.move_see_val(mv
[i
])>=0)
367 /* null-move threat */
368 if(null_threat
[ply
-1] == mv
[i
])
374 mv
[i
].val
+= history_hit
[HISTORY_INDEX(mv
[i
])] * 1024 / (history_tot
[HISTORY_INDEX(mv
[i
])] + 4);
377 static int bof
[128] = {
378 0,0,1,2,2,1,0,0,ENDL
,
379 0,1,2,3,3,2,1,0,ENDL
,
380 0,2,4,5,5,4,2,0,ENDL
,
381 1,2,5,6,6,5,2,1,ENDL
,
382 1,2,5,6,6,5,2,1,ENDL
,
383 0,2,4,5,5,4,2,0,ENDL
,
384 0,1,2,3,3,2,1,0,ENDL
,
388 /* add a bonus for moves towards the center */
389 mv
[i
].val
+= (bof
[mv
[i
].to
] - bof
[mv
[i
].from
]);
390 #endif //CENTER_HEURISTIC
394 mv
[hash_move
].val
= 30000;
399 Engine::moves_quiescence_heuristic(Move
*mv
, int num_mv
, const Move
& best_mv_hash
,
400 int static_eval
, int alpha
, int beta
, int orig_depth
, Move
* prev
)
402 for(int i
=0;i
<num_mv
;i
++)
407 /* give a high bonus to the move stored in the hash, if any.
408 mark only which is, don't continue, because some extensions
409 may be triggered ad added later (ie pawn strike, etc) */
410 if(mv
[i
].as_int
== best_mv_hash
.as_int
)
417 /* process strong pawn moves */
418 if(PIECE_OF(board
.data
[mv
[i
].from
])==PAWN
) /* pawn strike */
420 if( ROW_OF(mv
[i
].to
) == board
.seventh_rank
[IS_WHITE(board
.color_to_move
)] )
422 int x
= board
.move_see_val(mv
[i
]);
430 mv
[i
].val
+= 29499; /* 7th push */
431 mv
[i
].extend
= PLY
; /* extend search */
435 if( mv
[i
].flags
== PROMOTEQUEEN
)
437 int x
= board
.move_see_val(mv
[i
]);
445 mv
[i
].val
+= 29500; /* promote! */
446 mv
[i
].extend
= PLY
; /* extend search */
452 uint8_t p1
= mv
[i
].to
+ up_right
;
453 uint8_t p2
= mv
[i
].to
+ up_left
;
454 uint8_t a
= OUT_OF_BOARD(p1
) ? 0 : board
.data
[p1
];
455 uint8_t b
= OUT_OF_BOARD(p2
) ? 0 : board
.data
[p2
];
456 if( (COLOR_OF(a
)==board
.other_color
&& PIECE_OF(a
)!=PAWN
)
457 || (COLOR_OF(b
)==board
.other_color
&& PIECE_OF(b
)!=PAWN
) )
459 int x
= board
.move_see_val(mv
[i
]);
466 mv
[i
].val
+= 27000; /* pawn strike! */
467 mv
[i
].extend
= PLY
; /* extend search */
475 int x
= board
.move_see_val(mv
[i
]);
477 if(prev
&& prev
->capture
&&
478 (mv
[i
].to
== prev
->to
) && (x
>= Board::simple_values
[PIECE_OF(prev
->capture
)]) )
481 if( (x
== Board::simple_values
[PIECE_OF(prev
->capture
)]) )
482 mv
[i
].extend
= /*(x==1) ? (PLY/2) :*/ PLY
;
483 // else if(prev->capture && ABS(x - Board::simple_values[PIECE_OF(prev->capture)]) == 1)
484 // mv[i].extend = PLY/2;
490 if(orig_depth
>-5*PLY
&& board
.move_is_check(mv
[i
]) )
496 else if(x
>=0 && orig_depth
>-5*PLY
&& board
.move_is_check(mv
[i
]) )
498 /* = capture but check */
503 else /* add a bonus for checks (but not too deep, or quiescence will get mad) */
504 if(orig_depth
>-3*PLY
&& board
.move_is_check(mv
[i
]) )
506 if(board
.move_see_val(mv
[i
])>=0)
516 /*******************************************************************************
517 The main alpha-beta recursive search function.
518 It handles both normal search (with or without null move)
519 and quiescence search, because i have having 2 almost identical
521 *******************************************************************************/
522 int16_t Engine::search(int ply
, int depth
, bool pv
, int16_t alpha
, int16_t beta
)
524 SearchStack
*s
= &stack
[ply
];
526 uint16_t cbest_mv_hash
= 0; /* the compressed move from the hash */
527 Move best_mv_hash
= Move::FromInt(0); /* the move from the hash */
528 int best_mv_found
= -1; /* the index of the best move AFTER searching */
530 bool extended
= false;
531 int16_t position_val
;
536 s
->base_depth
= depth
;
542 s
->threat
= Move::FromInt(0);
544 null_threat
[ply
] = Move::FromInt(0);
545 null_threat_dangerous
[ply
] = false;
546 escape_from_1
[ply
] = escape_from_2
[ply
] = INVALID
;
548 /* check if time is running out */
552 /* check for a draw for repetition or 50mvs. Of course the draw for
553 repetition must be checked BEFORE probing the hash :)*/
555 return (board
.color_to_move
== st_computer_color
) ? -35 :
556 ((board
.other_color
== st_computer_color
) ? 35 : 0); /* be aggressive! */
558 /*******************************************************************************
560 If the probe is succesful the hashtable will return us value
561 that can be exact, a lower bound or an upper bound, and if the
562 depth of the hashed search is >= the current depth this value
563 will be used to improve alpha and beta and possibly return immediatly.
564 The hastable will also give us a "best" move that will be searched
566 This is the move that caused the "final" cutoff when this position
567 was searched previously. This best move is actually the index of the best
568 move in the array of generated moves (it is supposed to be deterministic :)
569 *******************************************************************************/
571 HashEntry
*h
= probe_hash( board
.hash
);
573 if(h
&& (h
->depth
>= s
->base_depth
))// || ABS(h->value)>INF-1000) )
575 int16_t l
= h
->lower();
576 int16_t u
= h
->upper();
583 alpha
= MAX(alpha
, l
);
587 cbest_mv_hash
= h
->best_mv
;
589 /*******************************************************************************
590 Test if we are under check, and if so extend search
591 *******************************************************************************/
593 s
->under_check
= board
.under_attack(board
.king_pos
[IS_WHITE(board
.color_to_move
)],
596 /*******************************************************************************
597 If it is time to quiesce, evaluate and test if we can exit
598 immediately with a beta cut-off (try first a rough eval - delta)
599 *******************************************************************************/
600 quiesce
= ((!s
->under_check
) && (depth
<=0)) || (depth
<-60*PLY
);
603 if(quiesce
&& depth
>=-PLY
)
606 Move
*mv
= mv_stack
+ mv_stack_top
;
607 board
.do_null_move();
608 num_mv
= board
.find_moves(mv
);
609 uint8_t pup
= INVALID
;
611 for(int i
=0;i
<num_mv
;i
++)
613 if(!mv
[i
].capture
|| PIECE_OF(mv
[i
].capture
)==PAWN
)
615 if(mv
[i
].to
!= pup
&& board
.move_see_val(mv
[i
])>0)
625 board
.undo_null_move();
632 best
= board
.evaluate(st_computer_color
, alpha
, beta
);
634 alpha
= MAX(alpha
, best
);
637 stat_evaluate_cutoff
++;
646 /*******************************************************************************
648 *******************************************************************************/
649 if(!s
->under_check
&& (stack
[ply
-1].curr_move
!= -1) && depth
>= 2*PLY
&& beta
<WORST_MATE
&& null_move_ok())
652 int sdepth
= (depth
>= 5*PLY
) ? (depth
-4*PLY
) : depth
-3*PLY
;
657 board
.do_null_move();
658 val
= -search( ply
+1, sdepth
, true, -beta
, -beta
+1);
659 board
.undo_null_move();
669 if(val
< -WORST_MATE
)
670 null_threat_dangerous
[ply
] = true;
672 if(val
<alpha
-100 && /* we are facing a threat*/
673 stack
[ply
+1].best_move
!= -1) /* be sure we aren't reading random memory */
675 /* ok, officially the array stack[ply+1].moves has already
676 been deallocated, but who cares :) */
677 s
->threat
= stack
[ply
+1].moves
[stack
[ply
+1].best_move
];
680 /* Botvinnik-Markoff extension!!! */
681 if(!extended
&& ply
>=3 && (s
->threat
== stack
[ply
-2].threat
) )
694 /*******************************************************************************
695 Now generate the legal moves and look for a check/stalemate
696 *******************************************************************************/
698 /* generate all the legal moves */
699 s
->moves
= &mv_stack
[mv_stack_top
];
700 s
->num_moves
= board
.find_moves(s
->moves
);
701 mv_stack_top
+= s
->num_moves
;
702 s
->under_check
= board
.under_check
;
704 if(s
->under_check
==2) /* double check */
709 else if(s
->under_check
) /* simple check */
712 if(stack
[ply
-1].curr_move
>=0 &&
713 !board
.pins
[stack
[ply
-1].moves
[ /* last moved piece is not attacking the king */
714 stack
[ply
-1].curr_move
].to
]) /* so this is a discover check */
721 /* return now if the positon is terminal */
726 /* while mating, sacrify as much as possible :) */
727 best
= -INF
+ ply
;//*50 + board.material[IS_WHITE(eng_color)]/50;
734 /* single-reply extension */
735 if(s
->num_moves
== 1 && !extended
)
740 else if(s
->num_moves
<= 3 && !extended
)
746 /*******************************************************************************
748 First comes the move from the hashtable, if avalable.
749 The remaining moves are sorted with a heuristic that keeps in account
750 the history heuristic (ie the moves that previously caused an alpha
751 cutoff), a MVV/LVA bonus value and a small bonus for moves that go
753 *******************************************************************************/
755 /* convert the move we got from the hash to the move structure */
758 best_mv_hash
= board
.uncompress_move(cbest_mv_hash
);
759 /* if it happened that the move we got from the hashtable
760 is not valid, simply no move will get the high
761 heuristic bonus value */
763 #if INTERNAL_ITERATIVE_DEEPENING
764 else if(s
->base_depth
>3*PLY
&& pv
) /* don't do it only on the pv, or it will be useless :) */
768 int val
= search(ply
+1, s
->base_depth
-2*PLY
, true, alpha
, beta
);
771 HashEntry
*h2
= probe_hash( board
.hash
);
772 if(h2
&& h2
->best_mv
)
774 cbest_mv_hash
= h2
->best_mv
;
775 best_mv_hash
= board
.uncompress_move(cbest_mv_hash
);
778 #endif //INTERNAL_ITERATIVE_DEEPENING
780 /* for each move calculate the heuristic goodness value */
782 Move
*prev
= (stack
[ply
-1].curr_move
>=0) ? &stack
[ply
-1].moves
[stack
[ply
-1].curr_move
] : NULL
;
784 moves_quiescence_heuristic( s
->moves
, s
->num_moves
, best_mv_hash
,
785 best
, alpha
, beta
, s
->base_depth
, prev
);
787 moves_heuristic( s
->moves
, s
->num_moves
, ply
, s
->base_depth
,
788 best_mv_hash
, quiesce
, prev
);
791 /* if quiesce rip-off the "non-critical" moves */
795 for(int i
=0;i
<s
->num_moves
;i
++)
796 if(s
->moves
[i
].val
>0)
797 s
->moves
[n
++] = s
->moves
[i
];
798 mv_stack_top
-= s
->num_moves
-n
;
802 /* Don't do it now, do it incrementally */
803 //sort_moves( s->moves, s->num_moves );
806 #if EARLY_TRANSP_CUTOFF
807 /*******************************************************************************
808 Try to get an early beta cutoff using the hash table values
809 of the following moves, and improve alpha too.
810 Try on the first 6 value of the ordered moves (argh, looking into the
811 hashtable is very expensive because of the cache!!!!!!!!)
812 *******************************************************************************/
816 HashKey hk
= board
.move_hash(s
->moves
[0]);
817 for(int i
=1;i
<s
->num_moves
;i
++)
820 HashKey newhk
= board
.move_hash(s
->moves
[i
]);
821 HashEntry
*h2
= probe_hash( hk
);
824 if(h2
&& h2
->depth
>= depth
-PLY
)
831 alpha
= MAX(alpha
, (int16_t)-h2
->up
);
835 HashEntry
*h2
= probe_hash( hk
);
836 if(h2
&& h2
->depth
>= depth
-PLY
)
843 alpha
= MAX(alpha
, (int16_t)-h2
->up
);
846 #endif //EARLY_TRANSP_CUTOFF
848 /* set the current best move index (as will be saved in the hash) */
851 /*******************************************************************************
852 It is now time to loop all the successor moves and search recursively.
853 *******************************************************************************/
856 /* calcluate the evaluation (required by fitility pruning) */
857 position_val
= quiesce
? best
: board
.evaluate( st_computer_color
, -INF
, INF
);
860 for(int i
=0;i
<s
->num_moves
;i
++)
863 int sdepth
= depth
-100;
865 /* sort moves incrementally, in the hope of a beta cut */
866 incremental_sort_moves(s
->moves
+i
, s
->num_moves
-i
);
868 if(depth
< s
->base_depth
+100)
869 sdepth
+= s
->moves
[i
].extend
; /* extensions calculated during the heuristic sort */
872 /* futility pruning, it is done only if we are no under check
873 and the move is not a "critical" move */
874 if(depth
>0 && depth
<3*PLY
&& !s
->under_check
&& s
->moves
[i
].val
< 28000)
876 static const int mavala
[] = { 0, 490, 315, 980, 315, 100, 0 };
878 int16_t fmargin
= (depth
<= PLY
? 420 : 950);
879 int16_t fval
= position_val
+ mavala
[PIECE_OF(s
->moves
[i
].capture
)];
880 if(fval
< alpha
-fmargin
)
885 /* collect history statistics */
886 if(s
->moves
[i
].val
<28000)
888 int ix
= HISTORY_INDEX(s
->moves
[i
]);
889 if(history_tot
[ix
] > 1024)
891 history_tot
[ix
] = history_tot
[ix
]*7/8;
892 history_hit
[ix
] = history_hit
[ix
]*7/8;
898 if(!quiesce
&& PIECE_OF(board
.data
[s
->moves
[i
].from
]) == PAWN
&& s
->moves
[i
].val
== 27000) //FIXME, UGLY
900 escape_from_1
[ply
] = s
->moves
[i
].to
+ Board::up_dir
[IS_WHITE(board
.color_to_move
)] + RIGHT
;
901 escape_from_2
[ply
] = s
->moves
[i
].to
+ Board::up_dir
[IS_WHITE(board
.color_to_move
)] + LEFT
;
905 escape_from_1
[ply
] = escape_from_2
[ply
] = 0;
911 board
.do_move(s
->moves
[i
]);
915 if(s
->base_depth
> 0 && sdepth
<= 0)
917 STAT(quiesce_called
);
918 q
= stat_quiesce_nodes
;
921 #if NEGA_SCOUT /* use negascout, (null window search for nodes that are not in the pv) */
922 if(i
== 0) // || depth<200)
923 val
= -search( ply
+1, sdepth
, pv
, -beta
, -alpha
);
926 #if LATE_MOVE_REDUCTION
927 /* history pruning, if this is not a "critical" move and the failhigh
928 stats are too low, try a reduced depth search (if it returns >alpha,
929 re-do the full depth search) */
930 // if((sdepth>0) && !s->under_check && depth<=3*PLY && s->moves[i].val<28000 &&
931 // (history_hit[HISTORY_INDEX(s->moves[i])]+1)*3
932 // < (history_tot[HISTORY_INDEX(s->moves[i])]+1))
933 if((sdepth
>0) && !s
->under_check
&& s
->moves
[i
].val
<28000 && (i
>=7 || (i
>=5 && s
->moves
[i
].val
<350) ) )
935 val
= -search( ply
+1, sdepth
- PLY
, false, -alpha
-1, -alpha
);
937 goto skip_search
; /* reduced search was effective */
940 val
= -search( ply
+1, sdepth
, false, -alpha
-1, -alpha
);
941 if((val
>alpha
) && pv
)
942 val
= -search( ply
+1, sdepth
, true, -beta
, -alpha
);
945 /* normal full width alpha-beta */
946 val
= -search( ply
+1, sdepth
, pv
, -beta
, -alpha
);
949 if(s
->base_depth
> 0 && sdepth
<= 0)
951 q
= stat_quiesce_nodes
-q
;
952 if(q
> stat_max_quiesce_nodes
)
954 stat_max_quiesce_nodes
= q
;
955 max_quiesce_board
= board
;
960 board
.undo_move(s
->moves
[i
]);
963 /* update the current best value and check for and alpha cut */
964 best
= MAX(best
, val
);
979 /* update a few stats */
990 if(ply
==0 && depth
>100)
999 stat_search_moves0
++;
1003 /* collect statistics for the history */
1005 !s
->moves
[best_mv_found
].capture
&&
1006 !(s
->moves
[best_mv_found
].flags
>=PROMOTE_FIRST
))
1008 history_hit
[HISTORY_INDEX(s
->moves
[best_mv_found
])]++;
1009 history_tot
[HISTORY_INDEX(s
->moves
[best_mv_found
])]++;
1013 mv_stack_top
-= s
->num_moves
; /* free the moves we allocated */
1015 /* this is a null move, save what the threat is */
1016 if(stack
[ply
-1].curr_move
== -1 && best_mv_found
>= 0)
1017 null_threat
[ply
-1] = s
->moves
[best_mv_found
];
1019 /* if we found a best move searching, that move will be saved.
1020 if we did no search (ie quiescence), save the old hash value,
1021 or -1 if no hash entry had been found */
1022 int bestmv
= cbest_mv_hash
;
1023 if(best_mv_found
>= 0)
1024 bestmv
= board
.compress_move(s
->moves
[best_mv_found
]);
1026 /* write the value in the hash, with the index of the best move */
1027 write_hash( best
> s
->alpha
? best
: -INF
,
1028 best
< beta
? MAX(best
, s
->alpha
) : +INF
,
1029 MAX(s
->base_depth
,-500), bestmv
);
1035 Move
Engine::find_best_move()
1037 int num_mate_hits
= 0;
1038 SearchStack
*s
= &stack
[0];
1044 /* initialize the root node */
1046 s
->base_depth
= 100;
1051 s
->threat
= Move::FromInt(0);
1054 s
->moves
= mv_stack
;
1055 s
->num_moves
= mv_stack_top
= board
.find_moves(s
->moves
);
1057 /* calculate how much time we will think*/
1058 start_think_time
= current_time();
1059 if( analysis_limit
== TIME_LIMIT
)
1061 if(board
.color_to_move
== st_computer_color
)
1063 else /* pondering? analysing? */
1064 time_best_csec
= 99999999;
1065 max_think_time
= start_think_time
+ time_best_csec
- 2;
1068 /* to print the analysis */
1070 output("\tply\tscore\ttime\tnodes\tpv\n");
1072 /* return immediatly if the move is forced. */
1076 /* probe the play lines */
1077 if( eng_status
== PLAYING
1078 && st_computer_color
== board
.color_to_move
1079 && probe_lines( board
.hash
, &retv
))
1085 /* probe the book */
1086 if(probe_book( board
.hash
, &retv
)) {
1087 for(int i
=0;i
<s
->num_moves
++;i
++)
1088 if(retv
.as_int
== s
->moves
[i
].as_int
)
1093 output("Error!!! invalid move in the book!!!\n");
1098 prof_find_moves
= 0;
1099 prof_find_captures
= 0;
1101 prof_sort_moves
= 0;
1102 prof_move_is_check
= 0;
1103 prof_move_see_val
= 0;
1107 stat_early_transp
= 0;
1112 stat_best_first
= 0;
1114 stat_search_moves
= 0;
1115 stat_best_first0
= 0;
1117 stat_search_moves0
= 0;
1119 stat_evaluate_cutoff
= 0;
1122 stat_hash_write
= 0;
1127 //analysis_color = board.color_to_move;
1128 processed_nodes
= 0;
1129 int16_t best_guess
= 0;
1133 /* set the back jump for the quick thinking exit */
1137 /* start with a guess of 0 */
1138 s
->moves
[0].val
= 0;
1141 /* do the iterative deepening thing. */
1144 int16_t alpha
= -INF
;
1147 memset( history_tot
, 0, HISTORY_SIZE
*sizeof(uint16_t));
1148 memset( history_hit
, 0, HISTORY_SIZE
*sizeof(uint16_t));
1150 /* save the result of the previous search */
1151 result
[s
->base_depth
/PLY
-1] = s
->moves
[0];
1153 /* for each move call the alpha-beta search function */
1155 for(i
=0;i
<s
->num_moves
;i
++)
1159 board
.do_move(s
->moves
[i
]);
1163 s
->moves
[i
].val
= -search( 1, s
->base_depth
-PLY
, true, -INF
, -alpha
);
1167 s
->moves
[i
].val
= -search( 1, s
->base_depth
-PLY
, false, -alpha
-1, -alpha
);
1168 if(s
->moves
[i
].val
> alpha
)
1169 s
->moves
[i
].val
= -search( 1, s
->base_depth
-PLY
, true, -INF
, -alpha
);
1172 s
->moves
[i
].val
= -search( 1, s
->base_depth
-100, true, -INF
, -alpha
);
1174 board
.undo_move(s
->moves
[i
]);
1179 if(s
->moves
[i
].val
> alpha
)
1181 alpha
= s
->moves
[i
].val
;
1186 /* this move caused an alpha cut, so print the new line */
1187 if( post
/*&& processed_nodes>100000*/)
1189 output("\t%d\t%d\t%d\t%llu\t", s
->base_depth
/100,
1190 s
->moves
[i
].val
, current_time() - start_think_time
, processed_nodes
);
1191 print_moves(&s
->moves
[i
], 1, true);
1198 /* the search is done, sort the moves so that best is searched first */
1201 s
->moves
[best_mv
].val
++;
1202 sort_moves(s
->moves
, i
); /* sort i moves (those that we where able to search) */
1206 /* print the result of the analysis at this depth */
1207 if( post
/*&& processed_nodes>100000*/)
1209 output("\t%d\t%d\t%d\t%llu\t", s
->base_depth
/100,
1210 s
->moves
[0].val
, current_time() - start_think_time
, processed_nodes
);
1211 print_moves(&s
->moves
[0], 1, true);
1215 if( s
->base_depth
>= 40*PLY
)
1218 /* return in case of fixed depth search */
1219 if( eng_status
== PLAYING
&& st_computer_color
== board
.color_to_move
&&
1220 analysis_limit
== DEPTH_LIMIT
&& s
->base_depth
== st_depth
*PLY
)
1223 /* return if 3/5 of time is gone (we can't search another ply anyway) */
1224 if( eng_status
== PLAYING
&& st_computer_color
== board
.color_to_move
&&
1225 analysis_limit
== TIME_LIMIT
&&
1226 (current_time()-start_think_time
) >= (time_best_csec
*3/5) )
1229 /* if a checkmate was detected return immediately */
1230 if( ABS(alpha
) > WORST_MATE
)
1233 if(num_mate_hits
>= 5)
1237 s
->base_depth
+= PLY
;
1245 prof_tot
= rdtsc() - prof_tot
;
1246 #define SHOW_PROF(a) output("@"#a": %llu (%llu%%)\n", \
1247 prof_##a, prof_##a*100/prof_tot);
1251 SHOW_PROF(find_moves
);
1252 SHOW_PROF(find_captures
);
1253 SHOW_PROF(heuristic
);
1254 SHOW_PROF(move_is_check
);
1255 SHOW_PROF(move_see_val
);
1256 SHOW_PROF(sort_moves
);
1258 output("#nodes: %llu (~%llu nps)\n", processed_nodes
, (processed_nodes
*100)/
1259 MAX(current_time()-start_think_time
,1) );
1260 output("# %d times all the moves were seached (non-leaf non-quiesce node)\n",
1262 output("# of which %d times first move caused a cutoff\n", stat_best_cut
);
1263 output("# of the remaining %d times first move was really best (%02d%%)\n",
1264 stat_best_first
, (stat_best_first
*100)/MAX(stat_search_moves
-stat_best_cut
, 1));
1265 output("# evaluate was called %d times (quiescence node)\n", stat_evaluate
);
1266 output("# of which %d times caused an early cutoff (leaf node)\n",
1267 stat_evaluate_cutoff
);
1268 output("#hash: %d writes, %d probes (%d succesful, =%d, >%d, <%d)\n",
1269 stat_hash_write
, stat_hash_tot
, stat_hash_ex
+stat_hash_low
+stat_hash_upp
,
1270 stat_hash_ex
, stat_hash_low
, stat_hash_upp
);
1271 output("#etc: %d\n", stat_early_transp
);
1272 output("#null move: %d (%d succesful)\n", stat_null_move
, stat_null_cut
);
1276 max_quiesce_board
.write_board(buf
);
1277 output("#max quiesce board: %s [%d %d]\n", buf
, max_quiesce_alpha
, max_quiesce_beta
);