Will Chess ever be "solved"?

I thought about this for a moment and it occurred to me that it probably doesn't work that way. I know there are other people (Optimissed or Nikki) who know more or could explain it better.

But I think the rate of improvement of computer in the 1940s vs now is not sustainable in the future for solving chess. Geometric progression I think it's called. Technology increases at a certain rate, but it can't keep that rate forever. Or even the 80 years you suggest. 

For technology to keep increasing at the rate needed we would see things like 10,000 mph cars, every human connected to the oracle of knowledge, and time travel. There comes a point where it just physically can't go much further, or at all. 

5 years ago or so I did a back of the envelope analysis using the fastest supercomputers at the time.  The gist of it was that even if you spent the entire world's money (roughly $80 trillion at the time) and created 290,000 of the world's fastest super computer, it would still take more than 3 million years)...and the human race would die through lack of resources, so... no, not going to happen.  That's even setting aside the storage issue of the universe not having enough matter .

"Calculating forward" does not work until you have already traversed the vast majority of the positions.

Ahh...here it is:

"100 PetaFLOPS is 10^17 floating point operations/sec. Evaluating a chess position is not 1 operation, mind you, nor is it 10, so let's be kind and say it falls in the 100s order of magnitude, which knocks 10^17 back down to 10^15 positions/second, which is 8.64^19 positions/day, 3.15^22 positions/year.

At that processing rate (assuming infinite memory/storage and ignoring all the issues thereof already laid out) you would solve chess in...3.175^24 years. I guess you could amortize a loan for the duration on the $273 million for the supercomputer...

Adding in storage, you solve chess...never (in this scenario).

So, the fastest supercomputer could solve checkers in a matter of seconds (10^17 FLOPS vs. calculating 10^14 positions), but it will take 3.175^24 years to solve chess. If you spend the entire wealth of the planet (approx. $80 Trillion in currency) to build an array of these supercomputers, approx. 290,000 of them, and use them all for solving chess leaving the human race to starve and die, it still would take 3.8 million years."

 

Even if you were to posit a *thousandfold* increase with quantum computing (not happening in our lifetimes either), you'd still be at 3800 years .  Still ignoring the impossible storage, mind you.

Usually when people say solved, at least people in the know, they define as "weakly solved", meaning that whatever you opponent plays, you have a known move that will end the game in a win or a draw. 

It's not necessary to calculate every position know to find the answer, simply to find a way to choose a move that will always ends the game in a win or a draw. 

The example I always use is tic tac toe on an infinite board. With an exhaustive search, one can argue it is more complex than chess, since each turn the player has infinite choices, while in chess there are only a finite number of positions. However, it can be weakly solved trivially where the first player always wins. 

"simply to find a way to choose a move that will always ends the game in a win or a draw"

Lol.

You sound like Q from that Star Trek episode..."simple...just change the gravitational constant of the universe...".

P.S. "infinite" and "exhaustive"

Technology goes forward. In 1940 vacuum tubes –> bipolar transistors –> field effect transistors –> quantum computing –> ? –> ?

https://en.wikipedia.org/wiki/History_of_computing_hardware 

It does not has to be computed with a single supercomputer. SETI and Mersenne Prime search use clusters. Maybe 10 billion computers end of this century.

https://en.wikipedia.org/wiki/Search_for_extraterrestrial_intelligence 

https://en.wikipedia.org/wiki/Great_Internet_Mersenne_Prime_Search 

More efficient storage: Nalimov 140 Tb Syzygy 18.4 Tb for the same.

https://en.wikipedia.org/wiki/Endgame_tablebase 

No complete table bases are needed. To prove chess a draw it is possible to either trace the initial position towards a table base draw or to prove the initial position cannot be traced towards a table base win.

 

So now we go from Q to South Park's underpants gnomes ...

I just said that a cluster of 290,000 of these super computers would still take 3.8 million years to solve.

