movelist.cpp

Go to the documentation of this file.

/*---------------------------------------------------------------------+
 * File: movelist.cpp
 * Project: part of belofte - A Promising Chess Program
 * Author: yves
 * SPDX-License-Identifier: GPL-2.0-only
+----------------------------------------------------------------------*/
 
#include "belofte.h"
 
/**
 * Allow index mapper for char values of piece into int in 1-12 range
 * to reduce space and easy initialisation
 */
namespace belofte {
  extern bWhiteKing const* cWhiteKingClass;
  extern bBlackKing const* cBlackKingClass;
}
 
namespace belofteeval {
  extern bScore piecevalues[];
  extern bScore centerplayvalues[];
  extern bScore piecevalues_movepenalty[];
}
 
//-----------------------------------------------------------------------
 
void bMoveList::addMoveToList(bBasicBoard const& b, bMove& m, bool const isInCheck)
{
  if (isInCheck) {
    m.setCheck();
    bBasicBoard newboard(b);
    newboard.applyMove(m);
    bMoveList ml;
    if (!ml.atLeastOneMovePossible(newboard))
      m.setGameEnd();
  }
 
  bScore sc;
  if (m.getGameEnd()) {
    sc = SCORE_MATE;
    ++m_nQSMoves; // always consider move ending game as non-silent
  } else if (isKeepScores()) {
    // malus points for moving own piece, except for pawn
    // the greater the value of the piece, the more the penalty
    sc = belofteeval::piecevalues_movepenalty[b.getPiece(m.from())];
    sc += belofteeval::centerplayvalues[m.to()]
          - belofteeval::centerplayvalues[m.from()];
    if (m.isCapture()) {
      sc += belofteeval::piecevalues[b.getPiece(m.to())];
    }
    if (m.isPawnMove()) {
      if (m.isPromotion()) {
        sc += 310;
        if (m.isMajorPromotion()) sc += 500;
      } else if (b.pieceCount() < 12 || b.getPly() > 70) {
        // bonus for playing pawn in endgame
        // we do not have gamestage here, so there is an approximation
        sc += 10;
      }
    } else if (m.isCastleMove()) {
      sc += 250; // malus for king move 200, so half a pawn
    }
    if (m.isCheck()) sc += 80; // check is less than a pawn, we prefer captures
    if (m.isNonSilent()) ++m_nQSMoves;
  } else {
    sc = 0;
    if (m.isNonSilent()) ++m_nQSMoves;
  }
 
  m.setScore(sc);
 
#if defined(INCOMPLETE_C11)
    m_lmoves.insert(m_lmoves.end(), m);
    if (getBestMoveId()) {
      // there is a best move registered, so we are adding second or later move
      if (bestMoveHasImprovedNS(sc)) {
        setBestMoveScore(getNumberOfMoves(), sc);
      }
      // we clear sorted flag too eagerly, but testing it would cost equal cpu
      clearIsSorted();
    } else {
      // no bestmove id stored yet, so newly inserted move is best move
      setBestMoveScore(1, sc);
    }
#else
  if (isKeepScores()) {
    if (getBestMoveId()) {
      // there is a best move registered, so we are adding second or later move
      if (isNeedSorted()) {
        if (bestMoveHasImprovedNS(sc)) {
          m_lmoves.insert(m_lmoves.begin(), m);
          setBestMoveScore(1, sc);
        } else {
          // best move has not improved
          m_lmoves.insert(m_lmoves.end(), m);
          if (getNumberOfMoves() > 2) {
            // we do not know if the moves beyond move 1 are in correct order
            clearIsSorted();
          }
        }
      } else {
        // sorting is not required, adding second move
        m_lmoves.insert(m_lmoves.end(), m);
        if (bestMoveHasImprovedNS(sc)) {
          // update best move
          setBestMoveScore(getNumberOfMoves(), sc);
        }
      }
    } else {
      // no bestmove id stored yet, so newly inserted move is best move
      m_lmoves.insert(m_lmoves.end(), m);
      setBestMoveScore(1, sc);
      setIsOnlyMove();
      if (isNeedSorted()) setIsSorted();
    }
  } else {
    // do not keep scores
    m_lmoves.insert(m_lmoves.end(), m);
    if (!getBestMoveId()) setBestMoveScore(1, sc);
  }
#endif
}
 
