Suicide chess tablebases (stalemated player wins)

[syzygy]

OK, clearly the problem is related to the fact that all these .stbz files are 80 bytes.

This is probably good news. The WDL tables should be fine and only some DTZ tables will have to be regenerated. 6-piece tables might not be affected, but I will have to look into this. (I suspect I collapse tables to 80 bytes when that works for 6-piece tables due to the more complicated probing. I should be more careful with 5-piece tables...)

edit: no, the difference between 5- and 6-piece tables should only matter for probe_wdl() / probe_ab(). I'm now thinking that the 80-byte DTZ tables are actually all fine, but that DTZ probing needs a bit more intelligence. I'll come back to this.

[syzygy]

probe_wdl() / probe_ab() is different too, because capturing is compulsory. So if at least one capture exists, you should return the result of the best capture. If no capture exists, you should return the result of probe_table().

If you go for 6-piece (generation would take many months though), probing becomes more complicated. In a 6-piece position without captures, you have to try out all moves of the side to move that immediately force a capture by the other side and then call probe_table(). The value of the position is the max of the various outcomes. So this is only necessary for the 6-piece position itself, not for the 5-piece positions obtained after a capture.

Here is a probe_wdl() implementation (probe_tb()) that takes arrays of numpcs piece types and positions, a bitboard with the occupied squares, and alpha/beta bounds (from -2 to 2):
https://github.com/syzygy1/tb/blob/master/src/sprobe.c
Lines 148-149 skip the part where all "threats" are tried (i.e. moves that force a capture by the opponent).

probe_dtz() should not need many changes (but I haven't actually tried probing my suicide dtz tables, so... let's hope they work at all ).

So probe_dtz() does need some changes after all.

Basically, what needs to be done extra for 6-piece WDL suicide tables (compared to 5-piece WDL suicide tables) also needs to be done for all 2/3/4/5/6-piece DTZ tables.

My probing code has a function probe_wdl_no_threats() for probing 2/3/4/5-piece WDL tables and a function probe_wdl_threats() for probing 6-piece WDL tables. The latter tries out all "threat" moves, i.e. non-captures that force the opponent to capture.

My probe_dtz() first calls probe_wdl_threats(). This returns a wdl value and a "success" flag with the following meaning (the following lines are from my probe_dtz()):

Code: Select all

  if (*success == 0) return 0; // probe failed

  if (wdl == 0) // draw
    return 0;

  if (*success == 3) // the side-to-move has a capture
    return  wdl == 2 ? 1
          : wdl == 1 ? 101
          : wdl == -1 ? -101 : -1;

  if (*success == 2) // the position is a win or cursed win by a threat move
    return wdl == 2 ? 2 : 102;

After this, check for winning or cursed winning pawn moves, then call probe_dtz_table(), etc.

Then there is the problem that probe_dtz_table() does not return the right value if the DTZ TB file collapsed to 80 bytes. This might actually be a small bug in the generator, but I think it can be worked around by changing this line:
https://github.com/syzygy1/Cfish/blob/m ... ore.c#L961
In suicide mode, set d->min_len to 1.

I have not yet verified that this works in all cases, but it fixes your position (up to an off-by-1). I will have a better look at this at some later point.

[niklasf]

Thanks, this looks promising. I tested it with 5 piece tables on a couple of hand picked positions (WDL, DTZ) as well as a list of antichess puzzle posiitons (WDL and the bound DTZ <= DTM). No errors so far.

My plan now is:

- Keep generating pawnless 6 piece suicide tables
- Further tests, maybe with the positions from the stat files or any other positions I can get my hands on
- Port suicide/giveaway probing to Daniel Dugovics variant Stockfish
- Make online lookup available
- Generate the remaining pawnful giveaway tables

This alone might take me months. I'll let you know how it goes.

6 piece giveaway tables is more than I hoped for initially. If I have spare resources I might eventually also go for 6 piece suicide tables, just for completeness.

[niklasf]

There seems to be a problem with some positions with pawns. For instance:

[d] 8/P7/8/8/8/8/7p/8 w - - 0 1

White to move is losing. There are no forced captures and no threats. probe_dtz_table returns 2 with success 1. Therefore probe_dtz returns -3. But the expected DTZ is -1.

More examples:

Longest win for black: 1 ply; 8/P7/8/8/8/8/7p/8 w - - (dtz differs, got: -3, PvP)
Longest win for black: 2 ply; 8/PP6/8/8/8/8/8/b7 b - - (dtz differs, got: 4, PPvB)
Longest win for black: 2 ply; 8/PP6/3k4/8/8/8/8/8 b - - (dtz differs, got: 4, PPvK)
Longest win for black: 2 ply; 8/PP6/8/8/1n6/8/8/8 b - - (dtz differs, got: 4, PPvN)
Longest win for black: 1 ply; 8/P7/8/1P6/8/8/p7/8 w - - (dtz differs, got: -3, PPvP)
Longest win for black: 2 ply; 8/PP6/8/8/8/8/8/3q4 b - - (dtz differs, got: 4, PPvQ)
Longest win for black: 2 ply; 8/PP6/8/8/8/8/8/3r4 b - - (dtz differs, got: 4, PPvR)
Longest win for black: 2 ply; 8/PP6/P7/8/8/8/8/1b6 b - - (dtz differs, got: 4, PPPvB)
Longest win for black: 2 ply; 8/PPP5/4k3/8/8/8/8/8 b - - (dtz differs, got: 4, PPPvK)
Longest win for black: 2 ply; 8/PPP5/8/8/n7/8/8/8 b - - (dtz differs, got: 4, PPPvN)
Longest win for black: 1 ply; 8/P7/1P6/8/2P5/8/p7/8 w - - (dtz differs, got: -3, PPPvP)
Longest win for black: 2 ply; 8/PPP5/8/8/8/8/8/4q3 b - - (dtz differs, got: 4, PPPvQ)
Longest win for black: 2 ply; 8/PPP5/8/8/8/8/8/4r3 b - - (dtz differs, got: 4, PPPvR)
Longest win for black: 1 ply; 8/P7/P7/8/8/8/1pp5/8 w - - (dtz differs, got: -3, PPvPP)
[...]

Can you reproduce this or is it an oversight in my implementation? Maybe it needs a special case for positions where one side has only pawns.

[niklasf]

With "one side has only pawns" excluded (DTZ is trivial in that case anyway) only a couple of stats positions in cursed territory remain broken.

For example:

[d] 8/4P3/1BP5/8/8/8/8/2k5 b - - 0 1

Black to move defends a blessed loss with DTZ -104. Black has no captures or threats. probe_dtz_table returns 0 with success 1. Therefore -101 is reported as the DTZ.

Complete list:

