Subversion Repositories Games.Chess Giants

/*

    Texel - A UCI chess engine.

    Copyright (C) 2012-2014  Peter Österlund, peterosterlund2@gmail.com

    This program is free software: you can redistribute it and/or modify

    it under the terms of the GNU General Public License as published by

    the Free Software Foundation, either version 3 of the License, or

    (at your option) any later version.

    This program is distributed in the hope that it will be useful,

    but WITHOUT ANY WARRANTY; without even the implied warranty of

    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the

    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License

    along with this program.  If not, see <http://www.gnu.org/licenses/>.

*/

/*

 * search.hpp

 *

 *  Created on: Feb 25, 2012

 *      Author: petero

 */

#ifndef SEARCH_HPP_

#define SEARCH_HPP_

#include "constants.hpp"

#include "position.hpp"

#include "killerTable.hpp"

#include "history.hpp"

#include "transpositionTable.hpp"

#include "evaluate.hpp"

#include "treeLogger.hpp"

#include "moveGen.hpp"

#include "searchUtil.hpp"

#include "parallel.hpp"

#include "util/histogram.hpp"

#include <limits>

#include <memory>

class SearchTest;

class ChessTool;

class PosGenerator;

/** Implements the nega-scout search algorithm. */

class Search {

    friend class SearchTest;

    friend class ChessTool;

    friend class PosGenerator;

public:

    /** Help tables used by the search. */

    struct SearchTables {

        SearchTables(TranspositionTable& tt0, KillerTable& kt0, History& ht0,

                     Evaluate::EvalHashTables& et0);

        TranspositionTable& tt;

        KillerTable& kt;

        History& ht;

        Evaluate::EvalHashTables& et;

    };

    /** Constructor. */

    Search(const Position& pos, const std::vector<U64>& posHashList,

           int posHashListSize, SearchTables& st,

           ParallelData& pd, const std::shared_ptr<SplitPoint>& rootSp,

           TreeLogger& logFile);

    Search(const Search& other) = delete;

    Search& operator=(const Search& other) = delete;

    /** Interface for reporting search information during search. */

    class Listener {

    public:

        virtual void notifyDepth(int depth) = 0;

        virtual void notifyCurrMove(const Move& m, int moveNr) = 0;

        virtual void notifyPV(int depth, int score, int time, U64 nodes, int nps,

                              bool isMate, bool upperBound, bool lowerBound,

                              const std::vector<Move>& pv, int multiPVIndex,

                              U64 tbHits) = 0;

        virtual void notifyStats(U64 nodes, int nps, U64 tbHits, int time) = 0;

    };

    void setListener(const std::shared_ptr<Listener>& listener);

    /** Exception thrown to stop the search. */

    class StopSearch : public std::exception {

    };

    class StopHandler {

    public:

        virtual bool shouldStop() = 0;

    };

    void setStopHandler(const std::shared_ptr<StopHandler>& stopHandler);

    /** Set which thread is owning this Search object. */

    void setThreadNo(int tNo);

    void timeLimit(int minTimeLimit, int maxTimeLimit);

    void setStrength(int strength, U64 randomSeed);

    /** Set minimum depth for TB probes. */

    void setMinProbeDepth(int depth);

    Move iterativeDeepening(const MoveList& scMovesIn,

                            int maxDepth, U64 initialMaxNodes, bool verbose,

                            int maxPV = 1, bool onlyExact = false,

                            int minProbeDepth = 0);

    /**

     * Main recursive search algorithm.

     * @return Score for the side to make a move, in position given by "pos".

     */

    template <bool smp, bool tb>

    int negaScout(int alpha, int beta, int ply, int depth, int recaptureSquare,

                  const bool inCheck);

    int negaScout(bool smp, bool tb,

                  int alpha, int beta, int ply, int depth, int recaptureSquare,

                  const bool inCheck);

