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 PAWN_STRIKE 0
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
, bool pv
, int ply
, int orig_depth
,
244 Move best_mv_hash
, bool quiesce
, Move
* prev
, int* overall_extensions
)
250 for(int i
=0;i
<num_mv
;i
++)
255 /* give a high bonus to the move stored in the hash, if any.
256 mark only which is, don't continue, because some extensions
257 may be triggered ad added later (ie pawn strike, etc) */
258 if(mv
[i
].as_int
== best_mv_hash
.as_int
)
262 if(num_escapes
<=2 && PIECE_OF(board
.data
[mv
[i
].from
]) != PAWN
&&
263 (mv
[i
].from
== escape_from_1
[ply
-1] || mv
[i
].from
== escape_from_2
[ply
-1]) )
265 int x
= board
.move_see_val(mv
[i
]);
270 escapes
[num_escapes
] = i
;
276 /* process strong pawn moves */
277 if(PIECE_OF(board
.data
[mv
[i
].from
])==PAWN
) /* pawn strike */
279 uint8_t x
= X(mv
[i
].to
);
280 uint8_t y
= IS_WHITE(board
.color_to_move
) ? Y(mv
[i
].to
) : 7-Y(mv
[i
].to
);
282 if( mv
[i
].flags
== PROMOTEQUEEN
|| y
== 6)
284 int x
= board
.move_see_val(mv
[i
]);
288 mv
[i
].val
+= mv
[i
].flags
? 29600 : 29599; /* promote! */
289 mv
[i
].extend
= PLY
; /* extend search */
296 int other
= IS_WHITE(board
.other_color
);
298 if((!board
.line_pawns
[other
][x
].count
|| board
.line_pawns
[other
][x
].pos
[0] > pos
)
299 && (x
==0 || !board
.line_pawns
[other
][x
-1].count
|| board
.line_pawns
[other
][x
-1].pos
[0] >= pos
)
300 && (x
==7 || !board
.line_pawns
[other
][x
+1].count
|| board
.line_pawns
[other
][x
+1].pos
[0] >= pos
))
302 int x
= board
.move_see_val(mv
[i
]);
306 mv
[i
].val
+= y
>= 5 ? 29550 : 29500; /* passed pawn advancing! */
308 mv
[i
].extend
= PLY
; /* extend search */
315 if(orig_depth
>= 2*PLY
)
318 uint8_t up_right
= Board::up_dir
[IS_WHITE(board
.color_to_move
)] + RIGHT
;
319 uint8_t up_left
= Board::up_dir
[IS_WHITE(board
.color_to_move
)] + LEFT
;
320 uint8_t p1
= mv
[i
].to
+ up_right
;
321 uint8_t p2
= mv
[i
].to
+ up_left
;
322 uint8_t a
= OUT_OF_BOARD(p1
) ? 0 : board
.data
[p1
];
323 uint8_t b
= OUT_OF_BOARD(p2
) ? 0 : board
.data
[p2
];
324 if( (COLOR_OF(a
)==board
.other_color
&& PIECE_OF(a
)!=PAWN
)
325 || (COLOR_OF(b
)==board
.other_color
&& PIECE_OF(b
)!=PAWN
) )
327 int x
= board
.move_see_val(mv
[i
]);
331 mv
[i
].val
= 27000; /* pawn strike! */
341 int x
= board
.move_see_val(mv
[i
]);
344 if(prev
&& prev
->capture
&&
345 (mv
[i
].to
== prev
->to
) && (x
>= Board::simple_values
[PIECE_OF(prev
->capture
)]) )
348 if( (x
== Board::simple_values
[PIECE_OF(prev
->capture
)]) )
355 if(orig_depth
>-7*PLY
&& board
.move_is_check(mv
[i
]) )
361 else if(x
>=0 && orig_depth
>-7*PLY
&& board
.move_is_check(mv
[i
]) )
363 /* = capture but check */
368 else /* add a bonus for checks (but not too deep, or quiescence will get mad) */
369 if(board
.move_is_check(mv
[i
]) )
371 if(board
.move_see_val(mv
[i
])>=0)
378 /* null-move threat */
379 if(null_threat
[ply
-1] == mv
[i
])
385 mv
[i
].val
+= (history_hit
[HISTORY_INDEX(mv
[i
])] + 32) * 1024 / (history_tot
[HISTORY_INDEX(mv
[i
])] + 64);
388 static int bof
[128] = {
389 0,0,1,2,2,1,0,0,ENDL
,
390 0,1,2,3,3,2,1,0,ENDL
,
391 0,2,4,5,5,4,2,0,ENDL
,
392 1,2,5,6,6,5,2,1,ENDL
,
393 1,2,5,6,6,5,2,1,ENDL
,
394 0,2,4,5,5,4,2,0,ENDL
,
395 0,1,2,3,3,2,1,0,ENDL
,
399 /* add a bonus for moves towards the center */
400 mv
[i
].val
+= bof
[mv
[i
].to
];
401 //mv[i].val += (bof[mv[i].to] - bof[mv[i].from]);
402 #endif //CENTER_HEURISTIC
406 if(escape_from_1
[ply
-1] != INVALID
|| escape_from_2
[ply
-1] != INVALID
)
409 for(int i
=0;i
<num_escapes
;i
++)
410 mv
[escapes
[i
]].extend
= PLY
;
415 mv
[hash_move
].val
= 30000;
420 Engine::moves_quiescence_heuristic(Move
*mv
, int num_mv
, const Move
& best_mv_hash
,
421 int static_eval
, int alpha
, int beta
, int orig_depth
, Move
* prev
)
423 for(int i
=0;i
<num_mv
;i
++)
428 /* give a high bonus to the move stored in the hash, if any.
429 mark only which is, don't continue, because some extensions
430 may be triggered ad added later (ie pawn strike, etc) */
431 if(mv
[i
].as_int
== best_mv_hash
.as_int
)
437 /* process strong pawn moves */
438 if(PIECE_OF(board
.data
[mv
[i
].from
])==PAWN
)
440 if( ROW_OF(mv
[i
].to
) == board
.seventh_rank
[IS_WHITE(board
.color_to_move
)] )
442 int x
= board
.move_see_val(mv
[i
]);
446 mv
[i
].val
+= 29499; /* 7th push */
447 mv
[i
].extend
= PLY
; /* extend search */
452 if( mv
[i
].flags
== PROMOTEQUEEN
)
454 int x
= board
.move_see_val(mv
[i
]);
458 mv
[i
].val
+= 29500; /* promote! */
459 mv
[i
].extend
= PLY
; /* extend search */
467 int x
= board
.move_see_val(mv
[i
]);
469 if(prev
&& prev
->capture
&&
470 (mv
[i
].to
== prev
->to
) && (x
>= Board::simple_values
[PIECE_OF(prev
->capture
)]) )
472 mv
[i
].val
= 29900 + x
;
473 if( (x
== Board::simple_values
[PIECE_OF(prev
->capture
)]) )
480 if(orig_depth
>=-5*PLY
&& board
.move_is_check(mv
[i
]) )
486 else if(x
>=0 && orig_depth
>=-5*PLY
&& board
.move_is_check(mv
[i
]) )
488 /* = capture but check */
493 else /* add a bonus for checks (but not too deep, or quiescence will get mad) */
494 if(orig_depth
>=-3*PLY
&& board
.move_is_check(mv
[i
]) )
496 if(board
.move_see_val(mv
[i
])>=0)
506 /*******************************************************************************
507 The main alpha-beta recursive search function.
508 It handles both normal search (with or without null move)
509 and quiescence search, because i have having 2 almost identical
511 *******************************************************************************/
512 int16_t Engine::search(int ply
, int depth
, bool pv
, int16_t alpha
, int16_t beta
)
514 SearchStack
*s
= &stack
[ply
];
516 uint16_t cbest_mv_hash
= 0; /* the compressed move from the hash */
517 Move best_mv_hash
= Move::FromInt(0); /* the move from the hash */
518 int best_mv_found
= -1; /* the index of the best move AFTER searching */
520 bool extended
= false;
521 bool no_good_moves
= false;
522 int16_t lower_bound
= -INF
;
523 int16_t position_val
;
528 s
->base_depth
= depth
;
534 s
->threat
= Move::FromInt(0);
536 null_threat
[ply
] = Move::FromInt(0);
537 null_threat_dangerous
[ply
] = false;
539 escape_from_1
[ply
] = escape_from_2
[ply
] = INVALID
;
542 /* check if time is running out */
546 /* check for a draw for repetition or 50mvs. Of course the draw for
547 repetition must be checked BEFORE probing the hash :)*/
549 return (board
.color_to_move
== st_computer_color
) ? v_eval_draw
:
550 ((board
.other_color
== st_computer_color
) ? -v_eval_draw
: 0); /* be aggressive! */
552 /*******************************************************************************
554 If the probe is succesful the hashtable will return us value
555 that can be exact, a lower bound or an upper bound, and if the
556 depth of the hashed search is >= the current depth this value
557 will be used to improve alpha and beta and possibly return immediatly.
558 The hastable will also give us a "best" move that will be searched
560 This is the move that caused the "final" cutoff when this position
561 was searched previously. This best move is actually the index of the best
562 move in the array of generated moves (it is supposed to be deterministic :)
563 *******************************************************************************/
565 HashEntry
*h
= probe_hash( board
.hash
);
568 GUI(notify_hash(ply
, h
->lo
, h
->up
, h
->depth
, alpha
, beta
,
569 h
->best_mv
? board
.uncompress_move(h
->best_mv
) : Move::None(), false,
570 (((h
->depth
>= s
->base_depth
) && (h
->lo
>=beta
|| h
->up
==h
->lo
|| h
->up
<=alpha
))
571 ? SearchGui::Bold
: 0) | SearchGui::Magenta
) );
574 if(h
&& (h
->depth
>= s
->base_depth
))// || ABS(h->value)>INF-1000) )
576 int16_t l
= h
->lower();
577 int16_t u
= h
->upper();
585 best
= alpha
= MAX(alpha
, l
);
589 cbest_mv_hash
= h
->best_mv
;
591 /*******************************************************************************
592 Test if we are under check, and if so extend search
593 *******************************************************************************/
595 s
->under_check
= board
.under_attack(board
.king_pos
[IS_WHITE(board
.color_to_move
)],
598 /*******************************************************************************
599 If it is time to quiesce, evaluate and test if we can exit
600 immediately with a beta cut-off (try first a rough eval - delta)
601 *******************************************************************************/
602 quiesce
= ((!s
->under_check
) && (depth
<=0)) || (depth
<-60*PLY
);
605 if(quiesce
&& depth
>=-PLY
)
608 Move
*mv
= mv_stack
+ mv_stack_top
;
609 board
.do_null_move();
610 num_mv
= board
.find_moves(mv
);
611 uint8_t pup
= INVALID
;
613 for(int i
=0;i
<num_mv
;i
++)
615 if(!mv
[i
].capture
|| PIECE_OF(mv
[i
].capture
)==PAWN
)
617 if(mv
[i
].to
!= pup
&& board
.move_see_val(mv
[i
])>0)
627 board
.undo_null_move();
631 if(quiesce
&& (best
== -INF
) )
634 best
= board
.evaluate(st_computer_color
, alpha
, beta
);
635 lower_bound
= best
; //we have at the very least "best" as lower bound now.
636 GUI(notify_eval(ply
, best
, alpha
, beta
, best
>=beta
? SearchGui::Blue
|SearchGui::Bold
: SearchGui::Blue
));
638 alpha
= MAX(alpha
, best
);
641 stat_evaluate_cutoff
++;
649 if(quiesce
&& h
&& h
->no_good_moves
)
653 /*******************************************************************************
655 *******************************************************************************/
656 if(!s
->under_check
&& (stack
[ply
-1].curr_move
!= -1) && depth
>= 2*PLY
&& beta
<WORST_MATE
&& null_move_ok())
659 int sdepth
= (depth
>= 5*PLY
) ? (depth
-4*PLY
) : depth
-3*PLY
;
664 board
.do_null_move();
665 GUI1(notify(Move::None(), ply
, sdepth
, -INF
, beta
-1, beta
, SearchGui::Green
));
666 val
= -search( ply
+1, sdepth
, true, -beta
, -beta
+1);
667 GUI2(notify_value(ply
, val
, DIFF_NODES
, SearchGui::Bold
));
668 board
.undo_null_move();
678 if(val
< -WORST_MATE
)
679 null_threat_dangerous
[ply
] = true;
682 if(val
<alpha
-100 && /* we are facing a threat*/
683 stack
[ply
+1].best_move
!= -1) /* be sure we aren't reading random memory */
685 /* ok, officially the array stack[ply+1].moves has already
686 been deallocated, but who cares :) */
687 s
->threat
= stack
[ply
+1].moves
[stack
[ply
+1].best_move
];
690 /* Botvinnik-Markoff extension!!! */
691 if(!extended
&& ply
>=3 && (s
->threat
== stack
[ply
-2].threat
) )
704 /*******************************************************************************
705 Now generate the legal moves and look for a check/stalemate
706 *******************************************************************************/
708 /* generate all the legal moves */
709 s
->moves
= &mv_stack
[mv_stack_top
];
710 s
->num_moves
= board
.find_moves(s
->moves
);
711 mv_stack_top
+= s
->num_moves
;
712 s
->under_check
= board
.under_check
;
714 if(s
->under_check
==2) /* double check */
719 else if(s
->under_check
) /* simple check */
722 if(stack
[ply
-1].curr_move
>=0 &&
723 !board
.pins
[stack
[ply
-1].moves
[ /* last moved piece is not attacking the king */
724 stack
[ply
-1].curr_move
].to
]) /* so this is a discover check */
731 /* return now if the positon is terminal */
736 /* while mating, sacrify as much as possible :) */
737 int mt
= IS_WHITE(board
.other_color
) ? 5 : -1;
738 int16_t matval
= Board::simple_values
[PAWN
]*board
.mat_tracking
[mt
+PAWN
].count
+
739 Board::simple_values
[KNIGHT
]*board
.mat_tracking
[mt
+KNIGHT
].count
+
740 Board::simple_values
[BISHOP
]*board
.mat_tracking
[mt
+BISHOP
].count
+
741 Board::simple_values
[QUEEN
]*board
.mat_tracking
[mt
+QUEEN
].count
;
742 best
= alpha
= beta
= -INF
+ ply
*100 + matval
;
745 best
= alpha
= beta
= 0;
749 /* single-reply extension */
750 if(s
->num_moves
== 1 && !extended
)
755 else if(s
->num_moves
<= 3 && !extended
)
761 /*******************************************************************************
763 First comes the move from the hashtable, if avalable.
764 The remaining moves are sorted with a heuristic that keeps in account
765 the history heuristic (ie the moves that previously caused an alpha
766 cutoff), a MVV/LVA bonus value and a small bonus for moves that go
768 *******************************************************************************/
770 /* convert the move we got from the hash to the move structure */
773 best_mv_hash
= board
.uncompress_move(cbest_mv_hash
);
774 /* if it happened that the move we got from the hashtable
775 is not valid, simply no move will get the high
776 heuristic bonus value */
778 #if INTERNAL_ITERATIVE_DEEPENING
779 else if(s
->base_depth
>3*PLY
&& pv
) /* don't do it only on the pv, or it will be useless :) */
783 GUI1(notify(Move::None(), ply
, s
->base_depth
-2*PLY
, -INF
, alpha
, beta
, SearchGui::Blue
));
784 int val
= search(ply
+1, s
->base_depth
-2*PLY
, true, alpha
, beta
);
785 GUI2(search_gui
->notify_value(ply
, val
, DIFF_NODES
, 0));
788 HashEntry
*h2
= probe_hash( board
.hash
);
789 if(h2
&& h2
->best_mv
)
791 cbest_mv_hash
= h2
->best_mv
;
792 best_mv_hash
= board
.uncompress_move(cbest_mv_hash
);
795 #endif //INTERNAL_ITERATIVE_DEEPENING
797 /* for each move calculate the heuristic goodness value */
799 Move
*prev
= (stack
[ply
-1].curr_move
>=0) ? &stack
[ply
-1].moves
[stack
[ply
-1].curr_move
] : NULL
;
801 moves_quiescence_heuristic( s
->moves
, s
->num_moves
, best_mv_hash
,
802 best
, alpha
, beta
, s
->base_depth
, prev
);
806 moves_heuristic( s
->moves
, s
->num_moves
, pv
, ply
, s
->base_depth
,
807 best_mv_hash
, quiesce
, prev
, &overall_ext
);
808 depth
+= overall_ext
;
812 /* if quiesce rip-off the "non-critical" moves */
816 for(int i
=0;i
<s
->num_moves
;i
++)
817 if(s
->moves
[i
].val
>0)
818 s
->moves
[n
++] = s
->moves
[i
];
819 mv_stack_top
-= s
->num_moves
-n
;
822 no_good_moves
= true;
825 /* Don't do it now, do it incrementally */
826 //sort_moves( s->moves, s->num_moves );
829 #if EARLY_TRANSP_CUTOFF
830 /*******************************************************************************
831 Try to get an early beta cutoff using the hash table values
832 of the following moves, and improve alpha too.
833 Try on the first 6 value of the ordered moves (argh, looking into the
834 hashtable is very expensive because of the cache!!!!!!!!)
835 *******************************************************************************/
839 HashKey hk
= board
.move_hash(s
->moves
[0]);
840 for(int i
=1;i
<s
->num_moves
;i
++)
843 HashKey newhk
= board
.move_hash(s
->moves
[i
]);
844 HashEntry
*h2
= probe_hash( hk
);
847 if(h2
&& h2
->depth
>= depth
-PLY
)
854 alpha
= MAX(alpha
, (int16_t)-h2
->up
);
858 HashEntry
*h2
= probe_hash( hk
);
859 if(h2
&& h2
->depth
>= depth
-PLY
)
866 alpha
= MAX(alpha
, (int16_t)-h2
->up
);
869 #endif //EARLY_TRANSP_CUTOFF
871 /*******************************************************************************
872 It is now time to loop all the successor moves and search recursively.
873 *******************************************************************************/
876 /* calcluate the evaluation (required by fitility pruning) */
877 position_val
= quiesce
? best
: board
.dummy_evaluate(); //evaluate( st_computer_color, -INF, INF);
880 for(int i
=0;i
<s
->num_moves
;i
++)
883 int sdepth
= depth
-100;
885 /* sort moves incrementally, in the hope of a beta cut */
886 incremental_sort_moves(s
->moves
+i
, s
->num_moves
-i
);
888 /* extensions calculated during the heuristic sort */
889 sdepth
+= s
->moves
[i
].extend
;
892 /* futility pruning, it is done only if we are not under check
893 and the move is not a "critical" move */
894 if(depth
>0 && depth
<=2*PLY
&& !s
->under_check
&& s
->moves
[i
].val
< 28000)
896 static const int mavala
[] = { 0, 500, 325, 1000, 325, 100, 0 };
898 int16_t fmargin
= (depth
<= PLY
? 420 : 720);
899 int16_t fval
= position_val
+ mavala
[PIECE_OF(s
->moves
[i
].capture
)];
900 if(fval
< alpha
-fmargin
)
905 /* collect history statistics */
906 if(!s
->moves
[i
].capture
&&
907 !(s
->moves
[i
].flags
>=PROMOTE_FIRST
) )
909 int ix
= HISTORY_INDEX(s
->moves
[i
]);
910 if(history_tot
[ix
] > 1024)
912 history_tot
[ix
] = history_tot
[ix
]*7/8;
913 history_hit
[ix
] = history_hit
[ix
]*7/8;
915 history_tot
[ix
] += quiesce
? 8 : 16;
918 //Set data for pawn-strike
920 if(!quiesce
&& PIECE_OF(board
.data
[s
->moves
[i
].from
]) == PAWN
&& s
->moves
[i
].val
== 27000) //FIXME, UGLY
922 escape_from_1
[ply
] = s
->moves
[i
].to
+ Board::up_dir
[IS_WHITE(board
.color_to_move
)] + RIGHT
;
923 if(OUT_OF_BOARD(escape_from_1
[ply
]) || !IS_OF_COLOR(escape_from_1
[ply
], board
.other_color
)
924 || PIECE_OF(escape_from_1
[ply
])==PAWN
)
925 escape_from_1
[ply
] = INVALID
;
926 escape_from_2
[ply
] = s
->moves
[i
].to
+ Board::up_dir
[IS_WHITE(board
.color_to_move
)] + LEFT
;
927 if(OUT_OF_BOARD(escape_from_2
[ply
]) || !IS_OF_COLOR(escape_from_2
[ply
], board
.other_color
)
928 || PIECE_OF(escape_from_2
[ply
])==PAWN
)
929 escape_from_2
[ply
] = INVALID
;
933 escape_from_1
[ply
] = escape_from_2
[ply
] = INVALID
;
938 board
.do_move(s
->moves
[i
]);
942 if(s
->base_depth
> 0 && sdepth
<= 0)
944 STAT(quiesce_called
);
945 q
= stat_quiesce_nodes
;
948 #if NEGA_SCOUT /* use negascout, (null window search for nodes that are not in the pv) */
951 GUI1(notify(s
->moves
[i
], ply
, sdepth
, s
->moves
[i
].val
, alpha
, beta
, SearchGui::Bold
));
952 val
= -search( ply
+1, sdepth
, pv
, -beta
, -alpha
);
953 GUI2(notify_value(ply
, val
, DIFF_NODES
, 0));
957 #if LATE_MOVE_REDUCTION
958 /* history pruning, if this is not a "critical" move and the failhigh
959 stats are too low, try a reduced depth search (if it returns >alpha,
960 re-do the full depth search) */
961 // if((sdepth>0) && !s->under_check && depth<=3*PLY && s->moves[i].val<28000 &&
962 // (history_hit[HISTORY_INDEX(s->moves[i])]+1)*3
963 // < (history_tot[HISTORY_INDEX(s->moves[i])]+1))
964 if( (sdepth
>0) && !s
->under_check
&& !null_threat_dangerous
[ply
]
965 && s
->moves
[i
].val
<28000 && s
->moves
[i
].val
<450 )
967 int rdepth
= sdepth
- PLY
; //(s->moves[i].val<300 ? 2*PLY : PLY) - s->moves[i].extend;
968 GUI1(notify(s
->moves
[i
], ply
, rdepth
, s
->moves
[i
].val
, alpha
, alpha
+1, SearchGui::Italic
|SearchGui::Gray
));
969 val
= -search( ply
+1, rdepth
, false, -alpha
-1, -alpha
);
970 GUI2(notify_value(ply
, val
, DIFF_NODES
, val
>alpha
? SearchGui::Red
: 0));
972 goto skip_search
; /* reduced search was effective */
975 GUI1(notify(s
->moves
[i
], ply
, sdepth
, s
->moves
[i
].val
, alpha
, alpha
+1, 0 ));
976 val
= -search( ply
+1, sdepth
, false, -alpha
-1, -alpha
);
977 GUI2(notify_value(ply
, val
, DIFF_NODES
, val
>alpha
? SearchGui::Red
: 0));
978 if((val
>alpha
) && pv
)
980 GUI1(notify(s
->moves
[i
], ply
, sdepth
, -INF
, alpha
, beta
, SearchGui::Bold
));
981 val
= -search( ply
+1, sdepth
, true, -beta
, -alpha
);
982 GUI2(notify_value(ply
, val
, DIFF_NODES
, val
>beta
? SearchGui::Red
: 0));
986 /* normal full width alpha-beta */
987 val
= -search( ply
+1, sdepth
, pv
, -beta
, -alpha
);
990 if(s
->base_depth
> 0 && sdepth
<= 0)
992 q
= stat_quiesce_nodes
-q
;
993 if(q
> stat_max_quiesce_nodes
)
995 stat_max_quiesce_nodes
= q
;
996 max_quiesce_board
= board
;
1001 board
.undo_move(s
->moves
[i
]);
1004 /* update the current best value and check for and alpha cut */
1015 /* alpha improvement! */
1024 /* update a few stats */
1027 if(best_mv_found
==0)
1034 stat_search_moves
++;
1035 if(ply
==0 && depth
>100)
1037 if(best_mv_found
==0)
1044 stat_search_moves0
++;
1048 /* collect statistics for the history */
1049 if(/*best >= beta &&*/ (best_mv_found
!=-1) &&
1050 !s
->moves
[best_mv_found
].capture
&&
1051 !(s
->moves
[best_mv_found
].flags
>=PROMOTE_FIRST
) )
1052 history_hit
[HISTORY_INDEX(s
->moves
[best_mv_found
])] += quiesce
? 8 : 16;
1055 mv_stack_top
-= s
->num_moves
; /* free the moves we allocated */
1057 /* this is a null move, save what the threat is */
1058 if(stack
[ply
-1].curr_move
== -1 && best_mv_found
>= 0)
1059 null_threat
[ply
-1] = s
->moves
[best_mv_found
];
1061 /* if we found a best move searching, that move will be saved.
1062 if we did no search (ie quiescence), save the old hash value,
1063 or -1 if no hash entry had been found */
1064 int bestmv
= cbest_mv_hash
;
1065 if(best_mv_found
>= 0)
1066 bestmv
= board
.compress_move(s
->moves
[best_mv_found
]);
1068 /* write the value in the hash, with the index of the best move */
1069 write_hash( best
> s
->alpha
? MIN(best
, beta
) : lower_bound
,
1070 best
< beta
? best
: +INF
,
1071 MAX(s
->base_depth
,-500), bestmv
, no_good_moves
);
1072 GUI(notify_hash(ply
, best
> s
->alpha
? MIN(best
, beta
) : lower_bound
, best
< beta
? best
: +INF
,
1073 MAX(s
->base_depth
,-500), alpha
, beta
, bestmv
? board
.uncompress_move(bestmv
) : Move::None(), true,
1074 SearchGui::Bold
| SearchGui::Magenta
) );
1080 Move
Engine::find_best_move()
1082 int num_mate_hits
= 0;
1083 SearchStack
*s
= &stack
[0];
1089 /* initialize the root node */
1091 s
->base_depth
= 100;
1096 s
->threat
= Move::FromInt(0);
1099 s
->moves
= mv_stack
;
1100 s
->num_moves
= mv_stack_top
= board
.find_moves(s
->moves
);
1102 /* calculate how much time we will think*/
1103 start_think_time
= current_time();
1104 if( analysis_limit
== TIME_LIMIT
)
1106 if(board
.color_to_move
== st_computer_color
)
1108 else /* pondering? analysing? */
1109 time_best_csec
= 99999999;
1110 max_think_time
= start_think_time
+ time_best_csec
- 2;
1113 /* to print the analysis */
1115 output("\tply\tscore\ttime\tnodes\tpv\n");
1117 /* return immediatly if the move is forced. */
1121 /* probe the play lines */
1122 if( eng_status
== PLAYING
1123 && st_computer_color
== board
.color_to_move
1124 && probe_lines( board
.hash
, &retv
))
1130 /* probe the book */
1131 if(probe_book( board
.hash
, &retv
)) {
1132 for(int i
=0;i
<s
->num_moves
++;i
++)
1133 if(retv
.as_int
== s
->moves
[i
].as_int
)
1138 output("Error!!! invalid move in the book!!!\n");
1141 stat_early_transp
= 0;
1146 stat_best_first
= 0;
1148 stat_search_moves
= 0;
1149 stat_best_first0
= 0;
1151 stat_search_moves0
= 0;
1153 stat_evaluate_cutoff
= 0;
1156 stat_hash_write
= 0;
1159 IFGUI(reset_hash()); //ONLY FOR DEBUGGING!!!
1161 //analysis_color = board.color_to_move;
1162 processed_nodes
= 0;
1166 /* set the back jump for the quick thinking exit */
1170 if(search_gui
) search_gui
->init_root();
1172 /* start with a guess of 0 */
1173 s
->moves
[0].val
= 0;
1176 memset( history_tot
, 0, HISTORY_SIZE
*sizeof(uint16_t));
1177 memset( history_hit
, 0, HISTORY_SIZE
*sizeof(uint16_t));
1179 /* do the iterative deepening thing. */
1182 int16_t alpha
= num_mate_hits
? -INF
: -WORST_MATE
;
1183 int16_t beta
= num_mate_hits
? INF
: WORST_MATE
;
1186 if(search_gui
) search_gui
->new_root_level(s
->base_depth
);
1188 /* save the result of the previous search */
1189 result
[s
->base_depth
/PLY
-1] = s
->moves
[0];
1191 /* for each move call the alpha-beta search function */
1193 for(i
=0;i
<s
->num_moves
;i
++)
1197 board
.do_move(s
->moves
[i
]);
1201 GUI1(notify(s
->moves
[i
], 0, s
->base_depth
-PLY
, s
->moves
[i
].val
, alpha
, beta
, SearchGui::Bold
));
1202 s
->moves
[i
].val
= -search( 1, s
->base_depth
-PLY
, true, -beta
, -alpha
);
1203 GUI2(notify_value(0, s
->moves
[i
].val
, DIFF_NODES
, 0));
1207 GUI1(notify(s
->moves
[i
], 0, s
->base_depth
-PLY
, s
->moves
[i
].val
, alpha
, alpha
+1, 0 ));
1208 s
->moves
[i
].val
= -search( 1, s
->base_depth
-PLY
, false, -alpha
-1, -alpha
);
1209 GUI2(notify_value(0, s
->moves
[i
].val
, DIFF_NODES
, s
->moves
[i
].val
>alpha
? SearchGui::Red
: 0));
1211 if(s
->moves
[i
].val
> alpha
)
1213 GUI1(notify(s
->moves
[i
], 0, s
->base_depth
-PLY
, -INF
, alpha
, beta
, SearchGui::Bold
));
1214 s
->moves
[i
].val
= -search( 1, s
->base_depth
-PLY
, true, -beta
, -alpha
);
1215 GUI2(notify_value(0, s
->moves
[i
].val
, DIFF_NODES
, 0));
1219 s
->moves
[i
].val
= -search( 1, s
->base_depth
-PLY
, true, -beta
, -alpha
);
1221 board
.undo_move(s
->moves
[i
]);
1226 if(s
->moves
[i
].val
> alpha
)
1228 alpha
= s
->moves
[i
].val
;
1233 /* this move caused an alpha cut, so print the new line */
1234 if( post
/*&& processed_nodes>100000*/)
1236 output("\t%d\t%d\t%d\t%llu\t", s
->base_depth
/100,
1237 s
->moves
[i
].val
, current_time() - start_think_time
, processed_nodes
);
1238 print_moves(&s
->moves
[i
], 1, true);
1243 /* the search is done, sort the moves so that best is searched first */
1246 s
->moves
[best_mv
].val
++;
1247 sort_moves(s
->moves
, i
); /* sort i moves (those that we where able to search) */
1251 /* print the result of the analysis at this depth */
1252 if( post
/*&& processed_nodes>100000*/)
1254 output("\t%d\t%d\t%d\t%llu\t", s
->base_depth
/100,
1255 s
->moves
[0].val
, current_time() - start_think_time
, processed_nodes
);
1256 print_moves(&s
->moves
[0], 1, true);
1260 if( s
->base_depth
>= 40*PLY
)
1263 /* return in case of fixed depth search */
1264 if( eng_status
== PLAYING
&& st_computer_color
== board
.color_to_move
&&
1265 analysis_limit
== DEPTH_LIMIT
&& s
->base_depth
== st_depth
*PLY
)
1268 /* return if 3/5 of time is gone (we can't search another ply anyway) */
1269 if( eng_status
== PLAYING
&& st_computer_color
== board
.color_to_move
&&
1270 analysis_limit
== TIME_LIMIT
&&
1271 (current_time()-start_think_time
) >= (time_best_csec
*3/5) )
1274 /* if a checkmate was detected return immediately */
1275 if( ABS(alpha
) > WORST_MATE
)
1278 if(num_mate_hits
>= 5)
1282 s
->base_depth
+= PLY
;
1290 prof_tot
= rdtsc() - prof_tot
;
1291 #define SHOW_PROF(a) output("@"#a": %llu (%llu%%)\n", \
1292 prof_##a, prof_##a*100/prof_tot);
1296 SHOW_PROF(find_moves
);
1297 SHOW_PROF(find_captures
);
1298 SHOW_PROF(heuristic
);
1299 SHOW_PROF(move_is_check
);
1300 SHOW_PROF(move_see_val
);
1301 SHOW_PROF(sort_moves
);
1303 output("#nodes: %llu (~%llu nps)\n", processed_nodes
, (processed_nodes
*100)/
1304 MAX(current_time()-start_think_time
,1) );
1305 output("# %d times all the moves were seached (non-leaf non-quiesce node)\n",
1307 output("# of which %d times first move caused a cutoff\n", stat_best_cut
);
1308 output("# of the remaining %d times first move was really best (%02d%%)\n",
1309 stat_best_first
, (stat_best_first
*100)/MAX(stat_search_moves
-stat_best_cut
, 1));
1310 output("# evaluate was called %d times (quiescence node)\n", stat_evaluate
);
1311 output("# of which %d times caused an early cutoff (leaf node)\n",
1312 stat_evaluate_cutoff
);
1313 output("#hash: %d writes, %d probes (%d succesful, =%d, >%d, <%d)\n",
1314 stat_hash_write
, stat_hash_tot
, stat_hash_ex
+stat_hash_low
+stat_hash_upp
,
1315 stat_hash_ex
, stat_hash_low
, stat_hash_upp
);
1316 output("#etc: %d\n", stat_early_transp
);
1317 output("#null move: %d (%d succesful)\n", stat_null_move
, stat_null_cut
);
1321 max_quiesce_board
.write_board(buf
);
1322 output("#max quiesce board: %s [%d %d]\n", buf
, max_quiesce_alpha
, max_quiesce_beta
);