Chess solved?

[mwyoung]

There are chess positions in which there are a large number of moves to the checkmate, but for which a rule can be written to determine whether the position is winning or not. That disproves the (assumed, not stated in the report) idea that there is a linear relationship between the number of moves to checkmate and the amount of processing needed to determine that the position is winning.

No, that is incorrect. You are misunderstanding the paper.

There is nothing in the paper related to or assuming some "linear relationship".

The paper uses a standard TCS proof technique. If you are not familiar with this technique, it might be confusing to you.

Why even try to explain? If towfarce: thinks he can solve chess. Then show us. Towfarce has shown no proofs yet!.

[towforce]

There are chess positions in which there are a large number of moves to the checkmate, but for which a rule can be written to determine whether the position is winning or not. That disproves the (assumed, not stated in the report) idea that there is a linear relationship between the number of moves to checkmate and the amount of processing needed to determine that the position is winning.

No, that is incorrect. You are misunderstanding the paper.

There is nothing in the paper related to or assuming some "linear relationship".

I know: I said that in the quoted text above.

The paper uses a standard TCS proof technique. If you are not familiar with this technique, it might be confusing to you.

I cannot see that in the paper. Unless I missed it, it makes no reference to a proof technique. If I did miss it, please quote the text that I missed in the paper.

Once again, here's what I can see that the paper ACTUALLY does:

1. it describes a binary game

2. it shows that, in winnable positions, the distance (number of moves) to the win can increase exponentially with the size of the game

3. it shows mathematical transformations between the binary game and the game of chess

So the "proving" in the paper is proving that as the chess board size increases, it's possible for the distance to checkmate to increase exponentially.

If the paper does more than that, it would be helpful if you would point to at least one sentence in the paper that does that, please.

As I've said before, both the authors and the peer reviewer were clumsy (e.g. the horribly incorrect use of the word "infinitely" on the first page). I once had a job in which I read thousands of reports. By the end, I was able to pick up a paper and judge its quality in, literally, seconds. This paper has two contra-indicators:

1. obvious clumsy mistakes, which scream "careless" to a trained listener

2. obfuscation, which often indicate that something (or multiple things) are being hidden

I am, however, willing to admit that I might be wrong - but it would be really helpful if someone, ANYONE!, could show me one single sentence in the paper that goes further that goes further than demonstrating that the number of moves to checkmate increases with the size of the game.

[jp]

There is nothing in the paper related to or assuming some "linear relationship".

I know: I said that in the quoted text above.

You claimed in the quoted text that it does assume that. It does not assume that.

You are misunderstanding the paper.

I once had a job in which I read thousands of reports. By the end, I was able to pick up a paper and judge its quality in, literally, seconds.

You might be able to do that for your reports, but you can't do that for mathematical proofs, especially if you have no familiarity with the area.

Do you have experience in TCS or anything closely related?

This is also not the only paper that rules out what you hope for. Are you really going to claim that all the papers that prove results you don't like are wrong?

[towforce]

Do you have experience in TCS or anything closely related?

If I was writing a proof/conjecture that the computational complexity of proving a win in chess can increase exponentially in n on an n*n board then I would start it by clearly explaining the overall method - something like this:

* I will show you a boolean game that another academic has written

* I will show you that the number of moves to the end of the game will increase exponentially in some positions as the size of the game increases

* I will show you key mathematical transformations from the boolean game to chess

* this will prove that positions exist in chess where the number of moves to checkmate increases exponentially in n on an n*n board

* from [name], a conjecture from computational complexity theory, we can therefore say that the complexity of proving a win in chess by any method increases exponentially in n on an n*n chessboard

Notice the difference between how I have introduced the proof, and the way the proof is introduced in the paper. In general, the paper is obfuscated, and in particular, the paper provides no link between demonstrating the number of moves to checkmate and the computational complexity of proving the win by any means (please quote text from the paper if I am wrong about this).

This is also not the only paper that rules out what you hope for.

At the moment, I'm afraid it's not 100% clear to me that there any proofs that the computational complexity of proving a win in chess can increase exponentially in n on an n*n board, but I'm humble enough to admit that I might be wrong about this. If anyone knows of any such papers, please provide a link.

[chrisw]

There are chess positions in which there are a large number of moves to the checkmate, but for which a rule can be written to determine whether the position is winning or not. That disproves the (assumed, not stated in the report) idea that there is a linear relationship between the number of moves to checkmate and the amount of processing needed to determine that the position is winning.

