Chess will never be solved, here's why

Sort:
technical_knockout

what about crazyhouse?

CDavvy
MARattigan wrote:
snoozyman wrote:
...
Since there are more chess games (10^120) than the number of atoms in the observable universe (10^80), it is highly unlikely that chess engines will ever completely solve the game of chess with all 32 pieces on the board in our lifetime.

10¹²⁰ b*llocks! That's a very rough estimate of the number of possible 40 move games with a constant 30 moves on each ply given by Shannon and never intended to represent the total number of chess games. 

The number of possible games under FIDE basic rules is א‎₀ if you consider only finite length games or if you allow (necessarily countable) infinite length games ב‎₁.

Also the number of atoms doesn't have much to do with it. The number of possible arrangements and states of atoms is far more relevant and that's vastly bigger. (On pre-quantum theory physics, at least, a single atom could encode the full set of up to 32 man tablebases and it would just be a matter of whether you could measure and set with enough precision to read and write the encoding.)

Regurgitating dubious figures is not a good approach to a feasible solution.

Well, no. The 50 move rule exists, and there are a finite number of pawn moves and exchanges that go with that. Chess is a finite game, at the end of the day, even if figuring out how long one can last is a pain that can run to thousands of moves. Forgive me if I've gotten anything wrong, I'm not qualified to talk about mathematics, these are just my observations. 

Elroch
tygxc wrote:

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

No. Solving chess requires this. Same for a white to play and draw problem, you need to deal with every black response to your first move, not just some of them.

Even more obviously where (unusually) you are not told whether the aim is to win or draw.

Your reasoning is inductive, based on a small sample of unreliable play.

There is no interest at all in "How to draw against 1 a4?"

Not unless you want to solve chess. Then it becomes essential, interesting or not.

 

tygxc

#2672

"you need to deal with every black response to your first move, not just some of them"
++ We disagree. Dealing best first is a good heuristic, also used to solve Losing Chess.

"you are not told whether the aim is to win or draw"
++ White tries to win, black tries to draw.
If black can draw against all reasonable white opposition, then chess is weakly solved.

"Your reasoning is inductive, based on a small sample of unreliable play."
I have hundreds of ICCF WC draws, 99% of which are ideal games with optimal moves.

"Then it becomes essential, interesting or not."
++ We disagree. 1 e4 and 1 d4 are essential. 1 c4 and 1 Nf3 a nice complement.
All 16 others can be ignored.

haiaku

@tygxc, your framework is so flawed and contrived, that I personally cannot properly deal with it in just one post. Once we have gone into details about any of the deep holes that can be found in your statements, we (you and I) may move on. So, about heuristics and selection of candidate moves, have you seen that even if you spend just 1 second to produce those 4 candidates for White (and one for Black for each of them), in 5 years you cannot have added to the search tree a number of them anywhere close to 10¹⁷?

tygxc

#2674
"about heuristics and selection of candidate moves"
++ Please see section 5.2 page 303 of
https://reader.elsevier.com/reader/sd/pii/S0004370201001527?token=F6ADD6A77544B86929A971CC9DE6A85753F3A8B3E14CFDD69AAB344D6EAF4833517E485A7033982799033E6312544A9E&originRegion=eu-west-1&originCreation=20220331110150 
"Next to brute-force methods it is often beneficial to incorporate knowledge-based
methods in game-solving programs. Their main advantage is providing an appropriate
move ordering or selection in the search trees." - Prof. van den Herik

That is what I think: brute force calculation from the 26-men tabiya towards the 7-men endgame table base, but incorporating knowledge for move ordering (first 1 e4, 1 d4, then 1 c4, 1 Nf3) and selection (no 1 a4, no 1 e4 e5 2 Ba6) i.e. pruning of the tree.

"in 5 years you cannot have added to the search tree a number of them anywhere close to 10¹⁷"
++ As previously said:
10^9 nodes/s/engine * 3 engines * 3600 s/h * 24 h/d * 365.25 d/a * 5 a = 4 * 10^17 nodes.
So yes, in 5 years 3 cloud engines do add 10^17 nodes to the search tree.

haiaku

Thanks, but I didn't ask for a lecture on heuristics. We may talk about that later. As for the question, be honest and do not mix things. You said previously that you aim to prune the children of a node, but the top 4, after 60 hours of calculations. All the nodes visited in this stage serve to produce those candidates; only then, the engine can proceed in expanding the search tree further, if those candidates did not get a definitive value.

