Stalemate Tablebases

Discussion of chess software programming and technical issues.

Moderators: hgm, Dann Corbit, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Dries
Posts: 9
Joined: Sun Jan 17, 2021 10:26 am
Full name: Dries De Clercq

Stalemate Tablebases

Post by Dries » Sun Feb 21, 2021 8:31 am

Recently, I discovered that you could have a "stalemate in 1" just like you can have a "mate in 1".

Here's a nice example of a stalemate in 1.



It's black to move and black would be lost unless he goes for the stalemate. So it makes complete sense to go for it. And black can do so. Notice that black can still move all of his 3 pieces. But after one move, black will be stalemated. Black would play 1. ...Ba3-b4+. It's the only move that would get him a draw. Now the white king is under attack and there's only one legal move for white, to capture the black bishop. White plays 2.Ka5xb4. And all the sudden, black is stalemated. It's almost like a victory for black although it's just a draw.

Here's an example of a stalemate in 2.



These things made me wonder. Did anyone ever made a tablebase to find all the stalemates that can be forced for a certain number of pieces?
And what would be the deepest stalemate that could be found in some particular endgame?

I don't think it's that important to build such a tablebase. But I find it very interesting. I was already considering building my own by adjusting the gaviota tablebases, since the source code was available and since it featured DTM (distance to mate).

I thought about just replacing "checkmate" with "stalemate". I mean, instead of finding all the possible checkmates from where you'd build your tablebases from, using retrograde analysis, you could start with finding all the possible stalemates. And then you could move back. What are all the positions in which one player cannot avoid a stalemate? Those would be, I suppose, "- Stalemate in 1" instead of "- Mate in 1". And from there, you could find all the positions from where you can reach a "- Stalemate in 1". And so on. So one side would want to avoid the stalemate while the other side would want to achieve it. Quite the same as with regular tablebases, but by substituting "checkmate" with "stalemate". There's some difference. Cause the player who achieves a checkmate moves last. While the player who achieves a stalemate, doesn't move last.

This would perhaps be simple enough and quite interesting by itself. Though it's not without problems. What if you can force a stalemate while you could actually have won with some other move? You'd find such positions when building such a tablebase while such positions do not seem to make to much sense. I suppose you could filter them out. That would be better already.

But there are other issues as well. What if one side could avoid giving the stalemate but he would get checkmated instead? Such positions wouldn't be found either with the previous approach. Even though it would make sense to give the stalemate to the other side if you'd lose otherwise.

One other more optional issue is this: What if one side can force a stalemate for himself even though he could have forced another way of achieving a draw? Cause why would you go for a "Stalemate in 5" or a "Stalemate in 10" if you can achieve a draw by some simple repetition?

I thought about doing these things myself at first. But that would be a bit too hard. But I guess you never know, perhaps some people would really want to achieve such a tablebase. It's far less important than a regular tablebase. But I think it would be much smaller though. And I'm sure the results would be very interesting.

Dries
Posts: 9
Joined: Sun Jan 17, 2021 10:26 am
Full name: Dries De Clercq

Re: Stalemate Tablebases

Post by Dries » Sun Feb 21, 2021 11:50 am

Oh yeah... and here's a stalemate in 4. But black could also reach a draw by repetition.



1. ...Kc6 2. Kb8 Rb7 3. Ka8 Ra7 4. Kb8 Ra8 5. Kxa8

I found these positions while searching for underpromotions. In this position, white should have promoted to a Rook instead of a Queen.

User avatar
Guenther
Posts: 3807
Joined: Wed Oct 01, 2008 4:33 am
Location: Regensburg, Germany
Full name: Guenther Simon
Contact:

Re: Stalemate Tablebases

Post by Guenther » Sun Feb 21, 2021 6:55 pm

Dries wrote:
Sun Feb 21, 2021 8:31 am
...

These things made me wonder. Did anyone ever made a tablebase to find all the stalemates that can be forced for a certain number of pieces?
And what would be the deepest stalemate that could be found in some particular endgame?

I don't think it's that important to build such a tablebase. But I find it very interesting. I was already considering building my own by adjusting the gaviota tablebases, since the source code was available and since it featured DTM (distance to mate).

