How close are we to solving chess?

JG27Pyth> [T]here is no way to say how small the solution might be.

Of course there is. There are 10^50 chess positions--that's the estimate. [Victor Allis, Searching for Solutions in Games and Artificial Intelligence].

How much space does one position require? 1 bit if all we want to know is whether a position is WON or NOT. 2 bits if we want to know if a position is WON, LOST, or DRAWN. 7-32 bits if we want to know the best move.

2^40 x 8 bits fit in 1 TB. 

So assuming 10^50 positions and 1 bit per position the solution will require:

10^50 / (2^40 x 8) = 1.1x10^37 =

11,000,000,000,000,000,000,000,000,000,000,000,000 TBs

(or 7-32 times this number if you want to know what the best move is)

likesforests, i think you missed the point of what JG2 said.  or maybe i missed the point of what you said . . .

what if solving chess didn't involve merely having a database of all possible moves and determining which ones are winning and which are losing?  what if a program was writeable that calculated a winning move by applying mathematical weights to pieces and positions (weights varying according to your opponents positions/pieces) to determine the best possible play instead of looking at every possible move tree following every possible move?  then you wouldn't need a computer that could hold all possible chess moves, you would need a formula that took into account position/piece/tactics, etc.  now i'm not saying there aren't 1,000 reasons why this hasn't happened yet, but i don't think there are any reasons why it couldn't happen ever.

 Did you understand my point? I'm inclined to think you didn't... but perhaps you are arguing that although there are superfluous games, there are no superfluous postions.  This is incorrect.

Consider the position after 1.f3? e6 2.g4?? ... Black is about to deliver fools mate with Qh4# .  This is a solved position on a solved line... all positions down the tree from f3 e6 g4 other than the one ending Qh4# are potentially superfluous, all other positions unique to the tree that contains f3 e6 g4 are superfluous.

Secondly, we don't analyze positions, but lines... who cares how many positions are theoretically possible, many of those positions cannot be arrived at without the cooperation of both players, these positions certainly lie OFF the true solution tree. It is possible to promote eight Pawns to Knights while the opponent promotes his pawns to Rooks -- these pieces can then synchronized swimming-esque manuver themselves into a happy face... how many of our theoretical 10^50 positions are taken up with nonsense like this?...these positions do not lie along any "best play" path. (That is to say, these postions aren't relevant and don't need to be calculated because they can't be reached, the path to them is too long -- other branches force descisive results, faster.) 

Positions must lie along lines. There are both superfluous positions and superfluous lines... lots of both. The true depth of calculation needed to 'solve' chess is hard to arrive at.  I don't claim to be able to estimate the number.

My brain hurts -- numbers too big. LMAO

This is all fascinating re the possibilities of computers "solving" chess and all, but as others have stated in so many words, OTB this issue is moot. Chess will remain an enjoyed game around the world with humans battling it out because of its inherent complexity and intrigue.

Russ 

I would actually disagree with everyone here....

 I'd say, chess is nearly solved.

 ^ of course, when I say that I do not mean to disagree with the numbers (that would be silly), I mean a different thing when I say "solve".

 By "solve", I mean, creating a machine (database, or whatever) that could never be defeated.

 suppose for example, two identical chess engines, on 100% equal software duke it out....the only difference bettween them is that one of these engines calculates at a depth of 2 ply, the other, only 1 ply.  -- its obvoius that the 2 ply computer will win the majority of games, perhaps close to 90%.

now suppose another game, as before, but this time one sees 5 ply, the other see's 4.  -- we would expect the 5 ply computer to win more games (as it is the better player), but this engine would probably win less than the 2 ply engine did against the 1ply.

This is Because, as we get deeper into variations, the ability to look one move ahead is less potent....(1 ply vs 2 ply = 100% improvement, 2ply vs 3ply = 66% improvement, ad infinitum) all we would need to do is find the point where, looking beyond X amount of ply's will not help find us a better move (which is significant enough to change the outcome of the game.)

This means that, looking 80ply ahead, from any given position, may well be enough to draw against God, inspite of fact God could look well beyond 60,000 ply ahead.  

