How to collect PV?

[benvining]

I'm working on implementing PV collection during search so that it can be printed in the info output. This is turning out to be a bit tricky to get right: trying to extract it from the transposition table usually results in a too-short PV, and trying to collect it during the search is tricky because you'll get the deepest plies first. Do folks usually collect it during search and reverse the moves array? Am I overthinking this?

[Aleks Peshkov]

https://www.chessprogramming.org/Triangular_PV-Table
It is important to know that principal variation is not a list of moves, but different lists of moves for each depth ply during search.

[benvining]

Thanks for the info. I'm looking into the triangular table idea.

[Aleks Peshkov]

https://web.archive.org/web/20040620092 ... ing/pv.htm
An alternative data representation of triangular array idea.
Disadvantages:
- Harder to debug.
- Spreads code snippets in several places of the most complex chess code: in the body of search function;
- Needs more stack memory (important only if code portability is an issue);
- Less efficient in garbage collecting languages (minor issue);

[hgm]

This does seem a variation on the triangular array, where you allocate each row of it as part of the local variables of the search routine. In my engines I use a separate stack for the PV, which basically packs the used part of each row of the triangular array in a linear array. This can be done because rows never change unless all later rows (except the one you copy) have become invalid and can be discarded.

Problem with the triangular array is that a hash cutoff in the PV will shorten it. You can try to dig the rest out of the TT, but that is a pretty unreliable process. Often the position at the end of such a PV has an evaluation different from the one reported by the search.

[Aleks Peshkov]

In my engines I use a separate stack for the PV, which basically packs the used part of each row of the triangular array in a linear array. This can be done because rows never change unless all later rows (except the one you copy) have become invalid and can be discarded.

I wanted to implement the same but it was difficult and dismissed the idea. I enjoy such kind of clever optimisations.

Problem with the triangular array is that a hash cutoff in the PV will shorten it. You can try to dig the rest out of the TT, but that is a pretty unreliable process. Often the position at the end of such a PV has an evaluation different from the one reported by the search.

IMany strong engines including Stockfish do not cutoff from TT for PV nodes. It makes PV as reliable as without TT.

[benvining]

https://web.archive.org/web/20040620092 ... ing/pv.htm
An alternative data representation of triangular array idea.
Disadvantages:
- Harder to debug.
- Spreads code snippets in several places of the most complex chess code: in the body of search function;
- Needs more stack memory (important only if code portability is an issue);
- Less efficient in garbage collecting languages (minor issue);

I tried this first, because it seemed to be easier, and it does correctly print the first few moves of the pv but it will sometimes include illegal moves. I must've written a bug somewhere, but I'm not quite sure how to debug it. It seems that the triangular table would be potentially more efficient anyway, at least in regard to stack memory usage ¯\_(ツ)_/¯

If anyone cares to take a quick look at my implementation attempt, it's here: https://github.com/benthevining/BenBot/ ... Search.cpp

I get output such as this from fastchess when running an SPRT:

Code: Select all

Started game 9 of 100 (Refactor vs Baseline)
Warning; Illegal pv move h6h5 from Refactor
Info; info depth 3 score mate -2 time 6 hashfull 0 nodes 3714 nps 619000 tbhits 0 pv b6b1 e4b1 h5h4 c7h7 h6h5
Position; startpos
Moves; d2d4 d7d6 c2c4 e7e5 d4d5 f7f5 e2e4 f5e4 b1c3 g8f6 g1e2 c8f5 e2g3 f5g6 c1g5 b8d7 d1a4 e8f7 g3e4 f7g8 f1d3 g6e4 c3e4 d7b6 g5f6 b6a4 f6d8 a4b2 d3f1 a8d8 a1b1 b2c4 f1c4 d8b8 c4a6 b7b6 b1c1 c7c5 d5c6 d6d5 c6c7 b8e8 c7c8q e8c8 c1c8 h7h6 e4c3 d5d4 c3d5 g8f7 a6c4 b6b5 c4b3 f7g6 e1g1 g6h7 f1e1 f8d6 b3c2 g7g6 c2g6 h7g7 g6e8 h8f8 e1c1 d4d3 c1c3 e5e4 e8b5 d3d2 d5e3 d6h2 g1h2 f8f2 b5c6 f2f4 h2g1 d2d1q e3d1 a7a6 d1e3 h6h5 c3c4 f4f6 c6e4 f6b6 c4c7 g7h6 c8g8 

[Aleks Peshkov]

Code: Select all

    void set(Ply ply, UciMove move) {
        pv[ply][0] = move;
        auto target = &pv[ply][1];
        auto source = &pv[ply+1][0];
        while ((*target++ = *source++));
        pv[ply+1][0] = {};
    }

Without last line of code I also had garbage.
And this:

Code: Select all

set(ply, UciMove{});

is needed for me right after each makeMove()

May be the first place is redundant (second is sure necessary) but I am not going to test it.

[flok]

Why not skip the pv-recording and reproduce it from the TT?

[Aleks Peshkov]

TT usually does not keep full PV. Lower depth PV entries will be overwritten because their low depth.
In my engine I do not use TT in QS but I can collect full PV till the static eval of final position.