/**
 * test if new score is better than previous best score
 * @param score is a valid score, so no tests required
 * @return true if new score is better than previous best score
 */
bool bMoveList::bestMoveHasImprovedNS(bScore const score) const
{
  bScore bestMoveScore = getBestMoveScore();
 
  if (bSearchScore::isRealScore(bestMoveScore)) {
    // bestMoveScore is not UNDEFINED/INFINITE
    if (bSearchScore::isDrawScore(score)) {
      return bestMoveScore < 0;
    }
    return score > bestMoveScore;
  } else if (bSearchScore::isDrawScore(bestMoveScore)) {
    if (bSearchScore::isDrawScore(score)) {
      return false;
    }
    return score > bestMoveScore;
  }
  // bestMoveScore is either + or - UNDEFINED/INFINITE
  // so we replace it in all cases
 
  return true;
}
 
/**
 * Store score of move and update best move
 * @param moveid of move to be stored [1 -> max number of moves]
 * @param score to be stored
 * @return true if best score updated
 */
bool bMoveList::setScoreOfMove(movenum_t const moveid, bScore const score)
{
  if (getBestMoveId()) {
    // there is a best move registered, so we are adding second or later move
    if (bestMoveHasImproved(score)) {
      setBestMoveScore(moveid, score);
      // the best move is no longer the first move
      if (isNeedSorted()) clearIsSorted();
    } else {
      setMoveScore(moveid, score);
      return false;
    }
  } else {
    // no bestmove id stored yet, so newly inserted move is best move
    setBestMoveScore(moveid, score);
    // list is sorted as only one member
    if (isNeedSorted()) setIsSorted();
  }
  return true;
}
 
/**
 * Store score of move and update best move (minimum)
 * @param moveid of move to be stored [1 -> max number of moves]
 * @param score to be stored
 * @return true if best score updated
 */
bool bMoveList::setMinScoreOfMove(movenum_t const moveid, bScore const score)
{
  if (getBestMoveId()) {
    // there is a best move registered, so we are adding second or later move
    if (minMoveHasImproved(score)) {
      setBestMoveScore(moveid, score);
      // the best move is no longer the first move
      clearIsSorted();
    } else {
      setMoveScore(moveid, score);
      return false;
    }
  } else {
    // no bestmove id stored yet, so newly inserted move is best move
    setBestMoveScore(moveid, score);
    // list is sorted as only one member
    setIsSorted();
  }
  return true;
}
 
/**
 * Store score of move and update best move
 * @param moveid of move to be stored [1 -> max number of moves]
 * @param score to be stored
 */
void bMoveList::setScoreOfMoveUnsorted(movenum_t const moveid, bScore const score)
{
  if (getBestMoveId()) {
    // there is a best move registered, so we are adding second or later move
    if (bestMoveHasImproved(score)) {
      setBestMoveScore(moveid, score);
    } else {
      setMoveScore(moveid, score);
    }
  } else {
    // no bestmove id stored yet, so newly inserted move is best move
    setBestMoveScore(moveid, score);
  }
}
 
/**
 * Store score of move and update best move
 * @param moveid of move to be stored [1 -> max number of moves]
 * @param score to be stored
 */
void bMoveList::setMinScoreOfMoveUnsorted(movenum_t const moveid, bScore const score)
{
  if (getBestMoveId()) {
    // there is a best move registered, so we are adding second or later move
    if (minMoveHasImproved(score)) {
      setBestMoveScore(moveid, score);
    } else {
      setMoveScore(moveid, score);
    }
  } else {
    // no bestmove id stored yet, so newly inserted move is best move
    setBestMoveScore(moveid, score);
  }
}
 
