multi-pv analysis

[Greg Strong]

I just added multi-pv for the first time. Implementation seemed pretty simple. My primary goal here is to use multi-pv analysis to build openings books.

So, everything seems to work fine, except that, for some moves, my PV is truncated to only a single move. I assume this is due to a TT hit. The fact that the PV is truncated doesn't really bother me for this purpose, but does that also mean that the evaluation isn't exact? And, if so, is there anything to be done about this (short of disabling TT entirely)?

[Ferdy]

I just added multi-pv for the first time. Implementation seemed pretty simple. My primary goal here is to use multi-pv analysis to build openings books.

So, everything seems to work fine, except that, for some moves, my PV is truncated to only a single move. I assume this is due to a TT hit. The fact that the PV is truncated doesn't really bother me for this purpose, but does that also mean that the evaluation isn't exact? And, if so, is there anything to be done about this (short of disabling TT entirely)?

A single move pv line is fine if there are no other legal moves to show, if there is, it is better to show the pv line (more than 1 move) that it considers best. Disabling the TT may weaken the engine's strength thereby not producing its best pv lines.

My multi-pv implementation guarantees me a pv of more than one move, say multi-pv 2.

Code: Select all

1. Search the position at iteration depth n (starts at 1) and find the bestmove and pv line
2. Search the position again at same iteration depth in (1) and find the best move and pv line and don't search the best move in (1) at the root
3. Increment iteration depth by 1 and follow (1) and (2)

[Greg Strong]

Thanks, Ferdinand, but I think I may have been misunderstood. If I search multi-pv of 8, for example, I do get 8 different moves - it is just that, for some of them, it will show a nice long PV. For others, the PV will just show the one move and nothing else. My guess is that it is hitting an 'exact' match with sufficient draft in the TT and then cutting off. Which is fine, so long as the evaluation it returns is exact, but I am in doubt about whether it is.

My goal is to study the openings for chess variants where the openings are not well understood. I'd like to start at the opening position of, for example, Grand Chess, run the search with multi-PV of 8, and see what the best 8 openings moves are, and - more importantly - what is the difference in evaluation between them.

P.S. I think what I am doing is exactly what you describe.

P.P.S. Maybe I should disable the TT at PV nodes only?

[Ferdy]

P.P.S. Maybe I should disable the TT at PV nodes only?

Right I don't return values but just use the pv move for move ordering in pv nodes.

[hgm]

Funny, I have been busy the past weeks doing exactly what you aim to do here: developing opening theory (for Tenjiku Shogi). I also implemented multi-PV for that purpose. Like you said, implementation is rather trivial: when I print a new PV, I just set alpha to bestScore - margin, where 'margin' is the option through which I control multi-PV. The only other change it requires is that I have to set bestScore = max(score, bestScore) after every move, while before I was only doing that when alpha increased (as the guarantee alpha >= bestScore existed when margin = 0).

As to the shortened PVs: if your TT is implemented correctly, they should be exact hits. A bound could never cut a PV move. There is only one good solution to this: store the PV of exact nodes in a hash table. As the fraction of exact nodes is extremely small, you can do with a quite small table here. Just store a 4-byte signature and fifteen 4-byte moves, with always-replace. If you take a hash-cut in a PV node (i.e. alpha < score < beta), you just copy the PV from that hash table (if there) and return it like you would when the node had actually searched.

[hgm]

Something off-topic:

I patched up the move notation issue that existed in the WinBoard Alien Edition for variants with more than 26 pieces. Now that I am using it for my Tenjiku engine it became a real annoyance that it could not read bits own saved games.

I used a relatively simple hack to cure that: instead of having disambiguation work by internal piece type (i.e. converting the piece ID in the move to an internal type, and then looking which of the generated legal moves match that type and the given square coordinates) I use the piece ID to see if a move matches. This allows different types to use the same ID. So both Gold and Great General can use G as ID; if they can both go to the same square, a coordinate disambiguator is added to make the distinction, just like when two Golds could move to the same square.

The advantage is that the moves don't look as ugly as when using L' or L! disambiguate piece type, and that it was very easy to implement. And that you can always use the obvious abbreviation, and don't have to resort to second or third letters of the name. A disadvantage is that it doesn't work in FEN.

Nevertheless I am inclined to consider this a valid form of SAN, i.e. in notation systems that use two-letter or letter + punctuation piece names, always allow use of the first letter only if the following coordinates are enough to uniquely identify the move. I.e. consider the second (or later) characters of the piece ID just as optional as the from-square, and allow disambiguation both through from-square coordinates or by supplying the remaining characters of the piece name. On writing you will of course have to pick a method, but on reading it would be good to understand both.

[cdani]

Thanks, Ferdinand, but I think I may have been misunderstood. If I search multi-pv of 8, for example, I do get 8 different moves - it is just that, for some of them, it will show a nice long PV. For others, the PV will just show the one move and nothing else. My guess is that it is hitting an 'exact' match with sufficient draft in the TT and then cutting off. Which is fine, so long as the evaluation it returns is exact, but I am in doubt about whether it is.?

I have an option in Andscacs that enables retrieving the pv from hash table (doing every move and fetching next one), thus avoiding short pvs.

[hgm]

But the problem with that is that the PV is often complete bogus, not at all related to the score that the moves gives.

[cdani]

But the problem with that is that the PV is often complete bogus, not at all related to the score that the moves gives.

Yes, but can also be done only when the standard pv is not long enough, and only in analysis or infinite mode.

[hgm]

But the part you add is still bogus.

So the question is really whether it is better to leave the PV short, so that you know what you don't know, or add stuff that very often is random garbage to make it look long, leaving the user completely in the dark which parts of the PV he can trust, and where the nonsense starts. I know what I would prefer...

Of course you won't have that problem when you hash PVs. They will virtually never be truncated, and always lead to the leaf from which the evaluation came.