OpenChess

H.G.Muller wrote: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.

thevinenator wrote: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.

thevinenator wrote: 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 wrote:

thevinenator wrote: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.

thevinenator wrote: 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 wrote: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.