Will computers ever solve chess?

Sort:
Elroch

There has been some progress towards 3D design. But thermal issues are going to be important. CPUs run hot even without reducing the surface area for cooling, eg 1.4 billion transistors in 130mm^2 on mine, generating 77W at design speed. Or a fair bit more when I overclock mine. 

So very low power designs are needed for deeply 3D processors.

Elroch
vickalan wrote:

Using data from humans and engines doesn't mean anything because we (humans) and engines don't play perfect chess. You can't say "chess cannot be solved" and at the same time say that humans have solved it.

 We can safely say humans and computers have not solved chess. 

However, existing chess can be viewed as stochastic (except where perfect play is accessible). This means moves are made which have random errors associated with them,

When two players both make random errors of similar sizes, it seems highly likely that the statistical results will tend to be closer to the true value of the game than some other value. If the true value of a game of chess were a win, we would see a gradual reduction in variance of results converging towards 100% for white. What we actually see is a gradual reduction in the variance of results converging on a slight plus score for white, not converging on 100% for white.

White's plus score can be viewed as an artifact of imperfect play. With real chess engines, rating is increased steadily with computing power. Because of the practical advantage of the first move, it seems black requires a bit more computing power to be equal (equivalently, a small advantage in rating).

I do not believe there has been any reduction in white's advantage with increasing quality of play, either by GMs or computers. This makes sense because if white's practical advantage corresponds to say a score of 54%, and this corresponds to an Elo difference of 28 points, this is going to remain until an engine is so good, there is no advantage to running it faster. We are a long way from there.

vickalan
Nathanhof wrote:
 
...Why do you think we'll find a forced mate within 40 moves when we already have computers that calculate that deep and cannot find a position even close to a mate?

 

The Shannon number (10^120) is based on a chess game of 40 moves. There's no engine that calculates exhaustively that deep from the starting position. There might be forced mates beyond 40 moves, but paths to a mate may be within this number too. I don't know if any forced-mates will be found in chess, but if there is, the first ones found will probably be within the game-tree size assumed by Shannnon.

DiogenesDue
Elroch wrote:

There has been some progress towards 3D design. But thermal issues are going to be important. CPUs run hot even without reducing the surface area for cooling, eg 1.4 billion transistors in 130mm^2 on mine, generating 77W at design speed. Or a fair bit more when I overclock mine. 

So very low power designs are needed for deeply 3D processors.

You're being kind with your "deeply 3D" term.  Apparently s23bog is unaware of the fact that circuit boards are already multilayered and 3 dimensional.

DiogenesDue
s23bog wrote:
btickler wrote:

Checkers was solved:

 

"Draughts, English (Checkers)This 8×8 variant of draughts was weakly solved on April 29, 2007 by the team of Jonathan Schaeffer, known for Chinook, the "World Man-Machine Checkers Champion". From the standard starting position, both players can guarantee a draw with perfect play.[10] Checkers is the largest game that has been solved to date, with a search space of 5×1020.[11] The number of calculations involved was 1014, which were done over a period of 18 years. The process involved from 200 desktop computers at its peak down to around 50.[12]"

 

Chess will not be.  10^46 is quite a bit more difficult than 10^14.  Over a billion billion billion times more difficult.  Eighteen years won't cut it.

 

On what basis do you impose limits on what can be accomplished?  Clearly define the boundaries of what is possible. And not with some wishy washy blurb.

You find paragraphs full of straight facts wishy-washy, do you?  

Nathanhof
s23bog wrote:

To illustrate my point .... let's try to figure out how many different possible paths there are to the following position:

 

Infinitely many, I can play around with the horses and queens , bishops and kings and still get in that position.

DiogenesDue
btickler wrote:

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.

Here's the factual line in the sand, s23bog, Vickylan, etc. that you keep pretending not to have seen (it's on page 63).

 

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.  

 

