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);
74 /* enable the quiescence search */
77 /* enable the nega-scout pv-search */
80 /* enable the null move */
83 /* il null move > beta-margin, reduce (not a dangerous position). Set to 1 to disable */
84 #define NULL_SOLIDITY_MARGIN 100
86 /* before doing the alpha beta search check if any of the following positions
87 can give use an early cutoff thanks to the hashtable */
88 #define EARLY_TRANSP_CUTOFF 1
90 /* reduce nodes for moves that are not check/captures that are considered
91 bad from the heuristic */
92 #define LATE_MOVE_REDUCTION 1
94 /* futility pruning: */
97 /* when the hashtable provides no "best" move, do a depth-2 search */
98 #define INTERNAL_ITERATIVE_DEEPENING 0
100 /* use the history sorting heuristic */
101 #define HISTORY_HEURISTIC 1
103 /* improve the sorting heuristic for pawn strikes */
104 #define PAWN_STRIKE 1
106 /* improve the sorting heuristic for moves to the center */
107 #define CENTER_HEURISTIC 0
111 void Engine::print_stat()
114 if(eng_status
!= ANALYZING
)
116 printf("Thinking: ");
117 for(int i
=0; i
<current_ply
; i
++)
119 if(stack
[i
].curr_move
== -2)
120 continue; //Internal iterative deepening
121 else if(stack
[i
].curr_move
== -1)
124 board
.do_null_move();
129 printf("%s", move_to_alg(buf
, &(stack
[i
].moves
[stack
[i
].curr_move
]) ) );
130 board
.do_move(stack
[i
].moves
[stack
[i
].curr_move
]);
132 printf((i
!= current_ply
-1) ? " " : "\n");
141 output("stat01: %d %llu %d %d %d %s\n",
142 current_time() - start_think_time
,
143 (unsigned long long)processed_nodes
,
144 stack
[0].base_depth
/100,
145 stack
[0].num_moves
-1-stack
[0].curr_move
,
147 move_to_alg(buf
, &(stack
[0].moves
[stack
[0].curr_move
]) ) );
150 output("stat01: 0 0 0 0 0\n");
154 void SearchRoot::print_pv(const Move
& m
)
160 engine
->output("%d.%s %s",
162 board
.color_to_move
==BLACK
? " ..." : "",
163 board
.move_to_alg(MoveStr().data(), m
) );
164 board
.do_move(m
, tmpy
[24]);
168 HashEntry
*h
= engine
->probe_hash( board
.hash
);
170 engine
->output(" ???");
172 engine
->output(" xxx");
173 if(!h
|| !h
->best_mv
)
176 hash_mv
[j
] = board
.uncompress_move(h
->best_mv
);
178 /* verify that the move in the hash is a legal move */
180 int num_tmp
= board
.find_moves(tmp
);
181 for(int q
=0;q
<num_tmp
;q
++)
182 if(tmp
[q
] == hash_mv
[j
])
188 if(board
.color_to_move
==WHITE
&& j
!=0)
189 engine
->output(" %d.",board
.num_moves
+1);
190 engine
->output( " %s", board
.move_to_alg(MoveStr().data(), hash_mv
[j
]) );
191 board
.do_move(hash_mv
[j
], tmpy
[j
]);
194 engine
->output("\n");
197 board
.undo_move(hash_mv
[j
], tmpy
[j
]);
198 board
.undo_move(m
, tmpy
[24]);
201 bool SearchRoot::null_move_ok()
203 int c
= IS_WHITE(board
.color_to_move
) ? 5 : -1;
204 int numpawns
= board
.mat_tracking
[c
+PAWN
].count
;
205 int numpieces
= board
.mat_tracking
[c
+KNIGHT
].count
+ board
.mat_tracking
[c
+BISHOP
].count
206 + board
.mat_tracking
[c
+ROOK
].count
+ board
.mat_tracking
[c
+QUEEN
].count
;
209 if(numpieces
>= 1 && numpawns
>= 2)
215 SearchRoot::moves_heuristic(Move
*mv
, int num_mv
, bool pv
, int ply
, int orig_depth
,
216 Move best_mv_hash
, bool quiesce
, Move
* prev
, int* overall_extensions
, bool expect_allbad
,
225 for(int i
=0;i
<num_mv
;i
++)
230 /* give a high bonus to the move stored in the hash, if any.
231 mark only which is, don't continue, because some extensions
232 may be triggered ad added later (ie pawn strike, etc) */
233 if(mv
[i
].as_int
== best_mv_hash
.as_int
)
237 if(num_escapes
<=2 && PIECE_OF(board
.data
[mv
[i
].from
]) != PAWN
&&
238 (mv
[i
].from
== stack
[ply
-1].escape_from
[1] || stack
[ply
-1].escape_from
[2]) )
240 int x
= board
.move_see_val(mv
[i
]);
245 escapes
[num_escapes
] = i
;
251 /* process strong pawn moves */
252 if(PIECE_OF(board
.data
[mv
[i
].from
])==PAWN
) /* pawn strike */
254 uint8_t x
= X(mv
[i
].to
);
255 uint8_t y
= IS_WHITE(board
.color_to_move
) ? Y(mv
[i
].to
) : 7-Y(mv
[i
].to
);
257 if( mv
[i
].flags
== PROMOTEQUEEN
|| y
== 6)
259 int x
= board
.move_see_val(mv
[i
]);
263 mv
[i
].val
+= mv
[i
].flags
? 29600 : 29599; /* promote! */
264 mv
[i
].extend
= PLY
; /* extend search */
271 int other
= IS_WHITE(board
.other_color
);
273 if((!board
.line_pawns
[other
][x
].count
|| board
.line_pawns
[other
][x
].pos
[0] > pos
)
274 && (x
==0 || !board
.line_pawns
[other
][x
-1].count
|| board
.line_pawns
[other
][x
-1].pos
[0] >= pos
)
275 && (x
==7 || !board
.line_pawns
[other
][x
+1].count
|| board
.line_pawns
[other
][x
+1].pos
[0] >= pos
))
277 int x
= board
.move_see_val(mv
[i
]);
281 mv
[i
].val
+= y
>= 5 ? 29550 : 29500; /* passed pawn advancing! */
283 mv
[i
].extend
= PLY
; /* extend search */
290 if(orig_depth
>= 2*PLY
)
293 uint8_t up_right
= Board::up_dir
[IS_WHITE(board
.color_to_move
)] + RIGHT
;
294 uint8_t up_left
= Board::up_dir
[IS_WHITE(board
.color_to_move
)] + LEFT
;
295 uint8_t p1
= mv
[i
].to
+ up_right
;
296 uint8_t p2
= mv
[i
].to
+ up_left
;
297 uint8_t a
= OUT_OF_BOARD(p1
) ? 0 : board
.data
[p1
];
298 uint8_t b
= OUT_OF_BOARD(p2
) ? 0 : board
.data
[p2
];
299 if( (COLOR_OF(a
)==board
.other_color
&& PIECE_OF(a
)!=PAWN
)
300 || (COLOR_OF(b
)==board
.other_color
&& PIECE_OF(b
)!=PAWN
) )
302 int x
= board
.move_see_val(mv
[i
]);
306 mv
[i
].val
= 27000; /* pawn strike! */
316 int x
= board
.move_see_val(mv
[i
]);
319 if(prev
&& prev
->capture
&&
320 (mv
[i
].to
== prev
->to
) && (x
>= Board::simple_values
[PIECE_OF(prev
->capture
)]) )
323 if( (x
== Board::simple_values
[PIECE_OF(prev
->capture
)]) )
330 if(orig_depth
>-7*PLY
&& board
.move_is_check(mv
[i
]) )
336 else if(x
>=0 && orig_depth
>-7*PLY
&& board
.move_is_check(mv
[i
]) )
338 /* = capture but check */
343 else /* add a bonus for checks (but not too deep, or quiescence will get mad) */
344 if(board
.move_is_check(mv
[i
]) )
346 if(board
.move_see_val(mv
[i
])>=0)
353 /* null-move threat */
354 if(stack
[ply
-1].null_threat
== mv
[i
])
364 mv
[i
].val
+= (history_hit
[HISTORY_INDEX(mv
[i
])] + 32) * 1024/3 / (history_tot
[HISTORY_INDEX(mv
[i
])] + 64);
366 int mx
= CAPT_INDEX(mv
[i
]);
369 int ix
= FAST_PLUTO(p1
, mx
);
370 mv
[i
].val
+= (pluto_hit
[ix
] + 32) * 1024/3 / (pluto_tot
[ix
] + 64);
376 int ix
= FAST_PLUTO(p2
, mx
);
377 mv
[i
].val
+= (pluto2_hit
[ix
] + 32) * 1024/3 / (pluto2_tot
[ix
] + 64);
382 mv
[i
].val
+= (history_hit
[HISTORY_INDEX(mv
[i
])] + 32) * 256*4 / (history_tot
[HISTORY_INDEX(mv
[i
])] + 64);
386 static int bof
[128] = {
387 0,0,1,2,2,1,0,0,ENDL
,
388 0,1,2,3,3,2,1,0,ENDL
,
389 0,2,4,5,5,4,2,0,ENDL
,
390 1,2,5,6,6,5,2,1,ENDL
,
391 1,2,5,6,6,5,2,1,ENDL
,
392 0,2,4,5,5,4,2,0,ENDL
,
393 0,1,2,3,3,2,1,0,ENDL
,
397 /* add a bonus for moves towards the center */
398 mv
[i
].val
+= bof
[mv
[i
].to
];
399 //mv[i].val += (bof[mv[i].to] - bof[mv[i].from]);
400 #endif //CENTER_HEURISTIC
404 if(stack
[ply
-1].escape_from
[1] != INVALID
|| stack
[ply
-1].escape_from
[2] != INVALID
)
407 for(int i
=0;i
<num_escapes
;i
++)
408 mv
[escapes
[i
]].extend
= PLY
;
413 mv
[hash_move
].val
= 30000;
418 SearchRoot::moves_quiescence_heuristic(Move
*mv
, int num_mv
, const Move
& best_mv_hash
,
419 int static_eval
, int alpha
, int beta
, int orig_depth
, Move
* prev
)
421 for(int i
=0;i
<num_mv
;i
++)
426 /* give a high bonus to the move stored in the hash, if any.
427 mark only which is, don't continue, because some extensions
428 may be triggered ad added later (ie pawn strike, etc) */
429 if(mv
[i
].as_int
== best_mv_hash
.as_int
)
435 /* process strong pawn moves */
436 if(PIECE_OF(board
.data
[mv
[i
].from
])==PAWN
)
438 if( ROW_OF(mv
[i
].to
) == board
.seventh_rank
[IS_WHITE(board
.color_to_move
)] )
440 int x
= board
.move_see_val(mv
[i
]);
444 mv
[i
].val
+= 29499; /* 7th push */
445 mv
[i
].extend
= PLY
; /* extend search */
450 if( mv
[i
].flags
== PROMOTEQUEEN
)
452 int x
= board
.move_see_val(mv
[i
]);
456 mv
[i
].val
+= 29500; /* promote! */
457 mv
[i
].extend
= PLY
; /* extend search */
465 int x
= board
.move_see_val(mv
[i
]);
467 if(prev
&& prev
->capture
&&
468 (mv
[i
].to
== prev
->to
) && (x
>= Board::simple_values
[PIECE_OF(prev
->capture
)]) )
470 mv
[i
].val
= 29900 + x
;
471 if( (x
== Board::simple_values
[PIECE_OF(prev
->capture
)]) )
478 if(orig_depth
>=-5*PLY
&& board
.move_is_check(mv
[i
]) )
484 else if(x
>=0 && orig_depth
>=-5*PLY
&& board
.move_is_check(mv
[i
]) )
486 /* = capture but check */
491 else /* add a bonus for checks (but not too deep, or quiescence will get mad) */
492 if(orig_depth
>=-3*PLY
&& board
.move_is_check(mv
[i
]) )
494 if(board
.move_see_val(mv
[i
])>=0)
504 /*******************************************************************************
505 The main alpha-beta recursive search function.
506 It handles both normal search (with or without null move)
507 and quiescence search, because i have having 2 almost identical
509 *******************************************************************************/
510 int16_t SearchRoot::search(int ply
, int base_depth
, bool pv
, int16_t orig_alpha
, int16_t beta
, bool expect_allbad
)
512 SearchStack
*s
= &stack
[ply
];
514 uint16_t cbest_mv_hash
= 0; /* the compressed move from the hash */
515 Move best_mv_hash
= Move::FromInt(0); /* the move from the hash */
516 int best_mv_found
= -1; /* the index of the best move AFTER searching */
518 bool extended
= false;
519 bool no_good_moves
= false;
520 int16_t lower_bound
= -INF
;
521 int16_t position_val
;
522 int depth
= base_depth
;
523 int16_t alpha
= orig_alpha
;
528 for(int i
=ply
-1;i
>=0;i
--)
530 if(stack
[i
].curr_move
== -1)
531 board
.undo_null_move(stack
[i
].save_buf
);
532 else if(stack
[i
].curr_move
>= 0)
533 board
.undo_move(stack
[i
].moves
[stack
[i
].curr_move
], stack
[i
].save_buf
);
535 printf("[FEN \"%s\"]\n", board
.to_fen(BigStr().data()) );
536 for(int i
=0;i
<ply
;i
++)
538 printf(" %s", stack
[i
].curr_move
<= -1 ? "NULL" :
539 board
.move_to_alg(TmpStr().data(), stack
[i
].moves
[stack
[i
].curr_move
]));
540 if(stack
[i
].curr_move
== -1)
541 board
.do_null_move(stack
[i
].save_buf
);
542 else if(stack
[i
].curr_move
>= 0)
543 board
.do_move(stack
[i
].moves
[stack
[i
].curr_move
], stack
[i
].save_buf
);
549 // STAT(quiesce_nodes)
554 s
->null_threat
= Move::FromInt(0);
555 s
->null_threat_dangerous
= false;
557 stack
[ply
].escape_from
[1] = stack
[ply
].escape_from
[2] = INVALID
;
560 /* check if time is running out */
561 engine
->check_time();
563 /* check for a draw for repetition or 50mvs. Of course the draw for
564 repetition must be checked BEFORE probing the hash :)*/
566 return (board
.color_to_move
== engine
->st_computer_color
) ? engine
->v_eval_draw
:
567 ((board
.other_color
== engine
->st_computer_color
) ? -engine
->v_eval_draw
: 0); /* be aggressive! */
569 /*******************************************************************************
571 If the probe is succesful the hashtable will return us value
572 that can be exact, a lower bound or an upper bound, and if the
573 depth of the hashed search is >= the current depth this value
574 will be used to improve alpha and beta and possibly return immediatly.
575 The hastable will also give us a "best" move that will be searched
577 This is the move that caused the "final" cutoff when this position
578 was searched previously. This best move is actually the index of the best
579 move in the array of generated moves (it is supposed to be deterministic :)
580 *******************************************************************************/
582 HashEntry
*h
= engine
->probe_hash( board
.hash
);
585 GUI(notify_hash(ply
, h
->lo
, h
->up
, h
->depth
, alpha
, beta
,
586 h
->best_mv
? board
.uncompress_move(h
->best_mv
) : Move::None(), false,
587 (((h
->depth
>= base_depth
) && (h
->lo
>=beta
|| h
->up
==h
->lo
|| h
->up
<=alpha
))
588 ? SearchGui::Bold
: 0) | SearchGui::Magenta
) );
591 if(h
&& (h
->depth
>= base_depth
))// || ABS(h->value)>INF-1000) )
593 int16_t l
= h
->lower();
594 int16_t u
= h
->upper();
602 best
= alpha
= MAX(alpha
, l
);
606 cbest_mv_hash
= h
->best_mv
;
608 /*******************************************************************************
609 Test if we are under check, and if so extend search
610 *******************************************************************************/
612 s
->under_check
= board
.under_attack(board
.king_pos
[IS_WHITE(board
.color_to_move
)],
615 /*******************************************************************************
616 If it is time to quiesce, evaluate and test if we can exit
617 immediately with a beta cut-off (try first a rough eval - delta)
618 *******************************************************************************/
619 quiesce
= ((!s
->under_check
) && (depth
<=0)) || (depth
<-60*PLY
);
622 if(quiesce
&& depth
>=-PLY
)
625 Move
*mv
= mv_stack
+ mv_stack_top
;
626 board
.do_null_move();
627 num_mv
= board
.find_moves(mv
);
628 uint8_t pup
= INVALID
;
630 for(int i
=0;i
<num_mv
;i
++)
632 if(!mv
[i
].capture
|| PIECE_OF(mv
[i
].capture
)==PAWN
)
634 if(mv
[i
].to
!= pup
&& board
.move_see_val(mv
[i
])>0)
644 board
.undo_null_move();
648 if(quiesce
&& (best
== -INF
|| depth
<-60*PLY
) )
650 best
= board
.evaluate(engine
->st_computer_color
, alpha
, beta
);
651 lower_bound
= best
; //we have at the very least "best" as lower bound now.
652 GUI(notify_eval(ply
, best
, alpha
, beta
, best
>=beta
? SearchGui::Blue
|SearchGui::Bold
: SearchGui::Blue
));
654 alpha
= MAX(alpha
, best
);
662 if(quiesce
&& h
&& h
->no_good_moves
)
666 /*******************************************************************************
668 *******************************************************************************/
669 if(!expect_allbad
&& !pv
&& !s
->under_check
&& (stack
[ply
-1].curr_move
!= -1)
670 && depth
>= 2*PLY
&& beta
<WORST_MATE
&& null_move_ok())
673 int sdepth
= (depth
>= 5*PLY
) ? (depth
-4*PLY
) : depth
-3*PLY
;
676 board
.do_null_move(s
->save_buf
);
677 GUI1(notify(Move::None(), ply
, sdepth
, -INF
, beta
-1, beta
, SearchGui::Green
));
678 val
= -search( ply
+1, sdepth
, false, -beta
, -beta
+NULL_SOLIDITY_MARGIN
, false);
679 GUI2(notify_value(ply
, val
, DIFF_NODES
, SearchGui::Bold
));
680 board
.undo_null_move(s
->save_buf
);
686 #if NULL_SOLIDITY_MARGIN > 1
687 if(val
> beta
- NULL_SOLIDITY_MARGIN
)
691 if(val
< -WORST_MATE
)
692 s
->null_threat_dangerous
= true;
695 if(val
<alpha
-100 && /* we are facing a threat*/
696 stack
[ply
+1].best_move
!= -1) /* be sure we aren't reading random memory */
698 /* ok, officially the array stack[ply+1].moves has already
699 been deallocated, but who cares :) */
700 s
->threat
= stack
[ply
+1].moves
[stack
[ply
+1].best_move
];
703 /* Botvinnik-Markoff extension!!! */
704 if(!extended
&& ply
>=3 && (s
->threat
== stack
[ply
-2].threat
) )
717 /*******************************************************************************
718 Now generate the legal moves and look for a check/stalemate
719 *******************************************************************************/
721 /* generate all the legal moves */
722 s
->moves
= &mv_stack
[mv_stack_top
];
723 s
->num_moves
= board
.find_moves(s
->moves
);
724 mv_stack_top
+= s
->num_moves
;
725 s
->under_check
= board
.under_check
;
727 pluto1
= stack
[ply
-1].best_move
>=0 ? PLUTO1(stack
[ply
-1].moves
[stack
[ply
-1].best_move
]) : -1;
728 pluto2
= (ply
>=2 && stack
[ply
-1].best_move
>=0 && stack
[ply
-2].best_move
>=0) ?
729 PLUTO2(stack
[ply
-2].moves
[stack
[ply
-2].best_move
], stack
[ply
-1].moves
[stack
[ply
-1].best_move
]) : -1;
731 if(s
->under_check
==2) /* double check */
736 else if(s
->under_check
) /* simple check */
739 if(stack
[ply
-1].curr_move
>=0 &&
740 !board
.pins
[stack
[ply
-1].moves
[ /* last moved piece is not attacking the king */
741 stack
[ply
-1].curr_move
].to
]) /* so this is a discover check */
748 /* return now if the positon is terminal */
753 /* while mating, sacrify as much as possible :) */
754 int mt
= IS_WHITE(board
.other_color
) ? 5 : -1;
755 int16_t matval
= Board::simple_values
[PAWN
]*board
.mat_tracking
[mt
+PAWN
].count
+
756 Board::simple_values
[KNIGHT
]*board
.mat_tracking
[mt
+KNIGHT
].count
+
757 Board::simple_values
[BISHOP
]*board
.mat_tracking
[mt
+BISHOP
].count
+
758 Board::simple_values
[QUEEN
]*board
.mat_tracking
[mt
+QUEEN
].count
;
759 best
= alpha
= beta
= -INF
+ ply
*100 + matval
;
762 best
= alpha
= beta
= 0;
766 /* single-reply extension */
767 if(s
->num_moves
== 1 && !extended
)
772 else if(s
->num_moves
<= 3 && !extended
)
778 /*******************************************************************************
780 First comes the move from the hashtable, if avalable.
781 The remaining moves are sorted with a heuristic that keeps in account
782 the history heuristic (ie the moves that previously caused an alpha
783 cutoff), a MVV/LVA bonus value and a small bonus for moves that go
785 *******************************************************************************/
787 /* convert the move we got from the hash to the move structure */
790 best_mv_hash
= board
.uncompress_move(cbest_mv_hash
);
791 /* if it happened that the move we got from the hashtable
792 is not valid, simply no move will get the high
793 heuristic bonus value */
795 #if INTERNAL_ITERATIVE_DEEPENING
796 else if(base_depth
>3*PLY
&& pv
) /* don't do it only on the pv, or it will be useless :) */
799 GUI1(notify(Move::None(), ply
, base_depth
-2*PLY
, -INF
, alpha
, beta
, SearchGui::Blue
));
800 int val
= search(ply
+1, base_depth
-2*PLY
, true, alpha
, beta
, expect_allbad
);
801 GUI2(search_gui
->notify_value(ply
, val
, DIFF_NODES
, 0));
803 HashEntry
*h2
= probe_hash( board
.hash
);
804 if(h2
&& h2
->best_mv
)
806 cbest_mv_hash
= h2
->best_mv
;
807 best_mv_hash
= board
.uncompress_move(cbest_mv_hash
);
810 #endif //INTERNAL_ITERATIVE_DEEPENING
812 /* for each move calculate the heuristic goodness value */
814 Move
*prev
= (stack
[ply
-1].curr_move
>=0) ? &stack
[ply
-1].moves
[stack
[ply
-1].curr_move
] : NULL
;
816 moves_quiescence_heuristic( s
->moves
, s
->num_moves
, best_mv_hash
,
817 best
, alpha
, beta
, base_depth
, prev
);
821 moves_heuristic( s
->moves
, s
->num_moves
, pv
, ply
, base_depth
,
822 best_mv_hash
, quiesce
, prev
, &overall_ext
, expect_allbad
, pluto1
, pluto2
);
823 depth
+= overall_ext
;
827 /* if quiesce rip-off the "non-critical" moves */
831 for(int i
=0;i
<s
->num_moves
;i
++)
832 if(s
->moves
[i
].val
>0)
833 s
->moves
[n
++] = s
->moves
[i
];
834 mv_stack_top
-= s
->num_moves
-n
;
837 no_good_moves
= true;
840 /* Don't do it now, do it incrementally */
841 //sort_moves( s->moves, s->num_moves );
844 #if EARLY_TRANSP_CUTOFF
845 /*******************************************************************************
846 Try to get an early beta cutoff using the hash table values
847 of the following moves, and improve alpha too.
848 Try on the first 6 value of the ordered moves (argh, looking into the
849 hashtable is very expensive because of the cache!!!!!!!!)
850 *******************************************************************************/
854 HashKey hk
= board
.move_hash(s
->moves
[0]);
855 for(int i
=1;i
<s
->num_moves
;i
++)
857 engine
->prefetch_hash(hk
);
858 HashKey newhk
= board
.move_hash(s
->moves
[i
]);
859 HashEntry
*h2
= engine
->probe_hash( hk
);
862 if(h2
&& h2
->depth
>= depth
-PLY
)
869 alpha
= MAX(alpha
, (int16_t)-h2
->up
);
873 HashEntry
*h2
= engine
->probe_hash( hk
);
874 if(h2
&& h2
->depth
>= depth
-PLY
)
881 alpha
= MAX(alpha
, (int16_t)-h2
->up
);
884 #endif //EARLY_TRANSP_CUTOFF
886 /*******************************************************************************
887 It is now time to loop all the successor moves and search recursively.
888 *******************************************************************************/
891 /* calcluate the evaluation (required by fitility pruning) */
892 position_val
= quiesce
? best
: board
.dummy_evaluate(); //evaluate( st_computer_color, -INF, INF);
895 for(int i
=0;i
<s
->num_moves
;i
++)
898 int sdepth
= depth
-100;
900 /* sort moves incrementally, in the hope of a beta cut */
901 engine
->incremental_sort_moves(s
->moves
+i
, s
->num_moves
-i
);
903 /* extensions calculated during the heuristic sort */
904 sdepth
+= s
->moves
[i
].extend
;
907 /* futility pruning, it is done only if we are not under check
908 and the move is not a "critical" move */
909 if(depth
>0 && depth
<=2*PLY
&& !s
->under_check
&& s
->moves
[i
].val
< 28000)
911 static const int mavala
[] = { 0, 500, 325, 975, 325, 100, 0 };
913 int16_t fmargin
= (depth
<= PLY
? 240 : 620);
914 int16_t fval
= position_val
+ mavala
[PIECE_OF(s
->moves
[i
].capture
)];
915 if(fval
< alpha
-fmargin
)
922 int mx
= CAPT_INDEX(s
->moves
[i
]);
924 /* collect history statistics */
925 if(!s
->moves
[i
].capture
&&
926 !(s
->moves
[i
].flags
>=PROMOTE_FIRST
) )
928 int ix
= HISTORY_INDEX(s
->moves
[i
]);
929 if(history_tot
[ix
] > 1024)
931 history_tot
[ix
] = history_tot
[ix
]*7/8;
932 history_hit
[ix
] = history_hit
[ix
]*7/8;
934 history_tot
[ix
] += quiesce
? 8 : 16;
937 if(pluto1
!=-1 && !s
->moves
[i
].capture
&&
938 !(s
->moves
[i
].flags
>=PROMOTE_FIRST
))
940 int ix
= FAST_PLUTO(pluto1
, mx
);
941 if(pluto_tot
[ix
] > 1024)
943 pluto_tot
[ix
] = pluto_tot
[ix
]*7/8;
944 pluto_hit
[ix
] = pluto_hit
[ix
]*7/8;
946 pluto_tot
[ix
] += quiesce
? 8 : 16;
949 if(pluto2
!=-1 && !s
->moves
[i
].capture
&&
950 !(s
->moves
[i
].flags
>=PROMOTE_FIRST
))
952 int ix
= FAST_PLUTO(pluto2
, mx
);
953 if(pluto2_tot
[ix
] > 1024)
955 pluto2_tot
[ix
] = pluto2_tot
[ix
]*7/8;
956 pluto2_hit
[ix
] = pluto2_hit
[ix
]*7/8;
958 pluto2_tot
[ix
] += quiesce
? 8 : 16;
962 //Set data for pawn-strike
964 if(!quiesce
&& PIECE_OF(board
.data
[s
->moves
[i
].from
]) == PAWN
&& s
->moves
[i
].val
== 27000) //FIXME, UGLY
966 stack
[ply
].escape_from
[1] = s
->moves
[i
].to
+ Board::up_dir
[IS_WHITE(board
.color_to_move
)] + RIGHT
;
967 if(OUT_OF_BOARD(stack
[ply
].escape_from
[1]) || !IS_OF_COLOR(board
.data
[stack
[ply
].escape_from
[1]], board
.other_color
)
968 || PIECE_OF(board
.data
[stack
[ply
].escape_from
[1]])==PAWN
)
969 stack
[ply
].escape_from
[1] = INVALID
;
970 stack
[ply
].escape_from
[2] = s
->moves
[i
].to
+ Board::up_dir
[IS_WHITE(board
.color_to_move
)] + LEFT
;
971 if(OUT_OF_BOARD(stack
[ply
].escape_from
[2]) || !IS_OF_COLOR(board
.data
[stack
[ply
].escape_from
[2]], board
.other_color
)
972 || PIECE_OF(board
.data
[stack
[ply
].escape_from
[2]])==PAWN
)
973 stack
[ply
].escape_from
[2] = INVALID
;
977 stack
[ply
].escape_from
[1] = stack
[ply
].escape_from
[2] = INVALID
;
981 board
.do_move(s
->moves
[i
], s
->save_buf
);
986 if(base_depth
> 0 && sdepth
<= 0)
988 STAT(quiesce_called
);
989 q
= stat_quiesce_nodes
;
993 #if NEGA_SCOUT /* use negascout, (null window search for nodes that are not in the pv) */
994 if(i
== 0 && !expect_allbad
)
997 GUI1(notify(s
->moves
[i
], ply
, sdepth
, s
->moves
[i
].val
, alpha
, beta
, SearchGui::Bold
));
998 val
= -search( ply
+1, sdepth
, pv
, -beta
, -alpha
, !pv
);
999 GUI2(notify_value(ply
, val
, DIFF_NODES
, 0));
1004 bool red_fuck
= false;
1005 #if LATE_MOVE_REDUCTION
1006 /* history pruning, if this is not a "critical" move and the failhigh
1007 stats are too low, try a reduced depth search (if it returns >alpha,
1008 re-do the full depth search) */
1009 // if((sdepth>0) && !s->under_check && depth<=3*PLY && s->moves[i].val<28000 &&
1010 // (history_hit[HISTORY_INDEX(s->moves[i])]+1)*3
1011 // < (history_tot[HISTORY_INDEX(s->moves[i])]+1))
1012 if( (sdepth
>0) && !s
->under_check
&& !s
->null_threat_dangerous
1013 && s
->moves
[i
].val
<28000 && (s
->moves
[i
].val
<(sdepth
<=PLY
? 650 : 450)) )
1015 int rdepth
= depth
- 2*PLY
;
1016 //sdepth - PLY; //(s->moves[i].val<250 ? 2*PLY : PLY) - s->moves[i].extend;
1017 GUI1(notify(s
->moves
[i
], ply
, rdepth
, s
->moves
[i
].val
, alpha
, alpha
+1, SearchGui::Italic
|SearchGui::Gray
));
1018 val
= -search( ply
+1, rdepth
, false, -alpha
-1, -alpha
, false );
1019 GUI2(notify_value(ply
, val
, DIFF_NODES
, val
>alpha
? SearchGui::Red
: 0));
1021 goto skip_search
; /* reduced search was effective */
1025 GUI1(notify(s
->moves
[i
], ply
, sdepth
, s
->moves
[i
].val
, alpha
, alpha
+1, 0 ));
1026 val
= -search( ply
+1, sdepth
, false, -alpha
-1, -alpha
, red_fuck
);
1027 GUI2(notify_value(ply
, val
, DIFF_NODES
, val
>alpha
? SearchGui::Red
: 0));
1029 if((val
>alpha
) && pv
)
1031 GUI1(notify(s
->moves
[i
], ply
, sdepth
, -INF
, alpha
, beta
, SearchGui::Bold
));
1032 val
= -search( ply
+1, sdepth
, true, -beta
, -alpha
, false );
1033 GUI2(notify_value(ply
, val
, DIFF_NODES
, val
>beta
? SearchGui::Red
: 0));
1039 if(base_depth
> 0 && sdepth
<= 0)
1041 q
= stat_quiesce_nodes
-q
;
1042 if(q
> stat_max_quiesce_nodes
)
1044 stat_max_quiesce_nodes
= q
;
1045 max_quiesce_board
= board
;
1051 board
.undo_move(s
->moves
[i
], s
->save_buf
);
1053 /* update the current best value and check for and alpha cut */
1064 /* alpha improvement! */
1073 if(!expect_allbad
|| best
>= beta
)
1075 /* collect statistics for the history */
1076 if(/*best >= beta &&*/ (best_mv_found
!=-1) &&
1077 !s
->moves
[best_mv_found
].capture
&&
1078 !(s
->moves
[best_mv_found
].flags
>=PROMOTE_FIRST
) )
1079 history_hit
[HISTORY_INDEX(s
->moves
[best_mv_found
])] += quiesce
? 8 : 16;
1081 int mx
= CAPT_INDEX(s
->moves
[best_mv_found
]);
1082 if(pluto1
!=-1 && !s
->moves
[best_mv_found
].capture
&&
1083 !(s
->moves
[best_mv_found
].flags
>=PROMOTE_FIRST
))
1085 int ix
= FAST_PLUTO(pluto1
, mx
);
1086 pluto_hit
[ix
] += quiesce
? 8 : 16;
1089 if(pluto2
!=-1 && !s
->moves
[best_mv_found
].capture
&&
1090 !(s
->moves
[best_mv_found
].flags
>=PROMOTE_FIRST
))
1092 int ix
= FAST_PLUTO(pluto2
, mx
);
1093 pluto2_hit
[ix
] += quiesce
? 8 : 16;
1098 mv_stack_top
-= s
->num_moves
; /* free the moves we allocated */
1100 /* this is a null move, save what the threat is */
1101 if(stack
[ply
-1].curr_move
== -1 && best_mv_found
>= 0)
1102 stack
[ply
-1].null_threat
= s
->moves
[best_mv_found
];
1104 /* if we found a best move searching, that move will be saved.
1105 if we did no search (ie quiescence), save the old hash value,
1106 or -1 if no hash entry had been found */
1107 int bestmv
= cbest_mv_hash
;
1108 if(best_mv_found
>= 0)
1109 bestmv
= board
.compress_move(s
->moves
[best_mv_found
]);
1111 /* write the value in the hash, with the index of the best move */
1112 engine
->write_hash( board
.hash
,
1113 best
> orig_alpha
? MIN(best
, beta
) : lower_bound
,
1114 best
< beta
? best
: +INF
,
1115 MAX(base_depth
,-500), bestmv
, no_good_moves
);
1116 GUI(notify_hash(ply
, best
> s
->alpha
? MIN(best
, beta
) : lower_bound
, best
< beta
? best
: +INF
,
1117 MAX(base_depth
,-500), alpha
, beta
, bestmv
? board
.uncompress_move(bestmv
) : Move::None(), true,
1118 SearchGui::Bold
| SearchGui::Magenta
) );
1124 SearchRoot::SearchRoot(Engine
* e
, const Board
& b
)
1130 SearchRoot::~SearchRoot()
1134 Move
Engine::find_best_move()
1137 int base_depth
= PLY
;
1138 int num_mate_hits
= 0;
1139 SearchRoot
root(this, board
);
1140 SearchRoot::SearchStack
*s
= &root
.stack
[0];
1142 /* initialize the root node */
1145 s
->null_threat
= Move::FromInt(0);
1146 s
->null_threat_dangerous
= false;
1147 s
->moves
= root
.mv_stack
;
1148 s
->num_moves
= root
.mv_stack_top
= root
.board
.find_moves(s
->moves
);
1150 s
->escape_from
[1] = s
->escape_from
[2] = INVALID
;
1151 #endif //PAWN_STRIKE
1155 /* calculate how much time we will think*/
1156 start_think_time
= current_time();
1157 if(analysis_limit
== TIME_LIMIT
)
1159 if(board
.color_to_move
== st_computer_color
)
1161 else /* pondering? analysing? */
1162 time_best_csec
= 99999999;
1163 max_think_time
= start_think_time
+ time_best_csec
- 2;
1166 /* to print the analysis */
1168 output("\tply\tscore\ttime\tnodes\tpv\n");
1170 /* return immediatly if the move is forced. */
1174 output("\t0\t0\t0\t0\t%s (only move)\n", board
.move_to_alg(MoveStr().data(), s
->moves
[0]));
1178 /* probe the play lines */
1179 if(eng_status
== PLAYING
&& st_computer_color
== board
.color_to_move
)
1181 Move retv
= probe_lines(&root
.board
);
1186 output("\t0\t0\t0\t0\t%s (selected line)\n", board
.move_to_alg(MoveStr().data(), retv
));
1191 /* probe the book */
1192 Move bookmove
= probe_book(&root
.board
);
1193 if(bookmove
.valid())
1196 for(int i
=0;i
<s
->num_moves
++;i
++)
1197 if(bookmove
== s
->moves
[i
])
1199 output("Error!!! invalid move in the book!!!\n");
1203 IFGUI(reset_hash()); //Try to be deterministic
1204 processed_nodes
= 0;
1208 memset( root
.history_tot
, 0, HISTORY_SIZE
*sizeof(uint16_t));
1209 memset( root
.history_hit
, 0, HISTORY_SIZE
*sizeof(uint16_t));
1210 memset( root
.pluto_tot
, 0, PLUTO_SIZE
*sizeof(uint16_t));
1211 memset( root
.pluto_hit
, 0, PLUTO_SIZE
*sizeof(uint16_t));
1212 memset( root
.pluto2_tot
, 0, PLUTO_SIZE
*sizeof(uint16_t));
1213 memset( root
.pluto2_hit
, 0, PLUTO_SIZE
*sizeof(uint16_t));
1218 /* set the back jump for the quick thinking exit */
1223 /* do the iterative deepening thing. */
1226 int16_t alpha
= num_mate_hits
? -INF
: -WORST_MATE
;
1227 int16_t beta
= num_mate_hits
? INF
: WORST_MATE
;
1229 GUI(new_root_level(base_depth
));
1231 /* for each move call the alpha-beta search function */
1232 for(int i
=0;i
<s
->num_moves
;i
++)
1235 root
.board
.do_move(s
->moves
[i
], s
->save_buf
);
1240 GUI1(notify(s
->moves
[i
], 0, base_depth
-PLY
, s
->moves
[i
].val
, alpha
, beta
, SearchGui::Bold
));
1241 s
->moves
[i
].val
= -root
.search( 1, base_depth
-PLY
, true, -beta
, -alpha
, false );
1242 GUI2(notify_value(0, s
->moves
[i
].val
, DIFF_NODES
, 0));
1247 GUI1(notify(s
->moves
[i
], 0, base_depth
-PLY
, s
->moves
[i
].val
, alpha
, alpha
+1, 0 ));
1248 s
->moves
[i
].val
= -root
.search( 1, base_depth
-PLY
, false, -alpha
-1, -alpha
, false );
1249 GUI2(notify_value(0, s
->moves
[i
].val
, DIFF_NODES
, s
->moves
[i
].val
>alpha
? SearchGui::Red
: 0));
1251 if(s
->moves
[i
].val
> alpha
)
1253 GUI1(notify(s
->moves
[i
], 0, base_depth
-PLY
, -INF
, alpha
, beta
, SearchGui::Bold
));
1254 s
->moves
[i
].val
= -root
.search( 1, base_depth
-PLY
, true, -beta
, -alpha
, false );
1255 GUI2(notify_value(0, s
->moves
[i
].val
, DIFF_NODES
, 0));
1259 root
.board
.undo_move(s
->moves
[i
], s
->save_buf
);
1262 if(s
->moves
[i
].val
> alpha
)
1264 alpha
= s
->moves
[i
].val
;
1266 Move tmp
= s
->moves
[i
];
1267 for(int q
=i
-1;q
>=0;q
--)
1268 s
->moves
[q
+1] = s
->moves
[q
];
1271 /* this move caused an alpha cut, so print the new line */
1272 if( post
/*&& processed_nodes>100000*/)
1274 output("\t%d\t%d\t%d\t%llu\t",
1277 current_time() - start_think_time
,
1278 (unsigned long long)processed_nodes
);
1279 root
.print_pv(s
->moves
[0]);
1284 /* print the result of the analysis at this depth */
1285 if( post
/*&& processed_nodes>100000*/)
1287 output("\t%d\t%d\t%d\t%llu\t",
1290 current_time() - start_think_time
,
1291 (unsigned long long)processed_nodes
);
1292 root
.print_pv(s
->moves
[0]);
1296 if( base_depth
>= 40*PLY
)
1299 /* return in case of fixed depth search */
1300 if( eng_status
== PLAYING
&& st_computer_color
== board
.color_to_move
&&
1301 analysis_limit
== DEPTH_LIMIT
&& base_depth
== st_depth
*PLY
)
1304 /* return if 3/5 of time is gone (we can't search another ply anyway) */
1305 if( eng_status
== PLAYING
&& st_computer_color
== board
.color_to_move
&&
1306 analysis_limit
== TIME_LIMIT
&&
1307 (current_time()-start_think_time
) >= (time_best_csec
*3/5) )
1310 /* if a checkmate was detected return immediately */
1311 if( ABS(alpha
) > WORST_MATE
)
1314 if(num_mate_hits
>= 5)
1326 output("#max quiesce board: %s [%d %d]\n", max_quiesce_board
.to_fen(BigStr().data()),
1327 max_quiesce_alpha
, max_quiesce_beta
);