Nalimov EGTB problem related to DTM?

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

Moderator: Ras

User avatar
Laskos
Posts: 10948
Joined: Wed Jul 26, 2006 10:21 pm
Full name: Kai Laskos

Re: Nalimov EGTB problem related to DTM?

Post by Laskos »

Daniel Mehrmann wrote:
Laskos wrote:I knew that Nalimovs have this problem, but first, I imagined it to be a problem with very rare, freak positions, second, I didn't know that Syzygy gives "perfect play" against "perfect play". I was under some sort of artistic impression that if Nalimov shows me the shortest distance to mate in a given root position, even ignoring the 50-move rule it should perform at least as well as Syzygy on wins from the root. Then several days ago I played (color and reversed) from my hard TB won positions, using Nalimov, Syzygy and Komodo no TB, with these results:

Code: Select all

Rank Name                          ELO   Games   Score   Draws
   1 Syzygy                         69    1032     60%     20%
   2 Nalimov                        43    1032     56%     21%
   3 Komodo No TB                 -115    1032     34%     32%
Finished match
Well, basicly i wouldn't say that Syzygy performs better then Nalimov. A combination of both can be good too. I tested it with Fruit and it looks not so bad.

Probably they are equal with distance zero/mate, but Syzygy performs better, because the files are smaller (timing i/o balance).

Well, if the root position is already inside a database, "Nalimov" engines doesn't do a move order based on the mate scores at root. At least i can say, i don't know such a engine yet. Maybe that could be a reason in some cases if the depth or time is extremely limited. However, i need to do more tests in that case.

Regards
Daniel
The sole advantage of Nalimovs is that they are showing the correct DTM in PV. Might be useful for analysis, otherwise Syzygy bases are to be preferred.
Top
User avatar
velmarin
Posts: 1600
Joined: Mon Feb 21, 2011 9:48 am

Re: Nalimov EGTB problem related to DTM?

Post by velmarin »

Laskos, you are absolutely right.
Nalimov behavior with this table (two bishops and a Knight) is rather disappointing.
I made a small test with Rybka with Nalimov and Stockfish with Syzygy at the Aquarium GUI.
The tablebasses loaded individually on each engine, no award all games until the end.
Nalimov won only one.

Code: Select all

1   stockfish dev             +168   ½1½1½1½1½1½1½1½1½101  14.5/20
2   Deep Rybka 4.1___        -168    ½0½0½0½0½0½0½0½0½010    5.5/20
Top
User avatar
Daniel Mehrmann
Posts: 858
Joined: Wed Mar 08, 2006 9:24 pm
Location: Germany
Full name: Daniel Mehrmann

Re: Nalimov EGTB problem related to DTM?

Post by Daniel Mehrmann »

Laskos wrote:
Daniel Mehrmann wrote:
Laskos wrote:I knew that Nalimovs have this problem, but first, I imagined it to be a problem with very rare, freak positions, second, I didn't know that Syzygy gives "perfect play" against "perfect play". I was under some sort of artistic impression that if Nalimov shows me the shortest distance to mate in a given root position, even ignoring the 50-move rule it should perform at least as well as Syzygy on wins from the root. Then several days ago I played (color and reversed) from my hard TB won positions, using Nalimov, Syzygy and Komodo no TB, with these results:

Code: Select all

Rank Name                          ELO   Games   Score   Draws
   1 Syzygy                         69    1032     60%     20%
   2 Nalimov                        43    1032     56%     21%
   3 Komodo No TB                 -115    1032     34%     32%
Finished match
Well, basicly i wouldn't say that Syzygy performs better then Nalimov. A combination of both can be good too. I tested it with Fruit and it looks not so bad.

Probably they are equal with distance zero/mate, but Syzygy performs better, because the files are smaller (timing i/o balance).

Well, if the root position is already inside a database, "Nalimov" engines doesn't do a move order based on the mate scores at root. At least i can say, i don't know such a engine yet. Maybe that could be a reason in some cases if the depth or time is extremely limited. However, i need to do more tests in that case.

Regards
Daniel
The sole advantage of Nalimovs is that they are showing the correct DTM in PV. Might be useful for analysis, otherwise Syzygy bases are to be preferred.
I don't think the problem is DTM itself. Okay, you can make things easier for a engine if you take care about the 50-move rule by generation.

Probably the most implementations of Nalimov's EGTB, including Fruit, are simply lazy written or copyed.

I think you can resolve this problem by a little local search on root, like Syzygy does, to take care of the 50-move rule.

I'll do that and we can bet that a engine of your choice will never draw a winning position against Fruit.

Regards
Daniel
Top
User avatar
hgm
Posts: 28353
Joined: Fri Mar 10, 2006 10:06 am
Location: Amsterdam
Full name: H G Muller

Re: Nalimov EGTB problem related to DTM?

Post by hgm »

If you don't search all the way to the mate (i.e. do not use the EGT at all) I don't see how this is possible. You could be in a position that is just barely won (i.e. where the conversion can be forced on the 50th move, but not earlier), and where Nalimov suggests a wrong move that speeds up the mate at the expense of delaying the conversion already on the second move. If you don't search at least 96 ply on every branch at the point where Nalimov suggests the error, you would never see the opponent now can force a 50-move draw. Any lower-depth search that at the leaves probes Nalimov will simply confirm what a 1-ply probing search gives, as there is no inconsistency within the Nalimov EGT. Nalimov will only be contradicted in nodes where the reversible-ply counter hits 100.
Top
bob
Posts: 20943
Joined: Mon Feb 27, 2006 7:30 pm
Location: Birmingham, AL

Re: Nalimov EGTB problem related to DTM?

Post by bob »