All of this is completely ignoring the physical limitations of size for storing the results, which just makes this problem that much more impossible,  Even if you mined our solar system's entire asteroid belt to a speck of dust, it would not even come close.

 

You guys just don't seem to have any grasp of really big numbers.  Saying that because we can solve checkers that chess is right around the corner, for example, shows a child's understanding of the problem, but worse, even when the gaping holes in your arguments are pointed out, you just pretend it doesn't affect anything.  You're willfully ignorant by the most literal definition of the term.  Maybe a human being's worse possible sin after pure malice wink.png...

 

So, I'm calling out all the vague BS about technology advances that will make this possible in our lifetimes,  If you can't fully refute this line of logical reasoning with hard numbers, then you have no argument.  You're bad poets, not even bad scientists wink.png...and you're just continuing to play with your own...imaginations, without a leg to stand on. 

 

If you want to jump on the "let's just re-define what solving a game means" bandwagon, that would be better.  At least that camp admits brute force solving is completely impossible, now and for any possibly foreseeable future.  Do you guys know the difference between hard and soft science fiction?  Soft science fiction is actually fantasy, just set in a technological venue, but it might as well be dragons and magic, because the technology is pure imagination.  That's where you live wink.png.

DiogenesDue
s23bog wrote:

Ah ... that surely is a line in the sand.  Try defining what is possible without using money.  Money is most certainly wishy-washy.

I remember how electronic devices used to be.  I watched them slowly improve throughout my life.  I wonder how many computers from the 70's and 80's, or even earlier, it would take to run this website.  How long would it take for a single page to load?

Everything you just said after the first sentence is gibberish and completely irrelevant, and unless you have dementia or something, you know it full well...so, you're just trolling at this point.

Even if you multiplied Moore's Law by a hundred it would not help your argument.

DiogenesDue
s23bog wrote:

Do you have some sort of issue with understanding how exponential growth works?  Multiply by 100??  Where di you pull that from?

 

I'll venture a guess that you have it tickled, and it starts with B.

Keep retreating from actual arguments.  It's your only avenue for saving any face here. 

vickalan
btickler wrote:

...You guys just don't seem to have any grasp of really big numbers...

 

Math is capable of handling big numbers. When checkers was studied, it turned out to be a draw and the entire game tree was explored to arrive at this conclusion.

Chess has not been proven to be a draw. The chance of finding a forced mate is related to the ratio of the number of forced mates to the number of games. This is within the bounds of math and programming. There's big numbers being thrown around all over this thread, but the ratio (forced mates/total games) may be a tractable and solvable problem.happy.png

Omega60

When I was young... ok that was a long time ago - there were lots of books written that had the idea "Will a computer EVER be able to beat a Master Chess player?"  That is Master, not even Grand Master.  And now the best computers are substantially better than all people.  Took around 40 years or so.

 

Based on that, I predict that chess will be solved in  another 40 or 50 years.  It will change chess a bit, but only around the edges.  The fact that computers play so strongly means we have a tool to learn chess that is very powerful - use a computer to analyze our games, or any position that is not understood.  So when I read my opening book, and it ends on move 16 and says "Black is better" ... I can use a computer to figure out exactly WHY black is better - well better yet to tell me how as black I would make this position turn out well for me.  This could not be done 40 years ago.

 

When chess is solved, the set of popular openings will change dramatically, and then chess will get back to its roots.  The more things change (like chess computers getting stronger than the best Grand Masters, or computers solving chess), the more they stay the same.

sea_of_trees

Comps have solved some endgames but the one to solve chess is still lightyears away from us, galaxies away. Maybe in two centuries we'll get a dim little statiky signal from the heap of metal and wires that will supposedly solve chess.

And then turns out there's no solution. Always a draw with best play by both sides.

Nathanhof
Omega60 wrote:

When I was young... ok that was a long time ago - there were lots of books written that had the idea "Will a computer EVER be able to beat a Master Chess player?"  That is Master, not even Grand Master.  And now the best computers are substantially better than all people.  Took around 40 years or so.

 

