7

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.

  • 19
    Why are you asking a question if you don't understand what it means? Context of what you think the term means, and why you think it might apply to chess, could help to answer. – Grade 'Eh' Bacon Dec 16 '19 at 14:12
  • 4
    I can’t answer as a scientist, but I can understand what others are writing about a finite state machine. Do you have complete understanding and knowledge of everything you talk or ask about? From my experience, knowledge improves in this way, by asking questions we aren’t 100% sure about, and then gradually, from insightful answers, getting a better picture of the whole idea or concept. – A. N. Other Dec 16 '19 at 14:18
  • 4
    @Grade'Eh'Bacon I relate to your desire to ask that, but I have found that it is more constructive if we just leave off remarks like "Why are you asking a question if you don't understand what it means?", and just go directly to saying what you said in your second sentence. – mtraceur Dec 16 '19 at 18:47
  • 4
    @Grade'Eh'Bacon Why do you care? The guy can ask whatever question he wants, leave him alone. – user428517 Dec 16 '19 at 21:11
  • 4
    Pedantically, I'm not sure it makes sense to ask "Is X a finite state machine." It is like asking, "is my bank account a function?" No, I guess not. The amount of money in it could be modeled using a function, though. Similarly, probably some aspects of chess could be modeled using a FSM, but the game itself is a game, not a mathematical construct. – Zwuwdz Dec 16 '19 at 22:02

10 Answers 10

21

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.

  • 4
    I don't think you need to leave out draw offers and other external factors ending the game. Add DrawAccepted and a BoardState+DrawOffered state for each board state. Plus BlackLoss and WhiteLoss states for other external factors (such as resignation) causing one side to lose. Every state has a link to BlackLoss, WhiteLoss, and its BoardState+DrawOffered, and BoardState+DrawOffered has a link to BoardState and to DrawAccepted. – CPomerantz Dec 16 '19 at 17:55
  • 19
    There's only a finite number of possible board states, which by definition makes it a FSM. However that's like arguing that all computers are FSMs because memory is always finite; while true, it's not a useful abstraction. if you want a FSM that doesn't contain an impossibly large number of nodes, the answer is probably "no" due to the complexity of the game rules. – BlueRaja - Danny Pflughoeft Dec 16 '19 at 19:39
  • 1
    Saying that a machine can recognize a valid sequence of moves or a valid board state is not the same thing as saying that the game itself is a machine. – Solomon Slow Dec 16 '19 at 22:54
  • @SolomonSlow yes, but the original poster admits to using the terms loosely. – Jasen Dec 17 '19 at 9:25
  • 2
    Board positions are not enough. You need info about whether King and Rooks have moved, the last move for en passant, and, for the sake of claiming a draw after threefold repetition of a position, you need in general all positions since the last pawn move. – M.Herzkamp Dec 18 '19 at 11:19
19

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.

11

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:

  • The machine begins in a known "start state"
  • The machine accepts a sequence of inputs
  • Each input is interpreted in the context of the current state
  • Each input causes an update to the current state; the update depends only on the current game state and the input.
  • Some states are "stop states", which cause the machine to stop.
  • There is a strict upper bound on the size of the state and the number of possible inputs.

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.

  • 1
    This is probably drifting off-topic, but for the shuffling of a deck, could you technically handle that with 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. – Dancrumb Dec 17 '19 at 2:31
  • @Dancrumb sounds exactly like converting a non-deterministic finite automaton to the equivalent deterministic one, complete with possible exponential explosion of states. NFAs and DFAs have the same computational power though (they both recognize only regular languages). – D. Ben Knoble Dec 18 '19 at 4:41
8

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.

8

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.

  • 1
    Draw with repetition can be embedded in a FSM because there are only finitely many possible board configurations, and therefore we can represent whether that configuration has been achieved in this game or not with finitely many bits. Of course in practice that would not be how we'd do it, but there is no objection in theory. – Eric Lippert Dec 16 '19 at 18:48
  • 1
    Indeed, I enjoy retro problems but have not given much thought to how one might automate their solution. It would be interesting to see if there is a way to apply lattice theory to retro problems. – Eric Lippert Dec 16 '19 at 19:31
  • Hi Eric thanks for your insightful comment. 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. – Laska Dec 16 '19 at 19:33
  • 1
    Added response to main answer – Laska Dec 16 '19 at 19:48
5

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.

3

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.

1

An answer from a programmer

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, its easy to implement those (any 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 definately 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.

What about AI

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.

1

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.

0

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. graph visualization of opening

https://www.chessroots.com/

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.