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;
 
  return CalcBestMove(b, ml, nDepth, alpha, beta);
}
 
//-----------------------------------------------------------------------
 
/**
 * 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)) {
    return Quiescence(b, nDepth, alpha, beta, (b.isInCheck() ? 1 : 0));
  }
 
  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 0;
    }
    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;
    b.calcMinorPieces();
    bScore terminalScore = RetrieveBoardEvaluation(b, gr);
    DEBUG_sendInfoSearching(b, nDepth, "(dead position)", terminalScore);
    return terminalScore;
  }
 
  if (nDepth > 2 && nDepth % 2) CheckIfAbortingSearch();
  adjustMaxSearchedDepth(nDepth);
 
  depth_t nNewDepth = nDepth + 1;
  bSearchScore bestscore(-SCORE_INFINITE);
  ml.sortMoves();
  ml.clearScores();
  for (movenum_t moveid = 1; moveid <= n_moves; ++moveid) {
    bMove m(ml[moveid]);
    sendInfoCurrMove(b, nDepth, m, moveid);
    bBoard chldbrd(b, m);
    chldbrd.applyMove(m);
    bMoveList chldML;
    bSearchScore chldscore(-CalcBestMove(chldbrd, chldML, nNewDepth, -beta, -alpha));
    bScore sc = chldscore.convergeScore();
    if (ml.setScoreOfMove(moveid, sc)) {
      DEBUG_sendInfoSearching(b, nDepth, "do 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 " + chldscore + " > " + alpha);
      alpha = sc; // alpha does not change type
    } else {
      DEBUG_sendInfoSearchingNS(b, nDepth, "no update " + chldscore);
    }
  }
 
  ++m_nonleafnodes;
  DEBUG_sendInfoSearching(b, nDepth, "(return best)", bestscore.getScore());
  return bestscore.getScore();
}
 
//-----------------------------------------------------------------------
 
/**
 * 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, "(draw)");
      return 0;
    }
    bScore terminalScore = bPositionEvaluation::resultToScoreFlag(gr) * b.minimizing();
    DEBUG_sendInfoSearching(b, nDepth, "(final score)", terminalScore);
    return terminalScore;
  }
 
  DEBUG_sendInfoSearchingNS(b, nDepth, "qs " + alpha
          + " " + beta
          + (b.isInCheck() ? " check" : "")
          + " +: " + belofte::to_string(nCheckCount));
 
  bMoveList ml;
  movenum_t n_moves = ml.generateMoves(b);
  if (!n_moves) {
    ++m_leafnodes;
    b.calcMinorPieces();
    bScore terminalScore = RetrieveBoardEvaluation(b, gr);
    DEBUG_sendInfoSearching(b, nDepth, "qs (dead position)", terminalScore);
    return terminalScore;
  }
 
  if (getLevel()->qsDepthReached(nDepth)) {
    ++m_leafnodes;
    b.calcMinorPieces();
    bScore terminalScore = RetrieveBoardEvaluation(b, gr);
    DEBUG_sendInfoSearching(b, nDepth, "qs (qs depth reached)", terminalScore);
    return terminalScore;
  }
 
  adjustMaxSearchedDepth(nDepth);
  if (nDepth > 4 && nDepth % 2) CheckIfAbortingSearch();
 
  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;
      b.calcMinorPieces();
      bScore terminalScore = RetrieveBoardEvaluation(b, gr);
      DEBUG_sendInfoSearching(b, nDepth, "qs (qs dead position)", terminalScore);
      return terminalScore;
    }
  }
  if (b.isInCheck()) ++nCheckCount;
 
  b.calcMinorPieces();
  bSearchScore bestscore(RetrieveBoardEvaluation(b, gr));
 
  if (bestscore.improvesOn(m_nBetaCutOffMargin, beta)) {
    ++m_leafnodes;
    DEBUG_sendInfoSearchingNS(b, nDepth, "qs (beta early cut-off) static: " + bestscore + GTOREQUAL + beta);
    return bestscore.getScore();
  }
 
  // apply null-move simulation
  if (bestscore.improvesOn(alpha)) {
    DEBUG_sendInfoSearchingNS(b, nDepth, "qs early alpha update " + bestscore + " > " + alpha);
    alpha = bestscore.getScore();
  }
 
  depth_t nNewDepth = nDepth + 1;
  ml.sortMoves();
  ml.clearScores();
  ml.setBestMoveScore(1, bestscore.getScore());
  for (movenum_t moveid = 1; moveid <= n_moves; ++moveid) {
    bMove m(ml[moveid]);
    if (escapeFirstCheck || (m.isNonSilent())) {
      sendInfoCurrMove(b, nDepth, m, moveid);
      boardInfo_t bi = b.applyMove(m);
      bSearchScore chldscore(-Quiescence(b, nNewDepth, -beta, -alpha, nCheckCount));
      b.unApplyMove(m, bi);
      ml.setScoreOfMove(moveid, chldscore.convergeScore());
      if (chldscore.improvesOn(m_nBetaCutOffMargin, beta)) {
        ++m_nonleafnodes;
        DEBUG_sendInfoSearchingNS(b, nDepth, "qs (fail soft) " + chldscore + GTOREQUAL + beta);
        return chldscore.getScore();
      }
      if (chldscore.improvesOn(alpha)) {
        bestscore = chldscore.getScore();
        if (chldscore.isWinning()) {
          DEBUG_sendInfoSearching(b, nDepth, "qs (winning)", chldscore.getScore());
          break;
        }
        DEBUG_sendInfoSearchingNS(b, nDepth, "qs alpha & best update: " + chldscore + " > " + alpha);
        alpha = chldscore.getScore(); // alpha does not change type
      } else {
        DEBUG_sendInfoSearchingNS(b, nDepth, "qs no update " + chldscore);
      }
    } else {
      if (moveid == 1) {
        // no QS moves
        DEBUG_sendInfoSearchingNS(b, nDepth, "qs no qs-moves " + bestscore);
        return bestscore.getScore();
      }
      DEBUG_sendInfoSearchingNS(b, nDepth, "qs skipped #" + belofte::to_string(moveid) +
              " till #" + belofte::to_string(n_moves));
      break; // all QS moves are sorted in front, so break on first non-QS
    }
    break; /// @bug quit after first move
  }
 
  ++m_nonleafnodes;
  DEBUG_sendInfoSearching(b, nDepth, "qs (return best)", bestscore.getScore());
  return bestscore.getScore();
}
 
// eof