How close are we to solving chess?

 If resources = beer, cheese doodles and hard rock music, then I can say with absolute certainty that the answer is "yes."

likesforests> "10^150 would be a better lower-bound of the complexity of finding "a solution" to chess, based on our new knowledge."

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

That's not what this number represents. 10^150 represents a lower-bound on the complexity of calculating a single winning solution to chess. It has nothing to do with calculating all chess positions or all games.

Step #1: Assume such a solution exists--or else it's even more complex. :)

Step #2: How long would a game between two perfect chess engines last? It's obviously more than 30 moves considering the state of modern opening theory. Games between 2300+ humans often last 40 moves. Games between 3000+ engines often last 100 moves. Games between perfect engines would probably last longer but we'll err on the low side (to come up with a lower-bound) and say 100 moves.

Step #3: How many moves do we have to examine for White? We'll assume by some magic (mathematical formula, efficient pruning, etc) you can select White's best move 100% perfectly and say 1 move. 

Step #4: How many moves do we have to examine for Black? To prove you have a winning solution you need to examine all of Black's legal moves. DeGroot's did extensive analysis and discovered that, on average, a player has 30 legal moves. 

So (1 x 30) ^ 100 = (30 ^ 2) ^ 50 = (900)^50 =~ (10^3)^50 = 10^150.

JG27Pyth> "I have designed a game which has which has more or less the same number of possible moves as ordinary chess.

This example is crude as you say, but we can apply the same steps to your game:

Step #1: OK

Step #2: 1 move. 

Step #3: 1 move. 

Step #4: N/A - Black has no part in your example.

So 1^1 = 1. The complexity of your game is 1. 

There may eventually be a computer that can calculate a path to mate from any opening, but what good is it going to do the average player? Little to none.

 Even if it could be proven that say, White to e4 can win every game, there is no possible way any human could memorize the millions (billions?) of various permutations for black's possible responses. In other words, if black goes "off script" from the optimal move tree, white is right back to having to work with tactics and position instead of predetermined moves. Even the most gifted and talented thinker on Earth would have difficulty memorizing more than a few hundred complete chess games, and that's not even close to what would be needed.

Computing power may eventually render human vs. AI chess obselete, but unless evolution bumps up our lifespan to several million years (and our brains to match), I wouldn't worry about chess being solved anytime soon.

Optimally solving chess will likely not occur for many years.

However, computers are definitely at the point that they can brute-force enough continuations of a line to beat any human.  A decade later, it would be fairly simple to create a more powerful version of Deep Blue that would run on a PC, using FPGAs, instead of the MOSFET ASICs used in Deep Blue.

Check out Hydra, an FPGA-based chess computer.  Apparently, it's never lost to an unaided human.  http://en.wikipedia.org/wiki/Hydra_(chess)

When I wrote this, I hadn't seen that there were 3 pages in the threath... so I think all my points have been mentioned by others on page 2 and 3 (sorry)... anyway, since I used time on wirting it, I let it be...

Munchies wrote: To create a mathmatical proof of this chess answer would be dealing with numbers beyond our comprehension. For each 'best move', there would have to be conclusive lines of why the "not best move" loses. Take for example the very first move. Let's say the solution of chess gives e4 as the answer to the first move. There would have to be an answer to why the other 19 possible first moves available to white are incorrect.

I do not agree with you on this part. If you find a "sure win for white" starting with 1. e4, then you had solved chess. All the other lines would be of absolutely no interest for that prove.

To the discussion about the possibility to find a "solution to chess". It is correct that there is aproximately 10^50 legal positions... and therefore there are estimated 10^123 possible chess-games (see http://en.wikipedia.org/wiki/Chess#Mathematics_and_computers). Compared to the number of subatomic particles in the universe, wich is estimated to 10^80, it will be physically absolutely impossible to search through all this lines. If we could use all of the particles, they should handle 10^43 games each. And since the age of the universe is estimated to 10^18 seconds, they should handle 10^25 games each, every second through the entire existence of the universe... that is not possible.

But from a mathematical point of view, there do exist a "solution to chess". In game theoretic terms chess is a "finite state game", and they do have solutions. The "solution" or "theorem" would be one of the following three:

1) There is an optimal strategy for white, that always gives white the victory.

