Chess will never be solved, here's why

#2648

"Define in a game-theoretic sense, without ambiguity, "compensation" so that everyone agree." ++ Defining anything so that everyone agrees is near impossible here.
Some people here even disagree with the definition of weakly solved.

"The structure of a proof tree derive from the definition of weak solution."
++ A proof tree is not the only way to solve a game. There are other ways of determining a strategy of achieving the game theoretic value of a game than a proof tree.
For example the game of Nim has been solved without a proof tree
https://en.wikipedia.org/wiki/Nim

So other ways than a proof tree are admissible instead of or complementing the proof tree.

"As said many times a "strategy" is a proof tree and "any opposition" means against any possible move by the opponent (not only the best ones), so in a game theoretic sense you cannot skip 1. e4 e5 2. Ba6."
++ I disagree. "A strategy" can be other than a proof tree. "Any opposition" can be relaxed. "Opposition" is not "any possible move", it is at least a move that tries to oppose. 1 e4 e5 2 Ba6 is no opposition: it does not try to oppose to the draw, it voluntarily loses.

If all possible moves have to be tested and for both sides, then the weak solution becomes the same as the strong solution. A strong solution of chess is not feasible with present technology. Even the simpler games Checkers and Losing Chess have not been strongly solved.

Yes, you are one of them.

And who says that, but you?

If you say so, I say that the opponent just tries every possibility without prejudice. Can you find in papers (about chess possibly) your meaning of "any opposition"?

No, we have already explained that, but in practice it might be not too different. In fact, in checkers 10¹⁴ of 10²⁰ positions have been searched.

You can always represent the game as a tree, in Nim too. Nodes are states (positions, in chess) and the edges are actions (moves, in chess). These actions produce a transition from one state to another. We use trees in chess because it is the standard. Of course, you could prove with a theorem that an algorithm to play a game is a solution for that game, but that usually happens when the search space is limited. In chess whe don't even know which are all those "sensible" position you talk about, so we cannot determine an optimal strategy a priori, we have to search; that's why an optimal strategy appears after the proof tree. An optimal strategy is a proof for a weak solution, if it works against any possible opponent's reply. Why? Because you cannot prove a theorem saying: "ok, I skip those cases because we know by experience that they are more favourable for a solution". Game theory is a branch of mathematics: no one would accept a "solution" like that, you see?

Issue:  Is there any way to use the mathematics of Statistics while talking about 'Solve' chess ?  And the mathematics of probability ?
Encountered a nice term earlier -  'cross entropy'.

I remember some terms from statistics:
Root-mean-square
Standard Deviation
Chi-squared
Boltzmann's correlation constant 
Average-median-mode ...  the differences between them
Bell curve

The one that stood out the most at the time - was 'Standard Deviation'
and concepts like - 'how many SD's away was that?'  

Can that stuff be used to 'solve chess' ?  Or 'weakly-solve' chess?Inclination:  No. 
Or ... not in a central or critical way or for premise-purposes.
Chess isn't like that. 
Positions are too particular -
and winning-won positions are too well-defined.

Could statistical and probability math be used 'peripherally' in some way in 'solving' projects.  Yes !   
Example:  people look up statistics like ratios and percentages arising from the tablebases ...

But that's statistics used as a Result:   Not a Method !!

Agree. Heuristics (including rules of thumb and positional principles), that we use as a strategy to play chess are indeed based on statistics. We (or a neural network) know by experience that they have good chances to work, but they do not work always, in fact even A0 has to calculate many variations to reach its maximum strength. That's why it's impossible to think about a solution for chess without a deep and broad search. We could only hope that an evaluation function, exploring the most promising(?) lines first, would speed up the search toward the tablebase, but we would know how good it is only after the search. There can be everywhere outliers, "monsters", "black swans" or however we want to name them, that can subvert the expected outcome based on statistics.

"how good it is only after the search."
Yes.  'after'.
And I'll venture - and what 'it' is good for  

I solved chess last week

You deliberately ignore essential parts in mine and @MARattigan posts. Even if that time was shortened to 1 s/move, it would be still far from covering 10¹⁷ nodes in 5 years.

No. You used this

error = a / timeᵇ

which is very different. However, an exponential decay would be even better for your purpose, as @MARattigan said before.

Denial and repetition with no real explanation. To prove that the error rate is low you used this (too much repeated imho) formula:

D = E + E³ + E⁵ + ...

from which E ≈ D and thus low. But those E, E³, etc. have that form because you supposed statistically independent errors (see here). If they are not almost independent, the above formula cannot be used. So statistical independence ⇒ low error rate ⇒ statistical independence... is circular. You should prove that errors are statistically independent, without using the error rate, which you deduce low by assuming statistically independent errors.

Was that a week solution?

Interesting example of using uncertain reasoning to get reliable results without genuine certainty. It is very quick to check the pseudoprimality of a numbers, which is to check a set of properties that would be true if the number was a prime, but which can be individually true for some other numbers - "pseudoprimes" - as well. The confidence in the primality can be enough to use these numbers for some purposes where you need a large prime number (on the grounds that it is very unlikely not to be one). 