syzygy wrote:
bob wrote:
syzygy wrote:
bob wrote:I am not sure what the problem is here. I tested this position a hundred times against multiple opponents and never saw a loss or draw by any program for the winning side. The knight is captured well before the 50 move rule limit with optimal play
I don't know what you call optimal play, but black can postpone the knight's capture until the49th move.

So the position is won for white under the 50-move rule, but white needs to play carefully and merely following Nalimov might be insufficient.
I call "optimal play" playing the sequence of moves that leads to the shortest possible mate. DTZ handles the 50 move rule where DTM currently does not, of course. But here 50 move is irrelevant. If black tries to postpone the knight loss, he gets mated even quicker however.
Apparently there are lines starting from Kai's position that have DTM-optimal moves by white but do run afoul of the 50-move rule.

And I don't find that surprising given that the position has DTZ=49: white can only afford to lose 1 move in the DTZ-metric. In this respect, your particular DTM-line that has a capture after 46 moves is simply meaningless.

Maybe Kai can give us an example game where white using Nalimov only manages to draw the position.
After thinking about this, I was obviously wrong. Since the king and knight moves have the same distance to mate, they are equal in the eyes of Crafty. Where the human would obviously try to push the DTZ counter as hard as possible to encourage a 1 tempo mistake here or there...
Top
bob
Posts: 20943
Joined: Mon Feb 27, 2006 7:30 pm
Location: Birmingham, AL

Re: Nalimov EGTB problem related to DTM?

Post by bob »

Laskos wrote:
syzygy wrote:
bob wrote:
syzygy wrote:
bob wrote:I am not sure what the problem is here. I tested this position a hundred times against multiple opponents and never saw a loss or draw by any program for the winning side. The knight is captured well before the 50 move rule limit with optimal play
I don't know what you call optimal play, but black can postpone the knight's capture until the49th move.

So the position is won for white under the 50-move rule, but white needs to play carefully and merely following Nalimov might be insufficient.
I call "optimal play" playing the sequence of moves that leads to the shortest possible mate. DTZ handles the 50 move rule where DTM currently does not, of course. But here 50 move is irrelevant. If black tries to postpone the knight loss, he gets mated even quicker however.
Apparently there are lines starting from Kai's position that have DTM-optimal moves by white but do run afoul of the 50-move rule.

And I don't find that surprising given that the position has DTZ=49: white can only afford to lose 1 move in the DTZ-metric. In this respect, your particular DTM-line that has a capture after 46 moves is simply meaningless.

Maybe Kai can give us an example game where white using Nalimov only manages to draw the position.
Sure, from the discussed position, a game between Shredder 12 Nalimov (3-4-5) against Komodo 9.3 Syzygy (3-4-5). Michael posted it with Crafty 25.01 Nalimov too.

I might experiment with this a bit as I wonder if it is fixable. IE the original is a mate in N score, which for Crafty is > 32000. I might could factor in the 50 move counter inversely so that it would prefer smallest mate score with largest 50 move counter, encouraging the 50 move counter to be reset earlier in the PV path. Since the 50 move counter is the problem, this would factor in a sort of DTZ approximation while preserving the actual mate score. Will need to adjust how I do the N part of mate in N so that it is dominant however.
Top
User avatar
hgm
Posts: 28353
Joined: Fri Mar 10, 2006 10:06 am
Location: Amsterdam
Full name: H G Muller

Re: Nalimov EGTB problem related to DTM?

Post by hgm »

The problem is that the fifty-move counter measures the distance to the previous irreversible move, while what you are interested in is the distance to the point in the future where you can reset it. But the latter is usually way beyond the horizon. Especially when you want to rely on DTM probing.

Note that when the successor end-game after conversion/zeroing is difficult, resetting the counter too early can be just as fatal as resetting it too late. You must be sure that you don't jump into a cursed win of that successor, and that can require careful preparation in the current phase. Nalimov doesn't contain that information, and plain DTZ would not either. Only DTZ50 guarantees this.
Top
Dirt
Posts: 2851
Joined: Wed Mar 08, 2006 10:01 pm
Location: Irvine, CA, USA

Re: Nalimov EGTB problem related to DTM?

Post by Dirt »

bob wrote:I might experiment with this a bit as I wonder if it is fixable.
The (relatively) easy way is to support Syzygy. It's files take up less room, too.
Deasil is the right way to go.
Top
bob
Posts: 20943
Joined: Mon Feb 27, 2006 7:30 pm
Location: Birmingham, AL

Re: Nalimov EGTB problem related to DTM?

Post by bob »

hgm wrote:The problem is that the fifty-move counter measures the distance to the previous irreversible move, while what you are interested in is the distance to the point in the future where you can reset it. But the latter is usually way beyond the horizon. Especially when you want to rely on DTM probing.

Note that when the successor end-game after conversion/zeroing is difficult, resetting the counter too early can be just as fatal as resetting it too late. You must be sure that you don't jump into a cursed win of that successor, and that can require careful preparation in the current phase. Nalimov doesn't contain that information, and plain DTZ would not either. Only DTZ50 guarantees this.
My thought was that since I don't know when it will be reset in the future, reward resetting it as early in the PV as possible, rather than later, which might avoid this particular problem.
Top
bob
Posts: 20943
Joined: Mon Feb 27, 2006 7:30 pm
Location: Birmingham, AL

Re: Nalimov EGTB problem related to DTM?

Post by bob »

Dirt wrote:
bob wrote:I might experiment with this a bit as I wonder if it is fixable.
The (relatively) easy way is to support Syzygy. It's files take up less room, too.
ONLY for 6 pieces or less. But this is a general problem that applies with more pieces on the board, hence thinking about something that has a chance,whether it would work or not is not even conjecture at this point.
Top

Return to “Computer Chess Club: General Topics”