Extracting PV from TT

[cms271828]

Hi,

I read this http://web.archive.org/web/200404270138 ... ing/pv.htm, it says it should be possible to collect the PV from the TT after the search.

I'm not sure if this will work, cause elements get overwritten, and I don't store elements of TT during QS, so a full PV won't be possible I don't think, but it will be upto its search depth I guess.

After the search, I'll have the best move, the score for it, and also the root position that was searched, so I guess if we look this up in the TT, we will also find this best move??

So then I guess, we can play that move on some imaginary board, to get a new position, which we can look for in the TT, if theres a best move, we can use it, and continue like this as far as possible.

Will this idea work, and will it possibly break down?

Thanks

[Dann Corbit]

Hi,

I read this http://web.archive.org/web/200404270138 ... ing/pv.htm, it says it should be possible to collect the PV from the TT after the search.

I'm not sure if this will work, cause elements get overwritten, and I don't store elements of TT during QS, so a full PV won't be possible I don't think, but it will be upto its search depth I guess.

After the search, I'll have the best move, the score for it, and also the root position that was searched, so I guess if we look this up in the TT, we will also find this best move??

So then I guess, we can play that move on some imaginary board, to get a new position, which we can look for in the TT, if theres a best move, we can use it, and continue like this as far as possible.

Will this idea work, and will it possibly break down?

Thanks

If you don't overwrite your pv nodes, then you won't pull bad pv values. The pv nodes are special.

The simplest way is to simply carry the pv as a list or array. There is not much overhead, even for a 100 ply search. I think that most people do it this way, since it is foolproof.

[MattieShoes]

It's possible but less bothersome to just store the PV manually whenever it changes.

Pulling it from the TT works but be careful of getting caught in a loop -- It's possible to pull an infinitely long PV from the hash table. Depending on how you store moves, you can also potentially run into issues where the move is illegal -- say trading QR instead of KR results in the same position because the recapture is with the untraded rook.. Then your best move in hash could potentially be telling you to move a rook that's not on the chessboard, etc.

[Gian-Carlo Pascutto]

Depending on how you store moves, you can also potentially run into issues where the move is illegal -- say trading QR instead of KR results in the same position because the recapture is with the untraded rook.. Then your best move in hash could potentially be telling you to move a rook that's not on the chessboard, etc.

This makes very little sense to me. The hashkey would be different so it's impossible to get a hit.

[Gian-Carlo Pascutto]

The simplest way is to simply carry the pv as a list or array. There is not much overhead, even for a 100 ply search. I think that most people do it this way, since it is foolproof.

In my mind, explicitly storing the PV is a needless waste of time. The PV should be fully obtainable from the hashtable. If it's not, you've got a serious bug you need to fix. So I prefer to find those early by relying 100% on the hashtable to get the PV.

[Evert]

In my mind, explicitly storing the PV is a needless waste of time. The PV should be fully obtainable from the hashtable. If it's not, you've got a serious bug you need to fix.

That's not quite true. In an ideal world where no hash table entries get overwritten, that would be true. In practice, hash table entries get replaced. You can mark PV nodes in the hash table and not overwrite them with non-PV nodes, but that can (will?) make your transposition table less efficient becaue you're not storing information that you should be storing. You can rehash the position in that case or use multiple slots, but again, that is slightly cumbersome. You have to do that should two PV nodes hash to the same position.
In other words, yes, you can retrieve the information from the transposition table, but unless you take special precaution, that is not 100% reliable, even if the implementation has no serious bugs.

[Gian-Carlo Pascutto]

In my mind, explicitly storing the PV is a needless waste of time. The PV should be fully obtainable from the hashtable. If it's not, you've got a serious bug you need to fix.

That's not quite true. In an ideal world where no hash table entries get overwritten, that would be true. In practice, hash table entries get replaced. You can mark PV nodes in the hash table and not overwrite them with non-PV nodes, but that can (will?) make your transposition table less efficient becaue you're not storing information that you should be storing. You can rehash the position in that case or use multiple slots, but again, that is slightly cumbersome. You have to do that should two PV nodes hash to the same position.
In other words, yes, you can retrieve the information from the transposition table, but unless you take special precaution, that is not 100% reliable, even if the implementation has no serious bugs.

Do you have any idea how many nodes in a search are PV nodes?

We've moved on since the time computers had 8k memory. If you are evicting PV nodes from your hash, you have a bug. And yes, obviously you have to use hashtable with multiple buckets. Not having that I would consider a bug.

[cms271828]

Thanks,

I wrote the code, and tried it on a couple of checkmate puzzles, and it coughed up the correct sequence of moves (PV) as intended.

I can see a problem when the moves start to repeat themselves, as that will print out an infinite sequence, but I can fix that.

I'm just using PV so I can see the programs line of thought, it doesn't have to be 100% accurate, but that would be nice though.

[bob]

The simplest way is to simply carry the pv as a list or array. There is not much overhead, even for a 100 ply search. I think that most people do it this way, since it is foolproof.

In my mind, explicitly storing the PV is a needless waste of time. The PV should be fully obtainable from the hashtable. If it's not, you've got a serious bug you need to fix. So I prefer to find those early by relying 100% on the hashtable to get the PV.

This is trivially _not_ a bug. On the last iteration, any move can involve a ton of searching, and can overwrite things, particularly the hash PV entries for shallow draft entries. I've never seen an implementation that did not have this problem...

[bob]

In my mind, explicitly storing the PV is a needless waste of time. The PV should be fully obtainable from the hashtable. If it's not, you've got a serious bug you need to fix.

That's not quite true. In an ideal world where no hash table entries get overwritten, that would be true. In practice, hash table entries get replaced. You can mark PV nodes in the hash table and not overwrite them with non-PV nodes, but that can (will?) make your transposition table less efficient becaue you're not storing information that you should be storing. You can rehash the position in that case or use multiple slots, but again, that is slightly cumbersome. You have to do that should two PV nodes hash to the same position.
In other words, yes, you can retrieve the information from the transposition table, but unless you take special precaution, that is not 100% reliable, even if the implementation has no serious bugs.

Do you have any idea how many nodes in a search are PV nodes?

We've moved on since the time computers had 8k memory. If you are evicting PV nodes from your hash, you have a bug. And yes, obviously you have to use hashtable with multiple buckets. Not having that I would consider a bug.

What about a case where the PV move at the root searches a tree of 500M nodes. And the _second_ move is almost good enough to become the best, but not quite? And it can easily search 500M nodes or _more_. And while deep draft entries are not usually lost, the ones near the tip can get overwritten in a heartbeat.

IMHO the PV is a complete variation, that goes from the root move through the last move made before Evaluate() is called to produce the actual score backed up to the root.