Hi guys, with regards to a quantum computing solution:
The power of a quantum computer is still limited by how much storage space it has. Even on a normal computer, chess is a constant-time problem (with a gigantic constant), and is a problem which will require a complete game tree to solve. This puts chess in the realm of problems for which the limiting factor is storage space, not computing time. A quantum computer will still need to store this entire game tree to deterministically solve chess, and thus, the benefit of quantum computing is negligible. QC is great for problems with a large amount of math, but chess reduces to a set of queries on a gigantic database. Hopefully, memory encoding becomes efficient enough for me to see chess being solved, but this is unlikely at best. The best thing QC can do for chess comes from a higher storage density, but this improvement would have to be colossal to even make a dent in the problem.
Hi everyone, first post. I wanted to post because a lot of what is being said in this thread is misinformed regarding the possible solution of chess. It is *not* required that a computer store the entire game tree of chess in order to solve it, as TheSicilianDragon said. For example, a straightforward solution is an ordered depth-first search through the game tree - this only requires that the current game path be stored, so the storage requirement is simply the length of the longest game.
Many other posts claim the impossibility of solving chess, and I believe these statements primarily stem from the 10^120 figure that is commonly thrown around in these discussions. It is true that 10^120 is very large, but it is of little relevance to the solution of chess. The number was produced by Claude Shannon as an approximation to the number of possible 40-move games (40 being the estimated length of the average game). But the crucial point is that the efficient algorithms for solving chess do not search through games, they search through *positions*. And the number of positions of chess is approximately 10^44, far less than 10^120, and far less than the number of atoms in the observable universe.
Further, it is not necessary to even search through all positions to solve chess! Alpha-beta and other pruning methods have the potential of reducing the number of searched positions required by as much as the square root. So chess could conceivably be solved by searching through as few as 10^22 positions. This is more than we are currently able to search through, but can one seriously state that we will *never* be able to search through 10^22 positions?
For a less optimistic estimate, we can look at the solution to checkers. Checkers has approximately 10^21 positions, yet only 10^14 positions were searched in the 2007 solution. So it required about n^(2/3) positions. If the same were to hold for chess, then about 10^29 positions will need to be searched. This is more, but again, by what reasoning can one confidently state that 10^29 will *never* be achievable?
In summary, the general belief that chess is unsolvable seems to be based on bad information. In any case, to argue effectively that chess is unsolvable, one must argue for an upper bound to the ultimate performance of computers, and I don't know of any good argument.
I'm also curious about what Kingpatzer meant by saying there is no theoretical basis for a solution to chess. Theoretically, the problem is simple - there are numerous finite algorithms that will definitively solve the problem. Our current computers are not able to run such algorithms, but this a practical consideration, not a theoretical one. It's simply a matter of whether or not computers will get sufficiently more powerful to solve the problem. "No theoretical basis" is a misnomer.
It's impossible to memorize every single chess position.
That's really not necessary. Chess software only has to understand certain positional tactics and rules to get ahead.