I thought about just replacing "checkmate" with "stalemate". I mean, instead of finding all the possible checkmates from where you'd build your tablebases from, using retrograde analysis, you could start with finding all the possible stalemates. And then you could move back. What are all the positions in which one player cannot avoid a stalemate? Those would be, I suppose, "- Stalemate in 1" instead of "- Mate in 1". And from there, you could find all the positions from where you can reach a "- Stalemate in 1". And so on. So one side would want to avoid the stalemate while the other side would want to achieve it. Quite the same as with regular tablebases, but by substituting "checkmate" with "stalemate". There's some difference. Cause the player who achieves a checkmate moves last. While the player who achieves a stalemate, doesn't move last.

This would perhaps be simple enough and quite interesting by itself. Though it's not without problems. What if you can force a stalemate while you could actually have won with some other move? You'd find such positions when building such a tablebase while such positions do not seem to make to much sense. I suppose you could filter them out. That would be better already.

But there are other issues as well. What if one side could avoid giving the stalemate but he would get checkmated instead? Such positions wouldn't be found either with the previous approach. Even though it would make sense to give the stalemate to the other side if you'd lose otherwise.

One other more optional issue is this: What if one side can force a stalemate for himself even though he could have forced another way of achieving a draw? Cause why would you go for a "Stalemate in 5" or a "Stalemate in 10" if you can achieve a draw by some simple repetition?

I thought about doing these things myself at first. But that would be a bit too hard. But I guess you never know, perhaps some people would really want to achieve such a tablebase. It's far less important than a regular tablebase. But I think it would be much smaller though. And I'm sure the results would be very interesting.
I found your post quite interesting. Stalemate really is something special and a lot of people simply dislike it, as it can be considered
a bit alien, or a discontinuity inside chess rules (because it is awarded half a point).

Also searching for longest forced stalemates has some charm.

Your post inspired me to filter stalemates (with pgn-extract) out of some quality (computerchess) database and then looking at the gamelist done by SCID, because here I can see immediately how much material is left in the end position and positions with more material left are much more
interesting positions than certain endgames which simply result in stalemate by best play (pawn opposition, 2N, B+blind pawn etc.)

The first one I found (with more end material) is already very entertaining. I included the pgn too, because it shows that even very strong
programs have problems with the unexpected (probably pruning of seemingly 'crap moves'). The pgn shows the big evals until the plot
was revealed. 81...c2?? just draws and fails to forced stalemate!





Huge problems for SF12 finally starting a big fail low since depth 33

(for readabilty I have kept just the main depth lines until depth 33)

Code: Select all

Version: WinBoard 4.9.1 + Stockfish_12-64
2410 >first : memory 272
2410 >first : egtpath syzygy C:\Syzygy_5
2410 >first : setboard r4k2/3p3Q/3Pbq2/7R/5p2/2p2P2/5B2/6K1 b - - 5 1
5090 <first : 0 0 0 0 NNUE evaluation using nn-82215d0fd0df.nnue enabled

