Chess will never be solved, here's why

So many many points to disagree with there !
Maybe a week's worth in that post #1587.
Of course its an efficiency issue !
There's often more than one 'optimal move'  (yes I know - you didn't claim there wasn't)
We could also have a big argument about things we agree on !
Arguing in a civil manner though - whether misplaced or on target -
is part of good discussion.   

We can 'take care' of many of the already illegal positions instantly - with a simple expression like 13∧64.  
You don't need a computer to eliminate a gigantic fraction of those.
A number bigger than total atoms in our observable local big bang clusters of galaxies - 
No need - to invest any computer time in most of those !  
None whatsoever.  

To really go at the task though - slicing pieces of computer cheese off it isn't going to work.
To get this - you've got to break its back.
And then - you bring on the computers!

Is there a way - in theory - to do that?
There are various 'candidate ways'. 
Some of them mentioned in the forum already.

How many positions could be arbitrated as:
'well there's lots of ways somebody could make a mistake here - but we'll count these as draws and therefore solved because play would have to be too weak for somebody to have a win' 
 
Prime example:  King and two knights versus King.  
Its considered a book draw even though you can set up a checkmate move with that.
Its considered Solved.  

But what about King and two knights versus King and two knights?
So many possibilities. 
So many ways for a knight or two to take away a flight square or more from its King.
So many ways for both of its knights to provide a move that deprives that King of stalemate.  

If a good way could be devised to pre-arbitrate such positions - that could be the beginning of 'breaking the back' of the task.  

Too inane:  "Well all positions of 2 knights versus two knights are draws except when they're not"
If that could be improved on lots - could be the light at the back end of the tunnel-maze that nobody can venture very far into at the front end from where it becomes progessively darker.  'Stygian' blackness ...
Just not enough seconds in a lifetime ...

If you want to remove a significant fraction of ~10^40 positions, you are not going to be doing it by hand!

The guys who made the Syzygy tablebase of all 7-piece positions managed to compress the information by a remarkable factor compared to the Lomonosov tablebase serving the same purpose. It takes only 18 Tb compared to 140 Tb.  But they still weren't concerned that it contained positions like the one I referred to which can never be reached in a game (due to the files the pawns are on. As this is the most efficient implementation in existence and certainly does not omit relevant positions, I look to them for guidance.

Interestingly, they calculated the 8-piece tablebase would require the best part of $1 million worth of hardware. That work is currently in progress, in a piecemeal fashion.

If you don't believe my algorithm, here is the algorithm used to generate the state of the art tablebase, Syzygy, described at chessprogramming.org

You will see it is basically the same as the one I found from first principles and described above.

