Stockfish change request.

[jwes]

When you get a value from the transition table that causes a cutoff, you can ensure that the generation of that entry is the current generation, either by always storing it, which is what crafty does, or by storing it only if the generation is different. This should give an improvement which is slight in fast games, significant in slow games, and large when doing back and forth analysis.

[mcostalba]

When you get a value from the transition table that causes a cutoff, you can ensure that the generation of that entry is the current generation, either by always storing it, which is what crafty does, or by storing it only if the generation is different. This should give an improvement which is slight in fast games, significant in slow games, and large when doing back and forth analysis.

Sorry but I don't understand. TT entries are grouped in clusters. You are talking of overwrite an exsisting entry that corresponds to the _same_ position of the new one or to overwrite another position's entry ?

Below is the code. It would be great if you are able to write (also in peseudo code if you don't know C++) what is the change you are proposing.

Thanks
Marco

Code: Select all

/// 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. 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 Key posKey, Value v, ValueType t, Depth d, Move m) {

  TTEntry *tte, *replace;
  uint32_t posKey32 = posKey >> 32; // Use the high 32 bits as key

  tte = replace = first_entry(posKey);
  for &#40;int i = 0; i < ClusterSize; i++, tte++)
  &#123;
      if (!tte->key&#40;) || tte->key&#40;) == posKey32&#41; // empty or overwrite old
      &#123;
          // Do not overwrite when new type is VALUE_TYPE_EV_LO
          if &#40;tte->key&#40;) && t == VALUE_TYPE_EV_LO&#41;
              return;

          // Preserve any exsisting ttMove
          if &#40;m == MOVE_NONE&#41;
              m = tte->move&#40;);

          *tte = TTEntry&#40;posKey32, v, t, d, m, generation&#41;;
          return;
      &#125;
      else if &#40;i == 0&#41;  // replace would be a no-op in this common case
          continue;

      int c1 = &#40;replace->generation&#40;) == generation ?  2 &#58; 0&#41;;
      int c2 = &#40;tte->generation&#40;) == generation ? -2 &#58; 0&#41;;
      int c3 = &#40;tte->depth&#40;) < replace->depth&#40;) ?  1 &#58; 0&#41;;

      if &#40;c1 + c2 + c3 > 0&#41;
          replace = tte;
  &#125;
  *replace = TTEntry&#40;posKey32, v, t, d, m, generation&#41;;
  writes++;
&#125;

[Tord Romstad]

When you get a value from the transition table that causes a cutoff, you can ensure that the generation of that entry is the current generation, either by always storing it, which is what crafty does, or by storing it only if the generation is different. This should give an improvement which is slight in fast games, significant in slow games, and large when doing back and forth analysis.

Sorry but I don't understand. TT entries are grouped in clusters. You are talking of overwrite an exsisting entry that corresponds to the _same_ position of the new one or to overwrite another position's entry ?

I am also not sure I understand, but I think he means that when a transposition table entry from a previous search (i.e. with a generation different from the current generation) proves useful in the current search, the generation of that entry should be replaced with the current generation, in order to prevent it from getting overwritten too easily. It sounds like an interesting idea to me. It probably won't make a big difference, but it is hard to see how it could hurt.

[mcostalba]

When you get a value from the transition table that causes a cutoff, you can ensure that the generation of that entry is the current generation, either by always storing it, which is what crafty does, or by storing it only if the generation is different. This should give an improvement which is slight in fast games, significant in slow games, and large when doing back and forth analysis.

Sorry but I don't understand. TT entries are grouped in clusters. You are talking of overwrite an exsisting entry that corresponds to the _same_ position of the new one or to overwrite another position's entry ?

I am also not sure I understand, but I think he means that when a transposition table entry from a previous search (i.e. with a generation different from the current generation) proves useful in the current search, the generation of that entry should be replaced with the current generation, in order to prevent it from getting overwritten too easily. It sounds like an interesting idea to me. It probably won't make a big difference, but it is hard to see how it could hurt.

I don't think so. He writes "or by storing it only if the generation is different" so my _assumption_ is that the proposed idea could be reworded as:"When storing a position in TT if an entry of the _same_ position is already stored _and_ the generation of the stored position is the same of the current one _and_ the depth of the stored position is bigger then the current one then do _not_ overwrite the old entry"

But I would suggest, because we have the luck that the author of the original text is still alive and is not an old egyptian mummified 3000 years ago, that _he_ could explain us this mistery

[michiguel]

When you get a value from the transition table that causes a cutoff, you can ensure that the generation of that entry is the current generation, either by always storing it, which is what crafty does, or by storing it only if the generation is different. This should give an improvement which is slight in fast games, significant in slow games, and large when doing back and forth analysis.

Sorry but I don't understand. TT entries are grouped in clusters. You are talking of overwrite an exsisting entry that corresponds to the _same_ position of the new one or to overwrite another position's entry ?

I am also not sure I understand, but I think he means that when a transposition table entry from a previous search (i.e. with a generation different from the current generation) proves useful in the current search, the generation of that entry should be replaced with the current generation, in order to prevent it from getting overwritten too easily. It sounds like an interesting idea to me. It probably won't make a big difference, but it is hard to see how it could hurt.

He means rather than (pseudo code from gaviota):

transref_hit = transref_retrieve(po, po->hashsig, &merit, &height, &type, &tablemove);
if (transref_hit && i_can_cutoff(merit, height, type, depht_input)) {
return merit;
}

do

transref_hit = transref_retrieve(po, po->hashsig, &merit, &height, &type, &tablemove);
if (transref_hit && i_can_cutoff(merit, height, type, depht_input)) {
transref_refresh (po->hashsig, merit, height, type, tablemove);
return merit;
}

where "transref_refresh" restore the info just obtained from retrieve. If it was old, now becomes fresh, and if it was at the end of a bucket or in a second HT now it goes to the top.
At least when I introduced this (many years ago, so things could be different) the efficiency of the hash table improved a lot.

Miguel

[Eelco de Groot]

When you get a value from the transition table that causes a cutoff, you can ensure that the generation of that entry is the current generation, either by always storing it, which is what crafty does, or by storing it only if the generation is different. This should give an improvement which is slight in fast games, significant in slow games, and large when doing back and forth analysis.

Sorry but I don't understand. TT entries are grouped in clusters. You are talking of overwrite an exsisting entry that corresponds to the _same_ position of the new one or to overwrite another position's entry ?

I am also not sure I understand, but I think he means that when a transposition table entry from a previous search (i.e. with a generation different from the current generation) proves useful in the current search, the generation of that entry should be replaced with the current generation, in order to prevent it from getting overwritten too easily. It sounds like an interesting idea to me. It probably won't make a big difference, but it is hard to see how it could hurt.

He means rather than (pseudo code from gaviota):

transref_hit = transref_retrieve(po, po->hashsig, &merit, &height, &type, &tablemove);
if (transref_hit && i_can_cutoff(merit, height, type, depht_input)) {
return merit;
}

do

transref_hit = transref_retrieve(po, po->hashsig, &merit, &height, &type, &tablemove);
if (transref_hit && i_can_cutoff(merit, height, type, depht_input)) {
transref_refresh (po->hashsig, merit, height, type, tablemove);
return merit;
}

where "transref_refresh" restore the info just obtained from retrieve. If it was old, now becomes fresh, and if it was at the end of a bucket or in a second HT now it goes to the top.
At least when I introduced this (many years ago, so things could be different) the efficiency of the hash table improved a lot.

Miguel

This all is very interesting everybody, sorry if I don't follow much of the code. I just wanted to say that there seems some similarity with the changes John proposes to what Stockfish already does for nullmove cutoffs or am I wrong? Referring to the discussion about Stockfish storing nullmove cutoffs "renewed", even with "fudged" depths where I would think that you should maybe not do all that, use depth of verification search maybe or at least behaviour in long searches might be different.

Just to say back and forth analysis I think might require other changes? That subject came up on the Rybka forum too and because it was probably in a thread that the Stockfish programmers would not look for Stockfish references I'll post a reply of my own in that thread. I apologize for off topic crossposts and any imprecise or blatantly wrong description of Stockfish and Glaurung code!

Eelco

>> But your description of the Stockfish algorithm sounds like a serious flaw.
> For the first part, it seems like a display issue (e.g. going from 0.40 to 0.70 to 0.00 back to 0.40, ONE of these is reliable, but no way to know which one is, it's almost as if Stockfish showed no evaluation), but it seems to affect all moves consistently (i.e. I don't see Stockfish switching move choice continuously due to this, and since it is very good, probably the problem isn't as bad as it looks).
>


Can't speak for the programmers but I'll try to shed some light on what is happening anyway This I think is mainly a problem with very narrow searchwindows. They speed up a PV search but the chance of "falling out of the window" is as you can easily appreciate all the more frequent. You see the result of a nullwindow search here saying "I'm somewhere on this side of the window" or "I'm somewhere on that side of the window". In Joona's scheme there are now a lot of re-searches, - widen window, then search again to the same depth -, but the aspiration windows are extended only gradually and in the direction that we fell out of it. Changing that is not so easy at least I'm not having too much succes doing that, but this way cannot fully deal with search instabilities; fail highs following a fail low and vice versa. If you want to read more about this try finding the programming introduction from Bruce Moreland, it will be somewhere on the Chessprogramming Wiki only as an archive I'm afraid.

Rybka "suffers" from similar re-searches as you all know when it uses very narrow searchwindows for resolving fail highs and fail lows but the information in them is seemingly less because Vas does not want to print unreliable PVs. And Stockfish just has larger eval swings coupled to the nullwindow searches than Rybka.



> For the second part it seems like terrible hash usage between moves, because on a single move, Stockfish hash usage has been praised as very powerful, or most powerful among engines, in where hash contents are capable of solving positions in record times (e.g. using the hash to exhaust the possible moves until you recognize fortress positions, while the other engines keep showing high scores).
>


This probably has pros and cons but for using Stockfish as analysis partner more cons, well, Tord never saw that as very important because he was to impatient for it Well something to that effect and Glaurung in the beginning had even more "optimism" built into its search, so it was not really consistent enough for long searches. This is mainly a legacy thing I think, I'm sure the programmers would consider looking at requests for making Stockfish better here.


> For the second part, yes, elo points must be hiding in there, a correct hash usage between moves (see Zappa Mexico, the best I've seen on this) or just a learning mechanism where Stockfish saves to a file its analysis to restore later (see Shredder, the best on this) would make Stockfish play as if the opponents were giving it a time handicap (Stockfish would find better moves faster since it doesn't need to start from scratch every time).


Some very basic sort of result learning Tord threw out of Glaurung quite a while ago because he felt the users did not understand what it was for
I'm not kidding But this is also a hidden treasure in old Glaurung's den, that means there is example code for a very basic form of keeping hashresults and it has been a secret plan of mine to do something with that... I would have to steal it from under the dragons belly when it is sleeping. But for Tord or Marco and Joona it would probably be less than half a days work to put the old code to work again? Efficient learning is of a totally different order I think, Stefan Meyer-Kahlen I'm sure has worked long and hard on getting it this good in Shredder.

Regards, Eelco

[zamar]

Are you talking about sth like this?

--- a/src/search.cpp
+++ b/src/search.cpp
@@ -1302,6 +1302,7 @@ namespace {
if (tte && ok_to_use_TT(tte, depth, beta, ply))
{
ss[ply].currentMove = ttMove; // Can be MOVE_NONE
+ TT.store(posKey, tte->value(), tte->type(), tte->depth(), tte->move());
return value_from_tt(tte->value(), ply);
}

@@ -1625,6 +1626,7 @@ namespace {
assert(tte->type() != VALUE_TYPE_EVAL);

ss[ply].currentMove = ttMove; // Can be MOVE_NONE
+ TT.store(pos.get_key(), tte->value(), tte->type(), tte->depth(), tte->move());
return value_from_tt(tte->value(), ply);
}

[zamar]

The jumping score people complain about has nothing to do with evaluation or transposition table. It is simply result of search instability caused by very aggressive late move reductions and prunings. Small differences in move ordering result in very different scores when you search deep.

Irritating perhaps, yes, but not fixable, because it's not a bug but a feature. We could solve the issue by printing less information, but we do not want to do it.

[mcostalba]

Are you talking about sth like this?

I have started a test with the following patch:

Code: Select all

Date: Thu, 29 Apr 2010 18:21:48 +0100
Subject: [PATCH] Refresh TT entry after a cut-off to avoid aging

Re-save the same TT entry if value is usable and allow
us to cut-off, it means that entry is valuable and
we want to keep it fresh updating the 'generation'
parameter up to the current value.

Patch suggested by J. Wesley Cleveland and better
clarified by Miguel A. Ballicora.

---
 src/search.cpp |    6 ++++++
 1 files changed, 6 insertions(+), 0 deletions(-)

diff --git a/src/search.cpp b/src/search.cpp
index b2b2414..84f5273 100644
--- a/src/search.cpp
+++ b/src/search.cpp
@@ -1301,6 +1301,9 @@ namespace {
 
     if (tte && ok_to_use_TT(tte, depth, beta, ply))
     {
+        // Refresh tte entry to avoid aging
+        TT.store(posKey, tte->value(), tte->type(), tte->depth(), tte->move());
+
         ss[ply].currentMove = ttMove; // Can be MOVE_NONE
         return value_from_tt(tte->value(), ply);
     }
@@ -1624,6 +1627,9 @@ namespace {
     {
         assert(tte->type() != VALUE_TYPE_EVAL);
 
+        // Refresh tte entry to avoid aging
+        TT.store(pos.get_key(), tte->value(), tte->type(), tte->depth(), tte->move());
+
         ss[ply].currentMove = ttMove; // Can be MOVE_NONE
         return value_from_tt(tte->value(), ply);
     }
-- 
1.6.5.1.1367.gcd48

[michiguel]

Are you talking about sth like this?

--- a/src/search.cpp
+++ b/src/search.cpp
@@ -1302,6 +1302,7 @@ namespace {
if (tte && ok_to_use_TT(tte, depth, beta, ply))
{
ss[ply].currentMove = ttMove; // Can be MOVE_NONE
+ TT.store(posKey, tte->value(), tte->type(), tte->depth(), tte->move());
return value_from_tt(tte->value(), ply);
}

@@ -1625,6 +1626,7 @@ namespace {
assert(tte->type() != VALUE_TYPE_EVAL);

ss[ply].currentMove = ttMove; // Can be MOVE_NONE
+ TT.store(pos.get_key(), tte->value(), tte->type(), tte->depth(), tte->move());
return value_from_tt(tte->value(), ply);
}

Yes, I think that is what I meant.

Note that what you have as TT.store may be improved with a hypothetical TT.refresh depending on your internals. For instance, a simple store may end up with two copies of the same entry. A "refresh" may bump the last used entry up to make sure it is not a the bottom of the pile, without having two copies. Anyway, even if you end up with two copies of the same entry your new version may be better.

If you are going to test this, it won't show a difference at fast games and big HT. Make sure that HT is somehow filled, reducing its size.

Miguel