Chess will never be solved, here's why

Sort:
tygxc

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

haiaku
tygxc wrote:

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

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.

MARattigan
tygxc wrote:

#3633

...

++ 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

...

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

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.

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

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

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.

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 !

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.

playerafar


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

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.

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 !

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

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.

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.

KingButDiff

makes sense tho

 

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.

novetan5

I give buy lopez a try

Elroch
tygxc wrote:

...

none of his 56011 legal samples are sensible because of multiple underpromotions to pieces not previously captured

...

Breaking news - these days when you play chess you don't have to just use the pieces that come in the box.

tygxc

#3661
" you don't have to just use the pieces that come in the box"
++ There has to be a good reason to underpromote to anything else but a queen.
Underpromotion to a knight sometimes makes sense to utilise its unique properties.
Underpromotion to a rook or a bishop sometimes makes sense to avoid stalemate.
Promoted rooks and / or bishops on the losing side make no sense: it were better queens.
Promoted rooks and / or bishops on both sides make no sense: it were better queens.
In real grandmaster / engine / correspondence games 3 or 4 queens occasionally happen, but multiple underpromotions to pieces not previously captured like in the 56011 samples never.