search_mm.cpp

Go to the documentation of this file.

/*---------------------------------------------------------------------+
 * File: search_mm.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
 */
bScore SearchMiniMax::CalcBestMove(bBoard& b, bMoveList& ml)
{
  bBoard searchBoard(b);
  bScore minimizing = searchBoard.minimizing();
  bScore score = CalcBestMove(searchBoard, ml, 0, minimizing) * minimizing;
  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 minimizing search from minimizing view
 */
bScore SearchMiniMax::CalcBestMove(bBoard& b,
        bMoveList& ml, depth_t const nDepth, bScore const minimizing)
{
 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;
    }
    // mate
    bScore terminalScore = bPositionEvaluation::resultToScoreFlag(gr);
    DEBUG_sendInfoSearching(b, nDepth, "(final score)", terminalScore);
    return terminalScore;
  }
 
  adjustMaxSearchedDepth(nDepth);
 
  if (getLevel()->searchDepthReached(nDepth)) {
    ++m_leafnodes;
    bScore terminalScore = RetrieveBoardEvaluationForWhite(b, gr, true);
    DEBUG_sendInfoSearching(b, nDepth, "Depth reached", terminalScore);
    return terminalScore;
  }
 
  // in bruteforce, we do not need moves to be ordered
  ml.clearNeedSorted();
  // in bruteforce, we do not need score during move-generation
  ml.clearKeepScores();
  movenum_t n_moves = ml.generateMoves(b);
 
  if (nDepth) ++m_nonleafnodes;
 
  if (!n_moves && isBench()) {
    bScore terminalScore = RetrieveBoardEvaluationForWhite(b, gr, true);
    DEBUG_sendInfoSearching(b, nDepth, "Dead position", terminalScore);
    return terminalScore;
  }
 
  // going forward, we set scores and keep scores
  ml.clearScores();
  ml.setKeepScores();
 
  if (nDepth > 2 && nDepth % 2) CheckIfAbortingSearch();
 
  ml.curmoveid = 1;
  if (minimizing == 1) {
    // maximize result
    for ( ; ml.curmoveid <= n_moves; ++ml.curmoveid) {
      bMove m(ml[ml.curmoveid]);
      sendInfoCurrMove(b, nDepth, m, ml.curmoveid);
      boardInfo_t bi = b.bBasicBoard::applyMove(m);
      bMoveList chldML;
      bScore chldScore = CalcBestMove(b, chldML, nDepth + 1, -1);
      ml.setScoreOfMoveUnsorted(ml.curmoveid, chldScore);
      b.bBasicBoard::unApplyMove(m, bi);
      // consider forced draw
      if (chldScore > SCORE_INFINITE) break;
    }
  } else {
    // minimize result
    for ( ; ml.curmoveid <= n_moves; ++ml.curmoveid) {
      bMove m(ml[ml.curmoveid]);
      sendInfoCurrMove(b, nDepth, m, ml.curmoveid);
      boardInfo_t bi = b.bBasicBoard::applyMove(m);
      bMoveList chldML;
      bScore chldScore = CalcBestMove(b, chldML, nDepth + 1, 1);
      ml.setMinScoreOfMoveUnsorted(ml.curmoveid, chldScore);
      b.bBasicBoard::unApplyMove(m, bi);
      // consider forced draw
      if (chldScore < -SCORE_INFINITE) break;
    }
  }
 
  bScore bestScore = bSearchScore::convergeScore(ml.getBestMoveScore());
  ml.setBestMoveScore(bestScore);
  DEBUG_sendInfoSearching(b, nDepth, "(return best)", bestScore);
  return bestScore;
}
 
//-----------------------------------------------------------------------
 
// eof