14

Given a board position, there are programs that try to find a series of legal moves that lead to it.

Are there algorithms that can do the opposite - prove that the position is not reachable by a series of legal moves?

Proof by exhaustion doesn't seem possible in the general case due to the size of the search space, but are there other methods?

2
  • Since I'm not that much of an expert at chess I thought it would be interesting to answer this a bit more from the algorithm side. The problem is that by design the algorithm has to work in a way that it can track valid moves and boards because proving this as a negative is trying to prove an unknowable. Any algorithm that would try to prove the negative would start with a basic chessboard layout and keep playing until you can say that the expected end can't be reached. But the problem is that there are always games where there are always moves to be made, no matter how arbitrary or repeated,
    – skippy
    Jul 14 at 13:02
  • 1
13

Easy illegality is easy: not exactly 1 king on both sides, both kings in check, pawns on the final ranks. It's also fairly easy to tally promoted material and subtract the missing pawns. A quick captures test, together with the pawn structures, is also possible.

An impossibility of last move test, even if only cursorily, is already tricky.

A full test is NP-hard (in whatever sense), I fear. There are many chess problems asking "Legal?" and they can be fiendlishly hard. (Note that the mentioned programs have no chance against them.) In any case, a quick illegality test is far easier than a quick legality test, if the position looks even remotely doubtful.

2
  • Comments are not for extended discussion; this conversation has been moved to chat.
    – Brian Towers
    Jul 15 at 15:49
  • The problem for generalised chess could be in co-NP, as a sequence of legal moves to the position is a counterexample (certificate to the complement class). It depends on how the max length of a legal sequence varies by board size. If it's in co-NP then it's not likely to be NP-hard, but could be co-NP complete.
    – A.M.
    Jul 15 at 23:34
4

The only way to decide, apart from obvious cases, is to use backtracking. In doing so, you are basically exhaustively checking each possible move and making a series of moves that would lead to that position. This is no less complex than going forward. Actually, including en passant, promotion, castling, not castling, and capturing a possible piece at any given position it is even more complicated. (Not much of an algorithm, it is just brute force which is the name of the actual algorithm.)

The reason it is more complicated than analyzing possible positions is that some of the positions done in reverse may actually be impossible themselves. But then, it is sufficient to find only one possible chain of moves to claim that a position is possible. The rest of the analysis is more or less wasted.

At the moment we have the 7-piece end game library and we are trying to create the 8-piece library and that will be very likely it. As you can see, even if we reach a 10-piece end game library that is not enough to cover all regular situations let alone irregular ones.

Note that it is a very big problem that you ask only about possible positions, disregarding the fact that people might never play and reach those positions. That is simply throwing away all heuristics that we have, which are designed for regular play style, where you want to win.

I would argue that in general way too many reachable positions are possible, but all totally unrealistic. So instead of going backward for each such position I would probably still go forward simply ignoring all the rules about winning or losing and just trying to arrange figures to get to that position.

This analysis might actually reveal that only some set of positions are impossible, regarding for example pawn structure, but the remaining figures as long as there are no two white bishops etc. are much more flexible. This is basically so, because by disregarding pawn structure you could revert each figure to its initial position first and then if this is so for all positions, only then think about if it is possible that all other missing figures are taken by your opponent.

If I am right, it would leave only pawn structure as the one that defines if a position is possible (even if stupid) or not.

That would leave then to analyze still quite some number of pawn arrangements. But I would definitely start from there.

Anyway I would definitely try to, regardless of artificiality, return each figure to its original position first. This is because it is very easy to offer a figure to the opponent and not ruin the initial structure, you just move the figure until it gets close to whatever it can take and there you are.

This generic approach might actually work in quite some number of cases. But... it is still heuristic and it would require quite some effort to prove that it might be working in general.

Not to leave the story empty handed

The total number of ways figures can be arranged around a table

13^64

since we have 6 different black and 6 different white pieces and one is for an empty space (as you can see I deliberately do not call this a position rather just an arrangement)

About the number of sensible positions and the number of sensible games, they differ only by a small factor because the branching factor is small. (Suppose we start from one possible position and have 2 different moves to choose from. After 8 moves we would have 2^8=256 possible games, if they do not overlap, and 1+2+4+8+16+32+64=127 possible positions. In chess the branching is about 3.) So we can say that the number of sensible positions is about the same as the number of sensible positions estimated to 10^40.

So the probability that a totally random position you set is sensible one as well is roughly 10^-30, or should I say it is close to impossible of doing it randomly.

One thing that would be quite interesting to know is how many groups of connected positions legal or illegal we have in chess. Connected means that you can reach one position from another. Nobody cares about these things, but we are not going to resolve chess in mathematical sense if we do not start asking these questions.

11
  • "return each figure to its original position first." ... Hmm... How many illegal positions are there, really? Almost any piece can be anywhere, and the ones that can't, have known possible locations, mainly, the knights? ... ... If you allow cooperation from both players, given any position under a small set of basic rules, every position is legal?
    – Malady
    Jul 14 at 2:42
  • @Malady: Absolutely not. Go to pdb.dieschwalbe.de, enter STIP='Löse' into the search field, and you get a lot of problems that basically say "Prove this position is legal". Which may be horribly tricky - no heuristic would be able to do that, especially as you can't simply walk in to Mordor or walk out of the knot the pieces are in. Just move one pawn a square back, and this might make the position illegal since this was a much needed tempo move. Jul 14 at 7:25
  • @Malady That is actually my point. If you ask about the position being reachable by any series of moves then it is unimportant in what order a rook was moving around or which figure took what figure exactly. So you have quite some freedom to decide how we got to this position. If you say, no, no, I want "legal" to mean "meaningful" then backtracking is the only option, with some additional analysis that would add "nobody would play that move" filter.
    – user28338
    Jul 14 at 10:52
  • @HaukeReddmann - Oh, you mean like because you must not move into checked positions... Or something. Well, at least a small number of reverse moves makes things easier? ... Might be more useful for you to respond to alex instead...
    – Malady
    Jul 14 at 14:44
  • 1
    Even tougher - things like "two white bishops" could also be the result of a promotion.
    – user45266
    Jul 14 at 22:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.