/**
 * Only add move to movelist if valid
 * @param b board on which move is calculated
 * @param m move to be added
 * @return number of moves added (1), meaning player is not in check after move
 */
movenum_t bMoveList::addWhiteMoveIfValid(bBasicBoard const& b, bMove& m)
{
  bBasicBoard newboard(b);
  newboard.applyWhiteMove(m);
 
  if (belofte::cWhiteKingClass->isAttacked(newboard, newboard.getWhiteKingPos())) return 0;
  addMoveToList(b, m, belofte::cBlackKingClass->isAttacked(newboard, newboard.getBlackKingPos()));
  return 1;
}
 
/**
 * Only add move to movelist if valid
 * @param b board on which move is calculated
 * @param m move to be added
 * @return number of moves added (1), meaning player is not in check after move
 */
movenum_t bMoveList::addBlackMoveIfValid(bBasicBoard const& b, bMove& m)
{
  bBasicBoard newboard(b);
  newboard.applyBlackMove(m);
 
  if (belofte::cBlackKingClass->isAttacked(newboard, newboard.getBlackKingPos())) return 0;
  addMoveToList(b, m, belofte::cWhiteKingClass->isAttacked(newboard, newboard.getWhiteKingPos()));
  return 1;
}
 
/**
 * Only add move to movelist if valid
 * @param b board on which move is calculated
 * @param m move to be added
 * @return number of moves added (4), meaning, player is not in check after move
 */
movenum_t bMoveList::addWhitePromotionIfValid(bBasicBoard const& b, bMove& m)
{
  m.setPawnMove();
  bBasicBoard newboard(b);
  newboard.applyWhiteMove(m);
  if (belofte::cWhiteKingClass->isAttacked(newboard, newboard.getWhiteKingPos())) return 0;
 
  // we are promoting, but did apply a dummy move on top
  // so modify dest board with custom pieces and check for in check
  case_t to = m.to();
  case_t bKingPos = newboard.getBlackKingPos();
 
  /// @todo optimize in case of uncover check just by moving pawn
  newboard.setPiece(to, tPiece::W_QUEEN);
  bool oppInCheckByQueen = belofte::cBlackKingClass->isAttacked(newboard, bKingPos);
  m.setPromotion(tPPiece::N_P_QUEEN);  addMoveToList(b, m, oppInCheckByQueen);
  m.clearIsCheck();
 
  newboard.setPiece(to, tPiece::W_KNIGHT);
  bool oppInCheck = belofte::cBlackKingClass->isAttacked(newboard, bKingPos);
  m.setPromotion(tPPiece::N_P_KNIGHT); addMoveToList(b, m, oppInCheck);
  m.clearIsCheck();
 
  newboard.setPiece(to, tPiece::W_ROOK);
  // do not re-evaluate check by rook if queen did not give check
  oppInCheck = oppInCheckByQueen && belofte::cBlackKingClass->isAttacked(newboard, bKingPos);
  m.setPromotion(tPPiece::N_P_ROOK);   addMoveToList(b, m, oppInCheck);
  m.clearIsCheck();
 
  newboard.setPiece(to, tPiece::W_BISHOP);
  oppInCheck = oppInCheckByQueen && belofte::cBlackKingClass->isAttacked(newboard, bKingPos);
  m.setPromotion(tPPiece::N_P_BISHOP); addMoveToList(b, m, oppInCheck);
  return 4;
}
 
/**
 * Only add move to movelist if valid
 * @param b board on which move is calculated
 * @param m move to be added
 * @return number of moves added (4), meaning, player is not in check after move
 */