5090 <first :   1     366      0        121 f6g7 h7g7 f8g7
5090 <first :   2     514      0        173 f6g7 h7g7 f8g7 g1h2
5100 <first :   3     385      0        253 f6g7 h7g7 f8g7 g1h2 a8f8
5100 <first :   4     432      0        362 f6g7 h7g7 f8g7 f2d4 g7g6 d4c3
5100 <first :   5     462      0        455 f6g7 h7g7 f8g7 f2d4 g7g6 d4c3
5100 <first :   6     448      0       1845 a8a2 g1g2 f6g7 h7g7 f8g7 h5c5 a2c2
5100 <first :   7     397      0       2552 a8a2 g1g2 f6g7 h7g7 f8g7 h5c5 a2c2 c5g5 g7f6 g5c5
5100 <first :   8     455      1       3573 a8a2 g1g2 a2d2 h5c5 d2f2 g2f2
5110 <first :   9     395      2       7603 a8a1 g1g2 a1a2 h7h8 f6h8 h5h8 f8f7 h8c8 a2c2 c8c7 f7g6 c7c5
5110 <first :  10     460      3      10921 a8a1 g1g2 a1a2 h7h8 f6h8 h5h8 f8f7 h8c8 c3c2
5160 <first :  11     167      8      33064 a8c8 h5c5 c8c5 h7e7 f6e7 d6e7 f8e7 f2c5 e7f7 c5d6 e6d5 d6f4 d5f3
5210 <first :  12     440     12      53323 a8a1 g1h2 c3c2 h5c5 c2c1q c5c1 a1c1 h7e7 f6e7 d6e7 f8e7
5270 <first :  13     314     18      85656 a8a1 g1g2 a1a2 h7e7 f6e7 h5h8 f8f7 h8h7 f7g6 d6e7 a2a8 f2d4 g6h7 d4c3 e6f7 g2g1 a8a2
5310 <first :  14     437     22     104393 a8a1 g1h2 c3c2 h5c5 c2c1q c5c1 a1c1 h7e7 f6e7 d6e7 f8e7
5540 <first :  15     189     45     217682 a8a1 g1h2 c3c2 h7c2 a1a2 c2c5 f6g6 h5h8 f8f7 h2h1 a2a1 h1h2 a1f1 c5d4 g6f5 d4c5 f5c5 f2c5 f1f3
6800 <first :  16      38    171     774919 f6g7 h7g7 f8g7 h5c5 a8a1 g1g2 a1d1 c5c3 g7f6 c3c8 f6f5 f2c5 f5e5 g2f2 d1a1 c8d8 a1a2 f2e1
7730 <first :  17      28    265    1160999 f6g7 h7g7 f8g7 h5c5 a8a1 g1g2 a1d1 c5c3 e6d5 f2h4 g7g6 g2f2 d1h1 h4e7 h1h2 f2g1 h2d2 g1f1 d2d4 f1e1 d5c6 e1e2 d4b4
8750 <first :  18      54    366    1601004 a8a1 g1h2 a1a2 h5c5 f6g7 h7h4 g7g3 h4g3 f4g3 h2g3 c3c2 f3f4 e6b3 f2d4 a2a4 d4b2 f8f7 g3f3 f7e6 f3e3 e6d6 c5h5 a4b4 h5g5
9210 <first :  19     100    413    1821635 a8a1 g1h2 f6g7 h7e4 c3c2 e4f4 f8e8 h5b5 a1b1 b5a5 e6d5 a5d5 c2c1q f4e4 e8d8 f2h4 d8c8 d5c5 c8b8 c5c1 b1c1 h4f2 g7h6 h2g2 h6d6 e4e3
10270 <first :  20      50    519    2314592 c3c2 h7c2 f6g7 g1h1 a8a1 h1h2 a1a2 h5f5 f8g8 c2c8 g8h7 f5h5 h7g6 c8c5 g7f6 h2g2 e6f5 h5h2 a2c2 c5b4 g6g5 g2f1 f5d3 f1g1 f6a1 b4e1 a1e1 f2e1
10330 <first :  21     141    524    2339869 c3c2 h7c2 f6g7 g1h1 a8a1 h1h2 a1a2 h5f5 f8g8 c2c8 g8h7 f5h5 h7g6 c8c5 g7f6 h2g2 e6f5 h5h2 a2c2 c5b4 f5d3 b4a3 f6g5 g2h1 g5d5 h2g2 g6f5 a3a4 d5f3 a4d7 f5e5
10460 <first :  22     405    537    2413901 c3c2 h7c2 f6g7 g1h1 a8a1 h1h2 a1a2 c2a2 e6a2 h5f5 f8e8 f5f4 g7h6 f4h4 h6d6 h2g2 d6d2 h4e4 e8d8 g2g3 d2g5 e4g4
10790 <first :  23     371    570    2619152 c3c2 h7c2 f6g7 g1h1 a8a1 h1h2 a1a2 h5f5 f8g8 c2c8 g8h7 f5h5 h7g6 c8c5 a2f2 h2g1 f2c2 c5g5 g6f7 g5g7 f7g7 h5h4 g7f6 h4f4 f6e5 f4a4 e6d5 f3f4 e5e6 a4a3 c2g2 g1f1 g2g4 f1e1 g4f4
11630 <first :  24     455    655    3237267 c3c2 h7c2 f6g7 g1h1 a8a1 h1h2 a1a2 h5f5 f8g8 c2c8 g8h7 f5h5 h7g6 c8c5 a2f2 h2g1 f2c2 h5g5 g6h6 g5g7 c2c5 g7g2 c5g5 g1f2 g5g2 f2g2 h6g6 g2g1 g6f6 g1f1 f6e5 f1e1 e5d6
12880 <first :  25     494    779    4196397 c3c2 h5c5 a8a1 g1h2 c2c1r h7e7 f6e7 d6e7 f8e7 c5c1 a1c1 f2d4 e7d6 h2g2 e6d5 d4f6 d6e6 f6g7 e6f5 g7f8 d5f3 g2f3 c1c3 f3f2 f5e4
13940 <first :  26     512    885    4966979 c3c2 h5c5 a8a1 g1g2 c2c1q h7e7 f6e7 d6e7 f8e7 c5c1 a1c1 f2h4 e7d6 g2f2 c1c2 f2e1 e6d5 e1d1 c2h2 h4g5 d5f3 d1c1 d6e5 g5e7 h2g2 e7b4 d7d5 b4c3 e5e4
16720 <first :  27     553   1163    7113918 c3c2 h7c2 f6g7 g1h1 a8a1 h1h2 a1a2 c2a2 e6a2 h5f5 f8e8 f5f4 a2d5 h2h3 d5e6 h3h2 g7h6 f4h4 h6f6 h2g3 f6g5 h4g4 e6g4 f3g4 g5e5 g3f3 e5d6 g4g5 e8f7 f2e3 d6d5 f3g3 d5d3 g3f4 f7e6 g5g6 d3f5 f4g3
19030 <first :  28     551   1394    8801026 c3c2 h7c2 f6g7 g1h1 a8a1 h1h2 a1a2 c2a2 e6a2 h5f5 f8e8 f5f4 a2d5 h2h3 d5e6 h3h2 g7e5 h2g3 e5g5 f4g4 e6g4 f3g4 g5e5 g3f3 e5d6 f2e3 e8f7 f3e2 d6c6 g4g5 c6e4 e2f2 f7e6
22320 <first :  29     569   1723   11219094 c3c2 h7c2 f6g7 g1h1 a8a1 h1h2 a1a2 c2a2 e6a2 h5f5 f8e8 f5f4 a2d5 h2h3 d5e6 h3h2 g7e5 h2g3 e5g5 f4g4 e6g4 f3g4 g5e5 g3f3 e5d5 f3g3 d5d3 g3f4 d3d6 f4e4 e8f7 e4f3 d6d3 f3f4 d7d5 f2h4 f7e6 h4d8 d5d4 g4g5 d3f5 f4g3 d4d3
24810 <first :  30     569   1972   12986720 c3c2 h7c2 f6g7 g1h1 a8a1 h1h2 a1a2 c2a2 e6a2 h5f5 f8e8 f5f4 a2d5 h2h3 d5e6 h3h2 g7e5 h2g3 e5g5 f4g4 e6g4 f3g4 g5e5 g3f3 e5d5 f3g3 d5d3 g3f4 d3d6 f4e4 e8f7 e4f3 d6d3 f3f4 d7d5 f2h4 f7e6 h4d8 d5d4 f4g5 d3c4 g5g6 d4d3
32290 <first :  31     579   2721   17991535 c3c2 h7c2 f6g7 g1h1 a8a1 h1h2 a1a2 c2a2 e6a2 h5f5 f8e8 f5f4 a2d5 h2h3 d5e6 h3h2 g7e5 h2g3 e5g5 f4g4 e6g4 f3g4 g5e5 g3f3 e5d5 f3f4 d5d6 f4e4 e8f7 e4f3 d6d3 f3g2 f7e6 f2h4 d3e4 g2g3 e4e3 g3g2 d7d5 h4d8 d5d4 g4g5
47270 <first :  32     652   4218   28427499 c3c2 h7c2 f6g7 g1h1 a8a1 h1h2 a1a2 c2a2 e6a2 h5f5 f8e8 f5f4 a2d5 f2h4 g7b2 h2g3 b2c1 h4e7 c1g1 g3h4 g1f2 h4h5 d5f7 h5h6 f2d2 h6g5 f7e6 e7f6 d2e3 f6d4 e3e2 g5g6 e2g2 g6f6 g2h2
49160 <first :  33     644   4408   29522452 c3c2 h7c2
49170 <first : ?
49570 <first :  33     636   4448   29767364 c3c2 h7c2
49570 <first : ?
49950 <first :  33     624   4486   29974770 c3c2 h7c2
49950 <first : ?
50410 <first :  33     606   4532   30268826 c3c2 h7c2
50410 <first : ?
51140 <first :  33     581   4606   30711328 c3c2 h7c2
51150 <first : ?
52270 <first :  33     549   4719   31247951 c3c2 h7c2
52280 <first : ?
https://rwbc-chess.de
HGM@'chessqueen' 2018-present, aka: 'George' 2013-2016, 'pichy' 2006-2013, 'Jorge Pichard' 2000-2006 (old forum) wrote: http://talkchess.com/forum3/viewtopic.p ... 79#p789713

