- 29 Mar '08 17:31 / 2 editsIs there a chess problem which is undecidable (it cannot be proved if the problem has a solution or not)?

Obviously the board size or something like that should be variable, otherwise the number of possibilities is finite and in theory the (non-)existence of a solution can be determined by brute force search.

If no such problem exists, maybe we can compose one? For example, choose a known math problem which is undecidable, and then compose a chess problem which has a solution if and only if the math problem has a solution. Maybe every math problem can be reduced to a chess problem on a large enough board, in the same way that it can be transformed into a Turing machine or a game-of-life position? - 29 Mar '08 18:30

Taking into the consideration that every move in a game (from a problems position or the starting position of an ordinary game) is one less move to the end of the game than the previous one, i.e. a game cannot be infinitely long, it has to stop in a finite number of moves with a win for one player or a draw... taking this into consideration, then every problem is decidable.*Originally posted by David113***Is there a chess problem which is undecidable (it cannot be proved if the problem has a solution or not)?**

Obviously the board size or something like that should be variable, otherwise the number of possibilities is finite and in theory the (non-)existence of a solution can be determined by brute force search.

If no such problem exists, maybe we can co ...[text shortened]... rd, in the same way that it can be transformed into a Turing machine or a game-of-life position? - 29 Mar '08 18:36 / 1 edit

This is why I said "Obviously the board size or something like that should be variable..." What you say is true only if the size of the board is fixed. But if I ask as in my other post, "Do K+B+N win against K on a square board of any size?" then I see no reason why a problem like this cannot be undecidable. Yes, you can verify that the K+B+N win on a specific board, but that does not answer the general question.*Originally posted by FabianFnas***Taking into the consideration that every move in a game (from a problems position or the starting position of an ordinary game) is one less move to the end of the game than the previous one, i.e. a game cannot be infinitely long, it has to stop in a finite number of moves with a win for one player or a draw... taking this into consideration, then every problem is decidable.** - 29 Mar '08 18:52 / 1 edit

I still thinks the above. The 50-move rule ensures that.*Originally posted by David113***This is why I said "Obviously the board size or something like that should be variable..." What you say is true only if the size of the board is fixed. But if I ask as in my other post, "Do K+B+N win against K on a square board of any size?" then I see no reason why a problem like this cannot be undecidable. Yes, you can verify that the K+B+N win on a specific board, but that does not answer the general question.**

Say you have the white king and other white pieces clustered around the a1 square, while the black king is somewhere in the z99 region. Then it is pretty sure that it will be a draw based on the 50-move rule.

Still, your thoughts are very clever. - 29 Mar '08 22:03 / 1 edit

That's a good point: the 50-move rule allows an easy proof that KBNK is decidable. But I don't think it forces all NxN chess problems to be decidable.*Originally posted by FabianFnas***Say you have the white king and other white pieces clustered around the a1 square, while the black king is somewhere in the z99 region. Then it is pretty sure that it will be a draw based on the 50-move rule.**

http://en.wikipedia.org/wiki/List_of_undecidable_problems may be helpful. I suspect it's easiest to construct a Turing machine on a chessboard. - 31 Mar '08 02:20

Whether chess is a win for white or black or drawn is decidable with a simple brute-force algorithm and a *lot* of time. This thread is concerned with whether or not there exist chess problems that for which no provable answer can be given, even in theory with all the computing power you could ever want. It is, strangely enough, possible to prove that certain assertions are unprovable. The question is whether one can frame such an assertion as a chess problem.*Originally posted by Thalassa***The basic unprovable chess problem is whether or not white can force a win with perfect play from the starting position.**

Cheers,

T. - 02 Apr '08 13:19 / 1 editI believe that on an infinite board, without the 50 move rule, Chess evaluation should be undecidable. Proof by reduction to turing-machine decidabilitiy.

It is well-known that a DFA with 4 counters is equivalent to a turing machine (use 2 counters to do the factoring required to use the other 2 counters as stacks via Godel numbering, and of course a DFA with two stacks is a turing machine. Note: It can be shown that only 3 are needed, but the DFA is much more complicated, so it's easier to use 4.

(begin handwaving)

I should think one should be able to make a counter pretty easily using rook-and-queen laddering, such that white's pursuit of a win pushes the rook back 1 square or pushes it forward one square, thus counting. Then the difficulty is connecting into a basic universal machine's DFA, which is still fairly complicated because of the need to do integer devision via counters. However this has been done for many classes of games (e.g. go, mindsweeper) so I would be very surprised if the expressiveness of Chess wasn't up to the task.

(end handwaving)

This proof would be long, highly mechanical, and ugly. However I can't see why it shouldn't work, and this probably classifies a huge number of infinite-board infinite-length chess questions undecidable. - 13 Apr '08 18:48Just a thought but there is positions that can never be reached with proper play. So if were thinking of positions from start to finish or something like that. I mean for sillyness sake, put both kings in mate or drawn (no moves) position and such a position is not resolvable since you don't know how to apply the rules.

So basically if you want to construct such problem that isn't resolvable with the chess rules as they are then you have to insert special rules, such as "it has to be reached with no bending of the rules."

If not then we're just making up a new ruleset for this particular question which does not seem to solve anything. :p - 13 Apr '08 19:01

The point about rules is a fair one, given that people in the thread are already talking about expanding the board size. Is an expanded board really*Originally posted by Tera***Just a thought but there is positions that can never be reached with proper play. So if were thinking of positions from start to finish or something like that. I mean for sillyness sake, put both kings in mate or drawn (no moves) position and such a position is not resolvable since you don't know how to apply the rules.**

So basically if you want to construct ...[text shortened]... ing up a new ruleset for this particular question which does not seem to solve anything. :p**chess**, or some bizarre variant masquerading as such?

Here's a much simpler answer to the thread's question:

Mate in 2

What was Black's last move? Either he moved his pawn two squares, or he moved his King or Rook. If the former, White can take*en passant*and 1.hxg6 forces mate; if the latter, 1.Ke6 forces mate because Black cannot castle. We can prove that there is a forced mate in 2, but we cannot tell what the correct move is! In that sense, the problem is 'undecidable'.