Chess will never be solved, here's why - Chess Forums - Page 283

TheChessIntellectReturns · 2022-01-16T22:50:19-08:00

Imagine a chess position of X paradigms. Now, a chess computer rated 3000 solves that position. All well and good. Could another computer rated a zillion solve that position better than Rybka? No, because not even chess computer zillion could solve the Ruy Lopez better than a sad FIDE master coul

MARattigan

Oct 1, 2022

0

#5641

She doesn't like it either. ...

Then possibly not much use in any case.

Elroch

Oct 1, 2022

0

#5642

MARattigan wrote:

Optimissed wrote:

tygxc wrote:

@5770
"Solved 32 piece chess game needs approximately 3 x 10^60 Bytes of data storage."
++ No. 10^44 bit is enough. Tromp has proven a 1 to 1 relationship between natural numbers 1...N and chess positions. So an array of 10^44 bit: 0 = draw, 1 = no draw is enough to store a strong solution of Chess.

Says you. Don't think so.

For once I agree with @Optimissed.

(I'm getting worried.)

Maybe you should be.

The latest tablebases achieve compression of 1 bit per position with efficient access.

It's worth remembering that compression is always a tradeoff between space and efficient access. You can "store" data in the size of a program to generate it on the fly. This is in cases like this hideously inefficient in computation time.

But Syzygy and its 8 piece successor use very high compression to 1 bit per position while permitting quick access. Don't ask me how.

You could argue that 32 pieces would not permit such compression. I suspect this is not true, but even if it was, you could likely throw in a tiny factor like 4.

So storing a 32-piece tablebase of over 10^44 positions in a similar number of bits is theoretically feasible. The problem is that 10^44 (non-trivial) operations is beyond computers that can be designed today. (

10^44 trivial operations is also beyond currently feasible. Eg, the current world's fastest supercomputer can manage this number of FLOPS (simplest floating point arithmetic operations) in about 7 billion trillion years).

Optimissed

Oct 1, 2022

0

#5643

Elroch wrote:

MARattigan wrote:

Optimissed wrote:

tygxc wrote:

@5770
"Solved 32 piece chess game needs approximately 3 x 10^60 Bytes of data storage."
++ No. 10^44 bit is enough. Tromp has proven a 1 to 1 relationship between natural numbers 1...N and chess positions. So an array of 10^44 bit: 0 = draw, 1 = no draw is enough to store a strong solution of Chess.

Says you. Don't think so.

For once I agree with @Optimissed.

(I'm getting worried.)

Maybe you should be.

The latest tablebases achieve compression of 1 bit per position with efficient access.

It's worth remembering that compression is always a tradeoff between space and efficient access. You can "store" data in the size of a program to generate it on the fly. This is in cases like this hideously inefficient in computation time.

But Syzygy and its 8 piece successor use very high compression to 1 bit per position while permitting quick access. Don't ask me how.

You could argue that 32 pieces would not permit such compression. I suspect this is not true, but even if it was, you could likely throw in a tiny factor like 4.

So storing a 32-piece tablebase of over 10^44 positions in a similar number of bits is theoretically feasible. The problem is that 10^44 (non-trivial) operations is beyond computers that can be designed today. (10^44 trivial operations is as well).

Boiling the rhetoric out, I think that means that he's reluctantly admitting that you still need a psychiatrist, MAR. I'll just have a word with Christine and get her to put her fees up again, if you like.

Elroch

Oct 1, 2022

0

#5644

A 32-piece tablebase is a strong solution of chess. You can trivially use it to make optimal strategies for each side with merely 1 access of the database per move.

[This was a reply to a post that seems to have been deleted].

MARattigan

Oct 1, 2022

0

#5645

Elroch wrote:

A 32-piece tablebase is a strong solution of chess. You can trivially use it to make optimal strategies for each side with merely 1 access of the database per move.

[This was a reply to a post that seems to have been deleted].

Reinstated in essence.

@tygxc is specifying a WD tablebase. That's not a solution. A WDL tablebase is also not a solution.

And 10^44 is not the number of competition rule game states, nor even Tromp's number.

I think Huffman codes come into it. Whether a solution could be stored in 10^44 is open to discussion.

Elroch

Oct 1, 2022

0

#5646

Syzygy and its 8-piece successor (under development) are state of the art and use about 1 bit per position, so no need to argue about WD/WDL.

Correct about the count. For practical purposes, it doesn't matter. It's too big to consider without a paradigm shift.

MARattigan

Oct 1, 2022

0

#5647

Elroch wrote:

Syzygy and its 8-piece successor (under development) are state of the art and use about 1 bit per position, so no need to argue about WD/WDL.

@tygxc says So an array of 10^44 bit: 0 = draw, 1 = no draw is enough to store a strong solution of Chess. justifying it by postulating a WD tablebase. Are you saying I should have agreed with @tygxc in preference to @Optimissed?

Is 10^44 classical bits enough to hold a strong solution of competition rules chess without holding a generation program in the probe code? Like @Optimissed I don't think so, but you can try to persuade me (granted it's a lot of bits).

Remember Syzygy is not a strong solution of any but a few endgame positions, not even the ply count 0 positions.

But I take your point about simply storing the Syzygy generation program. That brings us back to the definition of "solution".

Correct about the count. For practical purposes, it doesn't matter. It's too big to consider without a paradigm shift.

DiogenesDue

Oct 1, 2022

0

#5648

MARattigan wrote:

Reinstated in essence.

@tygxc is specifying a WD tablebase. That's not a solution. A WDL tablebase is also not a solution.

And 10^44 is not the number of competition rule game states, nor even Tromp's number.

I think Huffman codes come into it. Whether a solution could be stored in 10^44 is open to discussion.

I had Huffman as a teacher once. Have to tell you, I was not impressed with him in that capacity.

Optimissed

Oct 1, 2022

0

#5649

MARattigan wrote:

She doesn't like it either. ...

Then possibly not much use in any case.

Unfortunately a lot of agencies have totally bought into it and are selling it to people who need help, so they're not quite honest. But better than nothing at all.

Elroch

Oct 1, 2022

0

#5650

MARattigan wrote:

Elroch wrote:

Syzygy and its 8-piece successor (under development) are state of the art and use about 1 bit per position, so no need to argue about WD/WDL.

@tygxc says So an array of 10^44 bit: 0 = draw, 1 = no draw is enough to store a strong solution of Chess. justifying it by postulating a WD tablebase. Are you saying I should have agreed with @tygxc in preference to @Optimissed?

Is 10^44 classical bits enough to hold a strong solution of competition rules chess? Like @Optimissed I don't think so, but you can try to persuade me (granted it's a lot of bits).

Remember Syzygy is not a strong solution of any but a few endgame positions, not even the ply count 0 positions.

Correct about the count. For practical purposes, it doesn't matter. It's too big to consider without a paradigm shift.

From the Syzygy documentation:

"Syzygy Bases consist of two sets of files, WDL files (extension .rtbw) storing win/draw/loss information considering the fifty-move rule for access during search ..."

I believe this implies Syzygy provides a strong solution for all positions. (There can be no repetitions if you aim efficiently towards a win at the first opportunity, and if you are aiming for a draw any drawing move will do.

MARattigan

Oct 1, 2022

0

#5651

@Elroch

"I believe this implies Syzygy provides a strong solution for all positions."

Try it after move 20 here. There is a mate in 16 if you play it against Syzygy (which Tarrasch/SF15 makes a rather pathetic attempt at here, but it does at least mate), but not if you do it the other way round and take his top move (when you draw).

[Event "?"]
[Site "?"]
[Date "2022.09.12"]
[Round "?"]
[White "Stockfish 15"]
[Black "martin"]
[Result "1-0"]
[ECO "A00"]
[FEN "8/8/8/4k3/8/8/1R6/K7 b - - 0 1"]

1... Kd4 2. Ka2 Kc3 3. Rh2 Kd4 4. Rb2 Kd3 5. Kb1 Kc3 6. Rh2 Kd4 7. Rb2 Kc3 8.
Rh2 Kd4 9. Rb2 Kc3 10. Rg2 Kd3 11. Ka1 Kd4 12. Ra2 Kc3 13. Rg2 Kd4 14. Ra2 Kc3
15. Rf2 Kd3 16. Rf1 Kd4 17. Rb1 Kc3 18. Rf1 Kd4 19. Rf2 Kc4 20. Rb2 Kd4
{Stockfish 15-martin} 21. Rb5 Kc4 22. Rg5 Kd4 23. Kb2 Kc4 24. Ra5 Kd4 25. Kb3
Ke3 26. Kc4 Ke4 27. Kc3 Kf3 28. Kd4 Kf4 29. Kd3 Kf3 30. Ra4 Kf2 31. Rd4 Kf3 32.
Ra4 Kf2 33. Rf4+ Kg3 34. Ke3 Kg2 35. Rg4+ Kh3 36. Kf3 Kh2 37. Kf2 Kh3 38. Ra4
Kh2 39. Rh4# 1-0

Elroch

Oct 1, 2022

0

#5652

Sorry - I realise my reasoning only supports the conclusion that Syzygy explicitly provides all weak solutions. It also provides strong solutions for all drawing positions where this is not dependent on earlier repetitions of position, I think I am correct to claim.

It only provides a subset of strong solutions for winning positions, since where there are multiple strong solutions without a repetition rule, some of them may not work with a repetition rule and past repeated positions. Thus it is necessary to know which positions to avoid.

While the repetition rule is useful for practical chess, chess without this rule is more elegant. For some N (maybe less than 500), an N-move rule is perfectly adequate to deal with the infinite games that exist in basic chess (stopping it being a combinatorial game).

MARattigan

Oct 1, 2022

0

#5653

Elroch wrote:

Sorry - I realise my reasoning only supports the conclusion that Syzygy explicitly provides all weak solutions.

Weak solutions to positions including, but not restricted to, positions with ply count < 4, but not all positions - see the example in my previous post. Not many guaranteed in fact, but obviously enough for use in a chess game.

That assumes a sensible definition of weak solution.

You can't actually give Syzygy a competition rules position. It can take neither ply count nor previous moves. What you can give doesn't usually determine the game-theoretic value (assuming a suitable set of rules) but may determine optimal moves.

It also provides strong solutions for all drawing positions where this is not dependent on earlier repetitions of position, I think I am correct to claim.

It only provides a subset of strong solutions for winning positions, since where there are multiple strong solutions without a repetition rule, some of them may not work with a repetition rule and past repeated positions. Thus it is necessary to know which positions to avoid.

A strong solution for a position P has to provide a strategy for all positions X reachable from P. X can usually be any of a win either way or a draw irrespective of what P may be. Whether the strategy will avoid repetitions will normally be independent of P (unless P is terminal or half dead).

The strategy for X will be a weak solution for each player so that's back to the first comment.

The only rôle P plays in a strong solution of P is to determine the reachable positions.

While the repetition rule is useful for practical chess, chess without this rule is more elegant. For some N (maybe less than 500 - or maybe more than 3000000000 looking at Haworth's figures; we'll have to wait for Haworth's 32 man DTR tablebases for a clue), an N-move rule is perfectly adequate to deal with the infinite games that exist in basic chess (stopping it being a combinatorial game).

Agreed.

XOXOXOexpert

Oct 1, 2022

0

#5654

@tygxc can you show me the solution please.

DiogenesDue

Oct 1, 2022

0

#5655

XOXOXOexpert wrote:

@tygxc can you show me the solution please.

A more loaded question has never been asked on these forums.

Optimissed

Oct 1, 2022

0

#5656

Regarding our little part in the melodrama, probably not.

https://www.youtube.com/watch?v=OTn01jjEFfY

Optimissed

Oct 1, 2022

0

#5657

https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=&cad=rja&uact=8&ved=2ahUKEwjW1f65wMD6AhWBQEEAHcamCqsQwqsBegQIOxAB&url=https%3A%2F%2Fwww.youtube.com%2Fwatch%3Fv%3DVguUJ6WWRRs&usg=AOvVaw1oqG-RmWqm_3tvKvPDizNi

1a3

Oct 1, 2022

0

#5658

By definition, a mistake is anything that changes the outcome, so in that case there are many good moves in 1 position

tygxc

Oct 1, 2022

0

#5659

@5803
"a mistake is anything that changes the outcome,
so in that case there are many good moves in 1 position"
++ Yes, that is right. White has 19 good moves and 1 bad move 1 g4? that loses by force.
Black has less than 19 good replies to each of those.

tygxc

Oct 1, 2022

0

#5660

@5790

"@tygxc is specifying a WD tablebase. That's not a solution."
++ It is a solution. If it is not D, then it is obvious if it is W or L.

"A WDL tablebase is also not a solution." ++ It is a solution. In a certain D position,
legal moves that lead to D are good and legal moves that lead to L are bad.

"And 10^44 is not the number of competition rule game states"
++ The 50-moves rule plays no role in weakly solving Chess.
10^44 is the number of legal positions.
The competition rules define positions:
'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. Thus positions are not the same if:
9.2.2.1 at the start of the sequence a pawn could have been captured en passant
9.2.2.2 a king had castling rights with a rook that has not been moved, but forfeited these after moving. The castling rights are lost only after the king or rook is moved.'
https://handbook.fide.com/chapter/E012018

"nor even Tromp's number"
++ Tromp's number 4.82 * 10^44 is a factor 4 too high because of up / down and left / right symmetry: mirror images with exactly the same game state and exactly the same mirror image moves. That leaves 1.205 * 10^44, i.e. 10^44 for all practical purpose.

"Whether a solution could be stored in 10^44 is open to discussion."
++ It can, as I explained: just an array with bits draw / no draw.
The compression techniques no longer work for 32 men as they depend on sparse occupation.
However 10^44 bit is enormous, even for synthetic DNA.