User avatar
Guenther
Posts: 3807
Joined: Wed Oct 01, 2008 4:33 am
Location: Regensburg, Germany
Full name: Guenther Simon
Contact:

Re: Stalemate Tablebases

Post by Guenther » Sun Feb 21, 2021 7:15 pm

This is beautiful too! 67.Qxe6?? leads to forced stalemate draw.



https://rwbc-chess.de
HGM@'chessqueen' 2018-present, aka: 'George' 2013-2016, 'pichy' 2006-2013, 'Jorge Pichard' 2000-2006 (old forum) wrote: http://talkchess.com/forum3/viewtopic.p ... 79#p789713

Dries
Posts: 9
Joined: Sun Jan 17, 2021 10:26 am
Full name: Dries De Clercq

Re: Stalemate Tablebases

Post by Dries » Sun Feb 21, 2021 7:32 pm

Those are impressive stalemates. When I look at them, they made little sense at first just as well. Seems like senseless sacrifices. But they're not. I can imagine a chess engine may look over such "weird moves".

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

Re: Stalemate Tablebases

Post by hgm » Sun Feb 21, 2021 9:31 pm

The FairyGen EGT generator has an option to consider stalemating a win. But not one to consider it a loss. Like you say, it is an entirely different case, with the opposit player to move.

