From 2f2e48fad23225d23f87b95fb842156cfee668fb Mon Sep 17 00:00:00 2001 From: Marco Costalba Date: Mon, 27 Apr 2009 13:21:49 +0100 Subject: [PATCH] Code style cleanup in transposition table code Assorted fixes but no functional change. Signed-off-by: Marco Costalba --- src/search.cpp | 18 +++---- src/tt.cpp | 132 +++++++++++++++++++++---------------------------- src/tt.h | 31 +++++------- 3 files changed, 77 insertions(+), 104 deletions(-) diff --git a/src/search.cpp b/src/search.cpp index 21a13033..a8aa1bb6 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -315,7 +315,7 @@ namespace { //// // The main transposition table -TranspositionTable TT = TranspositionTable(TTDefaultSize); +TranspositionTable TT; // Number of active threads: @@ -1191,7 +1191,7 @@ namespace { return bestValue; if (bestValue <= oldAlpha) - TT.store(pos, value_to_tt(bestValue, ply), depth, MOVE_NONE, VALUE_TYPE_UPPER); + TT.store(pos, value_to_tt(bestValue, ply), VALUE_TYPE_UPPER, depth, MOVE_NONE); else if (bestValue >= beta) { @@ -1202,10 +1202,10 @@ namespace { update_history(pos, m, depth, movesSearched, moveCount); update_killers(m, ss[ply]); } - TT.store(pos, value_to_tt(bestValue, ply), depth, m, VALUE_TYPE_LOWER); + TT.store(pos, value_to_tt(bestValue, ply), VALUE_TYPE_LOWER, depth, m); } else - TT.store(pos, value_to_tt(bestValue, ply), depth, ss[ply].pv[ply], VALUE_TYPE_EXACT); + TT.store(pos, value_to_tt(bestValue, ply), VALUE_TYPE_EXACT, depth, ss[ply].pv[ply]); return bestValue; } @@ -1455,7 +1455,7 @@ namespace { return bestValue; if (bestValue < beta) - TT.store(pos, value_to_tt(bestValue, ply), depth, MOVE_NONE, VALUE_TYPE_UPPER); + TT.store(pos, value_to_tt(bestValue, ply), VALUE_TYPE_UPPER, depth, MOVE_NONE); else { BetaCounter.add(pos.side_to_move(), depth, threadID); @@ -1465,7 +1465,7 @@ namespace { update_history(pos, m, depth, movesSearched, moveCount); update_killers(m, ss[ply]); } - TT.store(pos, value_to_tt(bestValue, ply), depth, m, VALUE_TYPE_LOWER); + TT.store(pos, value_to_tt(bestValue, ply), VALUE_TYPE_LOWER, depth, m); } assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE); @@ -1544,7 +1544,7 @@ namespace { { // Store the score to avoid a future costly evaluation() call if (!isCheck && !tte && ei.futilityMargin == 0) - TT.store(pos, value_to_tt(bestValue, ply), Depth(-127*OnePly), MOVE_NONE, VALUE_TYPE_EVAL); + TT.store(pos, value_to_tt(bestValue, ply), VALUE_TYPE_EVAL, Depth(-127*OnePly), MOVE_NONE); return bestValue; } @@ -1637,9 +1637,9 @@ namespace { { Depth d = (depth == Depth(0) ? Depth(0) : Depth(-1)); if (bestValue < beta) - TT.store(pos, value_to_tt(bestValue, ply), d, MOVE_NONE, VALUE_TYPE_UPPER); + TT.store(pos, value_to_tt(bestValue, ply), VALUE_TYPE_UPPER, d, MOVE_NONE); else - TT.store(pos, value_to_tt(bestValue, ply), d, m, VALUE_TYPE_LOWER); + TT.store(pos, value_to_tt(bestValue, ply), VALUE_TYPE_LOWER, d, m); } // Update killers only for good check moves diff --git a/src/tt.cpp b/src/tt.cpp index 4cc19c59..fe222106 100644 --- a/src/tt.cpp +++ b/src/tt.cpp @@ -33,20 +33,13 @@ //// Functions //// -/// Constructor +TranspositionTable::TranspositionTable() { -TranspositionTable::TranspositionTable(unsigned mbSize) { - - size = 0; - generation = 0; - writes = 0; + size = writes = 0; entries = 0; - set_size(mbSize); + generation = 0; } - -/// Destructor - TranspositionTable::~TranspositionTable() { delete [] entries; @@ -64,27 +57,27 @@ void TranspositionTable::set_size(unsigned mbSize) { // We store a cluster of 4 TTEntry for each position and newSize is // the maximum number of storable positions - for ( ; newSize * 4 * (sizeof(TTEntry)) <= (mbSize << 20); newSize *= 2); - newSize /= 2; + while ((2 * newSize) * 4 * (sizeof(TTEntry)) <= (mbSize << 20)) + newSize *= 2; + if (newSize != size) { - size = newSize; - delete [] entries; - entries = new TTEntry[size * 4]; - if (!entries) - { - std::cerr << "Failed to allocate " << mbSize - << " MB for transposition table." - << std::endl; - exit(EXIT_FAILURE); - } - clear(); + size = newSize; + delete [] entries; + entries = new TTEntry[size * 4]; + if (!entries) + { + std::cerr << "Failed to allocate " << mbSize + << " MB for transposition table." << std::endl; + exit(EXIT_FAILURE); + } + clear(); } } /// TranspositionTable::clear overwrites the entire transposition table -/// with zeroes. It is called whenever the table is resized, or when the +/// with zeroes. It is called whenever the table is resized, or when the /// user asks the program to clear the table (from the UCI interface). /// Perhaps we should also clear it when the "ucinewgame" command is recieved? @@ -96,45 +89,44 @@ void TranspositionTable::clear() { /// TranspositionTable::store writes a new entry containing a position, /// a value, a value type, a search depth, and a best move to the -/// transposition table. The transposition table is organized in clusters -/// of four TTEntry objects, and when a new entry is written, it replaces -/// the least valuable of the four entries in a cluster. A TTEntry t1 is +/// transposition table. Transposition table is organized in clusters of +/// four TTEntry objects, and when a new entry is written, it replaces +/// the least valuable of the four entries in a cluster. 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. A TTEntry of type VALUE_TYPE_EVAL /// never replaces another entry for the same position. -void TranspositionTable::store(const Position &pos, Value v, Depth d, - Move m, ValueType type) { +void TranspositionTable::store(const Position& p, Value v, ValueType t, Depth d, Move m) { + TTEntry *tte, *replace; - tte = replace = first_entry(pos); + tte = replace = first_entry(p); for (int i = 0; i < 4; i++, tte++) { - if (!tte->key() || tte->key() == pos.get_key()) // empty or overwrite old - { - // Do not overwrite position entry when VALUE_TYPE_EVAL - if ( tte->key() - && type == VALUE_TYPE_EVAL) - return; - - if (m == MOVE_NONE) - m = tte->move(); - - *tte = TTEntry(pos.get_key(), v, type, d, m, generation); - return; - } - else if (i == 0) // replace would be a no-op in this common case - continue; - - int c1 = (replace->generation() == generation ? 2 : 0); - int c2 = (tte->generation() == generation ? -2 : 0); - int c3 = (tte->depth() < replace->depth() ? 1 : 0); - - if (c1 + c2 + c3 > 0) - replace = tte; + if (!tte->key() || tte->key() == p.get_key()) // empty or overwrite old + { + // Do not overwrite when new type is VALUE_TYPE_EVAL + if (tte->key() && t == VALUE_TYPE_EVAL) + return; + + if (m == MOVE_NONE) + m = tte->move(); + + *tte = TTEntry(p.get_key(), v, t, d, m, generation); + return; + } + else if (i == 0) // replace would be a no-op in this common case + continue; + + int c1 = (replace->generation() == generation ? 2 : 0); + int c2 = (tte->generation() == generation ? -2 : 0); + int c3 = (tte->depth() < replace->depth() ? 1 : 0); + + if (c1 + c2 + c3 > 0) + replace = tte; } - *replace = TTEntry(pos.get_key(), v, type, d, m, generation); + *replace = TTEntry(p.get_key(), v, t, d, m, generation); writes++; } @@ -143,15 +135,14 @@ void TranspositionTable::store(const Position &pos, Value v, Depth d, /// transposition table. Returns a pointer to the TTEntry or NULL /// if position is not found. -TTEntry* TranspositionTable::retrieve(const Position &pos) const { +TTEntry* TranspositionTable::retrieve(const Position& pos) const { TTEntry *tte = first_entry(pos); for (int i = 0; i < 4; i++, tte++) - { if (tte->key() == pos.get_key()) return tte; - } + return NULL; } @@ -159,13 +150,13 @@ TTEntry* TranspositionTable::retrieve(const Position &pos) const { /// TranspositionTable::first_entry returns a pointer to the first /// entry of a cluster given a position. -inline TTEntry* TranspositionTable::first_entry(const Position &pos) const { +inline TTEntry* TranspositionTable::first_entry(const Position& pos) const { return entries + (int(pos.get_key() & (size - 1)) << 2); } /// TranspositionTable::new_search() is called at the beginning of every new -/// search. It increments the "generation" variable, which is used to +/// search. It increments the "generation" variable, which is used to /// distinguish transposition table entries from previous searches from /// entries from the current search. @@ -177,19 +168,19 @@ void TranspositionTable::new_search() { /// TranspositionTable::insert_pv() is called at the end of a search -/// iteration, and inserts the PV back into the PV. This makes sure the -/// old PV moves are searched first, even if the old TT entries have been -/// overwritten. +/// iteration, and inserts the PV back into the PV. This makes sure +/// the old PV moves are searched first, even if the old TT entries +/// have been overwritten. -void TranspositionTable::insert_pv(const Position &pos, Move pv[]) { +void TranspositionTable::insert_pv(const Position& pos, Move pv[]) { StateInfo st; Position p(pos); for (int i = 0; pv[i] != MOVE_NONE; i++) { - store(p, VALUE_NONE, Depth(-127*OnePly), pv[i], VALUE_TYPE_NONE); - p.do_move(pv[i], st); + store(p, VALUE_NONE, VALUE_TYPE_NONE, Depth(-127*OnePly), pv[i]); + p.do_move(pv[i], st); } } @@ -198,19 +189,8 @@ void TranspositionTable::insert_pv(const Position &pos, Move pv[]) { /// entries which have received at least one write during the current search. /// It is used to display the "info hashfull ..." information in UCI. -int TranspositionTable::full() { +int TranspositionTable::full() const { double N = double(size) * 4.0; return int(1000 * (1 - exp(writes * log(1.0 - 1.0/N)))); } - - -/// Constructors - -TTEntry::TTEntry() { -} - -TTEntry::TTEntry(Key k, Value v, ValueType t, Depth d, Move m, - int generation) : - key_ (k), data((m & 0x1FFFF) | (t << 20) | (generation << 23)), - value_(int16_t(v)), depth_(int16_t(d)) {} diff --git a/src/tt.h b/src/tt.h index 76ecad81..0918e3e8 100644 --- a/src/tt.h +++ b/src/tt.h @@ -53,8 +53,11 @@ class TTEntry { public: - TTEntry(); - TTEntry(Key k, Value v, ValueType t, Depth d, Move m, int generation); + TTEntry() {} + TTEntry(Key k, Value v, ValueType t, Depth d, Move m, int generation) + : key_ (k), data((m & 0x1FFFF) | (t << 20) | (generation << 23)), + value_(int16_t(v)), depth_(int16_t(d)) {} + Key key() const { return key_; } Depth depth() const { return Depth(depth_); } Move move() const { return Move(data & 0x1FFFF); } @@ -76,32 +79,22 @@ private: class TranspositionTable { public: - TranspositionTable(unsigned mbSize); + TranspositionTable(); ~TranspositionTable(); void set_size(unsigned mbSize); void clear(); - void store(const Position &pos, Value v, Depth d, Move m, ValueType type); - TTEntry* retrieve(const Position &pos) const; + void store(const Position& pos, Value v, ValueType type, Depth d, Move m); + TTEntry* retrieve(const Position& pos) const; void new_search(); - void insert_pv(const Position &pos, Move pv[]); - int full(); + void insert_pv(const Position& pos, Move pv[]); + int full() const; private: - inline TTEntry* first_entry(const Position &pos) const; + inline TTEntry* first_entry(const Position& pos) const; - unsigned size; - int writes; + unsigned size, writes; TTEntry* entries; uint8_t generation; }; - -//// -//// Constants and variables -//// - -// Default transposition table size, in megabytes: -const int TTDefaultSize = 32; - - #endif // !defined(TT_H_INCLUDED) -- 2.39.2