Will computers ever solve chess?

I tried to read all the responses but I stopped about page 7.  But I wanted to see if anyone had said "compression" or "machine learning" ("deep learning").

A few people wrote about mathematical rules that could be found to determine if a position is won.  Basically the best hope for solving chess is to drastically (more than the square root) reduce the amount of actual thinking that has to be done, by finding some clear patterns.

For humans, the questions in chess concern games where the two sides are nearly equal.  What if White simply blunders away a Queen on move 4?  I hope we can prove Black would win.  Then if we compare random moves to moves that are considered pretty good, we see there are many more awful moves than moves that seem close to winning.  So when I picture the space of all games, I think of a large continent of games where some idiotic moves are made, and a much smaller area of games, the boundary, where all the moves are really decent.

To me, some hope lies in the thought that there are some clear patterns, based on material and position, so a computer could mathematically eliminate a great number of move choices, and then the game could somehow, someday be small enough to solve.

The obvious drawback in this approach is that it's very difficult to teach the poor computers to avoid miscategorizing bad moves and exceptional-looking positions. If Black gives away all but 1 piece and the result is something like a composed puzzle where Black has a forced smothered mate then this requires extra work to compute or detect.

Unfortunately in most positions with even material there are usually 2-7 or more interesting moves that don't just throw away material or positional value, so the combinatorial explosion is huge.  Basically the only hope, given the numbers, is to find some strong improvement of the evaluation function.  The basic idea might be to compress the tablebases drastically.

I think it's hopeful for the solution to ever be completed that computers are learning to improve their own software.  Stockfish has a program called Fishtest that is used to evaluate whether changes to its evaluation function are valuable, using crowdsourced computing power, and if the wins are increased in a large sample of games then it is included in the software.  This is a little bit like a "deep learning" approach I think.  Chess is too complicated for humans to figure out all the patterns, but if we leave the real programming to computers, it could be another area where they excel humans.

It is just a point of terminology, in psychology or neurology, that the "short-term memory" is much shorter than a week.  It's about 15 minutes I think (But I'm wrong, according to Wikipedia - it's even shorter.  https://en.wikipedia.org/wiki/Short-term_memory).  If anyone remembers anything longer than this, then it's becoming a long-term memory.  That is just the way psychologists use the term "short term memory".  

Thanks for writing something that actually discusses the topic. A quick persusal of this thread reveals tons of crap on this thread which has nothing to do with computers solving chess.

The topic of machine learning is interesting. As you mentioned, Stockfish is using "crowd-computing" to iterativelly make their engine stronger, and this may prove to be the best strategy for developing the best chess engine. (I'm sure you're aware it recently won the chess-com-computer-championship).

I just wonder if this can be taken to the level where chess becomes "mathematically solved". An engine that always wins (or never loses) would be a monumental achievement. But a mathematician can always argue that not every branch of the game-tree has been explored.

But then on the other hand, maybe deep learning can overcome this objection too. Really interesting.

I thought about that, but then...using the term long term memory or just memory just implies more credit than is due .  I added short to make it more clear that he'd forgotten his rambling post from a week before, not to delineate an actual threshold between short term and long term memory.

Venturing into the magical world of AI what-if doesn't really count, in the same way that positing a new subatomic particle or interaction is discovered that is perfect for computation and data storage doesn't count.  It's a call for magic to occur. 

South Park teaches us this truth:

Step 1:  gnomes steal underpants

Step 2:  ???

Step 3:  profit

If you can't lay out how step 2 may reasonably occur, any reference to step 3 is fantasy.

It's the difference between soft science fiction and hard science fiction:

Space elevator --> almost assured to happen one day

Warp drive --> magic

Computer learning ala AlphaGo --> assured to keep advancing slowly

Computer solution via AI reprogramming itself entirely. bootstraping itself further and further beyond humanity's understanding and employing mathematical proofs that are beyond mankind's understanding/capabilities to apply to chess --> magic 

Your last paragraph tries to make this prodigious leap from Step 1 to Step 3, but it's too long a jump.  Still magic at this point.

The next/additional problem is that even if your solution came to pass, the problem of "solving" chess by the definition of solved games implies that humans can actually comprehend the final solution, and there a strong probability in the "AI advances beyond human ken" story/wish that humans would not even have a way to figure out the answer provided...

Douglas Adams teaches us that:

42 might be the answer, but if we cannot understand it, it's meaningless.  

We had this discussion long, long ago in this thread, that solving chess requires a communicable soltution, ergo solving chess without storing the evidence in data storage to get around the resource contraints is not actually a solution, because it cannot be re-proven nor communicated.  In a similar vein, the possibility of solving chess using methods beyond the comprehension of mankind would not really be a solution from mankind's perspective.  

I suppose we could take yet another step into the world of fantasy and say that our computer overlords would be able to come up with a way to "teach" the human brain beyond it's capabilities in that case...but then we're just farther from reality and we might as well enter sbog territory and muse that a goldfish might solve chess for us...

Not in our lifetime, sorry.

But this mindless thread will run-on for years, unfortunately ??

Nope, chess can't be solved.

FAQ for Will computers ever solve chess?

1. Is chess a finite game?

Yes, chess is a finite game. There are a finite number of positions, each of which has a finite number of legal moves leading to another position. Each game could go on forever except for the rules added to allow the claiming of a draw when a game is going round and round in circles (only the rule about repetition is needed).

2. Does chess have a result?

Yes, game theory says that in a finite game of perfect information there is a pair of strategies for the players which can achieve the same specific result and which has the property that no alternative to either of the strategies can get a better result against the other. The result that is reached when the two players play these strategies is the true result of a perfect game of chess.

