1 /* 2 Stockfish, a UCI chess playing engine derived from Glaurung 2.1 3 Copyright (C) 2004-2021 The Stockfish developers (see AUTHORS file) 4 5 Stockfish is free software: you can redistribute it and/or modify 6 it under the terms of the GNU General Public License as published by 7 the Free Software Foundation, either version 3 of the License, or 8 (at your option) any later version. 9 10 Stockfish is distributed in the hope that it will be useful, 11 but WITHOUT ANY WARRANTY; without even the implied warranty of 12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 13 GNU General Public License for more details. 14 15 You should have received a copy of the GNU General Public License 16 along with this program. If not, see <http://www.gnu.org/licenses/>. 17 */ 18 19 #ifndef TT_H_INCLUDED 20 #define TT_H_INCLUDED 21 22 #include "misc.h" 23 #include "types.h" 24 25 namespace Stockfish { 26 27 /// TTEntry struct is the 10 bytes transposition table entry, defined as below: 28 /// 29 /// key 16 bit 30 /// depth 8 bit 31 /// generation 5 bit 32 /// pv node 1 bit 33 /// bound type 2 bit 34 /// move 16 bit 35 /// value 16 bit 36 /// eval value 16 bit 37 38 struct TTEntry { 39 moveTTEntry40 Move move() const { return (Move )move16; } valueTTEntry41 Value value() const { return (Value)value16; } evalTTEntry42 Value eval() const { return (Value)eval16; } depthTTEntry43 Depth depth() const { return (Depth)depth8 + DEPTH_OFFSET; } is_pvTTEntry44 bool is_pv() const { return (bool)(genBound8 & 0x4); } boundTTEntry45 Bound bound() const { return (Bound)(genBound8 & 0x3); } 46 void save(Key k, Value v, bool pv, Bound b, Depth d, Move m, Value ev); 47 48 private: 49 friend class TranspositionTable; 50 51 uint16_t key16; 52 uint8_t depth8; 53 uint8_t genBound8; 54 uint16_t move16; 55 int16_t value16; 56 int16_t eval16; 57 }; 58 59 60 /// A TranspositionTable is an array of Cluster, of size clusterCount. Each 61 /// cluster consists of ClusterSize number of TTEntry. Each non-empty TTEntry 62 /// contains information on exactly one position. The size of a Cluster should 63 /// divide the size of a cache line for best performance, as the cacheline is 64 /// prefetched when possible. 65 66 class TranspositionTable { 67 68 static constexpr int ClusterSize = 3; 69 70 struct Cluster { 71 TTEntry entry[ClusterSize]; 72 char padding[2]; // Pad to 32 bytes 73 }; 74 75 static_assert(sizeof(Cluster) == 32, "Unexpected Cluster size"); 76 77 // Constants used to refresh the hash table periodically 78 static constexpr unsigned GENERATION_BITS = 3; // nb of bits reserved for other things 79 static constexpr int GENERATION_DELTA = (1 << GENERATION_BITS); // increment for generation field 80 static constexpr int GENERATION_CYCLE = 255 + (1 << GENERATION_BITS); // cycle length 81 static constexpr int GENERATION_MASK = (0xFF << GENERATION_BITS) & 0xFF; // mask to pull out generation number 82 83 public: ~TranspositionTable()84 ~TranspositionTable() { aligned_large_pages_free(table); } new_search()85 void new_search() { generation8 += GENERATION_DELTA; } // Lower bits are used for other things 86 TTEntry* probe(const Key key, bool& found) const; 87 int hashfull() const; 88 void resize(size_t mbSize); 89 void clear(); 90 first_entry(const Key key)91 TTEntry* first_entry(const Key key) const { 92 return &table[mul_hi64(key, clusterCount)].entry[0]; 93 } 94 95 private: 96 friend struct TTEntry; 97 98 size_t clusterCount; 99 Cluster* table; 100 uint8_t generation8; // Size must be not bigger than TTEntry::genBound8 101 }; 102 103 extern TranspositionTable TT; 104 105 } // namespace Stockfish 106 107 #endif // #ifndef TT_H_INCLUDED 108