movenum_t bMoveList::addBlackPromotionIfValid(bBasicBoard const& b, bMove& m)
{
  m.setPawnMove();
  bBasicBoard newboard(b);
  newboard.applyBlackMove(m);
  if (belofte::cBlackKingClass->isAttacked(newboard, newboard.getBlackKingPos())) return 0;
 
  // we are promoting, but did apply a dummy move on top
  // so modify dest board with custom pieces and check for in check
  case_t to = m.to();
  case_t wKingPos = newboard.getWhiteKingPos();
 
  /// @todo optimize in case of uncover check just by moving pawn
  newboard.setPiece(to, tPiece::B_QUEEN);
  bool oppInCheckByQueen = belofte::cWhiteKingClass->isAttacked(newboard, wKingPos);
  m.setPromotion(tPPiece::N_P_QUEEN);  addMoveToList(b, m, oppInCheckByQueen);
  m.clearIsCheck();
 
  newboard.setPiece(to, tPiece::B_KNIGHT);
  bool oppInCheck = belofte::cWhiteKingClass->isAttacked(newboard, wKingPos);
  m.setPromotion(tPPiece::N_P_KNIGHT); addMoveToList(b, m, oppInCheck);
  m.clearIsCheck();
 
  newboard.setPiece(to, tPiece::B_ROOK);
  // do not re-evaluate check by rook if queen did not give check
  oppInCheck = oppInCheckByQueen && belofte::cWhiteKingClass->isAttacked(newboard, wKingPos);
  m.setPromotion(tPPiece::N_P_ROOK);   addMoveToList(b, m, oppInCheck);
  m.clearIsCheck();
 
  newboard.setPiece(to, tPiece::B_BISHOP);
  oppInCheck = oppInCheckByQueen && belofte::cWhiteKingClass->isAttacked(newboard, wKingPos);
  m.setPromotion(tPPiece::N_P_BISHOP); addMoveToList(b, m, oppInCheck);
  return 4;
}
 
//-----------------------------------------------------------------------
 
/**
 * sort moves and update bestmove id
 * if less than 5 moves, sort all
 * if more than 5 moves, and less than 3 qs moves, sort 3 best
 * if more than 5 moves and at least 3 qs moves, sort qsmoves + 1
 * @param bFastSort only do partial sorting (default)
 * @todo allow for sorting the other way around and putting lowest score first
 */
void bMoveList::sortMoves(bool const bFastSort)
{
  size_t nMoves = m_lmoves.size();
  if (nMoves > 1) {
    clearIsOnlyMove();
    if (isNotSorted() && isNeedSorted()) {
      if (bFastSort && nMoves >= 5) {
        // 5 or more moves
        if (m_nQSMoves < 3) {
          // only interested in 3 best scores in case of a few QS moves
          // first 2 will be qs move, and a single non qsmove will be added
          std::partial_sort(m_lmoves.begin(), m_lmoves.begin() + 2, m_lmoves.end(),
            [](bMove const& a, bMove const& b) { return a > b; });
        } else if (m_nQSMoves < nMoves) {
          // interested in all m_nQSMoves + 1 best scores
          std::partial_sort(m_lmoves.begin(), m_lmoves.begin() + m_nQSMoves, m_lmoves.end(),
            [](bMove const& a, bMove const& b) { return a > b; });
        } else {
          // all moves are qs moves and there are 5 or more moves
          std::sort(m_lmoves.begin(), m_lmoves.end(),
            [](bMove const& a, bMove const& b) { return a > b; });
        }
      } else {
        // sort all in case of 1 to 4 elements or full sort
        std::sort(m_lmoves.begin(), m_lmoves.end(),
          [](bMove const& a, bMove const& b) { return a > b; });
      }
      setBestMoveId(1);
      setIsSorted();
    }
  } else if (nMoves == 1) {
    setBestMoveId(1);
    setIsOnlyMove();
  } else {
    clearBestMoveId();
  }
#if defined(INCOMPLETE_C11)
  setIsSorted();
#endif
}
 
//-----------------------------------------------------------------------
 
/**
 * generate moves if not yet generated
 * @param b board to generate moves
 * @return number of moves generated
 */