No, that is incorrect. You are misunderstanding the paper.

There is nothing in the paper related to or assuming some "linear relationship".

I know: I said that in the quoted text above.

The paper uses a standard TCS proof technique. If you are not familiar with this technique, it might be confusing to you.

I cannot see that in the paper. Unless I missed it, it makes no reference to a proof technique. If I did miss it, please quote the text that I missed in the paper.

Once again, here's what I can see that the paper ACTUALLY does:

1. it describes a binary game

2. it shows that, in winnable positions, the distance (number of moves) to the win can increase exponentially with the size of the game

3. it shows mathematical transformations between the binary game and the game of chess

So the "proving" in the paper is proving that as the chess board size increases, it's possible for the distance to checkmate to increase exponentially.

If the paper does more than that, it would be helpful if you would point to at least one sentence in the paper that does that, please.

As I've said before, both the authors and the peer reviewer were clumsy (e.g. the horribly incorrect use of the word "infinitely" on the first page). I once had a job in which I read thousands of reports. By the end, I was able to pick up a paper and judge its quality in, literally, seconds. This paper has two contra-indicators:

1. obvious clumsy mistakes, which scream "careless" to a trained listener

2. obfuscation, which often indicate that something (or multiple things) are being hidden

I am, however, willing to admit that I might be wrong - but it would be really helpful if someone, ANYONE!, could show me one single sentence in the paper that goes further that goes further than demonstrating that the number of moves to checkmate increases with the size of the game.

Towforce signature:
Sometimes it is the people no one can imagine anything of who do the things no one can imagine - Alan Turing

The set of people who "do the things no one can imagine" all have one thing in common. They actually did DO something.

Whereas the set of people who do no work, have no data and no results, do no things that no one can imagine.

[jp]

At the moment, I'm afraid it's not 100% clear to me that there any proofs that the computational complexity of proving a win in chess can increase exponentially in n on an n*n board, but I'm humble enough to admit that I might be wrong about this. If anyone knows of any such papers, please provide a link.

It's not clear to you because you don't understand the paper. You do not appear to be familiar with computational complexity either.

If you've read this paper and know just a little bit about computational complexity, you'll already know about another paper that kills your goal (at least for NxN).

[towforce]

If you've read this paper carefully and know a little bit about computational complexity, you'll already know about another paper that kills your goal (at least for NxN).

May I humbly request that you quote one single sentence from the paper that goes from number of moves to checkmate to determining win by any method?

I'm not the biggest fan of guessing games - please tell me what the other paper is. Thank you in advance for this.

[syzygy]

If you've read this paper carefully and know a little bit about computational complexity, you'll already know about another paper that kills your goal (at least for NxN).

May I humbly request that you quote one single sentence from the paper that goes from number of moves to checkmate to determining win by any method?

I'm not the biggest fan of guessing games - please tell me what the other paper is. Thank you in advance for this.

As I explained multiple times already, the paper obviously says nothing about the constant time in which 8x8 chess can be solved.

The whole point of referring to this paper and such results in general is that it shows that in general there is no quick way to solve games like chess. Therefore 8x8 chess must be special for it to have a computationally easy solution. There is absolutely no empirical reason to expect it to be special. Therefore, all your "it would be surprising if I it cannot be solved by XYZ" amount to nothing. Q.E.D.

[towforce]

If you've read this paper carefully and know a little bit about computational complexity, you'll already know about another paper that kills your goal (at least for NxN).

May I humbly request that you quote one single sentence from the paper that goes from number of moves to checkmate to determining win by any method?

I'm not the biggest fan of guessing games - please tell me what the other paper is. Thank you in advance for this.

As I explained multiple times already, the paper obviously says nothing about the constant time in which 8x8 chess can be solved.

The whole point of referring to this paper and such results in general is that it shows that in general there is no quick way to solve games like chess. Therefore 8x8 chess must be special for it to have a computationally easy solution. There is absolutely no empirical reason to expect it to be special. Therefore, all your "it would be surprising if I it cannot be solved by XYZ" amount to nothing. Q.E.D.

OK, so we're going around in circles here.

Once again:

1. if the paper you've already shown me proves that computational complexity increases exponentially in n on an n*n board, please quote me ONE SENTENCE in the paper that links distance to checkmate to difficulty of resolving a position by any means.

