From: mstembera Date: Sat, 13 Dec 2014 07:16:35 +0000 (+0000) Subject: Avoid searching TT twice for the same key/position during probe() and store(). X-Git-Url: https://git.sesse.net/?p=stockfish;a=commitdiff_plain;h=14cf27e6f65787a1f9c8e4759ae0fcc218f37d2d Avoid searching TT twice for the same key/position during probe() and store(). Just keep the pointer and remove code from tt.cpp STC LLR: 2.96 (-2.94,2.94) [-1.50,4.50] Total: 13620 W: 2810 L: 2665 D: 8145 LTC LLR: 2.97 (-2.94,2.94) [0.00,6.00] Total: 13021 W: 2238 L: 2073 D: 8710STC http://tests.stockfishchess.org/tests/view/548436860ebc59331739b90c STC 4MB ELO: 2.41 +-2.2 (95%) LOS: 98.6% Total: 40000 W: 8175 L: 7897 D: 23928 LTC 16MB ELO: 1.78 +-2.0 (95%) LOS: 96.1% Total: 39683 W: 6763 L: 6560 D: 26360 Resolves #151 Bench: 8116521 --- diff --git a/src/search.cpp b/src/search.cpp index 135f7808..c774f08a 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -457,7 +457,8 @@ namespace { 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; @@ -477,6 +478,7 @@ namespace { bestMove = splitPoint->bestMove; bestValue = splitPoint->bestValue; tte = NULL; + ttHit = false; ttMove = excludedMove = MOVE_NONE; ttValue = VALUE_NONE; @@ -522,13 +524,13 @@ namespace { // 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) @@ -564,9 +566,9 @@ namespace { : 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; } @@ -580,7 +582,7 @@ namespace { 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) @@ -596,7 +598,7 @@ namespace { 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) @@ -718,8 +720,8 @@ namespace { search(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 @@ -1079,10 +1081,10 @@ 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); @@ -1107,7 +1109,8 @@ moves_loop: // When in check and at SpNode search starts from here 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; @@ -1138,12 +1141,12 @@ moves_loop: // When in check and at SpNode search starts from here // 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) @@ -1161,7 +1164,7 @@ moves_loop: // When in check and at SpNode search starts from here } else { - if (tte) + if (ttHit) { // Never assume anything on values stored in TT if ((ss->staticEval = bestValue = tte->eval_value()) == VALUE_NONE) @@ -1179,9 +1182,9 @@ moves_loop: // When in check and at SpNode search starts from here // 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; } @@ -1279,8 +1282,8 @@ moves_loop: // When in check and at SpNode search starts from here } 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; } @@ -1293,9 +1296,9 @@ moves_loop: // When in check and at SpNode search starts from here 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); @@ -1469,15 +1472,15 @@ moves_loop: // When in check and at SpNode search starts from here 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(pos).contains(pv[idx])); diff --git a/src/tt.cpp b/src/tt.cpp index 117b6002..2979c104 100644 --- a/src/tt.cpp +++ b/src/tt.cpp @@ -54,7 +54,7 @@ void TranspositionTable::resize(size_t mbSize) { /// 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() { @@ -64,47 +64,28 @@ 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) @@ -112,5 +93,6 @@ void TranspositionTable::store(const Key key, Value v, Bound b, Depth d, Move m, - (tte[i].depth8 < replace->depth8) < 0) replace = &tte[i]; - replace->save(key16, v, b, d, m, generation, statV); + found = false; + return replace; } diff --git a/src/tt.h b/src/tt.h index 534409f3..0c324c73 100644 --- a/src/tt.h +++ b/src/tt.h @@ -41,19 +41,21 @@ struct TTEntry { 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; @@ -67,7 +69,7 @@ private: /// 3 x TTEntry (3 x 10 bytes) /// padding (2 bytes) -const unsigned TTClusterSize = 3; +static const unsigned TTClusterSize = 3; struct TTCluster { TTEntry entry[TTClusterSize]; @@ -85,12 +87,11 @@ class TranspositionTable { 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;