The future of computer Chess

A reasonable hypothesis, but not a solution.  I suspect it is in fact a draw with best play, but a solution requires proof.

I recently read a fascinating article about quantum mechanics in photosynthesis. It states that photosynthesis is so efficient because the quantum wave can simultaneously try every possible pathway to find the most efficient one. This got me thinking about applying this to other problems (such as chess). If we could somehow represent a chess position in a way that we can apply a quantum wave function to it, we could simultaneously try all possible variations and get the most efficient path to checkmate out of it. I know it's not that simple (so don't beat me up if you're a physics person), I just enjoy the thought.

Thanks

I think the memory comparison quickly breaks down as memorizing digits of Pi is a linear exercise whereas chess variations are exponential.

Neither do I, but this also fits the bill: http://en.wikipedia.org/wiki/First-move_advantage_in_chess#Solving_chess 

Chess cannot be solved because of Godel's theorem. In every logical system there are "undecidable propositions" whose truth or falsehood cannot be deduced or determined. In the logical system of chess these correspond to positions that are undecidable, that is, it is impossible to determine by logic which side will win or lose or whether or not there will be a draw with best play. "Undecidable positions" save chess from ever being "solved."

To follow up on my last comment, if there are ANY undecidable positions that can be reached from the beginning position with best play, it follows that the beginning position is also undecidable.

By that same logic Tic-Tac-Toe cannot be solved, but it clearly has.

You're misapplying Gödel's incompleteness theorem.

Gödel's theory is about mathematical logic where most things are infinite. If the number of positions that could arise in a game of chess were infinite, then by the same logic it would be unprovable. However there is a well established upper bound for chess so you argument is false. 

For a proof to be complete, you need to address every possible condition. For chess to be completely solved and declared draw, then every single possible line of play will have to be analyzed as ending in draw. 

I'm going to give some considerable benefit of the doubt here for the following:

• Let's assume the contextual nature of lines in a chess game (versus the sheer randomness of the digits of Pi) coupled with knowledge of the game could give a 100 fold increase over the current world record for Pi reciting (83,431 digits).
• Let's trim the number of candidate moves for any given position from ~30 to ~5 to account for the fact that many of the ~30 candidate moves are unreasonable, and also assume that they're memorizing the best move for each of the 5 responses.

So, how far into a game could an individual who can remember 8,343,100 moves get assuming only five candidate responses from their opponent per turn?

Log5(8,343,100)=~9.9

10 moves, assuming they chose one response for each of the five candidate moves.

The reason why i think Chess may be unsolvable is that even though every position could possibly be analyzed by a computer, it is unlike tic tac toe:

What strategy would the computer choose?

A player can change his strategy while a computer is held to its program.

Please comment.

The strategy the computer would use would be to make the best move for the given position.

Solving the game makes strategy irrelevant.

...i tried w/ a computer here on our site, when ther was some upgrade, ...i was mated w/ my last king ...doing the last stand!...

First, as to the "chess is finite" argument: a chess game, like a baseball game, can theoretically be infinitely long. This distinguishes it from games like tic-tac-toe, which was used to pooh-pooh my application of Godel's theorem. Here is a proposition for you: with best play by both sides, can a game of chess be infinitely long? Or can you establish an upper bound for the number of moves? This proposition may well be undecidable. Unless you are prepared to answer it, you cannot "solve" chess no matter how powerful the computer.

Let us consider a game of potentially infinite length, like baseball, and presume that both pitchers are both perfect, never make a mistake, and have endless stamina. They both pitch perfect games. They go into extra innings. Still no hits, no walks, no runs scored. This could go on forever: the very idea of a finite outcome depends on someone making a mistake. Can baseball be "solved?" Of course not. And if the perfect game of chess should be infinite, then chess cannot be solved, for its outcome would not be win or loss, and would also not be a draw.

It is only the artifice of the "fifty-move rule" that imposes finitude on chess and creates the first condition for "solvability." But a result that chess is "solvable" as a draw only because of this arbitrary limitation--one designed for the limitations of humans, not computers--would not be very satisfactory and would not, in fact, tell us very much.

i hope chess is never solved. if it does i hope not in my lifetime

Ravi

All of that evidence is great, but the question is not one that will be solved by evidence. For instance, it sure looks like there are an infinite amount of prime numbers, and I can keep counting until the end of time but that is in no way proof that they continue forever. However, it is relatively simple to prove deductively that they do.

I feel that chess closely resembles propositional logic and, like formal logic, we don't have to show every statement is valid; rather, we only need to show how every statement can be proven valid/invalid. If we can do this for chess, then it would be possible for some hypothetical machine to decide every "statement" in chess.

Remember that in a drawn position, though, either party can claim the draw, and if the game were solved, the best move would in fact be to claim the draw.

While, yes, the game can theoretically be infinitely long, with best play it is not.

The idea that with best play chess cannot be infinitely long rests on a logical fallacy. How can a player use judgment to determine that a position is drawn, when "best play" is only defined in computer terms of being able to compute every possible variation to its end? The argument begs the question. For "best play" to be determinable, it depends on a finite game.

To mhtraylor: that is the point. In formal logic, it is possible to construct statements that are not decidable as to whether they are valid or not. And there can be statements that we cannot determine whether or not they are decidable. On this rests the unsolvability of chess.