MARattigan
CDavvy wrote:
MARattigan wrote:
snoozyman wrote:
...
Since there are more chess games (10^120) than the number of atoms in the observable universe (10^80), it is highly unlikely that chess engines will ever completely solve the game of chess with all 32 pieces on the board in our lifetime.

10¹²⁰ b*llocks! That's a very rough estimate of the number of possible 40 move games with a constant 30 moves on each ply given by Shannon and never intended to represent the total number of chess games. 

The number of possible games under FIDE basic rules is א‎₀ if you consider only finite length games or if you allow (necessarily countable) infinite length games ב‎₁.

Also the number of atoms doesn't have much to do with it. The number of possible arrangements and states of atoms is far more relevant and that's vastly bigger. (On pre-quantum theory physics, at least, a single atom could encode the full set of up to 32 man tablebases and it would just be a matter of whether you could measure and set with enough precision to read and write the encoding.)

Regurgitating dubious figures is not a good approach to a feasible solution.

Well, no. The 50 move rule exists, and there are a finite number of pawn moves and exchanges that go with that. Chess is a finite game, at the end of the day, even if figuring out how long one can last is a pain that can run to thousands of moves. Forgive me if I've gotten anything wrong, I'm not qualified to talk about mathematics, these are just my observations. 

Point is FIDE removed the 50 move rule from the basic rules in 2017 - and the triple repetition rule. So the basic rules game is infinite. The game was infinite in any case prior to the removal because the 50 move rule always needed to be claimed and there was never any compulsion to claim.

New 75 move and quintuple repetition rules, which result in automatic draws without any claim, were introduced to the competition rules game in 2017, so the longest competition rules game is now 8848.5 moves (see this).

The debate is not new. Troitzky wrote, of a game played in 1900:

... the game was considered a draw, as White after capturing Black's Knight and QRP could not mate in fifty moves. Maróczy proved that mate can be achieved in 49 moves, and indicated also that the rule of mate in 50 moves applies to tournament games only and not to match games. 

Edit:  Made some amendments to the above text in the interest of clarity and accuracy.

tygxc

#2676
"top 4, after 60 hours of calculations"
I later revised that. The 60 h was extrapolated from AlphaZero autoplay on slower hardware.
On a 10^9 nodes/s cloud engine the 60 h can probably be shortened to e.g. 1 min or less while still retaining confidence in the top 4 moves.

"All the nodes visited in this stage serve to produce those candidates; only then, the engine can proceed in expanding the search tree further, if those candidates did not get a definitive value."
++ Yes, that is right. A definitive value = looked up in the 7-men endgame table base or a 3-fold repetition draw, or a transposition to an earlier node reached.

tygxc

#2677
"Point is FIDE removed the 50 move rule from the basic rules in 2017 - and the triple repetition rule. So the game became infinite."
++ Without the 50-moves rule the game is still finite thanks to the 3-fold repetition rule.
As the number of legal chess positions is finite (10^44) so is the number of moves finite before all legal positions have been reached 3 times.

The 3-fold repetition rule is essential.
1 e4 c5 2 Nf3 d6 3 d4 cxd4 4 Nxd4 Nf6 5 Nc3 a6 6 Be3 Ng4 7 Bc1 Nf6 8 Be3 Ng4 can go on forever.

haiaku
tygxc wrote:

#2676
"top 4, after 60 hours of calculations"
I later revised that [ . . . ]

As I have already said at least three times, that's not the point. You didn't answer. It seems that you are trying to avoid the question because you don't understand how your algorithm works. Please detail how it works.

MARattigan
tygxc wrote:

#2677
"Point is FIDE removed the 50 move rule from the basic rules in 2017 - and the triple repetition rule. So the game became infinite."
++ Without the 50-moves rule the game is still finite thanks to the 3-fold repetition rule.
As the number of legal chess positions is finite (10^44) so is the number of moves finite before all legal positions have been reached 3 times.

The 3-fold repetition rule is essential.
1 e4 c5 2 Nf3 d6 3 d4 cxd4 4 Nxd4 Nf6 5 Nc3 a6 6 Be3 Ng4 7 Bc1 Nf6 8 Be3 Ng4 can go on forever.

FIDE also removed the triple repetition rule from the basic rules. 

Many games (ב‎₁) can go on forever under basic rules. Prior to 2017 this was the case for both basic rules games and competition rules games, because there was no legal obligation to claim under either the 50 move rule or triple repetition rule. 

