It may be easier to directly specify conditions on the position itself, which is probably equivalent to what you propose:Sesse wrote: ↑Sun Dec 20, 2020 12:25 amI wonder what happens if we introduce the following two concessions:It seems to me this reduces the problem from a near-impossible one to merely a difficult one. The former fixes a lot of parity issues and such, mainly related to the openings. The latter makes sure we don't need to go through great contortions to invalidate positions such as “starting position but with the rook on a1 moved to a3” (now possible since the pawn could have moved to a4, the rook moved out and then the pawn back), which are illegal under the strict FIDE definition but irrelevant for almost any kind of engine algorithm.
- We do not care about the full-move and half-move clocks; they just need to be integers in some defined range.
- We assume that pawns were allowed to move backwards (but not to the base rank), up to but not including the last move.
This still leaves some tricky issues about checks; there's the double-pawn-check as mentioned earlier (and similar situations, such as double-bishop-checks), and also some funny issues about X-ray checks: K1qq3k/8/8/8/8/6b1/8/8 (white to move) is legal but K1qq3k/8/8/8/8/7b/8/8 is not!
- restrictions on the numbers of white pieces of each type, and same for black pieces (consistent with these numbers being reachable by captures and promotions);
- no pawns on 1st or 8th rank;
- castling rights consistent with the board position;
- the side to move cannot directly capture the enemy king;
- if the side to move is in check, the situation should be "reachable".
The last condition is indeed tricky, but it will be just a finite list of situations to check.
Why is
[d]K1qq3k/8/8/8/8/7b/8/8 w
not reachable?
[d]K1Rq3k/8/8/8/8/7b/8/2q5 b - - 0 1