I would agree that we are a long way from solving chess, even if only taking into account computer capabilities. But I definitely think that it will be solved, even if it takes as much as another 100 years or more. If you look at the development of the computer in the last 10 years or less, my mobile phone is more powerful than the majority of the £1000+ machines you could buy in 1995, and that is with technology that is  still very very new. Who can say how powerful computers will be in another 10, 20, 50, 100 years. I would not be surprised if the kind of figures we are discussing here have become commonplace within this timeframe

Similarly, I don't think you can argue that it will make chess redundant for humans, only that it would become pointless to play against computers. If anything, wouldnt it be nice occasionally to go home and see which move would have been objectively the best? Even if e4 is proven a win from move 1, no human is capable of seeing the 'correct' line through any response of black's...

THE FINAL CHESS GAME!

Year: 2025

White: Lydia Blonde, the world chess champion for humans

Black: Fritz 22, the world chess champion for programs (not "computers", people! program play!)

This convo also seems skewed re the solving of classical chess. If one also throws in Chess960 and other variants in the equation, then the task of solving the game will grow apace.

I harken back to the simpler days of Battle Chess (could those queens ever dismember! LOL), but I digress.

Deep Blue's defeat of Kasparov may have diminished the game in some people's eyes, but I think that for discerning observers, it displayed the complexities of it and opened up the enjoyment of computer chess to a far wider audience. In getting more people more options in playing the game, it's a good thing. So chess will survive and evolve, albeit in less romantic notions than it being a human-dominated enterprise at the very highest level.

Russ 

My argument is exactly what it seemed to be, that I disagree with:

JG27Pyth> However true these calculations may be it is important to point out that a "solution" to chess must be far smaller than the Shannon number... there is no way to say how small the solution might be.

First, Shannon's Number (10^120) is a proposed lower-bound on the game-tree complexity of chess--it's not the size of the solution, and even the author who came up with the number realized that. Second, we already have the tools to estimate the full size of the solution, and I already did so in a previous post.

JG27Pyth> Just because there are zillions of possibilities doesn't mean we need actually to examine all possibilities! We need only calculate a forced winning line... and calculate that there is no shorter, more forcing line... the "the number is too enormous" argument is less secure than it might initially appear.

Your idea is: (a) to find a solution to chess, we need to examine every legal defense by Black, but we need only find the best line for White (b) and this may invalidate 'the number is too enormous' argument.

I agree with part (a) but I disagree with part (b).

Shannon's Number is a lower-bound on the game-tree complexity of chess. It was calculated from DeGroot's observations that on average there are 30 legal positions / ply, therefore 10^3 legal positions / move. And if there are 40 moves per game until resignation then (10^3)^40 = 10^120 describes a lower-bound on the game-tree complexity of chess.

But "40 moves per game" was the length of games between human masters. In recent times we've learned that clashes between top-rated chess engines (which are less blunder-prone) are much longer. The 10-game match Rybka-Zappa, New Mexico 2007 lasted approximately 100 moves per game. So new knowledge allows us to update "40 moves per game" to "100 moves per game", and provability becomes that much harder.

Specifically, (10^3)^100 = 10^300 would be a better estimate of the game-tree complexity of chess, and (10^3)^50 = 10^150 would be a reasonable lower-bound of the complexity of finding "a solution" to chess, based on our new knowledge.

I don't claim such things are impossible--there's always divine intervention--but at our current rate of technical evolution it won't happen this century.

Likeforests: I'm careful to offer no conclusion. I state that the enormous-number-objection  "might not be as secure as claimed" ... I lack the tools and time to determine the number, but what I do claim is the ability to spot flawed reasoning and point out arguments which are unconvincing.  

First, Shannon's Number (10^120) is a proposed lower-bound on the game-tree complexity of chess--it's not the size of the solution, and even the author who came up with the number realized that...  Nothing you say there in any way conflicts with anything I've said, nor does any of it address my original point. We agree:  Shannon's Number is a very conservative estimate of the number of possible games. My point has been all along, that these estimates of total possibilities, be they of games, or of positions, are logically unconvincing assessments of the size of the chess problem we've called, "solving chess."

Second, we already have the tools to estimate the full size of the solution, and I already did so in a previous post.  No. You cite an author who calls on the same flawed reasoning as others here have -- He, offers up the total number of possible positions as somehow closely related to the size of "solve chess" problem. I reject this estimate because the solution to chess must examine positions in lines, not in isolation... This weeds out an enormous number of theoretical positions because they need never be reached as we pursue a solution.  