I suppose it would have to be done by first doing the initialization for the reverse end-game, to find the stalemates. And then build the EGT for the end-game itself, but seed the identified stalemates as wins for the stalemated side. Depending on the way you want to treat checkmates by that side, you could also seed these as wins in the normal way, or use the stalemated positions as the only won seeds. And then start the retrograde generation from there.

I did something similar once for identifying 'fortress draws'. Which I defined as ways for the weak side to prevent losing that would not capture one of the pieces of the strong side. (Which would be 'tactical draws'.) I did that by first generating the EGT for the reverse end-game, while treating every conversion to a non-lost position in a successor end-game with fewer pieces for the strong side(as well as normal checkmates) as a win. What then is left as a non-win must be a fortress draw.

Dries
Posts: 9
Joined: Sun Jan 17, 2021 10:26 am
Full name: Dries De Clercq

Re: Stalemate Tablebases

Post by Dries » Mon Feb 22, 2021 10:24 am

Yes, I seem to understand a bit what you mean about your strategy of finding fortresses. Cause when a piece is captured in a fortress, it's not a loss for the weak side. So by first finding the captures that result in a win for the strong side, those that remain could then later on be seen as a win for the side who wants to achieve the fortress. I'm not totally sure I understand though. I sure have some difficulty in relating this to these stalemate tablebases. I didn't think it totally through. But I thought about it a bit more and I see one way of doing it.

It would also be to start out with computing all the possible stalemates. And then to work back. The one who moves last (and first when working backwards), would be the side that wants to avoid the stalemate. But there would be some positions in which that side could avoid the stalemate but that side would then get checkmated instead. And it would, of course, be preferable to not avoid the stalemate if you'd lose instead. So the positions that would loose, would have to be known already. So the regular tablebases should be probed as well. And if the side that wants to avoid the stalemate, cannot avoid the stalemate unless that side would get checkmated instead, those positions should be added to the stalemate tablebases.

