X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Ftt.cpp;h=3c43e12ce58cb17e5bc376feda94b60ab468430e;hp=01d4365522a772af5a09887106a3372d8044cd6f;hb=b96dd754ede60b8463606cf38eac3eab400a123d;hpb=bb751d6c890f5c50c642366d601740366cfae8d0 diff --git a/src/tt.cpp b/src/tt.cpp index 01d43655..3c43e12c 100644 --- a/src/tt.cpp +++ b/src/tt.cpp @@ -1,230 +1,117 @@ /* - Glaurung, a UCI chess playing engine. - Copyright (C) 2004-2008 Tord Romstad + Stockfish, a UCI chess playing engine derived from Glaurung 2.1 + Copyright (C) 2004-2008 Tord Romstad (Glaurung author) + Copyright (C) 2008-2015 Marco Costalba, Joona Kiiski, Tord Romstad + Copyright (C) 2015-2016 Marco Costalba, Joona Kiiski, Gary Linscott, Tord Romstad - Glaurung is free software: you can redistribute it and/or modify + Stockfish 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. - - Glaurung is distributed in the hope that it will be useful, + + Stockfish 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 . */ +#include // For std::memset +#include -//// -//// Includes -//// - -#include -#include - +#include "bitboard.h" #include "tt.h" +TranspositionTable TT; // Our global transposition table -//// -//// Functions -//// - -/// Constructor -TranspositionTable::TranspositionTable(unsigned mbSize) { - size = 0; - generation = 0; - writes = 0; - entries = 0; - this->set_size(mbSize); -} +/// TranspositionTable::resize() sets the size of the transposition table, +/// measured in megabytes. Transposition table consists of a power of 2 number +/// of clusters and each cluster consists of ClusterSize number of TTEntry. +void TranspositionTable::resize(size_t mbSize) { -/// Destructor + size_t newClusterCount = size_t(1) << msb((mbSize * 1024 * 1024) / sizeof(Cluster)); -TranspositionTable::~TranspositionTable() { - delete [] entries; -} - - -/// TranspositionTable::set_size sets the size of the transposition table, -/// measured in megabytes. - -void TranspositionTable::set_size(unsigned mbSize) { - unsigned newSize; + if (newClusterCount == clusterCount) + return; - assert(mbSize >= 4 && mbSize <= 1024); + clusterCount = newClusterCount; - for(newSize = 1024; newSize * 4 * (sizeof(TTEntry)) <= (mbSize << 20); - newSize *= 2); - newSize /= 2; + free(mem); + mem = calloc(clusterCount * sizeof(Cluster) + CacheLineSize - 1, 1); - if(newSize != size) { - size = newSize; - delete [] entries; - entries = new TTEntry[size * 4]; - if(entries == NULL) { + if (!mem) + { std::cerr << "Failed to allocate " << mbSize - << " MB for transposition table." - << std::endl; + << "MB for transposition table." << std::endl; exit(EXIT_FAILURE); - } - this->clear(); } + + table = (Cluster*)((uintptr_t(mem) + CacheLineSize - 1) & ~(CacheLineSize - 1)); } -/// TranspositionTable::clear overwrites the entire transposition table -/// with zeroes. It is called whenever the table is resized, or when the +/// TranspositionTable::clear() overwrites the entire transposition table +/// with zeros. It is called whenever the table is resized, or when the /// user asks the program to clear the table (from the UCI interface). -/// Perhaps we should also clear it when the "ucinewgame" command is recieved? void TranspositionTable::clear() { - memset(entries, 0, size * 4 * sizeof(TTEntry)); -} - - -/// TranspositionTable::store writes a new entry containing a position, -/// a value, a value type, a search depth, and a best move to the -/// transposition table. The transposition table is organized in clusters -/// of four TTEntry objects, and when a new entry is written, it replaces -/// the least valuable of the four entries in a cluster. A TTEntry t1 is -/// considered to be more valuable than a TTEntry t2 if t1 is from the -/// current search and t2 is from a previous search, or if the depth of t1 -/// is bigger than the depth of t2. - -void TranspositionTable::store(const Position &pos, Value v, Depth d, - Move m, ValueType type) { - TTEntry *tte, *replace; - - tte = replace = entries + int(pos.get_key() & (size - 1)) * 4; - for(int i = 0; i < 4; i++) { - if((tte+i)->key() == pos.get_key()) { - if(m == MOVE_NONE) - m = (tte+i)->move(); - *(tte+i) = TTEntry(pos.get_key(), v, type, d, m, generation); - return; - } - if(replace->generation() == generation) { - if((tte+i)->generation() != generation || - (tte+i)->depth() < replace->depth()) - replace = tte+i; - } - else if((tte+i)->generation() != generation && - (tte+i)->depth() < replace->depth()) - replace = tte+i; - } - *replace = TTEntry(pos.get_key(), v, type, d, m, generation); - writes++; -} - - -/// TranspositionTable::retrieve looks up the current position in the -/// transposition table, and extracts the value, value type, depth and -/// best move if the position is found. The return value is true if -/// the position is found, and false if it isn't. - -bool TranspositionTable::retrieve(const Position &pos, Value *value, - Depth *d, Move *move, - ValueType *type) const { - TTEntry *tte; - bool found = false; - - tte = entries + int(pos.get_key() & (size - 1)) * 4; - for(int i = 0; i < 4 && !found ; i++) - if((tte+i)->key() == pos.get_key()) { - tte = tte + i; - found = true; - } - if(!found) { - *move = MOVE_NONE; - return false; - } - - *value = tte->value(); - *type = tte->type(); - *d = tte->depth(); - *move = tte->move(); - return true; + std::memset(table, 0, clusterCount * sizeof(Cluster)); } -/// TranspositionTable::new_search() is called at the beginning of every new -/// search. It increments the "generation" variable, which is used to -/// distinguish transposition table entries from previous searches from -/// entries from the current search. +/// TranspositionTable::probe() looks up the current position in the transposition +/// table. It returns true and a pointer to the TTEntry if the position is found. +/// Otherwise, it returns false and a pointer to an empty or least valuable TTEntry +/// to be replaced later. The replace value of an entry is calculated as its depth +/// minus 8 times its relative age. TTEntry t1 is considered more valuable than +/// TTEntry t2 if its replace value is greater than that of t2. -void TranspositionTable::new_search() { - generation++; - writes = 0; -} - - -/// TranspositionTable::insert_pv() is called at the end of a search -/// iteration, and inserts the PV back into the PV. This makes sure the -/// old PV moves are searched first, even if the old TT entries have been -/// overwritten. - -void TranspositionTable::insert_pv(const Position &pos, Move pv[]) { - UndoInfo u; - Position p(pos); - - for(int i = 0; pv[i] != MOVE_NONE; i++) { - this->store(p, VALUE_NONE, Depth(0), pv[i], VALUE_TYPE_NONE); - p.do_move(pv[i], u); - } -} - - -/// TranspositionTable::full() returns the permill of all transposition table -/// entries which have received at least one write during the current search. -/// It is used to display the "info hashfull ..." information in UCI. - -int TranspositionTable::full() { - double N = double(size) * 4.0; - return int(1000 * (1 - exp(writes * log(1.0 - 1.0/N)))); -} +TTEntry* TranspositionTable::probe(const Key key, bool& found) const { + TTEntry* const tte = first_entry(key); + const uint16_t key16 = key >> 48; // Use the high 16 bits as key inside the cluster -/// Constructors + for (int i = 0; i < ClusterSize; ++i) + if (!tte[i].key16 || tte[i].key16 == key16) + { + if ((tte[i].genBound8 & 0xFC) != generation8 && tte[i].key16) + tte[i].genBound8 = uint8_t(generation8 | tte[i].bound()); // Refresh -TTEntry::TTEntry() { -} - -TTEntry::TTEntry(Key k, Value v, ValueType t, Depth d, Move m, - int generation) { - key_ = k; - data = (m & 0x7FFFF) | (t << 20) | (generation << 23); - value_ = v; - depth_ = int16_t(d); -} + return found = (bool)tte[i].key16, &tte[i]; + } + // Find an entry to be replaced according to the replacement strategy + TTEntry* replace = tte; + for (int i = 1; i < ClusterSize; ++i) + // Due to our packed storage format for generation and its cyclic + // nature we add 259 (256 is the modulus plus 3 to keep the lowest + // two bound bits from affecting the result) to calculate the entry + // age correctly even after generation8 overflows into the next cycle. + if ( replace->depth8 - ((259 + generation8 - replace->genBound8) & 0xFC) * 2 + > tte[i].depth8 - ((259 + generation8 - tte[i].genBound8) & 0xFC) * 2) + replace = &tte[i]; -/// Functions for extracting data from TTEntry objects. - -Key TTEntry::key() const { - return key_; + return found = false, replace; } -Depth TTEntry::depth() const { - return Depth(depth_); -} -Move TTEntry::move() const { - return Move(data & 0x7FFFF); -} +/// Returns an approximation of the hashtable occupation during a search. The +/// hash is x permill full, as per UCI protocol. -Value TTEntry::value() const { - return Value(value_); -} - -ValueType TTEntry::type() const { - return ValueType((data >> 20) & 3); -} - -int TTEntry::generation() const { - return (data >> 23); +int TranspositionTable::hashfull() const +{ + int cnt = 0; + for (int i = 0; i < 1000 / ClusterSize; i++) + { + const TTEntry* tte = &table[i].entry[0]; + for (int j = 0; j < ClusterSize; j++) + if ((tte[j].genBound8 & 0xFC) == generation8) + cnt++; + } + return cnt; }