Chess will never be solved, here's why

@12983

"the methods stockfish uses to play also prevent it from solving chess i.e. the way it prunes moves makes it a good player"
++ (1) To play is to select 1 legal move among the legal moves.
(2) To analyse, like for weakly solving chess, is to select all legal moves that oppose against the game-theoretic value.
(3) To generate a table base like for strongly solving chess is to select all legal moves.

If a program can do (1), then it can also do (2).
If a program can do (1) or (2), then it can also do (3).

llama puts it very clearly. As usual.
Stockfish is a 'non-solver'. The key.
An excellent post by llama.

But now there's a whole new subject - directly relevant to the forum topic.
Quantum computers.
Supposedly they 'got started' in the 1990's.
Are they really 'for real'?
If they're for real - why aren't they in widespread use yet?
And if and when that ever happens - how much faster would they be than today's computers?
from the net:
"Quantum computers have shown that they can process certain tasks exponentially faster than classical computers. In late 2019, Google claimed that it had managed to solve a problem that would take 10,000 years for the world's fastest supercomputer within just 200s using a quantum computer"
A billion times faster in other words?

With all the new physical properties and processing capabilities that quantum systems possess, it’s only natural that we may get tempted to think that they are universally faster than the classical ones. This is, unfortunately, not true.
------------------
"There are certain problems that classical computers can solve faster. For example, simple arithmetic and text processing are better suited for classical machines. Conversely, quantum machines excel in areas such as machine learning and cryptography."
-----------
And - what about the practical issues?
Quantum computers. Qubits.
Great new topic within the main topic.

Well sure, but what we're saying is you need an algorithm. Which will require more qubits, and we already ran out... You'll have to tell the computer what the goal is, you can't just give it a chess board and watch it pick up the pieces and start playing to win on its own. It could make any random move but it needs to know things like... to play for checkmate, how to run the game taking turns between white and black, what a stalemate is, what a repetition is... 
It needs to understand that black has a goal of checkmate that's in opposition to whites goal of checkmate...
It needs to be able to look ahead moves... 
This is an algorithm we're talking about. 
It's hard to estimate what the complexity of this quantum algorithm will be, the truth I'm just coming up with this stuff, neither of us are quantum computing engineers, but one thing I'm sure of is there will be more problems and more complexity that arises than what we know here today.

True true but they practically won almost every rapid game on chess.com anyway lol like otb rapid there might be less blunders but online from personal experience rapid is a complete mess

@12989

"you need an algorithm" ++ The algorithm to generate an 8 men table base from a 7-men endgame table base is retrograde analysis. That is how the 7-men endgame table base was generated from the 6-men endgame tablebase etc. This is about future strongly solving chess with a quantum computer to ultimately a 32-men table base of 10^44 positions.

"we already ran out" ++ For now, but in the future more qubits will be available.

"You'll have to tell the computer what the goal is" ++ Generate an 8-men endgame table base from the 7-men endgame tablebase

"playing to win on its own" ++ No generate win/draw/loss for 8 men from win/draw/loss for 7 men.

"to play for checkmate, how to run the game taking turns between white and black, what a stalemate is, what a repetition is" ++ No need: just retrograde analysis.

"It needs to be able to look ahead moves" ++ No, look backwards.

It has been done before to generate 4 men from 3 men, 5 men from 4 men, 6 men from 5 men, 7 men from 6 men. Only a quantum computer has the potential to do it in parallel, thus faster and do the required retrograde step directly, instead of indirectly.

Well even if that's your goal - a very modest one, certainly you aren't solving the game of chess with that - the computer has to have a concept of a "good move" to determine if the position prior should lead to the next. It has to understand checkmate to make a move... you're talking nonsense. We don't want a set of all possible 8 man positions that could possibly lead to 7 man positions, we want those 8 man positions that with best play lead to a 7 man position. Notice the keyword play here - the computer has to know how to play, it has to define playing the game.

You could set that as your goal sure, but the computer is not going to just pick up the board and know how to play.

@12992

"Well even if that's your goal - a very modest one" ++ Not modest, but ambitious.

"you aren't solving the game of chess with that"
++ Once 32 men are reached, chess is stronly solved.
With present conventional computers generating the complete table base 7->8->9...->32 would take too much time and storage. A future 2100 mature quantum computer could do it much faster while in parallel and directly instead of indirectly.

"We don't want a set of all possible 8 man positions that could possibly lead to 7 man positions" ++ The Endgame tablebase shows the best play.

"the computer has to know how to play" ++ No, only positions linked by legal moves.

"it has to define playing the game" ++ It only needs a legal move generator.

I see @tygxc has moved on from completely failing to weakly solve chess to speculating about strongly solving chess. Probably a good move: that post mostly makes sense.

You can't construct a proper N+1 piece tablebase purely by retrograde analysis from the N piece tablebase. You first of all need to deal with mates and stalemates that have N+1 pieces. Pure retrograde analysis would never discover these existed, since there is no legal path from them to the smaller tablebase.

