The future of computer Chess

A 32 piece table-base is an enumeration of the best possible move for any reachable position.  While it's true that there is not estimated to be enough space in the universe for such a catalogue in a non-quantum computing paradigm, I think that if a quantum computing breakthrough is made it will be the required catalyst for the solution if we are ever to achieve it.

This is why I gave "sometime after the next 50 years" as the aggressive estimate.

What is the longest possible mate-in-x-moves problem that can be constructed? Is it possible to find an upper limit? If it is always possible to find or create a forced mate problem that is one move longer, then chess is not solvable and the honor of both chess and humans are preserved against Skynet.

That's an interesting way of reformulating the problem, and one best left to the problem hobbyists among us.

230 seems a little light to me when using the phrase "longest possible".

I have read somewhere that the number of moves possible in chess exceed the number of (atoms) in the universe. That would mean that as long the universe remains a mystery ,chess will never be "solved". Deep blue was capable of calculating a few billion moves a second, but that was not even close to the number of possibilities that exists which is 10^120 more or less according to how stuff works.

http://electronics.howstuffworks.com/chess1.htm wrote

No computer is ever going to calculate the entire tree. What a chess computer tries to do is generate the board-position tree five or 10 or 20 moves into the future. Assuming that there are about 20 possible moves for any board position, a five-level tree contains 3,200,000 board positions. A 10-level tree contains about 10,000,000,000,000 (10 trillion) positions. The depth of the tree that a computer can calculate is controlled by the speed of the computer playing the game. The fastest chess computers can generate and evaluate millions of board positions per second.

Number of possible games >> Number of possible positions

Having searched for every loophole, I am about to be converted to the chess-is-finite camp. Can anyone help me out here?

I am still not too sure whether the universe has more (atoms) than the number of possible chess moves

http://www.chess-poster.com/english/notes_and_facts/did_you_know.htm

wrote Chess is infinite:  There are 400 different positions after each player makes one move apiece. There are 72,084 positions after two moves apiece. There are 9+ million positions after three moves apiece. There are 288+ billion different possible positions after four moves apiece. There are more 40-move games on Level-1 than the number of electrons in our universe. There are more game-trees of Chess than the number of galaxies (100+ billion), and more openings, defences, gambits, etc. than the number of quarks in our universe!          --Chesmayne

are you saying that the above is false?

Depending on whom you ask,

# of positions = 10^43 or 10^50
# of games = 10^123
# of atoms in the universe (not particles!) is between 4 x 10^79 and 10^81

Chess is definitely finite. Can't help you out! :-)

Thank you for clarifying NM ozzie_c_cobblepot

Chess is a game and every game has a end

HERE is a quote from Wikipedia. I Shall post the link after I post the important chunk I found within the text.

And I quote,

"The prospects of completely solving chess are generally considered to be rather remote. It is widely conjectured that there is no computationally inexpensive method to solve chess even in the very weak sense of determining with certainty the value of the initial position, and hence the idea of solving chess in the stronger sense of obtaining a practically usable description of a strategy for perfect play for either side seems unrealistic today. However, it should be noted that neither has it been proven that no computationally cheap way of determining the best move in a chess position exists, nor has it even been proven mathematically that a traditional alpha-beta-searcher running on present-day computing hardware could not solve the initial position in an acceptable amount of time. The difficulty in proving the latter lies in the fact that, while the number of board positions that could happen in the course of a chess game is huge (on the order of 10^40[17]), it is hard to rule out with mathematical certainty the possibility that the initial position allows either side to force a mate or a threefold repetition after relatively few moves, in which case the search tree might encompass only a very small subset of the set of possible positions. It has been mathematically proven that generalized chess (chess played with an arbitrarily large number of pieces on an arbitrarily large chessboard) is EXPTIME-complete,^[18] meaning that determining the winning side in an arbitrary position of generalized chess provably takes exponential time in the worst case; however, this theoretical result gives no lower bound on the amount of work required to solve ordinary 8x8 chess. Still, it can certainly be said that nothing indicates a practical possibility of solving chess at present in any sense of the word."

http://en.wikipedia.org/wiki/Computer_chess#Solving_chess

 Some musings on the solution to the longest possible game problem can be found here: http://blog.chess.com/kurtgodden/the-longest-possible-chess-game-revisited

The ~5900 figure assumes a forced draw after 50 move repetition.

Right, because in reality the 50 move rule requires one side to claim it. And it requires a scoresheet proving it.

I wonder at what point would Bill Goichberg step in... perhaps after you go back for the 118th score sheet and they've run out?

It is absolutely possible to find an upper limit to this question, because after a certain point you'll end up in a position that is identical to a previous one (given that there are a finite number of possible positions) and everything you've added in extending each mate-in-x will collapse out of the solution.

The absolute upper bound is the number of legal positions, which erroneously assumes you'd need to pass through each of them on your way to a forced mate.

must ... have ... citations ...

I disagree on the theoretica/pragmatic issue. But where do you get your meaningful numbers? Surely they are not poomas, right?

Incidentally, this only tells you whether chess solvable if the result of the solution is that one side always wins.

The set of positions from which a forced mate is possible and the set of drawn positions are mutually exclusive and with best play from both sides, never the twain shall meet.

Because it is mathematically convenient to do so. Indeed, one can spend much time coming up with a scheme for reducing the search space when ultimately it only pollutes the results.

Quantum computers would be used for super fast computation there would still be the problem of physical storage of information.

Chess is in theory finite because of the three-fold repetition and the 50 move drawing rules. The estimated number of possible chess positions is around 100 quindecillion, but if you consider just how deeply one game can be analyzed I would imagine that best guess is just the tip of the iceberg. There is a parallax problem when viewing this because who's to say when the last move has been reached. The complexity is just too much to bare.

Demonstrating equivalence is the key way in which this is done and in fact was instrumental in simplifying the solution to checkers down to a manageable problem.  Before eliminating parts of the problem the must first be shown to be mathematically equivalent to other parts of the problem otherwise the proof is not sound.  This is why the optionality of claiming a draw on repetition versus playing on forever is irrelevant:  They are both decidedly draws and as such are mathematically equivalent.

Another very simple example is that the solution to tic-tac-toe can be reduced eightfold by considering rotations and reflections of the board to be equivalent.