Will computers ever solve chess?

Way to gloss over 350 pages .

"Pandemic is about coughing.  Lots of people get it.  Still happening."

It's input...but is it valuable? 

Holy sh*t, 8 minutes after being posted it gets 6,000+ comments.

Actually, the last 6000 posts have taken over 4 years.

The answers have not changed in those years, but the resources for optimism (pessimism) have improved dramatically. 

#6986
The Shannon number of possible games plays no role at all. It is the number 10^38 of legal and sensible positions that counts. Only about the square root of these is relevant to solve chess i.e.  10^19 as we know from the proof that checkers is a draw. Each pawn move and each capture renders a huge number of positions irrelevant.

Estimates aren't proofs. To solve chess you'd have to provide proofs. The number of "sensible positions" doesn't matter. How do you define sensible? How do you know you're really winning regardless of material imbalance?

#6993
"To solve chess you'd have to provide proofs."
++ It is only proven after chess is solved. The estimates confirm the opinion of the late GM Sveshnikov: good assistants and modern computers take 5 years to solve chess.

"The number of "sensible positions" doesn't matter."
Excess promotions e.g. with 4 queens on the board occur like once in 1000 games. Underpromotions e.g. to a knight occur like once in 1000 games. John Tromp research shows a typical random legal position has both multiple excess promotions and multiple underpromotions. Such a position never arises in any real game between reasonably skilled players and thus is not sensible. Such a non sensible position plays no role in solving chess.

"How do you define sensible?"
++ sensible = possible with 1 box of chess men, i.e. without having to borrow excess promotion pieces from up to 8 additional boxes of chess men. This tosses out some sensible positions with 4 queens or with 3 knights, but on the other hand it still counts non sensible positions like with quintuple pawns. So the estimate should about even out.

"How do you know you're really winning regardless of material imbalance?"
++ Solving chess = proving that for all reasonable white moves there exists at least 1 black move that ultimately leads to a table base draw.

All anyone really needs to know about Sveshnikov is that he was not qualified to make the claim he did.  End of story.

@tygxc is only correct in a practical sense about "sensible" positions. For a watertight proof, you need to explicitly deal with even the daftest of moves by the defender to a strategy. Being pretty damn sure moves can be ignored is not good enough.

Thus, for example, a line where white's strategy to draw runs into black sequentially giving up all his pieces can't be ignored, and then includes the "non-sensible" position in it where white is up by 31 pawns (or whatever).

#6995
GM Sveshnikov knew less about chess than 1855 rated btickler?
#6996
Look at it this way. Let the good assistants prepare 26 men starting positions from each ECO code. Let the modern computer now play against itself until it reaches the table base. Is it a table base draw? No retract the last white move and replace it by the #2 choice. Still a draw? Retract the second last move. Still a draw? retract the 3rd last move...

This is why your efforts are doomed to failure.  Be precise in your thinking.  Be.  Precise.  Make distinctions.  Grok nuances.  

What you just said and what I said are completely different things.  Any 5th grader could tell that saying Sveshnikov is not qualified is not at all the same as claiming any particular 1855 player is better than him (and you are doubly imprecise here...1855 is my online chess960 rating).  If you see a plumber about to perform brain surgery, are you "qualified" to call the authorities and stop them?

You and Sveshnikov are the plumbers.  Normally, I would not have to say that last part explicitly, but...in this case I am wondering .

My starting point is the intuitive concept to deal in parallel with all of the possibilities as superpositions of states. To represent 10^44.5 positions you need over 10^50 classical bits of storage, but not necessarily more than 147 qubits (a practical representation is likely to require more than this, but less than 1000).

Then you need to add another couple of entangled qubits to represent the value of the positions. We need these qubits to be in conditionally definite states - i.e. at any time in the process, the conditional value of the value qubits given any specific position qubit representation is one of the following possibilities: "undetermined", "white win", "black win" or "draw" without any superposition.  The algorithm manipulating the entangled state will be changing these entangled values from "undetermined" to other values.

The initialisation applies an algorithm to positions that determines if it is a result (a checkmate on the board).

A key part of the algorithm is to determine the set of positions reachable by a legal move from a given position and generating the set of value bits associated with those positions. Only when the value is determined for all of these moves can the value be determined for the given position (just like for tablebase construction, but this needs to work in parallel).

So as time passes more and more of the position values (as represented in the entangled value bits) become definite. One of two things can happen. Either the initial position becomes determined, or it doesn't. 

I haven't bothered to try to address drawing rules here, thinking more of a variation of chess with all the drawing rules omitted except stalemate (a more elegant rule set, but one that permits infinite games that are only resolvable at huge depths related to the size of the equivalence classes of positions with reversible paths between them).  I am sure there are ways to add 50/75 move rules to be more relevant to normal chess (and more practical to compute).

Part 2: a toy example to indicate how the algorithm should work

Suppose a game has two possible positions P and Q  and two possible outcomes W and L.  We represent the position by just 1 qubit where P is true and Q is false and the outcome by a another state entangled with the position state and having three values - Undetermined, Win and Loss.

Suppose P is the initial position of the game.

So we can start with an entangled state which is a superposition of two states indicating the position P is 

PU + QU

Applying our algorithm for which positions have a result on the board we find Q is a win. The state becomes

PU + QW

Note that although this is entangled, the value conditional on the position is definite. The value conditional on position P it is U, and the value conditional on the position being Q is W.

Next we apply our algorithm that finds the legal moves in each position. It happens that there is a single legal move from P that reaches Q.  We can then update the conditional value of P to get the state:

PW + QW

As the value of the initial position is now determined, the game has been solved.

Of course most games would require repetition of the inner steps and there would be as many entangled states as there are positions, but the updates are in parallel.

7000 posts!

You can't run it all in parallel, because you have to check past results as the tree expands backwards.  You can't check or pass along those results because quantum computing is a "destructive read" technology.  When you check the answer, you destroy the answer, like eating a coded message after you read it.

Either that or every single process has to calculate completely standalone and so there will be countless evaluations of the same positions that are heading toward different endstate checkmates, and each possible checkmate will have to calculate the entire tree.  That vastly increases the 10^44+ we're dealing with as the goal.

"One of two things can happen. Either the initial position becomes determined, or it doesn't."

Yes .  I believe you are agreeing with me on this point.

That last sentence is the key, though.  If they solve the destructive read issue, then I will revise my stance... but I don't how they can...doesn't physics preclude it?  Like trying to determine where an electron is fixes it's location, observing the qubits results before the process ends kills the entire results "matrix" (I'm sure there's a different term in quantum computing circles).

I am not sure. The problem likely comes down to the no cloning theorem, so you have to be very careful how you transform the state, containing superimposed information at every stage. I tentatively hypothesise that if you can express it in a way where every step is reversible - i.e. unitary transformations - that would suffice. I have not done that above (rather assumed that it would be possible instead).

I think the computer should always be able to find the best moves in a position by calculating all the possible responses and so on, but I think it would take a very long time for it to calculate everything.

Correct me if I have missed something though.