En passant to block checking piece

[Nominom]

Feel free to close this if I'm mistaken or if this is fixed already but here goes:

When the king is in check and an en passant would be able to block the threatening piece the en passant move should be in the list of legal moves. However, this is not the case in Stockfish 12 at least.

Tested with: stockfish_12_win_x64_AVX2

How to reproduce (running in console): Stockfish 12 by the Stockfish developers (see AUTHORS file)

uci

id name Stockfish 12 id author the Stockfish developers (see AUTHORS file)

option name ... ... uciok

isready

readyok

position fen 8/8/8/1k6/3Pp3/8/8/4KQ2 b - d3 0 1 go perft 1

b5a4: 1 b5b4: 1 b5a5: 1 b5c6: 1 b5b6: 1

Nodes searched: 5

1 move is missing (e4d3), which is the en passant.

[ddugovic]

Reproduced on Ubuntu (latest):

position fen 8/8/8/1k6/3Pp3/8/8/4KQ2 b - d3 0 1
d

 +---+---+---+---+---+---+---+---+
 |   |   |   |   |   |   |   |   | 8
 +---+---+---+---+---+---+---+---+
 |   |   |   |   |   |   |   |   | 7
 +---+---+---+---+---+---+---+---+
 |   |   |   |   |   |   |   |   | 6
 +---+---+---+---+---+---+---+---+
 |   | k |   |   |   |   |   |   | 5
 +---+---+---+---+---+---+---+---+
 |   |   |   | P | p |   |   |   | 4
 +---+---+---+---+---+---+---+---+
 |   |   |   |   |   |   |   |   | 3
 +---+---+---+---+---+---+---+---+
 |   |   |   |   |   |   |   |   | 2
 +---+---+---+---+---+---+---+---+
 |   |   |   |   | K | Q |   |   | 1
 +---+---+---+---+---+---+---+---+
   a   b   c   d   e   f   g   h

Fen: 8/8/8/1k6/3Pp3/8/8/4KQ2 b - d3 0 1
Key: E362A1B5AA232196
Checkers: f1
go perft 1
b5a4: 1
b5b4: 1
b5a5: 1
b5c6: 1
b5b6: 1

Nodes searched: 5

[ddugovic]

If I move the king to c5, the en passant move is found. I'm not sure how d3 is a legal en passant square in the other position (what was Black's legal move prior to White playing d2-d4?):

position fen 8/8/8/2k5/3Pp3/8/8/4KQ2 b - d3 0 1
d

 +---+---+---+---+---+---+---+---+
 |   |   |   |   |   |   |   |   | 8
 +---+---+---+---+---+---+---+---+
 |   |   |   |   |   |   |   |   | 7
 +---+---+---+---+---+---+---+---+
 |   |   |   |   |   |   |   |   | 6
 +---+---+---+---+---+---+---+---+
 |   |   | k |   |   |   |   |   | 5
 +---+---+---+---+---+---+---+---+
 |   |   |   | P | p |   |   |   | 4
 +---+---+---+---+---+---+---+---+
 |   |   |   |   |   |   |   |   | 3
 +---+---+---+---+---+---+---+---+
 |   |   |   |   |   |   |   |   | 2
 +---+---+---+---+---+---+---+---+
 |   |   |   |   | K | Q |   |   | 1
 +---+---+---+---+---+---+---+---+
   a   b   c   d   e   f   g   h

Fen: 8/8/8/2k5/3Pp3/8/8/4KQ2 b - d3 0 1
Key: 980790AE076A6EFE
Checkers: d4
go perft 1
c5b4: 1
e4d3: 1
c5d4: 1
c5d6: 1
c5d5: 1
c5b6: 1
c5c6: 1

Nodes searched: 7

[Nominom]

Now that I think about it there doesn't seem to be a way to get to that position via normal play.

The position was just created with fen-editing to test my own move generator. Maybe this is a non-issue then.

[vondele]

interesting. I would put this in the category of illegal fen, however.

[vdbergh]

It's a garden of Eden... https://en.wikipedia.org/wiki/Garden_of_Eden_(cellular_automaton). Garden of Edens are not generally regarded as illegal configurations (and in fact they are considered rather interesting). But of course this is only a matter of convention. So there is no true or false answer.

If I were to define "legal" it would be:

(1) Castling rights not contradicted by king/rook positions. (2) Ep rights not contradicted by pawn positions, and the ep square should be free. (3) No pawns on the first or eight rank. (4) If a side is in check then it is also the side to move.

