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 ***************************************************************************/
20 #include "search_gui.h"
27 Move null_threat
[MAX_PV
];
28 bool null_threat_dangerous
[MAX_PV
];
29 uint8_t escape_from_1
[MAX_PV
];
30 uint8_t escape_from_2
[MAX_PV
];
32 #define HISTORY_SIZE (64*64)
33 uint16_t history_tot
[HISTORY_SIZE
];
34 uint16_t history_hit
[HISTORY_SIZE
];
36 #define HISTORY_INDEX(m) (SQUARE_TO_64(m.from)*64 + SQUARE_TO_64(m.to))
38 #define WORST_MATE (INF-5000)
40 int stat_early_transp
;
48 int stat_search_moves
;
51 int stat_search_moves0
;
53 int stat_evaluate_cutoff
;
63 S(max_quiesce_nodes); \
67 S(quiesce_best_can_be_first); \
68 S(quiesce_best_was_first); \
70 S(quiesce_cutoff_first); \
73 S(search_best_can_be_first); \
74 S(search_best_was_first); \
76 S(search_cutoff_first); \
80 #define STAT(x) stat_##x++;
82 #define S(x) uint64_t stat_##x;
84 Board max_quiesce_board
;
85 int16_t max_quiesce_alpha
;
86 int16_t max_quiesce_beta
;
91 #define S(x) stat_##x = 0;
98 #define S(x) printf("# " #x " = %llu\n", (unsigned long long)stat_##x);
105 /* enable the quiescence search */
108 /* enable the nega-scout pv-search */
111 /* enable the null move */
114 /* before doing the alpha beta search check if any of the following positions
115 can give use an early cutoff thanks to the hashtable */
116 #define EARLY_TRANSP_CUTOFF 1
118 /* reduce nodes for moves that are not check/captures that are considered
119 bad from the heuristic */
120 #define LATE_MOVE_REDUCTION 1
122 /* futility pruning: */
125 /* when the hashtable provides no "best" move, do a depth-2 search */
126 #define INTERNAL_ITERATIVE_DEEPENING 0
128 /* use the history sorting heuristic */
129 #define HISTORY_HEURISTIC 1
131 /* improve the sorting heuristic for pawn strikes */
132 #define PAWNSTRIKE_HEURISTIC 1
134 /* improve the sorting heuristic for moves to the center */
135 #define CENTER_HEURISTIC 0
141 int base_depth
; /* depth of the search at this ply */
142 int extensions
; /* global extensions at this node */
143 Move
*moves
; /* all generated moves */
144 int num_moves
; /* num of moves */
145 int curr_move
; /* the move being currently analyzed */
146 int16_t alpha
; /* alpha ans beta when the search started (not improved) */
153 Move mv_stack
[200*MAX_PV
];
154 int mv_stack_top
= 0;
155 SearchStack stack
[MAX_PV
];
158 void Engine::print_stat()
160 if(eng_status
!= ANALYZING
)
162 printf("Thinking: ");
163 for(int i
=0; i
<current_ply
; i
++)
165 if(stack
[i
].curr_move
== -2)
166 continue; //Internal iterative deepening
167 else if(stack
[i
].curr_move
== -1)
170 board
.do_null_move();
175 printf("%s", move_to_alg(buf
, &(stack
[i
].moves
[stack
[i
].curr_move
]) ) );
176 board
.do_move(stack
[i
].moves
[stack
[i
].curr_move
]);
178 printf((i
!= current_ply
-1) ? " " : "\n");
187 output("stat01: %d %llu %d %d %d %s\n",
188 current_time() - start_think_time
,
189 (unsigned long long)processed_nodes
,
190 stack
[0].base_depth
/100,
191 stack
[0].num_moves
-1-stack
[0].curr_move
,
193 move_to_alg(buf
, &(stack
[0].moves
[stack
[0].curr_move
]) ) );
196 output("stat01: 0 0 0 0 0\n");
199 void Engine::rewind_thinking()
201 for(int i
=current_ply
-1; i
>=0; i
--)
203 if(stack
[i
].curr_move
== -2)
205 else if(stack
[i
].curr_move
== -1)
206 board
.undo_null_move();
208 board
.undo_move(stack
[i
].moves
[stack
[i
].curr_move
]);
212 bool Engine::null_move_ok()
214 int c
= IS_WHITE(board
.color_to_move
) ? 5 : -1;
215 int numpawns
= board
.mat_tracking
[c
+PAWN
].count
;
216 int numpieces
= board
.mat_tracking
[c
+KNIGHT
].count
+ board
.mat_tracking
[c
+BISHOP
].count
217 + board
.mat_tracking
[c
+ROOK
].count
+ board
.mat_tracking
[c
+QUEEN
].count
;
220 if(numpieces
>= 1 && numpawns
>= 2)
225 void Engine::restore_thinking()
227 for(int i
=0; i
<current_ply
; i
++)
229 if(stack
[i
].curr_move
== -2)
231 else if(stack
[i
].curr_move
== -1)
232 board
.do_null_move();
234 board
.do_move(stack
[i
].moves
[stack
[i
].curr_move
]);
237 /* regenerate pinning info and under_check var, just to be sure :) */
239 board
.find_moves(mvs
);
243 Engine::moves_heuristic(Move
*mv
, int num_mv
, int ply
, int orig_depth
,
244 Move best_mv_hash
, bool quiesce
, Move
* prev
)
248 for(int i
=0;i
<num_mv
;i
++)
253 /* give a high bonus to the move stored in the hash, if any.
254 mark only which is, don't continue, because some extensions
255 may be triggered ad added later (ie pawn strike, etc) */
256 if(mv
[i
].as_int
== best_mv_hash
.as_int
)
261 if(PIECE_OF(board
.data
[mv
[i
].from
]) != PAWN
&&
262 (mv
[i
].from
== escape_from_1
[ply
-1] || mv
[i
].from
== escape_from_2
[ply
-1]) )
264 int x
= board
.move_see_val(mv
[i
]);
271 /* process strong pawn moves */
272 if(PIECE_OF(board
.data
[mv
[i
].from
])==PAWN
) /* pawn strike */
274 if( ROW_OF(mv
[i
].to
) == board
.seventh_rank
[IS_WHITE(board
.color_to_move
)] )
276 int x
= board
.move_see_val(mv
[i
]);
280 mv
[i
].val
+= 29599; /* 7th push */
281 mv
[i
].extend
= PLY
; /* extend search */
286 if( mv
[i
].flags
== PROMOTEQUEEN
)
288 int x
= board
.move_see_val(mv
[i
]);
292 mv
[i
].val
+= 29600; /* promote! */
293 mv
[i
].extend
= PLY
; /* extend search */
299 if(orig_depth
>= 2*PLY
)
302 uint8_t up_right
= Board::up_dir
[IS_WHITE(board
.color_to_move
)] + RIGHT
;
303 uint8_t up_left
= Board::up_dir
[IS_WHITE(board
.color_to_move
)] + LEFT
;
304 uint8_t p1
= mv
[i
].to
+ up_right
;
305 uint8_t p2
= mv
[i
].to
+ up_left
;
306 uint8_t a
= OUT_OF_BOARD(p1
) ? 0 : board
.data
[p1
];
307 uint8_t b
= OUT_OF_BOARD(p2
) ? 0 : board
.data
[p2
];
308 if( (COLOR_OF(a
)==board
.other_color
&& PIECE_OF(a
)!=PAWN
)
309 || (COLOR_OF(b
)==board
.other_color
&& PIECE_OF(b
)!=PAWN
) )
311 int x
= board
.move_see_val(mv
[i
]);
315 if( (COLOR_OF(a
)==board
.other_color
&& PIECE_OF(a
)!=PAWN
)
316 && (COLOR_OF(b
)==board
.other_color
&& PIECE_OF(b
)!=PAWN
) )
319 mv
[i
].extend
= PLY
; /* extend search */
322 mv
[i
].val
= 27000; /* pawn strike! */
332 int x
= board
.move_see_val(mv
[i
]);
334 if(prev
&& prev
->capture
&&
335 (mv
[i
].to
== prev
->to
) && (x
>= Board::simple_values
[PIECE_OF(prev
->capture
)]) )
338 if( (x
== Board::simple_values
[PIECE_OF(prev
->capture
)]) )
339 mv
[i
].extend
= /*(x==1) ? (PLY/2) :*/ PLY
;
340 // else if(prev->capture && ABS(x - Board::simple_values[PIECE_OF(prev->capture)]) == 1)
341 // mv[i].extend = PLY/2;
347 if(orig_depth
>-7*PLY
&& board
.move_is_check(mv
[i
]) )
353 else if(x
>=0 && orig_depth
>-7*PLY
&& board
.move_is_check(mv
[i
]) )
355 /* = capture but check */
360 else /* add a bonus for checks (but not too deep, or quiescence will get mad) */
361 if(orig_depth
>-3*PLY
&& board
.move_is_check(mv
[i
]) )
363 if(board
.move_see_val(mv
[i
])>=0)
370 /* null-move threat */
371 if(null_threat
[ply
-1] == mv
[i
])
377 mv
[i
].val
+= (history_hit
[HISTORY_INDEX(mv
[i
])] + 32) * 1024 / (history_tot
[HISTORY_INDEX(mv
[i
])] + 64);
380 static int bof
[128] = {
381 0,0,1,2,2,1,0,0,ENDL
,
382 0,1,2,3,3,2,1,0,ENDL
,
383 0,2,4,5,5,4,2,0,ENDL
,
384 1,2,5,6,6,5,2,1,ENDL
,
385 1,2,5,6,6,5,2,1,ENDL
,
386 0,2,4,5,5,4,2,0,ENDL
,
387 0,1,2,3,3,2,1,0,ENDL
,
391 /* add a bonus for moves towards the center */
392 mv
[i
].val
+= bof
[mv
[i
].to
];
393 //mv[i].val += (bof[mv[i].to] - bof[mv[i].from]);
394 #endif //CENTER_HEURISTIC
398 mv
[hash_move
].val
= 30000;
403 Engine::moves_quiescence_heuristic(Move
*mv
, int num_mv
, const Move
& best_mv_hash
,
404 int static_eval
, int alpha
, int beta
, int orig_depth
, Move
* prev
)
406 for(int i
=0;i
<num_mv
;i
++)
411 /* give a high bonus to the move stored in the hash, if any.
412 mark only which is, don't continue, because some extensions
413 may be triggered ad added later (ie pawn strike, etc) */
414 if(mv
[i
].as_int
== best_mv_hash
.as_int
)
421 /* process strong pawn moves */
422 if(PIECE_OF(board
.data
[mv
[i
].from
])==PAWN
) /* pawn strike */
424 if( ROW_OF(mv
[i
].to
) == board
.seventh_rank
[IS_WHITE(board
.color_to_move
)] )
426 int x
= board
.move_see_val(mv
[i
]);
434 mv
[i
].val
+= 29499; /* 7th push */
435 mv
[i
].extend
= PLY
; /* extend search */
439 if( mv
[i
].flags
== PROMOTEQUEEN
)
441 int x
= board
.move_see_val(mv
[i
]);
449 mv
[i
].val
+= 29500; /* promote! */
450 mv
[i
].extend
= PLY
; /* extend search */
456 uint8_t p1
= mv
[i
].to
+ up_right
;
457 uint8_t p2
= mv
[i
].to
+ up_left
;
458 uint8_t a
= OUT_OF_BOARD(p1
) ? 0 : board
.data
[p1
];
459 uint8_t b
= OUT_OF_BOARD(p2
) ? 0 : board
.data
[p2
];
460 if( (COLOR_OF(a
)==board
.other_color
&& PIECE_OF(a
)!=PAWN
)
461 || (COLOR_OF(b
)==board
.other_color
&& PIECE_OF(b
)!=PAWN
) )
463 int x
= board
.move_see_val(mv
[i
]);
470 mv
[i
].val
+= 27000; /* pawn strike! */
471 mv
[i
].extend
= PLY
; /* extend search */
479 int x
= board
.move_see_val(mv
[i
]);
481 if(prev
&& prev
->capture
&&
482 (mv
[i
].to
== prev
->to
) && (x
>= Board::simple_values
[PIECE_OF(prev
->capture
)]) )
485 if( (x
== Board::simple_values
[PIECE_OF(prev
->capture
)]) )
486 mv
[i
].extend
= /*(x==1) ? (PLY/2) :*/ PLY
;
487 // else if(prev->capture && ABS(x - Board::simple_values[PIECE_OF(prev->capture)]) == 1)
488 // mv[i].extend = PLY/2;
494 if(orig_depth
>-5*PLY
&& board
.move_is_check(mv
[i
]) )
500 else if(x
>=0 && orig_depth
>-5*PLY
&& board
.move_is_check(mv
[i
]) )
502 /* = capture but check */
507 else /* add a bonus for checks (but not too deep, or quiescence will get mad) */
508 if(orig_depth
>-3*PLY
&& board
.move_is_check(mv
[i
]) )
510 if(board
.move_see_val(mv
[i
])>=0)
520 /*******************************************************************************
521 The main alpha-beta recursive search function.
522 It handles both normal search (with or without null move)
523 and quiescence search, because i have having 2 almost identical
525 *******************************************************************************/
526 int16_t Engine::search(int ply
, int depth
, bool pv
, int16_t alpha
, int16_t beta
)
528 SearchStack
*s
= &stack
[ply
];
530 uint16_t cbest_mv_hash
= 0; /* the compressed move from the hash */
531 Move best_mv_hash
= Move::FromInt(0); /* the move from the hash */
532 int best_mv_found
= -1; /* the index of the best move AFTER searching */
534 bool extended
= false;
535 bool no_good_moves
= false;
536 int16_t lower_bound
= -INF
;
537 int16_t position_val
;
542 s
->base_depth
= depth
;
548 s
->threat
= Move::FromInt(0);
550 null_threat
[ply
] = Move::FromInt(0);
551 null_threat_dangerous
[ply
] = false;
552 escape_from_1
[ply
] = escape_from_2
[ply
] = INVALID
;
554 /* check if time is running out */
558 /* check for a draw for repetition or 50mvs. Of course the draw for
559 repetition must be checked BEFORE probing the hash :)*/
561 return (board
.color_to_move
== st_computer_color
) ? v_eval_draw
:
562 ((board
.other_color
== st_computer_color
) ? -v_eval_draw
: 0); /* be aggressive! */
564 /*******************************************************************************
566 If the probe is succesful the hashtable will return us value
567 that can be exact, a lower bound or an upper bound, and if the
568 depth of the hashed search is >= the current depth this value
569 will be used to improve alpha and beta and possibly return immediatly.
570 The hastable will also give us a "best" move that will be searched
572 This is the move that caused the "final" cutoff when this position
573 was searched previously. This best move is actually the index of the best
574 move in the array of generated moves (it is supposed to be deterministic :)
575 *******************************************************************************/
577 HashEntry
*h
= probe_hash( board
.hash
);
580 GUI(notify_hash(ply
, h
->lo
, h
->up
, h
->depth
, alpha
, beta
,
581 h
->best_mv
? board
.uncompress_move(h
->best_mv
) : Move::None(), false,
582 (((h
->depth
>= s
->base_depth
) && (h
->lo
>=beta
|| h
->up
==h
->lo
|| h
->up
<=alpha
))
583 ? SearchGui::Bold
: 0) | SearchGui::Magenta
) );
586 if(h
&& (h
->depth
>= s
->base_depth
))// || ABS(h->value)>INF-1000) )
588 int16_t l
= h
->lower();
589 int16_t u
= h
->upper();
597 best
= alpha
= MAX(alpha
, l
);
601 cbest_mv_hash
= h
->best_mv
;
603 /*******************************************************************************
604 Test if we are under check, and if so extend search
605 *******************************************************************************/
607 s
->under_check
= board
.under_attack(board
.king_pos
[IS_WHITE(board
.color_to_move
)],
610 /*******************************************************************************
611 If it is time to quiesce, evaluate and test if we can exit
612 immediately with a beta cut-off (try first a rough eval - delta)
613 *******************************************************************************/
614 quiesce
= ((!s
->under_check
) && (depth
<=0)) || (depth
<-60*PLY
);
617 if(quiesce
&& depth
>=-PLY
)
620 Move
*mv
= mv_stack
+ mv_stack_top
;
621 board
.do_null_move();
622 num_mv
= board
.find_moves(mv
);
623 uint8_t pup
= INVALID
;
625 for(int i
=0;i
<num_mv
;i
++)
627 if(!mv
[i
].capture
|| PIECE_OF(mv
[i
].capture
)==PAWN
)
629 if(mv
[i
].to
!= pup
&& board
.move_see_val(mv
[i
])>0)
639 board
.undo_null_move();
643 if(quiesce
&& (best
== -INF
) )
646 best
= board
.evaluate(st_computer_color
, alpha
, beta
);
647 lower_bound
= best
; //we have at the very least "best" as lower bound now.
648 GUI(notify_eval(ply
, best
, alpha
, beta
, best
>=beta
? SearchGui::Blue
|SearchGui::Bold
: SearchGui::Blue
));
650 alpha
= MAX(alpha
, best
);
653 stat_evaluate_cutoff
++;
661 if(quiesce
&& h
&& h
->no_good_moves
)
665 /*******************************************************************************
667 *******************************************************************************/
668 if(!s
->under_check
&& (stack
[ply
-1].curr_move
!= -1) && depth
>= 2*PLY
&& beta
<WORST_MATE
&& null_move_ok())
671 int sdepth
= (depth
>= 5*PLY
) ? (depth
-4*PLY
) : depth
-3*PLY
;
676 board
.do_null_move();
677 GUI1(notify(Move::None(), ply
, sdepth
, -INF
, beta
-1, beta
, SearchGui::Green
));
678 val
= -search( ply
+1, sdepth
, true, -beta
, -beta
+1);
679 GUI2(notify_value(ply
, val
, DIFF_NODES
, SearchGui::Bold
));
680 board
.undo_null_move();
690 if(val
< -WORST_MATE
)
691 null_threat_dangerous
[ply
] = true;
694 if(val
<alpha
-100 && /* we are facing a threat*/
695 stack
[ply
+1].best_move
!= -1) /* be sure we aren't reading random memory */
697 /* ok, officially the array stack[ply+1].moves has already
698 been deallocated, but who cares :) */
699 s
->threat
= stack
[ply
+1].moves
[stack
[ply
+1].best_move
];
702 /* Botvinnik-Markoff extension!!! */
703 if(!extended
&& ply
>=3 && (s
->threat
== stack
[ply
-2].threat
) )
716 /*******************************************************************************
717 Now generate the legal moves and look for a check/stalemate
718 *******************************************************************************/
720 /* generate all the legal moves */
721 s
->moves
= &mv_stack
[mv_stack_top
];
722 s
->num_moves
= board
.find_moves(s
->moves
);
723 mv_stack_top
+= s
->num_moves
;
724 s
->under_check
= board
.under_check
;
726 if(s
->under_check
==2) /* double check */
731 else if(s
->under_check
) /* simple check */
734 if(stack
[ply
-1].curr_move
>=0 &&
735 !board
.pins
[stack
[ply
-1].moves
[ /* last moved piece is not attacking the king */
736 stack
[ply
-1].curr_move
].to
]) /* so this is a discover check */
743 /* return now if the positon is terminal */
748 /* while mating, sacrify as much as possible :) */
749 int mt
= IS_WHITE(board
.other_color
) ? 5 : -1;
750 int16_t matval
= Board::simple_values
[PAWN
]*board
.mat_tracking
[mt
+PAWN
].count
+
751 Board::simple_values
[KNIGHT
]*board
.mat_tracking
[mt
+KNIGHT
].count
+
752 Board::simple_values
[BISHOP
]*board
.mat_tracking
[mt
+BISHOP
].count
+
753 Board::simple_values
[QUEEN
]*board
.mat_tracking
[mt
+QUEEN
].count
;
754 best
= alpha
= beta
= -INF
+ ply
*100 + matval
;
757 best
= alpha
= beta
= 0;
761 /* single-reply extension */
762 if(s
->num_moves
== 1 && !extended
)
767 else if(s
->num_moves
<= 3 && !extended
)
773 /*******************************************************************************
775 First comes the move from the hashtable, if avalable.
776 The remaining moves are sorted with a heuristic that keeps in account
777 the history heuristic (ie the moves that previously caused an alpha
778 cutoff), a MVV/LVA bonus value and a small bonus for moves that go
780 *******************************************************************************/
782 /* convert the move we got from the hash to the move structure */
785 best_mv_hash
= board
.uncompress_move(cbest_mv_hash
);
786 /* if it happened that the move we got from the hashtable
787 is not valid, simply no move will get the high
788 heuristic bonus value */
790 #if INTERNAL_ITERATIVE_DEEPENING
791 else if(s
->base_depth
>3*PLY
&& pv
) /* don't do it only on the pv, or it will be useless :) */
795 GUI1(notify(Move::None(), ply
, s
->base_depth
-2*PLY
, -INF
, alpha
, beta
, SearchGui::Blue
));
796 int val
= search(ply
+1, s
->base_depth
-2*PLY
, true, alpha
, beta
);
797 GUI2(search_gui
->notify_value(ply
, val
, DIFF_NODES
, 0));
800 HashEntry
*h2
= probe_hash( board
.hash
);
801 if(h2
&& h2
->best_mv
)
803 cbest_mv_hash
= h2
->best_mv
;
804 best_mv_hash
= board
.uncompress_move(cbest_mv_hash
);
807 #endif //INTERNAL_ITERATIVE_DEEPENING
809 /* for each move calculate the heuristic goodness value */
811 Move
*prev
= (stack
[ply
-1].curr_move
>=0) ? &stack
[ply
-1].moves
[stack
[ply
-1].curr_move
] : NULL
;
813 moves_quiescence_heuristic( s
->moves
, s
->num_moves
, best_mv_hash
,
814 best
, alpha
, beta
, s
->base_depth
, prev
);
816 moves_heuristic( s
->moves
, s
->num_moves
, ply
, s
->base_depth
,
817 best_mv_hash
, quiesce
, prev
);
820 /* if quiesce rip-off the "non-critical" moves */
824 for(int i
=0;i
<s
->num_moves
;i
++)
825 if(s
->moves
[i
].val
>0)
826 s
->moves
[n
++] = s
->moves
[i
];
827 mv_stack_top
-= s
->num_moves
-n
;
830 no_good_moves
= true;
833 /* Don't do it now, do it incrementally */
834 //sort_moves( s->moves, s->num_moves );
837 #if EARLY_TRANSP_CUTOFF
838 /*******************************************************************************
839 Try to get an early beta cutoff using the hash table values
840 of the following moves, and improve alpha too.
841 Try on the first 6 value of the ordered moves (argh, looking into the
842 hashtable is very expensive because of the cache!!!!!!!!)
843 *******************************************************************************/
847 HashKey hk
= board
.move_hash(s
->moves
[0]);
848 for(int i
=1;i
<s
->num_moves
;i
++)
851 HashKey newhk
= board
.move_hash(s
->moves
[i
]);
852 HashEntry
*h2
= probe_hash( hk
);
855 if(h2
&& h2
->depth
>= depth
-PLY
)
862 alpha
= MAX(alpha
, (int16_t)-h2
->up
);
866 HashEntry
*h2
= probe_hash( hk
);
867 if(h2
&& h2
->depth
>= depth
-PLY
)
874 alpha
= MAX(alpha
, (int16_t)-h2
->up
);
877 #endif //EARLY_TRANSP_CUTOFF
879 /*******************************************************************************
880 It is now time to loop all the successor moves and search recursively.
881 *******************************************************************************/
884 /* calcluate the evaluation (required by fitility pruning) */
885 position_val
= quiesce
? best
: board
.evaluate( st_computer_color
, -INF
, INF
);
888 for(int i
=0;i
<s
->num_moves
;i
++)
891 int sdepth
= depth
-100;
893 /* sort moves incrementally, in the hope of a beta cut */
894 incremental_sort_moves(s
->moves
+i
, s
->num_moves
-i
);
896 if(depth
< s
->base_depth
+100)
897 sdepth
+= s
->moves
[i
].extend
; /* extensions calculated during the heuristic sort */
900 /* futility pruning, it is done only if we are no under check
901 and the move is not a "critical" move */
902 if(depth
>0 && depth
<3*PLY
&& !s
->under_check
&& s
->moves
[i
].val
< 28000)
904 static const int mavala
[] = { 0, 490, 315, 980, 315, 100, 0 };
906 int16_t fmargin
= (depth
<= PLY
? 420 : 950);
907 int16_t fval
= position_val
+ mavala
[PIECE_OF(s
->moves
[i
].capture
)];
908 if(fval
< alpha
-fmargin
)
913 /* collect history statistics */
914 if(s
->moves
[i
].val
<28000)
916 int ix
= HISTORY_INDEX(s
->moves
[i
]);
917 if(history_tot
[ix
] > 8192)
919 history_tot
[ix
] = history_tot
[ix
]*7/8;
920 history_hit
[ix
] = history_hit
[ix
]*7/8;
922 history_tot
[ix
] += 8;
926 if(!quiesce
&& PIECE_OF(board
.data
[s
->moves
[i
].from
]) == PAWN
&& s
->moves
[i
].val
== 27000) //FIXME, UGLY
928 escape_from_1
[ply
] = s
->moves
[i
].to
+ Board::up_dir
[IS_WHITE(board
.color_to_move
)] + RIGHT
;
929 if(OUT_OF_BOARD(escape_from_1
[ply
]) || !IS_OF_COLOR(escape_from_1
[ply
], board
.other_color
)
930 || PIECE_OF(escape_from_1
[ply
])==PAWN
)
931 escape_from_1
[ply
] = 0;
932 escape_from_2
[ply
] = s
->moves
[i
].to
+ Board::up_dir
[IS_WHITE(board
.color_to_move
)] + LEFT
;
933 if(OUT_OF_BOARD(escape_from_2
[ply
]) || !IS_OF_COLOR(escape_from_2
[ply
], board
.other_color
)
934 || PIECE_OF(escape_from_2
[ply
])==PAWN
)
935 escape_from_2
[ply
] = 0;
939 escape_from_1
[ply
] = escape_from_2
[ply
] = 0;
945 board
.do_move(s
->moves
[i
]);
949 if(s
->base_depth
> 0 && sdepth
<= 0)
951 STAT(quiesce_called
);
952 q
= stat_quiesce_nodes
;
955 #if NEGA_SCOUT /* use negascout, (null window search for nodes that are not in the pv) */
958 GUI1(notify(s
->moves
[i
], ply
, sdepth
, s
->moves
[i
].val
, alpha
, beta
, SearchGui::Bold
));
959 val
= -search( ply
+1, sdepth
, pv
, -beta
, -alpha
);
960 GUI2(notify_value(ply
, val
, DIFF_NODES
, 0));
964 #if LATE_MOVE_REDUCTION
965 /* history pruning, if this is not a "critical" move and the failhigh
966 stats are too low, try a reduced depth search (if it returns >alpha,
967 re-do the full depth search) */
968 // if((sdepth>0) && !s->under_check && depth<=3*PLY && s->moves[i].val<28000 &&
969 // (history_hit[HISTORY_INDEX(s->moves[i])]+1)*3
970 // < (history_tot[HISTORY_INDEX(s->moves[i])]+1))
971 if( (sdepth
>0) && !s
->under_check
&& !null_threat_dangerous
[ply
]
972 && s
->moves
[i
].val
<28000 && (i
>=18 || (i
>=5 && s
->moves
[i
].val
<(450) ) ) )
974 int rdepth
= sdepth
- (s
->moves
[i
].val
<(100) ? 2*PLY
: PLY
) - s
->moves
[i
].extend
;
975 GUI1(notify(s
->moves
[i
], ply
, rdepth
, s
->moves
[i
].val
, alpha
, alpha
+1, SearchGui::Italic
|SearchGui::Gray
));
976 val
= -search( ply
+1, rdepth
, false, -alpha
-1, -alpha
);
977 GUI2(notify_value(ply
, val
, DIFF_NODES
, val
>alpha
? SearchGui::Red
: 0));
979 goto skip_search
; /* reduced search was effective */
982 GUI1(notify(s
->moves
[i
], ply
, sdepth
, s
->moves
[i
].val
, alpha
, alpha
+1, 0 ));
983 val
= -search( ply
+1, sdepth
, false, -alpha
-1, -alpha
);
984 GUI2(notify_value(ply
, val
, DIFF_NODES
, val
>alpha
? SearchGui::Red
: 0));
985 if((val
>alpha
) && pv
)
987 GUI1(notify(s
->moves
[i
], ply
, sdepth
, -INF
, alpha
, beta
, SearchGui::Bold
));
988 val
= -search( ply
+1, sdepth
, true, -beta
, -alpha
);
989 GUI2(notify_value(ply
, val
, DIFF_NODES
, val
>beta
? SearchGui::Red
: 0));
993 /* normal full width alpha-beta */
994 val
= -search( ply
+1, sdepth
, pv
, -beta
, -alpha
);
997 if(s
->base_depth
> 0 && sdepth
<= 0)
999 q
= stat_quiesce_nodes
-q
;
1000 if(q
> stat_max_quiesce_nodes
)
1002 stat_max_quiesce_nodes
= q
;
1003 max_quiesce_board
= board
;
1008 board
.undo_move(s
->moves
[i
]);
1011 /* update the current best value and check for and alpha cut */
1022 /* alpha improvement! */
1031 /* update a few stats */
1034 if(best_mv_found
==0)
1041 stat_search_moves
++;
1042 if(ply
==0 && depth
>100)
1044 if(best_mv_found
==0)
1051 stat_search_moves0
++;
1055 /* collect statistics for the history */
1056 if(best
>= beta
&& (best_mv_found
!=-1) &&
1057 !s
->moves
[best_mv_found
].capture
&&
1058 !(s
->moves
[best_mv_found
].flags
>=PROMOTE_FIRST
))
1060 history_hit
[HISTORY_INDEX(s
->moves
[best_mv_found
])] += 8;
1061 history_tot
[HISTORY_INDEX(s
->moves
[best_mv_found
])] += 8;
1065 mv_stack_top
-= s
->num_moves
; /* free the moves we allocated */
1067 /* this is a null move, save what the threat is */
1068 if(stack
[ply
-1].curr_move
== -1 && best_mv_found
>= 0)
1069 null_threat
[ply
-1] = s
->moves
[best_mv_found
];
1071 /* if we found a best move searching, that move will be saved.
1072 if we did no search (ie quiescence), save the old hash value,
1073 or -1 if no hash entry had been found */
1074 int bestmv
= cbest_mv_hash
;
1075 if(best_mv_found
>= 0)
1076 bestmv
= board
.compress_move(s
->moves
[best_mv_found
]);
1078 /* write the value in the hash, with the index of the best move */
1079 write_hash( best
> s
->alpha
? MIN(best
, beta
) : lower_bound
,
1080 best
< beta
? best
: +INF
,
1081 MAX(s
->base_depth
,-500), bestmv
, no_good_moves
);
1082 GUI(notify_hash(ply
, best
> s
->alpha
? MIN(best
, beta
) : lower_bound
, best
< beta
? best
: +INF
,
1083 MAX(s
->base_depth
,-500), alpha
, beta
, bestmv
? board
.uncompress_move(bestmv
) : Move::None(), true,
1084 SearchGui::Bold
| SearchGui::Magenta
) );
1090 Move
Engine::find_best_move()
1092 int num_mate_hits
= 0;
1093 SearchStack
*s
= &stack
[0];
1099 /* initialize the root node */
1101 s
->base_depth
= 100;
1106 s
->threat
= Move::FromInt(0);
1109 s
->moves
= mv_stack
;
1110 s
->num_moves
= mv_stack_top
= board
.find_moves(s
->moves
);
1112 /* calculate how much time we will think*/
1113 start_think_time
= current_time();
1114 if( analysis_limit
== TIME_LIMIT
)
1116 if(board
.color_to_move
== st_computer_color
)
1118 else /* pondering? analysing? */
1119 time_best_csec
= 99999999;
1120 max_think_time
= start_think_time
+ time_best_csec
- 2;
1123 /* to print the analysis */
1125 output("\tply\tscore\ttime\tnodes\tpv\n");
1127 /* return immediatly if the move is forced. */
1131 /* probe the play lines */
1132 if( eng_status
== PLAYING
1133 && st_computer_color
== board
.color_to_move
1134 && probe_lines( board
.hash
, &retv
))
1140 /* probe the book */
1141 if(probe_book( board
.hash
, &retv
)) {
1142 for(int i
=0;i
<s
->num_moves
++;i
++)
1143 if(retv
.as_int
== s
->moves
[i
].as_int
)
1148 output("Error!!! invalid move in the book!!!\n");
1151 stat_early_transp
= 0;
1156 stat_best_first
= 0;
1158 stat_search_moves
= 0;
1159 stat_best_first0
= 0;
1161 stat_search_moves0
= 0;
1163 stat_evaluate_cutoff
= 0;
1166 stat_hash_write
= 0;
1169 IFGUI(reset_hash()); //ONLY FOR DEBUGGING!!!
1171 //analysis_color = board.color_to_move;
1172 processed_nodes
= 0;
1176 /* set the back jump for the quick thinking exit */
1180 if(search_gui
) search_gui
->init_root();
1182 /* start with a guess of 0 */
1183 s
->moves
[0].val
= 0;
1186 memset( history_tot
, 0, HISTORY_SIZE
*sizeof(uint16_t));
1187 memset( history_hit
, 0, HISTORY_SIZE
*sizeof(uint16_t));
1189 /* do the iterative deepening thing. */
1192 int16_t alpha
= num_mate_hits
? -INF
: -WORST_MATE
;
1193 int16_t beta
= num_mate_hits
? INF
: WORST_MATE
;
1196 if(search_gui
) search_gui
->new_root_level(s
->base_depth
);
1198 /* save the result of the previous search */
1199 result
[s
->base_depth
/PLY
-1] = s
->moves
[0];
1201 /* for each move call the alpha-beta search function */
1203 for(i
=0;i
<s
->num_moves
;i
++)
1207 board
.do_move(s
->moves
[i
]);
1211 GUI1(notify(s
->moves
[i
], 0, s
->base_depth
-PLY
, s
->moves
[i
].val
, alpha
, beta
, SearchGui::Bold
));
1212 s
->moves
[i
].val
= -search( 1, s
->base_depth
-PLY
, true, -beta
, -alpha
);
1213 GUI2(notify_value(0, s
->moves
[i
].val
, DIFF_NODES
, 0));
1217 GUI1(notify(s
->moves
[i
], 0, s
->base_depth
-PLY
, s
->moves
[i
].val
, alpha
, alpha
+1, 0 ));
1218 s
->moves
[i
].val
= -search( 1, s
->base_depth
-PLY
, false, -alpha
-1, -alpha
);
1219 GUI2(notify_value(0, s
->moves
[i
].val
, DIFF_NODES
, s
->moves
[i
].val
>alpha
? SearchGui::Red
: 0));
1221 if(s
->moves
[i
].val
> alpha
)
1223 GUI1(notify(s
->moves
[i
], 0, s
->base_depth
-PLY
, -INF
, alpha
, beta
, SearchGui::Bold
));
1224 s
->moves
[i
].val
= -search( 1, s
->base_depth
-PLY
, true, -beta
, -alpha
);
1225 GUI2(notify_value(0, s
->moves
[i
].val
, DIFF_NODES
, 0));
1229 s
->moves
[i
].val
= -search( 1, s
->base_depth
-PLY
, true, -beta
, -alpha
);
1231 board
.undo_move(s
->moves
[i
]);
1236 if(s
->moves
[i
].val
> alpha
)
1238 alpha
= s
->moves
[i
].val
;
1243 /* this move caused an alpha cut, so print the new line */
1244 if( post
/*&& processed_nodes>100000*/)
1246 output("\t%d\t%d\t%d\t%llu\t", s
->base_depth
/100,
1247 s
->moves
[i
].val
, current_time() - start_think_time
, processed_nodes
);
1248 print_moves(&s
->moves
[i
], 1, true);
1253 /* the search is done, sort the moves so that best is searched first */
1256 s
->moves
[best_mv
].val
++;
1257 sort_moves(s
->moves
, i
); /* sort i moves (those that we where able to search) */
1261 /* print the result of the analysis at this depth */
1262 if( post
/*&& processed_nodes>100000*/)
1264 output("\t%d\t%d\t%d\t%llu\t", s
->base_depth
/100,
1265 s
->moves
[0].val
, current_time() - start_think_time
, processed_nodes
);
1266 print_moves(&s
->moves
[0], 1, true);
1270 if( s
->base_depth
>= 40*PLY
)
1273 /* return in case of fixed depth search */
1274 if( eng_status
== PLAYING
&& st_computer_color
== board
.color_to_move
&&
1275 analysis_limit
== DEPTH_LIMIT
&& s
->base_depth
== st_depth
*PLY
)
1278 /* return if 3/5 of time is gone (we can't search another ply anyway) */
1279 if( eng_status
== PLAYING
&& st_computer_color
== board
.color_to_move
&&
1280 analysis_limit
== TIME_LIMIT
&&
1281 (current_time()-start_think_time
) >= (time_best_csec
*3/5) )
1284 /* if a checkmate was detected return immediately */
1285 if( ABS(alpha
) > WORST_MATE
)
1288 if(num_mate_hits
>= 5)
1292 s
->base_depth
+= PLY
;
1300 prof_tot
= rdtsc() - prof_tot
;
1301 #define SHOW_PROF(a) output("@"#a": %llu (%llu%%)\n", \
1302 prof_##a, prof_##a*100/prof_tot);
1306 SHOW_PROF(find_moves
);
1307 SHOW_PROF(find_captures
);
1308 SHOW_PROF(heuristic
);
1309 SHOW_PROF(move_is_check
);
1310 SHOW_PROF(move_see_val
);
1311 SHOW_PROF(sort_moves
);
1313 output("#nodes: %llu (~%llu nps)\n", processed_nodes
, (processed_nodes
*100)/
1314 MAX(current_time()-start_think_time
,1) );
1315 output("# %d times all the moves were seached (non-leaf non-quiesce node)\n",
1317 output("# of which %d times first move caused a cutoff\n", stat_best_cut
);
1318 output("# of the remaining %d times first move was really best (%02d%%)\n",
1319 stat_best_first
, (stat_best_first
*100)/MAX(stat_search_moves
-stat_best_cut
, 1));
1320 output("# evaluate was called %d times (quiescence node)\n", stat_evaluate
);
1321 output("# of which %d times caused an early cutoff (leaf node)\n",
1322 stat_evaluate_cutoff
);
1323 output("#hash: %d writes, %d probes (%d succesful, =%d, >%d, <%d)\n",
1324 stat_hash_write
, stat_hash_tot
, stat_hash_ex
+stat_hash_low
+stat_hash_upp
,
1325 stat_hash_ex
, stat_hash_low
, stat_hash_upp
);
1326 output("#etc: %d\n", stat_early_transp
);
1327 output("#null move: %d (%d succesful)\n", stat_null_move
, stat_null_cut
);
1331 max_quiesce_board
.write_board(buf
);
1332 output("#max quiesce board: %s [%d %d]\n", buf
, max_quiesce_alpha
, max_quiesce_beta
);