My troubles with MultiPV and Syzygy in Stockfish 7

Discussion of anything and everything relating to chess playing software and machines.

Moderator: Ras

syzygy
Posts: 5774
Joined: Tue Feb 28, 2012 11:56 pm

Re: My troubles with MultiPV and Syzygy in Stockfish 7

Post by syzygy »

hgm wrote:
syzygy wrote:Suppose you have three moves leading to positions with DTZ=110 ply, DTZ=120 ply and DTZ=140 ply. Why should the engine consider playing anything else than the move leading to DTZ=110?
Why should an engine consider a move that gets it mated in 3 while it has one that keepsit a Pawn up? Because the user asks it to, obviously...
???

I asked a different question.

And I gave you the answer.

If you don't think it makes sense, think again.

If you don't have a good idea of what you're talking about (which the rest of your post confirms), well, then I will stop wasting my time. You're making all kinds of assumptions that are all false and I'm not here to educate you.
jdart
Posts: 4408
Joined: Fri Mar 10, 2006 5:23 am
Location: http://www.arasanchess.org

Re: My troubles with MultiPV and Syzygy in Stockfish 7

Post by jdart »

The problem is, with Syzygy, you don't get evals in the customary sense. All chess engines usually report scores that are based on distance to mate. With Syzygy you don't have that. You can sort the winning/drawing moves on DTZ. But if there are also losing moves, what is their score, if the search was cut off with a TB hit?

--Jon
User avatar
hgm
Posts: 28395
Joined: Fri Mar 10, 2006 10:06 am
Location: Amsterdam
Full name: H G Muller

Re: My troubles with MultiPV and Syzygy in Stockfish 7

Post by hgm »

syzygy wrote:I asked a different question.
Not really. In multi-PV the user asks for moves that the engine would never want to play, and to be compliant you have to give them. Whether it is a move that makes no progress or gets you mated.
If you don't have a good idea of what you're talking about (which the rest of your post confirms), well, then I will stop wasting my time. You're making all kinds of assumptions that are all false and I'm not here to educate you.
Perhaps you should shake your head to get your brain back right-side-up, because you seem to have things in reverse. No one forces you to come here. If you don't have anything sensible to say, you can just stay away, and you don't have to announce that. No one is interested in your personal policies as to saying sensible things. That is just spamming this thread, and wasting everybody else's time...
User avatar
hgm
Posts: 28395
Joined: Fri Mar 10, 2006 10:06 am
Location: Amsterdam
Full name: H G Muller

Re: My troubles with MultiPV and Syzygy in Stockfish 7

Post by hgm »

jdart wrote:The problem is, with Syzygy, you don't get evals in the customary sense. All chess engines usually report scores that are based on distance to mate. With Syzygy you don't have that. You can sort the winning/drawing moves on DTZ. But if there are also losing moves, what is their score, if the search was cut off with a TB hit?
Negative DTZ, of course. That isn't really different from DTM. There you also can have losing moves. You sort the winning moves on 32000-DTM, the losing moves on -32000+DTM, and the drawing move get either score 0 or (in swindle mode) the score from a search.

The only difference with DTZ is that the latter only tells part of the story, progress within the current EGT (or P-slice), and tacitly implies that any (winning) transition to a successor EGT is progress too. So it is always better to be in KBBK then in KBBKN. Even if DTZ in the latter was 7 (ply), and you go to DTZ = 32 in the former, it is considered a good deal. Normally this is implemented by assigning scores like 14000-DTZ to KBBKN and then 15000-DTZ (or 14100-DTZ) in KBBK. (Where mate scores would be 30000-DTM.) So each EGT has its own offset to indicate its position in the sequence of EGTs that you have to pass through to force mate (as the transitions are irreversible moves you can always order them to that effect), and the DTZ recorded in them is just a fine-tuning of that major score.

I don't see a reason why an engine could not print +141.23 for a "tablebase win in an unknown number of moves, but at most 23 ply to progress in the form of a capture or Pawn push". In fact I have seen many engines that print such scores, when they derive them from recognizers that are not accurate enough to predict the DTM.

One (basically unrelated) problem is that DTZ-guided play sucks in the eyes of most Chess players, as KQBBKN would be ordered behind KBBKN in the normal conversion ordering, so that it considers sacrifycing the Queen as progress. And usually forcing the opponent to capture the Queen can be done faster than gaining the Knight. So DTZ is inferior information, chosen as a compromise between compressibility and quality.

You can try to remedy that by having the engine not blindly follow the DTZ info, (i.e. cutting off on an EGT hit, taking the DTZ value for gospel), but continue searching deeper if it still indicates a win, in the hope you will find a "better win". Which will obviously not exist in the DTZ sense, but will exist in the eyes of the average Chess player, who would rather see conversion from KQBBKN to KQBBK in 15 ply then to KBBKN in 6. By searching the full 15 ply even when every node in the tree hits KQBBKN, and using the EGT-derived score only in the leaves you could see that. But of course it only would have the desired effect if the scores then also would be better in KQBBK then in KBBKN.

This can be easily achieved, though, by assigning the DTZ offsets for every EGT such that they mainly reflect decrease of opponent material. Both KQBBK and KBBKN wins are worse than KBBK (because they can convert to the latter), but you could make KBBKN far worse, and KQBBK only slightly worse (but still more worse than could be made up for by any DTZ difference). So that it would always prefer converting to KQBBK over converting to KBBKN if it sees a possibility for both. And it would only prefer converting to KBBK from KQBBK if it cannot see the mate in KQBBK (which usually is just 2 or 4 ply behind a forced Q sac). That would prevent most frowning by users.
petero2
Posts: 729
Joined: Mon Apr 19, 2010 7:07 pm
Location: Sweden
Full name: Peter Osterlund

Re: My troubles with MultiPV and Syzygy in Stockfish 7

Post by petero2 »

hgm wrote:
jdart wrote:The problem is, with Syzygy, you don't get evals in the customary sense. All chess engines usually report scores that are based on distance to mate. With Syzygy you don't have that. You can sort the winning/drawing moves on DTZ. But if there are also losing moves, what is their score, if the search was cut off with a TB hit?
Negative DTZ, of course. That isn't really different from DTM. There you also can have losing moves. You sort the winning moves on 32000-DTM, the losing moves on -32000+DTM, and the drawing move get either score 0 or (in swindle mode) the score from a search.

The only difference with DTZ is that the latter only tells part of the story, progress within the current EGT (or P-slice), and tacitly implies that any (winning) transition to a successor EGT is progress too. So it is always better to be in KBBK then in KBBKN. Even if DTZ in the latter was 7 (ply), and you go to DTZ = 32 in the former, it is considered a good deal. Normally this is implemented by assigning scores like 14000-DTZ to KBBKN and then 15000-DTZ (or 14100-DTZ) in KBBK. (Where mate scores would be 30000-DTM.) So each EGT has its own offset to indicate its position in the sequence of EGTs that you have to pass through to force mate (as the transitions are irreversible moves you can always order them to that effect), and the DTZ recorded in them is just a fine-tuning of that major score.
Texel already does something like that, see this post and this post. The difference is that instead of assigning more or less arbitrary offsets for each "EGT class", I use a dynamic programming algorithm to derive bounds on the DTM score based on the maximum DTZ value in all successor EGT classes.

This already works in texel 1.05, but the 50-move draw rule is not handled correctly in all cases. This has been fixed in 1.06a40.
User avatar
hgm
Posts: 28395
Joined: Fri Mar 10, 2006 10:06 am
Location: Amsterdam
Full name: H G Muller

Re: My troubles with MultiPV and Syzygy in Stockfish 7

Post by hgm »

Indeed, a good DTZ format should really contain these numbers (the maximum DTM that DTZ=0 corresponds to) as part of the data they hold.

Of course if you don't want silly DTZ behavior, like sacrifycing all the excess material and then slowly but surely win the most difficult end-game that you can still win, no attempt to hide it can be entirely satisfactory, and it would be better to just not use DTZ. In a certain sense this is a self-inflicted problem. It is not obvious that trading extra disk space for the need to make extra searches eventually leads to more efficient use of resources.
petero2
Posts: 729
Joined: Mon Apr 19, 2010 7:07 pm
Location: Sweden
Full name: Peter Osterlund

Re: My troubles with MultiPV and Syzygy in Stockfish 7

Post by petero2 »

hgm wrote:Indeed, a good DTZ format should really contain these numbers (the maximum DTM that DTZ=0 corresponds to) as part of the data they hold.

Of course if you don't want silly DTZ behavior, like sacrifycing all the excess material and then slowly but surely win the most difficult end-game that you can still win, no attempt to hide it can be entirely satisfactory, and it would be better to just not use DTZ. In a certain sense this is a self-inflicted problem. It is not obvious that trading extra disk space for the need to make extra searches eventually leads to more efficient use of resources.
In texel I continue searching after finding a forced TB win, which cures many of the "silly DTZ behavior" problems, but not all of them.

Not using DTZ is currently not a good solution I think. Using pure DTM is inferior in terms of how much it would score in real games, because it ignores the 50-move draw rule. Using DTM50 would be best, except for the fact that there are no publicly available 6-men DTM50 tables, and even if there were, they would probably be far too big to fit in a typical SSD drive.

This page contains lots of interesting information about DTM50 tablebases.
User avatar
hgm
Posts: 28395
Joined: Fri Mar 10, 2006 10:06 am
Location: Amsterdam
Full name: H G Muller

Re: My troubles with MultiPV and Syzygy in Stockfish 7

Post by hgm »

Very nice page indeed.

What is good and what is publicly available are of course different questions. And as I am a programmer, I tend to consider everything available to me, even if not public. :wink:

If the goal is to improve results in games that the engine plays from the start, it would not be terribly expensive to cure most silly behavior in the EGT itself. Just ignore 'bad conversions' in tables where you can afford it (like they were illegal moves), when building them. (I called that DTP, for "distance to progress") All that would do is replace a few quite low DTZ that were going for a forced sacrifice by somewhat higher DTZ. It is not even obvious that this would negatively impact compressibility. And in virtually ever material signature where you can afford to waste material you can certainly afford to waste moves. And in the cases where you cannot do it, you just don't do it, as you would know this at generation time.

Of course that would fail when you try to use the EGT in a position where the reversible ply counter is already so high that the true DTZ is barely enough to stay short of the rule. But I doubt that this is a worthwhile goal; most users would consider it paranoia/madness if you explain to them that it is better for the engine to prefer sacrificing a Queen in 2 moves over delivering mate in 5 because the move counter could be at 98. Users that are specifically interested in solving that kind of problems should simply use DTZ, and not complain about the silliness they are asking for!
syzygy
Posts: 5774
Joined: Tue Feb 28, 2012 11:56 pm

Re: My troubles with MultiPV and Syzygy in Stockfish 7

Post by syzygy »

jdart wrote:The problem is, with Syzygy, you don't get evals in the customary sense. All chess engines usually report scores that are based on distance to mate. With Syzygy you don't have that. You can sort the winning/drawing moves on DTZ. But if there are also losing moves, what is their score, if the search was cut off with a TB hit?
If the root position is not yet in the TB, then SF returns a score representative of the distance to a TB win or TB loss. So SF will play a line that most quickly leads to a TB position. (This is not always ideal from the human point of view, but it works "perfectly". Improving on this approach without turning to DTM tables is not impossible but rather tricky. Likely simply not worth it, but that depends on how much you care about code simplicity etc.)

The discussion here is about the case where the root position is in the TBs.

Since DTZ50 allows an engine to play TB endings perfectly while respecting the 50-move rule, the primary requirement is to actually play those endings perfectly. This is non-negotiable.

A secondary requirement is to play moves that don't look too stupid. A queen move that forces the losing side to capture the winning side's queen just to minimise DTZ (say in KQQvKR) looks stupid.

SF addresses the primary requirement by first filtering out all root moves that would lose half a point or more (taking into account the 50-move rule). This is done by a simple round of probing the DTZ50-tables for each root move.

The secondary requirement is addressed in a simple way by searching the remaining moves in the normal way, but without probing the TBs. This also has the advantage that mates will be found and reported if they are within the search horizon. The move that comes out on top is the move that is played. (There is the potential problem that this leads to a series of moves that repeats the position. Once that happens, SF switches to playing DTZ-optimal moves, which ensures that three-fold repetition is avoided.)

If the root position has high DTZ, the search might sometimes return a drawish or even negative score, because SF's search cannot yet see that the position is winning. Displaying those scores will only confuse the user. Even displaying a +10 score after SF has already announced a (TB) win is confusing. So instead, a TB win (or TB loss or TB draw) score is displayed. (If the search returns a mate score, then that mate score is displayed.)

The above all works out well with mathematical precision. See the other thread by Kai. The programmer understood very well what he was doing.

However, with the above approach, SF's multipv=N mode does not always display N PVs. That is because the filtering phase may select fewer than N moves.

Correcting for this by simply selecting a few more moves does not work, as each of these extra moves carries the risk of losing half a point or more: they are bad moves. Those bad moves simply may not be played (primary requirement). But SF's probeless search does not and cannot know that, in particular if DTZ is relatively high. So it may happen that one of the bad moves floats to the top of the multipv PVs. One could prevent that by adding lots of code to SF (to make sure that the bad moves stay at the bottom). But I am pretty sure that the SF maintainers would not allow that code injection. And for good reasons, because this is just a minor cosmetic quibble. If one really needs to know the outcomes of all moves, then there are online TB browsers.

Of course nobody is prevented from anyway preparing a patch and offering it to the SF maintainers.
jdart
Posts: 4408
Joined: Fri Mar 10, 2006 5:23 am
Location: http://www.arasanchess.org

Re: My troubles with MultiPV and Syzygy in Stockfish 7

Post by jdart »

That is a very cogent explanation, thanks.

I think possibly you could get n lines in analysis if you allowed all moves to be searched but always ordered moves so that the win/draw preserving ones are first.

--Jon