3. Can we find out what this result is?

Theoretically.

It is easy to write a short computer program that will determine the value of any finite game of perfect information such as chess. The problem is that for a game as large as chess such a program takes a stupendous time to run (unless it has most of the answer coded in it which will make it stupendously large and require near enough answering the question to write it).

4. Is there any chance that computers will ever solve chess?

The laws of physics (uncertainty principle relating time resolution and energy and information theory giving a finite amount of information per bit erasure at a given temperature) mean that any program running on a conventional computer that could solve chess would have to use a stupendous amount of energy for a very long time (more than a planet can provide). So, the answer "no" is justified.

[EDIT: the theoretical class of thermodynamically reversible computers avoid the erasure of bits, so avoid the minimum energy expenditure. It is unclear what the storage requirements would be].

5. What about quantum computers?

It is not entirely impossible that a quantum computer could solve chess by being able to model stupendous numbers of parallel lines at the same time, but this is mere speculation without details and no hypothetical design for such a computer (even an impractical one) has been published yet.

@elroch :

point 4 : where comes the info from from ? and who says that better energy sources will never be available if the current ones are not sufficient ? E = mc2 and there is a lot of m ... 

point 5: who says quantum computers are the best possible computers even in the future ?

Personally I think that it would be possible to proof that the brute force way of calculating chess is possible or not, given the number of possibilities in chess compared to theoretical storage possibility of information. I am very unsure about "smart" calculation ...

Thanks @Elroch, concise and to the point.

Now a sensible person might disregard the other 3619 posts, and this silly thread might be washed away -- until the next breathtaking advance is announced by the Tech Prophets. 

Nobel Laureate Herbert Simon predicted computers would beat the World Chess Champion  in about 10 years.  Instead , it took 40 years.

 A "solution" might take 400 years, or never.  

https://books.google.com/books?id=xQwwESPo8wsC&pg=PA153&lpg=PA153&dq=when+did+Simon+predict+computers+would+beat+World+Champion?&source=bl&ots=uN_Bvr0hgN&sig=YhsjbgCqI72i9c14nWywgpzMfg4&hl=en&sa=X&ved=0ahUKEwjQsIuU6c_XAhUX8WMKHcZHA6UQ6AEIJjAA#v=onepage&q=when%20did%20Simon%20predict%20computers%20would%20beat%20World%20Champion%3F&f=false

This thread is testament to the fact that we can IMAGINE a solution to chess.

No more or less.  Just live with it.

I don't think a chess 'solution' needs a 'stupendous amount of energy'. A chess game is basically over after about 30 moves. Someone makes an error and they lose. There is no coming back. There are more moves but the person who made the error slowly or quickly loses. It's complicated for the first 12 - 30  moves, then gets less complicated as the pieces are removed.  People try to make it a battle that has infinite solutions, but it's not. It has a limited number of solutions.  

Well stated, and I pretty much agree with most of it.

Take note that on item 4 however you correctly qualify the statement by saying "conventional" programs. This is an important qualifier because the number of unconventional solving algorithms outnumbers the number of chess games. In other words, the scope of solving strategies outnumbers the problem. Btw, for people interested in this topic, it's also interesting to note that this same question is discussed at math forums, and the possibility of solving chess within a few decades has not been ruled out.🤠

My wording was not good. I meant "program running on a conventional computer".

After I wrote this, I realised there was another point that needed to be made. The physical reason that conventional computers require a certain amount of energy per operation is that they erase information. The erasure of one bit requires a minimum amount of energy which is proportional to the temperature.

However, there is a class of (mainly theoretical) computers that use completely reversible operations studied by Bennet (and showing von Neumann to be wrong!). These computers have no minimum energy per operation. However, the question is whether the storage requirements of such a computer used to solve chess could be kept under control. Eg see Bennet and Landauer's SciAm article, The fundamental physical limits of computation and other papers like Ultimate physical limits to computation by Seth Lloyd.

They probably haven't ruled out P=NP either, which would make this problem easier.

Perhaps that is purely a joke, but P=NP is entirely irrelevant to the solution of a game of a fixed, finite size.

Try not to be too pedantic, chess is only trivially in P, since the lookup table can't be stored in this universe. "Generalized" chess is in EXP (so, yes, not in NP), but there are subproblems and generalizations of chess that are NP-Complete, such as the n-Queens problem.  

Mathematics and computer science are entirely pedantic.

P versus NP and all other similar propositions are about limits as some number tends to infinity. They may have relevance to practical problems, but complexity is about infinite sequences, like the prime number theorem is.

There is no reason to believe that the tablebase for chess cannot be stored in the Universe even in the relatively crude way we would do so for a conventional computer: we have no upper bound on the size of the Universe.

However, it is true that it would take a stupendously large storage device (again, using  extrapolations of current storage techniques) .

Extrapolations that involve hiding a second universe in your pocket? 

It's game tree complexity that's bigger than the observable universe, not the number of legal positions. That number of entries is still waaaaay too big to "store" in any normal sense of storage. 

Also, if P=NP, "secure" online credit card transactions will no longer be secure at all. I hope that's practical enough for everyone. 

You didn't say "observable Universe" before. We can be sure the Universe is bigger than the observable Universe, but can't be sure how much bigger.

Actually even if P=NP, it wouldn't necessarily break public key encryption: polynomial time is often prohibitive if the power happens to be fairly big, and all that is relevant is how big it is for a specific finite problem!

no. There are too many possible positions.