Will computers ever solve chess?

That's in your mind. Young kids learn to never lose tic-tac-toe, and they do it without storing all 27,000 games on their smart phones.

btickler, your tone is unreasonable.  vickalan's overall comments on this subject suggest a familiarity with phd-level math papers.  he does not fail to understand the high school concept of order of magnitude.  your missing that point is suggestive that you understand less than i'd otherwise give you credit for.

you did not answer his point 30-40 pages back.  you have repeatedly said things that don't actually answer his point and probably aren't even true.  and you also keep throwing around numbers like "billions" and percentages like 99.99% as if the were large when they are actually small for the purposes here.  maybe you know that and you are just being imprecise, but it doesn't help your position when you are calling people "Sherlock" and telling them to figure out easy concepts like orders of magnitude.

chess is protected, to the extent that it is, by the fact that even with vickilan's points being granted, there still is no chance of a solution short of a breakthrough of a size which is entirely unforeseeable from the current technical situation.

it also would help to start with if you'd agree on some definitions, since i am almost sure that vickalan is defining solved as a demonstration that the opening position is won by force for either side, or else drawn by force, where you seem to want what amounts to a 32-man tablebase--and those tasks are not even close to being equally difficult.

That is true, but you need to understand between having a method that happens to succeed and being about to prove something.

In the case of Tic-Tac-Toe a proof that a draw can be achieved by one side involves dealing with every possible position an opponent can reach against an effective strategy, Suppose we are the second player. Then the first player has 3 possible moves. Our strategy is to play in the centre. Then you look at each of the 3 possible positions the opponent can move on the second move and have some way of dealing with these and so on.

The total number of positions you need to deal with is in the hundreds at most (many lines are cut short because if the opponent blunders, you win immediately, or in 2 moves).

The strategy is probably not so complex to describe:

1. play a win if there is one on the board
2. prevent an immediate opponent win if one is threatened
3. create a double threat of win if you can (opponent blocks one, you win with the other)
4. prevent a double threat of win if there is one threatened (this means threatening a win that does not force the winning move, I think)
5. I suspect the strategy is arbitrary from there

A player can fairly easily arrive at the above strategy (except the arbitrary bit) by seeing the consequences of examples and generalising from them. But this does not mean he has proven the game is a draw. It might be that you had a strategy which had worked for all examples you had seen and someone played something new that found a hole in it. If you had played a strategy against all possibilities, you would have proved the result (this would be a couple of hundred carefully varied games).

Note here the comparison made above - a tablebase of tens of thousands of positions versus a complete strategy of mere hundreds of distinct examples.

So can I just clarify ... Vickalan has said you do not need to store all the positions to have a proof, and you are agreeing with him (albeit you provided a more detailed explanation of how that would work in a simpler game)?

