-/// 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.
-
-void TranspositionTable::new_search() {
-
- generation++;
- writes = 0;
+/// 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.
+
+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
+
+ for (int i = 0; i < ClusterSize; ++i)
+ if (!tte[i].key16 || tte[i].key16 == key16)
+ {
+ tte[i].genBound8 = uint8_t(generation8 | tte[i].bound()); // Refresh
+
+ 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];
+
+ return found = false, replace;