movenum_t bMoveList::generateMoves(bBasicBoard const& b)
{
  if (!isGenerated()) {
    setIsGenerated();
    side_t sidetomove = b.getColourToMove();
    if (sidetomove == tSide::SIDE_WHITE) {
      for (case_t iCase = 0; iCase < 64; ++iCase) {
        piece_t p = b.getPiece(iCase);
        if (bPiece::isWhitePiece(p)) {
          (bPiece::getPieceClass(p))->GenerateMoves(b, iCase, *this);
        }
      }
    } else {
      for (case_t iCase = 64; iCase > 0;) {
        --iCase;
        piece_t p = b.getPiece(iCase);
        if (bPiece::isBlackPiece(p)) {
          (bPiece::getPieceClass(p))->GenerateMoves(b, iCase, *this);
        }
      }
    }
  }
 
  if (getNumberOfMoves()) {
    setIsPossibleMove();
    return getNumberOfMoves();
  }
  return 0;
}
 
void bMoveList::emptyMoveList()
{
  m_lmoves.clear();
  clearIsGenerated();
  setIsSorted(); // if no moves or a single move is registered, sorted flag is set
  clearIsPossibleMove();
  m_nQSMoves = 0;
  clearBestMoveId();
}
 
/**
 * reduce the number of QS moves to filter out the best ones only
 */
movenum_t bMoveList::adjustQSMoves()
{
  if (m_bestmoveid && (m_nQSMoves > 1) && isSorted()) {
    // there is more than 1 QS move and all moves are sorted
    // break QS moves on move that is much worse than the best moves
    bScore currentScore = m_lmoves[m_bestmoveid - 1].getScore();
    for (movenum_t nMoveID = 1; nMoveID < m_nQSMoves - 1 && nMoveID < m_lmoves.size() - 1; ++nMoveID) {
      if (m_lmoves[nMoveID].getScore() < currentScore - 200) {
        // next move in ordered list is less than 200 points below previous one
        m_nQSMoves = nMoveID;
        break;
      }
    }
  }
  return m_nQSMoves;
}
 
/**
 * see if at least one move can be played e.g. (stale-)mate eval
 * called from addMoveToList, iterative search main loop and gameEndedResult
 */
bool bMoveList::atLeastOneMovePossible(bBasicBoard& b)
{
  if (isPossibleMove()) return true;
 
  if (b.getColourToMove() == tSide::SIDE_WHITE) {
    if (bPiece::getPieceClass(tPiece::W_KING)->hasValidMovePreflightCheck(b, b.getWhiteKingPos()))
        { setIsPossibleMove(); return true; }
    for (case_t iCase = 0; iCase < 64; ++iCase) {
      piece_t p = b.getPiece(iCase);
      if (bPiece::isWhitePiece(p) && p != tPiece::W_KING) {
        if (bPiece::getPieceClass(p)->hasValidMovePreflightCheck(b, iCase))
          { setIsPossibleMove(); return true; }
      }
    }
  } else {
    if (bPiece::getPieceClass(tPiece::B_KING)->hasValidMovePreflightCheck(b, b.getBlackKingPos()))
        { setIsPossibleMove(); return true; }
    for (case_t iCase = 64; iCase > 0;) {
      --iCase;
      piece_t p = b.getPiece(iCase);
      if (bPiece::isBlackPiece(p) && p != tPiece::B_KING) {
        if (bPiece::getPieceClass(p)->hasValidMovePreflightCheck(b, iCase))
          { setIsPossibleMove(); return true; }
      }
    }
  }
  return false;
}
 
//-----------------------------------------------------------------------
 
std::ostream& operator<<(std::ostream& os, bMoveList const& ml)
{
  os << "#" << static_cast<int>(ml.getNumberOfMoves()) << " ";
  if (ml.getNumberOfQSMoves()) {
     os << "QS #" << static_cast<int>(ml.getNumberOfQSMoves()) << " ";
  }
  for (bMove const& m: ml.m_lmoves) {
    os << m << m.getMoveEvalStr() << " ";
  }
  return os;
}
 
// eof