search_ab.cpp

Go to the documentation of this file.

/*---------------------------------------------------------------------+
 * File: search_ab.cpp
 * Project: part of belofte - A Promising Chess Program
 * Author: yves
 * SPDX-License-Identifier: GPL-2.0-only
+----------------------------------------------------------------------*/
 
#include "belofte.h"
 
//-----------------------------------------------------------------------
 
#if defined(BELOFTE_NOUNICODE)
#define GTOREQUAL " >= "
#else
#define GTOREQUAL " ≥ "
#endif
 
//-----------------------------------------------------------------------
// class SearchAlphaBeta
//-----------------------------------------------------------------------
 
#if defined(__GNUC__)
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Weffc++"
#endif
 
SearchAlphaBeta::SearchAlphaBeta()
  : bSearchAlgorithm("AB")
  , m_bEarlyBetaCutOff{false}
  , m_bEarlyQSBetaCutOff{true}
  , m_bFailSoft{true}
  , m_nBetaCutOffMargin{SCORE_BETAMARGIN}
  , m_bAttenuateScore{true}
{
  m_iterativesearch = true;
}
 
SearchAlphaBeta::SearchAlphaBeta(std::string const& s)
  : bSearchAlgorithm(s)
  , m_bEarlyBetaCutOff{false}
  , m_bEarlyQSBetaCutOff{true}
  , m_bFailSoft{true}
  , m_nBetaCutOffMargin{SCORE_BETAMARGIN}
  , m_bAttenuateScore{true}
{
  m_iterativesearch = true;
}
 
SearchAlphaBeta::~SearchAlphaBeta()
{
}
 
bBestMoveInfo SearchAlphaBeta::CalcBestMove(bBoard& b)
{
  return CalcBestMove(b, 0,
          bSearchScore(-SCORE_INFINITE, tScoreType::SC_ALPHA),
          bSearchScore(SCORE_INFINITE, tScoreType::SC_BETA));
}
 
//-----------------------------------------------------------------------
// class SearchAlphaBetaFS
//-----------------------------------------------------------------------
 
SearchAlphaBetaFS::SearchAlphaBetaFS()
  : SearchAlphaBeta("ABFS")
{
  m_bEarlyBetaCutOff = true;
}
 
SearchAlphaBetaFS::~SearchAlphaBetaFS()
{
}
 
//-----------------------------------------------------------------------
// class SearchAlphaBetaFH
//-----------------------------------------------------------------------
 
SearchAlphaBetaFH::SearchAlphaBetaFH()
  : SearchAlphaBeta("ABFH")
{
  m_bEarlyBetaCutOff = true;
  m_bFailSoft = false;
  m_nBetaCutOffMargin = SCORE_BETAMARGIN / 2;
}
 
SearchAlphaBetaFH::~SearchAlphaBetaFH()
{
}
 
//-----------------------------------------------------------------------
// class TerminalNode - helper class to quit early search
//-----------------------------------------------------------------------
 
TerminalNode::TerminalNode(bBoard& b, depth_t const& nDepth,
        bSearchScore const& alpha, bSearchScore const& beta, bSearchAlgorithm* algo)
  : m_isTerminal{true}
{
  movenum_t n_moves = b.generateAtLeastOneMove();
  m_terminalscore = algo->RetrieveBoardEvaluation(b);
 
  algo->sendInfoSearching(b, nDepth, alpha
          + " " + beta
          + " static: " + belofte::scoreAsStr(m_terminalscore)
          + " material: " + belofte::scoreAsStr(b.getMaterialEvaluation())
          + (b.isInCheck() ? " check" : ""), m_terminalscore);
 
  if ((m_terminalscore & SCORE_POSITIVE) == SCORE_THEORETIC_DRAW) {
    m_terminalscore = algo->sendInfoSearching(b, nDepth, "(th. draw)", SCORE_THEORETIC_DRAW);
  } else {
    if (!n_moves) {
      algo->sendInfoSearching(b, nDepth, "(dead position)", m_terminalscore);
    } else {
      m_isTerminal = false;
    }
  }
}
 
