search

miguel-ambrona / D3-Chess

Chess Unwinnability Analyzer is an implementation of a decision procedure for checking whether there exists a sequence of legal moves that allows a certain player to checkmate their opponent in a given chess position.
https://chasolver.org
GNU General Public License v3.0
51 stars 8 forks source link

More unidentified dead positions #40

Open viktpal opened 1 year ago

viktpal commented 1 year ago

The tool doesn't identify following dead positions:

image 8/B4b2/2k5/1p1p4/1P1Pp1pB/1pp1P1P1/1p6/bK3b2 b - - white

image 8/2b4B/4k3/8/8/2p1p1p1/2PpP1P1/1B1K3n b - - white

image

B2b4/8/4k3/8/1p1p1p1p/1PpP1P1P/K1P4b/RB6 b - - white
B2b4/8/4k3/8/1p1p1p1p/1PpP1P1P/K1P4b/RB6 b - - black
miguel-ambrona commented 1 year ago

Great positions! They show you have a clear understanding of how the current static algorithm works and its weaknesses.

Do you have any idea on how to address them with minor changes? For the first 2, I do. The last one seems trickier.

viktpal commented 1 year ago

I understand the idea of the algorithm, but I haven't gone into all the details of the implementation.

In the 3rd example, the only way to unblock the position (allow wK and wB to move) is to capture the white rook. I don't know if minor changes would be enough for the static algorithm to detect this.

viktpal commented 1 year ago

Another example similar to the last one: image

8/2b5/8/4k2B/1p1p4/1P1Pp1p1/4P1P1/2b2BRK b - - black
8/2b5/8/4k2B/1p1p4/1P1Pp1p1/4P1P1/2b2BRK b - - white
viktpal commented 1 year ago

The static algorithm cannot detect unwinnability in this simple position either: image 1b2k3/8/1p2K3/bP6/Pp6/1Pp5/B1P5/NB6 b - - white

The algorithm does not take into account that pieces that cannot move cannot mate. It is easy to improve the algorithm by adding an additional check in the SemiStatic::System::is_unwinnable():

if (!(visitors & ~blocked_pieces))
   return true;

I just don't know the most efficient way to get block_pieces (pieces that cannot move) because I haven't delved into all the details of the algorithm yet.

miguel-ambrona commented 1 year ago

In the 3rd example, the only way to unblock the position (allow wK and wB to move) is to capture the white rook. I don't know if minor changes would be enough for the static algorithm to detect this.

Yes, I don't know either. The static algorithm can realize that the rook can be captured, but it cannot guarantee that there is no other way the rook can "free" its current square (a1).

miguel-ambrona commented 1 year ago

1b2k3/8/1p2K3/bP6/Pp6/1Pp5/B1P5/NB6 b - - white

This one should be doable as you suggest. I'll develop a fix soon.

viktpal commented 1 year ago

My previous suggestion is not suitable for the following position: 1b2k3/8/1p2K3/bP6/Pp6/1Pp4B/B1P5/NB6

I think it would be better to exclude the pieces that cannot move from visitors.

viktpal commented 1 year ago

The static algorithm can realize that the rook can be captured, but it cannot guarantee that there is no other way the rook can "free" its current square (a1).

I think that the static algorithm could separately consider the case where only one capture of unmovable piece is possible in the position. For this, the initialization of variables (System::saturate() function) can be divided into several stages:

  1. In the first stage, consider only moves that are not captures, and captures of such pieces that can move. Repeat until there are no such moves left.
  2. Next, determine the number of possible captures of unmovable pieces. If there are no possible captures, the function would end.
  3. If there are multiple possible captures, the algorithm would continue as in its current implementation.
  4. If there is only one possible capture, then: (a) check whether it is possible to achieve mate without making further captures. If mate is possible, the function would end (is_unwinnable() would return false); (b) remove the piece from further consideration and continue as in the current implementation. However, other previously blocked pieces may be captured in subsequent steps.

Such improvement should also work for positions where only one capture of unmovable piece is possible at the beginning, but later there may be more captures, as in the following example:

image 1k4b1/1P1p4/BP1Pp1p1/1P2P1P1/p7/PpB5/1P1B4/K7

The current tool returns "undetermined", but if the first captured piece bPa4 were removed from the position, the result would be "unwinnable". Clearing square b3 would not affect the result.

andrew-buchanan commented 1 year ago

Wow these are cool positions, and very instructive (even though the last happens to be illegal). I'm sorry I haven't gone into the algorithm in enough depth