from the other nodes. Especially windowing at root node is
useful. However when I started with Onno it was apparently not so
clear which things are the best to do at root node.
At least, Fruit and Toga implemented an inferior root node
search. Fruit did not do windowing at all. When you start to think
about what Toga does at root node, you soon arrive the conclusion that
this a very questionable algorithm (especially: handling of fail-highs
and fail-lows; multi-PV). I did not study what Stockfish does at root
node, most likely it is better there.
I will just post what Onno does. Tested and definitely better then
what Fruit or Toga does. I leave the comparison to Stockfish to do for others.
The caller creates the moves and passes them in v_pv_list. Caller does
iterative deeping. The function below gets a v_pv_list that was
computed and sorted with p_depth-1 (just the moves if p_depth==1) and
returns a sorted v_pv_list computed with p_depth.
Coding convention:
d_ member variables (d as data)
p_ input parameters (p as parameter)
v_ inout parameters (v as VAR in Pascal)
r_ output parameters (r as result)
Classes begin with a capital, words are separated by intercaps.
Variables only contain lower case letters, words are separated by underscores
Move::_ and similar are enums.
Code: Select all
// Test for interrupt every time before updating v_pv_list.
void SearchRoot::root_search (int p_depth,
const Board& p_board,
int p_multi_pv,
int p_num_moves, PV* v_pv_list)
{
#ifdef OG_LOG_SEARCH
if (SearchRootRc::log_nodes)
{
std::cerr << "<"
<< "root "
<< "depth=\"" << p_depth << "\" "
<< "value=\"" << v_pv_list[0].value() << "\" "
<< ">" << std::endl;
}
#endif
// prepare
// ------------------------------------------------------------
// best reply to move
PV reply_pv;
// search window
int alpha, beta;
// value for scout search
int scout_value;
// number of moves where not to use scout search
int num_full_search = p_depth<SearchRootRc::scout_min_depth ? p_num_moves : p_multi_pv;
// loop over moves
// ------------------------------------------------------------
if (d_terminator->interrupt())
return;
for (int i=0; i<p_num_moves; ++i)
{
// prepare examination of move
// .........................................................
Move::_ move = v_pv_list[i].bestmove();
// get search window
/*
@tried: Not windowing at all makes the engine significantly weaker.
@tried: When root node search was quit with failhighs, windowing on value 0 made
the engine significantly weaker.
I dont't fully understand why, maybe because value 0 is due to repetition
and not very stable.
When doing research on failhighs and not quitting search prematurely,
there seemed to be little difference whether windowing on value 0 or not.
*/
if (i<num_full_search)
{
if (p_depth==1)
{
alpha = -ValueNode::infty;
beta = ValueNode::infty;
}
else
{
alpha = v_pv_list[i].value() - SearchRootRc::window_distance;
beta = v_pv_list[i].value() + SearchRootRc::window_distance;
}
}
else
{
// get worst value for that a full search has been done
scout_value = v_pv_list[num_full_search-1].value();
// reuse alpha and beta from previous iteration
}
// when num_full_search is exeeded we are not far from finishing current depth
if (i>=num_full_search)
d_terminator->send_extend ();
// send to uci
d_callback->send_currmove (move, i);
// get new search depth
d_new_depth->set_final_height (p_depth);
int new_depth = (*d_new_depth) (p_depth, 0, p_board, move, NodeType::pv);
// count move
d_node_counter->inc(0);
#ifdef OG_LOG_SEARCH
if (SearchRootRc::log && EventLogger::next())
{
std::cerr << EventLogger::number()
<< " " << g_messenger.rank() << ":"
<< " Search::inc_nodes " << d_node_counter->total()
<< std::endl;
}
Board board = p_board;
Undo undo;
board.get_undo (&undo);
board.do_move (move, &undo);
#endif
// evaluate the move
// .........................................................
if (i<num_full_search)
{
d_search_inner (new_depth, p_board, move, -beta, -alpha, NodeType::pv, &reply_pv);
if (reply_pv.value() <= -beta)
{
// pv move has not changed, so we can savely update pv
if (d_terminator->interrupt())
return;
v_pv_list[i].assign (move, reply_pv);
d_callback->send_move_data (d_node_counter->total(), d_tbhit_counter->total(), v_pv_list[i], Status::failhigh);
d_callback->send_pv (i);
if (i==0)
{
d_terminator->send_pv (v_pv_list[0].bestmove(), v_pv_list[0].value(), Status::failhigh);
}
// research
d_search_inner (new_depth, p_board, move, -ValueNode::infty, -alpha, NodeType::pv, &reply_pv);
}
else if (reply_pv.value() >= -alpha)
{
// pv move has not changed, so we can savely update pv
if (d_terminator->interrupt())
return;
v_pv_list[i].assign (move, reply_pv);
d_callback->send_move_data (d_node_counter->total(), d_tbhit_counter->total(),
v_pv_list[i], Status::faillow);
d_callback->send_pv (i);
if (i==0)
{
d_terminator->send_pv (v_pv_list[0].bestmove(), v_pv_list[0].value(), Status::faillow);
}
// research
d_search_inner (new_depth, p_board, move, -beta, ValueNode::infty, NodeType::pv, &reply_pv);
}
}
else
{
d_search_inner (new_depth, p_board, move,
-scout_value-1, -scout_value,
NodeType::cut, &reply_pv);
if (reply_pv.value() < -scout_value)
{
// do not update pv here, might be false positive (@tried, makes engine weaker)
if (scout_value < beta)
{
// research with a bit larger window
d_search_inner (new_depth, p_board, move,
-beta, -scout_value,
NodeType::pv, &reply_pv);
// research again with full window
if (reply_pv.value() <= -beta) // cannot happen if beta is beyond mate score
{
d_search_inner (new_depth, p_board, move,
-ValueNode::infty, -scout_value,
NodeType::pv, &reply_pv);
}
}
else
{
// research
d_search_inner (new_depth, p_board, move,
-ValueNode::infty, -scout_value,
NodeType::pv, &reply_pv);
}
}
// only scout search done, expected faillow occured:
// we do not know exact move value
if (reply_pv.value() >= -scout_value)
reply_pv.set_value (ValueNode::infty);
}
// postprocess evaluation
// .........................................................
#ifdef OG_LOG_SEARCH
board.undo_move (move, undo);
#endif
// test for interrupt
if (d_terminator->interrupt())
return;
// update pv and send to uci
int new_idx = escalate_pv (reply_pv, i, v_pv_list);
d_callback->send_move_data (d_node_counter->total(), d_tbhit_counter->total(),
v_pv_list[new_idx], Status::exact);
d_callback->send_pv (new_idx);
d_terminator->send_pv (v_pv_list[0].bestmove(), v_pv_list[0].value(), Status::exact);
}
// finalize
// ------------------------------------------------------------
// make sure that pv is in trans
// (in most cases it will be there anyway, but there might have been overwrites)
store_pv_in_trans (p_board, v_pv_list[0], d_trans_map);
// write xml dump
#ifdef OG_LOG_SEARCH
if (SearchRootRc::log_nodes)
{
std::cerr << "<Result" << std::endl
<< "pv=\"" << v_pv_list[0] << "\"" << std::endl
<< "/>" << std::endl
<< "</root>" << std::endl;
}
#endif
}