Chess will never be solved, here's why

Sort:
Avatar of Optimissed
Elroch wrote:

While "it" obviously does matter (see discussion above), in a way which is not comfortable to my pure mathematicians desire for neatness and simplicity, even for basic chess transposition surely only moderately reduces the exponent (the growth in the number of positions with depth of thorough analysis) for a long way from the opening position.

Part of the reason is the large number of irreversible moves that can occur in an optimal chess game. Recall that the set of legal basic chess positions is split into equivalence classes of positions by the ordering defined by the existence of a legal path of moves between two positions. Every pawn move, every capture and more, kind of "resets the transposition clock" (classes of positions which are "earlier" in the tree of legal paths cannot ever be reached again). So transpositions are localised to the equivalence classes. It's also worth remembering that the number of legal positions is relatively small compared to the number of legal games partly because of transpositions. So, enlighteningly, transpositions are already taken account of to get the number of legal positions in basic chess (~10^43 or whatever). And the version with official rule sets has an enormously greater number of states, however much of a pain I find that to be, making the point virtually moot.

I think we know two things. Maybe three. Firstly that it's a draw via best play for each side. Secondly, it's unsolvable. By that, I mean that if it's a draw it's literally unsolvable in an absolute sense unless an artificial method of restricting the analysis were found. Even a forced win is so far from our ability to detect it that for practical purposes, it doesn't exist.

The third thing is that where a deductive solution is for any reason impossible, mankind has in any case found other methods of "knowing" to be sufficient. You can't prove that gravity exists. All you can demonstrate is that in every case, ever measured, of massive objects potentially exerting an accelerative effect on one-another, that effect has been detected. But since you don't know if anything called "gravity" exists, it tends to be referred to as "the force of gravity", which is a force which acts AS IF it were a force between massive objects due to an hypothetical property, attributed to massive objects and called "gravity". Otherwise, it could be a tendency for their motion to accelerate relatively to one-another, which amounts to the same thing.

Countless other examples exist of things we say we know, without any necessity of a deductive proof, regarding things that cannot be proven deductively. So why should chess be different? People should take care how they think about this .... otherwise, one could be excused for imagining that chess players believe they're a special case. After all, some of their number already imagine they're playing sports or even "being athletic" when, in cold, calm, prosaic, sedentary fact, they're usually sitting at a table motionless, perhaps with their heads in their hands.

Avatar of tygxc

#3637
"Now, if using TT the branching factor is 4, only a depth of 28 plies, i.e. 14 full moves"
++ You only have to explore possibilities for 1 side, not for both. You need 1 strategy for black to draw against all reasonable white moves. There may be several strategies that draw, but after one is found chess is weakly solved.

Avatar of tygxc

#3638
"None of those "counterexamples" produce the same game state under competition rules."
++ Laws of Chess, competition rules:
"9.2.2
Positions are considered the same if and only if the same player has the move,
pieces of the same kind and colour occupy the same squares
and the possible moves of all the pieces of both players are the same."

Avatar of MARattigan
tygxc wrote:

#3638
"None of those "counterexamples" produce the same game state under competition rules."
++ Laws of Chess, competition rules:
"9.2.2
Positions are considered the same if and only if the same player has the move,
pieces of the same kind and colour occupy the same squares
and the possible moves of all the pieces of both players are the same."

I will concede that you can read. Well done!

What's the connection to my post? What's the connection to how you propose to solve competition rules chess?

If you want to use some version of Stockfish, it works with game states, not just those aspects of a position that are considered for the purposes of FIDE article 9.  (And you need to choose your release because there have been corrections to the 3-fold repetetition handling in recent versions.)

Avatar of haiaku
tygxc wrote:

#3637
"Now, if using TT the branching factor is 4, only a depth of 28 plies, i.e. 14 full moves"
++ You only have to explore possibilities for 1 side, not for both. You need 1 strategy for black to draw against all reasonable white moves. There may be several strategies that draw, but after one is found chess is weakly solved.

Then if the engine prunes all Black moves but the first one in the list (as nonsensical this is to me, but forget it for now) there are 4 candidates for White and one black child for each of them. So your formula for the number of positions becomes:

1 + 2w + 2w² + 2w³ + ... + 2wᵈ

where d is the number of full moves now. That means that with 10¹⁷ nodes and w = 4, d = 28, which I'd say is still not enough.

Avatar of playerafar


" enlighteningly, transpositions are already taken account of to get the number of legal positions in basic chess (~10^43 or whatever)"

Which I have mentioned too.
But somebody else trying to pretend that reduces the number of positions when it doesn't.  Transposition moves refers to sequences of moves - it doesn't reduce the number of positions.
But a lot of the posts are about a particular person trying to get away with pushing a pseudoscience that it does.  And other pseudocience and pseudomath.
It seems to be a demonstration that he can get away with that.  Forever.