2. If there's another paper I need to see then please show me the other paper.

3. in an attempt to break the circle, I'll offer a counterexample: you have a map of paths through a park, and you want to find the shortest distance between to points using these paths. This is obviously the shortest path problem on an unweighted graph. The fastest way to resolve that in graph theory is a breadth-first search, for which the computational complexity is O(E+V). However, a second way to solve it is to just look at the map and see the obvious route! When this happens, your brain isn't doing a breadth-first search - it's using heuristics that you've learned, and, without wanting an argument about computation in the brain, you've solved the problem in fewer steps.

The paper's way of demonstrating that the number of moves to checkmate can be exponential in n on an n*n board is clever, so I'm not surprised that they wanted to publish - but they definitely claim more for their paper than the paper demonstrates. I've been thinking that there may not be a way of proving that the computational complexity of discovering that a position is won increases exponentially with the size of the board, for one simple reason: some new maths might be discovered that enables it to be done quickly. Fermat wrote his last theorem in 1637, and it didn't get solved until 358 years later: when it was solved, the proof used some mathematical knowledge that wasn't available to Fermat himself.

The only way to really know whether my method will work will be to build it out and then:

1. chart the complexity of the polynomial fit against the complexity and number of training positions

2. see whether the polynomial makes reasonable evaluations of new positions

3. chart the improvement of evaluation of novel positions against size/quality of training data

4. if we're lucky, spot where the polynomial is converging to and hence write an EF that evaluates all chess positions accurately

[syzygy]

As I explained multiple times already, the paper obviously says nothing about the constant time in which 8x8 chess can be solved.

The whole point of referring to this paper and such results in general is that it shows that in general there is no quick way to solve games like chess. Therefore 8x8 chess must be special for it to have a computationally easy solution. There is absolutely no empirical reason to expect it to be special. Therefore, all your "it would be surprising if I it cannot be solved by XYZ" amount to nothing. Q.E.D.

OK, so we're going around in circles here.

Once again:

1. if the paper you've already shown me proves that computational complexity increases exponentially in n on an n*n board, please quote me ONE SENTENCE in the paper that links distance to checkmate to difficulty of resolving a position by any means.

Oh boy, are you really going to challenge the correctness of the paper? That is obviously way above your paygrade. Already the expression "computational complexity increases exponentially in n" makes no sense.

What the paper proves is that any algorithm that solves NxN chess requires a number of computational steps that is asymptotically exponential in N. The paper proves this by showing that another game that is known to be EXPTIME-complete can be reduced to NxN chess. This means that NxN chess is EXPTIME-complete as well. A problem is EXPTIME-complete if any problem solvable in exponential time (or less) can be reduced to it with at most polynomial overhead.

If you could come up with some smart algorithm that solves NxN chess in a number of computational steps asymptotically polynomial in N, in view of the paper that would mean that you could solve ANY problem in EXPTIME in polynomial time by reducing it to NxN chess.

However, it has been proven a long time ago that EXPTIME is strictly bigger than P, the class of problems that can be solved in polynomial time. So it is a mathematically proven fact that such a smart algorithm does not exist.

Now again:

As I explained multiple times already, the paper obviously says nothing about the constant time in which 8x8 chess can be solved.

The whole point of referring to this paper and such results in general is that it shows that in general there is no quick way to solve games like chess. Therefore 8x8 chess must be special for it to have a computationally easy solution. There is absolutely no empirical reason to expect it to be special. Therefore, all your "it would be surprising if I it cannot be solved by XYZ" amount to nothing. Q.E.D.

3. in an attempt to break the circle, I'll offer a counterexample: you have a map of paths through a park, and you want to find the shortest distance between to points using these paths. This is obviously the shortest path problem on an unweighted graph. The fastest way to resolve that in graph theory is a breadth-first search, for which the computational complexity is O(E+V). However, a second way to solve it is to just look at the map and see the obvious route! When this happens, your brain isn't doing a breadth-first search - it's using heuristics that you've learned, and, without wanting an argument about computation in the brain, you've solved the problem in fewer steps.

I have no idea why you think this is a counterexample.

Lots of problems are too hard to solve exactly, so heuristics have been developed to find approximate solutions. Your "at a glance" heuristic is not an algorithm that solves the problem.
When we are talking about solving chess, we are not talking about an approximate solution.

Btw, your "shortest path problem" is computationally really easy to solve. I guess you must have once read about the traveling salesman problem.