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 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?
Originally posted by David113Taking 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.
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?
Originally posted by FabianFnasThis 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.
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 David113I still thinks the above. The 50-move rule ensures that.
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.
Originally posted by FabianFnasThat'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.
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.
Originally posted by ThalassaWhether 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.
The basic unprovable chess problem is whether or not white can force a win with perfect play from the starting position.
Cheers,
T.
I 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.
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 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
Originally posted by TeraThe 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 chess, or some bizarre variant masquerading as such?
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
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'.