Will computers ever solve chess?

Just go back and check what you wrote. Your premise is based on naive algorithms to examine the entire game-tree of chess, which is what mathematicians often refer to as a "brute-force" analysis. It is known with certainty that this is not the only analytical method to study games.

When the discussion turned to the weakness of brute-force analysis, you argued (page 109, #2173) about the term although it's the same term used by Shannon (who wrote a famous paper on this topic in the year 1949).

Since this you haven't made any attempt to support your point with logic or math. On page 110 (post #2195) you tried to use a football analogy, "...Cowboys are going to beat the 49ers". Analogies aren't a basis for producing mathematical conclusions. If you ever decide to show your work using normal mathematical conventions I would still be interested in seeing it.

If you had found my analysis about brute force, you'd have posted it...unless you just realized it would make you look worse to post an analysis so much better than your blatherings.  As we've already established, you feel that you can solve chess without traversing the tree (even though you then always hedge your bets by claiming the whole tree doesn't have to be traversed if we get lucky and hit a forced win tomorrow...can't have it both ways).  But a "proof" without traversing the tree can't be backed up, and even if it could, there's zero evidence that a proof using a foundation of principles built on top of each other can be accomplished...we have not even started down this road with any success...ergo, "not in any foreseeable future".

Apparently, you just looked at a few pages (since you only drew from 2 consecutive pages)...which is the kind of half-assed garbage I've come to expect out of you.  You could't even find anything that works in the context of your point.  Your "Cowboys/49ers" point is pure BS, and you know it.  It's not even attempting to produce a mathematical conclusion.  It is simply calling you out on the pseudo logic you attempt to pass off as real arguments and specious arguments you make that don't up under the slightest scrutiny.

Oh no, LawAndOrderKing just can't let go.  I see this new sockpuppet is 2 days old.  Enjoy the next couple weeks before you disappear again.  Do you provide any value at all, or is the best you can ever do to snipe with oneliners from the sidelines and then run away like a little...?

Vickalan's analysis:

As for solving chess, there is some reason to believe it can happen within a decade or two. Here's a brief analysis:
Checkers has a game tree complexity of 10^31, and was solved in 2007. It was a draw, so every game had to be studied (make sure there was no way for white or black to win).

Chess is more complicated. The game tree complexity is 10^123. So chess is more complicated by a factor of about 10^92. (doesn't sound good so far).

Now, some factors that might simplify the calculation for chess:

1) If we can find a forced mate, not all positions need to be investigated.
2) If there is a forced mate, it would make sense to look for it by studying only well-played games (ignore games where one side purposely makes bad moves, like losing pieces for no reason).
3) Chess opening theory has already been highly studied.
4) All chess endgames with 7 pieces and less have already been solved.

Now to calculate how much each of these simplifies the calculation (note: one ply = 1/2 a move, such as a move by white)

Instead of a 10^123 game tree complexity, by checking only games with normal play (halting any calculation where one side makes a stupid move) the game tree complexity is reduced to 10^40. (1) (see Wikipedia "Shannon number/Sensible games"). Now our problem is only 10^9 times (1,000,000,000) as complicated as checkers (2).

Now use existing chess theory to ignore all bad chess openings (3). Let's say we use opening theory for the first 3 plies. (3 plies x 20 choices = 20^3 = about 10,000). 1,000,000,000/10,000 = 100,000. Our problem is now about 100,000 times as complicated as checkers.

Now use an existing chess tablebase to play the final 6 plies of the game (6 plies x 5 move choices = 5^6 = about 10,000). 100,000/10,000 = 10. Our problem is now about 10 times as complicated as checkers (4).

Checkers took 18 years to solve using 200 computers at the peak of the calculation. Our calculation is 10x as difficult, so it will take 180 years to solve chess (5). How to do better: Use 10 times as many computers. So chess might be able to be solved in 18 years (6). 

Now we're still at a disadvantage compared to checkers, because calculations may proceed more slowly. Each move needs to be checked if it was "stupid" or not (like losing a queen with no compensation). If stupid, stop the work and go to the next game.

On the other hand, we have one big advantage, If we find a forced mate, we're done. The rest of the game tree can be ignored.

So, with distributed computing, using about 2000 computers, and the assumptions above, we have a problem that can conceivably be solved in 15-20 years.

Considerations for the logic and math impaired:

(1) From the exact Wikipedia article Vickalan linked as his support, the correct number is 10^46.7, so saying 10^40 is making the problem more than a million times smaller than it actually is.