Based on that, I predict that chess will be solved in  another 40 or 50 years.  It will change chess a bit, but only around the edges.  The fact that computers play so strongly means we have a tool to learn chess that is very powerful - use a computer to analyze our games, or any position that is not understood.  So when I read my opening book, and it ends on move 16 and says "Black is better" ... I can use a computer to figure out exactly WHY black is better - well better yet to tell me how as black I would make this position turn out well for me.  This could not be done 40 years ago.

 

When chess is solved, the set of popular openings will change dramatically, and then chess will get back to its roots.  The more things change (like chess computers getting stronger than the best Grand Masters, or computers solving chess), the more they stay the same.

Any argument that goes "This was hard, but we did it, this is hard, we'll do it" is a bad argument.

Here's a neat exercise for you:
- look up how big the problem approximately is (google is your friend)
- look up how many calculations the best computers can do a sec
- extrapolate ^ that number with Moore's law (you can assume the exponential growth continues, which it won't, but hey you know what? Say it only takes half that time to double wink.png )
- see how long it would take before we have a computer that could solve it in a million years

It's all pretty basic math, but the numbers get really intense. I think it'll be a fun experience happy.png.

camter

Big numbers are just that. They are numbers. And they are big, and bigger is generally harder, but in essence they are the same as small nimbers. This means juggling or losing your place, sure.

And the computers can only be so big, whereas numbers can be as big as you like, and with very little wastage of ink.

Just write out nested powers, like 2^(10^(10^(10^(10^(^10))))).

That is a big(!) number, and hard, but not intrinsically, possible to manage.

Why?

Because it is stiil a long way short of infinity.

Aleph Null is another thing altogether!

Nathanhof
camter wrote:

Big numbers are just that. They are numbers. And they are big, and bigger is generally harder, but in essence they are the same as small nimbers. This means juggling or losing your place, sure.

And the computers can only be so big, whereas numbers can be as big as you like, and with very little wastage of ink.

Just write out nested powers, like 2^(10^(10^(10^(10^(^10))))).

That is a big(!) number, and hard, but not intrinsically, possible to manage.

Why?

Because it is stiil a long way short of infinity.

Aleph Null is another thing altogether!

In a mathematical sense you're right. In a computational sense, not so much.

Elroch

When people claim that solving chess would change human chess, bear in mind that the problem of how to beat humans at chess has been essentially solved. A top engine on powerful hardware would get near 100% results against any human (and exactly 100% against almost all).

So does this affect your play?

camter is correct in a mathematical sense that all finite numbers are small compared to infinite numbers. But a finitely complex problem can be unsolvable in a trillion years, which makes it for practical purposes just as bad as an infinite problem if it's the solution in which you are interested.

silvian600

computers dont play chess. they make computations. all that matters is the way the computations are interpreted by the default  human pattern of thinking. so no, computers will never solve or even play chess because computers are not "aware" of the purpose of the computations or their meaning and the way are used. but yes, humans can build and mantain such a system that could calculate the entire posibilities in a game play development. but will never play anything so there is no notion of winning something.

 

Elroch

grin.png

silvian600

humans detroying the world... if you mean "human  world"  as such civilization, society, individual habits etc. be advised we are doing this with every breath of existence. even far, from the time the first observer realized intense heat will result fire. didn't he rulled the world? didn't he turn upside down every life he encounter after that? we are destroying "the world" and build on it s remains again and again. only in our time we can build computers to simulate decisions before acting. the same as the game of chess simulated with n possibilities and  choosing the best. and we call it geopolitics.

if you mean the destruction of "THE WORLD", .. . dont underestimate "THE WORLD". that will never be possible. however we can, and are doing it constantly  the destruction of A world.

silvian600

seeing where this is heading I say let's not. anyway already kind of off-topic.and might not be the place for it. have a nice day.