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 ALPHABETA "alpha-beta"
#else
#define ALPHABETA "𝛼𝛽"
#endif
 
#if defined(_DEBUG)
#if defined(BELOFTE_NOUNICODE)
#define GTOREQUAL " >= "
#else
#define GTOREQUAL " ≥ "
#endif
#endif
 
//-----------------------------------------------------------------------
// class SearchAlphaBeta
//-----------------------------------------------------------------------
 
#if defined(__GNUC__)
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Weffc++"
#endif
 
SearchAlphaBeta::SearchAlphaBeta()
  : bSearchAlgorithm(ALPHABETA)
  , m_nBetaCutOffMargin{SCORE_BETAMARGIN}
{
  m_iterativesearch = true;
}
 
SearchAlphaBeta::SearchAlphaBeta(std::string const& s)
  : bSearchAlgorithm(s)
  , m_nBetaCutOffMargin{SCORE_BETAMARGIN}
{
  m_iterativesearch = true;
}
 
SearchAlphaBeta::~SearchAlphaBeta()
{
}
 
bScore SearchAlphaBeta::CalcBestMove(bBoard& b)
{
  bSearchScore alpha(-SCORE_INFINITE, tScoreType::SC_ALPHA);
  bSearchScore beta(SCORE_INFINITE, tScoreType::SC_BETA);
 
  return CalcBestMove(b, 0, alpha, beta);
}
 
//-----------------------------------------------------------------------
// class SearchAlphaBetaFH
//-----------------------------------------------------------------------
 
SearchAlphaBetaFH::SearchAlphaBetaFH()
  : SearchAlphaBeta(ALPHABETA " FH")
{
  m_nBetaCutOffMargin = SCORE_BETAMARGIN / 2;
}
 
SearchAlphaBetaFH::~SearchAlphaBetaFH()
{
}
 
#if defined(__GNUC__)
#pragma GCC diagnostic pop
#endif
 
//-----------------------------------------------------------------------
// class SearchAlphaBeta
//-----------------------------------------------------------------------
 
// TOCHECK: why not test for winning before evaluating moves
bScore SearchAlphaBeta::CalcBestMove(bBoard& b, depth_t const nDepth,
        bSearchScore alpha, bSearchScore beta)
{
  if (getLevel()->searchDepthReached(nDepth)) {
    return Quiescence(b, nDepth, alpha, beta, (b.isInCheck() ? 1 : 0));
  }
 
  bMoveList& ml = b.getMoveListRef();
  movenum_t m_nmoves = ml.generateMoves(b);
 
  bScore m_terminalscore = RetrieveBoardEvaluation(b);
 
  DEBUG_sendInfoSearching(b, nDepth, alpha
          + " " + beta
          + " static: " + belofte::scoreAsStr(m_terminalscore)
          + (b.isInCheck() ? " check" : ""), m_terminalscore);
 
  if ((m_terminalscore & SCORE_POSITIVE) == SCORE_THEORETIC_DRAW) {
    m_nodes++;
    return DEBUG_returnInfoSearching(b, nDepth, "(th. draw)", SCORE_THEORETIC_DRAW);
  } else {
    if (!m_nmoves) {
      m_nodes++;
      return DEBUG_returnInfoSearching(b, nDepth, "(dead position)", m_terminalscore);
    }
  }
 
  if (nDepth > m_maxDepth) m_maxDepth = nDepth;
  if (nDepth > 2 && nDepth % 2) CheckIfAbortingSearch();
 
  bSearchScore bestscore(-SCORE_INFINITE, tScoreType::SC_BEST);
  ml.sortMoves();
  for (movenum_t moveid = 1; moveid <= m_nmoves; moveid++) {
    sendInfoCurrMove(b, nDepth, moveid); /// @todo optimise
    bMove m = ml[moveid];
    bBoard chldbrd(b, m);
    bSearchScore chldscore(-CalcBestMove(chldbrd, nDepth + 1, -beta, -alpha), tScoreType::SC_CHILD);
    chldscore = attenuateScore(chldscore.getScore());
    ml.setScoreOfMove(moveid, chldscore.getScore());
    if (chldscore > SCORE_WINNING) {
      b.setVariation(chldbrd);
      m_nonleafnodes++;
      return DEBUG_returnInfoSearching(b, nDepth, "(winning)", chldscore.getScore());
    }
    if (chldscore.getRealScore() - m_nBetaCutOffMargin >= beta) {
      m_nonleafnodes++;
      return DEBUG_returnInfoSearching(b, nDepth, "(fail soft) " + chldscore
                + GTOREQUAL + beta, chldscore.getScore());
    }
    if (chldscore > alpha) {
      b.setVariation(chldbrd);
      DEBUG_sendInfoSearching(b, nDepth, "alpha & best update " + chldscore
              + " > " + alpha, chldscore.getScore());
      bestscore = chldscore.getScore();
      alpha = chldscore.getScore(); // alpha does not change type
    } else {
      DEBUG_sendInfoSearching(b, nDepth, "no update " + chldscore, SCORE_UNDEFINED);
    }
  }
 
  m_nonleafnodes++;
  return DEBUG_returnInfoSearching(b, nDepth, "(return best)", bestscore.getScore());
}
 
