I know that games can be solved, and that they are trying to solve chess these days.

I was wondering how close we were to achieving that goal. 

Not close at all.

 

Chess is solved for all positions with 6 pieces (including kings) or less on the board (except for 5 vs 1, which is easy to calculate anyhow). The solution for 7 pieces is estimated to be finished around 2015. Adding one additional piece increases the time to calculate signifcantly, so we are a long ways from the 8 piece solution a long long way from a 9 piece solution and you extrapolate this out to billions or trillions of years for the 32 piece solution with generous estimates.

 

Don't forget that the simple time extrapolation probably neglects the issue of where will you store the solution? If you estimate the size of the solution you'll find it's way larger than anything we could store it on. I'm sure someone will come around with these numbers soon. 

Well, if they do solve it... all you have to do is make the Knight and the Bishop trade places....Another 2000 year puzzle!

True that Loomis, there would be sooo many sooo long solutions that you'd need a whole computer to store it all up, like at Best buy, they'd sell you a chess-solving computer, no other features on it.

The team that solved checkers said it can't be done anytime soon. 

"It's probably impossible. [Chess is] just too complex," remarked Michael Genesereth, an associate professor of computer science at Stanford University, “I don't think it will ever be done."

 

ok, other question then:  How close are we to making computers that are 99% unbeatable. GMs have limits and so do computers, but in the race between computers and grand masters, who's winning.  With DeepBlue, something tells me the computers are. Am I right?

Computers are definitely winning, but it is not as one sided as you might think.  I remember reading somewhere that when you remove a chess computer's openings book and its endgame database, that even the strongest program is beatable.  In other words, when a computer program has to think for itself and not rely on pre-analyzed positions, it can run into trouble quickly because it doesn't have the two bookends that it uses to tie its strategy together.

 Am I correct on this?  I can't recall where I read this bit of chess AI info.

would it matter if they did? Even if they came up with a solution, only people trained with super memories would be able to recall it. Also there is the problem of variations. Unless the person with the super memory is also a very strong player, they wouldn't be able to adjust to any deviations. We won't see chess solved in our lifetime, and even if we do, humans won't be evolved enough to put the solution(s) to use. Long live chess!

Once quantum computers are invented chess will be solved, but quantum computers won't be invented for a really long time.

polosportply> True that Loomis, there would be sooo many sooo long solutions that you'd need a whole computer to store it all up, like at Best buy, they'd sell you a chess-solving computer, no other features on it.

It's a bit deeper than that. There are estimated to be 10^50 chess positions. Even assuming we only use 1 bit for each position (1=win, 0=loss) your computer would need at least (and probably more than) 1,000,000,000,000,000,000,000,000,000,000,000,000 TBs of storage to be able to store the outcome of all possible chess positions.

What exactly does it mean to "solve chess"?  Are you trying to find the best possible move from any possible position?  What if there were two computers that had solved chess, and they were playing each other.  Would the game always be the same, and if so would white or black win?  No, there would probably be different games because some moves might have an equal value. 

i really don't know what i'm talking about :)

The idea of solving chess is each side playing 'best move' until the game reaches a definite conclusion, be it a draw or a win. A 'solution' to chess is of little practical value anyway. 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. A solution to chess implies a forced win. Without a forced win, there would be multiple solutions. This is all really just more of a mathmatical curiousity than something of any practical value. We already have part of the solution proof built already, we call it opening theory. How many of us are booked up on all lines and know exactly how to exploit any deviation from 'best move'? Certainly not me. Stop worrying about if we will solve chess. There is NO way we will be able to apply the solution to our own games unless we were able to memorize the entire mathmatical proof in our brains with perfect recall..........not very likely folks, sorry. I'm gonna go have a beer.

If only Mensa would lower their standards a bit, I could make it in to be a genius. Then I could begin the work of memorizing the largest chess tree ever..........ever.

pvmike wrote: Once quantum computers are invented chess will be solved, but quantum computers won't be invented for a really long time.

---

 Quantum computers have been invented (still in the prototype stage though), and no, they would not be able to solve chess.

 The only kind of computer that could would be a CTC processor (but most scientists agree that making one isn't even possible due to the laws of physics)

If chess was solved, I think the game itself would be hurt by such a discovery. Imagine if it could be proven that say e4 is a forced win. This would mean that e4 would not be allowed to be used in a game cause the result is known and if black sees this as the first move, they might as well resign. Where is the fun in that?

 I hope that they never solve chess.  

Munchies wrote: If only Mensa would lower their standards a bit, I could make it in to be a genius. Then I could begin the work of memorizing the largest chess tree ever..........ever.

---

Haha.  You can be a genius who's not involved with Mensa.  I was just recently weighing the merits of Mensa, wondering if it would even be worth the membership fee.

The game won't be solved anytime soon (if ever) due to one reason only - storage.  As somebody mentioned before - the amount of bits to store each state would be enormous.  You would need a computer the size of a small planet to accomplish it - assuming you could store each bit in just one atom.

 

http://londerings.novalis.org/wlog/index.php?title=Solving_chess

 

I agree with JoseO. If chess were solved, the game would lose its mystery and sense of infinity

uh, I think computers are known to make sacrafices but not like GM sacrafices.  for example, a computer would sac a queen for a forced win...

 Now, would a computer sacrafice a knight even though it wasn't going to be a forced win?  Probably not...

 

But i heard earlier that instead of putting all solutions possible to each move... we should try and eliminate the ones that are obviously stupid which would cut back but still, chess would be better off unsolved

 Here are two snips from the Net:

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.

The number of legal positions in chess is estimated to be between 10^43 and 10^50, with a game-tree complexity of approximately 10^123. The game-tree complexity of chess was first calculated by Claude Shannon as 10^120, a number known as the Shannon number.

================

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 and there is no way to say how small the solution might be.  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.  For example, consider:

 

 

 

 

 

 

There are a staggering number of possible games available from this position!  I don't have the mathematical chops to figure out how many possible continuations there are from here, but it's a lot... How many different ways are there to play from here, 50 moves, without repeating a position three times?  Yet, none of that has the slightest bearing on the fact that this position has been solved... we don't need to store those positions, or calculate them, or bother with them in any way, to say that from my diagram, the postion is solved. 

I don't know if chess can be solved, but the "the number is too enormous" argument is less secure than it might initially appear.