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 GUI(notify_msg(ply
, "Searching...", 0))
518 /*******************************************************************************
519 Test if we are under check, and if so extend search
520 *******************************************************************************/
522 s
->under_check
= board
.under_attack(board
.king_pos
[IS_WHITE(board
.color_to_move
)],
525 /*******************************************************************************
526 If it is time to quiesce, evaluate and test if we can exit
527 immediately with a beta cut-off (try first a rough eval - delta)
528 *******************************************************************************/
529 quiesce
= ((!s
->under_check
) && (depth
<=0)) || (ply
> 70);
534 if(quiesce
&& depth
>=-PLY
)
537 Move
*mv
= mv_stack
+ mv_stack_top
;
538 board
.do_null_move();
539 num_mv
= board
.find_moves(mv
);
540 uint8_t pup
= INVALID
;
542 for(int i
=0;i
<num_mv
;i
++)
544 if(!mv
[i
].capture
|| PIECE_OF(mv
[i
].capture
)==PAWN
)
546 if(mv
[i
].to
!= pup
&& board
.move_see_val(mv
[i
])>0)
556 board
.undo_null_move();
560 if(quiesce
&& (best
<= -WORST_MATE
+MAX_PV
|| ply
>70) )
562 best
= board
.evaluate(engine
->st_computer_color
, alpha
, beta
);
563 lower_bound
= best
; //we have at the very least "best" as lower bound now.
564 GUI(notify_eval(ply
, best
, alpha
, beta
, best
>=beta
? SearchGui::Blue
|SearchGui::Bold
: SearchGui::Blue
));
566 alpha
= MAX(alpha
, best
);
574 if(quiesce
&& h
&& h
->no_good_moves
)
578 /*******************************************************************************
580 *******************************************************************************/
581 if(!expect_allbad
&& !pv
&& !s
->under_check
&& (stack
[ply
-1].curr_move
!= -1)
582 && depth
>= 2*PLY
&& beta
<WORST_MATE
&& null_move_ok())
585 int sdepth
= (depth
>= 5*PLY
) ? (depth
-4*PLY
) : depth
-3*PLY
;
588 board
.do_null_move(s
->save_buf
);
589 GUI1(notify(&board
, Move::None(), ply
, sdepth
, -INF
, beta
-NULL_SOLIDITY_MARGIN
, beta
, SearchGui::Green
));
590 val
= -search( ply
+1, sdepth
, false, -beta
, -beta
+NULL_SOLIDITY_MARGIN
, false);
591 GUI2(notify_value(ply
, val
, DIFF_NODES
, SearchGui::Bold
));
592 board
.undo_null_move(s
->save_buf
);
598 #if NULL_SOLIDITY_MARGIN > 1
599 if(depth
<= 3*PLY
&& val
> beta
- NULL_SOLIDITY_MARGIN
)
603 if(val
< -WORST_MATE
)
604 s
->null_threat_dangerous
= true;
607 if(val
<alpha
-100 && /* we are facing a threat*/
608 stack
[ply
+1].best_move
!= -1) /* be sure we aren't reading random memory */
610 /* ok, officially the array stack[ply+1].moves has already
611 been deallocated, but who cares :) */
612 s
->threat
= stack
[ply
+1].moves
[stack
[ply
+1].best_move
];
615 /* Botvinnik-Markoff extension!!! */
616 if(!extended
&& ply
>=3 && (s
->threat
== stack
[ply
-2].threat
) )
629 /*******************************************************************************
630 Now generate the legal moves and look for a check/stalemate
631 *******************************************************************************/
633 /* generate all the legal moves */
634 s
->moves
= &mv_stack
[mv_stack_top
];
635 s
->num_moves
= board
.find_moves(s
->moves
);
636 mv_stack_top
+= s
->num_moves
;
637 s
->under_check
= board
.under_check
;
639 pluto1
= stack
[ply
-1].best_move
>=0 ? PLUTO1(stack
[ply
-1].moves
[stack
[ply
-1].best_move
]) : -1;
640 pluto2
= (ply
>=2 && stack
[ply
-1].best_move
>=0 && stack
[ply
-2].best_move
>=0) ?
641 PLUTO2(stack
[ply
-2].moves
[stack
[ply
-2].best_move
], stack
[ply
-1].moves
[stack
[ply
-1].best_move
]) : -1;
643 if(s
->under_check
==2) /* double check */
648 else if(s
->under_check
) /* simple check */
651 if(stack
[ply
-1].curr_move
>=0 &&
652 !board
.pins
[stack
[ply
-1].moves
[ /* last moved piece is not attacking the king */
653 stack
[ply
-1].curr_move
].to
]) /* so this is a discover check */
660 /* return now if the positon is terminal */
665 /* while mating, sacrify as much as possible :) */
666 int mt
= IS_WHITE(board
.other_color
) ? 5 : -1;
667 int16_t matval
= Board::simple_values
[PAWN
]*board
.mat_tracking
[mt
+PAWN
].count
+
668 Board::simple_values
[KNIGHT
]*board
.mat_tracking
[mt
+KNIGHT
].count
+
669 Board::simple_values
[BISHOP
]*board
.mat_tracking
[mt
+BISHOP
].count
+
670 Board::simple_values
[QUEEN
]*board
.mat_tracking
[mt
+QUEEN
].count
;
671 best
= alpha
= beta
= -INF
+ ply
*100 + matval
;
674 best
= alpha
= beta
= 0;
678 /* single-reply extension */
679 if(s
->num_moves
== 1 && !extended
)
684 else if(s
->num_moves
<= 3 && !extended
)
690 /*******************************************************************************
692 First comes the move from the hashtable, if avalable.
693 The remaining moves are sorted with a heuristic that keeps in account
694 the history heuristic (ie the moves that previously caused an alpha
695 cutoff), a MVV/LVA bonus value and a small bonus for moves that go
697 *******************************************************************************/
699 /* convert the move we got from the hash to the move structure */
702 best_mv_hash
= board
.uncompress_move(cbest_mv_hash
);
703 /* if it happened that the move we got from the hashtable
704 is not valid, simply no move will get the high
705 heuristic bonus value */
707 #if INTERNAL_ITERATIVE_DEEPENING
708 else if(base_depth
>3*PLY
&& pv
) /* don't do it only on the pv, or it will be useless :) */
712 GUI1(notify(&board
, Move::None(), ply
, base_depth
-2*PLY
, -INF
, alpha
, beta
, SearchGui::Blue
));
713 val
= search(ply
+1, base_depth
-2*PLY
, true, alpha
, beta
, expect_allbad
);
714 GUI2(notify_value(ply
, val
, DIFF_NODES
, 0));
716 HashEntry
*h2
= probe_hash( board
.hash
);
717 if(h2
&& h2
->best_mv
)
719 cbest_mv_hash
= h2
->best_mv
;
720 best_mv_hash
= board
.uncompress_move(cbest_mv_hash
);
723 #endif //INTERNAL_ITERATIVE_DEEPENING
725 /* for each move calculate the heuristic goodness value */
726 #if DEBUG && TRACK_ATTACKS
727 board
.check_attacks();
730 Move
*prev
= (stack
[ply
-1].curr_move
>=0) ? &stack
[ply
-1].moves
[stack
[ply
-1].curr_move
] : NULL
;
732 moves_quiescence_heuristic( s
->moves
, s
->num_moves
, best_mv_hash
,
733 best
, alpha
, beta
, base_depth
, prev
);
737 moves_heuristic( s
->moves
, s
->num_moves
, pv
, ply
, base_depth
,
738 best_mv_hash
, quiesce
, prev
, &overall_ext
, pluto1
, pluto2
);
739 depth
+= overall_ext
;
742 #if DEBUG && TRACK_ATTACKS
743 board
.check_attacks();
746 /* if quiesce rip-off the "non-critical" moves */
750 for(int i
=0;i
<s
->num_moves
;i
++)
751 if(s
->moves
[i
].val
>0)
752 s
->moves
[n
++] = s
->moves
[i
];
753 mv_stack_top
-= s
->num_moves
-n
;
756 no_good_moves
= true;
759 /* Don't do it now, do it incrementally */
760 //sort_moves( s->moves, s->num_moves );
763 #if EARLY_TRANSP_CUTOFF
764 /*******************************************************************************
765 Try to get an early beta cutoff using the hash table values
766 of the following moves, and improve alpha too.
767 Try on the first 6 value of the ordered moves (argh, looking into the
768 hashtable is very expensive because of the cache!!!!!!!!)
769 *******************************************************************************/
773 HashKey hk
= board
.move_hash(s
->moves
[0]);
774 for(int i
=1;i
<s
->num_moves
;i
++)
776 engine
->prefetch_hash(hk
);
777 HashKey newhk
= board
.move_hash(s
->moves
[i
]);
778 HashEntry
*h2
= engine
->probe_hash( hk
);
781 if(h2
&& h2
->depth
>= depth
-PLY
)
788 alpha
= MAX(alpha
, (int16_t)-h2
->up
);
792 HashEntry
*h2
= engine
->probe_hash( hk
);
793 if(h2
&& h2
->depth
>= depth
-PLY
)
800 alpha
= MAX(alpha
, (int16_t)-h2
->up
);
803 #endif //EARLY_TRANSP_CUTOFF
805 /*******************************************************************************
806 It is now time to loop all the successor moves and search recursively.
807 *******************************************************************************/
810 /* calcluate the evaluation (required by fitility pruning) */
811 position_val
= quiesce
? best
: board
.dummy_evaluate(); //evaluate( st_computer_color, -INF, INF);
814 for(int i
=0;i
<s
->num_moves
;i
++)
817 int sdepth
= depth
-100;
819 /* sort moves incrementally, in the hope of a beta cut */
820 engine
->incremental_sort_moves(s
->moves
+i
, s
->num_moves
-i
);
822 /* extensions calculated during the heuristic sort */
823 sdepth
+= s
->moves
[i
].extend
;
826 /* futility pruning, it is done only if we are not under check
827 and the move is not a "critical" move */
828 if(depth
>0 && depth
<=2*PLY
&& !s
->under_check
&& s
->moves
[i
].val
< 28000)
830 static const int mavala
[] = { 0, 500, 325, 975, 325, 100, 0 };
832 int16_t fmargin
= (depth
<= PLY
? 420 : 720);
833 int16_t fval
= position_val
+ mavala
[PIECE_OF(s
->moves
[i
].capture
)];
834 if(fval
< alpha
-fmargin
)
841 int mx
= CAPT_INDEX(s
->moves
[i
]);
843 /* collect history statistics */
844 if(!s
->moves
[i
].capture
&&
845 !(s
->moves
[i
].flags
>=PROMOTE_FIRST
) )
847 int ix
= HISTORY_INDEX(s
->moves
[i
]);
848 if(history_tot
[ix
] > 1024)
850 history_tot
[ix
] = history_tot
[ix
]*7/8;
851 history_hit
[ix
] = history_hit
[ix
]*7/8;
853 history_tot
[ix
] += quiesce
? 8 : 16;
856 if(pluto1
!=-1 && !s
->moves
[i
].capture
&&
857 !(s
->moves
[i
].flags
>=PROMOTE_FIRST
))
859 int ix
= FAST_PLUTO(pluto1
, mx
);
860 if(pluto_tot
[ix
] > 256)
862 pluto_tot
[ix
] = pluto_tot
[ix
]*7/8;
863 pluto_hit
[ix
] = pluto_hit
[ix
]*7/8;
865 pluto_tot
[ix
] += quiesce
? 8 : 16;
868 if(pluto2
!=-1 && !s
->moves
[i
].capture
&&
869 !(s
->moves
[i
].flags
>=PROMOTE_FIRST
))
871 int ix
= FAST_PLUTO(pluto2
, mx
);
872 if(pluto2_tot
[ix
] > 128)
874 pluto2_tot
[ix
] = pluto2_tot
[ix
]*7/8;
875 pluto2_hit
[ix
] = pluto2_hit
[ix
]*7/8;
877 pluto2_tot
[ix
] += quiesce
? 8 : 16;
881 //Set data for pawn-strike
883 if(!quiesce
&& PIECE_OF(board
.data
[s
->moves
[i
].from
]) == PAWN
&& s
->moves
[i
].val
== 27000) //FIXME, UGLY
885 stack
[ply
].escape_from
[1] = s
->moves
[i
].to
+ Board::up_dir
[IS_WHITE(board
.color_to_move
)] + RIGHT
;
886 if(OUT_OF_BOARD(stack
[ply
].escape_from
[1]) || !IS_OF_COLOR(board
.data
[stack
[ply
].escape_from
[1]], board
.other_color
)
887 || PIECE_OF(board
.data
[stack
[ply
].escape_from
[1]])==PAWN
)
888 stack
[ply
].escape_from
[1] = INVALID
;
889 stack
[ply
].escape_from
[2] = s
->moves
[i
].to
+ Board::up_dir
[IS_WHITE(board
.color_to_move
)] + LEFT
;
890 if(OUT_OF_BOARD(stack
[ply
].escape_from
[2]) || !IS_OF_COLOR(board
.data
[stack
[ply
].escape_from
[2]], board
.other_color
)
891 || PIECE_OF(board
.data
[stack
[ply
].escape_from
[2]])==PAWN
)
892 stack
[ply
].escape_from
[2] = INVALID
;
896 stack
[ply
].escape_from
[1] = stack
[ply
].escape_from
[2] = INVALID
;
900 board
.do_move(s
->moves
[i
], s
->save_buf
);
905 if(base_depth
> 0 && sdepth
<= 0)
907 STAT(quiesce_called
);
908 q
= stat_quiesce_nodes
;
912 #if NEGA_SCOUT /* use negascout, (null window search for nodes that are not in the pv) */
913 if(i
== 0 && !expect_allbad
)
915 if(depth
>=0 && pv
&& mv_pv_top
>=ply
)
917 mv_pv
[ply
] = s
->moves
[i
];
921 GUI1(notify(&board
, s
->moves
[i
], ply
, sdepth
, s
->moves
[i
].val
, alpha
, beta
, SearchGui::Bold
));
922 val
= -search( ply
+1, sdepth
, pv
, -beta
, -alpha
, !pv
);
923 GUI2(notify_value(ply
, val
, DIFF_NODES
, 0));
928 bool red_fuck
= false;
929 #if LATE_MOVE_REDUCTION
930 /* history pruning, if this is not a "critical" move and the failhigh
931 stats are too low, try a reduced depth search (if it returns >alpha,
932 re-do the full depth search) */
933 // if((sdepth>0) && !s->under_check && depth<=3*PLY && s->moves[i].val<28000 &&
934 // (history_hit[HISTORY_INDEX(s->moves[i])]+1)*3
935 // < (history_tot[HISTORY_INDEX(s->moves[i])]+1))
936 if( (sdepth
>0) && !s
->under_check
&& !s
->null_threat_dangerous
937 && s
->moves
[i
].val
<28000 && (s
->moves
[i
].val
<(sdepth
<=PLY
? 650 : 450)) )
939 int rdepth
= depth
- 2*PLY
;
940 //sdepth - PLY; //(s->moves[i].val<250 ? 2*PLY : PLY) - s->moves[i].extend;
941 GUI1(notify(&board
, s
->moves
[i
], ply
, rdepth
, s
->moves
[i
].val
, alpha
, alpha
+1, SearchGui::Italic
|SearchGui::Gray
));
942 val
= -search( ply
+1, rdepth
, false, -alpha
-1, -alpha
, false );
943 GUI2(notify_value(ply
, val
, DIFF_NODES
, val
>alpha
? SearchGui::Red
: 0));
945 goto skip_search
; /* reduced search was effective */
949 GUI1(notify(&board
, s
->moves
[i
], ply
, sdepth
, s
->moves
[i
].val
, alpha
, alpha
+1, 0 ));
950 val
= -search( ply
+1, sdepth
, false, -alpha
-1, -alpha
, red_fuck
);
951 GUI2(notify_value(ply
, val
, DIFF_NODES
, val
>alpha
? SearchGui::Red
: 0));
953 if((val
>alpha
) && pv
)
955 if(depth
>=0 && mv_pv_top
>=ply
)
957 mv_pv
[ply
] = s
->moves
[i
];
961 GUI1(notify(&board
, s
->moves
[i
], ply
, sdepth
, -INF
, alpha
, beta
, SearchGui::Bold
));
962 val
= -search( ply
+1, sdepth
, true, -beta
, -alpha
, false );
963 GUI2(notify_value(ply
, val
, DIFF_NODES
, val
>beta
? SearchGui::Red
: 0));
969 if(base_depth
> 0 && sdepth
<= 0)
971 q
= stat_quiesce_nodes
-q
;
972 if(q
> stat_max_quiesce_nodes
)
974 stat_max_quiesce_nodes
= q
;
975 max_quiesce_board
= board
;
980 #if NEGA_SCOUT && LATE_MOVE_REDUCTION
983 board
.undo_move(s
->moves
[i
], s
->save_buf
);
985 /* update the current best value and check for and alpha cut */
996 /* alpha improvement! */
1005 if(!expect_allbad
|| best
>= beta
)
1007 /* collect statistics for the history */
1008 if(/*best >= beta &&*/ (best_mv_found
!=-1) &&
1009 !s
->moves
[best_mv_found
].capture
&&
1010 !(s
->moves
[best_mv_found
].flags
>=PROMOTE_FIRST
) )
1011 history_hit
[HISTORY_INDEX(s
->moves
[best_mv_found
])] += quiesce
? 8 : 16;
1013 int mx
= CAPT_INDEX(s
->moves
[best_mv_found
]);
1014 if(pluto1
!=-1 && !s
->moves
[best_mv_found
].capture
&&
1015 !(s
->moves
[best_mv_found
].flags
>=PROMOTE_FIRST
))
1017 int ix
= FAST_PLUTO(pluto1
, mx
);
1018 pluto_hit
[ix
] += quiesce
? 8 : 16;
1021 if(pluto2
!=-1 && !s
->moves
[best_mv_found
].capture
&&
1022 !(s
->moves
[best_mv_found
].flags
>=PROMOTE_FIRST
))
1024 int ix
= FAST_PLUTO(pluto2
, mx
);
1025 pluto2_hit
[ix
] += quiesce
? 8 : 16;
1030 mv_stack_top
-= s
->num_moves
; /* free the moves we allocated */
1032 /* this is a null move, save what the threat is */
1033 if(stack
[ply
-1].curr_move
== -1 && best_mv_found
>= 0)
1034 stack
[ply
-1].null_threat
= s
->moves
[best_mv_found
];
1036 /* if we found a best move searching, that move will be saved.
1037 if we did no search (ie quiescence), save the old hash value,
1038 or -1 if no hash entry had been found */
1039 int bestmv
= cbest_mv_hash
;
1040 if(best_mv_found
>= 0)
1041 bestmv
= board
.compress_move(s
->moves
[best_mv_found
]);
1043 GUI(notify_msg(ply
, TmpStr("Result: %d (%dth)", best
, best_mv_found
).data(), 0))
1045 /* write the value in the hash, with the index of the best move */
1046 int16_t low
= best
> orig_alpha
? MIN(best
, beta
) : lower_bound
;
1047 int16_t high
= best
< beta
? (quiesce
&& !s
->num_moves
? best
: MAX(alpha
, best
)) : +INF
;
1048 engine
->write_hash( board
.hash
, low
, high
,
1049 MAX(base_depth
,-500), bestmv
, no_good_moves
);
1050 GUI(notify_hash(ply
, low
, high
,
1051 MAX(base_depth
,-500), alpha
, beta
, bestmv
? board
.uncompress_move(bestmv
) : Move::None(), true,
1052 SearchGui::Bold
| SearchGui::Magenta
) );
1057 uint16_t SearchRoot::pluto_tot
[PLUTO_SIZE
];
1058 uint16_t SearchRoot::pluto_hit
[PLUTO_SIZE
];
1059 uint16_t SearchRoot::pluto2_tot
[PLUTO_SIZE
];
1060 uint16_t SearchRoot::pluto2_hit
[PLUTO_SIZE
];
1061 uint16_t SearchRoot::history_tot
[HISTORY_SIZE
];
1062 uint16_t SearchRoot::history_hit
[HISTORY_SIZE
];
1064 SearchRoot::SearchRoot(Engine
* e
, const Board
& b
)
1067 , search_gui(e
->search_gui
)
1071 engine
->current_root
= this;
1074 SearchRoot::~SearchRoot()
1076 engine
->current_root
= NULL
;
1079 Move
Engine::find_best_move()
1082 IFGUI(Engine
*engine
= this);
1083 int num_mate_hits
= 0;
1084 SearchRoot
root(this, board
);
1085 SearchRoot::SearchStack
*s
= &root
.stack
[0];
1087 /* initialize the root node */
1088 root
.base_depth
= PLY
;
1091 s
->null_threat
= Move::FromInt(0);
1092 s
->null_threat_dangerous
= false;
1093 s
->moves
= root
.mv_stack
;
1094 s
->num_moves
= root
.mv_stack_top
= root
.board
.find_moves(s
->moves
);
1096 s
->escape_from
[1] = s
->escape_from
[2] = INVALID
;
1097 #endif //PAWN_STRIKE
1101 /* calculate how much time we will think*/
1102 start_think_time
= current_time();
1103 if(analysis_limit
== TIME_LIMIT
)
1105 if(board
.color_to_move
== st_computer_color
)
1107 else /* pondering? analysing? */
1108 time_best_csec
= 99999999;
1109 max_think_time
= start_think_time
+ time_best_csec
- 2;
1112 /* to print the analysis */
1114 output("\tply\tscore\ttime\tnodes\tpv\n");
1116 /* return immediatly if the move is forced. */
1120 output("\t0\t0\t0\t0\t%s (only move)\n", board
.move_to_alg(MoveStr().data(), s
->moves
[0]));
1124 /* probe the play lines */
1125 if(eng_status
== PLAYING
&& st_computer_color
== board
.color_to_move
)
1127 Move retv
= probe_lines(&root
.board
);
1132 output("\t0\t0\t0\t0\t%s (selected line)\n", board
.move_to_alg(MoveStr().data(), retv
));
1137 /* probe the book */
1138 Move bookmove
= probe_book(&root
.board
);
1139 if(bookmove
.valid())
1142 for(int i
=0;i
<s
->num_moves
++;i
++)
1143 if(bookmove
== s
->moves
[i
])
1145 output("Error!!! invalid move in the book!!!\n");
1149 reset_hash(); //Try to be deterministic
1150 processed_nodes
= 0;
1154 memset( root
.history_tot
, 0, HISTORY_SIZE
*sizeof(uint16_t));
1155 memset( root
.history_hit
, 0, HISTORY_SIZE
*sizeof(uint16_t));
1156 memset( root
.pluto_tot
, 0, PLUTO_SIZE
*sizeof(uint16_t));
1157 memset( root
.pluto_hit
, 0, PLUTO_SIZE
*sizeof(uint16_t));
1158 memset( root
.pluto2_tot
, 0, PLUTO_SIZE
*sizeof(uint16_t));
1159 memset( root
.pluto2_hit
, 0, PLUTO_SIZE
*sizeof(uint16_t));
1164 /* set the back jump for the quick thinking exit */
1169 /* do the iterative deepening thing. */
1172 int16_t alpha
= num_mate_hits
? -INF
: -WORST_MATE
;
1173 int16_t beta
= num_mate_hits
? INF
: WORST_MATE
;
1175 GUI(new_root_level(root
.base_depth
));
1177 /* for each move call the alpha-beta search function */
1178 for(int i
=0;i
<s
->num_moves
;i
++)
1181 root
.board
.do_move(s
->moves
[i
], s
->save_buf
);
1185 root
.mv_pv
[0] = s
->moves
[i
];
1188 GUI1(notify(&root
.board
, s
->moves
[i
], 0, root
.base_depth
-PLY
, s
->moves
[i
].val
, alpha
, beta
, SearchGui::Bold
));
1189 s
->moves
[i
].val
= -root
.search( 1, root
.base_depth
-PLY
, true, -beta
, -alpha
, false );
1190 GUI2(notify_value(0, s
->moves
[i
].val
, DIFF_NODES
, 0));
1195 GUI1(notify(&root
.board
, s
->moves
[i
], 0, root
.base_depth
-PLY
, s
->moves
[i
].val
, alpha
, alpha
+1, 0 ));
1196 s
->moves
[i
].val
= -root
.search( 1, root
.base_depth
-PLY
, false, -alpha
-1, -alpha
, false );
1197 GUI2(notify_value(0, s
->moves
[i
].val
, DIFF_NODES
, s
->moves
[i
].val
>alpha
? SearchGui::Red
: 0));
1199 if(s
->moves
[i
].val
> alpha
)
1201 root
.mv_pv
[0] = s
->moves
[i
];
1204 GUI1(notify(&root
.board
, s
->moves
[i
], 0, root
.base_depth
-PLY
, -INF
, alpha
, beta
, SearchGui::Bold
));
1205 s
->moves
[i
].val
= -root
.search( 1, root
.base_depth
-PLY
, true, -beta
, -alpha
, false );
1206 GUI2(notify_value(0, s
->moves
[i
].val
, DIFF_NODES
, 0));
1210 root
.board
.undo_move(s
->moves
[i
], s
->save_buf
);
1213 if(s
->moves
[i
].val
> alpha
)
1215 alpha
= s
->moves
[i
].val
;
1217 Move tmp
= s
->moves
[i
];
1218 for(int q
=i
-1;q
>=0;q
--)
1219 s
->moves
[q
+1] = s
->moves
[q
];
1222 /* this move caused an alpha cut, so print the new line */
1223 if( post
/*&& processed_nodes>100000*/)
1225 output("\t%d\t%d\t%d\t%llu\t",
1226 root
.base_depth
/PLY
,
1228 current_time() - start_think_time
,
1229 (unsigned long long)processed_nodes
);
1230 print_moves(root
.mv_pv
, 1/*root.mv_pv_top*/, true, true);
1235 /* print the result of the analysis at this depth */
1236 if( post
/*&& processed_nodes>100000*/)
1238 output("\t%d\t%d\t%d\t%llu\t",
1239 root
.base_depth
/PLY
,
1241 current_time() - start_think_time
,
1242 (unsigned long long)processed_nodes
);
1243 print_moves(root
.mv_pv
, 1/*root.mv_pv_top*/, true, true);
1247 if( root
.base_depth
>= 50*PLY
)
1250 /* return in case of fixed depth search */
1251 if( eng_status
== PLAYING
&& st_computer_color
== board
.color_to_move
&&
1252 analysis_limit
== DEPTH_LIMIT
&& root
.base_depth
== st_depth
*PLY
)
1255 /* return if 3/5 of time is gone (we can't search another ply anyway) */
1256 if( eng_status
== PLAYING
&& st_computer_color
== board
.color_to_move
&&
1257 analysis_limit
== TIME_LIMIT
&&
1258 (current_time()-start_think_time
) >= (time_best_csec
*3/5) )
1261 /* if a checkmate was detected return immediately */
1262 if( ABS(alpha
) > WORST_MATE
)
1265 if(num_mate_hits
>= 5)
1269 root
.base_depth
+= PLY
;
1277 output("#max quiesce board: %s [%d %d]\n", max_quiesce_board
.to_fen(BigStr().data()),
1278 max_quiesce_alpha
, max_quiesce_beta
);