Chess will never be solved, here's why

#3629
If there were no transpositions, then width w = 4 and depth d = 34 would lead to
1 + w + w² + w³ + ... + w^d = (w^(d+1) - 1) / (w - 1) positions
If all moves were interchangeable, then that would lead to
1 + w + w²/2 + w³/3! + ... ~= e^w positions , with d! = d*(d-1)*...*3*2*1 and e = 2.718281828...
The truth lies between the two. 

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.

#3633

"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."
++ The reduction is massive.

"Part of the reason is the large number of irreversible moves that can occur in an optimal chess game." ++ That is no reason. You can have reversible and  irreversible moves that lead to the same position. See counterexamples below.

"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."
++ Usually there are many legal paths between two legal positions. There are even billions of paths between the initial position and the position after 1 e4 e5. Most of these make no sense.
1 e4 e5
1 e3 e6 2 e4 e5
1 e3 e5 2 e4
1 e3 Nf6 2 Nf3 e6 3 Ng1 e5 4 e4 Ng8

"Every pawn move, every capture and more, kind of "resets the transposition clock""
++ No, that is not true. Counterexamples:
1 e4 d5 2 exd5 Qxd5 3 Nc3 Qd6 4 d4 c6 5 Ne4 Qc7 is exactly the same as
1 e4 c6 2 d4 d5 3 Nc3 dxe4 4 Nxe4 Qc7

1 e4 c5 2 Nf3 Nc6 3 d4 cxd4 4 Nxd4 Nf6 5 Nc3 e5 6 Ndb5 d6 7 Bg5 is exactly the same as
1 e4 c5 2 Nf3 e6 3 d4 cxd4 4 Nxd4 Nf6 5 Nc3 Nc6 6 Ndb5 d6 7 Bf4 e5 8 Bg5

1 e4 c5 2 Nf3 e6 3 d4 cxd4 4 Nxd4 a6 5 Nc3 Nc6 6 Be3 Nf6 7 Bd3 d5 8 exd5 exd5 9 O-O Bd6 10 Nxc6 bxc6 11 Bg5 O-O is exactly the same as
1 e4 e5 2 Nf3 Nf6 3 Nc3 Nc6 4 d4 exd4 5 Nxd4 Bb4 6 Nxc6 bxc6 7 Bd3 d5 8 exd5 cxd5 9 O-O c6 10 Bg5 Bd6

"transpositions are localised to the equivalence classes"
++ No, transpositions go past equivalence classes. See counterexamples above.

"the number of legal positions is relatively small compared to the number of legal games partly because of transpositions." ++ Yes, that is true.

"transpositions are already taken account of to get the number of legal positions in basic chess (~10^43 or whatever)." ++ 10^44 legal, but 10^17 sensible, reachable, and relevant. However, some people tend to go back to games and then forget about the major impact of transpositions and thus arrive at numbers of positions that are way higher.

How is w=4 and d=34 related to solving chess? 

Moves that transpose to positions that are considered the same for the purposes of 9.2.2 don't generally produce the same game state under competition rules, so what, in fact, is the calculation supposed to be related to at all? 

#3635
w = 4 is a reasonable width. As shown earlier this would make 1 error in 10^20 positions.
d = 34 is an everage depth after a predecessor game
The calculation shows the number of positions with 0 transpositions and with full permutation.

As @Elroch already mentioned, if there are 10⁴⁴ legal different positions (but he and @MARattigan correctly note that the the same position can produce different states, depending on the rules used), and one intends to search only a subset of 10¹⁷ of them, these are different positions too, and one already has to rely on transposition tables to not expand the same node twice. Now, if using TT the branching factor is 4, only a depth of 28 plies, i.e. 14 full moves, can be reached after a search of 10¹⁷ nodes; if, again using TT, the branching factor is 2, you can more or less double the depth, no more.
A typical engine can reach great depths thanks to late move reductions and other techniques, which make the engine actually very selective: it is not unusual that at the end of the search they check only one candidate move. That is obviously inadequate for a game-solving program.
Checkers and antichess have been solved after a relatively small search because captures are compulsory, so often players have just one legal move to play.

None of those "counterexamples" produce the same game state under competition rules.

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

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

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.

" 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 !

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.

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

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.

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 !

#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

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.

            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.

makes sense tho