search.cpp

Go to the documentation of this file.

/*---------------------------------------------------------------------+
 * File: search.cpp
 * Project: part of belofte - A Promising Chess Program
 * Author: yves
 * SPDX-License-Identifier: GPL-2.0-only
+----------------------------------------------------------------------*/
 
#include "belofte.h"
 
//-----------------------------------------------------------------------
 
/**
 * Generic search, will call (non-)recursive method per algorithm
 * only when there are moves to be played
 * @param b initial board
 * @param ml movelist of this position
 */
void bSearchAlgorithm::SearchBestMove(bBoard& b, bMoveList& ml)
{
  StartSearch(b.minimizing());
 
  /// @todo Add debug manipulator
  std::stringstream ss;
  ss << "Searching started: " << this->operator std::string() << " "
          << getLevel()->operator std::string()
          << (b.whiteToMove() ? " For white" : " For Black");
  m_appei->sendInfoSearchStart(ss.str());
 
  b.clearVariation();
  b.setPreviousMoves({});
  b.calcMinorPieces();
  b.calcGameStage();
 
  m_leafnodes = 0LL;
  m_nonleafnodes = 0LL;
  initMaxSearchedDepth();
 
  gameResult_t gr = PosEvalPiecesOnly::gameEndedResult(b);
  if (gr != GR_UNKNOWN && isNoBench()) {
    m_appei->sendInfo("engine should not have started searching as position is final");
    m_appei->sendResult(b, gr);
    throw gameEndException();
  }
 
  if (ml.atLeastOneMovePossible(b)) {
    if ((m_iterativesearch)
            && (getLevel()->getType() != LevelType::MateSearch)) {
      SearchBestMoveIterative(b, ml);
    } else {
      CalcBestMove(b, ml);
    }
  } else {
    StopSearch();
    if (isNoBench())
      m_appei->sendError("no move found", getDuration());
    if (!m_iterativesearch) return;
 
    throw noMoveFoundException();
  }
 
  dumpMoveList(b, 0);
}
 
//-----------------------------------------------------------------------
 
void bSearchAlgorithm::SearchBestMoveIterative(bBoard& b, bMoveList& ml)
{
  int8_t nFluctuations = 0;
  depth_t iCurrentDepth = 1;
  bScore score;
 
  ml.generateMoves(b);
 
  std::string sPreviousBestMove, sNewBestMove;
 
  while (iCurrentDepth <= getLevel()->getMaxDepth()) {
    getLevel()->setSearchDepth(iCurrentDepth);
 
    std::string sDepth = "(depth " + belofte::to_string(iCurrentDepth) + ")";
    m_appei->sendDebug(1, "Iterative Depth Search " + sDepth);
 
    // clear search variation of previous searches in current position
    b.clearVariation();
 
    try {
      score = CalcBestMove(b, ml);
      {
        int64_t nNodes = m_leafnodes + m_nonleafnodes;
        #if defined(NPS_LOG)
          int64_t nDuration = getDurationMicroSec();
          if (nDuration < 1) nDuration = 1;
          long nNPS = nNodes * 1000000 / nDuration;
          m_appei->sendInfoDepth(iCurrentDepth, m_maxDepth, nNodes, static_cast<int>(nNPS));
        #else
          m_appei->sendInfoDepth(iCurrentDepth, m_maxDepth, nNodes, 0);
        #endif
      }
    } catch (const searchAbortedException&) {
      sendInfoSearching(b, 0, "abort search " + sDepth, score);
      break;
    } catch (...) { throw; // push other exceptions down
    }
 
    if (!bSearchScore::isUndefinedScore(score)) {
      // quit loop in case of absolute score
      if (bSearchScore::realScore(score) > SCORE_WINNING) {
        sendInfoSearching(b, 0, "winning " + sDepth, score);
        break;
      }
      // quit loop in case of getting mated
      if (bSearchScore::realScore(score) < -SCORE_WINNING) {
        sendInfoSearching(b, 0, "getting mated " + sDepth, score);
        break;
      }
    }
 
    // retrieve bestmove
    if (!b.getVariation().empty()) {
      sNewBestMove = b.getVariation()[0];
    }
 
    if (!sPreviousBestMove.empty()
            && (sNewBestMove != sPreviousBestMove)
            && iCurrentDepth > 3) {
      // there is an update to the bestmove found in this iteration
      // so increase time for allowing a further iteration
      ++nFluctuations;
      getLevel()->setMoreTimeRequired();
      bBoard nb(b);
      sendInfoSearching(nb, 0, "increase time for search");
    }
 
    // quit loop if not enough time left for another iteration
    if (!getLevel()->stillTimeLeft(iCurrentDepth, getDurationMilliSec())) {
      sendInfoSearching(b, 0, "no more search time allotted " + sDepth, score);
      break;
    } else if (sPreviousBestMove.empty() && !sNewBestMove.empty()) {
      sendInfoSearching(b, 0, "bestmove set " + sDepth + " done", score);
      sPreviousBestMove = sNewBestMove;
    } else if (sNewBestMove != sPreviousBestMove) {
      sendInfoSearching(b, 0, "bestmove updated " + sDepth + " done", score);
      sPreviousBestMove = sNewBestMove;
    } else {
      sendInfoSearching(b, 0, sDepth + " done", score);
    }
 
    if (iCurrentDepth < getLevel()->getMaxDepth()) {
      dumpMoveList(b, iCurrentDepth);
      ml.sortMoves();
    }
    ++iCurrentDepth;
  }
}
 