This definition has the advantage that it is very easy to understand (no strange corner cases - I think -).

[ddobbelaere]

@vdbergh Interesting thoughts, and arguably a more logical and less restrictive definition of the concept "illegal". Maybe supplement it with:

(5) If an ep square is present, the number of halfmoves since the last capture or pawn advance must be zero.

If http://wbec-ridderkerk.nl/html/UCIProtocol.html represents the UCI protocol description, the formulation of position fen implicitly assumes that the fen originates from an actual chess game. Note that Stockfish accepts more fen positions as it also supports Chess960.

A fen "that represents a position that is not reachable by a finite sequence of legal moves from a Chess960 starting position" (or "unreachable fen" for short) might be more apt here, although it is of course very much a matter of convention. Naturally, (vdbergh) illegal fens are unreachable but not necessarily the other way around.

[ddobbelaere]

Fun question: is reachability of fens (defined above) decidable?

EDIT: never mind, it is trivially decidable as there only a finite number of reachable positions (that can be tree-like enumerated).

[vdbergh]

I would guess it is not polynomial in the board size.

[ddobbelaere]

Maybe it is polynomial in board size though, e.g. if there would exist a finite set of necessary and sufficient conditions that can be checked in polynomial time (e.g. pawns should satisfy "whatever", no more queens/other pieces than allowed by promotions, etc...).

EDIT: the assumption that such a set exists seems very naive, my apologies.

[syzygy1]

The position can only be reached by white playing d2d4 from a position where black is in check, so from an illegal position. I see no good reason to slow down the move generator just to be able to generate all "legal moves" in a position that itself is illegal. (What are the legal moves in an illegal position anyway?)

[vdbergh]

@syzygy1 What is a "legal position" is just a matter of definition. Defining it as being reachable from the starting position seems pedantic to me. One obvious reason is that this condition is very hard to check. Another one is that it artificially excludes interesting positions which all engines are perfectly capable of playing otherwise.

IMHO one should make simple rules to define a "legal position" which are sufficient to make normal engine search work.

The position by the OP is an interesting borderline case because of the micro optimization in the move generator. But I wouldn't be surprised if that could be simplified away.

[ddobbelaere]

I agree with @vdbergh that we should define the current requirements on a position that is valid input for SF, but I also agree with @syzygy1 that we should not sacrifice speed or optimizations for it.

Let a legal position be the least restrictive interpretation of a legal chess position, e.g. as defined above by @vdbergh. Let a reachable position be a position that can be reached from a Chess960 starting position. Let a "SF legal" be a position that is "valid input" for SF.

Then the following set relations hold: reachable ⊂ SF legal ⊂ legal.

It is very hard to check if a given position is reachable (to this day, nobody knows how to do it efficiently). It is very easy to check if a position is legal or SF legal.

---

Right now the following course of events represents about one quarter of the opened issues:

A: Hi there! There is a huge bug in SF, look at how it crashes/generates illegal moves/... if I feed it this position. B: But the position you give is illegal. A: Illegal? What do you mean? C: Actually B means that the position is not reachable from the starting position. A: Oh, ok. But I got the position from the internet/a friend/my cat, how can I check fast if it is reachable? C: In general you can't. Sorry, can't help you anymore, goodbye! D: Wait, the situation is more complicated! There are actually positions that are not reachable but are still accepted by SF. Use at your own risk though. A: Euhm...

What should happen IMHO:

A: Hi there! There is a huge bug in SF, look at how it crashes/generates illegal moves/... if I feed it this position. B: A position is considered legal by SF if the following conditions are satisfied: ... This is to ensure it is both a legal chess position (e.g. only one king per side), but also allow some engine optimizations. A: Ok, that makes sense, thanks!

[syzygy1]

It would be nice to have a definition of "UCI legal" positions, which is missing from the UCI spec. It should include all FIDE legal positions and not include any FIDE illegal positions that could break engine optimisations. Giving such a definition is not a trivial exercise.

[syzygy1]

