Full Principal Variation Retrieval

[bob]

Code: Select all

    Crafty-23.4-2        2676    3    3 30000   66%  2552   22% 
    Crafty-23.4-1        2673    3    3 30000   66%  2552   22% 
    Crafty-23.4R02-1     2669    3    3 30000   65%  2552   22% 
    Crafty-23.3-1        2667    3    3 30000   65%  2552   22% 
    Crafty-23.3-2        2666    3    3 30000   65%  2552   22% 
    Crafty-23.2-1        2614    3    3 30000   58%  2552   22% 

So a measurable drop, although not a huge one. If you look at the BayesElo output, it essentially costs about 1 game out of every 100 played in this particular test. WIn percentage dropped from 66 to 65

[michiguel]

Code: Select all

    Crafty-23.4-2        2676    3    3 30000   66%  2552   22% 
    Crafty-23.4-1        2673    3    3 30000   66%  2552   22% 
    Crafty-23.4R02-1     2669    3    3 30000   65%  2552   22% 
    Crafty-23.3-1        2667    3    3 30000   65%  2552   22% 
    Crafty-23.3-2        2666    3    3 30000   65%  2552   22% 
    Crafty-23.2-1        2614    3    3 30000   58%  2552   22% 

So a measurable drop, although not a huge one. If you look at the BayesElo output, it essentially costs about 1 game out of every 100 played in this particular test. WIn percentage dropped from 66 to 65

Difference from Crafty-23.4-2 and Crafty-23.4-1 (same versions) is 3 elo points and between Crafty-23.4-1 and Crafty-23.4R02-1 is 4 elo points. That is an indication that the difference is too close to the noise. 66% to 65% is clearly rounded because 1% at that level is much more than 4 elo points. One must have rounded upwards, and the other downwards.

Miguel

[bob]

Code: Select all

    Crafty-23.4-2        2676    3    3 30000   66%  2552   22% 
    Crafty-23.4-1        2673    3    3 30000   66%  2552   22% 
    Crafty-23.4R02-1     2669    3    3 30000   65%  2552   22% 
    Crafty-23.3-1        2667    3    3 30000   65%  2552   22% 
    Crafty-23.3-2        2666    3    3 30000   65%  2552   22% 
    Crafty-23.2-1        2614    3    3 30000   58%  2552   22% 

So a measurable drop, although not a huge one. If you look at the BayesElo output, it essentially costs about 1 game out of every 100 played in this particular test. WIn percentage dropped from 66 to 65

Difference from Crafty-23.4-2 and Crafty-23.4-1 (same versions) is 3 elo points and between Crafty-23.4-1 and Crafty-23.4R02-1 is 4 elo points. That is an indication that the difference is too close to the noise. 66% to 65% is clearly rounded because 1% at that level is much more than 4 elo points. One must have rounded upwards, and the other downwards.

Miguel

Code: Select all

    Crafty-23.4-2        2676    3    3 30000   66%  2552   22% 
    Crafty-23.4-1        2673    3    3 30000   66%  2552   22% 
    Crafty-23.4R02-1     2669    3    3 30000   65%  2552   22% 
    Crafty-23.4R02-2     2667    3    3 30000   65%  2552   22% 
    Crafty-23.3-1        2668    3    3 30000   65%  2552   22% 
    Crafty-23.3-2        2666    3    3 30000   65%  2552   22% 

This doesn't look like "noise" to me. This is simply a small loss in Elo. As far as the rounding goes, so what? the difference between 66.0 and 65.4 is what? What about 66.4 to 65.4? So there is at least a half-percent difference, if not more.

I can run a match to drive the error down to +/- 1 if you aren't convinced, but the two runs are pretty much worse by 5 Elo or so.

[hgm]

This might be worse than expected. Crafty-23.4R02 is Crafty-23.4 with HashProbe() modified to return "miss" if it gets an EXACT hit, and the value of alpha is < beta - 1 (both are passed in from the current search). Here's the partial results so far:

This is a worse lobotomy than is needed to get complete PVs. When the hit is EXACT, but <= alpha or >= beta, even if the window was open, you can safely take the fail low or fail high, because node is then no longer on any PV.

In other words, you should judge if the node is PV after the hash cutoff, not before.

Still, I think there could be a performance hit: even though you would get hits on all non-PV side branches in the next move, making the overhead quite small, there remans an important effect on the PV itself: You suppress any form of grafting. Because you will search the PV, you will always get a score for it at the requested depth, even if deeper data was available in the hash.

[bob]

This might be worse than expected. Crafty-23.4R02 is Crafty-23.4 with HashProbe() modified to return "miss" if it gets an EXACT hit, and the value of alpha is < beta - 1 (both are passed in from the current search). Here's the partial results so far:

This is a worse lobotomy than is needed to get complete PVs. When the hit is EXACT, but <= alpha or >= beta, even if the window was open, you can safely take the fail low or fail high, because node is then no longer on any PV.

