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"
 
//-----------------------------------------------------------------------
 
/**
 * Root search for algorithm
 * @param b board
 * @param ml movelist of this position
 * @todo check why not test for winning before evaluating moves
 */
bScore SearchAlphaBeta::CalcBestMove(bBoard& b, bMoveList& ml)
{
  bSearchScore alpha(-SCORE_INFINITE, tScoreType::SC_ALPHA);
  bSearchScore beta(SCORE_INFINITE, tScoreType::SC_BETA);
  depth_t const nDepth = 0;
 
  bScore score = CalcBestMove(b, ml, nDepth, alpha, beta);
  return score;
}
 
//-----------------------------------------------------------------------
 
/**
 * Calculate best move from this position at given depth, iterative call
 * @param b Board
 * @param ml movelist of this position
 * @param nDepth depth to search for, increasing until searchDepth
 * @param alpha maximum for minimizing player
 * @param beta minimum for maximizing player
 * @bug alpha/beta values do not bubble up to calling function
 */
bScore SearchAlphaBeta::CalcBestMove(bBoard& b,
        bMoveList& ml, depth_t const nDepth,
        bSearchScore alpha, bSearchScore beta)
{
  if (nDepth && getLevel()->searchDepthReached(nDepth)) {
    bScore terminalScore = Quiescence(b, nDepth, alpha, beta, (b.isInCheck() ? 1 : 0));
    return terminalScore;
  }
 
  gameResult_t gr = bPositionEvaluation::gameEndedResult(b);
  if (isNoBench() && gr != GR_UNKNOWN) {
    ++m_leafnodes; // leaf node because of final position
    if (bPositionEvaluation::isDrawResult(gr)) {
      DEBUG_sendInfoSearchingNS(b, nDepth, "(draw)");
      return SCORE_THEORETIC_DRAW;
    }
    bScore terminalScore = bPositionEvaluation::resultToScoreFlag(gr) * b.minimizing();
    DEBUG_sendInfoSearching(b, nDepth, "(final score)", terminalScore);
    return terminalScore;
  }
 
  DEBUG_sendInfoSearchingNS(b, nDepth, alpha
          + " " + beta
          + (b.isInCheck() ? " check" : ""));
 
  movenum_t n_moves = ml.generateMoves(b);
  if (!n_moves) {
    ++m_leafnodes;
    bScore terminalScore = RetrieveBoardEvaluation(b, gr, true);
    DEBUG_sendInfoSearching(b, nDepth, "(dead position)", terminalScore);
    return terminalScore;
  }
 
  if (nDepth > 3 && nDepth % 2) CheckIfAbortingSearch();
  adjustMaxSearchedDepth(nDepth);
 
  depth_t nNewDepth = nDepth + 1;
  bSearchScore bestscore(-SCORE_INFINITE);
  ml.sortMoves(true);
  ml.clearScores(-SCORE_UNDEFINED);
  for (ml.curmoveid = 1; ml.curmoveid <= n_moves; ++ml.curmoveid) {
    bMove m(ml[ml.curmoveid]);
    sendInfoCurrMove(b, nDepth, m, ml.curmoveid);
    bBoard chldbrd(b, m);
    chldbrd.applyMove(m);
    bMoveList chldML;
    bSearchScore chldscore(-CalcBestMove(chldbrd, chldML, nNewDepth, -beta, -alpha));
    bScore sc = chldscore.convergeScore();
    if (ml.setScoreOfMove(ml.curmoveid, sc)) {
      DEBUG_sendInfoSearching(b, nDepth, "do movescore update", sc);
    }
    if (chldscore.improvesOn(m_nBetaCutOffMargin, beta)) {
      ++m_nonleafnodes;
      DEBUG_sendInfoSearchingNS(b, nDepth, "(fail soft) " + chldscore + GTOREQUAL + beta);
      return sc;
    }
    if (chldscore.improvesOn(alpha)) {
      b.setVariation(chldbrd);
      bestscore = sc;
      if (chldscore.isWinning()) {
        DEBUG_sendInfoSearching(b, nDepth, "(winning)", sc);
        break;
      }
      DEBUG_sendInfoSearchingNS(b, nDepth, "alpha & best update to : " + chldscore + " (> " + alpha + ")");
      alpha = sc; // alpha does not change type
    } else {
      DEBUG_sendInfoSearchingNS(b, nDepth, "no update " + chldscore);
    }
  }
 
  ++m_nonleafnodes;
  bScore score = bestscore.getScore();
  DEBUG_sendInfoSearching(b, nDepth, "(return best)", score);
  return score;
}
 
//-----------------------------------------------------------------------
 
/**
 * Calculate best move from this position considering only non-silent moves
 * @param b Board
 * @param nDepth depth to search for, increasing from searchDepth to qsSearchDepth
 * @param alpha maximum for minimizing player
 * @param beta minimum for maximizing player
 * @param nCheckCount number of checks inside qs search tree
 * @bug alpha/beta values do not bubble up to calling function
 */
