Almost perfect DTM tablebase

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Dann Corbit
Posts: 10856
Joined: Wed Mar 08, 2006 7:57 pm
Location: Redmond, WA USA
Contact:

Almost perfect DTM tablebase

Post by Dann Corbit » Wed Apr 08, 2020 8:56 pm

I was thinking about DTM tablebase files and the problem with the 50 move counter (and castle status).
It seems to me that castle status is needed, but the 50 move counter has a round about.
Suppose that the engine passes in the 50 move counter to the tablebase file set.
Now, the tablebase set (if complete) will already have the minimum distance to mate for the current position and every possible position that can be generated from this position.
So, if the distance to mate would drop the flag on the 50 move counter, then generate all moves that reset the counter and probe for each of those. If you put the code in the probe engine, the calling program would not have to worry about it. So if any of the generated moves still wins, return the fastest mate from that set. If there are no non-reversible moves, or the moves that reset the counter do not win, then generate all the moves you did not generate and repeat one time. If still no mate, return a status of cursed mate.
I guess that there are still some very rare positions where you need a three or four move sequence to get a beneficial capture and still win (or some other esoteric combination). But the programmer, upon seeing the cursed win flag returned, could still do some searching if he so desired.
It seems to me that this would be almost as good as a tablebase that incorporates the 50 move counter and much smaller in size.
Now, I guess that there are already engine programmers that perform a search similar to what I have described. The beneifit of putting it into the probing code would be that it only has to be written and debugged once.

Is this a dumb idea? Or has it already been tried? Or is there a logical flaw, where it simply would not work.
A similar idea would be for the programmer to supply the castle status, which would give a few more moves to search for the probing code.
I suspect that neither idea is perfect, but it seems they might offer some sort of improvement.
Taking ideas is not a vice, it is a virtue. We have another word for this. It is called learning.
But sharing ideas is an even greater virtue. We have another word for this. It is called teaching.

User avatar
hgm
Posts: 24449
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Almost perfect DTM tablebase

Post by hgm » Thu Apr 09, 2020 8:55 am

I don't understand completely what you propose, but I suspect it is a dumb idea. For one, the DTM is not the same as DTZ. Your ply counter could be at 80, and the DTM could be 60 moves, and it could still be an easy win, because the DTM-optimal play would reset the counter already after 5 moves against any defense, by advancing a Pawn (or worse), and advance it again 30 moves later. So DTM values are useless for deciding whether you will be in 50-move trouble or not. Even when they suggest you are not, (e.g. your counter is at 6, and DTM=46) it could be because they count on the losing player to delay the mate at all cost, even if that would mean missing a 50-move draw: according to DTM hanging on to your last piece for 45 moves and then being mated in 20 is much better than hanging on to it for 55 moves and being mated in 5, but in the FIDE world the latter would have been a draw.

The only way to judge whether the current value of the ply counter is low enough for focing a win is to know the DTZ50.

Of course when you have DTZ50 available you could pick the move that leads to the lowest DTM, and according to DTZ50 and your ply counter is still won. There is no guarantee that actually gives you the fastest mate, as DTZ50 might force you to later deviate again from the path DTM had in mind, while when opting for a longer DTM immediately might not have run into that problem. But it does remove the worst artifacts of pure DTZ50 play, such as sacrificing Q in KQBNKP, as the DTM of the remaining KBNKP will almost certainly be much larger than anything you could do while keeping the Queen on the board.

Dann Corbit
Posts: 10856
Joined: Wed Mar 08, 2006 7:57 pm
Location: Redmond, WA USA
Contact:

Re: Almost perfect DTM tablebase

Post by Dann Corbit » Thu Apr 09, 2020 8:59 am

That's what I get for trying to think.
Does anybody smell wood burning?
😕
Taking ideas is not a vice, it is a virtue. We have another word for this. It is called learning.
But sharing ideas is an even greater virtue. We have another word for this. It is called teaching.

User avatar
hgm
Posts: 24449
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Almost perfect DTM tablebase

Post by hgm » Thu Apr 09, 2020 1:25 pm

BTW, it is a good question what should be considered 'best defense' in late end-games. And it arguably is not postponing the mate as long as possible. Holding out long doesn't get you any extra points; it just prolongs your misery. In a lost position all you can hope for is an error of the opponent that bungles his win. When a fallible opponent makes errors, his DTM will increase. One can hope that the opponent has a fixed error rate per move, so in that respect trying to hold out as long as you can seems a good idea, as it increases the chances he will have another slip, and in the end he might not be able to do it within 50 moves.

