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(true);
  b.calcGameStage();
 
  m_leafnodes = 0LL;
  m_nonleafnodes = 0LL;
  initMaxSearchedDepth();
 
  gameResult_t gr = PosEvalPiecesOnly::gameEndedResult(b);
  if (gr != GR_UNKNOWN && isNoBench()) {
    StopSearch();
    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 {
      try {
        CalcBestMove(b, ml);
      } catch (const searchAbortedException&) {
        sendInfoSearching(b, 0, "abort non iterative search");
      } catch (...) { throw; // push other exceptions down
      }
    }
    StopSearch();
  } else {
    StopSearch();
    if (isNoBench())
      m_appei->sendError("no move found", getDuration());
    if (!m_iterativesearch) return;
 
    throw noMoveFoundException();
  }
  dumpMoveList(ml, 0);
}
 
//-----------------------------------------------------------------------
 
void bSearchAlgorithm::SearchBestMoveIterative(bBoard& b, bMoveList& ml)
{
  depth_t iCurrentDepth = 1;
  bScore score;
 
  if (ml.generateMoves(b)) {
    // in case we break out of search early, take first move
    // as back-up move
    ml.setBestMoveId(1);
    // we sort moves so best move candidate is searched first
    ml.sortMoves(false);
  }
 
  movenum_t n_moves = ml.getNumberOfMoves();
  movenum_t n_QSmoves = ml.getNumberOfQSMoves();
 
  std::string sPreviousBestMove;
  std::string sNewBestMove;
 
  while (iCurrentDepth <= getLevel()->getMaxDepth()) {
    getLevel()->setSearchDepth(iCurrentDepth);
 
    std::string sDepthLBL = " (depth " + belofte::to_string(iCurrentDepth) + ")";
    m_appei->sendInfo("ItSearch started at" + sDepthLBL);
 
    // 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(NO_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
      }
      // retrieve bestmove, note in case of abort, b has been restored
      // so take it from ml if possible
      if (!b.getVariation().empty()) {
        sNewBestMove = b.getVariation()[0];
        if (sNewBestMove == sPreviousBestMove) {
          m_appei->sendInfo("ItSearch Best move unchanged: " + sNewBestMove + sDepthLBL);
        } else if (sPreviousBestMove.empty()) {
          m_appei->sendInfo("ItSearch Best move found: " + sNewBestMove + sDepthLBL);
        } else {
          m_appei->sendInfo("ItSearch Best move updated: " + sNewBestMove + sDepthLBL);
        }
      }
      bCoordMove cm(ml[ml.getBestMoveId()]);
      if (!sNewBestMove.empty() && sNewBestMove != static_cast<std::string>(cm)) {
        m_appei->sendInfo("ItSearch Inconsistency with PV: " + static_cast<std::string>(cm) + " vs " + sNewBestMove + sDepthLBL);
      }
    } catch (const searchAbortedException&) {
      if (iCurrentDepth < 2) {
        /// @todo this is a special case, abort even without doing a good iteration
        sendInfoSearching(b, 0, "ItSearch early abort search" + sDepthLBL);
      }
      if ((ml.curmoveid > 2) && (n_moves > 1)) {
        // the movelist has been handling at least one two moves completely at new depth
        // and there is at least 2 moves
        bCoordMove cm(ml[ml.getBestMoveId()]);
        if (sPreviousBestMove != static_cast<std::string>(cm)) {
          sendInfoSearching(b, 0, "ItSearch partial search best move update: " + static_cast<std::string>(cm) + sDepthLBL);
        } else {
          score = ml.getBestMoveScore();
          sendInfoSearching(b, 0, "ItSearch abort partial search" + sDepthLBL, score);
        }
      } else if (ml.curmoveid > 1) {
        // only one move has been searched, it could be worse than
        // the result at previous depth
        /// @todo get score of second best move and compare it
        bCoordMove cm(ml[ml.getBestMoveId()]);
        if (sPreviousBestMove != static_cast<std::string>(cm)) {
          sendInfoSearching(b, 0, "ItSearch initial search best move update: " + static_cast<std::string>(cm) + sDepthLBL);
        } else {
          sendInfoSearching(b, 0, "ItSearch abort initial search" + sDepthLBL);
        }
      } else {
        // abort during search of first move
        sendInfoSearching(b, 0, "ItSearch abort search at" + sDepthLBL);
      }
      break;
    } catch (...) { throw; // push other exceptions down
    }
 
    // quit loop in case of absolute score
    // realscore is converting forced draw to 0
    if (bSearchScore::realScore(score) > SCORE_INFINITE) {
      sendInfoSearching(b, 0, "ItSearch mating opponent" + sDepthLBL, score);
      break;
    }
    // quit loop in case of getting mated
    if (bSearchScore::realScore(score) < -SCORE_INFINITE) {
      sendInfoSearching(b, 0, "ItSearch getting mated" + sDepthLBL, score);
      break;
    }
    // quit loop in case there is only one move
    if (n_moves == 1) {
      sendInfoSearching(b, 0, "ItSearch there is only one move" + sDepthLBL, score);
      break;
    }
 
    if (!sPreviousBestMove.empty()
            && (sNewBestMove != sPreviousBestMove)) {
      // there is an update to the bestmove found in this iteration
      // so increase time for allowing a further iteration
      getLevel()->setMoreTimeRequired();
      m_appei->sendInfo("ItSearch increase time for search");
    }
 
    // quit loop if not enough time left for another iteration
    if (!getLevel()->stillTimeLeft(iCurrentDepth, getDurationMilliSec(), n_QSmoves, n_moves)) {
      sendInfoSearching(b, 0, "ItSearch not enough time for more depth" + sDepthLBL + " done", score);
      break;
    } else if (sPreviousBestMove.empty() && !sNewBestMove.empty()) {
      sendInfoSearching(b, 0, "ItSearch bestmove set" + sDepthLBL + " done", score);
      sPreviousBestMove = sNewBestMove;
    } else if (sNewBestMove != sPreviousBestMove) {
      sendInfoSearching(b, 0, "ItSearch bestmove updated" + sDepthLBL + " done", score);
      sPreviousBestMove = sNewBestMove;
    } else {
      sendInfoSearching(b, 0, "ItSearch searching ended at" + sDepthLBL + " done", score);
    }
 
    if (iCurrentDepth < getLevel()->getMaxDepth()) {
      dumpMoveList(ml, iCurrentDepth);
      ml.sortMoves(false);
    }
    ++iCurrentDepth;
  }
}
 