2) There is an optimal strategy for black, that always gives black the victory.

3) If white and black both play optimal, it will allways end as a draw.

Personally I think 3... :-)

Kasper Bjering

PS: Ofcourse my calculations are very simplistic... There will be many games that we didn't need to search through, e.g. after 1. e4 e5 2. Bc4 d5 3. Qh5 Nf6 there can follow approximately 10^115 games, but only one - 4. Qxf7# - would gain our attention. But since we do not have all the subatomic particles to be used and since we may only use around 10^10 seconds (300 years), then the calculations says a lot anyway.

 good thinking...

Doubling 46 times is a lot of improvement.

 Take into account we will develop new technologies like 3D stacked processors, quantum computers (probably, and I was off with my last statement, but in comparison to our current level of technology, that's what I was being analogous to), possibly using neural nets as computing devices... I don't see Moore's Law being relevant any more after a while.

Then, I forgot to mention how they are using computers connected via the internet to create a 'web' of computers, all working on parts of a computing problem to make a sort of 'macro' supercomputer, and if we were to combine those technologies together, I'm sure we'd have more than a 'measly' 2^46 growth in computing power.

 But science fiction and reality merging? Well, we have artificial hearts, men can carry babies, and we can grow limbs in labs... We have computers embedded into sunglasses, refridgerators, cell phones that you can watch movies on, the internet (thank you, Al Gore!), all sorts of technological development. Consider how big of a difference that is from 92 years ago, then increase that level of improvement, exponentially. The only problem is that it is hard to put some numerical value to 'technological growth', so how can you calculate an exponential increase in it?

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

Likeforest> That's not what this number represents. 10^150 represents a lower-bound on the complexity of calculating a single winning solution to chess. It has nothing to do with calculating all chess positions or all games.

I have to concede that you are correct here and I had misinterpreted Shannon's number.  That said, my Sufficient but not Necessary critique still holds... indeed that paper you cited (Searching for Solutions in Games and Artifcial Intelligence /
L. Victor Allis) is really an expanded in depth and academic/professional (as opposed to you and I -- dilettante's both, I suspect ;0)  examination of the very questions you and I are debating.  Calculating out all the lines in that 10^150  game tree represents the lower-bound on a brute force "strongly solved" proof. (The author discusses three levels of solution, ultra-weakly solved, weakly solved, and strongly solved). 

My point all along has been that trotting out these big numbers is  simplistic -- bull-dogging thru all 10^150, (or 10^300, if you prefer) may not be necessary. And the authors are examining that very question -- when is it necessary, and when not, when can a game be solved, by what approaches.   Allis cites Hofstader's Mu-problem. I won't reiterate it here, but the point of the problem is that while calculating the problem is fruitless, thru recasting and rechunking the problem it can be solved quite intuitively... moral of the story, how we model a problem dramatically changes the 'solveability' of the problem.

In the words of Allis: A well-chosen representation may considerably reduce the amount of search needed to solve a problem, while a badly chosen representation may render solving a problem (virtually) impossible.

Endgames gave computer's fits, until Nalimov and his tablebases showed up, now, what is it? -- 6 piece endgames are solved?

It is hard to imagine how that tree can be pruned (and perhaps it can't be done... but no one has proved that)... that does not mean it can't be done.  

However, my original belief was that shannon's number represented all games... and I must admit, no, it does not, you are right, 10^150 is in fact already a _deep_ pruning of the full game tree (assuming the 50 move draw/3 repetitions of position rules are automatically enforced.)

I wonder what standing Viktor Allis has in the Information theory field? I'm not qualified to judge the technical aspects of his paper, but that sure looks like good work. 

JG27Pyth> Allis cites Hofstader's Mu-problem. I won't reiterate it here, but the point of the problem is that while calculating the problem is fruitless, thru recasting and rechunking the problem it can be solved quite intuitively... moral of the story, how we model a problem dramatically changes the 'solveability' of the problem.

I agree. As the problem is known now, and given the rate of technical advance we've seen over the past 40 years, we won't solve chess this century. But a solution may be possible if someone finds a revolutionary way to look at the problem.

Fermat's Last Theorem is an interesting example. It remained unprovable for a thousand years. When personal computers became a reality, some folks let their computers run for months trying to disprove (or provide more empirical evidence for) the thereom. Then something surprising happened--a guy studying elliptic curves found a new way of looking at the problem, and 30 years of study later the unprovable had been proven. :)

I agree with Blackadder - chess is nearly solved, practically speaking.  If it isn't, then the means to solve it exist already, but perhaps not the motivation.  It takes a lot of money to build the machine and pay the staff!

You don't have to have the entire tree pre-calculated and at your fingertips to claim a solution.

Currently the best programs can almost defeat the best GMs in a tournament conditions. These programs win against normal GMs.  How many GMs in the world can withstand the machine that defeated Kasparaov a few years ago? Maybe 3 have a chance? Since then, machines have gotten better and will continue to do so.

Regarding the idea that strategic sacrifice is exclusively a human capability... poppycock.  When computers do it it's just a combination.  Computers don't speculate.  Humans do because they can't see deep enough to be sure. 

"But we know that would be pretty much the end of human race once machines start to think themselves..."

I rather believe that also, actually.

A lot of this debate depends on the definition of "solved."  If solved means "unbeatable by humans" then it is nearly so.  If solved means "hard proof gained by playing every possible move in every possible variation" then the sun will nova first.

The inbetween stage is almost upon us. This is where computers are unbeatable by humans yet the entire game hasn't been hard-solved.

or if by "solved" you mean a computer that is completely 100% unmateable, then i think it could be done soon as well.  if black and white are equal then a solution to chess isn't a "winning" solution per se, it's a non-losing position.  that is to say that if black and white are equal then two 100% perfect computers playing eachother will always draw, and one of those computers playing a lesser computer or a person would either win or draw 100% of the time, there would be no losses possible.  keeping that in mind broadens the definition of "solved" for chess because a computer can play down to a draw, whether by trading down, 3 move repetition, stalemate, etc. 

1)

Guys like Berliner will never believe a computer, if the computer evaluates the psoition as  "8:2", and  if he believes  the opposite. 

Why?

Computers don't show an analysis which convinces human, because the variant tree is unimaginable already  after 5 half moves!

Kasparov asked , after the loss of his match, the team of Deep Blue for a printout of the computer's analysis. They didn't give him one, since they don't had it in their possession . Then Kasparov accused them  (wrongly!) of cheating.

You can ask for  a narrow part of the analysis, that is, for some exceptional linear variants, but never for a COMPLETE PROOF of a computer's judgement. That judgement would fill some hundredthousand pages, nobody will and can read them  ...

2)