TerminalNode::TerminalNode(bBoard& b, depth_t const& nDepth,
        bSearchScore const& alpha, bSearchScore const& beta, uint8_t const& nCheckCount,
        bSearchAlgorithm* algo)
  : m_isTerminal{true}
{
  movenum_t n_moves = b.generateAtLeastOneMove();
  m_terminalscore = algo->RetrieveBoardEvaluation(b);
 
  algo->sendInfoSearching(b, nDepth, "qs " + alpha
          + " " + beta
          + " static: " + belofte::scoreAsStr(m_terminalscore)
          + (b.isInCheck() ? " check" : "")
          + " +: " + belofte::to_string(nCheckCount), m_terminalscore);
 
  if ((m_terminalscore & SCORE_POSITIVE) == SCORE_THEORETIC_DRAW) {
    m_terminalscore = algo->sendInfoSearching(b, nDepth, "qs (th. draw)", SCORE_THEORETIC_DRAW);
  } else {
    if (!n_moves) {
      algo->sendInfoSearching(b, nDepth, "qs (dead position)", m_terminalscore);
    } else {
      m_isTerminal = false;
    }
  }
}
 
#if defined(__GNUC__)
#pragma GCC diagnostic pop
#endif
 
//-----------------------------------------------------------------------
// class SearchAlphaBeta
//-----------------------------------------------------------------------
 
/// @todo TOCHECK: why not test for winning before evaluating moves
bBestMoveInfo SearchAlphaBeta::CalcBestMove(bBoard& b, depth_t const& nDepth,
        bSearchScore alpha, bSearchScore beta)
{
  bBestMoveInfo result;
  if (getLevel()->depthReached(nDepth)) {
    uint8_t inCheck = b.isInCheck() ? 1 : 0;
    result = Quiescence(b, nDepth, alpha, beta, inCheck);
    return result;
  }
 
  if (nDepth > m_maxDepth) m_maxDepth = nDepth;
 
  TerminalNode n(b, nDepth, alpha, beta, this);
  if (n.isTerminal()) { ++m_leafnodes; return n.getNode(); }
 
  if (m_bEarlyBetaCutOff
          && (belofte::realScore(n.getScore()) - m_nBetaCutOffMargin >= beta)) {
    result = sendInfoSearching(b, nDepth, "(early beta cut-off) static: " + belofte::scoreAsStr(n.getScore())
            + GTOREQUAL + beta, (m_bFailSoft ? n.getScore() : beta.getScore()));
    ++m_leafnodes;
    return result;
  }
 
  bSearchScore bestscore(-SCORE_INFINITE, tScoreType::SC_BEST);
 
  movenum_t n_moves = b.generateMoves();
  bMoveList& ml = b.getMoves();
  for (movenum_t moveid = 1; moveid <= n_moves; moveid++) {
    handleInfoCurrMove(b, ml, nDepth, moveid);
    bBoard chldbrd(b, ml[moveid], ml.getMoveT(moveid));
    bSearchScore chldscore(CalcBestMove(chldbrd, nDepth + 1, -beta, -alpha), tScoreType::SC_CHILD);
    if (m_bAttenuateScore) chldscore = -attenuateScore(chldscore.getScore());
    else chldscore = -chldscore;
    ml.updateScoreOfBestMove(moveid, chldscore.getScore());
    if (chldscore > SCORE_WINNING) {
      b.setVariation(chldbrd);
      result = sendInfoSearching(b, nDepth, "(winning)", chldscore);
      ++m_nonleafnodes;
      return result;
    }
    if (chldscore.getRealScore() - m_nBetaCutOffMargin >= beta) {
      ++m_nonleafnodes;
      if (m_bFailSoft)
        result = sendInfoSearching(b, nDepth, "(fail soft) " + chldscore
                + GTOREQUAL + beta, chldscore);
      else
        result = sendInfoSearching(b, nDepth, "(fail hard) " + chldscore
                + GTOREQUAL + beta, beta);
      return result;
    }
    if (chldscore > alpha) {
      b.setVariation(chldbrd);
      sendInfoSearching(b, nDepth, "alpha & best update " + chldscore
              + " > " + alpha, chldscore);
      bestscore = chldscore.getScore();
      alpha = chldscore.getScore(); // alpha does not change type
#if defined(_DEBUG)
    } else {
      sendInfoSearching(b, nDepth, "no update " + chldscore, bestscore);
#endif
    }
  }
 
  ++m_nonleafnodes;
  result = sendInfoSearching(b, nDepth, "(return best)", bestscore);
  return result;
}
 