JG27Pyth> Just because there are zillions of possibilities doesn't mean we need actually to examine all possibilities! We need only calculate a forced winning line... and calculate that there is no shorter, more forcing line... the "the number is too enormous" argument is less secure than it might initially appear.

Yes. Well summarized.  

Your idea is: (a) to find a solution to chess, we need to examine every legal defense by Black, but we need only find the best line for White (b) and this may invalidate 'the number is too enormous' argument.

I agree with part (a) but I disagree with part (b).

To be strictly accurate, what I am saying is: Numbers like Shannon's number, or the 10^50 given as number of possible positions... these numbers are so crudely arrived at as to be unconvincing and moreover, the more I think about it, the more irrelevant they become when considering the problem of "solving chess." 

Solving chess could involve so radical a pruning of the game tree, and of the "total postions" set, that these big numbers just don't matter.

 ... IF we could look at 10^120 positions (and we can't), and store the answer, then yes, certainly we would solve chess...although as you've pointed out Shannon's number is itself perhaps a bit of a lowball. Whatever the total number of games is, if we could look at them, all, then yes, we could certainly solve chess. And I absolutely agree, we can't -- these numbers are literally astronomical. 

Calculating all chess positions, all games, this is a SUFFICIENT condition for solving chess... but the suggestion is they represent NECESSARY conditions. Why?   

Specifically, (10^3)^100 = 10^300 would be a better estimate of the game-tree complexity of chess, and (10^3)^50 = 10^150 would be a better lower-bound of the complexity of finding "a solution" to chess, based on our new knowledge.

This is just irrelevant...the total number of possible games is actually irrelevant to the solution... 

My hypothesis suggests an interesting puzzle/proof: I have designed a game which has which has more or less the same number of possible moves as ordinary chess.  So, this game can never be solved, either! Right?

My game is exactly like chess except that it is set up as follows:

 A computer that could calculate every variation possible would solve the game.  It doesn't need to be creative, as chess is a math problem.  Humans need to be "creative" simply because we can't solve the problem.  Also, programs are fully capable of strategic sacrifice.

But we know that would be pretty much the end of human race once machines start to think themselves... Do you get all your ideas from cheesy sci-fi stories?  There is no reason to believe this.

 That's pretty much the conclusion I reached. Were I to move to, say, Portland, I'd likely join.  There are apparently many cool activities/gatherings hosted by Mensa groups in major cities.  Here in Medford, though... not worth it.

Well, I am familiar with technological growth, and I find it highly probable that computers will 'solve' chess within the century.

 For more information, look up Moore's Law, which has been holding steady for about 60 years now, and I can only imagine a new law of technological advancement may be developed when newer computing techniques are fully developed, such as quantum computing (and quantum computing will more than likely be able to address the issue of 'solving' chess, because in each quantum unit, to put it simply, you can calculate an entire universe's worth of possibilities, instantly... which, theoretically, you could simulate a universe with multiple universe simulations in it in this case, thus, any speed or complexity of computing can be developed with relative ease). Also consider reading the works of Ray Kurzweil in regards to talk about disliking computers that are conscious beings.

It's actually more likely that humans and computers will 'merge' at some point, thus skipping the 'intelligent computer' phase and going straight to an 'augmented human' phase of technology.

Technology grows exponentially. And humans have a hard time imagining what future technology will hold for us. We tend to overestimate short-term gains in tech and underestimate long-term. It's an interesting phenomenon and well documented, yet we still make these same errors.

 And, in closing, I see all of this happening by the end of this century. There is no reason to think that it wouldn't happen, given the exponential nature of technology and our current level of progress.

themuz,  the line between reality and science fiction has become very blurred or perhaps non-existent for you.

"in each quantum unit, to put it simply, you can calculate an entire universe's worth of possibilities, instantly"

I don't know where you get that from, but it's simply not the case. Quantum computing, while very efficient at a few select problems in computational mathematics, is not magic. 

>  I find it highly probable that computers will 'solve' chess within the century. For more information, look up Moore's Law, which has been holding steady for about 60 years now...

Actually, Moore's Law predicts mankind will not solve chess this century.  In 92 years, technology will 'only' double 46 times according to his law.