Move pv[MAX_PLY+1], quietsSearched[64];
StateInfo st;
- const TTEntry *tte;
+ TTEntry* tte;
+ bool ttHit;
SplitPoint* splitPoint;
Key posKey;
Move ttMove, move, excludedMove, bestMove;
bestMove = splitPoint->bestMove;
bestValue = splitPoint->bestValue;
tte = NULL;
+ ttHit = false;
ttMove = excludedMove = MOVE_NONE;
ttValue = VALUE_NONE;
// TT value, so we use a different position key in case of an excluded move.
excludedMove = ss->excludedMove;
posKey = excludedMove ? pos.exclusion_key() : pos.key();
- tte = TT.probe(posKey);
- ss->ttMove = ttMove = RootNode ? RootMoves[PVIdx].pv[0] : tte ? tte->move() : MOVE_NONE;
- ttValue = tte ? value_from_tt(tte->value(), ss->ply) : VALUE_NONE;
+ tte = TT.probe(posKey, ttHit);
+ ss->ttMove = ttMove = RootNode ? RootMoves[PVIdx].pv[0] : ttHit ? tte->move() : MOVE_NONE;
+ ttValue = ttHit ? value_from_tt(tte->value(), ss->ply) : VALUE_NONE;
// At non-PV nodes we check for a fail high/low. We don't probe at PV nodes
if ( !PvNode
- && tte
+ && ttHit
&& tte->depth() >= depth
&& ttValue != VALUE_NONE // Only in case of TT access race
&& (ttValue >= beta ? (tte->bound() & BOUND_LOWER)
: v > drawScore ? VALUE_MATE - MAX_PLY - ss->ply
: VALUE_DRAW + 2 * v * drawScore;
- TT.store(posKey, value_to_tt(value, ss->ply), BOUND_EXACT,
- std::min(DEPTH_MAX - ONE_PLY, depth + 6 * ONE_PLY),
- MOVE_NONE, VALUE_NONE);
+ tte->save(posKey, value_to_tt(value, ss->ply), BOUND_EXACT,
+ std::min(DEPTH_MAX - ONE_PLY, depth + 6 * ONE_PLY),
+ MOVE_NONE, VALUE_NONE, TT.get_generation());
return value;
}
goto moves_loop;
}
- else if (tte)
+ else if (ttHit)
{
// Never assume anything on values stored in TT
if ((ss->staticEval = eval = tte->eval_value()) == VALUE_NONE)
eval = ss->staticEval =
(ss-1)->currentMove != MOVE_NULL ? evaluate(pos) : -(ss-1)->staticEval + 2 * Eval::Tempo;
- TT.store(posKey, VALUE_NONE, BOUND_NONE, DEPTH_NONE, MOVE_NONE, ss->staticEval);
+ tte->save(posKey, VALUE_NONE, BOUND_NONE, DEPTH_NONE, MOVE_NONE, ss->staticEval, TT.get_generation());
}
if (ss->skipEarlyPruning)
search<PvNode ? PV : NonPV, false>(pos, ss, alpha, beta, d / 2, true);
ss->skipEarlyPruning = false;
- tte = TT.probe(posKey);
- ttMove = tte ? tte->move() : MOVE_NONE;
+ tte = TT.probe(posKey, ttHit);
+ ttMove = ttHit ? tte->move() : MOVE_NONE;
}
moves_loop: // When in check and at SpNode search starts from here
else if (bestValue >= beta && !pos.capture_or_promotion(bestMove) && !inCheck)
update_stats(pos, ss, bestMove, depth, quietsSearched, quietCount - 1);
- TT.store(posKey, value_to_tt(bestValue, ss->ply),
- bestValue >= beta ? BOUND_LOWER :
- PvNode && bestMove ? BOUND_EXACT : BOUND_UPPER,
- depth, bestMove, ss->staticEval);
+ tte->save(posKey, value_to_tt(bestValue, ss->ply),
+ bestValue >= beta ? BOUND_LOWER :
+ PvNode && bestMove ? BOUND_EXACT : BOUND_UPPER,
+ depth, bestMove, ss->staticEval, TT.get_generation());
assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE);
Move pv[MAX_PLY+1];
StateInfo st;
- const TTEntry* tte;
+ TTEntry* tte;
+ bool ttHit;
Key posKey;
Move ttMove, move, bestMove;
Value bestValue, value, ttValue, futilityValue, futilityBase, oldAlpha;
// Transposition table lookup
posKey = pos.key();
- tte = TT.probe(posKey);
- ttMove = tte ? tte->move() : MOVE_NONE;
- ttValue = tte ? value_from_tt(tte->value(),ss->ply) : VALUE_NONE;
+ tte = TT.probe(posKey, ttHit);
+ ttMove = ttHit ? tte->move() : MOVE_NONE;
+ ttValue = ttHit ? value_from_tt(tte->value(), ss->ply) : VALUE_NONE;
if ( !PvNode
- && tte
+ && ttHit
&& tte->depth() >= ttDepth
&& ttValue != VALUE_NONE // Only in case of TT access race
&& (ttValue >= beta ? (tte->bound() & BOUND_LOWER)
}
else
{
- if (tte)
+ if (ttHit)
{
// Never assume anything on values stored in TT
if ((ss->staticEval = bestValue = tte->eval_value()) == VALUE_NONE)
// Stand pat. Return immediately if static value is at least beta
if (bestValue >= beta)
{
- if (!tte)
- TT.store(pos.key(), value_to_tt(bestValue, ss->ply), BOUND_LOWER,
- DEPTH_NONE, MOVE_NONE, ss->staticEval);
+ if (!ttHit)
+ tte->save(pos.key(), value_to_tt(bestValue, ss->ply), BOUND_LOWER,
+ DEPTH_NONE, MOVE_NONE, ss->staticEval, TT.get_generation());
return bestValue;
}
}
else // Fail high
{
- TT.store(posKey, value_to_tt(value, ss->ply), BOUND_LOWER,
- ttDepth, move, ss->staticEval);
+ tte->save(posKey, value_to_tt(value, ss->ply), BOUND_LOWER,
+ ttDepth, move, ss->staticEval, TT.get_generation());
return value;
}
if (InCheck && bestValue == -VALUE_INFINITE)
return mated_in(ss->ply); // Plies to mate from the root
- TT.store(posKey, value_to_tt(bestValue, ss->ply),
- PvNode && bestValue > oldAlpha ? BOUND_EXACT : BOUND_UPPER,
- ttDepth, bestMove, ss->staticEval);
+ tte->save(posKey, value_to_tt(bestValue, ss->ply),
+ PvNode && bestValue > oldAlpha ? BOUND_EXACT : BOUND_UPPER,
+ ttDepth, bestMove, ss->staticEval, TT.get_generation());
assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE);
void RootMove::insert_pv_in_tt(Position& pos) {
StateInfo state[MAX_PLY], *st = state;
- const TTEntry* tte;
size_t idx = 0;
for ( ; idx < pv.size(); ++idx)
{
- tte = TT.probe(pos.key());
+ bool ttHit;
+ TTEntry* tte = TT.probe(pos.key(), ttHit);
- if (!tte || tte->move() != pv[idx]) // Don't overwrite correct entries
- TT.store(pos.key(), VALUE_NONE, BOUND_NONE, DEPTH_NONE, pv[idx], VALUE_NONE);
+ if (!ttHit || tte->move() != pv[idx]) // Don't overwrite correct entries
+ tte->save(pos.key(), VALUE_NONE, BOUND_NONE, DEPTH_NONE, pv[idx], VALUE_NONE, TT.get_generation());
assert(MoveList<LEGAL>(pos).contains(pv[idx]));
/// TranspositionTable::clear() overwrites the entire transposition table
-/// with zeroes. It is called whenever the table is resized, or when the
+/// 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).
void TranspositionTable::clear() {
/// TranspositionTable::probe() looks up the current position in the
-/// transposition table. Returns a pointer to the TTEntry or NULL if
-/// position is not found.
-
-const TTEntry* TranspositionTable::probe(const Key key) const {
-
- TTEntry* const tte = first_entry(key);
- const uint16_t key16 = key >> 48;
-
- for (unsigned i = 0; i < TTClusterSize; ++i)
- if (tte[i].key16 == key16)
- {
- tte[i].genBound8 = uint8_t(generation | tte[i].bound()); // Refresh
- return &tte[i];
- }
-
- return NULL;
-}
-
-
-/// TranspositionTable::store() writes a new entry containing position key and
-/// valuable information of current position. The lowest order bits of position
-/// key are used to decide in which cluster the position will be placed.
-/// When a new entry is written and there are no empty entries available in the
-/// cluster, it replaces the least valuable of the entries. A TTEntry t1 is considered
+/// 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. 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 Key key, Value v, Bound b, Depth d, Move m, Value statV) {
+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
+ const uint16_t key16 = key >> 48; // Use the high 16 bits as key inside the cluster
for (unsigned i = 0; i < TTClusterSize; ++i)
- if (!tte[i].key16 || tte[i].key16 == key16) // Empty or overwrite old
+ if (!tte[i].key16 || tte[i].key16 == key16)
{
- // Save preserving any existing ttMove
- tte[i].save(key16, v, b, d, m ? m : tte[i].move(), generation, statV);
- return;
+ if (tte[i].key16)
+ tte[i].genBound8 = uint8_t(generation | tte[i].bound()); // Refresh
+
+ found = (bool)tte[i].key16;
+ return &tte[i];
}
- // Implement replace strategy
+ // Find an entry to be replaced according to the replacement strategy
TTEntry* replace = tte;
for (unsigned i = 1; i < TTClusterSize; ++i)
if ( (( tte[i].genBound8 & 0xFC) == generation || tte[i].bound() == BOUND_EXACT)
- (tte[i].depth8 < replace->depth8) < 0)
replace = &tte[i];
- replace->save(key16, v, b, d, m, generation, statV);
+ found = false;
+ return replace;
}
Depth depth() const { return (Depth)depth8; }
Bound bound() const { return (Bound)(genBound8 & 0x3); }
+ void save(Key k, Value v, Bound b, Depth d, Move m, Value ev, uint8_t g) {
+
+ k >>= 48;
+ if (m || k != key16) // preserve any existing ttMove
+ move16 = (uint16_t)m;
+ key16 = (uint16_t)k;
+ value16 = (int16_t)v;
+ evalValue = (int16_t)ev;
+ genBound8 = (uint8_t)(g | b);
+ depth8 = (int8_t)d;
+ }
+
private:
friend class TranspositionTable;
- void save(uint16_t k, Value v, Bound b, Depth d, Move m, uint8_t g, Value ev) {
-
- key16 = (uint16_t)k;
- move16 = (uint16_t)m;
- value16 = (int16_t)v;
- evalValue = (int16_t)ev;
- genBound8 = (uint8_t)(g | b);
- depth8 = (int8_t)d;
- }
-
uint16_t key16;
uint16_t move16;
int16_t value16;
/// 3 x TTEntry (3 x 10 bytes)
/// padding (2 bytes)
-const unsigned TTClusterSize = 3;
+static const unsigned TTClusterSize = 3;
struct TTCluster {
TTEntry entry[TTClusterSize];
public:
~TranspositionTable() { free(mem); }
void new_search() { generation += 4; } // Lower 2 bits are used by Bound
-
- const TTEntry* probe(const Key key) const;
+ uint8_t get_generation() const { return generation; }
+ TTEntry* probe(const Key key, bool& found) const;
TTEntry* first_entry(const Key key) const;
void resize(size_t mbSize);
void clear();
- void store(const Key key, Value v, Bound type, Depth d, Move m, Value statV);
private:
size_t clusterCount;