Full Principal Variation Retrieval

[snowman]

I'm working on getting full PV after the search but I couldn't come up with a solution which
1) guarantees to work and
2) doesn't harm the performance (speed)

For example, using Transposition Table (TT) doesn't always work, or a trick in SF preventing TT cut-off at PV nodes does harm performance. Although full PV is not compulsory (to be playable), I feel something wrong not getting it properly.

Many thanks for your help!

[rbarreira]

How much performance did you lose with the most trivial method of recording the PV?

I mean this one:

http://web.archive.org/web/200404270138 ... ing/pv.htm

It seems to me that this method should perform really well...

[snowman]

Hi Ricardo, I tried that method. It works well with very small overhead. However, when used with TT, we cannot simply return score when a node is stored in TT because we also need PV. Moreover, things like nullmove, lmr, etc make it more complicated.

[bob]

Hi Ricardo, I tried that method. It works well with very small overhead. However, when used with TT, we cannot simply return score when a node is stored in TT because we also need PV. Moreover, things like nullmove, lmr, etc make it more complicated.

You are probably going to have to give up on the perfect-PV idea. The PV array is the best solution, although EXACT hash hits will cause shortened PVs. You can recover some of the PV beyond a hash hit if you want...

When you back a PV up to the root and display it, you make each move, one at a time and then output them. When you reach the end of the PV, and make/display the last move, you can do another probe into the hash table. If you get a "best move" you can add it to the PV. Far from perfect, but you do get more information.

The perfect solution is to store a best PV rather than a best move in the hash table. Then you have the PV below the hash entry as well as the best move. Down-side is the entry is going to become huge, which will hurt performance and reduce the number of entries you can store by a large degree...

[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.

[jwes]

Hi Ricardo, I tried that method. It works well with very small overhead. However, when used with TT, we cannot simply return score when a node is stored in TT because we also need PV. Moreover, things like nullmove, lmr, etc make it more complicated.

You are probably going to have to give up on the perfect-PV idea. The PV array is the best solution, although EXACT hash hits will cause shortened PVs. You can recover some of the PV beyond a hash hit if you want...

When you back a PV up to the root and display it, you make each move, one at a time and then output them. When you reach the end of the PV, and make/display the last move, you can do another probe into the hash table. If you get a "best move" you can add it to the PV. Far from perfect, but you do get more information.

The perfect solution is to store a best PV rather than a best move in the hash table. Then you have the PV below the hash entry as well as the best move. Down-side is the entry is going to become huge, which will hurt performance and reduce the number of entries you can store by a large degree...

You can do better by storing a pointer to the pv in exact nodes. Since exact nodes are a tiny fraction of nodes, this will keep memory use reasonable but may give memory management problems.

[hgm]

You can do better by storing a pointer to the pv in exact nodes. Since exact nodes are a tiny fraction of nodes, this will keep memory use reasonable but may give memory management problems.

Indeed, I was considering something like this. (Did not have time to try it yet). If wanted to requisition a neighboring TT entry for this. If you have buckets of four (Some of my engines even use buckets of 6 or 7), you can easily afford to make exact entries double size, if only 0.1% or so is an exact entry. There would still be plenty of room to store other important (= deep) entries.

E.g. with four 16-byte slots per bucket, you could define two pairs, and always put exact entries in the left entry of the pair. The 'exact' flag in that entry would thus indicate if the partner slot is an independent entry, for which we should compare the lock, or if it is an extension containing only PV. You could trivially store 8 PV moves in there, and if you are smart, you can pack moves in a single byte, and store 16 moves (in addition to the normal hash move, which is in the primary entry).

Packing hardly takes any time, since you would use the packed format in the PV array as well. So you would be copying packed moves to update it, and only the move from the current node would have to be packed.

Being able to look 16 moves beyond a hash hit would solve most problems with truncated PVs, and the performance impact should be close to zero.

[michiguel]

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

[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

Since I do not recall having tested this, I just queued up a test run that ignores EXACT hash hits when alpha < beta - 1. Be interesting to see if there is no benefit. I know this hurts in endgames, but I don't know how much, precisely.

[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

Since I do not recall having tested this, I just queued up a test run that ignores EXACT hash hits when alpha < beta - 1. Be interesting to see if there is no benefit. I know this hurts in endgames, but I don't know how much, precisely.

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:

Code: Select all

   Crafty-23.4-2        2680    3    3 30000   66%  2557   22% 
   Crafty-23.4-1        2678    3    3 30000   66%  2557   22% 
   Crafty-23.3-1        2672    3    3 30000   65%  2557   22% 
   Crafty-23.3-2        2670    3    3 30000   65%  2557   22% 
   Crafty-23.4R02       2669    7    7  7814   65%  2553   23% 
   Crafty-23.2-1        2618    3    3 30000   58%  2557   22% 
   Crafty-23.2-2        2618    3    3 30000   58%  2557   22% 

So down -11 Elo at the moment, with +/- 7 error. Whether it will close near the end is speculation, but I'd suspect not. As always, the -1 and -2 runs are the same version, just a repeated 30K test match to test for consistency. I run those and save the PGN so that I can simply add new results without re-running those old matches.