How many legal but unreachable positions exist?

Question

Consider this legal chess position which can never be reached from the normal starting position.

    [FEN "6kb/6p1/6K1/8/8/8/8/8 w - - 0 1"]

The Black bishop is placed on h8, but with the Black pawn on g7, there is no way the bishop could have actually reached h8. How many such positions exist in chess which are legal but unreachable? Is there any research on reachable/non-reachable positions?

I found that endgame tablebases don't necessarily take this into consideration, but if the number of non-reachable positions is significantly large, it might possibly help minimize the size of endgame tablebases.

Here's a screenshot from the online Nalimov tablebases.

Now, in this unreachable position, I can add another piece like a knight on almost every square.

I can add an additional piece, like a rook.

This can go on and on and I can keep adding more pieces, but all those positions would be unreachable. We thus end up storing unnecessary positions in the tablebase and increasing its size.

Of course, it's a good thing for tablebases to have these positions if we want to use them for chess variants like Chess960, but they are not necessary for the standard version of chess. It would be quite interesting to know how many such unreachable positions exist.

(Addition of more relevant tags suggested)

Answer 1

The fraction of all six-man positions that are unreachable from the starting position is very, very small. Removing them would have a tiny effect on the size of a six-man database.

Here is an example of how rare these positions are. First of all, we can't get into one of these unreachable positions without a bishop and a pawn, so we already have a small subset of the number of total six-man positions. But okay, say that one side is lucky enough to have one pawn, one bishop, and a king. The bishop will have to be in one of its own corners (not the far corners!) and the pawn will have to be diagonally adjacent to it. So only 2 out of the 64 bishop positions could lead to a trapped bishop, and out of those, the pawn has to be in the one spot of its possible 48 positions that would trap the bishop. So even if you have one pawn and one bishop, which is pretty unlikely, the chances of randomly getting an unreachable position are only (2/64) * (1/48) = 1 in 1536.

Let's do one bishop, two pawns, and a king just for fun. If the bishop is in its own corner (2/64 chance), the chance of getting one of the two pawns in the diagonally adjacent square is 2/48 (2 of the 48 squares in ranks 2 through 7 have pawns in them). If the bishop is one of the other spots on the first rank (4/64 chance - c1 and f1 are definitely OK!), both pawns have to be in exactly the right spot (1/48 * 1/47) chance. When I do the math I get a chance of around 1.33% for getting an unreachable position even if you start with this very unlikely great combination of material for generating unreachable positions.

My conclusion, as first predicted in my comment above and now backed up by some math, is that these unreachable positions are an extremely small subset of the set of all six-man positions.

Answer 2

also consider the number of pawns stacked in a file vs the number of captured enemy pieces. For example, if two pawns are on the c-file, one enemy piece must have been captured; and if 6 pawns are on the a- or h-file, 15 enemy pieces (i.e. all but the king) must have been captured: the nearest knight's pawn must have made one capture, the bishop's pawn must have made two captures and so on.

Answer 3

As others have said, the number of those unreachable positions is rather small. There are other important things to consider, though: it seems rather difficult to determine which positions are unreachable and which are not for all but the trivial cases. And then, even if you know which positions are unreachable, that information can hardly be used to minimise the database size, as you cannot just remove some "random" positions. The positions are not stored as such, but just the values. Hence, you would need to construct an indexing function that skips just those positions, which seems impossible. (If not removed, it might bring tiny tiny gains during compression if you treat those positions as "don't cares", but this is probably negligible, and dangerous when looking at the position and not knowing it's unreachable).

As a side note, the Nalimov databases don't include illegal positions with unblockable checks, i.e. wKe1 bQe2 BTM, but they do include illegal positions with the slider away more than one square. These positions take up a significant part of the database, but it's rather difficult to exclude them in the indexing.

As far as "legal but unreachable" goes, keep in mind that even if unreachable, the position might become legal in a real game (after a non-disputed illegal move).

Answer 4

I agree that the number is very low. Namely 0.

A legal position is defined as a position reachable by regular moves. Your diagrams do not show legal positions.

Answer 5

The question remains a bit vague, but the suggestion in a couple of answers was that the most arrangements of pieces would be "reachable" (by which they mean in FIDE laws terms "legal" i.e. that can be arrived at by a sequence of legal moves). The supporting argument was the behaviour with 6 pieces. There just isn't much opportunity for illegality with 6 pieces, but the number of arrangements increases exponentially as the number of pieces on the board increases, so the 6-piece behaviour is not statistically relevant.

More importantly, 6-piece behaviour is also highly untypical. The mathoverflow.net version of the question, which @GloriaVictis sensibly pointed us to in a comment, has a much more rigorous question and answers, and shows by detailed analysis that almost all arrangements of chess pieces are illegal.

What they do seem to miss even in mathoverflow is that the notion of position includes who has the move and also castling and en passant capability, and that increases both the number of positions and the proportion which are illegal.