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/>.

*/

/*

 * transpositionTable.hpp

 *

 *  Created on: Feb 25, 2012

 *      Author: petero

 */

#ifndef TRANSPOSITIONTABLE_HPP_

#define TRANSPOSITIONTABLE_HPP_

#include "util/util.hpp"

#include "move.hpp"

#include "constants.hpp"

#include "util/alignedAlloc.hpp"

#include <vector>

class Position;

/**

 * Implements the main transposition table using Cuckoo hashing.

 */

class TranspositionTable {

public:

    /** In-memory representation of TT entry. Uses std::atomic for thread safety,

     * but accessed using memory_order_relaxed for maximum performance. */

    struct TTEntryStorage {

        std::atomic<U64> key;

        std::atomic<U64> data;

        TTEntryStorage();

        TTEntryStorage(const TTEntryStorage& a);

    };

    static_assert(sizeof(TTEntryStorage) == 16, "TTEntryStorage size wrong");

    /** A local copy of a transposition table entry. */

    class TTEntry {

    public:

        /** Set type to T_EMPTY. */

        void clear();

        /** Store in transposition table, encoded for thread safety. */

        void store(TTEntryStorage& ent);

        /** Load from transposition table, decode the thread safety encoding. */

        void load(const TTEntryStorage& ent);

        /** Return true if this object is more valuable than the other, false otherwise. */

        bool betterThan(const TTEntry& other, int currGen) const;

        U64 getKey() const;

        void setKey(U64 k);

        void getMove(Move& m) const;

        void setMove(const Move& m);

        /** Get the score from the hash entry and convert from "mate in x" to "mate at ply". */

        int getScore(int ply) const;

        /** Convert score from "mate at ply" to "mate in x" and store in hash entry. */

        void setScore(int score, int ply);

        /** Return true if entry is good enough to cut off this branch in the search tree. */

        bool isCutOff(int alpha, int beta, int ply, int depth) const;

        int getDepth() const;

        void setDepth(int d);

        int getGeneration() const;

        void setGeneration(int g);

        int getType() const;

        void setType(int t);

        int getEvalScore() const;

        void setEvalScore(int s);

    private:

        U64 key;        //  0 64 key         Zobrist hash key

        U64 data;       //  0 16 move        from + (to<<6) + (promote<<12)

                        // 16 16 score       Score from search

                        // 32 10 depth       Search depth

                        // 42  4 generation  Increase when OTB position changes

                        // 46  2 type        exact score, lower bound, upper bound

                        // 48 16 evalScore   Score from static evaluation

        void setBits(int first, int size, unsigned int value);

        unsigned int getBits(int first, int size) const;

    };

    /** Constructor. Creates an empty transposition table with numEntries slots. */

    TranspositionTable(int log2Size);

    void reSize(int log2Size);

    /** Insert an entry in the hash table. */

    void insert(U64 key, const Move& sm, int type, int ply, int depth, int evalScore);

    /** Retrieve an entry from the hash table corresponding to position with zobrist key "key". */

    void probe(U64 key, TTEntry& result);

    /** Prefetch cache line. */

    void prefetch(U64 key);

    /**

     * Increase hash table generation. This means that subsequent inserts will be considered

     * more valuable than the entries currently present in the hash table.

     */

    void nextGeneration();

    /** Clear the transposition table. */

    void clear();

    /** Extract a list of PV moves, starting from "rootPos" and first move "mFirst". */

    void extractPVMoves(const Position& rootPos, const Move& mFirst, std::vector<Move>& pv);

    /** Extract the PV starting from posIn, using hash entries, both exact scores and bounds. */

    std::string extractPV(const Position& posIn);

    /** Print hash table statistics. */

    void printStats() const;

private:

    /** Get position in hash table given zobrist key. */

    size_t getIndex(U64 key) const;

    /** Get part of zobrist key to store in hash table. */

    static U64 getStoredKey(U64 key);

    vector_aligned<TTEntryStorage> table;

    U8 generation;

};

inline

TranspositionTable::TTEntryStorage::TTEntryStorage() {

    key.store(0, std::memory_order_relaxed);

    data.store(0, std::memory_order_relaxed);

}

inline

TranspositionTable::TTEntryStorage::TTEntryStorage(const TTEntryStorage& a) {

    key.store(a.key.load(std::memory_order_relaxed), std::memory_order_relaxed);

    data.store(a.data.load(std::memory_order_relaxed), std::memory_order_relaxed);

}

inline void

TranspositionTable::TTEntry::clear() {

    key = 0;

    data = 0;

    static_assert(TType::T_EMPTY == 0, "type not set to T_EMPTY");

}

inline void

TranspositionTable::TTEntry::store(TTEntryStorage& ent) {

    ent.key.store(key ^ data, std::memory_order_relaxed);

    ent.data.store(data, std::memory_order_relaxed);

}

inline void

TranspositionTable::TTEntry::load(const TTEntryStorage& ent) {

    key = ent.key.load(std::memory_order_relaxed);

    data = ent.data.load(std::memory_order_relaxed);

    key ^= data;

}

inline bool

