Please turn on javascript in your browser to play chess.
www.redhotpawn.com - Play Online Chess

Forgot it?

Posers and Puzzles Forum

Undecidable chess problem?

Original post by Standard member David113, 29 Mar '08 17:31
  1. Joined : 25 Aug '06
    Moves : 0
    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
    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
    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
    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
    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
    The basic unprovable chess problem is whether or not white can force a win with perfect play from the starting position.

    Cheers,
    T.
  7. Rob Scheider is..
    A Stapler!
    Joined : 26 Jun '06
    Moves : 59283
    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
    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
    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. Fast and Curious
    slatington, pa, usa
    Joined : 28 Dec '04
    Moves : 34634
    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. Standard member afx
    Fichtekränzi
    Joined : 28 Mar '07
    Moves : 19582
    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
    Fritz 8 suggested Cxd5 for me at 0.50
    It gives Qxh7+ -1.69?
  13. Joined : 20 Dec '07
    Moves : 1254
    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. Caninus Interruptus
    2014.05.01
    Joined : 11 Apr '07
    Moves : 92274
    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