    int negaScout(int alpha, int beta, int ply, int depth, int recaptureSquare,

                  const bool inCheck);

    /** Compute extension depth for a move. */

    int getMoveExtend(const Move& m, int recaptureSquare);

    static bool canClaimDraw50(const Position& pos);

    static bool canClaimDrawRep(const Position& pos, const std::vector<U64>& posHashList,

                                int posHashListSize, int posHashFirstNew);

    /**

     * Compute scores for each move in a move list, using SEE, killer and history information.

     * @param moves  List of moves to score.

     */

    void scoreMoveList(MoveList& moves, int ply, int startIdx = 0);

    /** Set search tree information for a given ply. */

    void setSearchTreeInfo(int ply, const SearchTreeInfo& sti,

                           const Move& currMove, int currMoveNo, int lmr,

                           U64 rootNodeIdx);

    /** Get total number of nodes searched by this thread. */

    S64 getTotalNodesThisThread() const;

    /** Get number of TB hits for this thread. */

    S64 getTbHitsThisThread() const;

private:

    void init(const Position& pos0, const std::vector<U64>& posHashList0,

              int posHashListSize0);

    /** Information used for move ordering at root and for PV reporting. */

    struct MoveInfo {

        Move move;

        U64 nodes;

        int depth, alpha, beta;

        std::vector<Move> pv;

        MoveInfo(const Move& m, int n)

            : move(m), nodes(n), depth(0), alpha(0), beta(0) {}

        int score() const { return move.score(); }

        struct SortByScore {

            bool operator()(const MoveInfo& mi1, const MoveInfo& mi2) const {

                return mi1.move.score() > mi2.move.score();

            }

        };

        struct SortByNodes {

            bool operator()(const MoveInfo& mi1, const MoveInfo& mi2) {

                return mi1.nodes > mi2.nodes;

            }

        };

    };

    /** Store depth, alpha, beta, score and pv in scMoves[mi]. */

    void storeSearchResult(std::vector<MoveInfo>& scMoves, int mi, int depth,

                           int alpha, int beta, int score);

    /** Report PV information to listener. */

    void notifyPV(const std::vector<MoveInfo>& moveInfo, int mi, int maxPV);

    void notifyPV(const MoveInfo& info, int multiPVIndex);

    /** Report search statistics to listener. */

    void notifyStats();

    /** Get total number of nodes searched by all threads. */

    S64 getTotalNodes() const;

    /** Get total number of TB hits for all threads. */

    S64 getTbHits() const;

    /** Determine which root moves to search, taking low strength and

     *  missing TB files into account. */

    void getRootMoves(const MoveList& rootMovesIn,

                      std::vector<MoveInfo>& rootMovesOut,

                      int maxDepth);

    /** Return true if move should be skipped in order to make engine play weaker. */

    bool weakPlaySkipMove(const Position& pos, const Move& m, int ply) const;

    static bool passedPawnPush(const Position& pos, const Move& m);

    /** Quiescence search. Only non-losing captures are searched. */

    int quiesce(int alpha, int beta, int ply, int depth, const bool inCheck);

    /**

     * Static exchange evaluation function.

     * @return SEE score for m. Positive value is good for the side that makes the first move.

     */

    int SEE(const Move& m);

    /** Return >0, 0, <0, depending on the sign of SEE(m). */

    int signSEE(const Move& m);

    /** Return true if SEE(m) < 0. */

    bool negSEE(const Move& m);

    /** Score move list according to most valuable victim / least valuable attacker. */

    void scoreMoveListMvvLva(MoveList& moves) const;

    /** Find move with highest score and move it to the front of the list. */

    static void selectBest(MoveList& moves, int startIdx);

    /** If hashMove exists in the move list, move the hash move to the front of the list. */

    static bool selectHashMove(MoveList& moves, const Move& hashMove);

    void initNodeStats();

    class DefaultStopHandler : public StopHandler {

    public:

