Root node search

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Post Reply
User avatar
Onno Garms
Posts: 224
Joined: Mon Mar 12, 2007 6:31 pm
Location: Bonn, Germany

Root node search

Post by Onno Garms » Sun Mar 13, 2011 7:28 pm

It is well known that search at root node should be done differently
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&#58;&#58;cerr << "<"
              << "root "
              << "depth=\"" << p_depth << "\" "
              << "value=\"" << v_pv_list&#91;0&#93;.value&#40;) << "\" "
              << ">" << std&#58;&#58;endl;
  &#125;
#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&#58;&#58;scout_min_depth ? p_num_moves &#58; p_multi_pv;

  
  // loop over moves
  // ------------------------------------------------------------

  if &#40;d_terminator->interrupt&#40;))
    return;

  for &#40;int i=0; i<p_num_moves; ++i&#41;
  &#123;
    // prepare examination of move
    // .........................................................

    Move&#58;&#58;_ move = v_pv_list&#91;i&#93;.bestmove&#40;);

    // get search window
    /*
      @tried&#58; Not windowing at all makes the engine significantly weaker.
      @tried&#58; 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 &#40;i<num_full_search&#41;
    &#123;
      if &#40;p_depth==1&#41;
      &#123;
        alpha = -ValueNode&#58;&#58;infty;
        beta  = ValueNode&#58;&#58;infty;
      &#125;
      else
      &#123;
        alpha = v_pv_list&#91;i&#93;.value&#40;) - SearchRootRc&#58;&#58;window_distance;
        beta  = v_pv_list&#91;i&#93;.value&#40;) + SearchRootRc&#58;&#58;window_distance;
      &#125;
    &#125;
    else
    &#123;
      // get worst value for that a full search has been done
      scout_value = v_pv_list&#91;num_full_search-1&#93;.value&#40;);
      // reuse alpha and beta from previous iteration
    &#125;

    // when num_full_search is exeeded we are not far from finishing current depth
    if &#40;i>=num_full_search&#41;
      d_terminator->send_extend ();

    // send to uci
    d_callback->send_currmove &#40;move, i&#41;;
    
    // get new search depth
    d_new_depth->set_final_height &#40;p_depth&#41;;
    int new_depth = (*d_new_depth&#41; &#40;p_depth, 0, p_board, move, NodeType&#58;&#58;pv&#41;;

    // count move
    d_node_counter->inc&#40;0&#41;;
#ifdef OG_LOG_SEARCH
    if &#40;SearchRootRc&#58;&#58;log && EventLogger&#58;&#58;next&#40;))
    &#123;
      std&#58;&#58;cerr << EventLogger&#58;&#58;number&#40;)
                << " " << g_messenger.rank&#40;) << "&#58;"
                << " Search&#58;&#58;inc_nodes " << d_node_counter->total&#40;)
                << std&#58;&#58;endl;
    &#125;
    Board board = p_board;
    Undo undo;
    board.get_undo (&undo&#41;;
    board.do_move &#40;move, &undo&#41;;
#endif

    // evaluate the move
    // .........................................................
    if &#40;i<num_full_search&#41;
    &#123;
      d_search_inner &#40;new_depth, p_board, move, -beta, -alpha, NodeType&#58;&#58;pv, &reply_pv&#41;;
      if &#40;reply_pv.value&#40;) <= -beta&#41;
      &#123;
        // pv move has not changed, so we can savely update pv
        if &#40;d_terminator->interrupt&#40;))
          return;
        v_pv_list&#91;i&#93;.assign &#40;move, reply_pv&#41;;
        d_callback->send_move_data &#40;d_node_counter->total&#40;), d_tbhit_counter->total&#40;), v_pv_list&#91;i&#93;, Status&#58;&#58;failhigh&#41;;
        d_callback->send_pv &#40;i&#41;;
        if &#40;i==0&#41;
        &#123;
          d_terminator->send_pv &#40;v_pv_list&#91;0&#93;.bestmove&#40;), v_pv_list&#91;0&#93;.value&#40;), Status&#58;&#58;failhigh&#41;;
        &#125;
        // research
        d_search_inner &#40;new_depth, p_board, move, -ValueNode&#58;&#58;infty, -alpha, NodeType&#58;&#58;pv, &reply_pv&#41;;
      &#125;
      else if &#40;reply_pv.value&#40;) >= -alpha&#41;
      &#123;
        // pv move has not changed, so we can savely update pv
        if &#40;d_terminator->interrupt&#40;))
          return;
        v_pv_list&#91;i&#93;.assign &#40;move, reply_pv&#41;;
        d_callback->send_move_data &#40;d_node_counter->total&#40;), d_tbhit_counter->total&#40;),
                                    v_pv_list&#91;i&#93;, Status&#58;&#58;faillow&#41;;
        d_callback->send_pv &#40;i&#41;;
        if &#40;i==0&#41;
        &#123;
          d_terminator->send_pv &#40;v_pv_list&#91;0&#93;.bestmove&#40;), v_pv_list&#91;0&#93;.value&#40;), Status&#58;&#58;faillow&#41;;
        &#125;
        // research
        d_search_inner &#40;new_depth, p_board, move, -beta, ValueNode&#58;&#58;infty, NodeType&#58;&#58;pv, &reply_pv&#41;;
      &#125;
    &#125;

    else
    &#123;
      d_search_inner &#40;new_depth, p_board, move,
                      -scout_value-1, -scout_value,
                      NodeType&#58;&#58;cut, &reply_pv&#41;;
      
      if &#40;reply_pv.value&#40;) < -scout_value&#41;
      &#123;
        // do not update pv here, might be false positive (@tried, makes engine weaker&#41;
        
        if &#40;scout_value < beta&#41;
        &#123;
          // research with a bit larger window
          d_search_inner &#40;new_depth, p_board, move,
                          -beta, -scout_value,
                          NodeType&#58;&#58;pv, &reply_pv&#41;;
          // research again with full window
          if &#40;reply_pv.value&#40;) <= -beta&#41; // cannot happen if beta is beyond mate score
          &#123;
            d_search_inner &#40;new_depth, p_board, move,
                            -ValueNode&#58;&#58;infty, -scout_value,
                            NodeType&#58;&#58;pv, &reply_pv&#41;;
          &#125;
        &#125;
        else
        &#123;
          // research
          d_search_inner &#40;new_depth, p_board, move,
                          -ValueNode&#58;&#58;infty, -scout_value,
                          NodeType&#58;&#58;pv, &reply_pv&#41;;
        &#125;
      &#125;
      
      // only scout search done, expected faillow occured&#58;
      // we do not know exact move value
      if &#40;reply_pv.value&#40;) >= -scout_value&#41;
        reply_pv.set_value &#40;ValueNode&#58;&#58;infty&#41;;
    &#125;

    // postprocess evaluation
    // .........................................................

#ifdef OG_LOG_SEARCH
    board.undo_move &#40;move, undo&#41;;
#endif

    // test for interrupt
    if &#40;d_terminator->interrupt&#40;))
      return;

    // update pv and send to uci
    int new_idx = escalate_pv &#40;reply_pv, i, v_pv_list&#41;;
    d_callback->send_move_data &#40;d_node_counter->total&#40;), d_tbhit_counter->total&#40;),
                                v_pv_list&#91;new_idx&#93;, Status&#58;&#58;exact&#41;;
    d_callback->send_pv &#40;new_idx&#41;;
    d_terminator->send_pv &#40;v_pv_list&#91;0&#93;.bestmove&#40;), v_pv_list&#91;0&#93;.value&#40;), Status&#58;&#58;exact&#41;;
  &#125;


  // finalize
  // ------------------------------------------------------------

  // make sure that pv is in trans
  // &#40;in most cases it will be there anyway, but there might have been overwrites&#41;
  store_pv_in_trans &#40;p_board, v_pv_list&#91;0&#93;, d_trans_map&#41;;

  // write xml dump
#ifdef OG_LOG_SEARCH
  if &#40;SearchRootRc&#58;&#58;log_nodes&#41;
  &#123;
    std&#58;&#58;cerr << "<Result" << std&#58;&#58;endl
              << "pv=\"" << v_pv_list&#91;0&#93; << "\"" << std&#58;&#58;endl
              << "/>" << std&#58;&#58;endl
              << "</root>" << std&#58;&#58;endl;

  &#125;
#endif
&#125;


Post Reply