Idea for ID/transposition table

[JimmyRustles]

I was thinking, before you start your iterative deepening, you could probe the hash table, and if you get an exact result, start the ID search from the TT entry depth + 1 since you already have a result at depth. If you run out of time, you can just use the TT entry result.

So if you probe the TT at the root and it has an exact entry at depth 20, you can start the search at depth 21 and if you run out of time, just use the depth 20 TT result.

Is there a reason why this wouldn't work?

[bob]

Probably would work, but you won't have a PV for the best move at that point.

Would be sort of an odd circumstance as to how this might happen, however.

[hgm]

Most of my engines work that way. It happens sort of automatically, because I don't have a separate RootSearch routine, and it is what I do in every other node. I would have to slip in conditional code only active in the root to suppress it.

And it happens quite often; all it needs is that you expected the opponent's move (i.e. would have had a ponder hit if you had been pondering). Suou of course played your own PV move, so if the opponent plays the expected reply, you are still on our old PV, and the TT entry for it will be exact.

You don't save measurable time by this, though. If you don't do it, and start iterating from scratch, the iterations you have already done the previous time you visited the node will give you TT cutoffs in their daughter nodes, because you have done those already too. So these iterations take zero time, and you see the depth run up to previousDepth+1 in a flash, with PVs of 1 move. Unless you don't allow hash cuts in PV nodes, of course; then it would follow the PV, but every side branch would still give you a hash cutoff. So instead of each iteration taking 1 node, they then take 1, 2, 3, ... N nodes. Still negligible.

[chrisw]

Probably would work, but you won't have a PV for the best move at that point.

Would be sort of an odd circumstance as to how this might happen, however.

There's a moderately good chance that the PV can be recreated by following the stored best move from the hash for as far as it goes, which optimally will be the depth N position. *If* the hash table size was sufficient, then it contains most of the essential best-move information for the important parts of the tree, presumably carried over from previous searches, so the OP suggestion is viable. Whether worth doing or not, as usual, discoverable by empirical method, doubtful we could theoretically argue this one out.

[hgm]

That holds for any kind of hash cut in a PV node. A more reliable method is to store the PV of TT nodes in the hash table (which, for efficiency reasons, usually means you would use a separate hash table or hash-table extension for PV nodes). Then you will always have the full PV availabe, and you can in addition be sure that it actually leads to the position that provided the score, and was not altered by the search afterwards.

I thought that Crafty used that method.

[bob]

Probably would work, but you won't have a PV for the best move at that point.

Would be sort of an odd circumstance as to how this might happen, however.

There's a moderately good chance that the PV can be recreated by following the stored best move from the hash for as far as it goes, which optimally will be the depth N position. *If* the hash table size was sufficient, then it contains most of the essential best-move information for the important parts of the tree, presumably carried over from previous searches, so the OP suggestion is viable. Whether worth doing or not, as usual, discoverable by empirical method, doubtful we could theoretically argue this one out.

This is problematic. Many have tried it. But you end up with nonsense on the end of the PV. I came up with a different solution in Crafty. For every "exact" entry stored, I save the PV in a separate hash table. Since there are few EXACT entries saved, this doesn't require a ton of memory, and you get the exact PV that starts at the current move and goes to the last move where your eval produced the score.

[MOBMAT]

Probably would work, but you won't have a PV for the best move at that point.

Would be sort of an odd circumstance as to how this might happen, however.

There's a moderately good chance that the PV can be recreated by following the stored best move from the hash for as far as it goes, which optimally will be the depth N position. *If* the hash table size was sufficient, then it contains most of the essential best-move information for the important parts of the tree, presumably carried over from previous searches, so the OP suggestion is viable. Whether worth doing or not, as usual, discoverable by empirical method, doubtful we could theoretically argue this one out.

This is problematic. Many have tried it. But you end up with nonsense on the end of the PV. I came up with a different solution in Crafty. For every "exact" entry stored, I save the PV in a separate hash table. Since there are few EXACT entries saved, this doesn't require a ton of memory, and you get the exact PV that starts at the current move and goes to the last move where your eval produced the score.

Do the PV also get stored in the main TT as well or "only" in the special PV TT. Seems to me, that if you don't store in both, then a PV node might be missed elsewhere in a situation where the code is looking for the node in the main TT

[hgm]

That is an implementation detail. Many different efficient implementations seem possible. You could use the move field of an exact entry as an index into a table of PVs. Or you could make a separate (relatively small) hash table that contains only signature + PV, which you only consult when you make a hash cut in a PV node.