        DefaultStopHandler(Search& sc0) : sc(sc0) { }

        bool shouldStop() { return sc.shouldStop(); }

    private:

        Search& sc;

    };

    /** Return true if the search should be stopped immediately. */

    bool shouldStop();

    Position pos;

    Evaluate eval;

    KillerTable& kt;

    History& ht;

    std::vector<U64> posHashList; // List of hashes for previous positions up to the last "zeroing" move.

    int posHashListSize;          // Number of used entries in posHashList

    int posHashFirstNew;          // First entry in posHashList that has not been played OTB.

    TranspositionTable& tt;

    ParallelData& pd;

    std::vector<std::shared_ptr<SplitPoint>> spVec;

    std::vector<std::shared_ptr<SplitPoint>> pending;

    int threadNo;

    bool mainNumaNode; // True if this thread runs on the NUMA node holding the transposition table

    TreeLogger& logFile;

    std::shared_ptr<Listener> listener;

    std::shared_ptr<StopHandler> stopHandler;

    Move emptyMove;

    static const int MAX_SEARCH_DEPTH = 100;

    SearchTreeInfo searchTreeInfo[MAX_SEARCH_DEPTH * 2];

    // Time management

    S64 tStart;                // Time when search started

    RelaxedShared<S64> minTimeMillis; // Minimum recommended thinking time

    RelaxedShared<S64> maxTimeMillis; // Maximum allowed thinking time

    bool searchNeedMoreTime;   // True if negaScout should use up to maxTimeMillis time.

    S64 maxNodes;              // Maximum number of nodes to search (approximately)

    int minProbeDepth;         // Minimum depth to probe endgame tablebases.

    int nodesToGo;             // Number of nodes until next time check

    RelaxedShared<int> nodesBetweenTimeCheck; // How often to check remaining time

    // Reduced strength variables

    int strength;              // Strength (0-1000)

    bool weak;                 // True if strength < 1000

    U64 randomSeed;

    // Search statistics stuff

    Histogram<0,20> nodesByPly, nodesByDepth;

    S64 totalNodes;

    S64 tbHits;

    S64 tLastStats;        // Time when notifyStats was last called

    bool verbose;

    int q0Eval; // Static eval score at first level of quiescence search

};

inline

Search::SearchTables::SearchTables(TranspositionTable& tt0, KillerTable& kt0, History& ht0,

                                   Evaluate::EvalHashTables& et0)

    : tt(tt0), kt(kt0), ht(ht0), et(et0) {

}

inline void

Search::setListener(const std::shared_ptr<Listener>& listener) {

    this->listener = listener;

}

inline void

Search::setStopHandler(const std::shared_ptr<StopHandler>& stopHandler) {

    this->stopHandler = stopHandler;

}

inline bool

Search::canClaimDrawRep(const Position& pos, const std::vector<U64>& posHashList,

                       int posHashListSize, int posHashFirstNew) {

    int reps = 0;

    int stop = std::max(0, posHashListSize - pos.getHalfMoveClock());

    for (int i = posHashListSize - 4; i >= stop; i -= 2) {

        if (pos.zobristHash() == posHashList[i]) {

            reps++;

            if ((i >= posHashFirstNew) || (reps >= 2))

                return true;

        }

    }

    return false;

}

inline bool

Search::passedPawnPush(const Position& pos, const Move& m) {

    int p = pos.getPiece(m.from());

    if (pos.isWhiteMove()) {

        if (p != Piece::WPAWN)

            return false;

        if ((BitBoard::wPawnBlockerMask[m.to()] & pos.pieceTypeBB(Piece::BPAWN)) != 0)

            return false;

        return m.to() >= 40;

    } else {

        if (p != Piece::BPAWN)

            return false;

        if ((BitBoard::bPawnBlockerMask[m.to()] & pos.pieceTypeBB(Piece::WPAWN)) != 0)

            return false;

        return m.to() <= 23;

    }

}