That is exactly what I did. This is only activated when type==EXACT, and score > alpha _and_ < beta. I wanted to not allow a hash termination on a potential PV pathway.

In other words, you should judge if the node is PV after the hash cutoff, not before.

See above. If the retrieved score is "in the window" it still saves the hash move, but then returns "miss". If the exact score is <= alpha or >= beta, it returns that score which is tested to see if it will cause a cutoff...

BTW, I rewrote the hashing stuff recently, so showing the code won't make any sense if compared to 23.3. The current hashing code is cleaner and the way it interfaces with Search() is more sensible. I do not like the idea of looking up an entry, then having other places look at the hash entry to see if it should be tested for tt-singular and such. All of the accessing of pieces of the entry are now done in HashProbe() which is a much better structure by classic object-oriented programming standards. And it did make this change trivial to implement. If I return "HIT" then the value is tested in search, as expected. If I return "MISS" the value is ignored.

Still, I think there could be a performance hit: even though you would get hits on all non-PV side branches in the next move, making the overhead quite small, there remans an important effect on the PV itself: You suppress any form of grafting. Because you will search the PV, you will always get a score for it at the requested depth, even if deeper data was available in the hash.

The idea just seems wrong. We are going to get funny PVs because of grafting, or we lose the benefit of EXACT entries along PV nodes. One hurts performance, one hurts aesthetics.

[hgm]

It might be what you did, but it was not what you WROTE...

I agree with your conclusion. But I still think you could have 'the best of both Worlds' when storing the PV of PV nodes in the hash table in the way I described.

[bob]

It might be what you did, but it was not what you WROTE...

I agree with your conclusion. But I still think you could have 'the best of both Worlds' when storing the PV of PV nodes in the hash table in the way I described.

I probably didn't write it very clearly, I agree. I will go back to look and see.

Yes, storing the PV for those non-fail nodes sounds like an idea. I might try a quick trick later to test that. My quick idea is to take the 64 bit signature, squash it to something relatively small (say 16 bits) and use that as an index into a PV-holder. Doesn't change the length of the hash entry at all, only question is how significant will the collision rate be? with 65536 entries, and not very many true PV nodes, it might work. I am going to add a statistical measurement in Crafty to see how many times I would actually store one of these PV entries and compute a nodes per store average to get an idea of potential collisions...

More on this later. Fortunately it is simple, or I wouldn't bother since the effect will be nil on strength, but nice for debugging and seeing the real PV...

[Mincho Georgiev]

I tried couple of different schemes, none of them was satisfactory. So here is what I did lately. I am using triangular array as well as TT. If the PV in the array is shorter on plies than the current depth, only then the pv is extracted from the transposition table. This doesn't eliminate the ridiculous mate pv problem, but when I have a real pv in the array, it gets printed, when I don't (i.e. immediate tt cut-off for example), still have something to display. I doubt someone will like this particular scheme, but it's ok for me at this time.

The simplest solution it not to cut with a hash hit at PV nodes. I doubt there is a measurable performance penalty (they are cut at the next node) and you always have complete PVs. At least, this should be an option when the engine is used for analysis. Having complete PVs for analysis is a MUST. However, I keep saying this, programmers seem to not care, or forget, what a chess player needs.

Miguel

I don't know for others, but for me it gave -3 ELO pts. It was tempting though, but I didn't like the tiny ELO drop.
p.s. I saw the Bob's results after posting the last line, so it makes sense to me.

[bob]

I tried couple of different schemes, none of them was satisfactory. So here is what I did lately. I am using triangular array as well as TT. If the PV in the array is shorter on plies than the current depth, only then the pv is extracted from the transposition table. This doesn't eliminate the ridiculous mate pv problem, but when I have a real pv in the array, it gets printed, when I don't (i.e. immediate tt cut-off for example), still have something to display. I doubt someone will like this particular scheme, but it's ok for me at this time.

The simplest solution it not to cut with a hash hit at PV nodes. I doubt there is a measurable performance penalty (they are cut at the next node) and you always have complete PVs. At least, this should be an option when the engine is used for analysis. Having complete PVs for analysis is a MUST. However, I keep saying this, programmers seem to not care, or forget, what a chess player needs.

Miguel

I don't know for others, but for me it gave -3 ELO pts. It was tempting though, but I didn't like the tiny ELO drop.
p.s. I saw the Bob's results after posting the last line, so it makes sense to me.

We are in the same ballpark. My results were pretty close to your -3, when you factor in the +/-3 error bar on my numbers. This is just an idea I don't like and am not going to use. It makes no sense to go to all the trouble to maintain a hash table, then ignore the most valuable entries of all, just because you are on a PV.

I'm now interested in the "hash the PV" idea using the approach I mentioned in another part of this thread, to see what happens.

[Mincho Georgiev]

I am in a serious hardware trouble, so your results on this will be much appreciated!