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
Extracting PV from TT
Moderators: hgm, Rebel, chrisw
-
- Posts: 12541
- Joined: Wed Mar 08, 2006 8:57 pm
- Location: Redmond, WA USA
Re: Extracting PV from TT
If you don't overwrite your pv nodes, then you won't pull bad pv values. The pv nodes are special.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
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.
-
- Posts: 718
- Joined: Fri Mar 20, 2009 8:59 pm
Re: Extracting PV from TT
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.
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.
-
- Posts: 1243
- Joined: Sat Dec 13, 2008 7:00 pm
Re: Extracting PV from TT
This makes very little sense to me. The hashkey would be different so it's impossible to get a hit.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.
Last edited by Gian-Carlo Pascutto on Sat Sep 12, 2009 11:17 am, edited 1 time in total.
-
- Posts: 1243
- Joined: Sat Dec 13, 2008 7:00 pm
Re: Extracting PV from TT
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.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.
Re: Extracting PV from TT
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.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.
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.
-
- Posts: 1243
- Joined: Sat Dec 13, 2008 7:00 pm
Re: Extracting PV from TT
Do you have any idea how many nodes in a search are PV nodes?Evert wrote: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.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.
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.
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 7:49 pm, edited 1 time in total.
-
- Posts: 316
- Joined: Wed Apr 12, 2006 10:47 pm
Re: Extracting PV from TT
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.
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
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Extracting PV from TT
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...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. So I prefer to find those early by relying 100% on the hashtable to get the PV.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.
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Extracting PV from TT
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.Gian-Carlo Pascutto wrote:Do you have any idea how many nodes in a search are PV nodes?Evert wrote: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.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.
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.
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.
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.