Chess will never be solved, here's why

Sort:
MARattigan
haiaku wrote:

@Marattigan

To weakly solve a game it is enough to provide an optimal strategy in a reasonable time, so to save storage space, you can leave out some lines and provide them on demand, but you have to know, after tests, that they can be provided on demand.

MARattigan wrote:

Schaeffer’s proof solved checkers for 19 different openings, all of which end in draws. There are 300 total tournament openings, but many of these were determined to either be mirrors of other positions or altogether irrelevant to the proof because they lead to positions common to other openings.

For chess, If one sits at the board against SF and has weakly solved the game, s/he will make some moves using the proof tree, some others can be calculated by an engine, but it must hit an endgame tablebase or an already solved position in reasonable time. Instead, if s/he uses an engine just to evaluate the position as usual, they will likely draw against an equally strong silicon opponent, but the moves would be just the result of evaluations/guesses: if they use the same engine 10 years later against a much stronger opponent, they would lose most of the games. If chess was indeed weakly solved, on the other hand, they would replicate the same outcome with the very same silicon ally even 1000 years later.

You need only provide one opening line (half tree) if you weakly solve a game as a win. You have to provide a full half tree for each side if you weakly solve it as a draw.

That was apparently not done.

Of 300 openings only 19 were shown to draw. A further 100 validly excluded as transposition of moves, but the remaining 181 dismissed by the assertion that it would be possible to prove them drawn by alpha-beta pruning (without details of how that could lead to a proof) but without actually performing the computations.

I may be reading it wrong, but it is at least difficult to find either further details or an available database of the results computed. No database - no weak solution. Most of the lines still to be computed - no ultra weak solution either.

Btw. you have a touching faith in the reliability of computer results obtained over decades on different machines involving large amounts of data.

Elroch

A little intuition on how ridiculous positions may not be so ridiculous. Throw some reachable set of material on the board (<=32 pieces, with enough pieces and pawns missing to make the number of excess pieces possible by promotion) on the board until you get a position that is legal (a large proportion) and you will get a position where Stockfish will provide some material balance between say -200 and 200. 

