Confused About Triangular PV Table

[mvanthoor]

And, just like scores, PVs propagate to towards the root. According to the rule that a node's PV is the PV of its best child, prefixed by the best move (which leads to that child).

Because of that rule, I prefer to store the PV exactly in that way, as described in my post:

pv.clear();
pv.push(best_move);
pv.append(node_pv);

This way, the PV is kept almost automatically. it saves me writing a function to copy PV's manually from one array row to another. (And wasting half the array's storage capacity.)

[hgm]

I prevent wasting that space by putting all PVs on a stack (a 1-dimensional array of moves).

It is nice to hide the copying like you do, but just writing it out in plain code is hardly scary:
pv.clear: int myPV = pvPtr; pv[pvPtr++] = 0;
pv.push: int p = pvPtr; pvPtr = myPV; pv[pvPtr++] = best_move;
pv.append: while((pv[pvPtr++] = pv[p++])) {}

[lithander]

And, just like scores, PVs propagate to towards the root. According to the rule that a node's PV is the PV of its best child, prefixed by the best move (which leads to that child).

The PV at the root should always match the reported score, right? If I play each move of the PV starting from the root then I will get a leaf node that evaluates to the same score that propagated to the root, correct?

With a triangular PV table I was always able to maintain such a complete PV. But now I'm trying to implement a Transposition table and I have the problem that when I have a table hit I get a "score" but I don't save the PV in my TT table (and don't think I should) so the PV always ends when I find a position in the table.

How do you fix that and report a correct and complete PV to the GUI? I don't see how the "pv.append" code both of you posted would help with these incomplete PVs whenever you have a table hit. Even if you store one move in the TT you don't have a complete PV but just the first step.

Marcel suggested that "if you want to send a PV to the GUI, you would need to get the PV-move in the position, play it, get the PV-move in THAT position, play it.... until you get no more move."

Is that really the solution? Does it always work? (One of the entries in that path could have been overwritten andlost)

[Pio]

And, just like scores, PVs propagate to towards the root. According to the rule that a node's PV is the PV of its best child, prefixed by the best move (which leads to that child).

The PV at the root should always match the reported score, right? If I play each move of the PV starting from the root then I will get a leaf node that evaluates to the score that propagated to the root, correct?

With a triangular PV table I was always able to maintain such a complete PV. But now I'm trying to implement a Transposition table and I have the problem that when I have a table hit I get a "score" but I don't save the PV in my TT table (and don't think I should) so the PV always ends when I find a position in the table.

How do you fix that and report a correct and complete PV to the GUI? I don't see how the "pv.append" code both of you posted would help with these incomplete PVs whenever you have a table hit. Even if you store one move in the TT you don't have a complete PV but just the first step.

If you want to extract the PV from the TT, you access the root position’s move in the TT, then create a new position by applying the move to the root’s position, look up the newly created position and do the same all over (but of course the root will become the latest created position) until you cannot find more positions in the TT or until you reach the same position three times since you don’t want infinite PV. The problem with this method is that the PV nodes might be overwritten in the TT. In that case you will not get a complete PV but a truncated one.

[hgm]

Without TT the root score should be the eval of the leave at the end of the PV. (If you make sure the PV contains all QS plies as well.)

The TT can clip the tail of a PV, (obtained through the triangular-array method), when a node along it was taken from the hash table, rather than searched. For this reason some engines do not allow hash cuts in PV nodes. This also prevents the beneficial effect of 'grafting', though, where you get a hit on a TT entry that was search deeper than you need. (So that you effectively boost the depth of the search.)

[mvanthoor]

Marcel suggested that "if you want to send a PV to the GUI, you would need to get the PV-move in the position, play it, get the PV-move in THAT position, play it.... until you get no more move."

Is that really the solution? Does it always work? (One of the entries in that path could have been overwritten andlost)

It does work, but doesn't fix PV's being cut off. If a PV-node was overwritten, you lose that, and the part after it.

Pio actually suggests the same thing I did.

The TT can clip the tail of a PV, (obtained through the triangular-array method), when a node along it was taken from the hash table, rather than searched. For this reason some engines do not allow hash cuts in PV nodes.

This.

The PV gets cut off because the engine cuts the alpha/beta function using a value from the TT, when in a PV-node. Yesterday in the PM I said: "If you have PVS, there's a formula with which you can calculate if you're in a PV node." If you're in a PV node, you don't cut in that node. This will cost a few Elo points, but it will solve the problem of PV's being cut off. Rustic has this problem of (cosmetically) shorterend PV's. I'll likely fix it in the upcoming version by not cutting in PV-nodes.

[hgm]

You don't need PVS for that. A node is a PV node when the score is between alpha and beta. So you can only take a hash cutoff when the score you find in the TT is >= beta or <= alpha (and bound type is OK and depth sufficient).

Many authors would prefer the Elo over an unclipped PV.

You can try to retrieve the missing part (or the entire) PV from the TT, by probing for the position, following the move, and recursively repeating that. Usually the final moves will no longer be in the TT, and there is no guarantee that you will actually find the PV that the score was based on (because that could have been replaced by another one after it was overwritten, and then searched again).

Crafty solved the problem once and for all by storing the entire PV in the TT entry for a PV node. Normal TT entries of course do not have enough space to do that, so he used a separate TT used only for PV nodes, which a much larger entry. Only a very small fraction of the tree is TT nodes, so you can afford that. If you get a hash cutoff on a PV node you can then retrieve the PV from the table, and return it with that hash cutoff just like it had been found by search (and then stored in the TT).

[lithander]

Many authors would prefer the Elo over an unclipped PV.

For some reason I assumed that returning the full PV was required. If clipping is a best practice than I'm perfectly okay with that. I now clear my triangular table at the depth where I find a hash entry and the warnings by Cute Chess are gone, nothing broke, the ELO remained the same.

Thanks@all!

[emadsen]

Marcel suggested that "if you want to send a PV to the GUI, you would need to get the PV-move in the position, play it, get the PV-move in THAT position, play it.... until you get no more move."

Is that really the solution? Does it always work? (One of the entries in that path could have been overwritten andlost)

That's what MadChess does in UCI_AnalyseMode. When playing a game, MadChess immediately returns a score, which truncates the PV.

Returning a score or the "not cached" score is based on a boolean variable, TruncatePrincipalVariation.

Code: Select all

private int GetCachedScore(ulong CachedPositionData, int Depth, int Horizon, int Alpha, int Beta)
{
    //...
    switch (scorePrecision)
    {
        case ScorePrecision.Exact:
            if (score <= Alpha) return Alpha; // Score fails low.
            if (score >= Beta) return Beta; // Score fails high.
            // If necessary, avoid truncating the principal variation by returning a cached score.
            return TruncatePrincipalVariation ? score : StaticScore.NotCached;
        case ScorePrecision.UpperBound:
            //...
        case ScorePrecision.LowerBound:
            //...
    }
    return StaticScore.NotCached;
}

The CachedPositionData method parameter has a BestMove to guide the search. The net effect is PVs are returned when analyzing in a GUI, PVs are truncated when watching a game in a GUI.

The TruncatePrincipalVariation boolean is set in response to toggling analysis mode. Similarly, the number of repetitions considered a draw is adjusted.

Code: Select all

private void SetOption(List<string> Tokens)
{
    var optionName = Tokens[2];
    var optionValue = Tokens.Count > 4 ? Tokens[4] : string.Empty;
    switch (optionName.ToLower())
    {
        //...
        case "uci_analysemode":
        case "analyze":
            var analysisMode = optionValue.Equals("true", StringComparison.OrdinalIgnoreCase);
            if (analysisMode)
            {
                _search.TruncatePrincipalVariation = false;
                _evaluation.DrawMoves = 3;
            }
            else
            {
                _search.TruncatePrincipalVariation = true;
                _evaluation.DrawMoves = 2;
            }
            break;
        //...
        default:
            WriteMessageLine(optionName + " option not supported.");
            break;
    }
}