//-----------------------------------------------------------------------
 
void bSearchAlgorithm::StartSearch(bScore const sc)
{
  m_aborting = false;
  ClockStart();
  m_minimizing = sc;
  m_postlevel = App().sout.getLevel(); // cache value
  setLevel(&(Game()->getLevel())); // copy level from game-level to search
  m_appei = AppEI();
  m_evalptr = Game()->getEval();
}
 
void bSearchAlgorithm::CheckIfAbortingSearch() const
{
  /// @todo: limit calls to getDurationMilliSec
  if (m_aborting
          || m_levelptr->stoppingSearch(getDurationMilliSec()))
    throw searchAbortedException();
}
 
//-----------------------------------------------------------------------
 
void bSearchAlgorithm::dumpMoveList(bBoard const& b, depth_t const iDepth) const
{
  /// @todo check if we stream to sout, last element does not use outputWriter
  /// but ostream, this is why we stream to stringstream first
  bPgnMoveList ml(b);
  std::stringstream ss;
  if (iDepth) ss << "depth " << belofte::to_string(iDepth) << " ";
  ss << "ml " << ml;
  m_appei->sendDebug(51, ss.str());
}
 
//-----------------------------------------------------------------------
 
void bSearchAlgorithm::sendInfoSearching(bBoard const& b,
        depth_t const nDepth, std::string const& comment) const
{
  if (nDepth <= m_postlevel) { // speedup
    if (comment != "") {
      m_appei->sendInfoSearching(b, nDepth, m_maxDepth, comment, SCORE_UNDEFINED,
              getDurationMilliSec(), m_leafnodes + m_nonleafnodes);
    } else {
      m_appei->sendInfoSearching(b, nDepth, m_maxDepth, SCORE_UNDEFINED,
              getDurationMilliSec(), m_leafnodes + m_nonleafnodes);
    }
  }
}
 
bScore bSearchAlgorithm::sendInfoSearching(bBoard const& b,
        depth_t const nDepth, std::string const& comment,
        bScore const sc) const
{
  if (nDepth <= m_postlevel) { // speedup
    if (comment != "") {
      m_appei->sendInfoSearching(b, nDepth, m_maxDepth,
              comment, sc * m_minimizing * b.minimizing(), getDurationMilliSec(),
              m_leafnodes + m_nonleafnodes);
    } else {
      m_appei->sendInfoSearching(b, nDepth, m_maxDepth,
              sc * m_minimizing * b.minimizing(), getDurationMilliSec(),
              m_leafnodes + m_nonleafnodes);
    }
  }
  return sc;
}
 
void bSearchAlgorithm::sendInfoCurrMove(bBoard const& b,
        depth_t const nCurDepth,
        bMove const& m,
        movenum_t const moveid) const
{
  if (nCurDepth < m_postlevel) {
    m_appei->sendInfoCurrMove(b, nCurDepth,
            m, moveid, m_leafnodes + m_nonleafnodes);
  }
}
 
//-----------------------------------------------------------------------
 
/**
 * Get score of board, eventually from cache
 * @param b board
 * @param gr previous gameresult
 * @return score of board, either from cache, from gr or caclulated
 */
bScore bSearchAlgorithm::RetrieveBoardEvaluation(bBoard& b, gameResult_t gr) const
{
  if (gr == GR_UNSET) {
    gr = bPositionEvaluation::gameEndedResult(b);
  }
  if (gr != GR_UNKNOWN) {
    // gr is a forced end
    return bPositionEvaluation::resultToScoreFlag(gr);
  }
  return m_evalptr->getEvaluation(b) * b.minimizing();
}
 
//-----------------------------------------------------------------------
 
// eof