It’s very useful for problemists to think of chess as a finite state machine. The state can comprise:
- what kind of pieces are on each square
- who has the move?
- castling rights
- en passant capability
You really want this to be the scope of state, primarily because it’s in the Laws in Article 9.2 as the basis for defining repetition of position!
There is a subtlety here because while castling rights just depend upon whether K&R have moved (or arguably R has been captured), en passant capability depends on whether the e.p. can be executed. (There might be some pin or check preventing it.) So a look-ahead is needed.
We have been lavish in our supply of states, but we can be more sparing in our definition of the alphabet. We can define a move just by indicating two squares, source and target, and then we can interpret that to give a unique move (including castling and e.p.). Of course in most cases no move exists between the two squares, and other cases, the move is illegal due to check. This is fine according to FSM practice. Conceptually we can consider that each position affords a set of legal moves.
It is natural to allow arrangements of pieces on the board to be states, even those which represent illegal positions. Some positions look normal, but are in fact illegal - fine these are ok. Positions which have zero or one king, or player to move already giving check are easy. However positions where one player has pawns on the first or eighth rank suggest that a pawn might start on other ranks too, and then we would have to track additional state for each pawn to see whether it is entitled to a first move double hop. The starting square may also affect whether it can promote when it reaches the 8th rank. And we also have questions about what happens when a player has multiple kings. But in principle, defining movement in illegal positions is the best approach. The only difference between a legal and an illegal position is whether it can be rooted in the initial Game Array - a trivial enough feature but sometimes very hard to determine.
There are terminals at checkmate and stalemate positions, but to decide whether a position is dead requires looking forward into the future of the game, and so we don’t want to lose that later tree. It doesn’t make deadness any less real to say that it’s emergent.
50/75 move and draw by repetition rules are also surely outwith the state machine. The former might be embedded in the state machine, but the latter can’t be, so might as well just record the sequence of states from the beginning.
In most cases this beginning is the Game Array, but for composed problems the beginning is a later points, and we may need conventions to tell us how to decide the detailed game state and history.
What’s the point of doing all this? One of the issues with chess problems (particularly fairy ones) is that the rules and conventions are not quite clear. To pick a random example: does Dead Position rule have visibility of 50 move & 75 move status? The problem world doesn’t have arbiters to tell us what the FIDE rules are perhaps trying to say. If we just say ah well it doesn’t matter leave up to is individual cases, then we create a fog of uncertainty which stops retrograde analysis from achieving its full potential.
Where expert problemist Guus Rol would now take us is to break down each transition (move) into a journey of micro-phases. This allows for more subtle management of fairy conditions. My own feeling is that this should be grounded in a simpler model as I describe here which is kind of a Base Camp for his later Explorations.
EDIT: Others can confirm whether chess can be represented in a FSM. The unique angle I am trying to take is how should one approach this: what makes sense to embed within the machine and what should be built on top. The real complexity I did not mention is managing multiple possible retro histories which is necessary for many retrograde analysis problems. The only practical way forward for this is state=position in the FIDE sense. This is not a requirement for over the board chess.
There are two main paradigms for retrograde analysis: RS & PRA. Either of them may be a suitable candidate for lattice theory analysis, which has not been done in a systematic way. The best explanation is given here https://www.janko.at/Retros/Glossary/Castling-and-En-passant.htm.
Werner Keym’s article contains some classic and difficult retros.
Not thinking to automate the solution of retro problems, but just to define a language to represent their solution formally would be a great start.
I'm ignoring over-the-board events such as click click, write move, touch move, resignation, draw offer, draw claim etc, to focus on the compositional side. Note there is an interesting race condition possible where two players resign about the same time.