Probable primes

@Elroch
You've reminded me of another term from my memories of 50 years ago.
Fifty Years ago !  That's right. Before the internet even existed at all.
Normal Distribution.  Yes.  I remember that one.  
But now you've mentioned one I can't recall.
Pseudoprimality.
and: from @Elroch 's quote of me and his response.

The one that stood out the most at the time - was 'Standard Deviation'
and concepts like - 'how many SD's away was that?'  

This is usually in the context of assuming a distribution is roughly normal, and then using the statistics of the normal distribution to say how often n SDs would be exceeded.

A lot of natural statistics are roughly normal. One reason is the Central Limit Theorem, which says for any probability distribution with finite variance, the mean of the sum of a sufficiently large number of independent identically distributed random variables is very close to a normal distribution. 

Can that stuff be used to 'solve chess' ?  Or 'weakly-solve' chess?Inclination:  No. 

I agree. It's all terribly useful for doing empirical science, which is what @tygxc is doing without realising it is not "solving".

Progress.
Getting somewhere.
Principles of science and mathematics now very much on display.
And being affirmed.
Development - where statistics and its related math 'comes in' and where it does not.
'terribly useful for doing empirical science"
where 'terribly' is being used in a positive way.

Means Intensely Useful if I have Elroch's reply correct.
And I'm confident I do!
But also in addition:  "Empirical science" "is not solving".   Yes.
And for the benefit and convenience of readers:

Note the connection of empiricism with quackery ...
But like so many realities - its Paradoxical ...
Science starts with observations.  Has to. 
No incoming data at all ever - no science !
But then - it proceeds beyond that - where it can.
If it was all just 'empirical' - would mathematics even exist at all ?
How ?  
Good News: its not all 'empirical'.
Bad News for some but not others: 
Empiricism by itself isn't the be-all and the end-all.
Trying to think of a good analogy.
The tail doesn't wag the dog.   
Yes - that one could be improved on for this context.

#2652
"Is there any way to use the mathematics of Statistics while talking about 'Solve' chess ?"
Yes: I used statistics to prove that:
99% of ICCF draws are ideal games with optimal moves,
the 50-moves rule is never involved with 8 men or more,
at 60 h/move the exact move is within the top 4 engine moves in all but 1 position per 10^20.

#2651
"There are ways of weakly solving games other than explicitly listing a proof tree, but a weak solution of chess must generate a proof tree. You've said nothing to date about how you would use your supercomputers to produce an algorithm that isn't an explicit listing of moves. 
How would you go about that?"
++ As explained before I would use the cloud engines of 10^9 nodes/s starting from humanly prepared 26-men tabiya to calculate towards the 7-men endgame table base or an earlier 3-fold repetition. Then I would verify that all moves are optimal by peeling back and replacing the white moves by the top 2, then top 3, then top 4 moves.

Science:

1. Observe
2. Generate model consistent with all known observations
3. Observe
4. Test model with new observations
5. If model is falsified go to 2
6. Otherwise go to 3

#2650

"Some people here even disagree with the definition of weakly solved.
Yes, you are one of them."
++ Sorry, no, I abide by the generally accepted definition of van den Herik.

"tygxc wrote:"Any opposition" can be relaxed.
And who says that, but you?"
++ Any opposition is not any moves. We can use heuristics to prune what moves are opposition and what are not. Losing Chess also used heuristics.

"I say that the opponent just tries every possibility without prejudice."
++ Losing Chess was also solved with 'best first'. Likewise weakly solving chess should start with 1 e4 and 1 d4.

"If all possible moves have to be tested and for both sides, then the weak solution becomes the same as the strong solution.
No, we have already explained that, but in practice it might be not too different."
++ Yes: if you have to check all possible moves for both sides, then you end up with all legal positions and then you are attempting to strongly solve chess, which is not feasible with present technology as both the time and the storage are prohibitive. So I restrict the black moves to the top 1 engine move where the table base indicating the draw retroactively validates them all. Likewise I would restrict the white moves to the top 4, as extrapolation from AlphaZero autoplay shows that makes only 1 error in 10^20.

"In fact, in checkers 10¹⁴ of 10²⁰ positions have been searched."
++ Yes, that is correct. That is also the main point: we do not really know how many legal, sensible, reachable, and relevant positions there are in chess and thus how many nanoseconds weakly solving chess takes on 1 cloud engine of 10^9 nodes/s. I have produced some a priori estimates but we will only know a posteriori after chess is weakly solved.

tygxc wrote:"The structure of a proof tree derive from the definition of weak solution."
"You can always represent the game as a tree, in Nim too."
++ No sometimes it is not feasible, sometimes like for some infinite games it is impossible.

"We use trees in chess because it is the standard."
++ No, we also use heuristics. We know that certain endgames even with >7 men are won/drawn, we do not calculate the tree from there, we know the game-theoretic value of that node. We also know that losing material without compensation yields a game-theoretic value of a loss for such a node. That is why the node 1 e4 e5 2 Ba6 needs no further branching.

