Skip to content
Permalink
Branch: master
Find file Copy path
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
710 lines (554 sloc) 23.9 KB
#include "stdafx.h"
#include "search.h"
#include "transposition.h"
/* symbols used to enhance readability */
#define DO_NULL 1
#define NO_NULL 0
#define IS_PV 1
#define NO_PV 0
sSearchDriver sd;
int draw_opening = -10; // middlegame draw value
int draw_endgame = 0; // endgame draw value
int ASPIRATION = 50; // size of the aspiration window ( val-ASPITATION, val+ASPIRATION )
bool time_over = 0;
enum eproto {
PROTO_NOTHING,
PROTO_XBOARD,
PROTO_UCI
} extern mode;
U8 bestmove; // move id passed between iterations for sorting purposes
smove move_to_make; // move to be returned when search runs out of time
/******************************************************************************
* search_run() is the only function called outside search.cpp, so it acts as *
* an interface. After some preparatory work it calls search_iterate(); *
******************************************************************************/
void search_run() {
if (chronos.flags & (FTIME | FINC | FMOVESTOGO)) {
if (getBookMove(BOOK_BROAD)) return;
}
search_clearDriver();
time_calc_movetime();
ageHistoryTable();
if (mode == PROTO_NOTHING) printSearchHeader();
search_iterate();
}
void search_clearDriver() {
sd.myside = b.stm; // remember color - needed in contempt()
sd.starttime = gettime();
sd.movetime = 0;
sd.depth = 0;
// now clear all the statistical data
sd.nodes = 0;
sd.q_nodes = 0;
}
/******************************************************************************
* search_iterate() calls search_root() with increasing depth until allocated *
* time is exhausted. *
******************************************************************************/
void search_iterate() {
int val;
// check the exact number of legal moves in the current position
int move_count = move_countLegal();
// do a full-window 1-ply search to get the first estimate of val
sd.depth = 1;
val = search_root(sd.depth, -INF, INF);
// main loop, increasing deph in steps of 1
for (sd.depth = 2; sd.depth <= MAX_DEPTH; sd.depth += 1) {
// breaking conditions - either expired time
// or just one legal reply and position searched to depth 4
if (time_stop_root() || time_over) break;
if (move_count == 1 && sd.depth == 5) break;
// this function deals with aspiration window
val = search_widen(sd.depth, val);
}
// after the loop has finished, send the move to the interface
com_sendmove(move_to_make);
}
int search_widen(int depth, int val) {
int temp = val,
alpha = val - 50,
beta = val + 50;
temp = search_root(sd.depth, alpha, beta);
if (temp <= alpha || temp >= beta)
temp = search_root(sd.depth, -INF, INF);
return temp;
}
int search_root(U8 depth, int alpha, int beta) {
int flagInCheck;
smove movelist[256];
int val = 0;
int best = -INF;
U8 currmove_legal = 0;
/* Check extension is done also at the root */
flagInCheck = isAttacked(!b.stm, b.king_loc[b.stm]);
if (flagInCheck) ++depth;
U8 mcount = movegen(movelist, bestmove);
for (U8 i = 0; i < mcount; i++) {
int cl = b.stm;
movegen_sort(mcount, movelist, i);
if (movelist[i].piece_cap == KING) {
alpha = INF;
bestmove = movelist[i].id;
}
move_make(movelist[i]);
// filter out illegal moves
if (isAttacked(b.stm, b.king_loc[!b.stm])) {
move_unmake(movelist[i]);
continue;
}
sd.cutoff[cl] [movelist[i].from][movelist[i].to] -= 1;
// if ( mode == PROTO_UCI && depth > 6)
// info_currmove( movelist[i], currmove_legal );
currmove_legal++;
/* the "if" clause introduces PVS at root */
if (best == -INF)
val = -Search(depth - 1, 0, -beta, -alpha, DO_NULL, IS_PV);
else
if (-Search(depth - 1, 0, -alpha - 1, -alpha, DO_NULL, NO_PV) > alpha)
val = -Search(depth - 1, 0, -beta, -alpha, DO_NULL, IS_PV);
if (val > best) best = val;
move_unmake(movelist[i]);
if (time_over) break;
if (val > alpha) {
bestmove = movelist[i].id;
move_to_make = movelist[i];
if (val > beta) {
tt_save(depth, beta, TT_BETA, bestmove);
info_pv(beta);
return beta;
}
alpha = val;
tt_save(depth, alpha, TT_ALPHA, bestmove);
info_pv(val);
} // changing node value finished
}
tt_save(depth, alpha, TT_EXACT, bestmove);
return alpha;
}
int Search(U8 depth, U8 ply, int alpha, int beta, int can_null, int is_pv) {
int val = -INF;
char bestmove;
char tt_move_index = (char)-1;
char tt_flag = TT_ALPHA;
int flagInCheck;
int raised_alpha = 0;
int f_prune = 0;
int reduction_depth = 0;
int moves_tried = 0;
int new_depth;
int mate_value = INF - ply; // will be used in mate distance pruning
smove movelist[256]; // move list
smove move; // current move
/**************************************************************************
* Probably later we will want to probe the transposition table. Here we *
* tell the cpu to prepare for that event. This is just a minor speed *
* optimization and program would run fine without that. *
**************************************************************************/
_mm_prefetch((char *)&tt[b.hash & tt_size], _MM_HINT_NTA);
/**************************************************************************
* Check for timeout. This is quite time-consuming, so we do it only every *
* every so often. The side effect is that if we want to limit search by *
* the number of nodes, it will be slightly inexact. *
**************************************************************************/
CheckInput(); // check for new commands or timeout
if (time_over) return 0;
/**************************************************************************
* MATE DISTANCE PRUNING, a minor improvement that helps to shave off some *
* some nodes when the checkmate is near. Basically it prevents looking *
* for checkmates taking longer than one we have already found. No Elo *
* gain expected, but it's a nice feature. Don't use it at the root, *
* since this code doesn't return a move, only a value. *
**************************************************************************/
if (alpha < -mate_value) alpha = -mate_value;
if (beta > mate_value - 1) beta = mate_value - 1;
if (alpha >= beta) return alpha;
/**************************************************************************
* Are we in check? If so, extend. It also means that program will never *
* never enter quiescence search while in check. *
**************************************************************************/
flagInCheck = (isAttacked(!b.stm, b.king_loc[b.stm]));
if (flagInCheck) depth += 1;
/**************************************************************************
* At leaf nodes we do quiescence search (captures only) to make sure *
* that only relatively quiet positions with no hanging pieces will be *
* evaluated. *
**************************************************************************/
if (depth < 1) return Quiesce(alpha, beta);
sd.nodes++;
if (isRepetition()) return contempt();
/**************************************************************************
* Read the transposition table. We may have already searched current *
* position. If depth was sufficient, then we might use the score *
* of that search. If not, hash move still is expected to be good *
* and should be sorted first. *
* *
* NOTE: current implementation is sub-standard, since tt_move is just *
* an index showing move's location on a move list. We should be able *
* to retrieve move without generating full move list instead. *
**************************************************************************/
if ((val = tt_probe(depth, alpha, beta, &tt_move_index)) != INVALID) {
// in pv nodes we return only in case of an exact hash hit
if (!is_pv || (val > alpha && val < beta)) {
/******************************************************************
* Here we must be careful about checkmate scoring. "Mate in n" *
* returned by transposition table means "mate in n if we start *
* counting n right now". Yet search always returns mate scores *
* as distance from root, so we must convert to that metric. *
* Other programs might hide similar code within tt_probe() and *
* tt_save() functions. *
******************************************************************/
if (abs(val) > INF - 100) {
if (val > 0) val -= ply;
else val += ply;
}
return val;
}
}
/**************************************************************************
* EVAL PRUNING / STATIC NULL MOVE *
**************************************************************************/
if (depth < 3
&& !is_pv
&& !flagInCheck
&& abs(beta - 1) > -INF + 100)
{
int static_eval = eval(alpha, beta, 1);
int eval_margin = 120 * depth;
if (static_eval - eval_margin >= beta)
return static_eval - eval_margin;
}
/**************************************************************************
* Here we introduce NULL MOVE PRUNING. It means allowing opponent *
* to execute two moves in a row, i.e. capturing something and escaping *
* a recapture. If this cannot wreck our position, then it is so good *
* that there's no point in searching further. The flag "can_null" *
* ensures we don't do two null moves in a row. Null move is not used *
* in the endgame because of the risk of zugzwang. *
**************************************************************************/
if (depth > 2
&& can_null
&& !is_pv
&& eval(alpha, beta, 1) > beta
&& b.piece_material[b.stm] > e.ENDGAME_MAT
&& !flagInCheck)
{
char ep_old = b.ep;
move_makeNull();
/**********************************************************************
* We use so-called adaptative null move pruning. Size of reduction *
* depends on remaining depth. *
**********************************************************************/
char R = 2;
if (depth > 6) R = 3;
val = -Search(depth - R - 1, ply + 1, -beta, -beta + 1, NO_NULL, NO_PV);
move_unmakeNull(ep_old);
if (time_over) return 0;
if (val >= beta) return beta;
} // end of null move code
/**************************************************************************
* RAZORING - if a node is close to the leaf and its static score is low, *
* we drop directly to the quiescence search. *
**************************************************************************/
if (!is_pv
&& !flagInCheck
&& tt_move_index == -1
&& can_null
// && !(bbPc(p, p->side, P) & bbRelRank[p->side][RANK_7]) // no pawns to promote in one move
&& depth <= 3) {
int threshold = alpha - 300 - (depth - 1) * 60;
if (eval(alpha, beta, 1) < threshold) {
val = Quiesce(alpha, beta);
if (val < threshold) return alpha;
}
} // end of razoring code
/**************************************************************************
* Decide if FUTILITY PRUNING is applicable. If we are not in check, *
* not searching for a checkmate and eval is below (alpha - margin), it *
* might mean that searching non-tactical moves at low depths is futile *
* so we set a flag allowing this pruning. *
**************************************************************************/
int fmargin[4] = { 0, 200, 300, 500 };
if (depth <= 3
&& !is_pv
&& !flagInCheck
&& abs(alpha) < 9000
&& eval(alpha, beta, 1) + fmargin[depth] <= alpha)
f_prune = 1;
/**************************************************************************
* Generate moves, then place special cases higher on the list *
**************************************************************************/
U8 mcount = movegen(movelist, tt_move_index);
ReorderMoves(movelist, mcount, ply);
bestmove = movelist[0].id;
/**************************************************************************
* Loop through the move list, trying them one by one. *
**************************************************************************/
for (int i = 0; i < mcount; i++) {
int cl = b.stm;
movegen_sort(mcount, movelist, i); // pick the best of untried moves
move = movelist[i];
move_make(move);
// filter out illegal moves
if (isAttacked(b.stm, b.king_loc[!b.stm])) {
move_unmake(move);
continue;
}
/**********************************************************************
* When the futility pruning flag is set, prune moves which do not *
* give check and do not change material balance. Some programs *
* prune insufficient captures as well, but that seems too risky. *
**********************************************************************/
if (f_prune
&& moves_tried
&& !move_iscapt(move)
&& !move_isprom(move)
&& !isAttacked(!b.stm, b.king_loc[b.stm])) {
move_unmake(move);
continue;
}
sd.cutoff[cl][move.from][move.to] -= 1;
moves_tried++;
reduction_depth = 0; // this move has not been reduced yet
new_depth = depth - 1; // decrease depth by one ply
/**********************************************************************
* Late move reduction. Typically a cutoff occurs on trying one of *
* the first moves. If it doesn't, we are probably in an all-node, *
* which means that all moves will fail low. So we might as well *
* spare some effort, searching to reduced depth. Of course this is *
* not a foolproof method, but it works more often than not. Still, *
* we need to exclude certain moves from reduction, in order to *
* filter out tactical moves that may cause a late cutoff. *
**********************************************************************/
if (!is_pv
&& new_depth > 3
&& moves_tried > 3
&& !isAttacked(!b.stm, b.king_loc[b.stm])
&& !flagInCheck
&& sd.cutoff[cl][move.from][move.to] < 50
&& (move.from != sd.killers[0][ply].from || move.to != sd.killers[0][ply].to)
&& (move.from != sd.killers[1][ply].from || move.to != sd.killers[1][ply].to)
&& !move_iscapt(move)
&& !move_isprom(move)) {
/******************************************************************
* Real programs tend to use more advanced formulas to calculate *
* reduction depth. Typically they calculate it from both remai- *
* ning depth and move count. Formula used here is very basic and *
* gives only a minimal improvement over uniform one ply reduction,*
* and is included for the sake of completeness only. *
******************************************************************/
sd.cutoff[cl][move.from][move.to] = 50;
reduction_depth = 1;
if (moves_tried > 6) reduction_depth += 1;
new_depth -= reduction_depth;
}
re_search:
/**********************************************************************
* The code below introduces principal variation search. It means *
* that once we are in a PV-node (indicated by IS_PV flag) and we *
* have found a move that raises alpha, we assume that the rest *
* of moves ought to be refuted. This is done relatively cheaply *
* by using a null-window search centered around alpha. Only if *
* this search fails high, we are forced repeat it with full window. *
* *
* Understanding the shorthand in the first two lines is a bit tricky *
* If alpha has not been raised, we might be either in a zero window *
* (scout) node or in an open window (pv) node, entered after a scout *
* search failed high. In both cases, we need to search with the same *
* alpha, the same beta AND the same node type. * *
**********************************************************************/
if (!raised_alpha)
val = -Search(new_depth, ply + 1, -beta, -alpha, DO_NULL, is_pv);
else {
// first try to refute a move - if this fails, do a real search
if (-Search(new_depth, ply + 1, -alpha - 1, -alpha, DO_NULL, NO_PV) > alpha)
val = -Search(new_depth, ply + 1, -beta, -alpha, DO_NULL, IS_PV);
}
/**********************************************************************
* Sometimes reduced search brings us above alpha. This is unusual, *
* since we expected reduced move to be bad in first place. It is *
* not certain now, so let's search to the full, unreduced depth. *
**********************************************************************/
if (reduction_depth
&& val > alpha) {
new_depth += reduction_depth;
reduction_depth = 0;
goto re_search;
}
move_unmake(move);
if (time_over) return 0;
/**********************************************************************
* We can improve over alpha, so we change the node value together *
* with the expected move. Also the raised_alpha flag, needed to *
* control PVS, is set. In case of a beta cuoff, when our position *
* is so good that the score will not be accepted one ply before, *
* we return it immediately. *
**********************************************************************/
if (val > alpha) {
bestmove = movelist[i].id;
sd.cutoff[cl][move.from][move.to] += 6;
if (val >= beta) {
/**************************************************************
* On a quiet move update killer moves and history table *
* in order to enhance move ordering. *
**************************************************************/
if (!move_iscapt(move)
&& !move_isprom(move)) {
setKillers(movelist[i], ply);
sd.history[b.stm][move.from][move.to] += depth*depth;
/**********************************************************
* With super deep search history table would overflow *
* - let's prevent it. *
**********************************************************/
if (sd.history[b.stm][move.from][move.to] > SORT_KILL) {
for (int cl = 0; cl < 2; cl++)
for (int a = 0; a < 128; a++)
for (int b = 0; b < 128; b++) {
sd.history[cl][a][b] = sd.history[cl][a][b] / 2;
}
}
}
tt_flag = TT_BETA;
alpha = beta;
break; // no need to search any further
}
raised_alpha = 1;
tt_flag = TT_EXACT;
alpha = val;
} // changing the node value is finished
} // end of looping through the moves
/**************************************************************************
* Checkmate and stalemate detection: if we can't find a legal move in *
* the current position, we test if we are in check. If so, mate score *
* relative to search depth is returned. If not, we use draw score pro- *
* vided by contempt() function. *
**************************************************************************/
if (!moves_tried) {
bestmove = -1;
if (flagInCheck) alpha = -INF + ply;
else alpha = contempt();
}
/* tt_save() does not save anything when the search is timed out */
tt_save(depth, alpha, tt_flag, bestmove);
return alpha;
}
void setKillers(smove m, U8 ply) {
/* if a move isn't a capture, save it as a killer move */
if (m.piece_cap == PIECE_EMPTY) {
/* make sure killer moves will be different
before saving secondary killer move */
if (m.from != sd.killers[ply][0].from
|| m.to != sd.killers[ply][0].to)
sd.killers[ply][1] = sd.killers[ply][0];
/* save primary killer move */
sd.killers[ply][0] = m;
}
}
void ReorderMoves(smove * m, U8 mcount, U8 ply) {
for (int j = 0; j<mcount; j++) {
if ((m[j].from == sd.killers[ply][1].from)
&& (m[j].to == sd.killers[ply][1].to)
&& (m[j].score < SORT_KILL - 1)) {
m[j].score = SORT_KILL - 1;
}
if ((m[j].from == sd.killers[ply][0].from)
&& (m[j].to == sd.killers[ply][0].to)
&& (m[j].score < SORT_KILL)) {
m[j].score = SORT_KILL;
}
}
}
int info_currmove(smove m, int nr) {
switch (mode) {
case PROTO_UCI:
char buffer[64];
char move[6];
algebraic_writemove(m, move);
sprintf(buffer, "info depth %d currmove %s currmovenumber %d", (int)sd.depth, move, nr + 1);
com_send(buffer);
}
return 0;
}
int info_pv(int val) {
char buffer[2048];
char score[10];
char pv[2048];
if (abs(val) < INF - 2000) {
sprintf(score, "cp %d", val);
}
else {
//the mating value is returned in moves not plies ( thats why /2+1)
if (val > 0) sprintf(score, "mate %d", (INF - val) / 2 + 1);
else sprintf(score, "mate %d", -(INF + val) / 2 - 1);
}
U32 nodes = (U32)sd.nodes;
U32 time = gettime() - sd.starttime;
util_pv(pv);
if (mode == PROTO_NOTHING)
sprintf(buffer, " %2d. %9u %5u %5d %s", (int)sd.depth, nodes, time / 10, val, pv);
else
sprintf(buffer, "info depth %d score %s time %u nodes %u nps %u pv %s", (int)sd.depth, score, time, nodes, countNps(nodes, time), pv);
com_send(buffer);
return 0;
}
/******************************************************************************
* countNps() guards against overflow and thus cares for displaying correct *
* nps during longer searches. Node count is converted from U64 to unsigned *
* int because of some problems with output. *
******************************************************************************/
unsigned int countNps(unsigned int nodes, unsigned int time) {
if (time == 0) return 0;
if (time > 20000) return nodes / (time / 1000);
else return (nodes * 1000) / time;
}
/******************************************************************************
* Checking if the current position has been already encountered on the cur- *
* rent search path. Function does NOT check the number of repetitions. *
******************************************************************************/
int isRepetition() {
for (int i = 0; i < b.rep_index; i++) {
if (b.rep_stack[i] == b.hash)
return 1;
}
return 0;
}
/******************************************************************************
* Clearing the history table is needed at the beginning of a search starting *
* from a new position, like at the beginning of a new game. *
******************************************************************************/
void clearHistoryTable() {
for (int cl = 0; cl < 2; cl++)
for (int i = 0; i < 128; i++)
for (int j = 0; j < 128; j++) {
sd.history[cl][i][j] = 0;
sd.cutoff[cl][i][j] = 100;
}
}
/******************************************************************************
* ageHistoryTable() is run between searches to decrease the history values *
* used for move sorting. This causes obsolete information to disappear gra- *
* dually. Clearing the table was worse for the move ordering. *
******************************************************************************/
void ageHistoryTable() {
for (int cl = 0; cl < 2; cl++)
for (int i = 0; i < 128; i++)
for (int j = 0; j < 128; j++) {
sd.history[cl][i][j] = sd.history[cl][i][j] / 8;
sd.cutoff[cl][i][j] = 100;
}
}
/******************************************************************************
* contempt() returns a draw value (which may be non-zero) relative to the *
* side to move and to the game stage. This way we may make our program *
* play for a draw or strive to avoid it. *
******************************************************************************/
int contempt() {
int value = draw_opening;
if (b.piece_material[sd.myside] < e.ENDGAME_MAT)
value = draw_endgame;
if (b.stm == sd.myside) return value;
else return -value;
}
void CheckInput() {
if (!time_over && !(sd.nodes & 4095))
time_over = time_stop();
}
You can’t perform that action at this time.