But this doesn't just hold for the checkmate; it holds for any zeroing of the ply counter. If you are defending a KBBKN position that, according to DTZ50, is close to being cursed (e.g. 48 moves until you lose the Knight, after which you are mated in 6 in KBBK), the opponent only has to lose 2 moves compared to optimal play, and you have secured the draw. A defensive strategy that would lose the Knight in 40 moves, after which you get checkmated in 16, would have pushed the checkmate 2 moves more distant (56 moves vs 54). But it would virtually offer no hope for a draw at all. Even 16 moves is so far from 50 (abd even the max DTM in KBBK is), that the opponent is extremely unlikely to bungle the KBBK, even if he has a quite high error rate. So postponing the mate hardly gained you anything. But upping the number of moves he must slip in the (intrinsically much more difficult, and often cursed) KBBKN from 2 to 10 will strongly reduce the chances that you will get a draw there.

Trying to postpone the mate from 54 to 56 moves in this case seems a gross strategic blunder, not at all an 'optimal defense'. When you are in a won end-game there is something to be said for playing by DTM, as it minimizes the remaining duration of the game in the worst case, and you know you are not going to make any mistakes as you have all the required EGT. But in a lost position using DTM can be pretty stupid, and playing by DTC or DTZ would give you much better chances to swindle a fallible opponent.

User avatar
phhnguyen
Posts: 723
Joined: Wed Apr 21, 2010 2:58 am
Location: Australia
Full name: Nguyen Hong Pham
Contact:

Re: Almost perfect DTM tablebase

Post by phhnguyen » Thu Apr 09, 2020 2:03 pm

Dann Corbit wrote:
Thu Apr 09, 2020 8:59 am
That's what I get for trying to think.
Does anybody smell wood burning?
😕
IMO, your thought is correct: we can search over DTM EGTBs to solve the problem of the 50-move draw. Syzygy actually does a lot of searches too (when it sees curved wins/losses).

However, there is a problem - effectiveness for DTM:
- Syzygy base does not require to search when the endgames return values of draws, sure wins/losses. It searches only for curved wins/losses. On the other hand, for a DTM EGTB, only draw value is sure but wins/losses are not - they all are curved and needed to search. I don't have any statistics to prove that but can guess the number of cursed cases must be significantly higher than Syzygy ones
- When searching with Syzygy if we see a capture or a pawn push, the curved case will change to sure case and the search can stop at that branch. For a DTM EGTB we may not (stop searching when seeing a capture/pawn push) since the new value may be a curved one too. It means we may have to continue to search deeper.

I guess it is not every case but sometimes the EGTB search may have to search exponentially, slow down everything which may be big troubles for engines

BTW, DTZ50 is better for winning but not much. We had been using DTM (without worrying about 50-move draw) for a long time and we could continue. I mightn't use any of them. However, now the size of EGTBs plays the main role and it is actually the success key of Syzygy, not its DTZ50. DTZ50 helps indirect way: its values are typically smaller than DTM ones. That can help to have higher compressed ratios. Ronald de Man also applied many clever tricks to make Syzygy data be small.

At the moment Syzygy base is 8 times as small as the smallest DTM one (for a fairer comparison, Syzygy actually omitted data of one side, thus if we count its both-side data, it is about 3 times smaller the best rival).

DTM EGTBs have to overcome that gap to win back users.
https://banksiagui.com
A freeware chess GUI, based on opensource Banksia - the chess tournament manager

User avatar
Nordlandia
Posts: 2588
Joined: Fri Sep 25, 2015 7:38 pm
Location: Sortland, Norway

Re: Almost perfect DTM tablebase

Post by Nordlandia » Tue Apr 14, 2020 4:40 pm

DTM50 is the optimum format but at the expense of massive size of 100 times larger than Nalimov +/-

syzygy
Posts: 4503
Joined: Tue Feb 28, 2012 10:56 pm

Re: Almost perfect DTM tablebase

Post by syzygy » Tue Apr 14, 2020 10:14 pm

phhnguyen wrote:
Thu Apr 09, 2020 2:03 pm
BTW, DTZ50 is better for winning but not much.
Fake mate announcements aren't very nice if one pretends to have "perfect" information (but I guess one could just change the rules of chess, as ICCF did...).

WDL50+ is a bit bigger than plain WDL would be, but I decided it was worth it. Indeed DTZ50+ is smaller than plain DTZ.
(I add the "+" to distinguish from WDL50 that scores cursed wins/losses as draws.)
At the moment Syzygy base is 8 times as small as the smallest DTM one (for a fairer comparison, Syzygy actually omitted data of one side, thus if we count its both-side data, it is about 3 times smaller the best rival).
WDL50+ is double sided.

