Another tweak. Test was unsuccessfull, bayeselo says original stockfish is better with LOS=87:12.
But it was a lot of work, and I would say there are few bugs left hurting performance, so I am going to post the patch anayway, so you can tell me why is it not working better.
Idea is simple, make transposition table store both lower bound and upper bound with their respective depths. I had to squeeze all that into TTEntry and modify search to use new interface the right way. Implementation is of course a mess. Affected files: value.h, tt.h, tt.cpp and search.cpp
I have polished few thing when the test was running, but here is the tested patch:
Code: Select all
diff -dur src-Ch/search.cpp src-BbCh/search.cpp
--- src-Ch/search.cpp 2010-07-09 13:04:18.000000000 +0200
+++ src-BbCh/search.cpp 2010-07-20 22:24:14.000000000 +0200
@@ -1113,10 +1113,13 @@
if (!PvNode && tte && ok_to_use_TT(tte, depth, beta, ply))
{
// Refresh tte entry to avoid aging
- TT.store(posKey, tte->value(), tte->type(), tte->depth(), ttMove, tte->static_value(), tte->king_danger());
+ TT.refresh(*const_cast<TTEntry*>(tte));
ss->currentMove = ttMove; // Can be MOVE_NONE
- return value_from_tt(tte->value(), ply);
+ if (is_lower_bound(tte->type()) && value_from_tt(tte->lowerbound(), ply) >= beta)
+ return value_from_tt(tte->lowerbound(), ply);
+ else
+ return value_from_tt(tte->upperbound(), ply);
}
// Step 5. Evaluate the position statically
@@ -1148,7 +1151,7 @@
{
// Pass ss->eval to qsearch() and avoid an evaluate call
if (!tte || tte->static_value() == VALUE_NONE)
- TT.store(posKey, ss->eval, VALUE_TYPE_EXACT, Depth(-127*OnePly), MOVE_NONE, ss->eval, ei.kingDanger[pos.side_to_move()]);
+ TT.store(posKey, MOVE_NONE, VALUE_TYPE_BOTH, Depth(-128), Depth(-128), -VALUE_INFINITE, VALUE_INFINITE, ss->eval, ei.kingDanger[pos.side_to_move()]);
Value rbeta = beta - razor_margin(depth);
Value v = qsearch<NonPV>(pos, ss, rbeta-1, rbeta, Depth(0), ply);
@@ -1262,7 +1265,7 @@
&& tte && tte->move()
&& !excludedMove // Do not allow recursive singular extension search
&& is_lower_bound(tte->type())
- && tte->depth() >= depth - 3 * OnePly;
+ && tte->lowerdepth() >= depth - 3 * OnePly;
// Step 10. Loop through moves
// Loop through all legal moves until no moves remain or a beta cutoff occurs
@@ -1288,7 +1291,7 @@
&& move == tte->move()
&& ext < OnePly)
{
- Value ttValue = value_from_tt(tte->value(), ply);
+ Value ttValue = value_from_tt(tte->lowerbound(), ply);
if (abs(ttValue) < VALUE_KNOWN_WIN)
{
@@ -1442,9 +1445,16 @@
if (AbortSearch || TM.thread_should_stop(threadID))
return bestValue;
- ValueType f = (bestValue <= oldAlpha ? VALUE_TYPE_UPPER : bestValue >= beta ? VALUE_TYPE_LOWER : VALUE_TYPE_EXACT);
- move = (bestValue <= oldAlpha ? MOVE_NONE : ss->bestMove);
- TT.store(posKey, value_to_tt(bestValue, ply), f, depth, move, ss->eval, ei.kingDanger[pos.side_to_move()]);
+ if (bestValue <= oldAlpha)
+ TT.store(posKey, MOVE_NONE, VALUE_TYPE_UPPER, Depth(-128), depth, -VALUE_INFINITE,
+ value_to_tt(bestValue, ply), ss->eval, ei.kingDanger[pos.side_to_move()]);
+ else if (bestValue >= beta)
+ TT.store(posKey, ss->bestMove, VALUE_TYPE_LOWER, depth, Depth(-128), value_to_tt(bestValue, ply),
+ VALUE_INFINITE, ss->eval, ei.kingDanger[pos.side_to_move()]);
+ else
+ TT.store(posKey, ss->bestMove, VALUE_TYPE_EXACT, depth, depth, value_to_tt(bestValue, ply),
+ value_to_tt(bestValue, ply), ss->eval, ei.kingDanger[pos.side_to_move()]);
+ move = ss->bestMove;
// Update killers and history only for non capture moves that fails high
if (bestValue >= beta)
@@ -1501,7 +1511,10 @@
if (!PvNode && tte && ok_to_use_TT(tte, depth, beta, ply))
{
ss->currentMove = ttMove; // Can be MOVE_NONE
- return value_from_tt(tte->value(), ply);
+ if (is_lower_bound(tte->type()) && value_from_tt(tte->lowerbound(), ply) >= beta)
+ return value_from_tt(tte->lowerbound(), ply);
+ else
+ return value_from_tt(tte->upperbound(), ply);
}
isCheck = pos.is_check();
@@ -1529,7 +1542,8 @@
if (bestValue >= beta)
{
if (!tte)
- TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_LOWER, Depth(-127*OnePly), MOVE_NONE, ss->eval, ei.kingDanger[pos.side_to_move()]);
+ TT.store(pos.get_key(), MOVE_NONE, VALUE_TYPE_LOWER, Depth(-2), Depth(-128),
+ value_to_tt(bestValue, ply), VALUE_INFINITE, ss->eval, ei.kingDanger[pos.side_to_move()]);
return bestValue;
}
@@ -1625,8 +1639,15 @@
// Update transposition table
Depth d = (depth == Depth(0) ? Depth(0) : Depth(-1));
- ValueType f = (bestValue <= oldAlpha ? VALUE_TYPE_UPPER : bestValue >= beta ? VALUE_TYPE_LOWER : VALUE_TYPE_EXACT);
- TT.store(pos.get_key(), value_to_tt(bestValue, ply), f, d, ss->bestMove, ss->eval, ei.kingDanger[pos.side_to_move()]);
+ if (bestValue <= oldAlpha)
+ TT.store(pos.get_key(), ss->bestMove, VALUE_TYPE_UPPER, Depth(-128), d, -VALUE_INFINITE,
+ value_to_tt(bestValue, ply), ss->eval, ei.kingDanger[pos.side_to_move()]);
+ else if (bestValue >= beta)
+ TT.store(pos.get_key(), ss->bestMove, VALUE_TYPE_LOWER, d, Depth(-128), value_to_tt(bestValue, ply),
+ VALUE_INFINITE, ss->eval, ei.kingDanger[pos.side_to_move()]);
+ else
+ TT.store(pos.get_key(), ss->bestMove, VALUE_TYPE_EXACT, d, d, value_to_tt(bestValue, ply),
+ value_to_tt(bestValue, ply), ss->eval, ei.kingDanger[pos.side_to_move()]);
// Update killers only for checking moves that fails high
if ( bestValue >= beta
@@ -2001,14 +2022,17 @@
bool ok_to_use_TT(const TTEntry* tte, Depth depth, Value beta, int ply) {
- Value v = value_from_tt(tte->value(), ply);
-
- return ( tte->depth() >= depth
- || v >= Max(value_mate_in(PLY_MAX), beta)
- || v < Min(value_mated_in(PLY_MAX), beta))
+ Value lb = value_from_tt(tte->lowerbound(), ply);
+ Value ub = value_from_tt(tte->upperbound(), ply);
- && ( (is_lower_bound(tte->type()) && v >= beta)
- || (is_upper_bound(tte->type()) && v < beta));
+ return ( is_lower_bound(tte->type())
+ && ( depth <= tte->lowerdepth()
+ || lb >= value_mate_in(PLY_MAX))
+ && lb >= beta)
+ || ( is_upper_bound(tte->type())
+ && ( depth <= tte->upperdepth()
+ || ub < value_mated_in(PLY_MAX))
+ && ub < beta);
}
@@ -2020,11 +2044,13 @@
if (!tte)
return defaultEval;
- Value v = value_from_tt(tte->value(), ply);
+ Value lb = value_from_tt(tte->lowerbound(), ply);
+ Value ub = value_from_tt(tte->upperbound(), ply);
- if ( (is_lower_bound(tte->type()) && v >= defaultEval)
- || (is_upper_bound(tte->type()) && v < defaultEval))
- return v;
+ if (is_lower_bound(tte->type()) && lb >= defaultEval)
+ return lb;
+ if (is_upper_bound(tte->type()) && ub < defaultEval)
+ return ub;
return defaultEval;
}
diff -dur src-Ch/tt.cpp src-BbCh/tt.cpp
--- src-Ch/tt.cpp 2010-07-09 13:04:18.000000000 +0200
+++ src-BbCh/tt.cpp 2010-07-20 22:24:14.000000000 +0200
@@ -98,22 +98,51 @@
/// 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 Key posKey, Value v, ValueType t, Depth d, Move m, Value statV, Value kingD) {
+/// Now TTEntry stores both upper bound and lower bound with respective depths
+/// and store return Depth != -128 when it detects conflict with stored bound.
+/// The returned depth would be a hint for search to resolve conflict.
- int c1, c2, c3;
+void TranspositionTable::store(const Key posKey, Move m, ValueType t, Depth ld, Depth ud, Value lb, Value ub, Value sv, Value kd) {
+
+ int c1, c2, c3, c4;
TTEntry *tte, *replace;
uint32_t posKey32 = posKey >> 32; // Use the high 32 bits as key
+ assert(t != VALUE_TYPE_NONE);
+ assert(t != VALUE_TYPE_EXACT || (m != MOVE_NONE));
+ assert(lb <= ub);
tte = replace = first_entry(posKey);
for (int i = 0; i < ClusterSize; i++, tte++)
{
if (!tte->key() || tte->key() == posKey32) // empty or overwrite old
{
- // Preserve any exsisting ttMove
+ // Preserve any existing ttMove, StatV or kingD.
if (m == MOVE_NONE)
m = tte->move();
+ if (sv == VALUE_NONE)
+ sv = tte->static_value();
+ if (kd == VALUE_NONE)
+ kd = tte->king_danger();
- tte->save(posKey32, v, t, d, m, generation, statV, kingD);
+ // Also, preserve compatible bounds.
+ if ( lb == -VALUE_INFINITE
+ && is_lower_bound(tte->type())
+ && ub >= tte->lowerbound())
+ {
+ ld = tte->lowerdepth();
+ lb = tte->lowerbound();
+ t = (t == VALUE_TYPE_EXACT) ? VALUE_TYPE_EXACT : VALUE_TYPE_BOTH;
+ }
+ if ( ub == VALUE_INFINITE
+ && is_upper_bound(tte->type())
+ && lb <= tte->upperbound())
+ {
+ ud = tte->upperdepth();
+ ub = tte->upperbound();
+ t = (t == VALUE_TYPE_EXACT) ? VALUE_TYPE_EXACT : VALUE_TYPE_BOTH;
+ }
+
+ tte->save(posKey32, m, t, generation, ld, ud, lb, ub, sv, kd);
return;
}
@@ -122,12 +151,14 @@
c1 = (replace->generation() == generation ? 2 : 0);
c2 = (tte->generation() == generation ? -2 : 0);
- c3 = (tte->depth() < replace->depth() ? 1 : 0);
+ c3 = (Max(tte->lowerdepth(), tte->upperdepth()) < Max(replace->lowerdepth(), replace->upperdepth()) ? 1 : 0);
+ c4 = (Max(tte->lowerdepth(), tte->upperdepth()) == Max(replace->lowerdepth(), replace->upperdepth())
+ ? (Min(tte->lowerdepth(), tte->upperdepth()) < Min(replace->lowerdepth(), replace->upperdepth()) ? 1 : 0) : 0);
- if (c1 + c2 + c3 > 0)
+ if (c1 + c2 + c3 + c4 > 0)
replace = tte;
}
- replace->save(posKey32, v, t, d, m, generation, statV, kingD);
+ replace->save(posKey32, m, t, generation, ld, ud, lb, ub, sv, kd);
overwrites++;
}
@@ -156,7 +187,7 @@
void TranspositionTable::new_search() {
- generation++;
+ generation = (generation + 1) & 0x0F;
overwrites = 0;
}
@@ -175,7 +206,7 @@
{
TTEntry *tte = retrieve(p.get_key());
if (!tte || tte->move() != pv[i])
- store(p.get_key(), VALUE_NONE, VALUE_TYPE_NONE, Depth(-127*OnePly), pv[i], VALUE_NONE, VALUE_NONE);
+ store(p.get_key(), pv[i], VALUE_TYPE_EXACT, Depth(-128), Depth(-128), -VALUE_INFINITE, VALUE_INFINITE, VALUE_NONE, VALUE_NONE);
p.do_move(pv[i], st);
}
}
@@ -203,7 +234,6 @@
// get a ponder move, that's the reason of ply < 2 conditions.
while ( (tte = retrieve(p.get_key())) != NULL
&& tte->move() != MOVE_NONE
- && (tte->type() == VALUE_TYPE_EXACT || ply < 2)
&& move_is_legal(p, tte->move())
&& (!p.is_draw() || ply < 2)
&& ply < PLY_MAX)
diff -dur src-Ch/tt.h src-BbCh/tt.h
--- src-Ch/tt.h 2010-07-09 13:03:34.000000000 +0200
+++ src-BbCh/tt.h 2010-07-20 22:24:14.000000000 +0200
@@ -36,49 +36,65 @@
/// The TTEntry class is the class of transposition table entries
///
-/// A TTEntry needs 96 bits to be stored
-///
-/// bit 0-31: key
-/// bit 32-63: data
-/// bit 64-79: value
-/// bit 80-95: depth
+/// A TTEntry needs 128 bits to be stored
///
-/// the 32 bits of the data field are so defined
+/// bit 0- 31: key
+/// bit 32- 48: move
+/// bit 49- 51: value type
+/// bit 52- 55: generation
+/// bit 56- 63: depth of lowerbound (signed)
+/// bit 64- 71: depth of uperbound (signed)
+/// bit 72- 85: lowerbound (signed, shifted)
+/// bit 86- 99: upperbound (signed, shifted)
+/// bit 100-113: static value (signed, shifted)
+/// bit 114-127: king danger (signed, shifted)
///
-/// bit 0-16: move
-/// bit 17-19: not used
-/// bit 20-22: value type
-/// bit 23-31: generation
+/// works correctly for GrainSize >= 4
class TTEntry {
public:
- void save(uint32_t k, Value v, ValueType t, Depth d, Move m, int g, Value statV, Value kd) {
+ void save(uint32_t k, Move m, ValueType t, uint8_t g, Depth ld, Depth ud, Value lb, Value ub, Value sv, Value kd) {
key32 = k;
- data = (m & 0x1FFFF) | (t << 20) | (g << 23);
- value16 = int16_t(v);
- depth16 = int16_t(d);
- staticValue = int16_t(statV);
- kingDanger = int16_t(kd);
+ move16 = uint32_t(m) >> 1;
+ mtg8 = ((uint16_t(m) & 1) << 7) | (uint16_t(t) << 4) | g;
+ lowerdepth8 = ld;
+ upperdepth8 = ud;
+ data1_8 = uint16_t(int(lb) + 0x8000) >> 8;
+ data2_8 = (uint16_t(int(lb) + 0x8000) & 0x00FC) | (uint16_t(int(ub) + 0x8000) >> 14);
+ data3_8 = (uint16_t(int(ub) + 0x8000) & 0x3FC0) >> 6;
+ data4_8 = ((uint16_t(int(ub) + 0x8000) & 0x003C) << 2) | (uint16_t(int(sv) + 0x8000) >> 12);
+ data5_8 = (uint16_t(int(sv) + 0x8000) & 0x0FF0) >> 4;
+ data6_8 = ((uint16_t(int(sv) + 0x8000) & 0x000C) << 4) | (uint16_t(int(kd) + 0x8000) >> 10);
+ data7_8 = (uint16_t(int(kd) + 0x8000) & 0x03FC) >> 2;
}
+ void set_generation(uint8_t g) { mtg8 = (mtg8 & 0xF0) | g; }
uint32_t key() const { return key32; }
- Depth depth() const { return Depth(depth16); }
- Move move() const { return Move(data & 0x1FFFF); }
- Value value() const { return Value(value16); }
- ValueType type() const { return ValueType((data >> 20) & 7); }
- int generation() const { return data >> 23; }
- Value static_value() const { return Value(staticValue); }
- Value king_danger() const { return Value(kingDanger); }
+ Move move() const { return Move((uint32_t(move16) << 1) | (mtg8 >> 7)) ; }
+ ValueType type() const { return ValueType((mtg8 & 0x70) >> 4); }
+ uint8_t generation() const { return mtg8 & 0x0F; }
+ Depth lowerdepth() const { return Depth(lowerdepth8); }
+ Depth upperdepth() const { return Depth(upperdepth8); }
+ Value lowerbound() const { return Value((int(uint32_t(data1_8) << 8) | (data2_8 & 0xFC)) - 0x8000); }
+ Value upperbound() const { return Value((int(uint32_t(data2_8 & 0x03) << 14) | (uint16_t(data3_8) << 6) | ((data4_8 & 0xF0) >> 2)) - 0x8000); }
+ Value static_value() const { return Value((int(uint32_t(data4_8 & 0x0F) << 12) | (uint16_t(data5_8) << 4) | ((data6_8 & 0xC0) >> 4)) - 0x8000); }
+ Value king_danger() const { return Value((int(uint32_t(data6_8 & 0x3F) << 10) | (uint16_t(data7_8) << 2)) - 0x8000); }
private:
uint32_t key32;
- uint32_t data;
- int16_t value16;
- int16_t depth16;
- int16_t staticValue;
- int16_t kingDanger;
+ uint16_t move16;
+ uint8_t mtg8; // Move, value Type and Generation
+ int8_t lowerdepth8;
+ int8_t upperdepth8;
+ uint8_t data1_8;
+ uint8_t data2_8;
+ uint8_t data3_8;
+ uint8_t data4_8;
+ uint8_t data5_8;
+ uint8_t data6_8;
+ uint8_t data7_8;
};
@@ -106,7 +122,8 @@
~TranspositionTable();
void set_size(size_t mbSize);
void clear();
- void store(const Key posKey, Value v, ValueType type, Depth d, Move m, Value statV, Value kingD);
+ void store(const Key posKey, Move m, ValueType t, Depth ld, Depth ud, Value lb, Value ub, Value sv, Value kd);
+ void refresh(TTEntry& e) {e.set_generation(generation); }
TTEntry* retrieve(const Key posKey) const;
void new_search();
void insert_pv(const Position& pos, Move pv[]);
diff -dur src-Ch/value.h src-BbCh/value.h
--- src-Ch/value.h 2010-07-09 13:03:34.000000000 +0200
+++ src-BbCh/value.h 2010-07-20 22:24:14.000000000 +0200
@@ -36,7 +36,8 @@
VALUE_TYPE_NONE = 0,
VALUE_TYPE_UPPER = 1, // Upper bound
VALUE_TYPE_LOWER = 2, // Lower bound
- VALUE_TYPE_EXACT = VALUE_TYPE_UPPER | VALUE_TYPE_LOWER
+ VALUE_TYPE_BOTH = VALUE_TYPE_UPPER | VALUE_TYPE_LOWER,
+ VALUE_TYPE_EXACT = 7
};
@@ -44,8 +45,8 @@
VALUE_DRAW = 0,
VALUE_KNOWN_WIN = 15000,
VALUE_MATE = 30000,
- VALUE_INFINITE = 30001,
- VALUE_NONE = 30002,
+ VALUE_INFINITE = 30004, // because TT needs GrainSize>=4
+ VALUE_NONE = 30008,
VALUE_ENSURE_SIGNED = -1
};