TranspositionTable::TTEntry::betterThan(const TTEntry& other, int currGen) const {

    if ((getGeneration() == currGen) != (other.getGeneration() == currGen))

        return getGeneration() == currGen;   // Old entries are less valuable

    if ((getType() == TType::T_EXACT) != (other.getType() == TType::T_EXACT))

        return getType() == TType::T_EXACT;         // Exact score more valuable than lower/upper bound

    if (getDepth() != other.getDepth())

        return getDepth() > other.getDepth();     // Larger depth is more valuable

    return false;   // Otherwise, pretty much equally valuable

}

inline U64

TranspositionTable::TTEntry::getKey() const {

    return key;

}

inline void

TranspositionTable::TTEntry::setKey(U64 k) {

    key = k;

}

inline void

TranspositionTable::TTEntry::getMove(Move& m) const {

    int move = getBits(0, 16);

    m.setMove(move & 63, (move >> 6) & 63, (move >> 12) & 15, m.score());

}

inline void

TranspositionTable::TTEntry::setMove(const Move& m) {

    int move = (short)(m.from() + (m.to() << 6) + (m.promoteTo() << 12));

    setBits(0, 16, move);

}

inline int

TranspositionTable::TTEntry::getScore(int ply) const {

    int sc = (S16)getBits(16, 16);

    if (SearchConst::isWinScore(sc))

        sc -= ply;

    else if (SearchConst::isLoseScore(sc))

        sc += ply;

    return sc;

}

inline void

TranspositionTable::TTEntry::setScore(int score, int ply) {

    if (SearchConst::isWinScore(score))

        score += ply;

    else if (SearchConst::isLoseScore(score))

        score -= ply;

    setBits(16, 16, score);

}

inline bool

TranspositionTable::TTEntry::isCutOff(int alpha, int beta, int ply, int depth) const {

    using namespace SearchConst;

    const int score = getScore(ply);

    const int plyToMate = MATE0 - std::abs(getScore(0));

    const int eDepth = getDepth();

    const int eType = getType();

    if ((eDepth >= depth) || (eDepth >= plyToMate*plyScale)) {

        if ( (eType == TType::T_EXACT) ||

            ((eType == TType::T_GE) && (score >= beta)) ||

            ((eType == TType::T_LE) && (score <= alpha)))

            return true;

    }

    return false;

}

inline int

TranspositionTable::TTEntry::getDepth() const {

    return getBits(32, 10);

}

inline void

TranspositionTable::TTEntry::setDepth(int d) {

    setBits(32, 10, d);

}

inline int

TranspositionTable::TTEntry::getGeneration() const {

    return getBits(42, 4);

}

inline void

TranspositionTable::TTEntry::setGeneration(int g) {

    setBits(42, 4, g);

}

inline int

TranspositionTable::TTEntry::getType() const {

    return getBits(46, 2);

}

inline void

TranspositionTable::TTEntry::setType(int t) {

    setBits(46, 2, t);

}

inline int

TranspositionTable::TTEntry::getEvalScore() const {

    return (S16)getBits(48, 16);

}

inline void

TranspositionTable::TTEntry::setEvalScore(int s) {

    setBits(48, 16, s);

}

inline void

TranspositionTable::TTEntry::setBits(int first, int size, unsigned int value) {

    U64 mask = ((1ULL << size) - 1) << first;

    data = (data & ~mask) | (((U64)value << first) & mask);

}

inline unsigned int

TranspositionTable::TTEntry::getBits(int first, int size) const {

    U64 sizeMask = ((1ULL << size) - 1);

    return (unsigned int)((data >> first) & sizeMask);

}

inline size_t

TranspositionTable::getIndex(U64 key) const {

    return (size_t)(key & (table.size() - 1));

}

inline U64

TranspositionTable::getStoredKey(U64 key) {

    return key;

}

inline TranspositionTable::TranspositionTable(int log2Size) {

    reSize(log2Size);

}

inline void

TranspositionTable::probe(U64 key, TTEntry& result) {

    size_t idx0 = getIndex(key);

    U64 key2 = getStoredKey(key);

    TTEntry ent;

    ent.load(table[idx0]);

    if (ent.getKey() == key2) {

        if (ent.getGeneration() != generation) {

            ent.setGeneration(generation);

            ent.store(table[idx0]);

        }

        result = ent;

        return;

    }

    size_t idx1 = idx0 ^ 1;

    ent.load(table[idx1]);

    if (ent.getKey() == key2) {

        if (ent.getGeneration() != generation) {

            ent.setGeneration(generation);

            ent.store(table[idx1]);

        }

        result = ent;

        return;

    }

    result.setType(TType::T_EMPTY);

}

inline void

TranspositionTable::prefetch(U64 key) {

#ifdef HAS_PREFETCH

    size_t idx0 = getIndex(key);

    __builtin_prefetch(&table[idx0]);

#endif

}

inline void

TranspositionTable::nextGeneration() {

    generation = (generation + 1) & 15;

}

inline void

TranspositionTable::clear() {

    TTEntry ent;

    ent.clear();

    for (size_t i = 0; i < table.size(); i++)

        ent.store(table[i]);

}

#endif /* TRANSPOSITIONTABLE_HPP_ */