It is to be expected that the distribution of the evaluation is not thinner than average near the middle, so at least 0.5% of these positions will be in the range -1 to 1 evaluation and for it to be entirely plausible the positions are a draw to an oracle (some won't but these will be made up for by others that appear to have larger evaluations that are in truth more difficult draws).

That means a quite large fraction of random positions are perfectly reasonable ones for optimal play to go to (if chess is a draw), and this is true for all chains through such positions, which can certainly start from a normal position such as the initial position.

Taking one such random position with an unusually large number of knights for example, you can work backwards from that position to reach an exponentially growing number of other positions by optimal play. It may be only when you reach say 10^9 such positions that one of them involves the possibility of an underpromotion to a knight (this is excessively pessimistic - underpromotions comprise at least 1 in a 100,000 perceived best moves in high level chess games).

You can repeat this process for multiple promotions to find that it is indeed perfectly reasonable for optimal play to reach positions with large numbers of underpromotions.

Note that each step of this process - working back from a position with odd material balance to an underpromotion - traverses a tiny fraction of the set of legal positions, say N positions (I generously allocated N=10^9 but was well aware a lot fewer would probably be needed on average), so a position with M underpromotions can reasonably find a path back to a position with no underpromotions by retrogade analysis looking at N * M positions, a very tiny fraction of the whole.

An intuitive error would be to think this number would be N^M, which would become very large for large M.

haiaku
Optimissed wrote:

"Optimal strategy" can obviously alter because it's inferential, based on ideas we have at present. The whole idea of a weak solution which may be relied upon absolutely is nonsense.

For the purpose of weakly solving chess, "strategy" is not what we commonly think, that is a set of rule of thumbs, ideas, principles we use during the game to deal with the complexity of chess with our brains; it means a proof tree: for any opponent's move from the beginning, you can prove there is a move that will lead to the game-theoretic value of the game. Leaving out, for simplicity now, the matter of the 50-moves rule or three-fold repetition, you can see the previous posts here and here.

llama51
Elroch wrote:

A little intuition on how ridiculous positions may not be so ridiculous. Throw all the pieces on the board (with some of them falling off) until you get a position that is legal (a large proportion) and you will get a position where Stockfish will provide some material balance between say -200 and 200 once a sizeable.  It is to be expected that the distribution of the evaluation is not thinner than average near the middle, so at least 0.5% of these positions will be close enough to 0 evaluation for it to be entirely plausible the positions are a draw to an oracle (some won't but these will be made up for by others that appear to have larger evaluations that are in truth more difficult draws).

That means a quite large fraction of random positions are perfectly reasonable ones for optimal play to go to, and this is true for all chains through such positions, which can certainly start from a normal position such as the initial position.

Taking one such random position with an unusually large number of knights for example, you can work backwards from that position to reach an exponentially growing number of other positions by optimal play. It may be only when you reach say 10^9 such positions that one of them involves the possibility of an underpromotion to a knight (this is excessively pessimistic - underpromotions comprise at least 1 in a 100,000 perceived best moves in high level chess games).

You can repeat this process for multiple promotions to find that it is indeed perfectly reasonable for optimal play to reach positions with large numbers of underpromotions.

Note that each step of this process - working back from a position with odd material balance to an underpromotion - traverses a tiny fraction of the set of legal positions, say N positions (I generously allocated N=10^9 but was well aware it a lot fewer would probably be needed on average), so a position with M underpromotions can reasonably find a path back to a position with no underpromotions by retrogade analysis looking at N * M positions, a very tiny fraction of the whole.

An intuitive error would be to think this number would be N^M, which would become very large for large M.

Working backwards from odd-but-balanced random positions (which on each step includes exponentially more) until you reach a "normal" position is a nice... what to call it... thought experiment I guess.

Elroch

Yes, the strategies involved are quickly calculable, deterministic, and comprehensive.

Elroch
llama51 wrote:
 

Working backwards from odd-but-balanced random positions (which on each step includes exponentially more) until you reach a "normal" position is a nice... what to call it... thought experiment I guess.

Note I edited the start to better explain the range of material balance that is being dealt with - everything that is legally possible.

Note also that the intuitive idea is that typically there will be multiple predecessor positions with optimal play. There will be some positions with no predecessor, but it seems likely that these will not greatly reduce the log of the number of positions reachable by optimal play.

haiaku
MARattigan wrote:

That was apparently not done.

Of 300 openings only 19 were shown to draw. A further 100 validly excluded as transposition of moves, but the remaining 181 dismissed by the assertion that it would be possible to prove them drawn by alpha-beta pruning (without details of how that could lead to a proof) but without actually performing the computations.

I may be reading it wrong, but it is at least difficult to find either further details or an available database of the results computed. No database - no weak solution. Most of the lines still to be computed - no ultra weak solution either.

I guess we have to trust them they actually performed the computations happy.png. They would make a fool of themselves if they were demanded to provide the optimal strategy in reasonable time and the game didn't end in a draw.

MARattigan wrote:

Btw. you have a touching faith in the reliability of computer results obtained over decades on different machines involving large amounts of data.

He! that's a crucial point Schaeffer himself addressed. The solution of the four colour theorem aroused a similar controversy, you know.

haiaku

Define exactly "full" and "semi-strong" solution and "performing" a solution. In this case it's better not to identify the process to obtain the solution with the solution itself (the result of the process), imo.

Elroch

Yes. Optimissed seems not be clear that "weak solution" is an established label for a precisely defined entity. Referring to a "very weak solution" as he does is unhelpful, as this is an undefined term.

Likewise, no-one (probably including him) knows what he means by "semi-strong solution", since it has not been defined.

The "authorities" (researchers with peer-reviewed research) can be very safely assumed to understand such issues better.

In addition, the 50 move rule cannot be ignored. A basic rules tables is different to a tablebase for chess with a 50-move rule - obviously when some positions are drawn in one that would be won in the other, this changes things. The basic rules tablebase has a strict superset of winning positions. The Syzygy tablebase is the first 7 piece tablebase with DTZ - indicating the number of moves before an irreversible move that is not a blunder - this guides a defender to play a path that achieves a 50-move draw by, for example, choosing maximal DTZ move (like an attacker in a winning position avoids interminable wandering by picking a minimum DTM (distance to mate) move.

tygxc

#2212
"the 50 move rule cannot be ignored"
The 50 moves rule can be ignored for all positions with 8 men or more.
It never gets invoked in grandmaster or ICCF games before the table base is reached.
It is just a practical rule to ensure that games and tournaments finish in a reasonable time,
even if some player does not know her 5 basic checkmates.
Whoever disagrees, please do present one grandmaster or ICCF game where the 50 moves rule was or could be invoked before the 7-men endgame table base was reached.

playerafar


The 50 move rule can be addressed as a side issue.
Something like the clocks in chess and somebody's flag is down and do they have mating material.
So in addressing a position - a supercomputer can assign findings:

1)  Forced draw available to one player because there is forced free-of-checkmate play available to compell a 50 move draw.
2)  Such forced play available to Either player.

3) Comments as to whether a player could decline that option of such forced play and play/risk for the win instead.
4) Comments as to whether there's a win available to one player in over 50 moves.  
5) Comments as to whether 'greater than 50' was not addressed in the position because it was quickly found to exceed default computer time allotments -
and therefore referred to another Tablebase computer and Project ! 