bScore SearchAlphaBeta::Quiescence(bBoard& b,
        depth_t const nDepth,
        bSearchScore alpha, bSearchScore beta, uint8_t nCheckCount)
{
  gameResult_t gr = bPositionEvaluation::gameEndedResult(b);
  if (isNoBench() && gr != GR_UNKNOWN) {
    ++m_leafnodes; // leaf node because of final position
    if (bPositionEvaluation::isDrawResult(gr)) {
      DEBUG_sendInfoSearchingNS(b, nDepth, "qs (draw)");
      return SCORE_THEORETIC_DRAW;
    }
    bScore terminalSC = bPositionEvaluation::resultToScoreFlag(gr) * b.minimizing();
    DEBUG_sendInfoSearching(b, nDepth, "qs (final score)", terminalSC);
    return terminalSC;
  }
 
  bMoveList ml;
  movenum_t n_moves = ml.generateMoves(b);
  bScore terminalScore = RetrieveBoardEvaluation(b, gr, true);
 
  DEBUG_sendInfoSearching(b, nDepth, "qs " + alpha
          + " " + beta
          + (b.isInCheck() ? " check" : "")
          + " +: " + belofte::to_string(nCheckCount),
          terminalScore);
 
  if (!n_moves) {
    ++m_leafnodes;
    DEBUG_sendInfoSearching(b, nDepth, "qs (dead position)", terminalScore);
    return terminalScore;
  }
 
  if (getLevel()->qsDepthReached(nDepth)) {
    ++m_leafnodes;
    DEBUG_sendInfoSearching(b, nDepth, "qs (qs depth reached)", terminalScore);
    return terminalScore;
  }
 
  if (nDepth > 5 && nDepth % 2) CheckIfAbortingSearch();
  adjustMaxSearchedDepth(nDepth);
 
  bool escapeFirstCheck = false;
  if (!ml.getNumberOfQSMoves()) {
    if ((nCheckCount < 1) && (b.isInCheck())) {
      // make sure QS does not end up in endless checks
      escapeFirstCheck = true;
    } else {
      ++m_leafnodes;
      DEBUG_sendInfoSearching(b, nDepth, "qs (qs dead position)", terminalScore);
      return terminalScore;
    }
  }
  if (b.isInCheck()) ++nCheckCount;
 
  bSearchScore bestscore(terminalScore);
 
  if (bestscore.improvesOn(m_nBetaCutOffMargin, beta)) {
    ++m_leafnodes;
    DEBUG_sendInfoSearchingNS(b, nDepth, "qs (beta early cut-off) : " + bestscore + GTOREQUAL + beta);
    return terminalScore;
  }
 
  // apply null-move simulation
  if (bestscore.improvesOn(alpha)) {
    DEBUG_sendInfoSearchingNS(b, nDepth, "qs early alpha update : " + bestscore + " > " + alpha);
    alpha = terminalScore;
  }
 
  depth_t nNewDepth = nDepth + 1;
  ml.sortMoves(true);
  ml.clearScores(-SCORE_UNDEFINED);
  ml.setBestMoveScore(1, terminalScore);
  for (ml.curmoveid = 1; ml.curmoveid <= n_moves; ++ml.curmoveid) {
    bMove m(ml[ml.curmoveid]);
    if (escapeFirstCheck || m.isNonSilent() || m.isCheck()) {
      sendInfoCurrMove(b, nDepth, m, ml.curmoveid);
      boardInfo_t bi = b.applyMove(m);
      bSearchScore chldscore(-Quiescence(b, nNewDepth, -beta, -alpha, nCheckCount));
      b.unApplyMove(m, bi);
      bScore sc = chldscore.convergeScore();
      if (ml.setScoreOfMove(ml.curmoveid, sc)) {
        DEBUG_sendInfoSearching(b, nDepth, "qs do bestscore update", sc);
        if (chldscore.improvesOn(m_nBetaCutOffMargin, beta)) {
          ++m_leafnodes;
          DEBUG_sendInfoSearchingNS(b, nDepth, "qs (fail soft) : " + chldscore + GTOREQUAL + beta);
          return sc;
        }
        if (chldscore.improvesOn(alpha)) {
          bestscore = sc;
          if (chldscore.isWinning()) {
            DEBUG_sendInfoSearching(b, nDepth, "qs (winning)", sc);
            break;
          }
          DEBUG_sendInfoSearching(b, nDepth, "qs alpha update (" + alpha + ")", sc);
          alpha = sc; // alpha does not change type
        } else {
          DEBUG_sendInfoSearchingNS(b, nDepth, "qs no update on alpha");
        }
      }
    } else {
      if (ml.curmoveid == 1) {
        // no QS moves
        DEBUG_sendInfoSearching(b, nDepth, "qs (no qs-moves)", terminalScore);
        return terminalScore;
      }
      // all QS moves are sorted in front, so break on first non-QS
      DEBUG_sendInfoSearchingNS(b, nDepth, "qs skipped #" + belofte::to_string(ml.curmoveid) +
              " till #" + belofte::to_string(n_moves));
      break;
    }
  }
 
  ++m_nonleafnodes;
  bScore score = bestscore.getScore();
  DEBUG_sendInfoSearching(b, nDepth, "qs (return best)", score);
  return score;
}
 
// eof