1. Joined
    25 Aug '06
    Moves
    0
    29 Mar '08 17:312 edits
    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?
  2. Joined
    11 Nov '05
    Moves
    43938
    29 Mar '08 18:30
    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?
    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.
  3. Joined
    25 Aug '06
    Moves
    0
    29 Mar '08 18:361 edit
    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.
    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.
  4. Joined
    11 Nov '05
    Moves
    43938
    29 Mar '08 18:521 edit
    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.
    I still thinks the above. The 50-move rule ensures that.

    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.
  5. Joined
    13 Dec '06
    Moves
    792
    29 Mar '08 22:031 edit
    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.
    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.

    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.
  6. Joined
    22 May '04
    Moves
    39709
    30 Mar '08 18:08
    The basic unprovable chess problem is whether or not white can force a win with perfect play from the starting position.

    Cheers,
    T.
  7. Joined
    26 Jun '06
    Moves
    59283
    30 Mar '08 20:27
    in "the immortal game" there was said to be a chess problem so hard only 1 person new the answer... i wonder how many people could solve it today if known
  8. Joined
    13 Dec '06
    Moves
    792
    31 Mar '08 02:20
    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.
    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.
  9. Joined
    28 Mar '08
    Moves
    445
    02 Apr '08 13:191 edit
    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.
  10. Subscribersonhouse
    Fast and Curious
    slatington, pa, usa
    Joined
    28 Dec '04
    Moves
    53223
    04 Apr '08 15:50
    Originally posted by irontigran
    in "the immortal game" there was said to be a chess problem so hard only 1 person new the answer... i wonder how many people could solve it today if known
    Fritz would do it in one second flat.
  11. Fichtekränzi
    Joined
    28 Mar '07
    Moves
    20555
    05 Apr '08 14:55
    Originally posted by sonhouse
    Fritz would do it in one second flat.
    Don't be so sure about Fritz and other engines!
    e.g.

    thats a position from a epd-File with test cases for engines.

    The problem is: avoid move Qxh7+, because the endgame is lost.
    But which move does Fritz suggest??
  12. Joined
    31 May '07
    Moves
    696
    06 Apr '08 09:48
    Fritz 8 suggested Cxd5 for me at 0.50
    It gives Qxh7+ -1.69?
  13. Joined
    20 Dec '07
    Moves
    1254
    13 Apr '08 18:48
    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
  14. Standard memberSwissGambit
    Caninus Interruptus
    2014.05.01
    Joined
    11 Apr '07
    Moves
    92274
    13 Apr '08 19:01
    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
    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 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'.
Back to Top

Cookies help us deliver our Services. By using our Services or clicking I agree, you agree to our use of cookies. Learn More.I Agree