inline int

Search::signSEE(const Move& m) {

    int p0 = ::pieceValue[pos.getPiece(m.from())];

    int p1 = ::pieceValue[pos.getPiece(m.to())];

    if (p0 < p1)

        return 1;

    return SEE(m);

}

inline bool

Search::negSEE(const Move& m) {

    int p0 = ::pieceValue[pos.getPiece(m.from())];

    int p1 = ::pieceValue[pos.getPiece(m.to())];

    if (p1 >= p0)

        return false;

    return SEE(m) < 0;

}

inline void

Search::scoreMoveListMvvLva(MoveList& moves) const {

    for (int i = 0; i < moves.size; i++) {

        Move& m = moves[i];

        int v = pos.getPiece(m.to());

        int a = pos.getPiece(m.from());

        m.setScore(Evaluate::pieceValueOrder[v] * 8 - Evaluate::pieceValueOrder[a]);

    }

}

inline void

Search::selectBest(MoveList& moves, int startIdx) {

    int bestIdx = startIdx;

    int bestScore = moves[bestIdx].score();

    for (int i = startIdx + 1; i < moves.size; i++) {

        int sc = moves[i].score();

        if (sc > bestScore) {

            bestIdx = i;

            bestScore = sc;

        }

    }

    std::swap(moves[bestIdx], moves[startIdx]);

}

inline void

Search::setSearchTreeInfo(int ply, const SearchTreeInfo& sti, const Move& currMove,

                          int currMoveNo, int lmr, U64 rootNodeIdx) {

    searchTreeInfo[ply] = sti;

    searchTreeInfo[ply].currentMove = currMove;

    searchTreeInfo[ply].currentMoveNo = currMoveNo;

    searchTreeInfo[ply].lmr = lmr;

    searchTreeInfo[ply].nodeIdx = rootNodeIdx;

}

inline int

Search::negaScout(bool smp, bool tb,

                  int alpha, int beta, int ply, int depth, int recaptureSquare,

                  const bool inCheck) {

    using namespace SearchConst;

    int minDepth = pd.wq.getMinSplitDepth() * plyScale;

    if (threadNo == 0)

        minDepth = (minDepth + MIN_SMP_DEPTH * plyScale) / 2;

    if (smp && (depth >= minDepth) &&

               ((int)spVec.size() < MAX_SP_PER_THREAD)) {

        bool tb2 = tb && depth >= minProbeDepth;

        if (tb2)

            return negaScout<true,true>(alpha, beta, ply, depth, recaptureSquare, inCheck);

        else

            return negaScout<true,false>(alpha, beta, ply, depth, recaptureSquare, inCheck);

    } else {

        bool tb2 = tb && depth >= minProbeDepth;

        if (tb2)

            return negaScout<false,true>(alpha, beta, ply, depth, recaptureSquare, inCheck);

        else

            return negaScout<false,false>(alpha, beta, ply, depth, recaptureSquare, inCheck);

    }

}

inline int

Search::negaScout(int alpha, int beta, int ply, int depth, int recaptureSquare,

                  const bool inCheck) {

    return negaScout<false,false>(alpha, beta, ply, depth, recaptureSquare, inCheck);

}

inline bool

Search::canClaimDraw50(const Position& pos) {

    return (pos.getHalfMoveClock() >= 100);

}

inline S64

Search::getTotalNodes() const {

    return totalNodes + pd.getNumSearchedNodes();

}

inline S64

Search::getTotalNodesThisThread() const {

    return totalNodes;

}

inline S64

Search::getTbHits() const {

    return tbHits + pd.getTbHits();

}

inline S64

Search::getTbHitsThisThread() const {

    return tbHits;

}

inline void

Search::setMinProbeDepth(int depth) {

    minProbeDepth = depth * SearchConst::plyScale;

}

#endif /* SEARCH_HPP_ */