But idea !
This doesn't mean the discussion is useless.
What it means is that the value in the discussion would be in the discussions of peripheral topics.  

For example - inductive versus deductive reasoning.  Induction versus deduction.  'the guy' getting that all wrong - leads to it being posted about by others accurately instead of his pushing of pseudo-stuff.

There's also the nature of 'not knowing something'.
Came up in the other forum.
Everybody in the world perhaps - has a different reaction to the unknown and a different take on it.
The whole generic subject of reactions to the unknown is a topic in itself.
And related enough to the forum topic.
Suggestion:  when something is unknown - that doesn't mean a position has to be taken.  No arbitration necessary to get rid of the 'unknown'.
Nor any assumptions.
But people often go in those exact directions !

Avatar of haiaku
Optimissed wrote:

Countless other examples exist of things we say we know, without any necessity of a deductive proof, regarding things that cannot be proven deductively. So why should chess be different?

We are actually in the same situation: we use the knowledge gathered in centuries to make the most precise predictions we can, but we do know that this knowledge is not definitive: a new phenomenon may force us to use other, more general models of the "universe" (be it the physical one or a chessboard with its pieces), because the current ones may not hold true anymore in new known conditions. Since we have no idea of how many unknown physical phenomena are out there to be discovered, all the physical "laws" we know are in fact just theories. For chess we have at least an idea of how many positions and possible games there are, and we know for sure how to test any strategy, thus we can start to make estimations on how much time a deductive and exhaustive proof (that leads to certain results) would require. That's the meaning of "solution" in game theory, as opposed to inductive reasoning, which leads only to probable conclusions, as mentioned by @Elroch.

Avatar of playerafar


Acceptance of the unknown.  Often eschewed.  If that's the word.

Avatar of Optimissed

Rejected would do.

Avatar of Optimissed
haiaku wrote:
Optimissed wrote:

Countless other examples exist of things we say we know, without any necessity of a deductive proof, regarding things that cannot be proven deductively. So why should chess be different?

We are actually in the same situation: we use the knowledge gathered in centuries to make the most precise predictions we can, but we do know that this knowledge is not definitive: a new phenomenon may force us to use other, more general models of the "universe" (be it the physical one or a chessboard with its pieces), because the current ones may not hold true anymore in new known conditions. Since we have no idea of how many unknown physical phenomena are out there to be discovered, all the physical "laws" we know are in fact just theories. For chess we have at least an idea of how many positions and possible games there are, and we know for sure how to test any strategy, thus we can start to make estimations on how much time a deductive and exhaustive proof (that leads to certain results) would require. That's the meaning of "solution" in game theory, as opposed to inductive reasoning, which leads only to probable conclusions, as mentioned by @Elroch.

I didn't find your preamble all that relevant .... in fact none of it. Seems to be argument for argument's sake. I'm asserting that anything other than an inductive understanding of a "chess solution" is impossible. I think that's completely incontrovertible.

I said this to you when we first met. I think you should try harder to understand what I'm saying. You must be capable of it on some level.

Avatar of playerafar


Inductive reasoning needs to be distinguished from mathematical induction.
The conflict between the two is enough that the words induction and inductive aren't good for this context.  They would tend to serve themselves rather than the discussion.

Acceptance of the unknown.  Lots of wriggling and bobbing and weaving ...  by so many.  Trying to make the unknown a known.
With so many unknowns always still there at the end.  Undented.

Avatar of Optimissed
playerafar wrote:


Inductive reasoning needs to be distinguished from mathematical induction.
The conflict between the two is enough that the words induction and inductive aren't good for this context.  They would tend to serve themselves rather than the discussion.

Acceptance of the unknown.  Lots of wriggling and bobbing and weaving ...  by so many.  Trying to make the unknown a known.
With so many unknowns always still there at the end.  Undented.

I think I disagree. https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=&cad=rja&uact=8&ved=2ahUKEwiEgbzjjPL4AhVxSkEAHQOGC0wQFnoECB0QAw&url=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FMathematical_induction%23%3A~%3Atext%3DMathematical%2520induction%2520is%2520a%2520mathematical%2C3)%252C%2520...%2520.&usg=AOvVaw26pDBSfPkj6xv-4c2gJb5I
Mathematical induction gives the base case (that the basis of a repetitive sequence is achievable) and then the repetition .... that if a mathematical mechanism is possible, then it can be repeated in similar mathematical conditions.

I believe this is no different from "any old" induction.

Avatar of playerafar


It is different.  And it should be obvious.
If what I read on defining inductive reasoning was correct.
"'I think' I disagree."
Think more.  Its good for you.
Now - to make sure I don't get drawn into the pingpong desired by another -  time to unfollow this one for a while.
Several days from now there'll be some retorts - some nodes/square root spam - maybe some good posts by some !!  Yes !

Avatar of Optimissed

Listen, I read that Wiki article on mathematical induction for nearly 17.2 seconds. How could I be wrong over such a simple issue, when I studied it in such depth? happy.png

