10

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.

enter image description here

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

enter image description here

I can add an additional piece, like a rook.

enter image description here

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)

  • 2
    By "legal" I mean a position where the side to move doesn't have the opponent's king already in check. – Wes Feb 26 '14 at 15:16
  • 1
    I am sure that the fraction of positions in a tablebase that are unreachable is a tiny, tiny fraction of the total number of positions. Just from general combinatorial principles, I would imagine that is far less than a thousandth of all tablebase positions. Omitting these positions is going to have basically no effect on the size of your tablebase. – dfan Feb 26 '14 at 19:05
  • @dfan post this as an answer? – Rauan Sagit Feb 26 '14 at 20:10
  • 7
    Actually "legal" is a fixed expression meaning "reachable". It is commonly used to describe studies and other compositions. No big deal of course, you made it clear enough ... – BlindKungFuMaster Jan 23 '15 at 9:44
  • 1
    Related, may be of interest: mathoverflow.net/questions/138133/… – GloriaVictis Aug 20 '15 at 13:18
7

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.

  • 1
    How about opposite corners with opposite side's pawns? For e.g. Black bishop on h1, white pawn on g2. – Wes Feb 26 '14 at 22:49
  • Good point! I expect that would double the number. (It will still be really really small in comparison to the entire set.) – dfan Feb 26 '14 at 22:53
  • 1
    I'm thinking if there are other possible unreachable positions. Maybe some positions are unreachable because the king cannot get there successfully without being under check. – Wes Feb 26 '14 at 22:57
  • 1
    By the way, I take back my agreement about a Black bishop on h1 and a White pawn on g2 being an unreachable position. You'd have to put a White pawn on h2 as well for it to be unreachable. – dfan Feb 26 '14 at 23:18
  • 2
    Indeed! We got too excited about the trapped-bishop case. Another example: 4/64 * 3/63 + 24/64 * 5/63 + 36/64 * 8/63 = 10.42% of all positions will have adjacent kings. – dfan Feb 27 '14 at 12:42
3

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.

  • This won't end up disallowing any positions, since any position in an endgame tablebase will have so few pieces on the board (especially if there are many pawns) that this constraint will certainly be satisfied. – dfan Feb 27 '14 at 1:46
  • But there are positions with for example white pawns on h3,h2,g2. Those are illegal as well. – BlindKungFuMaster Aug 20 '15 at 11:39
  • 1
    @RosieF I think it's George Jelliss - wonderful guy - hope to meet him one day – Laska Jan 13 at 14:42
  • 1
    @Laska I stand corrected. I beg his pardon. The following corrects and replaces an old comment which I've now deleted: George Peter Jelliss.lists many examples in Chessics 19, p32-3 and Chessics 29, p.159. Some more examples: double check by two units neither of which can discover from the other, where no ep capture can discover both; wBa1 bKb2; wRa1 bKb1 anything a2; wNa1 bKb3 anything c2; check by unmoved pawn. – Rosie F Jan 13 at 16:58
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).

2

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.

2

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.

  • 1
    OP has already clarified what they mean by 'legal' in a comment on the question. – konsolas Dec 27 '19 at 20:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.