I feel as though I am being repetitive and possibly I am the one missing the point (though I don't think I am missing the point).

For a weak solution (opening position only), a vast amount (approximately equivalent to dividing the total space by a one followed by 22 zeros) of positions can be discounted.  The game still can't be weakly solved by any technology that doesn't include a future miraculous discovery.

For a strong solution (all legally reachable positions) requires a lot more than that, though still not "all positions" since some positions will fall in sets that can be solved algorithmically along the lines you've mentioned.  K&Q vs K is a good example of one of these, and it has nothing to do with the idea that there happens to already be a tablebase, because it would be solvable algorithmically even without the tablebase--it serves only as an example of any position so overwhelming that an algorithmic solution can be demonstrated.  But if the weak solution is not possible with foreseeable technology, then this solution is certainly not possible, since it is many (perhaps up to 20-ish) orders of magnitude harder.

Yes, at least for the weak solution, and I think this is exactly why it is said that only the square root of the potential tree size needs to be considered.  Because only the weak side is "pumping" the exponent, and the strong side is choosing just one move.  This is why i said, for the weak solution, you can divide the whole order-of 10^45 gamespace by order-of 10^22.  And it still can't be done.

But I think you DO have to store almost all positions if you are going for a strong solution (all legally reachable positions), not because you need them to prove a previous result, but because each one is its own result.  NOTE:  It has been previously argued that you don't have to store them, since you can just calculate them as needed, and that is probably true, but not easier.  Also, I have previously conceded that some amount of positions probably don't need to be accounted for if they can be solved algorithmically, but it will be a much smaller number (many, many zeroes) than what could be ignored in the weak solution.

s23bog What does this mean?

No first move has been thoroughly searched for the win.

Does not this assume there is a win?

Do you not know that tens of thousands of humans have searched for a win from the opening position and have found none?

I think it means what it seems to mean.  In fact, "no first move has been thoroughly searched for the win."

But this is because, as has been alluded to for quite a lot of pages, we don't have the capacity to conduct that search, even with all the computers on earth, or foreseeable to be on earth.  So it will remain the case.

Declaring a strategy of "solve for one first move" is approximately equal to declaring a strategy of "solve for all first moves" because solving for all is only 20 times harder (and less than that, due to transpositions), and we aren't off by a factor of 20, but by a factor of 10^20 (ish) (and that is just for the weak solution).

Yes, you can start by searching for a forced White win.  How to go about this is actually known by the math PhDs whose whole life is to study such things (complexity theory).  You don't have to come up with a process--they have one.

The trouble with proposing, basically, to just start doing it with one move first, is there isn't enough processing power to do it.  And for basic physical reasons, there likely won't be enough processing power at any point in the future.

For example, the speed of light across the width of a chip is a limit to what is possible in the future.  The size of transistors on a chip as a function of the size of individual atoms is a limit to what is possible in the future.  Quantum tunneling of electrons, such that they don't flow predictably, is a limit to what is possible in the future.  These limits are what will bring an end to Moore's Law, in only three or four more generations of chip (when or before chips are at 3nm scale).

After that you have to rely on some magical  future development which, who knows, may happen, but there is no reason to count on it.

ok, here's a prediction. Within 10-20 years, quantum computers will be powerful enough to solve chess, if anyone wants to waste the world's most powerful computing resource on an arbitrary, unimportant problem to which we are rather sure we know the answer already.

As other posts indicate, you can reduce the complexity by about a power of 1/2, by only dealing thoroughly with opponent moves. This is basically what was done with checkers.

The actual problem of "solving chess" is far, far simpler than what it's made out to be here.

To start, a hypothesis needs to be accepted. Once it is the solution is simplistic. The hypothesis states human intuition/research/experience has established specific evaluations to be factual.

A basic example: After the move 1. d4 we KNOW that the move 1. ...h5 can be discounted from analysis, as better moves are available. 400 years of human testing has shown this. There is no need to waste computer analysis. All you naysayers are incorrect. There is no point in analyzing inferior moves when better moves are known.

To proceed.

Only 2 1st moves need a complete analysis. 1. d4 1. e4. If these 1st moves do not lead to a forced win, there is no need to proceed any further. We do not need a computer to tell us 1. h3 or any other such move could lead to a win.  1. c4 1. f4 1. Nf3 are alternatives, but we are intelligent enough to know they can NOT be "better" moves.

Hence, the "tree" is really much narrower. A computer will "solve" the game to be a draw in the distant future.

OK, I think we are agreed on that.  You concede this is for "weak" solution only?  "Strong" solution requires more?  I believe this is the case but I am not 100% sure.

It's not an algorithm, but it is a process.  Although that kinda suggests there must be an algorithm.  I can't share it too well, because it is over my head to do so.

But there are quite a few papers available online (Shannon, Shaeffer, etc.).  And then there is more than that too (such as the whole Handbook of Game Complexity Theory which appears to have four volumes!?).

But as far as improving the process, sure that would be great.  Not an easy trick though.  These are smart guys and they spent their whole life working it, after all.  You'd be a famous mathematician if you did that.  And the improvement would have to be very, very big too.

http://partiallyexaminedlife.com/2017/07/18/how-could-scalar-consequentialism-ever-lose-at-chess/

Humans are doing the programming ! What ? you think someday "HAL" will evolve and do it himself ??? HaHa. Of course humans will have to be involved. A program is only what is written until AI takes over, then God help us if comps develop self awareness.

1. Nf3 can not be considered a superior move to either 1. d4 or 1. e4. Simply it is at best  equal. It Blocks an advancement of the f4 pawn which may be required to control space. If d4 and e4 can be demonstrated not to lead to a forced win, then Nf3 logically can not lead to a forced win and need not be analyzed. This is chess 101.

Similarly 1. f4 need not be analyzed as it allows a potential weakness on the dark squares leading to the King. If d4 and e4 can be demonstrated as not leading to a forced win, then it's really very simple. The search can end there. This hullabaloo about every possible position needs to be analyzed is nonsense.

Exactly. The entire point. How to tell the computer. I have said all along, the problem lies in telling the program how to make the best and accurate evaluation of a position. Brute force analyzing all possibilities is fruitless if it can't accurately make an evaluation.

First, Vickylan has been skimming some Googled papers.  I've skimmed them, too, years ago when this thread started, in fact.  

You clearly need to read the thread.  The definition of "solved" in the context of chess is not something we're deciding here...it's already been defined.  As for the numbers, they are continuations of numbers I already went into in more depth 30-50 pages ago.  Vickylan knows (or he should) exactly where those numbers are coming from.  I'm not going to re-hash for you.

As for your last statement...ummm, you do realize that a 32 piece tablebase would make the remainder of this problem trivial, I hope?  You also realize that completing a 32 piece tablebase requires largely the same resources as solving?

What is your computer background, exactly?  This is a systems problem.

Vickalan may have only skimmed some papers or he may have done a bit more, but he clearly doesn't need to be told about orders of magnitude, nor called Sherlock, which is what you did.  It's rude and dismissive.

I have been following this thread for years and I have read most of it.

There are at least three generally accepted definitions of "solved" which you know (or should know) and I'm asking you which one you are using, though I think it's fairly clear, and it's fairly clear Vickalan is using a different one.  Specifically, he is satisfied if the opening position is solved, and you want all positions solved.  At least that fits your argument.  If you accept solving only the opening position as "solved" then your numbers are too big.

Yes, I do know that a 32 man tablebase requires largely the same resources as solving (I'd have said exactly the same), which is why I mentioned it.  You and Vickalan seem to be talking about two different standards--weakly solved and strongly solved.

My background in CS is I have a degree in it.