// TOCHECK: why not test for winning before evaluating moves
bScore SearchAlphaBetaFH::CalcBestMove(bBoard& b, depth_t const nDepth,
        bSearchScore alpha, bSearchScore beta)
{
  if (getLevel()->searchDepthReached(nDepth)) {
    return Quiescence(b, nDepth, alpha, beta, (b.isInCheck() ? 1 : 0));
  }
 
  bMoveList& ml = b.getMoveListRef();
  movenum_t m_nmoves = ml.generateMoves(b);
 
  bScore m_terminalscore = RetrieveBoardEvaluation(b);
 
  DEBUG_sendInfoSearching(b, nDepth, alpha
          + " " + beta
          + " static: " + belofte::scoreAsStr(m_terminalscore)
          + (b.isInCheck() ? " check" : ""), m_terminalscore);
 
  if ((m_terminalscore & SCORE_POSITIVE) == SCORE_THEORETIC_DRAW) {
    m_nodes++;
    return DEBUG_returnInfoSearching(b, nDepth, "(th. draw)", SCORE_THEORETIC_DRAW);
  } else {
    if (!m_nmoves) {
      m_nodes++;
      return DEBUG_returnInfoSearching(b, nDepth, "(dead position)", m_terminalscore);
    }
  }
 
  if (nDepth > m_maxDepth) m_maxDepth = nDepth;
  if (nDepth > 2 && nDepth % 2) CheckIfAbortingSearch();
 
  bSearchScore bestscore(-SCORE_INFINITE, tScoreType::SC_BEST);
  ml.sortMoves();
  for (movenum_t moveid = 1; moveid <= m_nmoves; moveid++) {
    sendInfoCurrMove(b, nDepth, moveid); /// @todo optimise
    bMove m = ml[moveid];
    bBoard chldbrd(b, m);
    bSearchScore chldscore(-CalcBestMove(chldbrd, nDepth + 1, -beta, -alpha), tScoreType::SC_CHILD);
    chldscore = attenuateScore(chldscore.getScore());
    ml.setScoreOfMove(moveid, chldscore.getScore());
    if (chldscore > SCORE_WINNING) {
      b.setVariation(chldbrd);
      m_nonleafnodes++;
      return DEBUG_returnInfoSearching(b, nDepth, "(winning)", chldscore.getScore());
    }
    if (chldscore.getRealScore() - m_nBetaCutOffMargin >= beta) {
      m_nonleafnodes++;
      return DEBUG_returnInfoSearching(b, nDepth, "(fail hard) " + chldscore
              + GTOREQUAL + beta, beta.getScore());
    }
    if (chldscore > alpha) {
      b.setVariation(chldbrd);
      DEBUG_sendInfoSearching(b, nDepth, "alpha & best update " + chldscore
              + " > " + alpha, chldscore.getScore());
      bestscore = chldscore.getScore();
      alpha = chldscore.getScore(); // alpha does not change type
    } else {
      DEBUG_sendInfoSearching(b, nDepth, "no update " + chldscore, SCORE_UNDEFINED);
    }
  }
 
  m_nonleafnodes++;
  return DEBUG_returnInfoSearching(b, nDepth, "(return best)", bestscore.getScore());
}
 
//-----------------------------------------------------------------------
 
