7

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)

  • 1
    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
  • I didn't want to make it an answer unless I actually provided a mathematical demonstration or something rather than just saying "I'm sure this is true". Nevertheless, I am sure it is true :) – dfan Feb 26 '14 at 20:19
  • 3
    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
6

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
  • 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
  • 1
    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
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.

  • 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
    Graham 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 May 27 '16 at 14:41
1

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).

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.