Longest cursed win for white: 104 ply; 8/4P3/1BP5/8/8/8/8/2k5 b - - (expected dtz: -104, got: -101, BPPvK)
Longest cursed win for white: 109 ply; 8/2P5/b5B1/8/4N3/8/8/k7 w - - (expected dtz: 109, got: 65535, BNPvKB)
Longest cursed win for white: 106 ply; B7/8/2PPP3/8/8/8/8/3k4 b - - (expected dtz: -106, got: -101, BPPPvK)
Longest cursed win for white: 106 ply; 2B5/8/2PP4/8/3p4/8/8/3b4 b - - (expected dtz: -106, got: -101, BPPvBP)
Longest cursed win for white: 105 ply; 1k6/4P3/1P3B2/8/8/k7/8/8 w - - (expected dtz: 105, got: 102, BPPvKK)
Longest cursed win for white: 106 ply; 5q2/3P4/1P6/8/k3B3/8/8/8 b - - (expected dtz: -106, got: -101, BPPvKQ)
Longest cursed win for white: 106 ply; 8/1P6/8/q7/1p6/3P4/4B3/8 b - - (expected dtz: -106, got: -102, BPPvQP)
Longest cursed win for white: 114 ply; 5q2/4k3/8/8/8/8/8/1K2B2N b - - (expected dtz: -114, got: 102, KBNvKQ)
Longest cursed win for white: 106 ply; 3NB3/K7/8/8/8/8/1p6/2q5 b - - (expected dtz: -106, got: -104, KBNvQP)
Longest cursed win for white: 104 ply; 8/8/3N4/7K/8/8/p1K5/6b1 w - - (expected dtz: 104, got: 101, KKNvBP)
Longest cursed win for white: 104 ply; N6k/8/K7/8/8/8/1p5K/8 w - - (expected dtz: 104, got: 101, KKNvKP)
Longest cursed win for white: 102 ply; 3q4/8/8/7K/6N1/8/p7/2K5 b - - (expected dtz: -102, got: 102, KKNvQP)
Longest cursed win for white: 106 ply; 4r3/8/8/8/2K5/7K/2p5/7N w - - (expected dtz: 106, got: 101, KKNvRP)
Longest cursed win for white: 106 ply; 8/3P4/8/8/8/2K5/6k1/2K3n1 b - - (expected dtz: -106, got: -101, KKPvKN)
Longest cursed win for white: 104 ply; K1k5/P7/8/4K3/8/8/6p1/8 w - - (expected dtz: 104, got: 102, KKPvKP)
Longest cursed win for white: 105 ply; 4K3/8/3P4/8/8/5p2/8/1K5n b - - (expected dtz: -105, got: -102, KKPvNP)
Longest cursed win for white: 103 ply; 8/KK6/8/8/6r1/1P5p/8/8 w - - (expected dtz: 103, got: 101, KKPvRP)
Longest cursed win for white: 107 ply; 8/7K/8/8/8/5R2/pn5K/8 b - - (expected dtz: -107, got: -102, KKRvNP)
Longest cursed win for white: 106 ply; 5k2/2N5/8/7K/8/8/1p6/4N3 w - - (expected dtz: 106, got: 101, KNNvKP)
Longest cursed win for white: 105 ply; 8/2n5/8/8/N7/1p6/7K/5N2 b - - (expected dtz: -105, got: -102, KNNvNP)
Longest cursed win for white: 106 ply; 8/2PP4/8/8/4b1K1/8/3p4/8 b - - (expected dtz: -106, got: -101, KPPvBP)
Longest cursed win for white: 104 ply; 8/P7/K7/2P5/8/1p6/8/1q6 b - - (expected dtz: -104, got: -102, KPPvQP)
Longest cursed win for white: 106 ply; 8/1P6/8/5P2/8/rp6/8/7K w - - (expected dtz: 106, got: 102, KPPvRP)
Longest cursed win for white: 105 ply; 7k/P7/Q7/7P/8/8/6K1/8 w - - (expected dtz: 105, got: 102, KQPPvK)
Longest cursed win for white: 104 ply; 8/6K1/8/8/8/8/pN4R1/2n5 w - - (expected dtz: 104, got: 101, KRNvNP)
Longest cursed win for white: 107 ply; 1N6/8/7n/2P5/5p2/5N2/8/8 b - - (expected dtz: -107, got: -102, NNPvNP)
Longest cursed win for white: 106 ply; 8/8/4P3/3p1P2/8/6b1/8/6N1 w - - (expected dtz: 106, got: 102, NPPvBP)
Longest cursed win for white: 106 ply; 4k3/P6N/1P6/8/8/8/8/k7 b - - (expected dtz: -106, got: -101, NPPvKK)
Longest cursed win for white: 105 ply; 3k4/7P/p7/8/8/1N6/5P2/8 w - - (expected dtz: 105, got: 102, NPPvKP)
Longest cursed win for white: 106 ply; 5N2/1P6/8/8/8/2P5/7q/k7 b - - (expected dtz: -106, got: -101, NPPvKQ)
Longest cursed win for white: 104 ply; 8/5P2/8/5P2/8/q1p5/6N1/8 b - - (expected dtz: -104, got: -101, NPPvQP)
Longest cursed win for white: 107 ply; 8/3P4/8/p7/r7/2P5/5N2/8 b - - (expected dtz: -107, got: -101, NPPvRP)
Longest cursed win for white: 102 ply; 8/1PP1k3/8/4P3/1p6/8/8/8 b - - (expected dtz: -102, got: 102, PPPvKP)
Longest cursed win for white: 106 ply; 8/Q1P5/2P5/8/8/5N2/8/2k5 w - - (expected dtz: 106, got: 102, QNPPvK)
Longest cursed win for white: 105 ply; 3B4/2P1P3/8/R7/8/2k5/8/8 b - - (expected dtz: -105, got: -101, RBPPvK)
Longest cursed win for white: 105 ply; 8/1PR1P3/8/N4k2/8/8/8/8 b - - (expected dtz: -105, got: -101, RNPPvK)
Longest cursed win for white: 104 ply; 2N4n/3P4/8/8/8/R7/8/5k2 b - - (expected dtz: -104, got: -101, RNPvKN)
Longest cursed win for white: 104 ply; 2N5/3P4/8/8/5n2/8/5p2/7R w - - (expected dtz: 104, got: 101, RNPvNP)
Longest cursed win for white: 103 ply; n7/5P2/4P3/8/8/8/2p5/7R w - - (expected dtz: 103, got: 101, RPPvNP)

[syzygy]

With "one side has only pawns" excluded (DTZ is trivial in that case anyway) only a couple of stats positions in cursed territory remain broken.

WDL tables that need to store the same WDL or DTZ value for all positions (as determined by probe_wdl_table(), so after sorting out captures etc.) store just a single value.

For DTZ tables the same is done, except that the generator seems not to store the value (or rather values: they might be different win/cursed win/blessed loss/loss positions).

Unfortunately, "guessing" the right value might be a bit more tricky than I had initially hoped. With the help of the stats it should be possible though and in theory they could be used to fix the 80-byte TB files. For example the stats for KQNvQB are this:

Code: Select all

########## KQNvQB ##########

White to move:

