# Undecidable chess problem?

David113
Posers and Puzzles 29 Mar '08 17:31
1. 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. 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. 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. 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. 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. 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. 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. 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. 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. sonhouse
Fast and Curious
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. 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. 06 Apr '08 09:48
Fritz 8 suggested Cxd5 for me at 0.50
It gives Qxh7+ -1.69?
13. 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. SwissGambit
Caninus Interruptus
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?