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()
110 if(eng_status
!= ANALYZING
)
112 printf("Thinking: ");
113 for(int i
=0; i
<current_ply
; i
++)
115 if(stack
[i
].curr_move
== -2)
116 continue; //Internal iterative deepening
117 else if(stack
[i
].curr_move
== -1)
120 board
.do_null_move();
125 printf("%s", move_to_alg(buf
, &(stack
[i
].moves
[stack
[i
].curr_move
]) ) );
126 board
.do_move(stack
[i
].moves
[stack
[i
].curr_move
]);
128 printf((i
!= current_ply
-1) ? " " : "\n");
137 output("stat01: %d %llu %d %d %d %s\n",
138 current_time() - start_think_time
,
139 (unsigned long long)processed_nodes
,
140 stack
[0].base_depth
/100,
141 stack
[0].num_moves
-1-stack
[0].curr_move
,
143 move_to_alg(buf
, &(stack
[0].moves
[stack
[0].curr_move
]) ) );
146 output("stat01: 0 0 0 0 0\n");
150 bool SearchRoot::null_move_ok()
152 int c
= IS_WHITE(board
.color_to_move
) ? 5 : -1;
153 int numpawns
= board
.mat_tracking
[c
+PAWN
].count
;
154 int numpieces
= board
.mat_tracking
[c
+KNIGHT
].count
+ board
.mat_tracking
[c
+BISHOP
].count
155 + board
.mat_tracking
[c
+ROOK
].count
+ board
.mat_tracking
[c
+QUEEN
].count
;
158 if(numpieces
>= 1 && numpawns
>= 2)
164 SearchRoot::moves_heuristic(Move
*mv
, int num_mv
, bool pv
, int ply
, int orig_depth
,
165 Move best_mv_hash
, bool quiesce
, Move
* prev
, int* overall_extensions
,
174 for(int i
=0;i
<num_mv
;i
++)
179 /* give a high bonus to the move stored in the hash, if any.
180 mark only which is, don't continue, because some extensions
181 may be triggered ad added later (ie pawn strike, etc) */
182 if(mv
[i
].as_int
== best_mv_hash
.as_int
)
186 if(num_escapes
<=2 && PIECE_OF(board
.data
[mv
[i
].from
]) != PAWN
&&
187 (mv
[i
].from
== stack
[ply
-1].escape_from
[1] || stack
[ply
-1].escape_from
[2]) )
189 int x
= board
.move_see_val(mv
[i
]);
194 escapes
[num_escapes
] = i
;
200 /* process strong pawn moves */
201 if(PIECE_OF(board
.data
[mv
[i
].from
])==PAWN
) /* pawn strike */
203 uint8_t x
= X(mv
[i
].to
);
204 uint8_t y
= IS_WHITE(board
.color_to_move
) ? Y(mv
[i
].to
) : 7-Y(mv
[i
].to
);
206 if( mv
[i
].flags
== PROMOTEQUEEN
|| y
== 6)
208 int x
= board
.move_see_val(mv
[i
]);
212 mv
[i
].val
+= mv
[i
].flags
? 29600 : 29599; /* promote! */
213 mv
[i
].extend
= PLY
; /* extend search */
220 int other
= IS_WHITE(board
.other_color
);
222 if((!board
.line_pawns
[other
][x
].count
|| board
.line_pawns
[other
][x
].pos
[0] > pos
)
223 && (x
==0 || !board
.line_pawns
[other
][x
-1].count
|| board
.line_pawns
[other
][x
-1].pos
[0] >= pos
)
224 && (x
==7 || !board
.line_pawns
[other
][x
+1].count
|| board
.line_pawns
[other
][x
+1].pos
[0] >= pos
))
226 int x
= board
.move_see_val(mv
[i
]);
230 mv
[i
].val
+= y
>= 5 ? 29550 : 29500; /* passed pawn advancing! */
232 mv
[i
].extend
= PLY
; /* extend search */
239 if(orig_depth
>= 2*PLY
)
242 uint8_t up_right
= Board::up_dir
[IS_WHITE(board
.color_to_move
)] + RIGHT
;
243 uint8_t up_left
= Board::up_dir
[IS_WHITE(board
.color_to_move
)] + LEFT
;
244 uint8_t p1
= mv
[i
].to
+ up_right
;
245 uint8_t p2
= mv
[i
].to
+ up_left
;
246 uint8_t a
= OUT_OF_BOARD(p1
) ? 0 : board
.data
[p1
];
247 uint8_t b
= OUT_OF_BOARD(p2
) ? 0 : board
.data
[p2
];
248 if( (COLOR_OF(a
)==board
.other_color
&& PIECE_OF(a
)!=PAWN
)
249 || (COLOR_OF(b
)==board
.other_color
&& PIECE_OF(b
)!=PAWN
) )
251 int x
= board
.move_see_val(mv
[i
]);
255 mv
[i
].val
= 27000; /* pawn strike! */
264 int x
= board
.move_see_val(mv
[i
]);
267 if(prev
&& prev
->capture
&&
268 (mv
[i
].to
== prev
->to
) && (x
>= Board::simple_values
[PIECE_OF(prev
->capture
)]) )
271 if( (x
== Board::simple_values
[PIECE_OF(prev
->capture
)]) )
278 if(orig_depth
>-7*PLY
&& board
.move_is_check(mv
[i
]) )
284 else if(x
>=0 && orig_depth
>-7*PLY
&& board
.move_is_check(mv
[i
]) )
286 /* = capture but check */
291 else /* add a bonus for checks (but not too deep, or quiescence will get mad) */
292 if(board
.move_is_check(mv
[i
]) )
294 if(board
.move_see_val(mv
[i
])>=0)
301 /* null-move threat */
302 if(stack
[ply
-1].null_threat
== mv
[i
])
309 mv
[i
].val
+= (history_hit
[HISTORY_INDEX(mv
[i
])] + 32) * 1024 / (3 * (history_tot
[HISTORY_INDEX(mv
[i
])] + 64));
311 int mx
= CAPT_INDEX(mv
[i
]);
314 int ix
= FAST_PLUTO(p1
, mx
);
315 mv
[i
].val
+= (pluto_hit
[ix
] + 24) * 1024 / (3 * (pluto_tot
[ix
] + 48));
321 int ix
= FAST_PLUTO(p2
, mx
);
322 mv
[i
].val
+= (pluto2_hit
[ix
] + 16) * 1024 / (3 * (pluto2_tot
[ix
] + 32));
327 mv
[i
].val
+= (history_hit
[HISTORY_INDEX(mv
[i
])] + 32) * 256*4 / (history_tot
[HISTORY_INDEX(mv
[i
])] + 64);
332 if((stack
[ply
-1].escape_from
[1] != INVALID
|| stack
[ply
-1].escape_from
[2] != INVALID
) && num_escapes
<= 2)
334 for(int i
=0;i
<num_escapes
;i
++)
335 mv
[escapes
[i
]].extend
= PLY
;
340 mv
[hash_move
].val
= 30000;
345 SearchRoot::moves_quiescence_heuristic(Move
*mv
, int num_mv
, const Move
& best_mv_hash
,
346 int static_eval
, int alpha
, int beta
, int orig_depth
, Move
* prev
)
349 for(int i
=0;i
<num_mv
;i
++)
354 /* give a high bonus to the move stored in the hash, if any.
355 mark only which is, don't continue, because some extensions
356 may be triggered ad added later (ie pawn strike, etc) */
357 if(mv
[i
].as_int
== best_mv_hash
.as_int
)
360 /* process strong pawn moves */
361 if(PIECE_OF(board
.data
[mv
[i
].from
])==PAWN
)
363 if( ROW_OF(mv
[i
].to
) == board
.seventh_rank
[IS_WHITE(board
.color_to_move
)] )
365 int x
= board
.move_see_val(mv
[i
]);
369 mv
[i
].val
+= 29499; /* 7th push */
370 mv
[i
].extend
= PLY
; /* extend search */
375 if( mv
[i
].flags
== PROMOTEQUEEN
)
377 int x
= board
.move_see_val(mv
[i
]);
381 mv
[i
].val
+= 29500; /* promote! */
382 mv
[i
].extend
= PLY
; /* extend search */
390 int x
= board
.move_see_val(mv
[i
]);
392 if(prev
&& prev
->capture
&&
393 (mv
[i
].to
== prev
->to
) && (x
>= Board::simple_values
[PIECE_OF(prev
->capture
)]) )
395 mv
[i
].val
= 29900 + x
;
396 if( (x
== Board::simple_values
[PIECE_OF(prev
->capture
)]) )
401 if( x
>0 && ((orig_depth
>-2*PLY
|| static_eval
==-INF
) ? true : x
*100+static_eval
+200>alpha
) )
406 else if((x
>=0 && orig_depth
>-4*PLY
) && board
.move_is_check(mv
[i
]) )
408 /* = capture but check */
413 else /* add a bonus for checks (but not too deep, or quiescence will get mad) */
414 if(orig_depth
>-2*PLY
&& board
.move_is_check(mv
[i
]) && board
.move_see_val(mv
[i
])>=0)
421 if(hash_move
>= 0 && mv
[hash_move
].val
> 9000)
422 mv
[hash_move
].val
= 30000;
426 /*******************************************************************************
427 The main alpha-beta recursive search function.
428 It handles both normal search (with or without null move)
429 and quiescence search, because i have having 2 almost identical
431 *******************************************************************************/
432 int16_t SearchRoot::search(int ply
, int base_depth
, bool pv
, int16_t orig_alpha
, int16_t beta
, bool expect_allbad
)
434 SearchStack
*s
= &stack
[ply
];
436 uint16_t cbest_mv_hash
= 0; /* the compressed move from the hash */
437 Move best_mv_hash
= Move::FromInt(0); /* the move from the hash */
438 int best_mv_found
= -1; /* the index of the best move AFTER searching */
440 bool extended
= false;
441 bool no_good_moves
= false;
442 int16_t lower_bound
= -INF
;
443 int16_t position_val
;
444 int depth
= base_depth
;
445 int16_t alpha
= orig_alpha
;
448 #if IGNORE_ALLBAD_NODES
449 expect_allbad
= false;
455 for(int i
=ply
-1;i
>=0;i
--)
457 if(stack
[i
].curr_move
== -1)
458 board
.undo_null_move(stack
[i
].save_buf
);
459 else if(stack
[i
].curr_move
>= 0)
460 board
.undo_move(stack
[i
].moves
[stack
[i
].curr_move
], stack
[i
].save_buf
);
462 printf("[FEN \"%s\"]\n", board
.to_fen(BigStr().data()) );
463 for(int i
=0;i
<ply
;i
++)
465 printf(" %s", stack
[i
].curr_move
<= -1 ? "NULL" :
466 board
.move_to_alg(TmpStr().data(), stack
[i
].moves
[stack
[i
].curr_move
]));
467 if(stack
[i
].curr_move
== -1)
468 board
.do_null_move(stack
[i
].save_buf
);
469 else if(stack
[i
].curr_move
>= 0)
470 board
.do_move(stack
[i
].moves
[stack
[i
].curr_move
], stack
[i
].save_buf
);
478 // STAT(quiesce_nodes)
483 s
->null_threat
= Move::FromInt(0);
484 s
->null_threat_dangerous
= false;
486 stack
[ply
].escape_from
[1] = stack
[ply
].escape_from
[2] = INVALID
;
489 engine
->prefetch_hash( board
.hash
);
491 /* check if time is running out */
492 engine
->check_time();
494 /* check for a draw for repetition or 50mvs. Of course the draw for
495 repetition must be checked BEFORE probing the hash :)*/
497 return (board
.color_to_move
== engine
->st_computer_color
) ? engine
->v_eval_draw
:
498 ((board
.other_color
== engine
->st_computer_color
) ? -engine
->v_eval_draw
: 0); /* be aggressive! */
500 /*******************************************************************************
502 If the probe is succesful the hashtable will return us value
503 that can be exact, a lower bound or an upper bound, and if the
504 depth of the hashed search is >= the current depth this value
505 will be used to improve alpha and beta and possibly return immediatly.
506 The hastable will also give us a "best" move that will be searched
508 This is the move that caused the "final" cutoff when this position
509 was searched previously. This best move is actually the index of the best
510 move in the array of generated moves (it is supposed to be deterministic :)
511 *******************************************************************************/
513 HashEntry
*h
= engine
->probe_hash( board
.hash
);
516 GUI(notify_hash(ply
, h
->lo
, h
->up
, h
->depth
, alpha
, beta
,
517 h
->best_mv
? board
.uncompress_move(h
->best_mv
) : Move::None(), false,
518 (((h
->depth
>= base_depth
) && (h
->lo
>=beta
|| h
->up
==h
->lo
|| h
->up
<=alpha
))
519 ? SearchGui::Bold
: 0) | SearchGui::Magenta
) );
522 if(h
&& (h
->depth
>= base_depth
))// || ABS(h->value)>INF-1000) )
524 int16_t l
= h
->lower();
525 int16_t u
= h
->upper();
533 best
= alpha
= MAX(alpha
, l
);
537 cbest_mv_hash
= h
->best_mv
;
539 /*******************************************************************************
540 Test if we are under check, and if so extend search
541 *******************************************************************************/
543 s
->under_check
= board
.under_attack(board
.king_pos
[IS_WHITE(board
.color_to_move
)],
546 /*******************************************************************************
547 If it is time to quiesce, evaluate and test if we can exit
548 immediately with a beta cut-off (try first a rough eval - delta)
549 *******************************************************************************/
550 quiesce
= ((!s
->under_check
) && (depth
<=0)) || (ply
> 70);
555 if(quiesce
&& depth
>=-PLY
)
558 Move
*mv
= mv_stack
+ mv_stack_top
;
559 board
.do_null_move();
560 num_mv
= board
.find_moves(mv
);
561 uint8_t pup
= INVALID
;
563 for(int i
=0;i
<num_mv
;i
++)
565 if(!mv
[i
].capture
|| PIECE_OF(mv
[i
].capture
)==PAWN
)
567 if(mv
[i
].to
!= pup
&& board
.move_see_val(mv
[i
])>0)
577 board
.undo_null_move();
581 if(quiesce
&& (best
== -INF
|| ply
>70) )
583 best
= board
.evaluate(engine
->st_computer_color
, alpha
, beta
);
584 lower_bound
= best
; //we have at the very least "best" as lower bound now.
585 GUI(notify_eval(ply
, best
, alpha
, beta
, best
>=beta
? SearchGui::Blue
|SearchGui::Bold
: SearchGui::Blue
));
587 alpha
= MAX(alpha
, best
);
595 if(quiesce
&& h
&& h
->no_good_moves
)
599 /*******************************************************************************
601 *******************************************************************************/
602 if(!expect_allbad
&& !pv
&& !s
->under_check
&& (stack
[ply
-1].curr_move
!= -1)
603 && depth
>= 2*PLY
&& beta
<WORST_MATE
&& null_move_ok())
606 int sdepth
= (depth
>= 5*PLY
) ? (depth
-4*PLY
) : depth
-3*PLY
;
609 board
.do_null_move(s
->save_buf
);
610 GUI1(notify(&board
, Move::None(), ply
, sdepth
, -INF
, beta
-1, beta
, SearchGui::Green
));
611 val
= -search( ply
+1, sdepth
, false, -beta
, -beta
+NULL_SOLIDITY_MARGIN
, false);
612 GUI2(notify_value(ply
, val
, DIFF_NODES
, SearchGui::Bold
));
613 board
.undo_null_move(s
->save_buf
);
619 #if NULL_SOLIDITY_MARGIN > 1
620 if(depth
<= 3*PLY
&& val
> beta
- NULL_SOLIDITY_MARGIN
)
624 if(val
< -WORST_MATE
)
625 s
->null_threat_dangerous
= true;
628 if(val
<alpha
-100 && /* we are facing a threat*/
629 stack
[ply
+1].best_move
!= -1) /* be sure we aren't reading random memory */
631 /* ok, officially the array stack[ply+1].moves has already
632 been deallocated, but who cares :) */
633 s
->threat
= stack
[ply
+1].moves
[stack
[ply
+1].best_move
];
636 /* Botvinnik-Markoff extension!!! */
637 if(!extended
&& ply
>=3 && (s
->threat
== stack
[ply
-2].threat
) )
650 /*******************************************************************************
651 Now generate the legal moves and look for a check/stalemate
652 *******************************************************************************/
654 /* generate all the legal moves */
655 s
->moves
= &mv_stack
[mv_stack_top
];
656 s
->num_moves
= board
.find_moves(s
->moves
);
657 mv_stack_top
+= s
->num_moves
;
658 s
->under_check
= board
.under_check
;
660 pluto1
= stack
[ply
-1].best_move
>=0 ? PLUTO1(stack
[ply
-1].moves
[stack
[ply
-1].best_move
]) : -1;
661 pluto2
= (ply
>=2 && stack
[ply
-1].best_move
>=0 && stack
[ply
-2].best_move
>=0) ?
662 PLUTO2(stack
[ply
-2].moves
[stack
[ply
-2].best_move
], stack
[ply
-1].moves
[stack
[ply
-1].best_move
]) : -1;
664 if(s
->under_check
==2) /* double check */
669 else if(s
->under_check
) /* simple check */
672 if(stack
[ply
-1].curr_move
>=0 &&
673 !board
.pins
[stack
[ply
-1].moves
[ /* last moved piece is not attacking the king */
674 stack
[ply
-1].curr_move
].to
]) /* so this is a discover check */
681 /* return now if the positon is terminal */
686 /* while mating, sacrify as much as possible :) */
687 int mt
= IS_WHITE(board
.other_color
) ? 5 : -1;
688 int16_t matval
= Board::simple_values
[PAWN
]*board
.mat_tracking
[mt
+PAWN
].count
+
689 Board::simple_values
[KNIGHT
]*board
.mat_tracking
[mt
+KNIGHT
].count
+
690 Board::simple_values
[BISHOP
]*board
.mat_tracking
[mt
+BISHOP
].count
+
691 Board::simple_values
[QUEEN
]*board
.mat_tracking
[mt
+QUEEN
].count
;
692 best
= alpha
= beta
= -INF
+ ply
*100 + matval
;
695 best
= alpha
= beta
= 0;
699 /* single-reply extension */
700 if(s
->num_moves
== 1 && !extended
)
705 else if(s
->num_moves
<= 3 && !extended
)
711 /*******************************************************************************
713 First comes the move from the hashtable, if avalable.
714 The remaining moves are sorted with a heuristic that keeps in account
715 the history heuristic (ie the moves that previously caused an alpha
716 cutoff), a MVV/LVA bonus value and a small bonus for moves that go
718 *******************************************************************************/
720 /* convert the move we got from the hash to the move structure */
723 best_mv_hash
= board
.uncompress_move(cbest_mv_hash
);
724 /* if it happened that the move we got from the hashtable
725 is not valid, simply no move will get the high
726 heuristic bonus value */
728 #if INTERNAL_ITERATIVE_DEEPENING
729 else if(base_depth
>3*PLY
&& pv
) /* don't do it only on the pv, or it will be useless :) */
732 GUI1(notify(&board
, Move::None(), ply
, base_depth
-2*PLY
, -INF
, alpha
, beta
, SearchGui::Blue
));
733 int val
= search(ply
+1, base_depth
-2*PLY
, true, alpha
, beta
, expect_allbad
);
734 GUI2(search_gui
->notify_value(ply
, val
, DIFF_NODES
, 0));
736 HashEntry
*h2
= probe_hash( board
.hash
);
737 if(h2
&& h2
->best_mv
)
739 cbest_mv_hash
= h2
->best_mv
;
740 best_mv_hash
= board
.uncompress_move(cbest_mv_hash
);
743 #endif //INTERNAL_ITERATIVE_DEEPENING
745 /* for each move calculate the heuristic goodness value */
746 #if DEBUG && TRACK_ATTACKS
747 board
.check_attacks();
750 Move
*prev
= (stack
[ply
-1].curr_move
>=0) ? &stack
[ply
-1].moves
[stack
[ply
-1].curr_move
] : NULL
;
752 moves_quiescence_heuristic( s
->moves
, s
->num_moves
, best_mv_hash
,
753 best
, alpha
, beta
, base_depth
, prev
);
757 moves_heuristic( s
->moves
, s
->num_moves
, pv
, ply
, base_depth
,
758 best_mv_hash
, quiesce
, prev
, &overall_ext
, pluto1
, pluto2
);
759 depth
+= overall_ext
;
762 #if DEBUG && TRACK_ATTACKS
763 board
.check_attacks();
766 /* if quiesce rip-off the "non-critical" moves */
770 for(int i
=0;i
<s
->num_moves
;i
++)
771 if(s
->moves
[i
].val
>0)
772 s
->moves
[n
++] = s
->moves
[i
];
773 mv_stack_top
-= s
->num_moves
-n
;
776 no_good_moves
= true;
779 /* Don't do it now, do it incrementally */
780 //sort_moves( s->moves, s->num_moves );
783 #if EARLY_TRANSP_CUTOFF
784 /*******************************************************************************
785 Try to get an early beta cutoff using the hash table values
786 of the following moves, and improve alpha too.
787 Try on the first 6 value of the ordered moves (argh, looking into the
788 hashtable is very expensive because of the cache!!!!!!!!)
789 *******************************************************************************/
793 HashKey hk
= board
.move_hash(s
->moves
[0]);
794 for(int i
=1;i
<s
->num_moves
;i
++)
796 engine
->prefetch_hash(hk
);
797 HashKey newhk
= board
.move_hash(s
->moves
[i
]);
798 HashEntry
*h2
= engine
->probe_hash( hk
);
801 if(h2
&& h2
->depth
>= depth
-PLY
)
808 alpha
= MAX(alpha
, (int16_t)-h2
->up
);
812 HashEntry
*h2
= engine
->probe_hash( hk
);
813 if(h2
&& h2
->depth
>= depth
-PLY
)
820 alpha
= MAX(alpha
, (int16_t)-h2
->up
);
823 #endif //EARLY_TRANSP_CUTOFF
825 /*******************************************************************************
826 It is now time to loop all the successor moves and search recursively.
827 *******************************************************************************/
830 /* calcluate the evaluation (required by fitility pruning) */
831 position_val
= quiesce
? best
: board
.dummy_evaluate(); //evaluate( st_computer_color, -INF, INF);
834 for(int i
=0;i
<s
->num_moves
;i
++)
837 int sdepth
= depth
-100;
839 /* sort moves incrementally, in the hope of a beta cut */
840 engine
->incremental_sort_moves(s
->moves
+i
, s
->num_moves
-i
);
842 /* extensions calculated during the heuristic sort */
843 sdepth
+= s
->moves
[i
].extend
;
846 /* futility pruning, it is done only if we are not under check
847 and the move is not a "critical" move */
848 if(depth
>0 && depth
<=2*PLY
&& !s
->under_check
&& s
->moves
[i
].val
< 28000)
850 static const int mavala
[] = { 0, 500, 325, 975, 325, 100, 0 };
852 int16_t fmargin
= (depth
<= PLY
? 420 : 720);
853 int16_t fval
= position_val
+ mavala
[PIECE_OF(s
->moves
[i
].capture
)];
854 if(fval
< alpha
-fmargin
)
861 int mx
= CAPT_INDEX(s
->moves
[i
]);
863 /* collect history statistics */
864 if(!s
->moves
[i
].capture
&&
865 !(s
->moves
[i
].flags
>=PROMOTE_FIRST
) )
867 int ix
= HISTORY_INDEX(s
->moves
[i
]);
868 if(history_tot
[ix
] > 1024)
870 history_tot
[ix
] = history_tot
[ix
]*7/8;
871 history_hit
[ix
] = history_hit
[ix
]*7/8;
873 history_tot
[ix
] += quiesce
? 8 : 16;
876 if(pluto1
!=-1 && !s
->moves
[i
].capture
&&
877 !(s
->moves
[i
].flags
>=PROMOTE_FIRST
))
879 int ix
= FAST_PLUTO(pluto1
, mx
);
880 if(pluto_tot
[ix
] > 256)
882 pluto_tot
[ix
] = pluto_tot
[ix
]*7/8;
883 pluto_hit
[ix
] = pluto_hit
[ix
]*7/8;
885 pluto_tot
[ix
] += quiesce
? 8 : 16;
888 if(pluto2
!=-1 && !s
->moves
[i
].capture
&&
889 !(s
->moves
[i
].flags
>=PROMOTE_FIRST
))
891 int ix
= FAST_PLUTO(pluto2
, mx
);
892 if(pluto2_tot
[ix
] > 128)
894 pluto2_tot
[ix
] = pluto2_tot
[ix
]*7/8;
895 pluto2_hit
[ix
] = pluto2_hit
[ix
]*7/8;
897 pluto2_tot
[ix
] += quiesce
? 8 : 16;
901 //Set data for pawn-strike
903 if(!quiesce
&& PIECE_OF(board
.data
[s
->moves
[i
].from
]) == PAWN
&& s
->moves
[i
].val
== 27000) //FIXME, UGLY
905 stack
[ply
].escape_from
[1] = s
->moves
[i
].to
+ Board::up_dir
[IS_WHITE(board
.color_to_move
)] + RIGHT
;
906 if(OUT_OF_BOARD(stack
[ply
].escape_from
[1]) || !IS_OF_COLOR(board
.data
[stack
[ply
].escape_from
[1]], board
.other_color
)
907 || PIECE_OF(board
.data
[stack
[ply
].escape_from
[1]])==PAWN
)
908 stack
[ply
].escape_from
[1] = INVALID
;
909 stack
[ply
].escape_from
[2] = s
->moves
[i
].to
+ Board::up_dir
[IS_WHITE(board
.color_to_move
)] + LEFT
;
910 if(OUT_OF_BOARD(stack
[ply
].escape_from
[2]) || !IS_OF_COLOR(board
.data
[stack
[ply
].escape_from
[2]], board
.other_color
)
911 || PIECE_OF(board
.data
[stack
[ply
].escape_from
[2]])==PAWN
)
912 stack
[ply
].escape_from
[2] = INVALID
;
916 stack
[ply
].escape_from
[1] = stack
[ply
].escape_from
[2] = INVALID
;
920 board
.do_move(s
->moves
[i
], s
->save_buf
);
925 if(base_depth
> 0 && sdepth
<= 0)
927 STAT(quiesce_called
);
928 q
= stat_quiesce_nodes
;
932 #if NEGA_SCOUT /* use negascout, (null window search for nodes that are not in the pv) */
933 if(i
== 0 && !expect_allbad
)
935 if(depth
>=0 && pv
&& mv_pv_top
>=ply
)
937 mv_pv
[ply
] = s
->moves
[i
];
941 GUI1(notify(&board
, s
->moves
[i
], ply
, sdepth
, s
->moves
[i
].val
, alpha
, beta
, SearchGui::Bold
));
942 val
= -search( ply
+1, sdepth
, pv
, -beta
, -alpha
, !pv
);
943 GUI2(notify_value(ply
, val
, DIFF_NODES
, 0));
948 bool red_fuck
= false;
949 #if LATE_MOVE_REDUCTION
950 /* history pruning, if this is not a "critical" move and the failhigh
951 stats are too low, try a reduced depth search (if it returns >alpha,
952 re-do the full depth search) */
953 // if((sdepth>0) && !s->under_check && depth<=3*PLY && s->moves[i].val<28000 &&
954 // (history_hit[HISTORY_INDEX(s->moves[i])]+1)*3
955 // < (history_tot[HISTORY_INDEX(s->moves[i])]+1))
956 if( (sdepth
>0) && !s
->under_check
&& !s
->null_threat_dangerous
957 && s
->moves
[i
].val
<28000 && (s
->moves
[i
].val
<(sdepth
<=PLY
? 650 : 450)) )
959 int rdepth
= depth
- 2*PLY
;
960 //sdepth - PLY; //(s->moves[i].val<250 ? 2*PLY : PLY) - s->moves[i].extend;
961 GUI1(notify(&board
, s
->moves
[i
], ply
, rdepth
, s
->moves
[i
].val
, alpha
, alpha
+1, SearchGui::Italic
|SearchGui::Gray
));
962 val
= -search( ply
+1, rdepth
, false, -alpha
-1, -alpha
, false );
963 GUI2(notify_value(ply
, val
, DIFF_NODES
, val
>alpha
? SearchGui::Red
: 0));
965 goto skip_search
; /* reduced search was effective */
969 GUI1(notify(&board
, s
->moves
[i
], ply
, sdepth
, s
->moves
[i
].val
, alpha
, alpha
+1, 0 ));
970 val
= -search( ply
+1, sdepth
, false, -alpha
-1, -alpha
, red_fuck
);
971 GUI2(notify_value(ply
, val
, DIFF_NODES
, val
>alpha
? SearchGui::Red
: 0));
973 if((val
>alpha
) && pv
)
975 if(depth
>=0 && mv_pv_top
>=ply
)
977 mv_pv
[ply
] = s
->moves
[i
];
981 GUI1(notify(&board
, s
->moves
[i
], ply
, sdepth
, -INF
, alpha
, beta
, SearchGui::Bold
));
982 val
= -search( ply
+1, sdepth
, true, -beta
, -alpha
, false );
983 GUI2(notify_value(ply
, val
, DIFF_NODES
, val
>beta
? SearchGui::Red
: 0));
989 if(base_depth
> 0 && sdepth
<= 0)
991 q
= stat_quiesce_nodes
-q
;
992 if(q
> stat_max_quiesce_nodes
)
994 stat_max_quiesce_nodes
= q
;
995 max_quiesce_board
= board
;
1001 board
.undo_move(s
->moves
[i
], s
->save_buf
);
1003 /* update the current best value and check for and alpha cut */
1014 /* alpha improvement! */
1023 if(!expect_allbad
|| best
>= beta
)
1025 /* collect statistics for the history */
1026 if(/*best >= beta &&*/ (best_mv_found
!=-1) &&
1027 !s
->moves
[best_mv_found
].capture
&&
1028 !(s
->moves
[best_mv_found
].flags
>=PROMOTE_FIRST
) )
1029 history_hit
[HISTORY_INDEX(s
->moves
[best_mv_found
])] += quiesce
? 8 : 16;
1031 int mx
= CAPT_INDEX(s
->moves
[best_mv_found
]);
1032 if(pluto1
!=-1 && !s
->moves
[best_mv_found
].capture
&&
1033 !(s
->moves
[best_mv_found
].flags
>=PROMOTE_FIRST
))
1035 int ix
= FAST_PLUTO(pluto1
, mx
);
1036 pluto_hit
[ix
] += quiesce
? 8 : 16;
1039 if(pluto2
!=-1 && !s
->moves
[best_mv_found
].capture
&&
1040 !(s
->moves
[best_mv_found
].flags
>=PROMOTE_FIRST
))
1042 int ix
= FAST_PLUTO(pluto2
, mx
);
1043 pluto2_hit
[ix
] += quiesce
? 8 : 16;
1048 mv_stack_top
-= s
->num_moves
; /* free the moves we allocated */
1050 /* this is a null move, save what the threat is */
1051 if(stack
[ply
-1].curr_move
== -1 && best_mv_found
>= 0)
1052 stack
[ply
-1].null_threat
= s
->moves
[best_mv_found
];
1054 /* if we found a best move searching, that move will be saved.
1055 if we did no search (ie quiescence), save the old hash value,
1056 or -1 if no hash entry had been found */
1057 int bestmv
= cbest_mv_hash
;
1058 if(best_mv_found
>= 0)
1059 bestmv
= board
.compress_move(s
->moves
[best_mv_found
]);
1061 /* write the value in the hash, with the index of the best move */
1062 engine
->write_hash( board
.hash
,
1063 best
> orig_alpha
? MIN(best
, beta
) : lower_bound
,
1064 best
< beta
? best
: +INF
,
1065 MAX(base_depth
,-500), bestmv
, no_good_moves
);
1066 GUI(notify_hash(ply
, best
> orig_alpha
? MIN(best
, beta
) : lower_bound
, best
< beta
? best
: +INF
,
1067 MAX(base_depth
,-500), alpha
, beta
, bestmv
? board
.uncompress_move(bestmv
) : Move::None(), true,
1068 SearchGui::Bold
| SearchGui::Magenta
) );
1073 uint16_t SearchRoot::pluto_tot
[PLUTO_SIZE
];
1074 uint16_t SearchRoot::pluto_hit
[PLUTO_SIZE
];
1075 uint16_t SearchRoot::pluto2_tot
[PLUTO_SIZE
];
1076 uint16_t SearchRoot::pluto2_hit
[PLUTO_SIZE
];
1077 uint16_t SearchRoot::history_tot
[HISTORY_SIZE
];
1078 uint16_t SearchRoot::history_hit
[HISTORY_SIZE
];
1080 SearchRoot::SearchRoot(Engine
* e
, const Board
& b
)
1083 , search_gui(e
->search_gui
)
1089 SearchRoot::~SearchRoot()
1093 Move
Engine::find_best_move()
1096 Engine
*engine
= this;
1097 int base_depth
= PLY
;
1098 int num_mate_hits
= 0;
1099 SearchRoot
root(this, board
);
1100 SearchRoot::SearchStack
*s
= &root
.stack
[0];
1102 /* initialize the root node */
1105 s
->null_threat
= Move::FromInt(0);
1106 s
->null_threat_dangerous
= false;
1107 s
->moves
= root
.mv_stack
;
1108 s
->num_moves
= root
.mv_stack_top
= root
.board
.find_moves(s
->moves
);
1110 s
->escape_from
[1] = s
->escape_from
[2] = INVALID
;
1111 #endif //PAWN_STRIKE
1115 /* calculate how much time we will think*/
1116 start_think_time
= current_time();
1117 if(analysis_limit
== TIME_LIMIT
)
1119 if(board
.color_to_move
== st_computer_color
)
1121 else /* pondering? analysing? */
1122 time_best_csec
= 99999999;
1123 max_think_time
= start_think_time
+ time_best_csec
- 2;
1126 /* to print the analysis */
1128 output("\tply\tscore\ttime\tnodes\tpv\n");
1130 /* return immediatly if the move is forced. */
1134 output("\t0\t0\t0\t0\t%s (only move)\n", board
.move_to_alg(MoveStr().data(), s
->moves
[0]));
1138 /* probe the play lines */
1139 if(eng_status
== PLAYING
&& st_computer_color
== board
.color_to_move
)
1141 Move retv
= probe_lines(&root
.board
);
1146 output("\t0\t0\t0\t0\t%s (selected line)\n", board
.move_to_alg(MoveStr().data(), retv
));
1151 /* probe the book */
1152 Move bookmove
= probe_book(&root
.board
);
1153 if(bookmove
.valid())
1156 for(int i
=0;i
<s
->num_moves
++;i
++)
1157 if(bookmove
== s
->moves
[i
])
1159 output("Error!!! invalid move in the book!!!\n");
1163 IFGUI(reset_hash()); //Try to be deterministic
1164 processed_nodes
= 0;
1168 memset( root
.history_tot
, 0, HISTORY_SIZE
*sizeof(uint16_t));
1169 memset( root
.history_hit
, 0, HISTORY_SIZE
*sizeof(uint16_t));
1170 memset( root
.pluto_tot
, 0, PLUTO_SIZE
*sizeof(uint16_t));
1171 memset( root
.pluto_hit
, 0, PLUTO_SIZE
*sizeof(uint16_t));
1172 memset( root
.pluto2_tot
, 0, PLUTO_SIZE
*sizeof(uint16_t));
1173 memset( root
.pluto2_hit
, 0, PLUTO_SIZE
*sizeof(uint16_t));
1178 /* set the back jump for the quick thinking exit */
1183 /* do the iterative deepening thing. */
1186 int16_t alpha
= num_mate_hits
? -INF
: -WORST_MATE
;
1187 int16_t beta
= num_mate_hits
? INF
: WORST_MATE
;
1189 GUI(new_root_level(base_depth
));
1191 /* for each move call the alpha-beta search function */
1192 for(int i
=0;i
<s
->num_moves
;i
++)
1195 root
.board
.do_move(s
->moves
[i
], s
->save_buf
);
1199 root
.mv_pv
[0] = s
->moves
[i
];
1202 GUI1(notify(&root
.board
, s
->moves
[i
], 0, base_depth
-PLY
, s
->moves
[i
].val
, alpha
, beta
, SearchGui::Bold
));
1203 s
->moves
[i
].val
= -root
.search( 1, base_depth
-PLY
, true, -beta
, -alpha
, false );
1204 GUI2(notify_value(0, s
->moves
[i
].val
, DIFF_NODES
, 0));
1209 GUI1(notify(&root
.board
, s
->moves
[i
], 0, base_depth
-PLY
, s
->moves
[i
].val
, alpha
, alpha
+1, 0 ));
1210 s
->moves
[i
].val
= -root
.search( 1, base_depth
-PLY
, false, -alpha
-1, -alpha
, false );
1211 GUI2(notify_value(0, s
->moves
[i
].val
, DIFF_NODES
, s
->moves
[i
].val
>alpha
? SearchGui::Red
: 0));
1213 if(s
->moves
[i
].val
> alpha
)
1215 root
.mv_pv
[0] = s
->moves
[i
];
1218 GUI1(notify(&root
.board
, s
->moves
[i
], 0, base_depth
-PLY
, -INF
, alpha
, beta
, SearchGui::Bold
));
1219 s
->moves
[i
].val
= -root
.search( 1, base_depth
-PLY
, true, -beta
, -alpha
, false );
1220 GUI2(notify_value(0, s
->moves
[i
].val
, DIFF_NODES
, 0));
1224 root
.board
.undo_move(s
->moves
[i
], s
->save_buf
);
1227 if(s
->moves
[i
].val
> alpha
)
1229 alpha
= s
->moves
[i
].val
;
1231 Move tmp
= s
->moves
[i
];
1232 for(int q
=i
-1;q
>=0;q
--)
1233 s
->moves
[q
+1] = s
->moves
[q
];
1236 /* this move caused an alpha cut, so print the new line */
1237 if( post
/*&& processed_nodes>100000*/)
1239 output("\t%d\t%d\t%d\t%llu\t",
1242 current_time() - start_think_time
,
1243 (unsigned long long)processed_nodes
);
1244 print_moves(root
.mv_pv
, 1/*root.mv_pv_top*/, true, true);
1249 /* print the result of the analysis at this depth */
1250 if( post
/*&& processed_nodes>100000*/)
1252 output("\t%d\t%d\t%d\t%llu\t",
1255 current_time() - start_think_time
,
1256 (unsigned long long)processed_nodes
);
1257 print_moves(root
.mv_pv
, 1/*root.mv_pv_top*/, true, true);
1261 if( base_depth
>= 40*PLY
)
1264 /* return in case of fixed depth search */
1265 if( eng_status
== PLAYING
&& st_computer_color
== board
.color_to_move
&&
1266 analysis_limit
== DEPTH_LIMIT
&& base_depth
== st_depth
*PLY
)
1269 /* return if 3/5 of time is gone (we can't search another ply anyway) */
1270 if( eng_status
== PLAYING
&& st_computer_color
== board
.color_to_move
&&
1271 analysis_limit
== TIME_LIMIT
&&
1272 (current_time()-start_think_time
) >= (time_best_csec
*3/5) )
1275 /* if a checkmate was detected return immediately */
1276 if( ABS(alpha
) > WORST_MATE
)
1279 if(num_mate_hits
>= 5)
1291 output("#max quiesce board: %s [%d %d]\n", max_quiesce_board
.to_fen(BigStr().data()),
1292 max_quiesce_alpha
, max_quiesce_beta
);