I wrote that I think I disagree because I think your explanation's mistaken. You could never in a million years show I'm wrong and that mathematical induction isn't based squarely on general induction. You could always try though.

Avatar of Optimissed

Naturally, the incentive to demonstrate a divergence from usual norms, by expressing thought in complex and meandering sentences, isn't to be taken as an obligation, since any judgement the reader may confer upon such endeavour may remain unmitigated by an empathy with the author's intentions; whether or not those intentions are consciously rational or merely the expression of an unconscious narrative which, when unpacked and set out clearly, may well demonstrate an inner and hidden antipathy towards ideas or ideals which the author may believe himself to espouse.

In short, madam, the writer may be confused.

Avatar of tygxc

#3644
"So your formula for the number of positions becomes:"
++ No. With width w = 4 and depth d = 39
Without transpositions:
1 + w + w² + w³ + ... + w^d = (w^(d + 1) - 1) / (w - 1)
With full permutations:
1 + w/1! + w²/2! + w³/3! + w^4/4! + ... + w^d/d! ~= e^w regardless of d
The truth lies in between

Avatar of haiaku
Optimissed wrote:

I'm asserting that anything other than an inductive understanding of a "chess solution" is impossible. I think that's completely incontrovertible.

Yes, we all think it's impossible with current technology, and the humankind might very well be extincted before it is possible, without a breakthrough in technology, or in our understanding of the game. You wondered why people seem fixated wiith a mathematical solution, then. To me it's not that, but exact solutions have been found for other games, so it's natural to take that as a reference. We already use inductive reasoning to play better and better, so it's completely fine, but it is not correct to call it an exact solution, a theorem, like someone (not you) does: chess is still too complex for that. Inductive reasoning cannot fully generalize, so its conclusions are, strictly speaking, only probable, while mathematical induction is a special case, where it can be proven that the generalization is full, i.e. exhaustive. That's still impossible for chess, without a complete mathematical representation of the game, as you noted.

Avatar of haiaku
tygxc wrote:

"So your formula for the number of positions becomes:"
++ No. With width w = 4 and depth d = 39, without transpositions:
1 + w + w² + w³ + ... + w^d = (w^(d + 1) - 1) / (w - 1)

            o  __   root node
           / | \   |   White's moves
          x x x x   nodes at depth 1 in plies
          |  |  |  |    Blak's moves
          o o o o  nodes at depth 2 in plies

After one full move the total number of nodes is 9, not 5 or 21, like in your formula. Anyway, d (that in your previous post was 34 and now has magically become 39), must be deduced from the total number of positions you intend to search, that is 10¹⁷. With d = 39, the total number of positions would be 4 × 10²³, per your formula. I am sure you are well aware of that.

Avatar of KingButDiff

makes sense tho

 

Avatar of tygxc

#3657

"            o  __   root node
           / | \   |   White's moves
          x x x x   nodes at depth 1 in plies
          |  |  |  |    Blak's moves
          o o o o  nodes at depth 2 in plies"

OK, without transpositions you count black replies too, getting upper bound:
2 * (1 + w + w² + w³ + ... + w^d) = 2*(w^(d+1) - 1) / (w - 1)
With full transpositions it becomes a lower bound:
2 * (1 + w/1! + w²/2! + w)³/3! + w^4/4! + ... + w^d/d!) =~ 2 * e^w

"d (that in your previous post was 34 and now has magically become 39"
++ No. d = 39 is the average number of moves in the ICCF WC.
d = 34 is the average number of moves past theory in the Madrid 2022 Candidates'

"the total number of positions would be 4 × 10²³, per your formula"
++ Let us take the 2 formulas above, w = 4, and d = 39
Without transpositions: upper bound 2*(4^40 - 1) / (8 - 1) = 8*10^23
With full transpositions: lower bound 2*e^4 = 100
Geometric mean on both: 9*10^12
So 10^17 is on the safe side.

I derived the 10^17 by another way.
Per Tromp there are 10^44 legal positions, but none of his 56011 legal samples are sensible because of multiple underpromotions to pieces not previously captured.
Per Gourion there are 10^37 positions without promotions to pieces not previously captured.
I multiply this by 10 to accept positions with 3 or 4 queens.
I note that 1000 sampled positions are not sensible either and accept Tromp's estimate that only 1 in 10^6 is sensible. That leads to 10^32 sensible positions.
Then in analogy with the solution of Checkers I estimate that only 10^19 of these are reachable in the course of the solution. E.g. when working on 1 e4, all positions with a white pawn on e2 are no longer reachable.
Then I estimate that only 1% of these are relevant. E.g. when 1 e4 e5 is proven a draw, then it is not relevant if 1 e4 c5 draws as well or not. Likewise I consider 1 a4 and 1 e4 e5 2 Ba6 as not relevant either.
That leaves 10^17 legal, sensible, reachable, and relevant positions.