xcomponent wrote:If it comes down to printing the PV, i dont see a problem to do whatever you want (retrieve it).
My personal opinion if we talk about move ordering is that the pv_move and tt_move should be delimited if they differ from each other.
I may misunderstood the general topic idea, but i didn't see if it's about collecting the pv for move ordering (or refute) or just collecting it for printing.
Why would it matter? In what case can they differ anyway in PV nodes? A PV is by definition the sequence with the best moves.
I didn't say anything about pv-nodes, all-nodes or cut-nodes.
"My personal opinion if we talk about move ordering is that the pv_move and tt_move should be delimited if they differ from each other."
"i didn't see if it's about collecting the pv for move ordering (or refute) or just collecting it for printing"
If you talk about collecting the PV or about move ordering with pv_move, you are talking about PV nodes. Even if you would refuse to acknowledge that, what you said *still* doesn't make any sense: please explain how you first sentence can happen, i.e. a case where pv_move != tt_move.
xcomponent wrote:If it comes down to printing the PV, i dont see a problem to do whatever you want (retrieve it).
My personal opinion if we talk about move ordering is that the pv_move and tt_move should be delimited if they differ from each other.
I may misunderstood the general topic idea, but i didn't see if it's about collecting the pv for move ordering (or refute) or just collecting it for printing.
It is about collecting the PV after the search has terminated. What I want to see is the PV from the root position all the way to the terminal position that produced the score that was backed up as best, since that is a useful bit of data for debugging.
bob wrote:
How do you know an entry is a PV entry? And if you flag each one, how do you go back and remove the flag as the PV changes while searching the first move, or even as you search other root moves?
Entries with exact scores are PV entries. The amount of them in a complete search is so minuscule that you shouldn't have to evict them from your hashtable. Obviously you don't replace them by bound entries with deeper drafts.
For a new search they are evicted due to aging.
I replace them since the deeper draft entry is more useful. Hence the term "depth-preferred".
There can be lots of EXACT entries in the hash table that have nothing to do with the PV. I don't want 'em sticking around and do my best to save that which will save me the most work if I hit that entry.
I used depth preferred in Cray Blitz, modified by preferring exact over bound entries. I eventually god rid of the "type" test and just used depth and found better performance. I again tried this in early versions of Crafty, and went to the pure depth-preferred replacement scheme which again provided better performance. YMMV of course, but for my circumstances, I am certain it is better to do it the way I am currently doing it.
And of course, this still leaves the _same_ problem as before. You can _still_ overwrite the original PV entry with a PV entry from a later search, even though that search never produces a new best move at the root...
Gian-Carlo Pascutto wrote:
Entries with exact scores are PV entries. The amount of them in a complete search is so minuscule that you shouldn't have to evict them from your hashtable. Obviously you don't replace them by bound entries with deeper drafts.
What are typical values for the number of PV nodes in a search?
I checked my engine: about 0.01% to 0.1% (for searches of about 10M nodes).
This seems a little on the high side.
Doesn't seem unusual. You will get lots of fail-highs in a PVS search, which lets you store scores that are > alpha and < beta, even though these scores never back up to the root or anywhere near it.
well I get my PV from TT, and it does lose chunks of the PV quite frequently....and I use a TT with an associativity value of 4. Of course, I admit its quite plausible that I have bugs in my TT so I am no help in the current debate . A practical note: if you do this, design things such that you always maintain a best move AND a best reply without relying on the TT. The best reply is important because you always want something to ponder.
And while I don't plan to debate it....I agree with Bob that if you do this you MUST assume you will be losing some of your PV regularly. I also agree with Gian-Carlo that it is helpful to spot glaring bugs in your TT to keep an eye on how frequently this happens.
BubbaTough wrote:well I get my PV from TT, and it does lose chunks of the PV quite frequently....and I use a TT with an associativity value of 4. Of course, I admit its quite plausible that I have bugs in my TT so I am no help in the current debate . A practical note: if you do this, design things such that you always maintain a best move AND a best reply without relying on the TT. The best reply is important because you always want something to ponder.
And while I don't plan to debate it....I agree with Bob that if you do this you MUST assume you will be losing some of your PV regularly. I also agree with Gian-Carlo that it is helpful to spot glaring bugs in your TT to keep an eye on how frequently this happens.
-Sam
The thing that made me drop this in Crafty when I was testing it was that for debugging, I _really_ want the complete PV that takes me to the position that produced the best score. I have found lots of bugs like that because I can identify the precise position that produces a score, and then I can feed that to the scoring code with no search involved to see where the odd values are coming from. yes, I get an occasional short PV due to TT hits that terminate the search with an EXACT value produced in a previous search somewhere. But this is not nearly as common as the missing tail end of the PV that I saw when I used the hash table only.
BTW current crafty is also using an associativity of 4 as I have mentioned. I decided to do this to improve cache-alignment issues where a bucket size of anything but 64 results in too many double-cache-line fills...
BubbaTough wrote:well I get my PV from TT, and it does lose chunks of the PV quite frequently....and I use a TT with an associativity value of 4. Of course, I admit its quite plausible that I have bugs in my TT so I am no help in the current debate . A practical note: if you do this, design things such that you always maintain a best move AND a best reply without relying on the TT. The best reply is important because you always want something to ponder.
And while I don't plan to debate it....I agree with Bob that if you do this you MUST assume you will be losing some of your PV regularly. I also agree with Gian-Carlo that it is helpful to spot glaring bugs in your TT to keep an eye on how frequently this happens.
-Sam
I believe that if you have a goal, the best philosophy is to design a straightforward algorithm to reach it. If the PV is important for the programmer and user, then there should be an algorithm that will guarantee to get it. Storing the PV is the one, getting from the TT is not. Getting things accomplished from a side effects of other algorithms is not the best design, IMHO. Whenever you touch one, you have to think about secondary effects on others. What if you do not store 3-reps? what if you do not store the last ply of the search? Any of those decisions and could be many more, will affect how you get the PV. I do not like that.
I do not think getting the PV from the TT is a good idea because it will catch bugs. If the intention is to catch bugs, and not getting the PV itself, then an explicit procedure should be done for it. For instance, in a debug version of the engine, the PV should be calculated in both ways and whenever there is a difference the results should be logged and/or caught with an assert().
If we care about getting a PV, then we should do it. If we care catching bugs, then lets's have a debug version of the engine and compare procedures.
Bob and Miguel are both making sense . It sounds like the ideal would be:
1. Debug version. Gets PV both ways (since they both help different aspect of debugging).
2. Performance version. If you really really care about winning a tournament, I guess getting PV from TT is a tiny tiny bit better.
3. Release version. explicitly track PV. People like to see the PV, and this is the sure-fire way.
michiguel wrote:Getting things accomplished from a side effects of other algorithms is not the best design, IMHO.
Well this really the crux of the matter I guess. The PV is the single most important variation for the move ordering of the entire search. The hash table is the single most important tool for storing move ordering information. I find that being able to retrieve the most important move ordering information from the table that's supposed to store it is not a side effect, but the design requirement.
Having to work around a buggy hashtable that's not able to remember it by storing it twice...now that is IMHO bad design
michiguel wrote:Getting things accomplished from a side effects of other algorithms is not the best design, IMHO.
Well this really the crux of the matter I guess. The PV is the single most important variation for the move ordering of the entire search. The hash table is the single most important tool for storing move ordering information. I find that being able to retrieve the most important move ordering information from the table that's supposed to store it is not a side effect, but the design requirement.
Having to work around a buggy hashtable that's not able to remember it by storing it twice...now that is IMHO bad design
IMHO the best design is the one that works best. If you refuse to overwrite an EXACT entry, performance goes down. It's been measured by several different people using different programs, over the years. I do not consider overwriting something that is less useful with something that is more useful to be "buggy" when it offers the best performance _during_ the search. When an iteration ends, it is certainly trivial and costs nothing to make sure that the PV is actually in the table so that move ordering uses the PV first.
I've never seen _anyone_ disagree that "the most useful entries" are those with the highest draft, since they are the ones that save the most effort when they are used. This means that entries stored out near the end of the PV actually _should_ be overwritten.
. A practical note: if you do this, design things such that you always maintain a best move AND a best reply without relying on the TT. The best reply is important because you always want something to ponder. 
. It sounds like the ideal would be: