TalkChess.com

Dann Corbit wrote: ↑Tue May 22, 2018 5:55 am Probably ignorant on my part, but could it be possible to pass in the current game state to the EGTB reader method of a DTM file?
It would then have knowledge of the visited positions and the half move clock.
Instead of a simple lookup, it would require a search.
I don't see why it would not work, but probably it is just my lack of vision in understanding how these files really work.

You would need to do a full search, finding a reply to every possible opponent move. The point of having TBs beyond WDL is exactly to avoid that search.

The current DTZ50+ tables are essentially perfect in that they tell the program whether it can win without exceeding the 50-move rule or not. No wins are tossed, and a search is not needed. (And if you don't care about the 50-move rule, they still contain enough information about cursed positions to guide you to a win.)

Of course even DTZ50+ tables can fail if the game history includes two instances of a position with lower DTZ than the current position. If the engine is in charge, it can always avoid that situation.

noobpwnftw wrote: ↑Tue May 22, 2018 1:18 am

Dann Corbit wrote: ↑Tue May 22, 2018 12:55 am By perfect I mean that every move is optimal from the supplied root position. No move results in a shorter mate.
It is also possible to preserve maximal material if there are several paths to checkmate, all of the same length.

DTZ tables do not guarantee shortest mate. Only a sure win.
Same for bitbase.

I guess I see it like this:
bitbase -> show winning moves if there are any, show drawing moves if no winning moves. Theoretically possible to not win a won game if you pick a bad path.
DTZ -> similar but better information. I do not know if you can toss a win, but I suspect it is possible if you do not choose the shortest path to the win and the 100 ply counter gets exhausted.
DTM -> optimal moves.

Now, if it is not DTM50, then the chess programmer will have to look at the distance returned and at his 100 ply counter to see if it is cursed or blessed. But it still offers the best possible move path, albeit with more work on the programmer's part.

Your best possible DTM path must ignore 50-move rule completely, because there may be multiple times that you need to pick the sub-optimal DTM move in favor of a counter reset. In fact, you wouldn't be able to know if a win under 50-move rule is actually achievable without expansive search, it would need looking for all possible paths for which satisfies the counter by raising some DTM but still the overall shortest.

DTM50 basically stores the counter along with DTM(I guess), and when the counter reaches 100 ply then it is blessed/cursed and considered drawn at next iteration, when there is a zeroing move the counter gets reset while the DTM keeps going. It looks not difficult to do aside from doubling memory requirements. But I guess it would be too different from current Syzygy implementation in other parts and probably immense in file size.

DTM50 conceptually stores a distance-to-mate value for each pair (position, rule50_counter). So that is 100x as much raw data as for DTM. The sequence of values for a particular position is far from random, but it is not immediately obvious how to find an efficient encoding that fits into a good compression scheme. And generating these values efficiently is another problem.

DTZ50 avoids this explosion of the state space because the DTZ50 value of a position is essentially independent of the value of the 50-move counter (except that a dtz50 value that is higher than the number of plies left on the 50-move clock should be interpreted as draw).

syzygy wrote: ↑Tue May 22, 2018 3:17 pm DTM50 conceptually stores a distance-to-mate value for each pair (position, rule50_counter). So that is 100x as much raw data as for DTM. The sequence of values for a particular position is far from random, but it is not immediately obvious how to find an efficient encoding that fits into a good compression scheme. And generating these values efficiently is another problem.

DTZ50 avoids this explosion of the state space because the DTZ50 value of a position is essentially independent of the value of the 50-move counter (except that a dtz50 value that is higher than the number of plies left on the 50-move clock should be interpreted as draw).

Ok, so I'm sure I've asked this before, but I don't remember the explanation and I can't find it using the search.
Assuming I have N-piece DTM and DTZ50 tables. Can't I get DTM50 optimal play (not value) by first reducing the move list to those moves that preserve the win (according to DTZ50), and then picking the move with the smallest DTM from that list?

Thank you for your excellent, clear explanation. I think I understand the difficulties better now.

Evert wrote: ↑Tue May 22, 2018 8:11 pm

syzygy wrote: ↑Tue May 22, 2018 3:17 pm DTM50 conceptually stores a distance-to-mate value for each pair (position, rule50_counter). So that is 100x as much raw data as for DTM. The sequence of values for a particular position is far from random, but it is not immediately obvious how to find an efficient encoding that fits into a good compression scheme. And generating these values efficiently is another problem.

DTZ50 avoids this explosion of the state space because the DTZ50 value of a position is essentially independent of the value of the 50-move counter (except that a dtz50 value that is higher than the number of plies left on the 50-move clock should be interpreted as draw).

Ok, so I'm sure I've asked this before, but I don't remember the explanation and I can't find it using the search.
Assuming I have N-piece DTM and DTZ50 tables. Can't I get DTM50 optimal play (not value) by first reducing the move list to those moves that preserve the win (according to DTZ50), and then picking the move with the smallest DTM from that list?

No, because the move with the smallest DTM might not be the move with the smallest DTM50(current_value_of_50_move_counter).

And in theory and most likely also in practice your move-picking rule will sometimes lead to a draw by repetition. (But that can be fixed by detecting that a repetition has occurred since the pawn move or capture and not allowing any moves that would bring DTZ50 to the DTZ50 value of the once-repeated position or higher.)

syzygy wrote: ↑Tue May 22, 2018 8:53 pm

Evert wrote: ↑Tue May 22, 2018 8:11 pm Ok, so I'm sure I've asked this before, but I don't remember the explanation and I can't find it using the search.
Assuming I have N-piece DTM and DTZ50 tables. Can't I get DTM50 optimal play (not value) by first reducing the move list to those moves that preserve the win (according to DTZ50), and then picking the move with the smallest DTM from that list?

No, because the move with the smallest DTM might not be the move with the smallest DTM50(current_value_of_50_move_counter).

Well, obviously that has to be true if what I suggested doesn't work. What I can't figure out is under what conditions it would be true.
Let W50 be the set of winning moves under DTZ50.
Now I pick the move m from W50 that has the smallest DTM.
What you're saying is that there exists an m' in W50 that has a DTM50 that is smaller than the DTM50 of m.
Ok, I think I see where this is going now. I was thinking that DTM50(m') cannot be smaller than DTM(m) or we'd have picked m' instead of m. The first part of that is true, but of course we should compare with DTM50(m), which is >=DTM(m), and then DTM50(m') can be smaller than DTM50(m): DTM(m)<=DTM50(m')<=DTM50(m).

It would be interesting to know how common this situation is. If it's somewhat rare, it might be possible to exploit that to reduce the size of the tables...?

Evert wrote: ↑Tue May 22, 2018 10:52 pm

syzygy wrote: ↑Tue May 22, 2018 8:53 pm

Evert wrote: ↑Tue May 22, 2018 8:11 pm Ok, so I'm sure I've asked this before, but I don't remember the explanation and I can't find it using the search.
Assuming I have N-piece DTM and DTZ50 tables. Can't I get DTM50 optimal play (not value) by first reducing the move list to those moves that preserve the win (according to DTZ50), and then picking the move with the smallest DTM from that list?

No, because the move with the smallest DTM might not be the move with the smallest DTM50(current_value_of_50_move_counter).

Well, obviously that has to be true if what I suggested doesn't work. What I can't figure out is under what conditions it would be true.

With TBs, anything that you cannot rule out by pure logic does happen in some position.

Let W50 be the set of winning moves under DTZ50.
Now I pick the move m from W50 that has the smallest DTM.
What you're saying is that there exists an m' in W50 that has a DTM50 that is smaller than the DTM50 of m.

I am saying that there are positions and values of the 50-move counters for which this happens.

The move with smallest DTM may correspond to a mate path that is 5 moves away to a zeroing move, which does not work if there are only 4 moves left on the 50-move clock. Such a move may still be in W50 though. For example, it could still be winning by a quick queen sac to prevent the 50-move draw. Another move in W50 with a higher DTM value might not need the queen sac to reach the zeroing move in time and will then likely have lower DTM50.

It would be interesting to know how common this situation is. If it's somewhat rare, it might be possible to exploit that to reduce the size of the tables...?

Yes, there might be such tricks.

syzygy wrote: ↑Tue May 22, 2018 8:53 pm No, because the move with the smallest DTM might not be the move with the smallest DTM50(current_value_of_50_move_counter).

If moves are first filtered according to DTZ50 i.e. all cursed wins are removed the remaining move with smallest DTM would not be with the smallest DTM50 if and only if that particular move after first zeroing would still lead only to cursed win and that there is another winning move that doesn't lead to cursed win. That is ofc possible put extremely improbable.
Would be interesting to test this but I seriously doubt you'd be able to find even a single example of this (even though they might exist).
And if you are really worried about this, you could still check by search, i.e. just always use DTZ50 for filtering, choose lowest DTM move and continue until your line is filtered due to DTZ50 or you reach mate. In first case backtrack to the point before previous zeroing and select another move and continue. In that way, the first time you actually reach mate that would be certainly DTM50. And since probability of cursed win is very small the amount of backtracking and researching would be miniscule.

KQQQvKPP.txt was curious. I'm not sure if I understand this:

Black to move:

65816916 positions win in 1 ply.
756 positions win in 101 ply.
[…]
Longest win for white: 5 ply; 8/8/7Q/8/8/1k6/pp6/2K1Q1Q1 w - -
Longest cursed win for white: 101 ply; k7/8/3Q4/8/1Q6/K1Q5/pp6/8 b - -
Longest win for black: 2 ply; 8/8/8/8/3Q4/k7/pp1QQ3/1K6 w - -

Where did the longest (cursed) win for black go? And is there really only a mate directly on the board or a win that's just exactly cursed? (Or maybe “in 101 ply” means a conversion to a cursed win, where we don't really care about the true distance?)

Sesse wrote: ↑Wed May 23, 2018 7:46 pm KQQQvKPP.txt was curious. I'm not sure if I understand this:

Black to move:

65816916 positions win in 1 ply.
756 positions win in 101 ply.
[…]
Longest win for white: 5 ply; 8/8/7Q/8/8/1k6/pp6/2K1Q1Q1 w - -
Longest cursed win for white: 101 ply; k7/8/3Q4/8/1Q6/K1Q5/pp6/8 b - -
Longest win for black: 2 ply; 8/8/8/8/3Q4/k7/pp1QQ3/1K6 w - -

Where did the longest (cursed) win for black go? And is there really only a mate directly on the board or a win that's just exactly cursed? (Or maybe “in 101 ply” means a conversion to a cursed win, where we don't really care about the true distance?)

101 ply indeed means either 101 ply to a winning zeroing move or 1 ply to a cursed winning zeroing move.

I'm not sure why the 101 ply white win is shown but the 101 ply black win is not. It probably has to do with the black winning move being a pawn move.