Prime search and SETI are trivial, linear problems by comparison.  SETIhome was 235,000 computers with *maybe* 100 GFLOPS each (that's being extremely generous given it started in 1999).  So, a total of 23,500,000 GFLOPS, which is 23.5 billion FLOPS.

1 quadrillion FLOPS per PetaFLOPS.  17 PetaFLOPS per supercomputer...so just one of these $273 million supercomputers I mentioned is roughly 725,000 times the processing power of your entire SETI cluster.  Now, let's multiple the 725,000 by 290,000 of those super computers...that's:

209,787,234,043 SETI clusters needed to do the job in 3.8 million years, or roughly 800,000,000,000,000,000 (800 quadrillion) years for one SETI cluster to solve.

Maybe now you can start to appreciate what 10^46.7 really means.

10^120 possible chess games, 10^46.7 unique chess positions.

#77
Yes, but you calculate with present technology and present economics.
Imagine somebody had in 1940 asked the question if checkers could be solved. Back then based on ENIAC the answer would have been that it would take and unfeasible time and cost.

https://en.wikipedia.org/wiki/ENIAC 

Imagine it will be solved and, surprise!, black can always win, so initial position is a sort of zugzwang

Syzygy also lists 423,836,835,667,331 positions, not only the draw/win/loss evaluation, but also the possible moves, not needed for a proof.
Chess needs no FLOPS floating point operations, but boolean operations on digital bits. 1 move = 12 bit.

Sorry, but you're not going to cut 3.8 million years in an already impossible scenario to "within our lifetimes".  You might as well say God will come down and hand you the answer.  Same probability.  

Moore's Law is slowing drastically, not increasing.  Silicon is reaching the limits of distance vs. light speed.  Switching to Gallium Arsenide will not make it much better, and is way more expensive.  Quantum computing also has no foreseeable way to increase mankind's processing power by the 7-8 orders of magnitude required, nor have the more limited instruction sets of quantum computers even been shown to be applicable to the problem yet (at least not the last time I dug into it).  Quantum computing is faster for modeling chaotic systems, so will likely predict the weather worldwide long before it makes even a small dent in chess.

Some people offer long and detailed explanations as to the major obstacles involved.... and then there are those with zingy one-liners with zero analysis beyond “quantum solves everything” or “computers keep improving so duh.” It ain’t happening folks.

Google doesn’t even care enough to continuously update Alpha Zero. Does anyone actually think that anyone is going to to dedicate the computer resources necessary to do a 10 or 11 tablebase? We’re talking exabytes verging on zettabytes. The entirety of the monthly US monthly traffic is about 300 exabytes. What kind of moron would waste that kind of storage on something as trivial as a tablebase? Nobody!

Why don’t we talk about something less silly like how many angels can dance on the tip of a pin or how many tons of unicorn poo it takes to fertilize trees that grow golden apples.

You can't get people to talk about something less silly until you show it to *be* silly .  I am retiring for the evening, however.

Quantum computing has been demonstrated to be 10^14 times faster than a conventional supercomputer.
https://science.sciencemag.org/content/370/6523/1460 

Checkers has 5 10^20 positions, but to solve it only 10 men table bases were needed with 3.9 10^13 positions stored on 237 Gbyte. In 1940 with ENIAC at 5 operations per second this would have been totally unfeasible.

To look ahead 80 years, look back 80 years.

3.8 million years / 10^14 = 1 second

You're getting ahead of yourself.  Now walk back what some academic abstract has posited and go find what quantum computing has actually solved/done thus far.  That is what constitutes "demonstrated".

I can show you an abstract from NASA about warp drive .  It doesn't mean that FTL travel is coming in our lifetimes.

P.S. Your maxim about looking ahead does not hold up.  If you look ahead 300 years from the Fall of Rome, you find yourself in the middle of the Dark Ages...and coincidentally, we're in the decline of another empire right now...

     There's no telling how technology will advance, or how quickly. The steam engine was discovered by ancient Greeks (early centuries AD) but was only used in small devices, mostly for amusement, as metallurgy hadn't produced a material that could withstand the temperature and pressure that a steam engine powerful enough to run a large machine would produce. Several centuries later, in a different culture, high-quality Damascus steel was introduced, but by then the steam engine had been forgotten. A few more centuries passed before practical large-scale steam engines were invented.

     Had stronger metals existed where and when the steam engine was first discovered, or the toys using them remained popular, or an Arab engineer looking for other uses for steel stumbled across the records of early steam engines, the industrial revolution would have started centuries earlier and today's world would be vastly different (or perhaps already destroyed by global warming).

      The point is that using the limits of present-day knowledge to predict the probabilities of future technological advances is highly uncertain. Hippocrates never would have believed that a man's bladder and prostate could be removed and a piece of his intestine could be repurposed to let the urine drain out of the body, but I am living proof that it can be done.

     It may be that 500 years from now the problems of computing and data storage mentioned here will remain unsolved, or somebody later this century will come up with a unique idea that solves the problem using techniques unimagined at present.

     So I still believe that chess can and probably will be "solved". Still, that won't affect how humans play.

Ermm, no...that one's already done and gone.

The British may arguably have done it better (though they also caused more damage and did less good), but as any good Diplomacy player will tell you, the advantage of having an island as the seat of your empire cannot be overstated.  And one with natural cliffs for walls and a narrow channel as a natural moat to boot.

This is the version I have:

The elevation key is funny because it has absolutely zero effect on gameplay.

You would remember. The game feature of Diplomacy is that the only way to win is to cooperate, but there can only be a single winner.

You must stab your teammates in the back or else. 

My advice on both Diplomacy and Risk. If you are playing for the first time with a group of people you will be playing again and again, do not win. If you do, and they are any good, you will never win again.