ChessUSA.com TalkChess.com
Hosted by Your Move Chess & Games
 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

Root node search
Post new topic    TalkChess.com Forum Index -> Computer Chess Club: Programming and Technical Discussions Flat
View previous topic :: View next topic  
Author Message
Onno Garms



Joined: 12 Mar 2007
Posts: 224
Location: Bonn, Germany

PostPost subject: Root node search    Posted: Sun Mar 13, 2011 7:28 pm Reply to topic Reply with quote

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:


// 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
}

Back to top
View user's profile Send private message
Display posts from previous:   
Subject Author Date/Time
Root node search Onno Garms Sun Mar 13, 2011 7:28 pm
Post new topic    TalkChess.com Forum Index -> Computer Chess Club: Programming and Technical Discussions

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum




Powered by phpBB © 2001, 2005 phpBB Group
Enhanced with Moby Threads