One of the reasons for the agreed draw rule.

The competition rules game is now limited by mandatory 75 move and quintuple repetition rules.

tygxc

#2680

"you don't understand how your algorithm works. Please detail how it works"
++ Let us take an example.

This is an ICCF WC draw. It ends in a known drawn endgame with opposite colored bishops.
It is 99% sure to be an ideal game with optimal moves.
Look at white move 35 Be3. Check 3 other moves if they are draws as well.
Look at white move 34 a5. Check 3 other moves if they are draws as well.
Look at white move 33 a4. Check 3 other moves if they are draws as well.
Like that all the way back until other ICCF WC drawn predecessors.
If all are draws, then chess is weakly solved.

"I fail to see any real difference in the total number of nodes searched between your method and a typical search"
++ There is no real difference: I just use an engine. The only tweaks are that I do not look at black alternatives and that I only look at 4 white alternatives.

 

MARattigan
tygxc wrote:

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

...

1. It's not the generally accepted definition. What part of this post (and about 27 similar) did you fail to understand?

2. You don't abide by the definition of van den Herik (or anybody else's).

tygxc

#2683
Yes, I abide by the generally accepted definition
"weakly solved means that for the initial position a strategy has been determined to achieve the game-theoretic value against any opposition"
It is generally accepted by all in game theory.
It is carefully worded, so that it also applies to games with more than 3 outcomes (e.g. Lasker scoring proposal) etc.
You posted a position lost for white anyway. The definition applies. I see no relevance in your post. Anyway definitions are not open for discussion. If everybody applies his own definitions then confusion becomes even greater. Please stick to the same definition.

MARattigan
tygxc wrote:

#2683
Yes, I abide by the generally accepted definition
"weakly solved means that for the initial position a strategy has been determined to achieve the game-theoretic value against any opposition"
It is generally accepted by all in game theory.
It is carefully worded, so that it also applies to games with more than 3 outcomes (e.g. Lasker scoring proposal) etc.
You posted a position lost for white anyway. The definition applies. I see no relevance in your post. Anyway definitions are not open for discussion. If everybody applies his own definitions then confusion becomes even greater. Please stick to the same definition.

You have posted three incompatible definitions so far, as I first pointed out in #1764.

You don't stick to any of them.

"You posted a position lost for white anyway. The definition applies."

Are you saying that the strategy I gave here is a weak solution of that position? If so, you are the only person who would think so.

But at least it answers the question, "What part of this post (and about 27 similar) did you fail to understand?". The answer, apparently, all of it. About par.

tygxc

#2685
"You don't stick to any of them."
++ I stick to the generally accepted
"weakly solved means that for the initial position a strategy has been determined
to achieve the game-theoretic value against any opposition"

haiaku
tygxc wrote:

Look at white move 35 Be3. Check 3 other moves if they are draws as well [ . . . ]

That's trivial, and it's a very specific part of your algorithm. I would like to understand better the link between the 10⁹ nodes/s, the 60 hours (I refer to that because you originally used that, but it can be a parameter), the candidates, the pruned part of the search tree. You could even post a pseudocode, or even a code in a simple language (like Python, JavaScript) with some comments, that simulates what your algorithm is supposed to do every 60 hours. Black boxes, you know. Especially, it would be nice if, running it, we could see how many nodes are expected to be in the search tree, on average, every 60 hours (or 17 s, 1 s, changing the parameter), from the beginning of the search to the end after 5 years.

MARattigan
tygxc wrote:

#2685
"You don't stick to any of them."
++ I stick to the generally accepted
"weakly solved means that for the initial position a strategy has been determined
to achieve the game-theoretic value against any opposition"

It is not generally accepted.

It does say, "a strategy has been determined
to achieve the game-theoretic value against any opposition" (my italics)

You say here

"The only tweaks are that I do not look at black alternatives and that I only look at 4 white alternatives." (again my italics)

The italicised phrases are incompatible. You do not stick to the definition you quote. 

tygxc

#2688
The van den Herik definition is generally accepted. All in the field of game theory accept it.
You are the only one who comes up with your own, erroneous and confusing alternative.
I stick to the general definition, but then I work out in practice
I remark that black alternatives need no investigation as long as the result is a draw.
Besides per the definition it is white who has to oppose to the draw.
Black only has to achieve the draw in one way.
I remark that the top 4 white moves at enough time always contain the optimal move and thus the opposition with that time consists of 4 white moves.