"If you want to remove a significant fraction of ~10^40 positions, you are not going to be doing it by hand!"
I didn't say you would.  My turn for that now.
You've got to break the back of the problem.
By mind - not hand.
Algorithms are written for computers by humans.  Yes - computers nowadays can probably write some of their own programming.
But the process of improvements starts with humanity nonetheless.
Its not like Skynet and Terminator judgement day ...
(and would I have to say in advance every single time -  "yes I'll say it in advance that you didn't say that.  I'm saying it."   
Somehow that isn't 'grasped'.

Szygy is better than Lomonosov ?
Okay.  Does the Szygy take castling and en passant into consideration?
If not - its starting to cut corners.   Again.
8 piece could be many many factors more difficult than 7 piece.
Have they got an idea how long that's going to take?
And then the nine piece after it ?
If they're only generating their 8 piece from 7 piece 'reverse legal captures' that's starting to look like an invalid jump.
Would they do that?   I don't think so.
But it still should be better verbally presented as to how they're doing that 8 piece generation - as opposed to algorithms for 'solving' it.
I say again - 'reverse legal capture' and 'retrograde analysis' aren't comprehensive.  Leaves out too much.
There ought to be a better way to describe a valid process - in like one sentence - that's much more valid and better than those.
But he does make some effort.  Got to give him credit for that.
Regarding every time @Elroch said 'correct' - maybe some of those could be regarded as 'concessions' ?    To be further noted/pursued ?

There was no comment at all about the two knights versus two knights.
Its a paradox that adding more material to the drawing side might actually make that side a losing side.
But its a valid paradox.  The kind of thing where humans have to help the computers.  Early on.  Before the computers continue crunching away.
Got to have steering to go with those 'engines'.
Whether you call it 'by hand' or not.

Regarding e4 e5 Ba6 bxa ...  that @tygxc has mentioned I believe
yes it looks very silly.  But is it 'solved'?
According to Lasker the plus of a rook is enough to win 'ceteris paribus'.
A rook.  Not of a minor piece.  

Let's think about it...

The number of chess positions isn't infinite:

* There are up to 32 pieces in a chess board;

* The board has 64 squares;

* 2 pieces cannot be at the same square.

To calculate the maximum number of possibilities (with all the pieces on the board), you can do like that:

* The first piece can occupy 64 squares;

* The second piece can occupy 63 squares (it cannot be on the first piece);

* The third piece can occupy 62 squares (it cannot be on the other 2 pieces);

* And so on...

Now, the result is:

64*63*62*61*60*59*(...)*34*33*32

By simplifying, we have this:

(64!)/(31!)

(The symbol "!" means every positive number lower than itself multiplied by itself, so 4! means 4*3*2*1=24).

Now, if you want to calculate with only some pieces on the board, you can do this:

The quantity of "(64-x)" represents the number of pieces on the board. For example, you can do (64-0)*(64-1) for a board with two pieces and (64-0)*(64-1)*(64-2) for a board with two pieces.

The total amount of maximum number of possibilities is

(64-0)*(64-1)+(64-0)*(64-1)*(64-2)+(64-0)*(64-1)*(64-2)*(64-3)+(...)+(64-0)*(64-1)*(64-2)*(64-3)*(...)*(64-30)*(64-31)*(64-32).

Lomonosov (DTM) will fail to win this mate in 84 against Syzygy (DTZ50) in the competition rules game.

On the other hand, in the basic rules game Syzygy would need more than 84 moves (depending on the best moves chosen) to beat Lomonosov, whereas Lomonosov would beat Syzygy in less than 73 moves (again depending on the best moves chosen).

You can see the difference in this mate downloaded from the syygy-tables.info site - I've inserted a possible Lomonosov (DTM) variation.

So before you make a comparison you need to decide which game you're playing. Basic rules chess and competition rules chess are both called "chess", but they're different games.

Unfortunately it is more complicated than that for several reasons.

Firstly, there is a vast range of different material. Eg, even for 3 pieces (the smallest non-trivial tablebase) there are 10 different sets of material. These can be reduced to 5 by symmetry - KkP, KkQ, KkR, KkB, KkN and KkP.  For more pieces the variety of material is a lot greater. This is not actually true for the 32-piece tablebase, because you can't queen a pawn without a capture taking place, but the 31-piece tablebase has a large set of possible material. First there are 5 for each piece black might have had captured. Then if you assume there has been one capture and one promotion, assume by symmetry that it is black who has lost a piece. This means there are 5 types of piece that could have been captured and then 8 types of piece to promote to, which I make 45 types of set of material.

It gets worse.

Then there is a simplification when there is more than one piece of a type. Eg if there are 8 white pawns, a crude calculation would say they are on any set of squares from the 2nd to the 7th ranks, so that would be (48 * 47 * ... * 41) / (8 * 7 * ... * 1)   positions  (called "48 choose 8" in maths).

You are right, as I verify by trying one where a side has castling rights but doesn't have to lose them on the first move. Here we go:

https://syzygy-tables.info/?fen=4k3/8/8/8/8/8/8/4KB1R_w_K_-_0_1

Answer: it just does a one ply calculation and tells you what it knows about the positions after every legal move. Either the move loses castling rights, when it fully understands it or it doesn't, when it knows nothing.

So it really only deals fully with positions with castling rights where you have to give them up on the first move. Not that surprising - others would really need to be generated as a tablebase as they have indefinite depth with castling rights.

OK. Two knights v two knights not too deep. Max 7 move forced mate.

Mind you if you're using USCF competition rules and get int a losing 7 mover it's probably worth timing out. If the arbiter can't see the mate you get a draw.

@Elroch

And I think the same applies to en passant.

Quite a lot of work to do before we can say 7 man chess of either flavour is (weakly) solved - but give me 3 Summit machines and a few good looking assistants and I think I could sort it in a few years (for my usual quite reasonable contract rate).

#1577
"even weakly solving chess requires 10^40+ positions"
++ No, not at all. The 10^44 is way too high for the purpose of assessing the feasibility of solving chess, as all 543 legal positions sampled by Tromp contain mutiple excess underpromotions, which never occur in a reasonable game with reasonable moves and thus not in an ideal game with optimal moves.
The 10^37 of Gourion is a better estimate. It is too low as it excludes excess promotions like e.g. 4 queens, which can occur in a reasonable game with reasonable moves and thus might occur in an  ideal game with optimal moves. It is also too high, as inspection of randomly sampled positions without any excess promotions shows they cannot occur in a reasonable game with reasonable moves and thus not in an ideal game with optimal moves. Tromp conjectured only 1 in 10^6 can occur in a reasonable game with reasonable moves. Hence 10^36 is a good and conservative estimate: add positions to include 4 queens, subtract positions that cannot occur in a reasonable game with reasonable moves.
Those 10^36 positions would need to be investigated for strongly solving chess i.e. a 32-men table base. Neither the time nor the storage is feasible.
Weakly solving chess requires visiting less positions than stronly solving chess. Checkers was solved using only the square root of the number of positions. Losing chess was solved using only the 4th root of the number of positions. Thus it is plausible that for weakly solving chess also about the 4th root needs visiting, that is 10^18 positions.
The number of openings can be reduced by another factor of 10.

"Saying that excess promotions and "nonsensical" positions can be discarded is a shortcut that will not stand up to said scrutiny"
++ We are looking for an ideal game with optimal moves, so that should at least be a reasonable game with reasonable moves.

"evaluating all those positions to determine if they should be "included" for deeper/full evaluation also requires timeframes with copious orders of magnitudes."
++ No, it is not necessary to determine if these positions should be included for deeper/full analysis: in the course of the analysis they do not occur: they are not reached. These require no effort.

#1594
"According to Lasker the plus of a rook is enough to win 'ceteris paribus'."
No, 1 pawn is enough to win.
"The winning of a pawn among good players of even strength often means the winning of the game." - Capablanca

According to Elroch, there are many positions where one side has sacrificed a rook and is winning. There are far more positions where one side has sacrificed a pawn and is winning. The quoted statements are of course untenable without vague assumptions that there are not positional and tactical factors that are adequate compensation.

Also, with a one pawn advantage the average score tends is probably less than 70% (based on examples). This is difficult to be precise about, because the actual positions that are reached are a sample skewed by the choices of the players. Eg sound gambits are more commonly played than bad ones. Eg the position after 1. e4 e5 2. f4 exf4 -  a true gambit - scores 49% for white in recent master praxis.

Not actually the same purpose.

The Lomonosov (DTM) tablebases provide a strong and (DTM) efficient solution of 7 man basic rules chess (with caveats re castling and also - I think - en passant and assuming FIDE would fix their specification).

The Syzygy (near enough DTZ50) tablebases provide a strong, but not (DTM) efficient solution of 7 man basic rules chess and also a weak (again not DTM efficient) solution of 7 man competition rules chess (with the same caveats as the Lomonosov tablebases). The Syzygy tablebases are efficient in some sense, but a much weaker sense than the Lomonosov tables (see last example in post #1597 above).

You say "But they still weren't concerned that it contained positions like the one I referred to which can never be reached in a game ...".

The fact is the more illegal positions you identify and omit in tablebase generation, the faster will be the generation, but the less general will be the result. E.g. both Nalimov/Lomonosov and Syzygy tablebases will contain the following illegal position.

If they didn't, the tablebases would be useless for chess 960 (FRC).

The fact is that almost all illegal positions (as defined by FIDE as opposed to the natural interpretation) are "accidental" consequences of arts. 2.1-2.3 which define the initial board size, starting material, ownership of the starting material and layout of the material on the board. (I say "almost all" because some of the remaining laws become difficult to interpret unless it is assumed that the pieces occupy unique squares. For example, would a piece placed at the centre of the board count as an "intervening piece" for ranks files and diagonals through the four centre squares for the purposes of defining the moves of the pieces?)

So :

Any position with a diagram on, for example, a 6x4 board is illegal, because the initial board size is 8x8 and none of the defined legal moves change the board size.

Any position with a diagram in which more than one piece occupies some square is illegal because no more than one piece occupies any square in the initial position and art. 3 prohibits moving a piece to an occupied square without removing the piece that is occupying it.

Any position with a diagram that doesn't include exactly one king of each colour is illegal because the diagram in the starting position contains exactly one king of each colour and the remaining rules prohibit either the removal or addition of a king to the board.

etc. etc.

About the only illegal positions that allow for reasonable interpretation of the laws and would be illegal irrespective of arts 2.1-2.3 are positions like

Here Black's last move must have been d6-d4 (starting position for the pawn must have been d6) but the move is illegal because there's a knight in the way, so the position is illegal.

This is not to say that positions with, for example, one king on the board may not legitimately occur during games. The FIDE laws do not lay down any specification of the path a piece must take between touching it with the intent to move and releasing it on a square as a legal move or part of a legal move - it is permissible for it to leave the board between these events. But these positions, while legitimate, are not "legal" in conformance with FIDE's definition of "legal".

One possible purpose of tablebases is to allow for more reliable guesses about positions with a greater number of men. Such guesses obviously become not very reliable at all if extended too far, e.g. from 7 men to the starting position, but ignoring some of the "accidental" aspects of 2.1-2.3 might be more useful, if less economic, in building tablebases.

At the moment the legality constraints in different tablebases are different. Syzygy for example rules out triple checks, while Nalimov doesn't. That complicates statistics you might want to consider that use both tablebases. Preferable, from this point of view, would be to formulate a set of legality criteria, mark the positions illegal with the applicable criteria, and continue with generation.

I did once work out by hand the draw percentage for legal positions in KQQK (might have been KQQQK - it's some time ago). It differed from the ICGA published stats in the first significant figure. No error margins are shown for the stats which refer neither to legal nor total positions, but somewhere in between. Obviously not an ideal situation.