12

Is the number of legal chess positions odd or even? Two positions are not the same if they differ in castling rights (i.e. whether K or R have actually moved) or en passant capability (i.e. whether the move can actually be made) or who has the move.

The number of times position has been repeated is not part of the definition of position for obvious reasons; nor is the number of moves since last capture or pawn move.

I don’t have the answer myself. This is hard but doable with a bit of programming I think.

EDIT: The answer so far and the comments are clearly heading along the right lines, although not always correct yet: terrific work. I want to give multiple +1s! I will summarize the key points to help focus the work. Pairing mirrored positions is essential i.e. those which allow triangulation. I term positions which have no mirror image “vampires” :-) Any vampire (except for the starting position) must be immediate offspring of a vampire, so it’s maybe easiest to just focus on them.

Someone touched on castling, which is very important. We can partition the vampires into 16 different clans. The head of each clan is an "initial game array" position (i.e. with 32 pieces on apparently original squares) but with specific castling rights disabled (by some initial dance of rooks and knight taking 2n.0 moves).

In a clan, if a castling right remains, then that implies that the rook's pawn can safely capture off the file, the f-pawn can move forward a single square or capture or (on the kingside) the bishop can be captured, without allowing triangulation. If the right is lost then the rook's pawn can only move forward a single square, and the bishops cannot be captured.

En passant is less important but amazingly there are vampire en passant positions. For example:

r1bqkb1r/2pppppp/8/1pP5/8/8/PPPPP1PP/R1BQKB1R w KQkq b6 0 12

where White retains at least one castling right, Black has at least queenside castling rights and White can capture e.p.

