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

Algorithm is unsound #41

Closed viktpal closed 1 year ago

viktpal commented 1 year ago

The semi-static algorithm is unsound because it doesn't take into account possible pawn checkmate from outside the king's region. Example:

image 1b3kBR/4pP1P/1p1pP2P/1P1P4/8/K5p1/6P1/1B6 b - - white

The output of the algorithm is “unwinnable”, which is not true.

miguel-ambrona commented 1 year ago

Thanks for this! This is remarkably the first counterexample to the soundness of the tool.

I didn't have pawn attacks into account when identifying visitors to the king's region. Here is a fix: https://github.com/miguel-ambrona/D3-Chess/pull/42

I'll merge it in about 24 h in case you want to have a look before that.

viktpal commented 1 year ago

It seems to be working great now. Similar example:

image

8/1p3b2/pPp1p1p1/BkP1P1P1/1P6/BPB5/PKP5/8 b - - white

miguel-ambrona commented 1 year ago

Great, thanks!