(2) Ummm, no, now you are comparing the 10^31 full tree of checkers to your own bogus chess 10^40 positions number instead of the 10^120 number...saying saying you are now within 10^9 is completely wrong.  The number they actually traversed for Checkers was 10^14, which is over 10^32 away from number of Chess positions.  You are over 30 orders of magnitude off.  It's a little much .

(3) Ummm, no, because your "bad openings" eliminations overlap the set of your "bad positions" (bogus) number already given.  You are double counting "bad" positions here.

(4) Ummm, no, now you are double counting on the other end of the game...

(5) False by a factor of, at best even allowing for your double countings, more than a million times.

(6) Even this is not technically true.  There is overhead for "distributed computing".  

Here is proof that it might be possible to solve chess without examining the entire game tree:

Your tree has been debunked many times, and not just by me.  Replace that "this section of game tree doesn't matter" with "this section of Vickalan's brain doesn't work" and it would be more accurate.  Maybe you should draw the tree as it really exists ...probably far wider than our entire galaxy at the scale you are drawing it here even without getting anyway near the bottom of the tree.  We'll wait patiently.

What I wrote in response to Vickalan's assertions about the world's fastest supercomputer at 100 PetaFLOPS:

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).

Which I expanded upon later:

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.

No.  Value.  You're wasting oxygen.

P.S. Vickalan will never notice your affections, save yourself the anguish.

The diagram isn't to represent the width of the game tree - it shows that it might be possible to solve chess without examining the entire tree. Therefore, any conclusion (such as yours) that chess cannot be solved because the game tree is too large is based on a faulty assumption.

To solve chess, you have to go through every line, leaving one line undone means its not actually solved. 

He agreed with me, you're not very observant.

It's disingenuous to show the "not needed" part of the game tree to be visually within the same basic size range, as if you can flip a coin and if it lands heads, Chess is solved, if tails, it's not.  The more correct representation would make it clear that the "solved by pure luck" part of your tree is one in a billion billion billion shot...something that makes winning the Powerball lottery look incredibly easy by comparison.

But you already know this.  Disingenuous is your middle name .

That's one definition, but not commonly used by mathematicians. Solving chess generally means knowing which side wins if the game is played perfectly. Also to be answered is learning the strategy to play a perfect game. Games which have inaccuracies, blunders, senseless or silly play are usually considered less interesting to mathematicians.

Checkers is solved, but nobody made a catalog of every possible game.

Sudoku was also interesting to mathematicians when it was studied as to the fewest clues possible. Once this was answered, the mathematical interest in Sudoku went down.

The diagram does not represent the size of the game tree. What it shows is that it might be possible to solve chess without examining the entire tree.

As for the ratio of forced wins to total games, no mathematician has determined it yet. If your analysis makes the assumption that the entire tree needs to be examined to solve chess, then your analysis is wrong. There is no guesswork here.

Btw, you adding insults to your text is interesting. It lets me know that you've run out of meaningful things to say, a sure sign by you that your argument is lost.

Let me know when you graduate elementary school...

More of the same.  You say You know full well that if the solution to Chess is that it is a draw (the most likely outcome) that all the positions will have to be traversed...how do I know?  Because you said it on page 56:

"On the other hand, if best play is a draw, chess won't be solved until the entire tree is checked."

So you hide behind your technicality, again.  The chances of finding a forced win that cuts the tree size significantly enough to occur in our lifetimes are not much different than the original problem.

As for insults, it merely means I'm tired of your asshattery.  Willful ignorance, misuse of terms, false equivalencies, misrepresenting numbers...all of it.  Your ridiculous idea about there being some gigantic ratio of forced wins out there somewhere has already been found wanting, and again, by more than just me.

It's too bad the Elroch's of this thread are too polite to tell you directly when you are full of crap.

The fact that you see common sense in Vickalan's posts is pretty damning, for him.  Shouldn't you be taking calls or something?

That's not hiding. It's explaining the answer. And the insults are the normal thing you do - when you become unable to refute an answer with math, you call people names like a little crybaby.

It's probably just me, but your answers seem more rational and polite. His answers, or outbursts, are more difficult for me to understand because they often include things that are way off topic, like insulting people.

Yes, if he ever placed any interesting mathematical analysis on this thread, it's buried in his usually rude commentary.

If anyone is interested in this same topic discussed politely between programmers and mathematicians, this same question was asked at the StackExchange:

https://cs.stackexchange.com/questions/79272/is-there-an-algorithm-that-can-solve-chess-within-the-span-of-a-human-lifetime

They've come to the same conclusion as here - it has not been proven that chess cannot be solved, not even within our lifetime.