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"
 
//-----------------------------------------------------------------------
 
bSearchScore::bSearchScore(bSearchScore const& sc) noexcept
  : m_score{sc.m_score}
  , m_type{sc.m_type}
{
}
 
bSearchScore::bSearchScore(bSearchScore&& sc) noexcept
  : m_score{std::move(sc.m_score)}
  , m_type{std::move(sc.m_type)}
{
}
 
bSearchScore::bSearchScore(bScore const& sc) noexcept
  : m_score{sc}
{
}
 
bSearchScore::bSearchScore(bScore const& sc, scoretype_t const& st) noexcept
  : m_score{sc}
  , m_type{st}
{
}
 
bSearchScore& bSearchScore::operator=(bSearchScore&& sc) noexcept
{
  m_score = std::move(sc.m_score);
  m_type  = std::move(sc.m_type);
 
  return *this;
}
 
bSearchScore& bSearchScore::operator=(bScore const& sc) noexcept
{
  m_score = sc;
 
  return *this;
}
 
bSearchScore& bSearchScore::operator=(bScore&& sc) noexcept
{
  m_score = std::move(sc);
 
  return *this;
}
 
bSearchScore::~bSearchScore()
{
}
 
bSearchScore bSearchScore::operator-() const
{
  if (!m_type) {
    bSearchScore(-m_score);
  } else if (m_type == tScoreType::SC_ALPHA) {
    return bSearchScore(-m_score, tScoreType::SC_BETA);
  } else if (m_type == tScoreType::SC_BETA) {
    return bSearchScore(-m_score, tScoreType::SC_ALPHA);
  }
  return bSearchScore(-m_score, m_type);
}
 
std::string const operator+(std::string const& lhs, bSearchScore const& sc)
{
  return lhs + sc.operator std::string();
}
 
std::string const operator+(bSearchScore const& sc, std::string const& rhs)
{
  return sc.operator std::string() + rhs;
}
 
bool operator>(bScore const& lhsc, bSearchScore const& rhsc)
{
  return lhsc > rhsc.getRealScore();
}
 
bool operator>=(bScore const& lhsc, bSearchScore const& rhsc)
{
  return lhsc >= rhsc.getRealScore();
}
 
bool operator>(bSearchScore const& lhsc, bScore const& rhsc)
{
  return lhsc.getRealScore() > rhsc;
}
 
bool operator>(bSearchScore const& lhsc, bSearchScore const& rhsc)
{
  return lhsc.getRealScore() > rhsc.getRealScore();
}
 
bSearchScore::operator std::string() const
{
  if (!m_type) {
    return belofte::scoreAsStr(m_score);
#if defined(BELOFTE_NOUNICODE)
  } else if (m_type == tScoreType::SC_ALPHA) {
    return "alpha: " + belofte::scoreAsStr(m_score);
  } else if (m_type == tScoreType::SC_BETA) {
    return "beta: " + belofte::scoreAsStr(m_score);
  } else if (m_type == tScoreType::SC_CHILD) {
    return "search: " + belofte::scoreAsStr(m_score);
  } else if (m_type == tScoreType::SC_BEST) {
    return "best: " + belofte::scoreAsStr(m_score);
#else
  } else if (m_type == tScoreType::SC_ALPHA) {
    return "𝛼: " + belofte::scoreAsStr(m_score);
  } else if (m_type == tScoreType::SC_BETA) {
    return "𝛽: " + belofte::scoreAsStr(m_score);
  } else if (m_type == tScoreType::SC_CHILD) {
    return "⅀: " + belofte::scoreAsStr(m_score);
  } else if (m_type == tScoreType::SC_BEST) {
    return "↑: " + belofte::scoreAsStr(m_score);
#endif
  }
  return belofte::scoreAsStr(m_score);
}
 
//-----------------------------------------------------------------------
 
bSearchAlgorithm::bSearchAlgorithm(std::string const& n)
  : m_aborting{false}
  , m_name{n}
  , m_levelptr{nullptr}
{
}
 
