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"
32 S(max_quiesce_nodes); \
36 S(quiesce_best_can_be_first); \
37 S(quiesce_best_was_first); \
39 S(quiesce_cutoff_first); \
42 S(search_best_can_be_first); \
43 S(search_best_was_first); \
45 S(search_cutoff_first); \
49 #define STAT(x) stat_##x++;
51 #define S(x) uint64_t stat_##x;
53 Board max_quiesce_board
;
54 int16_t max_quiesce_alpha
;
55 int16_t max_quiesce_beta
;
60 #define S(x) stat_##x = 0;
67 #define S(x) printf("# " #x " = %llu\n", (unsigned long long)stat_##x);
75 /* enable the nega-scout pv-search */
78 /* enable the null move */
81 /* il null move > beta-margin, reduce (not a dangerous position). Set to 1 to disable */
82 #define NULL_SOLIDITY_MARGIN 1
84 /* before doing the alpha beta search check if any of the following positions
85 can give use an early cutoff thanks to the hashtable */
86 #define EARLY_TRANSP_CUTOFF 0
88 /* reduce nodes for moves that are not check/captures that are considered
89 bad from the heuristic */
90 #define LATE_MOVE_REDUCTION 0
92 /* futility pruning: */
95 /* when the hashtable provides no "best" move, do a depth-2 search */
96 #define INTERNAL_ITERATIVE_DEEPENING 0
98 /* use the history sorting heuristic */
99 #define HISTORY_HEURISTIC 1
101 /* improve the sorting heuristic for pawn strikes */
102 #define PAWN_STRIKE 1
104 #define IGNORE_ALLBAD_NODES 0
107 void Engine::print_stat()
109 if(thinking
&& current_root
)
111 output("stat01: %d %llu %d %d %d %s\n",
112 current_time() - start_think_time
,
113 (unsigned long long)processed_nodes
,
114 current_root
->base_depth
/PLY
,
115 current_root
->stack
[0].num_moves
- 1 - current_root
->stack
[0].curr_move
,
116 current_root
->stack
[0].num_moves
,
117 board
.move_to_alg(TmpStr().data(),
118 current_root
->stack
[0].moves
[current_root
->stack
[0].curr_move
])
122 output("stat01: 0 0 0 0 0\n");
125 bool SearchRoot::null_move_ok()
127 int c
= IS_WHITE(board
.color_to_move
) ? 5 : -1;
128 int numpawns
= board
.mat_tracking
[c
+PAWN
].count
;
129 int numpieces
= board
.mat_tracking
[c
+KNIGHT
].count
+ board
.mat_tracking
[c
+BISHOP
].count
130 + board
.mat_tracking
[c
+ROOK
].count
+ board
.mat_tracking
[c
+QUEEN
].count
;
133 if(numpieces
>= 1 && numpawns
>= 2)
139 SearchRoot::moves_heuristic(Move
*mv
, int num_mv
, bool pv
, int ply
, int orig_depth
,
140 Move best_mv_hash
, bool quiesce
, Move
* prev
, int* overall_extensions
,
149 for(int i
=0;i
<num_mv
;i
++)
154 /* give a high bonus to the move stored in the hash, if any.
155 mark only which is, don't continue, because some extensions
156 may be triggered ad added later (ie pawn strike, etc) */
157 if(mv
[i
].as_int
== best_mv_hash
.as_int
)
161 if(num_escapes
<=2 && PIECE_OF(board
.data
[mv
[i
].from
]) != PAWN
&&
162 (mv
[i
].from
== stack
[ply
-1].escape_from
[1] || stack
[ply
-1].escape_from
[2]) )
164 int x
= board
.move_see_val(mv
[i
]);
169 escapes
[num_escapes
] = i
;
175 /* process strong pawn moves */
176 if(PIECE_OF(board
.data
[mv
[i
].from
])==PAWN
) /* pawn strike */
178 uint8_t x
= X(mv
[i
].to
);
179 uint8_t y
= IS_WHITE(board
.color_to_move
) ? Y(mv
[i
].to
) : 7-Y(mv
[i
].to
);
181 if( mv
[i
].flags
== PROMOTEQUEEN
|| y
== 6)
183 int x
= board
.move_see_val(mv
[i
]);
187 mv
[i
].val
+= mv
[i
].flags
? 29600 : 29599; /* promote! */
188 mv
[i
].extend
= PLY
; /* extend search */
195 int other
= IS_WHITE(board
.other_color
);
197 if((!board
.line_pawns
[other
][x
].count
|| board
.line_pawns
[other
][x
].pos
[0] > pos
)
198 && (x
==0 || !board
.line_pawns
[other
][x
-1].count
|| board
.line_pawns
[other
][x
-1].pos
[0] >= pos
)
199 && (x
==7 || !board
.line_pawns
[other
][x
+1].count
|| board
.line_pawns
[other
][x
+1].pos
[0] >= pos
))
201 int x
= board
.move_see_val(mv
[i
]);
205 mv
[i
].val
+= y
>= 5 ? 29550 : 29500; /* passed pawn advancing! */
207 mv
[i
].extend
= PLY
; /* extend search */
214 if(orig_depth
>= 2*PLY
)
217 uint8_t up_right
= Board::up_dir
[IS_WHITE(board
.color_to_move
)] + RIGHT
;
218 uint8_t up_left
= Board::up_dir
[IS_WHITE(board
.color_to_move
)] + LEFT
;
219 uint8_t p1
= mv
[i
].to
+ up_right
;
220 uint8_t p2
= mv
[i
].to
+ up_left
;
221 uint8_t a
= OUT_OF_BOARD(p1
) ? 0 : board
.data
[p1
];
222 uint8_t b
= OUT_OF_BOARD(p2
) ? 0 : board
.data
[p2
];
223 if( (COLOR_OF(a
)==board
.other_color
&& PIECE_OF(a
)!=PAWN
)
224 || (COLOR_OF(b
)==board
.other_color
&& PIECE_OF(b
)!=PAWN
) )
226 int x
= board
.move_see_val(mv
[i
]);
230 mv
[i
].val
= 27000; /* pawn strike! */
239 int x
= board
.move_see_val(mv
[i
]);
242 if(prev
&& prev
->capture
&&
243 (mv
[i
].to
== prev
->to
) && (x
>= Board::simple_values
[PIECE_OF(prev
->capture
)]) )
246 if( (x
== Board::simple_values
[PIECE_OF(prev
->capture
)]) )
253 if(orig_depth
>-7*PLY
&& board
.move_is_check(mv
[i
]) )
259 else if(x
>=0 && orig_depth
>-7*PLY
&& board
.move_is_check(mv
[i
]) )
261 /* = capture but check */
266 else /* add a bonus for checks (but not too deep, or quiescence will get mad) */
267 if(board
.move_is_check(mv
[i
]) )
269 if(board
.move_see_val(mv
[i
])>=0)
276 /* null-move threat */
277 if(stack
[ply
-1].null_threat
== mv
[i
])
284 mv
[i
].val
+= (history_hit
[HISTORY_INDEX(mv
[i
])] + 32) * 1024 / (3 * (history_tot
[HISTORY_INDEX(mv
[i
])] + 64));
286 int mx
= CAPT_INDEX(mv
[i
]);
289 int ix
= FAST_PLUTO(p1
, mx
);
290 mv
[i
].val
+= (pluto_hit
[ix
] + 24) * 1024 / (3 * (pluto_tot
[ix
] + 48));
296 int ix
= FAST_PLUTO(p2
, mx
);
297 mv
[i
].val
+= (pluto2_hit
[ix
] + 16) * 1024 / (3 * (pluto2_tot
[ix
] + 32));
302 mv
[i
].val
+= (history_hit
[HISTORY_INDEX(mv
[i
])] + 32) * 256*4 / (history_tot
[HISTORY_INDEX(mv
[i
])] + 64);
307 if((stack
[ply
-1].escape_from
[1] != INVALID
|| stack
[ply
-1].escape_from
[2] != INVALID
) && num_escapes
<= 2)
309 for(int i
=0;i
<num_escapes
;i
++)
310 mv
[escapes
[i
]].extend
= PLY
;
315 mv
[hash_move
].val
= 30000;
320 SearchRoot::moves_quiescence_heuristic(Move
*mv
, int num_mv
, const Move
& best_mv_hash
,
321 int static_eval
, int alpha
, int beta
, int orig_depth
, Move
* prev
)
324 for(int i
=0;i
<num_mv
;i
++)
329 /* give a high bonus to the move stored in the hash, if any.
330 mark only which is, don't continue, because some extensions
331 may be triggered ad added later (ie pawn strike, etc) */
332 if(mv
[i
].as_int
== best_mv_hash
.as_int
)
335 /* process strong pawn moves */
336 if(PIECE_OF(board
.data
[mv
[i
].from
])==PAWN
)
338 if( ROW_OF(mv
[i
].to
) == board
.seventh_rank
[IS_WHITE(board
.color_to_move
)] )
340 int x
= board
.move_see_val(mv
[i
]);
344 mv
[i
].val
+= 29499; /* 7th push */
345 mv
[i
].extend
= PLY
; /* extend search */
350 if( mv
[i
].flags
== PROMOTEQUEEN
)
352 int x
= board
.move_see_val(mv
[i
]);
356 mv
[i
].val
+= 29500; /* promote! */
357 mv
[i
].extend
= PLY
; /* extend search */
365 int x
= board
.move_see_val(mv
[i
]);
367 if(prev
&& prev
->capture
&&
368 (mv
[i
].to
== prev
->to
) && (x
>= Board::simple_values
[PIECE_OF(prev
->capture
)]) )
370 mv
[i
].val
= 29900 + x
;
371 if( (x
== Board::simple_values
[PIECE_OF(prev
->capture
)]) )
376 if( x
>0 && ((orig_depth
>-2*PLY
|| static_eval
==-INF
) ? true : x
*100+static_eval
+200>alpha
) )
381 else if((x
>=0 && orig_depth
>-4*PLY
) && board
.move_is_check(mv
[i
]) )
383 /* = capture but check */
388 else /* add a bonus for checks (but not too deep, or quiescence will get mad) */
389 if(orig_depth
>-2*PLY
&& board
.move_is_check(mv
[i
]) && board
.move_see_val(mv
[i
])>=0)
396 if(hash_move
>= 0 && mv
[hash_move
].val
> 9000)
397 mv
[hash_move
].val
= 30000;
401 /*******************************************************************************
402 The main alpha-beta recursive search function.
403 It handles both normal search (with or without null move)
404 and quiescence search, because i have having 2 almost identical
406 *******************************************************************************/
407 int16_t SearchRoot::search(int ply
, int base_depth
, bool pv
, int16_t orig_alpha
, int16_t beta
, bool expect_allbad
)
409 SearchStack
*s
= &stack
[ply
];
411 uint16_t cbest_mv_hash
= 0; /* the compressed move from the hash */
412 Move best_mv_hash
= Move::FromInt(0); /* the move from the hash */
413 int best_mv_found
= -1; /* the index of the best move AFTER searching */
415 bool extended
= false;
416 bool no_good_moves
= false;
417 int16_t lower_bound
= -INF
;
419 int16_t position_val
;
421 int depth
= base_depth
;
422 int16_t alpha
= orig_alpha
;
425 #if IGNORE_ALLBAD_NODES
426 expect_allbad
= false;
432 for(int i
=ply
-1;i
>=0;i
--)
434 if(stack
[i
].curr_move
== -1)
435 board
.undo_null_move(stack
[i
].save_buf
);
436 else if(stack
[i
].curr_move
>= 0)
437 board
.undo_move(stack
[i
].moves
[stack
[i
].curr_move
], stack
[i
].save_buf
);
439 printf("[FEN \"%s\"]\n", board
.to_fen(BigStr().data()) );
440 for(int i
=0;i
<ply
;i
++)
442 printf(" %s", stack
[i
].curr_move
<= -1 ? "NULL" :
443 board
.move_to_alg(TmpStr().data(), stack
[i
].moves
[stack
[i
].curr_move
]));
444 if(stack
[i
].curr_move
== -1)
445 board
.do_null_move(stack
[i
].save_buf
);
446 else if(stack
[i
].curr_move
>= 0)
447 board
.do_move(stack
[i
].moves
[stack
[i
].curr_move
], stack
[i
].save_buf
);
455 // STAT(quiesce_nodes)
460 s
->null_threat
= Move::FromInt(0);
461 s
->null_threat_dangerous
= false;
463 stack
[ply
].escape_from
[1] = stack
[ply
].escape_from
[2] = INVALID
;
466 engine
->prefetch_hash( board
.hash
);
468 /* check if time is running out */
469 engine
->check_time();
471 /* check for a draw for repetition or 50mvs. Of course the draw for
472 repetition must be checked BEFORE probing the hash :)*/
474 return (board
.color_to_move
== engine
->st_computer_color
) ? engine
->v_eval_draw
:
475 ((board
.other_color
== engine
->st_computer_color
) ? -engine
->v_eval_draw
: 0); /* be aggressive! */
477 /*******************************************************************************
479 If the probe is succesful the hashtable will return us value
480 that can be exact, a lower bound or an upper bound, and if the
481 depth of the hashed search is >= the current depth this value
482 will be used to improve alpha and beta and possibly return immediatly.
483 The hastable will also give us a "best" move that will be searched
485 This is the move that caused the "final" cutoff when this position
486 was searched previously. This best move is actually the index of the best
487 move in the array of generated moves (it is supposed to be deterministic :)
488 *******************************************************************************/
490 HashEntry
*h
= engine
->probe_hash( board
.hash
);
493 GUI(notify_hash(ply
, h
->lo
, h
->up
, h
->depth
, alpha
, beta
,
494 h
->best_mv
? board
.uncompress_move(h
->best_mv
) : Move::None(), false,
495 (((h
->depth
>= base_depth
) && (h
->lo
>=beta
|| h
->up
==h
->lo
|| h
->up
<=alpha
))
496 ? SearchGui::Bold
: 0) | SearchGui::Magenta
) );
499 if(h
&& (h
->depth
>= base_depth
))// || ABS(h->value)>INF-1000) )
501 int16_t l
= h
->lower();
502 int16_t u
= h
->upper();
510 best
= alpha
= MAX(alpha
, l
);
514 cbest_mv_hash
= h
->best_mv
;
516 /*******************************************************************************
517 Test if we are under check, and if so extend search
518 *******************************************************************************/
520 s
->under_check
= board
.under_attack(board
.king_pos
[IS_WHITE(board
.color_to_move
)],
523 /*******************************************************************************
524 If it is time to quiesce, evaluate and test if we can exit
525 immediately with a beta cut-off (try first a rough eval - delta)
526 *******************************************************************************/
527 quiesce
= ((!s
->under_check
) && (depth
<=0)) || (ply
> 70);
532 if(quiesce
&& depth
>=-PLY
)
535 Move
*mv
= mv_stack
+ mv_stack_top
;
536 board
.do_null_move();
537 num_mv
= board
.find_moves(mv
);
538 uint8_t pup
= INVALID
;
540 for(int i
=0;i
<num_mv
;i
++)
542 if(!mv
[i
].capture
|| PIECE_OF(mv
[i
].capture
)==PAWN
)
544 if(mv
[i
].to
!= pup
&& board
.move_see_val(mv
[i
])>0)
554 board
.undo_null_move();
558 if(quiesce
&& (best
== -INF
|| ply
>70) )
560 best
= board
.evaluate(engine
->st_computer_color
, alpha
, beta
);
561 lower_bound
= best
; //we have at the very least "best" as lower bound now.
562 GUI(notify_eval(ply
, best
, alpha
, beta
, best
>=beta
? SearchGui::Blue
|SearchGui::Bold
: SearchGui::Blue
));
564 alpha
= MAX(alpha
, best
);
572 if(quiesce
&& h
&& h
->no_good_moves
)
576 /*******************************************************************************
578 *******************************************************************************/
579 if(!expect_allbad
&& !pv
&& !s
->under_check
&& (stack
[ply
-1].curr_move
!= -1)
580 && depth
>= 2*PLY
&& beta
<WORST_MATE
&& null_move_ok())
583 int sdepth
= (depth
>= 5*PLY
) ? (depth
-4*PLY
) : depth
-3*PLY
;
586 board
.do_null_move(s
->save_buf
);
587 GUI1(notify(&board
, Move::None(), ply
, sdepth
, -INF
, beta
-1, beta
, SearchGui::Green
));
588 val
= -search( ply
+1, sdepth
, false, -beta
, -beta
+NULL_SOLIDITY_MARGIN
, false);
589 GUI2(notify_value(ply
, val
, DIFF_NODES
, SearchGui::Bold
));
590 board
.undo_null_move(s
->save_buf
);
596 #if NULL_SOLIDITY_MARGIN > 1
597 if(depth
<= 3*PLY
&& val
> beta
- NULL_SOLIDITY_MARGIN
)
601 if(val
< -WORST_MATE
)
602 s
->null_threat_dangerous
= true;
605 if(val
<alpha
-100 && /* we are facing a threat*/
606 stack
[ply
+1].best_move
!= -1) /* be sure we aren't reading random memory */
608 /* ok, officially the array stack[ply+1].moves has already
609 been deallocated, but who cares :) */
610 s
->threat
= stack
[ply
+1].moves
[stack
[ply
+1].best_move
];
613 /* Botvinnik-Markoff extension!!! */
614 if(!extended
&& ply
>=3 && (s
->threat
== stack
[ply
-2].threat
) )
627 /*******************************************************************************
628 Now generate the legal moves and look for a check/stalemate
629 *******************************************************************************/
631 /* generate all the legal moves */
632 s
->moves
= &mv_stack
[mv_stack_top
];
633 s
->num_moves
= board
.find_moves(s
->moves
);
634 mv_stack_top
+= s
->num_moves
;
635 s
->under_check
= board
.under_check
;
637 pluto1
= stack
[ply
-1].best_move
>=0 ? PLUTO1(stack
[ply
-1].moves
[stack
[ply
-1].best_move
]) : -1;
638 pluto2
= (ply
>=2 && stack
[ply
-1].best_move
>=0 && stack
[ply
-2].best_move
>=0) ?
639 PLUTO2(stack
[ply
-2].moves
[stack
[ply
-2].best_move
], stack
[ply
-1].moves
[stack
[ply
-1].best_move
]) : -1;
641 if(s
->under_check
==2) /* double check */
646 else if(s
->under_check
) /* simple check */
649 if(stack
[ply
-1].curr_move
>=0 &&
650 !board
.pins
[stack
[ply
-1].moves
[ /* last moved piece is not attacking the king */
651 stack
[ply
-1].curr_move
].to
]) /* so this is a discover check */
658 /* return now if the positon is terminal */
663 /* while mating, sacrify as much as possible :) */
664 int mt
= IS_WHITE(board
.other_color
) ? 5 : -1;
665 int16_t matval
= Board::simple_values
[PAWN
]*board
.mat_tracking
[mt
+PAWN
].count
+
666 Board::simple_values
[KNIGHT
]*board
.mat_tracking
[mt
+KNIGHT
].count
+
667 Board::simple_values
[BISHOP
]*board
.mat_tracking
[mt
+BISHOP
].count
+
668 Board::simple_values
[QUEEN
]*board
.mat_tracking
[mt
+QUEEN
].count
;
669 best
= alpha
= beta
= -INF
+ ply
*100 + matval
;
672 best
= alpha
= beta
= 0;
676 /* single-reply extension */
677 if(s
->num_moves
== 1 && !extended
)
682 else if(s
->num_moves
<= 3 && !extended
)
688 /*******************************************************************************
690 First comes the move from the hashtable, if avalable.
691 The remaining moves are sorted with a heuristic that keeps in account
692 the history heuristic (ie the moves that previously caused an alpha
693 cutoff), a MVV/LVA bonus value and a small bonus for moves that go
695 *******************************************************************************/
697 /* convert the move we got from the hash to the move structure */
700 best_mv_hash
= board
.uncompress_move(cbest_mv_hash
);
701 /* if it happened that the move we got from the hashtable
702 is not valid, simply no move will get the high
703 heuristic bonus value */
705 #if INTERNAL_ITERATIVE_DEEPENING
706 else if(base_depth
>3*PLY
&& pv
) /* don't do it only on the pv, or it will be useless :) */
709 GUI1(notify(&board
, Move::None(), ply
, base_depth
-2*PLY
, -INF
, alpha
, beta
, SearchGui::Blue
));
710 int val
= search(ply
+1, base_depth
-2*PLY
, true, alpha
, beta
, expect_allbad
);
711 GUI2(search_gui
->notify_value(ply
, val
, DIFF_NODES
, 0));
713 HashEntry
*h2
= probe_hash( board
.hash
);
714 if(h2
&& h2
->best_mv
)
716 cbest_mv_hash
= h2
->best_mv
;
717 best_mv_hash
= board
.uncompress_move(cbest_mv_hash
);
720 #endif //INTERNAL_ITERATIVE_DEEPENING
722 /* for each move calculate the heuristic goodness value */
723 #if DEBUG && TRACK_ATTACKS
724 board
.check_attacks();
727 Move
*prev
= (stack
[ply
-1].curr_move
>=0) ? &stack
[ply
-1].moves
[stack
[ply
-1].curr_move
] : NULL
;
729 moves_quiescence_heuristic( s
->moves
, s
->num_moves
, best_mv_hash
,
730 best
, alpha
, beta
, base_depth
, prev
);
734 moves_heuristic( s
->moves
, s
->num_moves
, pv
, ply
, base_depth
,
735 best_mv_hash
, quiesce
, prev
, &overall_ext
, pluto1
, pluto2
);
736 depth
+= overall_ext
;
739 #if DEBUG && TRACK_ATTACKS
740 board
.check_attacks();
743 /* if quiesce rip-off the "non-critical" moves */
747 for(int i
=0;i
<s
->num_moves
;i
++)
748 if(s
->moves
[i
].val
>0)
749 s
->moves
[n
++] = s
->moves
[i
];
750 mv_stack_top
-= s
->num_moves
-n
;
753 no_good_moves
= true;
756 /* Don't do it now, do it incrementally */
757 //sort_moves( s->moves, s->num_moves );
760 #if EARLY_TRANSP_CUTOFF
761 /*******************************************************************************
762 Try to get an early beta cutoff using the hash table values
763 of the following moves, and improve alpha too.
764 Try on the first 6 value of the ordered moves (argh, looking into the
765 hashtable is very expensive because of the cache!!!!!!!!)
766 *******************************************************************************/
770 HashKey hk
= board
.move_hash(s
->moves
[0]);
771 for(int i
=1;i
<s
->num_moves
;i
++)
773 engine
->prefetch_hash(hk
);
774 HashKey newhk
= board
.move_hash(s
->moves
[i
]);
775 HashEntry
*h2
= engine
->probe_hash( hk
);
778 if(h2
&& h2
->depth
>= depth
-PLY
)
785 alpha
= MAX(alpha
, (int16_t)-h2
->up
);
789 HashEntry
*h2
= engine
->probe_hash( hk
);
790 if(h2
&& h2
->depth
>= depth
-PLY
)
797 alpha
= MAX(alpha
, (int16_t)-h2
->up
);
800 #endif //EARLY_TRANSP_CUTOFF
802 /*******************************************************************************
803 It is now time to loop all the successor moves and search recursively.
804 *******************************************************************************/
807 /* calcluate the evaluation (required by fitility pruning) */
808 position_val
= quiesce
? best
: board
.dummy_evaluate(); //evaluate( st_computer_color, -INF, INF);
811 for(int i
=0;i
<s
->num_moves
;i
++)
814 int sdepth
= depth
-100;
816 /* sort moves incrementally, in the hope of a beta cut */
817 engine
->incremental_sort_moves(s
->moves
+i
, s
->num_moves
-i
);
819 /* extensions calculated during the heuristic sort */
820 sdepth
+= s
->moves
[i
].extend
;
823 /* futility pruning, it is done only if we are not under check
824 and the move is not a "critical" move */
825 if(depth
>0 && depth
<=2*PLY
&& !s
->under_check
&& s
->moves
[i
].val
< 28000)
827 static const int mavala
[] = { 0, 500, 325, 975, 325, 100, 0 };
829 int16_t fmargin
= (depth
<= PLY
? 420 : 720);
830 int16_t fval
= position_val
+ mavala
[PIECE_OF(s
->moves
[i
].capture
)];
831 if(fval
< alpha
-fmargin
)
838 int mx
= CAPT_INDEX(s
->moves
[i
]);
840 /* collect history statistics */
841 if(!s
->moves
[i
].capture
&&
842 !(s
->moves
[i
].flags
>=PROMOTE_FIRST
) )
844 int ix
= HISTORY_INDEX(s
->moves
[i
]);
845 if(history_tot
[ix
] > 1024)
847 history_tot
[ix
] = history_tot
[ix
]*7/8;
848 history_hit
[ix
] = history_hit
[ix
]*7/8;
850 history_tot
[ix
] += quiesce
? 8 : 16;
853 if(pluto1
!=-1 && !s
->moves
[i
].capture
&&
854 !(s
->moves
[i
].flags
>=PROMOTE_FIRST
))
856 int ix
= FAST_PLUTO(pluto1
, mx
);
857 if(pluto_tot
[ix
] > 256)
859 pluto_tot
[ix
] = pluto_tot
[ix
]*7/8;
860 pluto_hit
[ix
] = pluto_hit
[ix
]*7/8;
862 pluto_tot
[ix
] += quiesce
? 8 : 16;
865 if(pluto2
!=-1 && !s
->moves
[i
].capture
&&
866 !(s
->moves
[i
].flags
>=PROMOTE_FIRST
))
868 int ix
= FAST_PLUTO(pluto2
, mx
);
869 if(pluto2_tot
[ix
] > 128)
871 pluto2_tot
[ix
] = pluto2_tot
[ix
]*7/8;
872 pluto2_hit
[ix
] = pluto2_hit
[ix
]*7/8;
874 pluto2_tot
[ix
] += quiesce
? 8 : 16;
878 //Set data for pawn-strike
880 if(!quiesce
&& PIECE_OF(board
.data
[s
->moves
[i
].from
]) == PAWN
&& s
->moves
[i
].val
== 27000) //FIXME, UGLY
882 stack
[ply
].escape_from
[1] = s
->moves
[i
].to
+ Board::up_dir
[IS_WHITE(board
.color_to_move
)] + RIGHT
;
883 if(OUT_OF_BOARD(stack
[ply
].escape_from
[1]) || !IS_OF_COLOR(board
.data
[stack
[ply
].escape_from
[1]], board
.other_color
)
884 || PIECE_OF(board
.data
[stack
[ply
].escape_from
[1]])==PAWN
)
885 stack
[ply
].escape_from
[1] = INVALID
;
886 stack
[ply
].escape_from
[2] = s
->moves
[i
].to
+ Board::up_dir
[IS_WHITE(board
.color_to_move
)] + LEFT
;
887 if(OUT_OF_BOARD(stack
[ply
].escape_from
[2]) || !IS_OF_COLOR(board
.data
[stack
[ply
].escape_from
[2]], board
.other_color
)
888 || PIECE_OF(board
.data
[stack
[ply
].escape_from
[2]])==PAWN
)
889 stack
[ply
].escape_from
[2] = INVALID
;
893 stack
[ply
].escape_from
[1] = stack
[ply
].escape_from
[2] = INVALID
;
897 board
.do_move(s
->moves
[i
], s
->save_buf
);
902 if(base_depth
> 0 && sdepth
<= 0)
904 STAT(quiesce_called
);
905 q
= stat_quiesce_nodes
;
909 #if NEGA_SCOUT /* use negascout, (null window search for nodes that are not in the pv) */
910 if(i
== 0 && !expect_allbad
)
912 if(depth
>=0 && pv
&& mv_pv_top
>=ply
)
914 mv_pv
[ply
] = s
->moves
[i
];
918 GUI1(notify(&board
, s
->moves
[i
], ply
, sdepth
, s
->moves
[i
].val
, alpha
, beta
, SearchGui::Bold
));
919 val
= -search( ply
+1, sdepth
, pv
, -beta
, -alpha
, !pv
);
920 GUI2(notify_value(ply
, val
, DIFF_NODES
, 0));
925 bool red_fuck
= false;
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
->null_threat_dangerous
934 && s
->moves
[i
].val
<28000 && (s
->moves
[i
].val
<(sdepth
<=PLY
? 650 : 450)) )
936 int rdepth
= depth
- 2*PLY
;
937 //sdepth - PLY; //(s->moves[i].val<250 ? 2*PLY : PLY) - s->moves[i].extend;
938 GUI1(notify(&board
, s
->moves
[i
], ply
, rdepth
, s
->moves
[i
].val
, alpha
, alpha
+1, SearchGui::Italic
|SearchGui::Gray
));
939 val
= -search( ply
+1, rdepth
, false, -alpha
-1, -alpha
, false );
940 GUI2(notify_value(ply
, val
, DIFF_NODES
, val
>alpha
? SearchGui::Red
: 0));
942 goto skip_search
; /* reduced search was effective */
946 GUI1(notify(&board
, s
->moves
[i
], ply
, sdepth
, s
->moves
[i
].val
, alpha
, alpha
+1, 0 ));
947 val
= -search( ply
+1, sdepth
, false, -alpha
-1, -alpha
, red_fuck
);
948 GUI2(notify_value(ply
, val
, DIFF_NODES
, val
>alpha
? SearchGui::Red
: 0));
950 if((val
>alpha
) && pv
)
952 if(depth
>=0 && mv_pv_top
>=ply
)
954 mv_pv
[ply
] = s
->moves
[i
];
958 GUI1(notify(&board
, s
->moves
[i
], ply
, sdepth
, -INF
, alpha
, beta
, SearchGui::Bold
));
959 val
= -search( ply
+1, sdepth
, true, -beta
, -alpha
, false );
960 GUI2(notify_value(ply
, val
, DIFF_NODES
, val
>beta
? SearchGui::Red
: 0));
966 if(base_depth
> 0 && sdepth
<= 0)
968 q
= stat_quiesce_nodes
-q
;
969 if(q
> stat_max_quiesce_nodes
)
971 stat_max_quiesce_nodes
= q
;
972 max_quiesce_board
= board
;
977 #if NEGA_SCOUT && LATE_MOVE_REDUCTION
980 board
.undo_move(s
->moves
[i
], s
->save_buf
);
982 /* update the current best value and check for and alpha cut */
993 /* alpha improvement! */
1002 if(!expect_allbad
|| best
>= beta
)
1004 /* collect statistics for the history */
1005 if(/*best >= beta &&*/ (best_mv_found
!=-1) &&
1006 !s
->moves
[best_mv_found
].capture
&&
1007 !(s
->moves
[best_mv_found
].flags
>=PROMOTE_FIRST
) )
1008 history_hit
[HISTORY_INDEX(s
->moves
[best_mv_found
])] += quiesce
? 8 : 16;
1010 int mx
= CAPT_INDEX(s
->moves
[best_mv_found
]);
1011 if(pluto1
!=-1 && !s
->moves
[best_mv_found
].capture
&&
1012 !(s
->moves
[best_mv_found
].flags
>=PROMOTE_FIRST
))
1014 int ix
= FAST_PLUTO(pluto1
, mx
);
1015 pluto_hit
[ix
] += quiesce
? 8 : 16;
1018 if(pluto2
!=-1 && !s
->moves
[best_mv_found
].capture
&&
1019 !(s
->moves
[best_mv_found
].flags
>=PROMOTE_FIRST
))
1021 int ix
= FAST_PLUTO(pluto2
, mx
);
1022 pluto2_hit
[ix
] += quiesce
? 8 : 16;
1027 mv_stack_top
-= s
->num_moves
; /* free the moves we allocated */
1029 /* this is a null move, save what the threat is */
1030 if(stack
[ply
-1].curr_move
== -1 && best_mv_found
>= 0)
1031 stack
[ply
-1].null_threat
= s
->moves
[best_mv_found
];
1033 /* if we found a best move searching, that move will be saved.
1034 if we did no search (ie quiescence), save the old hash value,
1035 or -1 if no hash entry had been found */
1036 int bestmv
= cbest_mv_hash
;
1037 if(best_mv_found
>= 0)
1038 bestmv
= board
.compress_move(s
->moves
[best_mv_found
]);
1040 /* write the value in the hash, with the index of the best move */
1041 engine
->write_hash( board
.hash
,
1042 best
> orig_alpha
? MIN(best
, beta
) : lower_bound
,
1043 best
< beta
? best
: +INF
,
1044 MAX(base_depth
,-500), bestmv
, no_good_moves
);
1045 GUI(notify_hash(ply
, best
> orig_alpha
? MIN(best
, beta
) : lower_bound
, best
< beta
? best
: +INF
,
1046 MAX(base_depth
,-500), alpha
, beta
, bestmv
? board
.uncompress_move(bestmv
) : Move::None(), true,
1047 SearchGui::Bold
| SearchGui::Magenta
) );
1052 uint16_t SearchRoot::pluto_tot
[PLUTO_SIZE
];
1053 uint16_t SearchRoot::pluto_hit
[PLUTO_SIZE
];
1054 uint16_t SearchRoot::pluto2_tot
[PLUTO_SIZE
];
1055 uint16_t SearchRoot::pluto2_hit
[PLUTO_SIZE
];
1056 uint16_t SearchRoot::history_tot
[HISTORY_SIZE
];
1057 uint16_t SearchRoot::history_hit
[HISTORY_SIZE
];
1059 SearchRoot::SearchRoot(Engine
* e
, const Board
& b
)
1062 , search_gui(e
->search_gui
)
1066 engine
->current_root
= this;
1069 SearchRoot::~SearchRoot()
1071 engine
->current_root
= NULL
;
1074 Move
Engine::find_best_move()
1077 IFGUI(Engine
*engine
= this);
1078 int num_mate_hits
= 0;
1079 SearchRoot
root(this, board
);
1080 SearchRoot::SearchStack
*s
= &root
.stack
[0];
1082 /* initialize the root node */
1083 root
.base_depth
= PLY
;
1086 s
->null_threat
= Move::FromInt(0);
1087 s
->null_threat_dangerous
= false;
1088 s
->moves
= root
.mv_stack
;
1089 s
->num_moves
= root
.mv_stack_top
= root
.board
.find_moves(s
->moves
);
1091 s
->escape_from
[1] = s
->escape_from
[2] = INVALID
;
1092 #endif //PAWN_STRIKE
1096 /* calculate how much time we will think*/
1097 start_think_time
= current_time();
1098 if(analysis_limit
== TIME_LIMIT
)
1100 if(board
.color_to_move
== st_computer_color
)
1102 else /* pondering? analysing? */
1103 time_best_csec
= 99999999;
1104 max_think_time
= start_think_time
+ time_best_csec
- 2;
1107 /* to print the analysis */
1109 output("\tply\tscore\ttime\tnodes\tpv\n");
1111 /* return immediatly if the move is forced. */
1115 output("\t0\t0\t0\t0\t%s (only move)\n", board
.move_to_alg(MoveStr().data(), s
->moves
[0]));
1119 /* probe the play lines */
1120 if(eng_status
== PLAYING
&& st_computer_color
== board
.color_to_move
)
1122 Move retv
= probe_lines(&root
.board
);
1127 output("\t0\t0\t0\t0\t%s (selected line)\n", board
.move_to_alg(MoveStr().data(), retv
));
1132 /* probe the book */
1133 Move bookmove
= probe_book(&root
.board
);
1134 if(bookmove
.valid())
1137 for(int i
=0;i
<s
->num_moves
++;i
++)
1138 if(bookmove
== s
->moves
[i
])
1140 output("Error!!! invalid move in the book!!!\n");
1144 IFGUI(reset_hash()); //Try to be deterministic
1145 processed_nodes
= 0;
1149 memset( root
.history_tot
, 0, HISTORY_SIZE
*sizeof(uint16_t));
1150 memset( root
.history_hit
, 0, HISTORY_SIZE
*sizeof(uint16_t));
1151 memset( root
.pluto_tot
, 0, PLUTO_SIZE
*sizeof(uint16_t));
1152 memset( root
.pluto_hit
, 0, PLUTO_SIZE
*sizeof(uint16_t));
1153 memset( root
.pluto2_tot
, 0, PLUTO_SIZE
*sizeof(uint16_t));
1154 memset( root
.pluto2_hit
, 0, PLUTO_SIZE
*sizeof(uint16_t));
1159 /* set the back jump for the quick thinking exit */
1164 /* do the iterative deepening thing. */
1167 int16_t alpha
= num_mate_hits
? -INF
: -WORST_MATE
;
1168 int16_t beta
= num_mate_hits
? INF
: WORST_MATE
;
1170 GUI(new_root_level(root
.base_depth
));
1172 /* for each move call the alpha-beta search function */
1173 for(int i
=0;i
<s
->num_moves
;i
++)
1176 root
.board
.do_move(s
->moves
[i
], s
->save_buf
);
1180 root
.mv_pv
[0] = s
->moves
[i
];
1183 GUI1(notify(&root
.board
, s
->moves
[i
], 0, root
.base_depth
-PLY
, s
->moves
[i
].val
, alpha
, beta
, SearchGui::Bold
));
1184 s
->moves
[i
].val
= -root
.search( 1, root
.base_depth
-PLY
, true, -beta
, -alpha
, false );
1185 GUI2(notify_value(0, s
->moves
[i
].val
, DIFF_NODES
, 0));
1190 GUI1(notify(&root
.board
, s
->moves
[i
], 0, root
.base_depth
-PLY
, s
->moves
[i
].val
, alpha
, alpha
+1, 0 ));
1191 s
->moves
[i
].val
= -root
.search( 1, root
.base_depth
-PLY
, false, -alpha
-1, -alpha
, false );
1192 GUI2(notify_value(0, s
->moves
[i
].val
, DIFF_NODES
, s
->moves
[i
].val
>alpha
? SearchGui::Red
: 0));
1194 if(s
->moves
[i
].val
> alpha
)
1196 root
.mv_pv
[0] = s
->moves
[i
];
1199 GUI1(notify(&root
.board
, s
->moves
[i
], 0, root
.base_depth
-PLY
, -INF
, alpha
, beta
, SearchGui::Bold
));
1200 s
->moves
[i
].val
= -root
.search( 1, root
.base_depth
-PLY
, true, -beta
, -alpha
, false );
1201 GUI2(notify_value(0, s
->moves
[i
].val
, DIFF_NODES
, 0));
1205 root
.board
.undo_move(s
->moves
[i
], s
->save_buf
);
1208 if(s
->moves
[i
].val
> alpha
)
1210 alpha
= s
->moves
[i
].val
;
1212 Move tmp
= s
->moves
[i
];
1213 for(int q
=i
-1;q
>=0;q
--)
1214 s
->moves
[q
+1] = s
->moves
[q
];
1217 /* this move caused an alpha cut, so print the new line */
1218 if( post
/*&& processed_nodes>100000*/)
1220 output("\t%d\t%d\t%d\t%llu\t",
1221 root
.base_depth
/PLY
,
1223 current_time() - start_think_time
,
1224 (unsigned long long)processed_nodes
);
1225 print_moves(root
.mv_pv
, 1/*root.mv_pv_top*/, true, true);
1230 /* print the result of the analysis at this depth */
1231 if( post
/*&& processed_nodes>100000*/)
1233 output("\t%d\t%d\t%d\t%llu\t",
1234 root
.base_depth
/PLY
,
1236 current_time() - start_think_time
,
1237 (unsigned long long)processed_nodes
);
1238 print_moves(root
.mv_pv
, 1/*root.mv_pv_top*/, true, true);
1242 if( root
.base_depth
>= 50*PLY
)
1245 /* return in case of fixed depth search */
1246 if( eng_status
== PLAYING
&& st_computer_color
== board
.color_to_move
&&
1247 analysis_limit
== DEPTH_LIMIT
&& root
.base_depth
== st_depth
*PLY
)
1250 /* return if 3/5 of time is gone (we can't search another ply anyway) */
1251 if( eng_status
== PLAYING
&& st_computer_color
== board
.color_to_move
&&
1252 analysis_limit
== TIME_LIMIT
&&
1253 (current_time()-start_think_time
) >= (time_best_csec
*3/5) )
1256 /* if a checkmate was detected return immediately */
1257 if( ABS(alpha
) > WORST_MATE
)
1260 if(num_mate_hits
>= 5)
1264 root
.base_depth
+= PLY
;
1272 output("#max quiesce board: %s [%d %d]\n", max_quiesce_board
.to_fen(BigStr().data()),
1273 max_quiesce_alpha
, max_quiesce_beta
);