Another thing that annoys me is the quote @tygxc uses is 15 years old. If 2007 computers could solve chess in 5 years, then current computers could do it in as little as 1 month... and top GMs hire other GMs all the time. Carlsen had more than 5 on his team for the last world chess championship match IIRC. The claim is, essentially, that they had the opportunity to solve chess in 1 month.
Chess will never be solved, here's why
Sort:
Dec 16, 2022
0
#5043
Supercomputers are about a million times faster than a top end PC. So, a few seconds should do. 
Dec 16, 2022
0
#5044
Oh, did Sveshnikov claim he could do it with standard computers? Looking up the quote he merely says "modern computers."
In any case modern supercomputers are at least 60x faster now, so 5 years -> 1 month.
@6665
"You also need to deal with lines like 1. e4 Nc6 etc... " ++ White tries to win, black tries to draw. Once black succeeds in all lines and white fails, chess is weakly solved.
On the first move white has 20 legal moves and black has 20 legal answers, that makes 20*20 = 400 legal positions after move 1. However, to weakly solve chess we only need a strategy, i.e. one strategy for black to draw, i.e. for all 20 white moves 1 black response that draws. Thus a priori only 20 = Sqrt (400) relevant positions after move 1 instead of 400.
We can use game knowledge to further prune this.
From no other input but the Laws of Chess and many boolean operations AlphaZero ranked the 20 legal first moves for white:
d4 > e4 > Nf3 > c4 > e3 > g3 > Nc3 > c3 > b3 > a3 >
h3 > d3 > a4 > f4 > b4 > Nh3 > h4 > Na3 > f3 > g4
If the 4 best moves cannot win for white, then the 16 worst moves cannot win either.
So instead of 400 legal positions or 20 relevant positions after move 1, this can be pruned to e.g.
- 1 e4 e5
- 1 d4 d5
- 1 c4 e5
- 1 Nf3 d5
How does that fit into your summary "If all lines end in a draw 7 men-table base endgame position or a prior 3-fold repetition, then that retroactively validates all black moves as optimal."
++ White tries to win, black tries to draw. If all lines end in a 7-men endgale table base draw, or in a prior 3-fold repetition, then in retrospect all black moves were good: fit to draw.
@6666
"If 2007 computers could solve chess in 5 years, then current computers could do it in as little as 1 month" ++ Maybe the 2007 statement was visionary. I only calculated with present computers. It took from 1961 to 1969 to land humans on the Moon. By the same logic that should only take one month now.
"top GMs hire other GMs all the time. Carlsen had more than 5 on his team for the last world chess championship match IIRC" ++ Carlsen, Caruana, Nepomniachtchi probably solved part of it during their months of preparation with grandmasters and cloud engines.
@6668
"did Sveshnikov claim he could do it with standard computers?" ++ Yes
"he merely says modern computers." ++ He did not say how many, but he used plural.
"modern supercomputers are at least 60x faster now, so 5 years -> 1 month."
++ I do not know how many nodes/s the best engine in 2007 could calculate.
I can only state that 3 modern cloud engines of 10^9 nodes/s can in 5 years exhaust the 10^17 relevant positions.
Dec 16, 2022
0
#5048
tygxc wrote:
@6665
"You also need to deal with lines like 1. e4 Nc6 etc... " ++ White tries to win, black tries to draw. Once black succeeds in all lines and white fails, chess is weakly solved.
No. This falls short.
You should know that two optimal strategies are needed, each achieving a bound on the value of the game, with the bounds being equal.
Neither strategy can make any assumptions about the opposing play - in particular the absurd assumption that a specific opposing strategy is optimal.
My take on it based on reading none of the past comments is that it will take a supercomputer to solve chess.
Even with pruning there have been positions that have been known to be draws that end up being mate in 546 moves. This would only extend the more pieces there are and while we can say that “nf3” is the best move here we really don’t know (yet) after 30000000000 moves.
Chess have been proven to be decidable and there number of moves are finite making it an EXP Complete problem and the computers we have today could solve it, it would just taking longer than we would exist. Eventually though with a quantum computer where these problems are easier to solve, we will have solved chess
Even with pruning there have been positions that have been known to be draws that end up being mate in 546 moves. This would only extend the more pieces there are and while we can say that “nf3” is the best move here we really don’t know (yet) after 30000000000 moves.
Chess have been proven to be decidable and there number of moves are finite making it an EXP Complete problem and the computers we have today could solve it, it would just taking longer than we would exist. Eventually though with a quantum computer where these problems are easier to solve, we will have solved chess
Dec 16, 2022
0
#5050
tygxc wrote:
So instead of 400 legal positions or 20 relevant positions after move 1, this can be pruned to e.g.
- 1 e4 e5
- 1 d4 d5
- 1 c4 e5
- 1 Nf3 d5
Any other response would be wasted.
@6667
"Supercomputers are about a million times faster than a top end PC"
++ False. A top cloud engine reaches 10^9 nodes/s. A standard desktop reaches 10^6 nodes/s.
That is a factor 1000. So instead of the 3 cloud engines of 10^9 nodes/s each also a cluster of 3000 desktops of 10^6 nodes/s each can do it in 5 years.
That is also how I estimated the cost. In 5 years computers should be written off.
So I calulate 3000 desktops at discount price $500 each = 1.5 million $ to rent the engines.
I calculate the 3 elder grandmasters at 100 k$/a each, thus 1.5 million $ to hire them.
That makes 3 million $ total.
@6673
"it will take a supercomputer to solve chess."
++ It even takes 3 supercomputers during 5 years to weakly solve chess.
"positions that have been known to be draws that end up being mate in 546 moves"
++ Yes, but these long forced mates cannot be forced from the initial position.
"we really don’t know (yet) after 30000000000 moves"
++ We do know. There are only 10^44 legal positions, the vast majority of them stupid.
Now 10^44 = 2^146. So even if there are only 2 choices per move, 146 moves exhaust the number of legal positions. Checkmates with more than 146 moves must contain a string of forced only moves for the defending side.
"the computers we have today could solve it"
++ Yes, it takes 3 of these 5 years to exhaust the 10^17 relevant positions.
Dec 16, 2022
0
#5053
So essentially what we have is a human sitting in front of stockfish saying this or that position is irrelevant so let's not look at it... and they claim this based on their intuition or on how stockfish ranks moves. Using that method you can prune all sorts of positions.
Ok, but this is not what people mean by "solve" chess. Try submitting that to an academic journal "we ignored 99.999...% of positions because, well, obviously."
With sloppy standards like that, anyone could solve chess... they could have solved it 20 years ago.
@6677
"a human sitting in front of stockfish saying this or that position is irrelevant"
++ No, the irrelevant positions are not reached in the course of the solving process.
See e.g. the relevant search space in the figure of Schaeffer's solution of Checkers
https://www.researchgate.net/publication/231216842_Checkers_Is_Solved
"Try submitting that to an academic journal we ignored 99.999...% of positions"
++ Read Schaeffer's solution of Checkers: of the 300 tournament openings he calculated only 19. 200 could be eliminated by transposition. 81 were eliminated as irrelevant by pruning.
Dec 16, 2022
0
#5055
tygxc wrote:
@6677
"a human sitting in front of stockfish saying this or that position is irrelevant"
++ No, the irrelevant positions are not reached in the course of the solving process.
See e.g. the relevant search space in the figure of Schaeffer's solution of Checkers
https://www.researchgate.net/publication/231216842_Checkers_Is_Solved
"Try submitting that to an academic journal we ignored 99.999...% of positions"
++ Read Schaeffer's solution of Checkers: of the 300 tournament openings he calculated only 19. 200 could be eliminated by transposition. 81 were eliminated as irrelevant by pruning.
Sure, I understand there's a difference between weakly solved and solved.
@6679
"I understand there's a difference between weakly solved and solved"
++ Many here still do not understand the difference between weakly and strongly solved.
Checkers has been weakly solved only and with 10^14 relevant positions of the 10^20 legal positions.
Chess can be weakly solved with 10^18 relevant positions. That can be done in 5 years.
Strongly solving Chess i.e. a 32-men table base, would require all 10^44 legal positions, which would take 10^44 nanoseconds of time and 10^44 bits of storage, out of reach now.
tygxc wrote:
@6679
"I understand there's a difference between weakly solved and solved"
++ Many here still do not understand the difference between weakly and strongly solved.
Checkers has been weakly solved only and with 10^14 relevant positions of the 10^20 legal positions.
Chess can be weakly solved with 10^18 relevant positions. That can be done in 5 years.
Strongly solving Chess i.e. a 32-men table base, would require all 10^44 legal positions, which would take 10^44 nanoseconds of time and 10^44 bits of storage, out of reach now.
How many years have you been saying it "can be done in 5 years"? Does the 5 years start every time you say it again or did it start 5 or 6 years ago?
Because if it starts every time you say it again then the title of this topic is true, it will never be solved. Because 5 years from now will never happen.
And if you started saying that 3 and a half years ago for example then you should say it "can be done in 18 months". Not 5 years.
@6681
"Does the 5 years start every time you say it again"
++ No, the 5 years start after funding to hire the 3 grandmasters and rent the 3 cloud engines.
How much does it cost to hire 3 grandmasters? Like a hundred bucks or something? I don't know what 3 cloud engines rent for but it can't be that much. So why hasn't your 5 years happened yet?
@6636
"Are you saying you can square root the positions because we're assuming we can ignore all non-optimal play by black?" ++ We can even discard optimal play by black. Suppose both 1 e4 e5 and 1 e4 c5 draw. To weakly solve chess it is possible to look only at 1 e4 e5 and discard 1 e4 c5.
Not if 1. e4 is part of your drawing strategy for white! You also need to deal with lines like 1. e4 Nc6 etc...
"How do you discard non-optimal moves without analyzing them?"
++ By the end result.
That you have guessed?
If all lines end in a draw 7 men-table base endgame position or a prior 3-fold repetition, then that retroactively validates all black moves as optimal.
So let's consider the example where 1. e4 is part of your drawing strategy as white. Unquestionably, the positions reached by 20 legal black moves need to be dealt with by a competent game solver. (I say "unquestionably", because if you are failing even to consider what legal moves are available from a position, I have to suggest you should lay off the wacky baccy).
How does that fit into your summary "If all lines end in a draw 7 men-table base endgame position or a prior 3-fold repetition, then that retroactively validates all black moves as optimal.", given the sole objective of the strategy is optimality for WHITE, a different thing to optimality for black?