Idea for ID/transposition table

Discussion of chess software programming and technical issues.

Moderators: Harvey Williamson, Dann Corbit, hgm

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
User avatar
JimmyRustles
Posts: 22
Joined: Sun May 05, 2019 9:24 pm
Full name: Steven Griffin

Idea for ID/transposition table

Post by JimmyRustles » Sat Jul 11, 2020 12:52 am

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
Posts: 20920
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Idea for ID/transposition table

Post by bob » Sat Jul 11, 2020 2:53 am

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.

User avatar
hgm
Posts: 25386
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Idea for ID/transposition table

Post by hgm » Sat Jul 11, 2020 6:17 am

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.
Get rid of the shit: vote for SHID!

chrisw
Posts: 3851
Joined: Tue Apr 03, 2012 2:28 pm

Re: Idea for ID/transposition table

Post by chrisw » Sat Jul 11, 2020 8:45 am

bob wrote:
Sat Jul 11, 2020 2:53 am
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.

User avatar
hgm
Posts: 25386
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Idea for ID/transposition table

Post by hgm » Sat Jul 11, 2020 8:54 am

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.
Get rid of the shit: vote for SHID!

bob
Posts: 20920
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Idea for ID/transposition table

Post by bob » Sun Jul 12, 2020 1:34 am

chrisw wrote:
Sat Jul 11, 2020 8:45 am
bob wrote:
Sat Jul 11, 2020 2:53 am
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
Posts: 327
Joined: Sat Feb 04, 2017 10:57 pm
Location: USA

Re: Idea for ID/transposition table

Post by MOBMAT » Sun Jul 12, 2020 4:47 am

bob wrote:
Sun Jul 12, 2020 1:34 am
chrisw wrote:
Sat Jul 11, 2020 8:45 am
bob wrote:
Sat Jul 11, 2020 2:53 am
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
i7-6700K @ 4.00Ghz (using 6 threads), EGTBs on PCI SSD
Benchmark: Stockfish 11 64 bmi2 (nps): 2067669

User avatar
hgm
Posts: 25386
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Idea for ID/transposition table

Post by hgm » Sun Jul 12, 2020 6:16 am

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.
Get rid of the shit: vote for SHID!

Post Reply