After computing all those "- Stalemates in 1", the other side takes his turn. The other side wants to achieve the stalemate. But it wouldn't make much sense to achieve the stalemate if you could win instead. So I guess you could probe the regular tablebases to find out which positions would be winning. Those should be excluded.

But not only should we have to exclude the positions that would be winning. Cause it wouldn't make to much sense either to go for a forced stalemate if you can get a draw in some other way. So the side that wants to achieve the stalemate, should only be able to make a move which would result in a position that would lead to a forced stalemate or to a loss. Which would then mean that the only best move for the side that wants to achieve the stalemate, would be to go for the forced stalemate. And since the positions that are drawn, are not in the regular tablebases, all drawn positions are actually known.

So it's possible to do all of this if you'd have the regular tablebases already at your disposal when building the stalemate tablebases.

But honestly, I'm a lousy programmer. Would take me quite a bit of effort to achieve such a thing. If I'd achieve it at all. I don't think I'd be doing it for the time being. It's of course, all open for anyone to do it.

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

Re: Stalemate Tablebases

Post by hgm » Mon Feb 22, 2021 10:58 am

Indeed, if you would consider being stalemated an inferior outcome to delivering checkmate, but still preferable over fortress draws, (which in practice must end in repetition or 50-move draws) I would do it by first generating the regular EGT which would give Distance to Mate, and only after that start calculating back from the stalemates, using still higher DTM codes. E.g. use the code that otherwise would have meant mate-in-60 (if no real mate took that long) for indicating stalemated-in-0 (= stalemated), but not winnable by checkmate.

This is a technique you could use in general for games with a more diversified outcome than win/draw/loss: start generating the EGT for the highest-rewarded game end, and when that finishes, continue with the next-highest reward, using the remaining 'distance-to-success' codes, etc. That way the DTx codes would still correspond to the desirability of the position.

My EGT generators usually only keep only one bit of information for the 'strong' side on move (indicating 'won' or 'other'), and the process starts by setting to 'won' the positions where the strong side can capture the weak King. After that all moves of the weak side that would go to such a position are not just losing, but actually illegal. (In any later iteration that would not be true, as many perfectly legal moves can also be losing.) So when I test all weak-side-on-move positions for the first time to see whether they (still) have a non-losing move, and they have none, they are not automatically lost (as they would be in later iterations), but are mates. I then have to check whether that position would be won won with the strong side on move to determine if it is a checkmate or a stalemate. Normally only the checkmates would be labeled as losses (DTM=0), and the generation process would continue from those. The stalemates would forever remain 'undecided', which when the generation process runs out of steam automatically means 'not won'.

In your case you could already label the stalemates with DTM code 60 (say), and after the generation process runs out of steam at DTM < 60, restart it from DTM = 60. (Normally it operates on DTM=N to generate all DTM=N+1, for ever increasing N.)

Dries
Posts: 9
Joined: Sun Jan 17, 2021 10:26 am
Full name: Dries De Clercq

Re: Stalemate Tablebases

Post by Dries » Mon Feb 22, 2021 1:35 pm

Yeah, generating both makes sense and using a high DTM to start from for the stalemates, makes sense too. Makes it a bit simpler. Thanks.

So umm.. how did it go, when generating the fortresses? Did you discover a lot?

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

Re: Stalemate Tablebases

Post by hgm » Mon Feb 22, 2021 1:58 pm

Not really; I mainly used it to prove there were none. I needed that to get a better interpretation on which combinations of pieces were able to beat which other combinations. Especially with powerful pieces a 3+2-men end-game (E.g. KQBKQ) has an enormous number of non-wins, making it very hard to judge whether it was a generally won or a generally drawn end-game. I needed a method to determine whether these where due to the attacker quickly losing a piece by tactics, or whether the single piece was really able to hold out indefinetely (fortress draw). And I wasn't doing that for orthodox Chess pieces, but for the various pieces of Chess with Different Armies, in order to prepare the 'drawishness' table for my engine KingSlayer-CwDA.

Post Reply