Chess Stack Exchange is a question and answer site for serious players and enthusiasts of chess. It only takes a minute to sign up.
Sign up to join this community
A very common model in programming is the Finite State Machine (FSM) (see here for a great worked example.) Is a FSM a good way to model chess? What are the best ways to go about it? What chess features can be put in; what should be left out?
I have no big knowledge of computer science or engineering, or even chess programming, so I was wondering about this question.
Yes, I think so.
You'd have all possible board positions as states (so lots of states, but finite). The starting position as an initial state. Legal moves as links between the states (so the "alphabet" would consist of all possible moves). Positions that end the game like checkmate, stalemate and dead positions as accepting states.
In the end you'd get the set of all possible chess games as the language that is accepted by the machine.
How you'd work this out formally with things like illegal moves, the 50- and 75- move rules, describing a list of legal moves formally et cetera are left as exercises for the reader.
Draw offers, and games ending in other external ways like a mobile phone going off should probably be left out.
Finite state machines can be described as the recognizers of regular languages. You could perhaps identify chess with the set of all possible game records. For example f3e5g4Qh4# (the fool's mate) is one of the shorter strings in this language. Since this language has a finite alphabet and all words have bounded length (with the upper bound somewhere in the vicinity of 35,000 since there is a maximum game length of under 6000 moves (assuming the 50-move draw rule) and most moves take 6 letters to encode)). Thus the language of chess is a finite language, hence it is trivially regular and thus recognized by a FSM.
may the game of chess be considered a finite state machine?
Yes; this is a good insight.
A FSM is an abstract model of computation with the following characteristics:
It is the last feature which makes the machine a finite state machine. That is, if we numbered each individual state that the machine could possibly be in, there would be a largest such number. Maybe larger than the number of atoms in the universe, but still finite.
We can then model a game of chess as an FSM. The start state is the starting board. The inputs are legal moves -- including moves such as "I resign" -- and each move updates the state of the board. Some states are "stop states" -- we call these "white has checkmate", "black is in stalemate", "black resigned", and so on.
Moreover, any game that has these characteristics can be modeled as an FSM; all you need is finite game state and inputs that predictably update game state. For example, if we consider putting a limitation on poker such that the total number of chips available to all players totals less than, say, a hundred trillion -- or any other finite number -- then poker can also be modeled as a FSM. We have a starting state: the number of players, the chip counts of each player and the shuffled deck. We have rules which update the state -- bets and calls and folds and so on -- and we have states which stop the game.
But if we modeled poker as having no limits on the total number of chips available, then technically it would stop being an FSM; if players may have any number of chips then no finite amount of information characterizes every poker game.
It is interesting to think about games that are not FSMs; I already noted that games where there is some unbounded number are not FSMs. Consider a card game where a player could at some point take an action which causes the deck to be shuffled. In this case we have a non-deterministic state transition, and that would make it technically not an FSM... but maybe there is a way around that:
What about dice-based games? Those are random, so it would appear that they are not FSMs, but we can cleverly make them FSMs by making each player's rolls an input, just one that is not chosen by the player. And the same then goes for other randomized game elements such as card shuffles.
Chess is a particularly good candidate to be treated as an FSM because there is no randomness, and indeed, no hidden state at all. Both players know the entire state of the game at all times.
52! post-shuffle states? While shuffling is non-deterministic from the view of a player, it is definitive from the POV of the state machine? I'm asking, sincerely, as I'm not really sure.
In a sense, yes I would say so. There are an incredibly large number of states/positions chess can be in, but this number is finite. And to get from one state to another, some action is taken. If you're in one state, you can choose from multiple actions to reach another state.
It’s very useful for problemists to think of chess as a finite state machine. The state can comprise:
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.
You could possibly associate an FSA with recognition of a valid chess game (the language being recognized by the FSA being the set of all valid chess games) by associating an FSA state with a pair of values: (1) a possible board configuration and (2) a value that specifies the next player who would be moving. (The 2nd value might be option given the color coding of the pieces.) Each of these pairs would only be connected with a transition if there was a valid game move available to join them. A valid game would be a series of legal moves. The definition of this FSA as such would be prohibitively large, I would guess. I'm not sure how it would compare to, say, an FSA for moves on the Rubik's cube, which would require 43 quintillion states in its definition (although there are many possible stating states in that game). A stack machine would be an enormous improvement for modeling a game of chess.
Chess game IS a finite state machine, by definition.
Then again, the number of possible states is rather large and there is an even greater number of strategies that both players can follow.
Spare for some endspiels, these numbers generally exceed the modern computational capabilities, so the game is usually NOT modelled as a FSM.
As you flagged your question with „rules“, i will try an answer.
I do not think that a FSM is an appropriate model. Of course, you have a big but finite number of states. There are advantages and disadvantages of that model, there are better computer scientists than me to explain this. My point: The number of transitions might be infinite.
To make this clear, you have to define „chess“. I hope we will agree that chess is defined by the Laws of Chess by FIDE. Those contain mainly two parts: The Basic Rules of Play (Art. 1 – 5) and Competition Rules (Art. 6 – 12, Appendices, and Guidelines).
To go from the initial position to the position after 1.e4, there are several transitions. 1.Nf3 Nf6 2.Ng1 Ng8 3.e4 is one of them. You see the problem.
According to the Competition Rules, esp. Art 9.6, the number of transitions is limited and finite because after the 5th occuring of a position, the game ends drawn, and FSM is a fine model.
But if you only apply the Basic Rules, then repetition of positions is possible ad infinitum. And for an infinite number of transition, a Finite State Machine can per definitionem be no model.
I stumbled across this and thought an answer from a programmer would be useful here.
While a chess board could be represented as a set of finite states, this would not be practical due to the sheer number of them.
However, the logic of the game contains specific steps - the game client is often implemented using an FSM. Because the actions the player takes have to follow certain rules, it's easy to implement those (and many other turn-based games) using an FSM.
The client sits in a particular state while you plot your move. We could call that "planning".
Then you select a piece, and the client could give a list of moves available to be selected. The "Moving" state.
Once you select a move, the client can animate the move.
Then you switch to "waiting" in which the other client performs the same steps.
Once checkmate occurs or the game cannot continue, we switch to the "scoring" state.
The board itself is definitely stateful, and while technically finite, this is not the same as an FSM, because we aren't writing the states, and the rules of transfer between states, in advance.
Although having pre-coded states for every position of the board is not possible, an AI is capable of mapping many thousands of moves ahead of time and building a large FSM. In this case, it's then using the properties each state has to determine a move. Technically a finite state machine, although not in the same definition.
Yes! Since there are a finite number of states, and you can move between these states based on the chess rules. There is a neat page, which visualizes possible moves in a connected graph, so that is already 90% of what you would do if you'd program a state machine.
An old thread but also an interesting one. I will focus on the question in the title. "Is a Finite State Machine a good way to model chess?" To answer this one must note a very important part of the question: "a good way".
I normally cringe every time i see such a qualifier in a question or affirmation. Not because "Good/Bad" is wrong in itself. It becomes very valid for the ones that are experiencing/practicing/solving a certain problem, but when "Good" comes from outsiders it becomes something extremely dubious.
So to answer that question tldr: It depends.
One can easily argue that most everything can be modelled or seen as a state machine. But is it "good" to do it explicitly for a game of chess?
I will just say that it isn't really a common practice to program chess explicitly as a state machine (ignoring here that in programming the most basic If statement is already the core of any state machine), but this doesn't mean that it won't be wrong somewhere for someone working on something. So as usual when dealing with such broad questions, the answer (avoiding a lengthy boring monography) can only be:
Not a usual practice and nothing exactly wrong with it, it just depends.