I call the  chess problem " approximately solvable" for a computer IF there exists a certain "magical" number R of half moves such that every analysis which is exhaustive (=complete) up to number R, allows with a VERY small percentage of exceptions - say 1 percent -  to evaluate the resulting final positions (win/loss/draw) with the following two SIMPLE criteria 

(a) material,

(b) evaluation of the strength of the position, but based only on some clear mathematical formula (and not on abstract considerations). For instance , such a formula could  count the total number of squares which are controlled by all the pieces on the board.

The existence of such a number R is quite possible, since it seems by now that a GM has a chance only if he pushes the computer into a "long" strategic water,

where the outcome of the battle can be determined (by computer) only with VERY long variants (which are hopefully beyond the computer's horizont).

Those situations seem to happen less often from year to year. 

My guess is, that there just do not exist so many of such situations in chess!

What, if every one of the "deep, long" strategic plans of Rubinstein, Nimzowitsch and others  can be checked and evaluated (with the above simple computer-criteria) based on variants which are never longer than, say, 26 half moves?    

Mandelshtam

P.S.: Don't worry, chess will not be dead by this. We just don't have to play the "monsters"...

Also, an interesting alternative are matches between two humans, both equipped with a chess program which they can use at any time.

The recent practice of correspondence chess shows that such a tandem

(= program + human) is much stronger than any chess program alone!