//-----------------------------------------------------------------------
 
/// @todo TOCHECK: why not test for winning before evaluating moves
bScore SearchAlphaBeta::Quiescence(bBoard& b, depth_t const& nDepth,
        bSearchScore alpha, bSearchScore beta, uint8_t& nCheckCount)
{
  if (nDepth > m_maxDepth) m_maxDepth = nDepth;
 
  TerminalNode n(b, nDepth, alpha, beta, nCheckCount, this);
  if (n.isTerminal()) { ++m_leafnodes; return n.getScore(); }
 
  if (getLevel()->qsDepthReached(nDepth)) {
    return sendInfoSearching(b, nDepth, "qs (qs depth reached)", n.getScore());
  }
 
  bool isAllMoves = false;
  if (!b.generateAtLeastOneQSMove()) {
    if ((nCheckCount < 1) && (b.isInCheck())) {
      // make sure QS does not end up in endless checks
      isAllMoves = true;
    } else {
      ++m_leafnodes;
      return sendInfoSearching(b, nDepth, "qs (qs dead position)", n.getScore());
    }
  }
  if (b.isInCheck()) nCheckCount++;
 
  if (m_bEarlyQSBetaCutOff
          && (belofte::realScore(n.getScore()) - m_nBetaCutOffMargin >= beta)) {
    ++m_leafnodes;
    return sendInfoSearching(b, nDepth, "qs (beta early cut-off) static: " + belofte::scoreAsStr(n.getScore())
            + GTOREQUAL + beta, n.getScore());
  }
 
  // apply null-move simulation
  if (belofte::realScore(n.getScore()) > alpha) {
    sendInfoSearching(b, nDepth, "qs early alpha & best update " + belofte::scoreAsStr(n.getScore())
            + " > " + alpha, n.getScore());
    //b.setBestScore(n.getScore()); // already done above
    alpha = n.getScore();
  }
 
  bSearchScore bestscore(n.getScore(), tScoreType::SC_BEST);
 
  movenum_t n_moves = b.generateMoves();
  bMoveList& ml = b.getMoves();
  for (movenum_t moveid = 1; moveid <= n_moves; moveid++) {
    // TODO: count move 0 as null-move (n.getScore())
    if (isAllMoves || (ml[moveid].isNonSilent())
            || ((!nCheckCount) && (b.isInCheck()))) {
      handleInfoCurrMove(b, ml, nDepth, moveid);
      bBoard chldbrd(b, ml[moveid], ml.getMoveT(moveid));
      bSearchScore chldscore(Quiescence(chldbrd, nDepth + 1, -beta, -alpha, nCheckCount), tScoreType::SC_CHILD);
      if (m_bAttenuateScore) chldscore = -attenuateScore(chldscore.getScore());
      else chldscore = -chldscore;
      ml.updateScoreOfBestMove(moveid, chldscore.getScore());
      if (chldscore > SCORE_WINNING) {
        b.setVariation(chldbrd);
        ++m_nonleafnodes;
        return sendInfoSearching(b, nDepth, "qs (winning)", chldscore);
      }
      if (chldscore.getRealScore() - m_nBetaCutOffMargin >= beta) {
        ++m_nonleafnodes;
        return sendInfoSearching(b, nDepth, "qs (fail soft) " + chldscore
                + GTOREQUAL + beta, chldscore);
      }
      if (chldscore > alpha) {
        b.setVariation(chldbrd);
        sendInfoSearching(b, nDepth, "qs alpha & best update: " + chldscore
                + " > " + alpha, chldscore);
        bestscore = chldscore.getScore();
        alpha = chldscore.getScore(); // alpha does not change type
#if defined(_DEBUG)
      } else {
        sendInfoSearching(b, nDepth, "qs no update " + chldscore, bestscore);
#endif
      }
#if defined(_DEBUG)
    } else {
      sendInfoSearching(b, nDepth, "qs skipped #" + belofte::to_string(moveid) +
              " till #" + belofte::to_string(n_moves), bestscore);
#endif
      break; // all QS moves are sorted in front, so break on first non-QS
    }
  }
 
  ++m_nonleafnodes;
  return sendInfoSearching(b, nDepth, "qs (return best)", bestscore);
}
 
// eof