bSearchAlgorithm::~bSearchAlgorithm()
{
  m_levelptr = nullptr;
  m_name = "";
}
 
//-----------------------------------------------------------------------
 
/**
 * Generic search, will call (non-)recursive method per algorithm
 * only when there are moves to be played
 * @param b initial board
 */
bBestMoveInfo bSearchAlgorithm::SearchBestMove(bBoard& b)
{
  StartSearch(b.minimizing());
  bBestMoveInfo result;
 
  // TODO: Add debug manipulator
  std::stringstream ss;
  ss << "Searching started: " << this->operator std::string() << " "
          << getLevel()->operator std::string()
          << (b.whiteToMove() ? " For white" : " For Black");
  AppEI()->sendInfo(ss.str());
 
  b.clearVariation();
  b.setPreviousMoves({});
 
  bMoveList& ml = b.getMoveListRef();
  movenum_t n_moves = ml.generateMoves(b);
  ml.sortMoves();
  RetrieveBoardEvaluation(b);
  m_nodes = 0LL;
  m_nonleafnodes = 0LL;
  m_maxDepth = 0;
 
  if (n_moves) {
    if ((m_iterativesearch)
            && (getLevel()->getType() != LevelType::MateSearch)) {
      result = SearchBestMoveIterative(b);
    } else {
      CalcBestMove(b);
    }
  } else {
    StopSearch();
    AppEI()->sendError("no move found", getDuration());
 
    throw noMoveFoundException();
  }
 
  result.moveid = ml.sortMoves(); // TODO: retrieve best move id without sorting it on top
  dumpMoveList(b, 0);
 
  result.score = ml[result.moveid].getScore();
  //sendInfoScore(b, 0, result.score);
  return result;
}
 
//-----------------------------------------------------------------------
 
bBestMoveInfo bSearchAlgorithm::SearchBestMoveIterative(bBoard& b)
{
  depth_t iCurrentDepth = 1;
  bBestMoveInfo result;
 
  bMoveList& ml = b.getMoveListRef();
  ml.generateMoves(b);
 
  while (iCurrentDepth <= getLevel()->getMaxDepth()) {
    getLevel()->setSearchDepth(iCurrentDepth);
 
    std::string sDepth = "(depth " + belofte::to_string(iCurrentDepth) + ")";
    AppEI()->sendDebug(1, "Iterative Depth Search " + sDepth);
 
    try {
      result.score = CalcBestMove(b);
      sendInfoSearching(b, 0, sDepth + " done", result.score);
      int64_t nNodes = m_nodes + m_nonleafnodes;
      int64_t nDuration = getDurationMicroSec();
      if (nDuration < 1) nDuration = 1;
      long nNPS = nNodes * 1000000 / nDuration;
      AppEI()->sendInfoDepth(iCurrentDepth, m_maxDepth, nNodes, static_cast<int>(nNPS));
    } catch (const searchAbortedException&) {
      sendInfoSearching(b, 0, "abort search " + sDepth, result.score);
      break;
    } catch (...) { throw; // push other exceptions down
    }
 
    if ((result.score & SCORE_POSITIVE) != SCORE_PUNDEFINED) {
      // quit loop in case of absolute score
      if (belofte::realScore(result.score) > SCORE_WINNING) {
        sendInfoSearching(b, 0, "winning " + sDepth, result.score);
        break;
      }
      // quit loop in case of getting mated
      if (belofte::realScore(result.score) < -SCORE_WINNING) {
        sendInfoSearching(b, 0, "getting mated " + sDepth, result.score);
        break;
      }
    }
 
    // quit loop if not enough time left for another iteration
    if (!getLevel()->stillTimeLeft(iCurrentDepth, getDurationMilliSec())) {
      sendInfoSearching(b, 0, "not enough time left " + sDepth, result.score);
      break;
    }
 
    iCurrentDepth++;
    if (iCurrentDepth <= getLevel()->getMaxDepth()) {
      dumpMoveList(b, iCurrentDepth - 1);
      //sendInfoScore(b, 0, result.score);
      ml.sortMoves();
    }
  }
  return result;
}
 
