We will see. There is already research regarding chess and quantum computers but from what I've seen so far they only made the first step out of a gazillion steps.
Whether this leads to anything substantial we don't know yet. There will be a solution in the very distant future but not with the tools we have now.
Computer is just a tool.
The Shannon Number x = 10^120
It is far to be reached.
Computer is just a tool.
The Shannon Number x = 10^120
It is far to be reached.
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.
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...
#6995
GM Sveshnikov knew less about chess than 1855 rated btickler?
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 .
It is a different programming paradigm, but I believe in principle entirely general. One interesting property of quantum computing is reversibility: it is essential that all quantum gates are reversible for it to work.
If by different paradigm you mean like Turing's Enigma breaker, that has to crank through the entire process and either succeeds in one pass or fails, then I would agree. But 10^44.5 is a large process to do in one shot , and it's a fundamentally iterative process evaluating backwards from mate. You cannot "evaluate" each single position standalone, that would be like solving chess another 10^44.5 times over. So you need to carry information states from one subprocess to another...ergo the problem for quantum computers.
I would liken it to a massive pattern of dominoes tipping over. One shot to do it right, no stopping, and no having certain dominoes wait for others to do their tipping. It's unidirectional in nature. The pattern falls and then you see what you got in the end. It's a tremendous limitation compared to traditional programming.
Edit: ...and sure enough, as soon as I Googled "quantum computers like dominoes", I found this...
...and this.
Maybe I should be in quantum computing. It seems like an incredibly frustrating way to program though, much like real domino pattern builders. It's well suited to massively parallel tasks, but not iterative ones.
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.
It is a different programming paradigm, but I believe in principle entirely general. One interesting property of quantum computing is reversibility: it is essential that all quantum gates are reversible for it to work.
If by different paradigm you mean like Turing's Enigma breaker, that has to crank through the entire process and either succeeds in one pass or fails, then I would agree. But 10^44.5 is a large process to do in one shot , and it's a fundamentally iterative process evaluating backwards from mate. You cannot "evaluate" each single position standalone, that would be like solving chess another 10^44.5 times over. So you need to carry information states from one subprocess to another...ergo the problem for quantum computers.
I would liken it to a massive pattern of dominoes tipping over. One shot to do it right, no stopping, and no having certain dominoes wait for others to do their tipping. It's unidirectional in nature. The pattern falls and then you see what you got in the end. It's a tremendous limitation compared to traditional programming.
Edit: ...and sure enough, as soon as I Googled "quantum computers like dominoes", I found this...
...and this.
Maybe I should be in quantum computing. It seems like an incredibly frustrating way to program though, much like real domino pattern builders. It's well suited to massively parallel tasks, but not iterative ones.
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).
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.
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.
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).
It is a different programming paradigm, but I believe in principle entirely general. One interesting property of quantum computing is reversibility: it is essential that all quantum gates are reversible for it to work.
If by different paradigm you mean like Turing's Enigma breaker, that has to crank through the entire process and either succeeds in one pass or fails, then I would agree. But 10^44.5 is a large process to do in one shot
, and it's a fundamentally iterative process evaluating backwards from mate. You cannot "evaluate" each single position standalone, that would be like solving chess another 10^44.5 times over. So you need to carry information states from one subprocess to another...ergo the problem for quantum computers.
I would liken it to a massive pattern of dominoes tipping over. One shot to do it right, no stopping, and no having certain dominoes wait for others to do their tipping. It's unidirectional in nature. The pattern falls and then you see what you got in the end. It's a tremendous limitation compared to traditional programming.
Edit: ...and sure enough, as soon as I Googled "quantum computers like dominoes", I found this...
...and this.
Maybe I should be in quantum computing. It seems like an incredibly frustrating way to program though, much like real domino pattern builders. It's well suited to massively parallel tasks, but not iterative ones.