To make the comparison fair, one could re-encode the Nalimov TBs as a set of double-sided WDL tables and a set of single-sided (and signless) DTM tables. Of course, if you have Syzygy WDL50+ around anyway, you don't need the WDL tables.

User avatar
phhnguyen
Posts: 723
Joined: Wed Apr 21, 2010 2:58 am
Location: Australia
Full name: Nguyen Hong Pham
Contact:

Re: Almost perfect DTM tablebase

Post by phhnguyen » Wed Apr 15, 2020 1:28 am

syzygy wrote:
Tue Apr 14, 2020 10:14 pm
phhnguyen wrote:
Thu Apr 09, 2020 2:03 pm
BTW, DTZ50 is better for winning but not much.
Fake mate announcements aren't very nice if one pretends to have "perfect" information (but I guess one could just change the rules of chess, as ICCF did...).

WDL50+ is a bit bigger than plain WDL would be, but I decided it was worth it. Indeed DTZ50+ is smaller than plain DTZ.
(I add the "+" to distinguish from WDL50 that scores cursed wins/losses as draws.)
At the moment Syzygy base is 8 times as small as the smallest DTM one (for a fairer comparison, Syzygy actually omitted data of one side, thus if we count its both-side data, it is about 3 times smaller the best rival).
WDL50+ is double sided.

To make the comparison fair, one could re-encode the Nalimov TBs as a set of double-sided WDL tables and a set of single-sided (and signless) DTM tables. Of course, if you have Syzygy WDL50+ around anyway, you don't need the WDL tables.
I am confused about the detail of Syzygy's data sides. Can you confirm (I will use to update CPW):
- does current released Syzygy EGTB have full data of all sides?
- if some data is omitted, what the (roughly) size of full data, say 5 men? Just for comparing with other EGTBs. We don't need the fairest comparison, but enough for a quick evaluation.

Thanks
https://banksiagui.com
A freeware chess GUI, based on opensource Banksia - the chess tournament manager

User avatar
hgm
Posts: 24449
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Almost perfect DTM tablebase

Post by hgm » Wed Apr 15, 2020 9:14 am

Nordlandia wrote:
Tue Apr 14, 2020 4:40 pm
DTM50 is the optimum format ...
Not really. It can lead to very stupid defense, because it tries at all cost to guarantee the mate is delayed as long as possible. Even when that massively reduces the probability to get a draw through an opponent error. While in the end delaying mate in terms of the move number will not gain you any points, while delaying a zeroing event beyond the 50-move limit would have earned you a draw.

So you should always go for postponing the zeroing event that is closest to the 50-move limit, when defending a lost position. Often that is the first zeroing event you will encounter, as defending gets progressively more difficult as the opponent approches the winning goal. E.g. sacrificing a Knight in KBBKN just to secure a KBBK postion with a maximum DTM is a completely hopeless tactic, as the max DTM in KBBK is only 18 and the mate is easy, so you will never be able to draw it out to more than 50 moves even against a very fallible opponent. While in KBBKN you might have been only 1 sub-optimal move removed from a draw. Most KBBKN positions are cursed wins, so there are lots of possibilities for the opponent to err. It isn't very likely he will blunder away a Bishop in KBBK, though.

syzygy
Posts: 4503
Joined: Tue Feb 28, 2012 10:56 pm

Re: Almost perfect DTM tablebase

Post by syzygy » Wed Apr 15, 2020 10:15 am

phhnguyen wrote:
Wed Apr 15, 2020 1:28 am
I am confused about the detail of Syzygy's data sides. Can you confirm (I will use to update CPW):
- does current released Syzygy EGTB have full data of all sides?
Syzygy WDL is double sided, DTZ is single sided.

So to know whether a 7-piece position is winning, losing or drawn (or cursed), the engine needs to do only a single probe of a 7-piece WDL table. (It may in addition have to do some probes of 6-piece WDL tables if any direct captures are available.)

If the engine needs to know the DTZ value (which is only necessary when a TB root position has been reached), the probing code may have to do a 1-ply search to get to the "right" side of the DTZ table.
if some data is omitted, what the (roughly) size of full data, say 5 men? Just for comparing with other EGTBs. We don't need the fairest comparison, but enough for a quick evaluation.
For 6-piece TBs, DTZ is 81.9GB when storing only the smaller side of each table. Storing both sides might require perhaps 240GB.

Post Reply