"In chess whe don't even know which are all those "sensible" position you talk about"
++ A sensible position is a position that can be reached from the initial position by a proof game with > 50% accuracy.

"we cannot determine an optimal strategy a priori"
++ Yes, we have a priori knowledge about the game.
A pawn can move to 1-2 squares and capture to 1 or 2 squares, a knight can move or capture to 2-8 squares, a bishop can move or capture to 7-13 squares, a rook can move or capture to 14 squares, a queen can move or capture to 21-27 squares, a king can move or capture to 3-8 squares. From that follows that the 4 central squares e4-d4-e5-d5 are more important than the other squares. From that follows a priori that 1 a4 is inferior to 1 e4, 1 d4, 1 c4, 1 Nf3 and hence needs no consideration.
We know a priori that 1 pawn is enough to win some endgames. We thus know a priori that losing material witout compensation is inferior. That is why we know a priori that 1 e4 e5 2 Ba6 needs no consideration.

"an optimal strategy appears after the proof tree"
++ The optimal strategy can also be used to grow the proof tree with pruning, like a gardener grows a tree by pruning. He also uses a priori knowledge and heuristics like 'prune crossing twigs'. 'Hang no pieces, hang no pawns without good reason to do so.' is a valuable heuristic.

"An optimal strategy is a proof for a weak solution, if it works against any possible opponent's reply." ++ Not all replies are opposition, some replies like 1 e4 e5 2 Ba6 do not oppose.

"Because you cannot prove a theorem saying: "ok, I skip those cases because we know by experience that they are more favourable for a solution".
++ Yes, that is done in many mathematics proofs, where the proof declares such uninteresting cases 'trivial' meaning it can be done by the same method.

"Game theory is a branch of mathematics: no one would accept a "solution" like that"
++ There are many mathematical proofs where 'trivial' cases are omitted.

#2657
"You should prove that errors are statistically independent, without using the error rate, which you deduce low by assuming statistically independent errors."
++ No, that is not necessary, as often used in other sciences.
Example:
To what speed v accelerates a voltage V an electron with charge e and mass m in vacuum?
Solution: assume v << c velocity of light, so classical mechanics can be used
mv²/2 = eV.
v = sqrt (2Ve/m)
Now check: If v << c, then the calculation is valid, else turn to relativistic mechanics. 

"No. You used this

error = a / timeᵇ

which is very different. However, an exponential decay would be even better for your purpose, as @MARattigan said before."

++ No, mine is correct. It is linear on log-log scales:
log (error) = log(a) - b * log (time)
Anyway, there is no need to split hairs over simple math.
60 times more time yields 5.6 times less decisive games and thus 5.6 times less error/game

@Elroch
you posted:
Mathematics exists outside of science. It is 100% independent of the properties of the physical Universe,
Agreed.  That's why I said - "if it was all about 'empiricism' then would mathematics exist at all?"
But it isn't.  It isn't 'all about' empiricism.
In that case - I deliberately set up an invalid premise ...
but not as a strawman to attack that idea -
but to make a rhetorical question.
To illustrate the actual reality.
The universe couldn't be all about empiricism anyway - unless one chose to perceive it that way.
Happens - yes.  That's often where 'solipsism' appears.

And - we just got also ... from @tygxc
"Is there any way to use the mathematics of Statistics while talking about 'Solve' chess ?"
(he quoted my text) and then replied with
"Yes: I used statistics to prove that ..."

Even just the assertion 'used statistics to prove' looks suspect just by itself - but then its followed by claims ...
Trying to totally bypass exposure of the invalidity of 'empiricism for 'solving' purposes'.
@tygxc  possibly will keep bypassing the term 'empiricism'.
Not realizing what it is and how its invalid in various applications.

#2668

"Losing chess is a win for white so only the one strategy is needed, and this strategy is always heading closer to a win rather than maintaining a draw."
++ Yes, That is right. It is also one reason why solving Losing Chess is easier (less nodes) than solving the simpler game of Checkers, which is a draw. A win is easier to prove than a draw.

"Unless chess is a forced win for white (most believe not)"
++ Yes, general consensus is that the game theoretic value of chess is a draw.
Expert opinions, GM games, ICCF results, AlphaZero autoplay, TCEC all point in that direction.
That is one reason why Chess (a draw) is more complicated than Losing Chess (a win).
The other reason is that both Checkers and Losing Chess have compulsory captures, while Chess has discretionary captures.

"your strategy for black needs to provide a strategic response to 20 first moves by white."
++ I disagree. If I can achieve a draw against 4 of these: 1 e4 1 d4 1 c4 1 Nf3 then the 16 other are trivial. They can be done by the same means as the top 4 if required, it just burns resources for something that is undisputed a priori. I use a priori knowledge about the game i.e. the importance of the center to follow a best first approach and to trunctate the effort after the top 4 is done. There is genuine interest in "How to draw against 1 e4 and 1 d4?".
There is no interest at all in "How to draw against 1 a4?"