31917632 positions win in 1 ply.
33281532 positions win in 2 ply.
95 positions win in 4 ply.

65199259 positions are wins.
1329566 positions are draws.
47840535 positions are losses.

47827348 positions lose in 1 ply.
8847 positions lose in 2 ply.
4316 positions lose in 3 ply.
8 positions lose in 4 ply.
16 positions lose in 5 ply.

Black to move:

47774166 positions win in 1 ply.
19314330 positions win in 2 ply.
10 positions win in 3 ply.
27 positions win in 4 ply.

67088533 positions are wins.
914916 positions are draws.
46365911 positions are losses.

46365400 positions lose in 1 ply.
511 positions lose in 3 ply.

The TB file only stores black-to-move. The win-in-1 positions win by capture. The win-in-2 positions win by threats. So for these positions arbitrary values may be stored. What is left are win-in-3 and win-in-4, and these are all mapped to the value 1 (0 -> 1/2 ply, 1-> 3/4 ply, etc.). Similarly, lose-in-1 positions are captures so what is left is lose-in-3, which is mapped to 1. So here returning 1 is correct.

If a side only has pawns, then everything has dtz=1, so returning 0 is correct.

This seems to cover at least wins and losses.

It seems possible though that tables exists where both sides have pawns and pieces, max dtz = 2 and some win-in-2 positions are not won by a winning threat move but by a move that "forces" the other side to play a losing pawn move. But that could only happen in rare positions where all piece moves for the other side are blocked by pawns or other pieces. Such rare positions exist, but do they occur in tables with max dtz = 2? If they do, then returning 1 (-> 3/4) would be be incorrect.

A quick check shows that all tables with 2 ply as longest win for white or black either have only pieces or one side with only pawns. So I think we should be OK here...

Now I'll have a look at the cursed win problems.

[syzygy]

These work OK for me:

Longest cursed win for white: 109 ply; 8/2P5/b5B1/8/4N3/8/8/k7 w - - (expected dtz: 109, got: 65535, BNPvKB)
Longest cursed win for white: 114 ply; 5q2/4k3/8/8/8/8/8/1K2B2N b - - (expected dtz: -114, got: 102, KBNvKQ)
Longest cursed win for white: 102 ply; 3q4/8/8/7K/6N1/8/p7/2K5 b - - (expected dtz: -102, got: 102, KKNvQP)
Longest cursed win for white: 102 ply; 8/1PP1k3/8/4P3/1p6/8/8/8 b - - (expected dtz: -102, got: 102, PPPvKP)

In the 3rd and 4th positions, you somehow seem to get the wrong sign for the WDL value. The same problem might explain the 2nd position and somehow also the 1st position.

Unfortunately, the others are caused by a bug in the generator. The values for cursed win and blessed loss position are all mapped to 0 in some (but not all) pawnful tables.

This fixes it (at least it works for BPPvQP):
https://github.com/syzygy1/tb/commit/96 ... 2551562b25

I think the bug affects all pawnful DTZ tables with a longest cursed win of 103, 104, 105, 106 or 107. Positions with dtz = 101 and 102 are dealt with correctly anyway and if the longest cursed win is 108 or higher, then a complicated mechanism kicks in to avoid overflows in the table being generated and other code is doing the mapping which does not have this bug. Also pawnless tables are fine.

[syzygy]

When regenerating DTZ tables, time can be saved by passing -z to the generator to skip generation of WDL tables.

Just to be clear, this bug is unrelated to the problem with 80-byte TB files. I think that problem can be worked around as we already discussed.

Thanks for all your testing!

[syzygy]

I think the bug affects all pawnful DTZ tables with a longest cursed win of 103, 104, 105, 106 or 107. Positions with dtz = 101 and 102 are dealt with correctly anyway and if the longest cursed win is 108 or higher, then a complicated mechanism kicks in to avoid overflows in the table being generated and other code is doing the mapping which does not have this bug. Also pawnless tables are fine.

Ouch, it is more complicated. Even if max dtz >= 108 with the leading pawn in one file, it can be <= 107 with the leading pawn in another file. So just looking at max dtz as stated in the stats file is not sufficient.

Finding out whether a particular table is affected by the bug by decompressing the TB file also seems highly untrivial.

This is annoying

It seems 1214 out of 4830 pawnful 2/3/4/5/6-piece tables are potentially affected in case of suicide (but I did not filter out those with max dtz <= 102).

[syzygy]

Finding out whether a particular table is affected by the bug by decompressing the TB file also seems highly untrivial.

Actually, the table file header should contain sufficient information to do this.

It might also be possible to skip the generation of unaffected "a/b/c/d-file" tables within a pawnful TB table, but that might be too tricky to get right.