Extracting PV from TT

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
User avatar
cms271828
Posts: 316
Joined: Wed Apr 12, 2006 8:47 pm

Extracting PV from TT

Post by cms271828 » Sat Sep 12, 2009 3:45 am

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
Colin

Dann Corbit
Posts: 10101
Joined: Wed Mar 08, 2006 7:57 pm
Location: Redmond, WA USA
Contact:

Re: Extracting PV from TT

Post by Dann Corbit » Sat Sep 12, 2009 5:45 am

cms271828 wrote: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
Posts: 718
Joined: Fri Mar 20, 2009 7:59 pm

Re: Extracting PV from TT

Post by MattieShoes » Sat Sep 12, 2009 7:00 am

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
Posts: 1184
Joined: Sat Dec 13, 2008 6:00 pm
Contact:

Re: Extracting PV from TT

Post by Gian-Carlo Pascutto » Sat Sep 12, 2009 9:14 am

MattieShoes wrote: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.
Last edited by Gian-Carlo Pascutto on Sat Sep 12, 2009 9:17 am, edited 1 time in total.

Gian-Carlo Pascutto
Posts: 1184
Joined: Sat Dec 13, 2008 6:00 pm
Contact:

Re: Extracting PV from TT

Post by Gian-Carlo Pascutto » Sat Sep 12, 2009 9:16 am

Dann Corbit wrote: 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

Re: Extracting PV from TT

Post by Evert » Sat Sep 12, 2009 3:01 pm

Gian-Carlo Pascutto wrote: 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
Posts: 1184
Joined: Sat Dec 13, 2008 6:00 pm
Contact:

Re: Extracting PV from TT

Post by Gian-Carlo Pascutto » Sat Sep 12, 2009 5:48 pm

Evert wrote:
Gian-Carlo Pascutto wrote: 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.
Last edited by Gian-Carlo Pascutto on Sat Sep 12, 2009 5:49 pm, edited 1 time in total.

User avatar
cms271828
Posts: 316
Joined: Wed Apr 12, 2006 8:47 pm

Re: Extracting PV from TT

Post by cms271828 » Sat Sep 12, 2009 5:48 pm

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.
Colin

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

Re: Extracting PV from TT

Post by bob » Sat Sep 12, 2009 9:44 pm

Gian-Carlo Pascutto wrote:
Dann Corbit wrote: 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
Posts: 20549
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Extracting PV from TT

Post by bob » Sat Sep 12, 2009 9:46 pm

Gian-Carlo Pascutto wrote:
Evert wrote:
Gian-Carlo Pascutto wrote: 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.

Post Reply