This deficiency can be dealt with by adding a step: whenever a position is added to the N+1 piece tablebase a forward step can take place to see if there are any immediate resolutions by stalemate or checkmate.

I am not 100% sure what the exact procedure used for efficiency is.

And note that for larger tablebases, even this does not suffice. There are positions that can never have a capture in their future, but which are not resolved (so not dealt with by the above). These would be missed without an additional way to included them.

Which is the smallest such position? Here is a 10 piece example that can be reached in a legal game:

the empirical N = B = 3 P, R = 5 P, Q = 9 P

imo these are kinda rough #'s. theyre are gonna needta be alot more elastic. and thiss where AI comes in. u know, move made for chess to be solved to a win needs for these #'s to be broken down to at least tenths (if not hundreths). maybe theyve already done this - dont know.

Sure it will do it faster, I am aware of that, my point is it needs an algorithm. It has to know how to play the game, it has to know how to evaluate a position.

The existing tablebases we have were generated using minimax algorithms exhaustively traversing the game tree. Minimax - Wikipedia

The computer has to know how to play the game. You cannot employ a minimax algorithm without some ability to evaluate a position. An 8 piece position where I throw my knight away for no reason and then reach a 7 man tablebase position does not belong in the 8 man tablebase. If the computer doesn't have any concept of a "good move" it cannot generate any useful tablebase. There is no doubt about this.
If this were not the case, all the final 32-man tablebase of chess would be is just a set of all possible permutations of moves, and nothing more. Infact it would actually be an infinite set.

the largest quantum computer *in the world* today has 1121 qubits.

not what i heard. Atom Computing has one at 1125 Qbits. but theyre on birdcaged N atoms not SC circuits. is Condor ?

Well, at least you didn't say COBOL.

dodo due did. that one burst me into tears btw !

The only sense it which it has to know how to play the game is that:

1. it can calculate legal moves (in the reverse direction. i.e. given a position P, the retrograde step identifies all positions that could reach P in one legal move)
2. it can identify if a position is mate or stalemate

The retrograde analysis progresses by first identifying all the positions with mate on the board
("-M0") then the positions where one side has mate in 1 ("M1") then the positions where one side cannot avoid being mated in 1 whatever they play ("-M1"), then the positions where a player can mate in 2 ("M2").

Each step is just 1 ply retrograde analysis. Eg for a position to be getting mated in 2, every move by a player must lead to a position where the other side has mate in 1. Only positions that satisfy this are classified as "-M2".

Eventually a step occurs where the class of positions being generated is null. I think that class in the 7-piece Syzygy tablebase is "-M549". This was reached after 1098 passes of retrograde analysis.

At this point you have a tablebase only of decisive positions - losing or winning. You can deduce that all other positions with the given pieces are drawn.

The latter deals with my observation that there are positions that can never lead to mate, stalemate or a capture, so would never appear in retrograde analysis. They are just a subset of the class of inferred drawn positions.

There is no need to explicitly store drawing positions in a tablebase. If a query fails to find the position, it is drawing. You can then look forward one ply to see the positions that can be reached and to identify the value of all of those positions by a similar lookup.

Technicalities include that all positions with a single set of material are kept together (as all moves except captures transition between them, and that lookups take into account symmetries, so that you only need one copy for up to 8 positions (left/right, up/down, black/white symmetries).

Some time in the 80's I was attracted by an ad that was giving people tests of programming aptitude for lucrative commercial programming. I liked the idea of seeing how well I did in the test, so I hopped on the tube and did a sort of exam. Apparently I aced it (could be genuine, could be really a marketing technique), but then I discovered that what they were offering was a future in COBOL applications development, at which time I said "No way, Jose". At that time it sounded like an invitation to the Stone Age.

Apparently COBOL applications were developed even up to around 2006 and there may still be legacy systems being maintained. What a horrible thought.

[I bet someone here has made a fortune programming in COBOL...]

See just think if quantum idea is billions of times faster and all this tech has come in the last hundred years what will it look like in 1000 if we are not all dead. We don't even have a basis for what they could be doing in the future maybe we all die from a comet first who knows but I'm betting if we don't it gets full solved by someone far more clever than any of us long after we die.

With current computers it would take many trillions of years to solve chess.
Yes - computers will improve and so will their programming.
Provided there's no nuclear war or some other kind of world disaster.
And if and when chess is 'solved' it won't have to be somebody 'cleverer' or even clever. It will only need the better enough hardware and better enough software and enough extra money. But all three of those are each very unlikely.

@12998

"given a position P, the retrograde step identifies all positions that could reach P in one legal move"
++ That is one reason why quantum computing is good at this: a conventional computer starts from the earlier position and generates all legal moves there are possible from it and then checks if some already are strongly solved, i.e. already are in the table base.

A quantum computer can perform this inverse operation directly:
given position P it gives all positions that could reach P in one legal move.

A quantum computer can perform this operation in parallel: given an array of positions P(k) in one operation gives all arrays of positions that could reach P(k) in one legal move.

"To analyse, like for weakly solving chess, is to select all legal moves that oppose against the game-theoretic value."

solving again means dealing with EVERY move. try again.