To make any comprehensive attempt to define solving -
it seems logical to set out the categories of possible results and findings.

Tempting:  either a position has a checkmate available by force in a known or upper-bounded number of moves - or it does not.

Digital A or B again.  Usually a mistake in so many many situations.

Elroch
tygxc wrote:

#2212
"the 50 move rule cannot be ignored"
The 50 moves rule can be ignored for all positions with 8 men or more.
It never gets invoked in grandmaster or ICCF games before the table base is reached.

You say that like it has some relevance to solving chess! The non-existence of an example in a random sample of say 10^8 positions between imperfect players implies (to you) that there can be no example in 10^46 positions (that's 10^38 times more positions!) between perfect players.

Bad inference, (never mind deductive reasoning, which is absent) as you should be able to see.

There is no basis for confidence that there are not positions with more than 8 men where the 50 move rule is relevant. To me, the most likely candidates would be imbalanced pawnless positions. Eg one side has 3 rooks, the other 5 minor pieces

tygxc

#2216

"Pick a random sample of say 10^8 positions with imperfect players and make inference about 10^46 positions."
++ There are only 10^44 legal positions and the vast majority of these cannot be reached in a reasonable game with > 50% accuracy.
Some of ICCF or even human games may already be ideal games with optimal moves.
The rules of the games are such, that they compel moving pawns or trading pieces to avoid losing. The dynamics stem from the rules. Pawns 'want' to move forward, because the closer to promotion to a queen the more powerful they get. Pieces on central squares are more powerful than pieces on the edge. So 32 pieces fight for 4 central squares. That inevitably leads to trades.

"To me, the most likely candidates would be imbalanced pawnless positions. Eg one side has 3 rooks, the other 5 minor pieces"
++ Such positions cannot happen in a reasonable game with > 50% accuracy.
Nobody promotes a pawn to a 3rd rook or to a 5th minor piece without compelling reason and the only compelling reason is to avoid stalemate.
Both sides needing to avoid stalemate makes no sense at all.

playerafar

that's Instantly Wrong.
Underpromotion can be done to knight check to get a critical tempo -
either to save one's own skin or to get checkmate or even both.
It can also be done to win material.

'Knowing' about something - having 'facts' - 'peer review articles' ...
without understanding basics of logic and math - with such basics flying right by ...  totally missed ...  where most people (including pre-teenagers) do grasp or partially grasp.  And grasp while remaining unskilled and admitting to themselves and others they're unskilled or without much aptitude or inclination.
Or even admitting they don't get the basics - that they don't understand.
Or - becoming skilled because they tried to grasp the basics - successfully - or did so without effort.  

But this is a Very special situation ...
somebody claiming he 'knows more' - while not grasping basics.  
There's a saying:  "the more he learns the less he knows." 
Often happens.
But on this scale?

Elroch
tygxc wrote:

#2216

"Pick a random sample of say 10^8 positions with imperfect players and make inference about 10^46 positions."
++ There are only 10^44 legal positions

I acknowledge this typo.

Thus your sample involves uncertain conclusions based on a sample comprising about 1 of each 10^36 positions. It is virtually worthless for drawing conclusions.

and the vast majority of these cannot be reached in a reasonable game with > 50% accuracy.

You know you are guessing wildly. So do we all.
Some of ICCF or even human games may already be ideal games with optimal moves.

So what? Why would you even think this is relevant?

Try to understand post #2205, which explains why a sizeable fraction (probably > 0.1%) of positions with multiple underpromotions probably occur in (game-theoretic) optimal play  If you don't understand it,  ask. The empirical based intuition should suit your style. You might like to investigate the statistics of the number of legal moves that lead to a given position with drawish evaluation from another with drawish evaluation (Stockfish evaluations near zero are being used as an empirical proxy for the inaccessible tablebase drawing criterion).

MARattigan
tygxc wrote:

#2212
"the 50 move rule cannot be ignored"
The 50 moves rule can be ignored for all positions with 8 men or more.

You obviously missed these positions the first time I posted them for you. Each has 8 men and is mate for White under basic rules but a draw with the 50 move rule in effect.

Black to play, ply count=0
 

White to play, ply count=0

I've posted them for you again, but if you just carry on repeating, " The 50 moves rule can be ignored for all positions with 8 men or more", I shan't try again - I'll just have to assume stem death.


It never gets invoked in grandmaster or ICCF games before the table base is reached.
It is just a practical rule to ensure that games and tournaments finish in a reasonable time,
even if some player does not know her 5 basic checkmates.
Whoever disagrees, please do present one grandmaster or ICCF game where the 50 moves rule was or could be invoked before the 7-men endgame table base was reached.

GMs are quite often out of their depth with only five men on the board and sometimes less. ICCF players invariably give up playing long before the 7 man tablebase. We can agree that the rule is almost irrelevant in practical chess if there are 8 or more pieces.

We can also agree that it's not relevant to your solution, since you have now dropped it from the game you want to solve. It would have been before you dropped it, because you don't show any method of restricting the positions arising in your computation to those known to have occurred during games in your chess club.

 

Elroch
MARattigan wrote:
Elroch wrote:

I think you mean that the paper says checkers has not been strongly solved. Strategies for optimal play from the opening position are complete. This only meant about 10^14 calculations (so certainly not the full 10^20 positions). The 10 piece endgame tablebase for the solution has 39 trillion positions, which is between 10^13 and 10^14 positions.

I was referring to the comments:

(a)

 The fact that the game wasn’t solved for every possible position and then tucked away in a database doesn’t seem to bother him. ”Well, the checkers players would love it, because [then] you’ve got this oracle that can tell them everything—answer every single unanswered question in the game of checkers,” he says. ”But first of all, I don’t have the patience to do it. And second of all, I don’t have the technology to do it.” Even with the best data-compression techniques, Schaeffer says, the amount of storage required to solve all possible positions of checkers would exceed even the capacity of the world’s biggest supercomputers with tens of petabytes (1015) of storage by an order of magnitude. That puts it—at the earliest—at least a decade away.

This refers to a strong solution - "all possible positions".

and

(b)

Schaeffer’s proof solved checkers for 19 different openings, all of which end in draws. There are 300 total tournament openings, but many of these were determined to either be mirrors of other positions or altogether irrelevant to the proof because they lead to positions common to other openings.

Both mirrors and transpositions are fine - they are dealt with.

or from https://www.researchgate.net/publication/231216842_Checkers_Is_Solved 

The checkers proof consisted of solving 19 three-move openings, leading to a determination of the starting position’s value: a draw. Although there are roughly 300 three-move openings, over 100 are duplicates (move transpositions). The rest can be proven [not have been proven] to be irrelevant by an Alpha Beta search.

So that's it: a complete opening strategy leading to the the tablebase - i.e. a weak solution.

Elroch
Optimissed wrote:
Elroch wrote:

Yes. Optimissed seems not be clear that "weak solution" is an established label for a precisely defined entity. Referring to a "very weak solution" as he does is unhelpful, as this is an undefined term.

An entity that can't possibly exist, without first there being a semi-strong solution.

Did you miss the bit about that NOT BEING DEFINED?

Elroch
Optimissed wrote:

Where do I mention a very weak solution, anyway?

#2211

To be precise it was "strategy  ... very weak"

Elroch

The point is that if the definition doesn't exist, a term is meaningless.

Emphasis seems necessary.