//-----------------------------------------------------------------------
 
void bSearchAlgorithm::StartSearch(bScore const m)
{
  m_aborting = false;
  ClockStart();
  m_minimizing = m;
  m_postlevel = App().sout.getLevel(); // cache value
  setLevel(&(Game()->getLevel())); // copy level from game-level to search
}
 
void bSearchAlgorithm::StopSearch()
{
  m_aborting = false;
  ClockEnd();
}
 
void bSearchAlgorithm::InterruptSearch()
{
  m_aborting = true;
}
 
void bSearchAlgorithm::CheckIfAbortingSearch() const
{
  // TODO: limit calls to getDurationMilliSec
  if (m_aborting
          || m_levelptr->stoppingSearch(getDurationMilliSec()))
    throw searchAbortedException();
}
 
//-----------------------------------------------------------------------
 
void bSearchAlgorithm::dumpMoveList(bBoard& b, depth_t const iDepth) const
{
  // TOCHECK: 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;
  AppEI()->sendDebug(51, ss.str());
}
 
//-----------------------------------------------------------------------
 
bScore bSearchAlgorithm::sendInfoSearching(bBoard const& b,
        depth_t const nDepth, std::string const& c,
        bScore const sc) const
{
  if (nDepth <= m_postlevel) { // speedup
    AppEI()->sendInfoSearching(b, nDepth, m_maxDepth,
#if !defined(_DEBUG)
            this->operator std::string() + " " +
#endif
            c, sc * m_minimizing * b.minimizing(), getDurationMilliSec(),
            m_nodes + m_nonleafnodes);
  }
  return sc;
}
 
bScore bSearchAlgorithm::sendInfoScore(bBoard const& b,
        depth_t const nDepth,
        bScore const sc) const
{
  if (nDepth <= m_postlevel) { // speedup
    AppEI()->sendInfoScore(getDurationMilliSec(), b,
            sc * m_minimizing * b.minimizing());
  }
  return sc;
}
 
void bSearchAlgorithm::sendInfoCurrMove(bBoard const& b, depth_t const nDepth,
        movenum_t const moveid) const
{
  if (nDepth < m_postlevel) {
    // speedup
    AppEI()->sendInfoCurrMove(b, nDepth, m_maxDepth, this->operator std::string(),
            b.getMove(moveid), moveid, m_nodes + m_nonleafnodes);
  }
}
 
//-----------------------------------------------------------------------
 
/**
 * Cache score of board
 * @param b board
 */
bScore bSearchAlgorithm::RetrieveBoardEvaluation(bBoard& b) const
{
  bScore sc = b.getBoardEvaluation();
  if (sc == SCORE_UNDEFINED) {
    sc = Game()->EvalForPlayer(b);
    b.setBoardEvaluation(sc);
  }
  return sc;
}
 
/** converge score towards zero in order to force immediate best move
 *  first
 */
bScore bSearchAlgorithm::attenuateScore(bScore const sc) const
{
  // make sure theoretic draw does not oscillate
  if ((sc & SCORE_POSITIVE) == SCORE_THEORETIC_DRAW) return SCORE_THEORETIC_DRAW;
  if ((sc & SCORE_POSITIVE) == SCORE_PUNDEFINED) return SCORE_UNDEFINED;
 
  // special score values are kept
  if ((sc & SCORE_POSITIVE) > SCORE_ALMOST_NORMAL) return sc;
  // do not converge if close to zero
  if ((sc & SCORE_POSITIVE) < SCORE_ALMOST_DRAW) return sc;
 
  if (sc > 0) return sc - SCORE_CONVERGE_BYDEPTH;
  return sc + SCORE_CONVERGE_BYDEPTH;
}
 
//-----------------------------------------------------------------------
 
// eof