But as far as the "one quarter of opened issues" is concerned (I don't think it is that many), in my view it is perfectly reasonable to expect bug reports to deal with legal positions only and to close those issues that report problems with illegal positions.

[ddobbelaere]

@syzygy1 The term "FIDE legal position" is ill-defined (at least I don't find it in https://www.fide.com/FIDE/handbook/LawsOfChess.pdf). Do you mean "legal" in vdbergh sense or reachable from a Chess960 starting position?

At the moment, IMHO, it would already be an achievement to just list the current internal assumptions present in SF dev that are reflected in conditions on "valid input". This list (notion of "SF legal") is of course not set in stone and might change over time, but at least is clear to the user then (no more impossible to check "reachable position" nonsense that doesn't even cover the whole spectrum of allowed positions), and also to the developers ("if we add/drop this optimization, we restrict/broaden our set of allowed input positions").

Of course, defining a more general notion of "UCI legal" is more ambitious but has to be discussed with other engine developers (do we allow 12 or more queens per side, etc...).

[syzygy1]

Chess960 is a different game, played with the engine set to a different mode. There is no need to consider Chess960 here (everything valid for normal chess applies mutatis mutandis to Chess960).

The concept of a "legal position" is defined in the handbook of chess composition of the WFCC. It seems thr WFCC used to be part of FIDE but is now independent (but cooperating with FIDE).

So legal position means a position reachable by legal moves from the starting position. The concept is implicit in the FIDE rules, which require a game to start from the starting position.

[ddobbelaere]

Hmm, I see, thanks for clarifications.

How about extending (1)-(5) with

(6) If the side to move is in check, the position has to have at least one predecessor.

One open question is if that predecessor should satisfy (1)-(5) (I think that is enough) or the full (1)-(6).

[vdbergh]

Well one has to look at the domain.

I can see why in a chess composition it makes sense to impose that positions must be reachable from the starting position. In that way one can make problems whose solution depends on subtle retrograde analysis to determine castling and ep rights.

But this situation is very different from computer chess. In particular castling and ep rights are already encoded in the fen. Clearly it would make no sense to require the GUI to attempt to do the kind of retrograde analysis typically associated with solving compositions, to certify the validity of these rights.

[syzygy1]

Hmm, I see, thanks for clarifications.

How about extending (1)-(5) with

(6) If the side to move is in check, the position has to have at least one predecessor.

One open question is if that predecessor should satisfy (1)-(5) (I think that is enough) or the full (1)-(6).

I'm wondering about (2), but if the position has ep rights and the side to move is not in check, (2) is probably sufficient to ensure that the double pawn push was legal.

I would replace your (5) with "number of pieces of any color and type is consistent with the starting position" (i.e. "reachable" by captures and promotions). I don't think the number of half moves is of much concern (unless it is negative or >= 100).

Then I suspect that the predecessor of (6) only has to satisfy (1)-(5), and perhaps only (4). It would be weird to accept a position with a pawn on e1 as the predecessor of a position with a white pawn on e2 and a black king on f3, but e1e2 is probably not going to be generated as one of the "unmoves" when looking for a predecessor.

[ddobbelaere]

Your (5) seems indeed desirable for a proposed easily-checked definition of "UCI legal", as some engines might keep piece lists with limited number of slots (didn't we do that in the past also?).

My (5) is indeed pedantic and obvious, let's ignore it.

However, I think it that your (5) can be dropped for a characterization of "SF (dev) legal" that captures as much positions that are currently allowed inputs (apart from the obvious "exactly one king per color").

[syzygy1]

Stockfish had piece lists until very recently. They allowed for 16 pieces of the same type and color, so probably there were problems only in extreme cases.

There can still be problems with too many pieces, since the NNUE evaluation assumes there are at most 30 non-king pieces (both colors): https://github.com/official-stockfish/Stockfish/blob/b06ef36ae5f23fa2d4188c9fe6d95c4f551ab035/src/nnue/features/half_kp.h#L43-L44 There may be more places where assumptions are made.

Btw, the tablebases only need (4) (but they don't store positions with castling rights or ep rights, and 3-7 piece TBs by definition don't cover positions that violate (5)). That makes the following position interesting: https://syzygy-tables.info/?fen=4r3/8/6b1/1k6/3Pp3/8/2K1Q3/8_b_-_d3_0_1 TBs say black wins, but SF won't find the win :)

[BM123499]

Correct me if I'm wrong. But when you double push a pawn and make a check, you either check with the pawn or with a discovery attack. So why don't you check if it's a discovery attack instead of checking if the pawn is the checking piece, by doing if (Type == EVASIONS && (target & (pos.ep_square() + Up))) instead of if (Type == EVASIONS && !(target & (pos.ep_square() - Up)))?