//-----------------------------------------------------------------------
 
void bSearchAlgorithm::StartSearch(bScore const sc)
{
  m_aborting = false;
  Game()->setSearching(true);
  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::StopSearch()
{
  m_aborting = false;
  ClockEnd();
  Game()->setSearching(false);
}
 
//-----------------------------------------------------------------------
 
void bSearchAlgorithm::dumpMoveList(bMoveList const& ml, depth_t const iDepth) const
{
  std::stringstream ss;
  if (iDepth) ss << "depth " << belofte::to_string(iDepth) << " ";
  ss << "ml " << ml;
  m_appei->sendInfo(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
 * @param bRecalcFirst recalculate pieces first
 * @return score of board, either from cache, from gr or caclulated
 */
bScore bSearchAlgorithm::RetrieveBoardEvaluation(bBoard& b,
        gameResult_t gr, bool const bRecalcFirst) const
{
  if (gr == GR_UNSET) {
    gr = bPositionEvaluation::gameEndedResult(b);
  }
  if (gr != GR_UNKNOWN) {
    // gr is a forced end
    return bPositionEvaluation::resultToScoreFlag(gr);
  }
  if (bRecalcFirst) b.calcMinorPieces(false);
  return m_evalptr->getEvaluation(b, gr) * b.minimizing();
}
 
/**
 * Get score of board, eventually from cache, from whites view
 * @param b board
 * @param gr previous gameresult
 * @param bRecalcFirst recalculate pieces first
 * @return score of board, either from cache, from gr or caclulated
 */
bScore bSearchAlgorithm::RetrieveBoardEvaluationForWhite(bBoard& b,
        gameResult_t gr, bool const bRecalcFirst) const
{
  if (gr == GR_UNSET) {
    gr = bPositionEvaluation::gameEndedResult(b);
  }
  if (gr != GR_UNKNOWN) {
    // gr is a forced end
    return bPositionEvaluation::resultToScoreFlag(gr);
  }
  if (bRecalcFirst) b.calcMinorPieces(false);
  return m_evalptr->getEvaluation(b, gr);
}
 
//-----------------------------------------------------------------------
 
// eof