Laska
  • 10,710
  • 4
  • 37
  • 70
  • Shouldn't it be even because to every position there is a mirrored position, mirrored on the axis between the e and d files. (Note that a position cannot be mirror symmetric because of the kings. – user1583209 Mar 30 '20 at 07:31
  • 2
    @user1583209 the mirror image of the initial position isn't exactly legal (or at least the OP should clarify whether it is) - it cannot be reached from the starting position. – Glorfindel Mar 30 '20 at 07:38
  • 1
    @Glorfindel: Good point. Is this (and similar positions where queen/king could not have moved) the only exception? – user1583209 Mar 30 '20 at 07:42
  • Clearly there has to be some matching strategy based on symmetry, but flipping left/right isn’t viable I think, because it’s hard to marshal the exceptional positions. – Laska Mar 30 '20 at 09:26
  • 1
    @bot I think the approach would be to count the positions that cannot be reached legally with the opposite color on the move. For example, you can reach the equivalent of `1. e3` with `1. Nf3 e6 2. Ng1 Bd6 3. Nf3 Be7 4. Ng1 Bf8`, so there are an even number of legal positions from that point. Of white's 20 opening options, only the four knight moves, a3, f3, and h3 have unreachable equivalents with black. I think it could still be very difficult, though. – D Krueger Mar 30 '20 at 11:18
  • @DKrueger Even then, the number will be so high, it probably cannot be counted to in billions of lifetimes. I think that the only way is some kind of mathematical proof, like on a much lower level, why a negative times a negative is a positive, for example. – PhishMaster Mar 30 '20 at 11:23
  • @DKrueger Unfortunately, that includes not just opening positions, but every position which includes a check. – D M Mar 30 '20 at 11:34
  • @bof it’s a good sub-puzzle so I won’t give the answer - it’s only a corner case. Dealing with castling properly is a necessary first step. – Laska Mar 31 '20 at 12:15
  • @bof This is a question I want the answer to because I don’t know it. But I have some partial results and I want you guys to reach the frontier of my thinking. One cute thing I have found is this e.p. idea: someone else might enjoy looking for it. You need to think about the different sets of castling rights which are possible and the implications so that you don’t double count. I am only doing matching based on non-vampire mirroring. I don’t see any other way to be sure that the matching is 1-1. Hope this helps – Laska Mar 31 '20 at 12:49
  • @bof attitude? What attitude? I’m baffled – Laska Mar 31 '20 at 13:59
  • 1
    @Laska There is some strange interaction between castling and parity which I can't quite see how to count effectively yet. Take for instance the position after 1. Nf3 Nf6 2. Ne5 Ng8 3. Ng6 Nf6 4. Nxf8 Ng8. This position cannot be "mirrored" (inversion about horizontal axis + colour inversion) because of the side to move, despite a piece being captured -- you can't reach the "mirror" position while preserving white kingside castling rights. – Remellion Mar 31 '20 at 14:53
  • @Remellion: I think there are 16 independent vampire clans, each for a different combination of castling rights. The head of each clan has the pieces all in game array squares. If a player has one castling right then the only way they can move K and R is by castling. Any other move would duplicate a position in one of the other less entitled clans – Laska Mar 31 '20 at 15:06
  • @bof so is the number of en passant vampires odd or even? :) – Laska Mar 31 '20 at 15:08
  • @bof Yes I think so too. Two possible double pawn moves in every case. If as was suggested we count all the vampires, then we should count all of these little guys separately – Laska Mar 31 '20 at 15:45
  • 1
    If I have to rely on humanly identifying matrices like the one I posted to do a census of the clans, then I wouldn't call that "effective". :P Too easy to miss an idea or wrongly identify a corner case. – Remellion Mar 31 '20 at 16:19
  • Comments are not for extended discussion; this conversation has been [moved to chat](https://chat.stackexchange.com/rooms/106162/discussion-on-question-by-laska-is-the-number-of-legal-chess-positions-odd-or-ev). – Brian Towers Mar 31 '20 at 16:25
  • No warning? And this is intended as communal solving of a difficult unsolved problem. Does that have no space here? Thanks for spoiling – Laska Apr 02 '20 at 10:24

1 Answers1

3

Odd if you count the initial position and Even if not.

Mirrored positions

Almost any position, including checkmates and stalemates can be flipped by switching colors.

Mirroring the chess board horizontally between 4 and 5 rows, you cannot find a position that colors can be switched and produce an illegal position. So for each position there exists a mirrored position, except the start position.

The challenge would be to find a position that cannot be mirrored.

Non Mirrored positions / Corresponding positions

There can exist positions where it cannot be mirrored due to the "turn that cannot be switched". For its this position, there would be a "corresponding position" that also cannot be mirrored.

e.g. 1. Nf3 Nf6 2. Ng1 Nd5 3. Nf3 Nf4 4. Ng1 Nd3+

its corresponding condition is:

  1. Nf3 Nf6 2. Nd4 Ng8 3. Nf5 Nf6 4. Nd6+

Both cannot be mirrored.

Triangulation

Due to Triangulation, all positions after a pawn is pushed can be mirrored. Non mirrored positions can be constructed only with knight moves, moving only knights cannot produce Triangulation.

Start position

The start position, before any moves, the turn cannot be switched so that black makes the first move.

Calculating positions from knight moves

To solve this for sure, we need to calculate the total positions that arise from only knight moves.

bof
  • 3,710
  • 1
  • 18
  • 32
Jannes Botis
  • 275
  • 1
  • 7
  • 6
    1. Nf3 Nf6 2. Ng1 Nd5 3. Nf3 Nf4 4. Ng1 Nd3+ I don't think you can mirror this with Black to move, as there's no way to lose the tempo. – D M Mar 30 '20 at 20:57
  • 3
    Also just 1. Nf3 Nf6. Like the start position, it's its own mirror image. – academic Mar 30 '20 at 22:27
  • 2
    I am confused you have "switching colors", "mirrored horizontally" and "corresponding positions". Could you make the difference more clear, specifically when counting, do you count the color-switched or the mirrored positions? – user1583209 Mar 31 '20 at 08:01
  • Mirrored positions have exactly the same piece positions on the board switched both piece colors and turn. You must have both, due to checks you cannot only switch turn or colors. Corresponding have the turn switched, but different piece layout on the board, actually ALL positions with only knights moved cannot be mirrored, but have a corresponding position that also cannot be mirrored. – Jannes Botis Mar 31 '20 at 08:07
  • 1
    @JannesBotis: Still confused. If I just take your sentence: **"you cannot find a position that colors can be switched and produce an illegal position"** and apply this to the initial position, I end up with all white pawns on the 7th rank and all black pawns on the 2nd. This is clearly illegal because the pawns could not pass each other. Perhaps I misunderstand something.... – user1583209 Mar 31 '20 at 08:11
  • 1
    You have also to "flip/ mirror" the chess board horizontally between 4 and 5 rows. The goal is to produce pairs of positions, so to prove the total is even. – Jannes Botis Mar 31 '20 at 08:18
  • 4
    It's not true that non-mirrored positions can only involve knight moves. You can also push rook pawns a single square, and move the rooks a single square forward or sideways. Since this does not give a rook enough freedom to move more than a single square, no triangulation can happen. – Especially Lime Mar 31 '20 at 09:29
  • 1
    If it really comes down to the knight-move only group, that should be even. The special case is check. There are two checking squares and for both, the non-checking knights have equivalent possibilities. So those are even. All the non-checking positions can be mirrored, with the caveat that that may not change the move. But there are an even number of those as well. – D Krueger Mar 31 '20 at 09:30
  • 2
    Triangulation section is wrong. The moves a3, h3, ...a6, and ...h6 also preserve the parity of the position. – Remellion Mar 31 '20 at 14:41
  • I see no reason why there would be one and exactly one "corresponding position" for each "non-mirrorable position". – Evargalo Apr 19 '22 at 10:04
  • If anything, you haven't shown how to build such a "corresponding position"... – Evargalo May 02 '23 at 07:08