]> git.sesse.net Git - stockfish/blob - src/tt.h
VLTC Search parameters tune
[stockfish] / src / tt.h
1 /*
2   Stockfish, a UCI chess playing engine derived from Glaurung 2.1
3   Copyright (C) 2004-2023 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 <cstddef>
23 #include <cstdint>
24
25 #include "misc.h"
26 #include "types.h"
27
28 namespace Stockfish {
29
30 // TTEntry struct is the 10 bytes transposition table entry, defined as below:
31 //
32 // key        16 bit
33 // depth       8 bit
34 // generation  5 bit
35 // pv node     1 bit
36 // bound type  2 bit
37 // move       16 bit
38 // value      16 bit
39 // eval value 16 bit
40 struct TTEntry {
41
42     Move  move() const { return Move(move16); }
43     Value value() const { return Value(value16); }
44     Value eval() const { return Value(eval16); }
45     Depth depth() const { return Depth(depth8 + DEPTH_OFFSET); }
46     bool  is_pv() const { return bool(genBound8 & 0x4); }
47     Bound bound() const { return Bound(genBound8 & 0x3); }
48     void  save(Key k, Value v, bool pv, Bound b, Depth d, Move m, Value ev);
49
50    private:
51     friend class TranspositionTable;
52
53     uint16_t key16;
54     uint8_t  depth8;
55     uint8_t  genBound8;
56     uint16_t move16;
57     int16_t  value16;
58     int16_t  eval16;
59 };
60
61
62 // A TranspositionTable is an array of Cluster, of size clusterCount. Each
63 // cluster consists of ClusterSize number of TTEntry. Each non-empty TTEntry
64 // contains information on exactly one position. The size of a Cluster should
65 // divide the size of a cache line for best performance, as the cacheline is
66 // prefetched when possible.
67 class TranspositionTable {
68
69     static constexpr int ClusterSize = 3;
70
71     struct Cluster {
72         TTEntry entry[ClusterSize];
73         char    padding[2];  // Pad to 32 bytes
74     };
75
76     static_assert(sizeof(Cluster) == 32, "Unexpected Cluster size");
77
78     // Constants used to refresh the hash table periodically
79     static constexpr unsigned GENERATION_BITS = 3;  // nb of bits reserved for other things
80     static constexpr int      GENERATION_DELTA =
81       (1 << GENERATION_BITS);  // increment for generation field
82     static constexpr int GENERATION_CYCLE = 255 + (1 << GENERATION_BITS);  // cycle length
83     static constexpr int GENERATION_MASK =
84       (0xFF << GENERATION_BITS) & 0xFF;  // mask to pull out generation number
85
86    public:
87     ~TranspositionTable() { aligned_large_pages_free(table); }
88     void new_search() { generation8 += GENERATION_DELTA; }  // Lower bits are used for other things
89     TTEntry* probe(const Key key, bool& found) const;
90     int      hashfull() const;
91     void     resize(size_t mbSize);
92     void     clear();
93
94     TTEntry* first_entry(const Key key) const {
95         return &table[mul_hi64(key, clusterCount)].entry[0];
96     }
97
98    private:
99     friend struct TTEntry;
100
101     size_t   clusterCount;
102     Cluster* table;
103     uint8_t  generation8;  // Size must be not bigger than TTEntry::genBound8
104 };
105
106 extern TranspositionTable TT;
107
108 }  // namespace Stockfish
109
110 #endif  // #ifndef TT_H_INCLUDED