// 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)
{
  bMoveList& ml = b.getMoveListRef();
  movenum_t m_nmoves = ml.generateMoves(b);
 
  bScore terminalScore = RetrieveBoardEvaluation(b);
 
  DEBUG_sendInfoSearching(b, nDepth, "qs " + alpha
          + " " + beta
          + " static: " + belofte::scoreAsStr(terminalScore)
          + (b.isInCheck() ? " check" : "")
          + " +: " + belofte::to_string(nCheckCount), terminalScore);
 
  if ((terminalScore & SCORE_POSITIVE) == SCORE_THEORETIC_DRAW) {
    m_nodes++;
    return DEBUG_returnInfoSearching(b, nDepth, "qs (th. draw)", SCORE_THEORETIC_DRAW);
  } else {
    if (!m_nmoves) {
      m_nodes++;
      return DEBUG_returnInfoSearching(b, nDepth, "qs (dead position)", terminalScore);
    }
  }
 
  if (getLevel()->qsDepthReached(nDepth)) {
    m_nodes++;
    return DEBUG_returnInfoSearching(b, nDepth, "qs (qs depth reached)", terminalScore);
  }
 
  if (nDepth > m_maxDepth) m_maxDepth = nDepth;
  if (nDepth > 4 && nDepth % 2) CheckIfAbortingSearch();
 
  bool isAllMoves = false;
  if (!ml.getNumberOfQSMoves()) {
    if ((nCheckCount < 1) && (b.isInCheck())) {
      // make sure QS does not end up in endless checks
      isAllMoves = true;
    } else {
      m_nodes++;
      return DEBUG_returnInfoSearching(b, nDepth, "qs (qs dead position)", terminalScore);
    }
  }
  if (b.isInCheck()) nCheckCount++;
 
  if (terminalScore - m_nBetaCutOffMargin >= beta) {
    m_nodes++;
    return DEBUG_returnInfoSearching(b, nDepth, "qs (beta early cut-off) static: " + belofte::scoreAsStr(terminalScore)
            + GTOREQUAL + beta, terminalScore);
  }
 
  // apply null-move simulation
  if (terminalScore > alpha) {
    DEBUG_sendInfoSearching(b, nDepth, "qs early alpha update " + belofte::scoreAsStr(terminalScore)
            + " > " + alpha, terminalScore);
    alpha = terminalScore;
  }
 
  bSearchScore bestscore(terminalScore, tScoreType::SC_BEST);
  ml.sortMoves();
  for (movenum_t moveid = 1; moveid <= m_nmoves; moveid++) {
    // TODO: count move 0 as null-move (terminalScore)
    if (isAllMoves || (ml[moveid].isNonSilent())
            || ((!nCheckCount) && (b.isInCheck()))) {
      sendInfoCurrMove(b, nDepth, moveid);
      bMove m = ml[moveid];
      bBoard chldbrd(b, m);
      bSearchScore chldscore(-Quiescence(chldbrd, nDepth + 1, -beta, -alpha, nCheckCount), tScoreType::SC_CHILD);
      chldscore = attenuateScore(chldscore.getScore());
      ml.setScoreOfMove(moveid, chldscore.getScore());
      if (chldscore > SCORE_WINNING) {
        b.setVariation(chldbrd);
        m_nonleafnodes++;
        return DEBUG_returnInfoSearching(b, nDepth, "qs (winning)", chldscore.getScore());
      }
      if (chldscore.getRealScore() - m_nBetaCutOffMargin >= beta) {
        m_nonleafnodes++;
        return DEBUG_returnInfoSearching(b, nDepth, "qs (fail soft) " + chldscore
                + GTOREQUAL + beta, chldscore.getScore());
      }
      if (chldscore > alpha) {
        b.setVariation(chldbrd);
        DEBUG_sendInfoSearching(b, nDepth, "qs alpha & best update: " + chldscore
                + " > " + alpha, chldscore.getScore());
        bestscore = chldscore.getScore();
        alpha = chldscore.getScore(); // alpha does not change type
      } else {
        DEBUG_sendInfoSearching(b, nDepth, "qs no update " + chldscore, SCORE_UNDEFINED);
      }
#if defined(_DEBUG)
    } else {
      DEBUG_sendInfoSearching(b, nDepth, "qs skipped #" + belofte::to_string(moveid) +
              " till #" + belofte::to_string(m_nmoves), SCORE_UNDEFINED);
#endif
      /// @todo this is a bug in non-debug mode
      break; // all QS moves are sorted in front, so break on first non-QS
    }
  }
 
  m_nonleafnodes++;
  return DEBUG_returnInfoSearching(b, nDepth, "qs (return best)", bestscore.getScore());
}
 
// eof