capturing PV in QSearch

[thevinenator]

I've implemented Bruce Moreland's " PV-List on the Stack" method of capturing PV which works like a champ.
I use it to display the PV to the GUI as well as posting the moves back to the TT between iterations.

Currently I'm not capturing the PV or storing anything in the TT in QSearch.

This all started because I was trying to reconcile my displayed eval to what the static eval was producing and realized I wasn't taking into account the QSearch moves which ends in a call to eval.

so other than displaying the QSearch PV moves for debugging purposes, is there any benefit (doing something with the TT as well) for collecting the PV in the QSearch ?

I've seen threads on other forums where Dr. Hyatt, as an example explained that using the TT in Crafty's QSearch was a wash, but that was a thread from a few years ago and there might be new data or ideas now.

[notachessplayer]

Performance.
Same as in your alpha beta, you would store the best move for a certain position key, with a certain depth. If the depth is bigger or equal to your current depth, then no need to go on searching, you can return the score of that move.

[thevinenator]

I'm aware of how the TT works, my main TT works great.

Just curious if there is any new developments regarding PV/TT in the QSearch.

[H.G.Muller]

Most engines of course do not get the PV out of the hash table, so that storing QS in the TT is really a separate issue. Retrieving it from the hash almost never leads to the node that provided the score, even if you did store QS nodes.

BTW, not storing QS nodes made all of my engines weaker.

[sandermvdb]

Most engines of course do not get the PV out of the hash table, so that storing QS in the TT is really a separate issue. Retrieving it from the hash almost never leads to the node that provided the score, even if you did store QS nodes.

I DO get the PV from the hash-table and was wondering if I maybe also should implement Bruce Moreland's concept. Does this only result in a better (longer and more accurate) PV or will this also improve the move ordering? (I guess the second)

[thevinenator]

Bruce's code saves the PV going down the search tree, saving the best line each time alpha is raised, but once back to the top, what to do with it?

at first I was just using it to pass on the best "line" to the GUI, but after examining some Stockfish code, I saw where they write the PV back to the hash, but with values that will cause the entry to be ignored for cutoffs. Since I implemented a double entry (Always/better depth) hash, I then had a Eureka moment. I take the PV and push the position/move back to the "always" entry in the hash, only if there isn't already a better one there.

as the next iteration begins, it will always find the PV I entered in the hash and will use either a previously stored "cutoff" entry or will use the PV entry to retrieve the best move to try first. I don't even bother with any move ordering yet, I push that off till I've tried the move the hash, if one is present.

I'm sure that this is old school for most of the seasoned engine designers, but it is good to hear about what others have done as many times as it takes to sink in! LOL

Just by writing this did I realize I might not be doing the check correctly when I write a PV to the hash..so it's back to the code once again!

As for your comment about move ordering, no move is better than the move that was tried the iteration before. The code will continue to walk down the tree and try all those PV moves out of the hash till it reaches the bottom (now one ply deeper) and then it will have to think and then back track back up the tree. it is only when a secondary choice of moves is needed do you need to worry about move ordering. My code generates the move list prior to making the PV move, so that the PV move can be validated as "legal". when it finds it in the move list, it is flagged as used so that the next move fetch will ignore it.

hope that helps

[sandermvdb]

Bruce's code saves the PV going down the search tree, saving the best line each time alpha is raised, but once back to the top, what to do with it?

at first I was just using it to pass on the best "line" to the GUI, but after examining some Stockfish code, I saw where they write the PV back to the hash, but with values that will cause the entry to be ignored for cutoffs. Since I implemented a double entry (Always/better depth) hash, I then had a Eureka moment. I take the PV and push the position/move back to the "always" entry in the hash, only if there isn't already a better one there.

as the next iteration begins, it will always find the PV I entered in the hash and will use either a previously stored "cutoff" entry or will use the PV entry to retrieve the best move to try first. I don't even bother with any move ordering yet, I push that off till I've tried the move the hash, if one is present.

Yesterday I implemented Bruce's code and I am also writing the PV back to the hash. But what do you mean by this regarding Stockfish: 'but with values that will cause the entry to be ignored for cutoffs'?
And you are updating your "always" hash only if the score is better. But what do you mean by better?

As for your comment about move ordering, no move is better than the move that was tried the iteration before. The code will continue to walk down the tree and try all those PV moves out of the hash till it reaches the bottom (now one ply deeper) and then it will have to think and then back track back up the tree. it is only when a secondary choice of moves is needed do you need to worry about move ordering. My code generates the move list prior to making the PV move, so that the PV move can be validated as "legal". when it finds it in the move list, it is flagged as used so that the next move fetch will ignore it.

hope that helps

I was indeed thinking about trying (ordering) the PV move first because the hashtable could be overwritten, whereas the PV isn't.

Yes this helps!

[H.G.Muller]

If your hash table preserves deep entries, there hardly is any benefit from storing the PV back into the TT. The early part of it should still be there, because of its high depth. And the few moves at the end that could have been overwritten take negligible time to search again.

[thevinenator]

Bruce's code saves the PV going down the search tree, saving the best line each time alpha is raised, but once back to the top, what to do with it?

at first I was just using it to pass on the best "line" to the GUI, but after examining some Stockfish code, I saw where they write the PV back to the hash, but with values that will cause the entry to be ignored for cutoffs. Since I implemented a double entry (Always/better depth) hash, I then had a Eureka moment. I take the PV and push the position/move back to the "always" entry in the hash, only if there isn't already a better one there.

as the next iteration begins, it will always find the PV I entered in the hash and will use either a previously stored "cutoff" entry or will use the PV entry to retrieve the best move to try first. I don't even bother with any move ordering yet, I push that off till I've tried the move the hash, if one is present.

Yesterday I implemented Bruce's code and I am also writing the PV back to the hash. But what do you mean by this regarding Stockfish: 'but with values that will cause the entry to be ignored for cutoffs'?
And you are updating your "always" hash only if the score is better. But what do you mean by better?

i only overwrite the "always replace" half of the TT entry, not the "deeper then" part. if you already have an entry in the "deeper then" entry, you wouldn't want to overwrite it with a entry that has no depth; just use the one that is there. if you do store the PV, you want to make sure the depth and value are not such that the TT would think the entry is good enough to cause a cutoff, so put in a negative depth which will never be better than the depth you are in the search (unless your search allows negative depths). i didn't say i use the score, i write back a score that represents a value that can never occur in the evaluation. it doesn't matter, actually since the negative depth prevents the entry from ever being used for a score, but it will still return the move.

As for your comment about move ordering, no move is better than the move that was tried the iteration before. The code will continue to walk down the tree and try all those PV moves out of the hash till it reaches the bottom (now one ply deeper) and then it will have to think and then back track back up the tree. it is only when a secondary choice of moves is needed do you need to worry about move ordering. My code generates the move list prior to making the PV move, so that the PV move can be validated as "legal". when it finds it in the move list, it is flagged as used so that the next move fetch will ignore it.

hope that helps

I was indeed thinking about trying (ordering) the PV move first because the hashtable could be overwritten, whereas the PV isn't.

Yes this helps!

[thevinenator]

If your hash table preserves deep entries, there hardly is any benefit from storing the PV back into the TT. The early part of it should still be there, because of its high depth. And the few moves at the end that could have been overwritten take negligible time to search again.

i'll do some timing tests to see if is a wash, but it seems from your comments that the turbulence in the hash entries occurs near the leaf nodes, which makes sense because the search spends most of its time there, so wouldn't every little bit help down in the trenches, so to speak?