Answers.Body: <p>Yes, I think so.</p>
  
  <p>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.</p>
  
  <p>In the end you'd get the set of all possible chess games as the language that is accepted by the machine.</p>
  
  <p>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.</p>
  
  <p>Draw offers, and games ending in other external ways like a mobile phone going off should probably be left out.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-12-16T17:55:44.383Z
Answers.Text: 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.
Answers.UserDisplayName: CPomerantz
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-12-16T19:39:57.183Z
Answers.Text: 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.
Answers.UserDisplayName: BlueRaja - Danny Pflughoeft
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-12-16T22:54:46.900Z
Answers.Text: 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.
Answers.UserDisplayName: Solomon Slow
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-12-17T09:25:22.337Z
Answers.Text: @SolomonSlow yes, but the original poster admits to using the terms loosely.
Answers.UserDisplayName: Jasen
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-12-18T11:19:48.390Z
Answers.Text: 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.
Answers.UserDisplayName: M.Herzkamp
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-12-18T20:53:18.290Z
Answers.Text: @M.Herzkamp That's easy to handle, at the cost of blowing up the size of the set of states.
Answers.UserDisplayName: chepner
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-12-16T09:39:56.160Z
Answers.LastActivityDate: 2019-12-16T09:39:56.160Z
Answers.UserDisplayName: RemcoGerlich
Answers.Body: <p>Finite state machines can be described as the recognizers of <a href="https://en.wikipedia.org/wiki/Regular_language" rel="noreferrer">regular languages</a>. You could perhaps identify chess with the set of all possible game records. For example <code>f3e5g4Qh4#</code> (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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-12-18T15:35:56.283Z
Answers.Text: @Cruncher seriously, you fool, [how could you possibly think that XML can't be parsed by regex](https://stackoverflow.com/a/1732454/745903)?
Answers.UserDisplayName: leftaroundabout
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-12-16T14:00:27.563Z
Answers.LastActivityDate: 2019-12-16T14:00:27.563Z
Answers.UserDisplayName: John Coleman
Answers.Body: <blockquote>
    <p>may the game of chess be considered a finite state machine?</p>
  </blockquote>
  
  <p>Yes; this is a good insight. </p>
  
  <p>A FSM is an abstract model of computation with the following characteristics:</p>
  
  <ul>
  <li>The machine begins in a known "start state"</li>
  <li>The machine accepts a sequence of inputs</li>
  <li>Each input is interpreted in the context of the current state</li>
  <li>Each input causes an update to the current state; the update depends <em>only</em> on the current game state and the input.</li>
  <li>Some states are "stop states", which cause the machine to stop.</li>
  <li>There is a strict upper bound on the size of the state and the number of possible inputs.</li>
  </ul>
  
  <p>It is the last feature which makes the machine a <em>finite</em> state machine. That is, if we <em>numbered</em> each individual state that the machine could <em>possibly</em> be in, there would be a <em>largest</em> such number. Maybe larger than the number of atoms in the universe, but still finite.</p>
  
  <p>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.</p>
  
  <p>Moreover, <strong>any</strong> 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. </p>
  
  <p>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 <em>any</em> number of chips then no finite amount of information characterizes <em>every</em> poker game.</p>
  
  <p>It is interesting to think about games that are <em>not</em> 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 <em>non-deterministic state transition</em>, and that would make it technically not an FSM... but maybe there is a way around that:</p>
  
  <p>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 <em>input</em>, just one that is not <em>chosen</em> by the player. And the same then goes for other randomized game elements such as card shuffles.</p>
  
  <p>Chess is a particularly good candidate to be treated as an FSM because there is no randomness, and indeed, <em>no hidden state at all</em>. Both players know the entire state of the game at all times.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-12-17T02:31:46.287Z
Answers.Text: 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.
Answers.UserDisplayName: Dancrumb
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-12-18T04:41:57.597Z
Answers.Text: @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).
Answers.UserDisplayName: D. Ben Knoble
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-12-16T18:45:59.587Z
Answers.LastActivityDate: 2019-12-16T20:00:12.467Z
Answers.LastEditDate: 2019-12-16T20:00:12.467Z
Answers.UserDisplayName: Eric Lippert
Answers.Body: <p>It’s very useful for problemists to think of chess as a finite state machine. The state can comprise:</p>
  
  <ul>
  <li>what kind of pieces are on each square</li>
  <li>who has the move?</li>
  <li>castling rights</li>
  <li>en passant capability</li>
  </ul>
  
  <p>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!</p>
  
  <p>There is a subtlety here because while castling rights just depend upon whether K&amp;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.</p>
  
  <p>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.</p>
  
  <p>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.</p>
  
  <p>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.</p>
  
  <p>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.</p>
  
  <p>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.</p>
  
  <p>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 &amp; 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.</p>
  
  <p>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. </p>
  
  <p>EDIT: Others can confirm whether chess can be represented in a FSM. The unique angle I am trying to take is <em>how</em> 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.</p>
  
  <p>There are two main paradigms for retrograde analysis: RS &amp; 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 <a href="https://www.janko.at/Retros/Glossary/Castling-and-En-passant.htm" rel="nofollow noreferrer">https://www.janko.at/Retros/Glossary/Castling-and-En-passant.htm</a>.
  Werner Keym’s article contains some classic and difficult retros.</p>
  
  <p>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.</p>
  
  <p>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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-12-16T18:48:26.830Z
Answers.Text: 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.
Answers.UserDisplayName: Eric Lippert
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-12-16T19:31:43.330Z
Answers.Text: 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.
Answers.UserDisplayName: Eric Lippert
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-12-16T19:33:47.423Z
Answers.Text: 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.
Answers.UserDisplayName: Laska
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-12-16T19:48:34.277Z
Answers.Text: Added response to main answer
Answers.UserDisplayName: Laska
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-12-16T10:46:25.760Z
Answers.LastActivityDate: 2019-12-17T06:25:30.050Z
Answers.LastEditDate: 2019-12-17T06:25:30.050Z
Answers.UserDisplayName: Laska
Answers.Body: <p>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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-12-16T10:54:51.757Z
Answers.LastActivityDate: 2019-12-16T10:54:51.757Z
Answers.UserDisplayName: Inertial Ignorance
Answers.Body: <p>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 <em>as such</em> 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.  </p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-12-16T19:49:02.433Z
Answers.LastActivityDate: 2019-12-16T19:49:02.433Z
Answers.UserDisplayName: Tertium Quid
Answers.Body: <p>Chess game IS a finite state machine, by definition.</p>
  
  <p>Then again, the number of possible states is rather large and there is an even greater number of strategies that both players can follow.</p>
  
  <p>Spare for some endspiels, these numbers generally exceed the modern computational capabilities, so the game is usually NOT modelled as a FSM.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-12-17T08:30:13.963Z
Answers.LastActivityDate: 2019-12-17T08:30:13.963Z
Answers.UserDisplayName: fraxinus
Answers.Body: <p>As you flagged your question with „rules“, i will try an answer.</p>
  
  <p>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.</p>
  
  <p>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).</p>
  
  <p>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.</p>
  
  <p>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.</p>
  
  <p>But if you only apply the Basic Rules, then repetition of positions is possible <em>ad infinitum</em>. And for an infinite number of transition, a <strong>Finite</strong> State Machine can <em>per definitionem</em> be no model.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-12-21T13:14:11.670Z
Answers.LastActivityDate: 2019-12-21T13:14:11.670Z
Answers.UserDisplayName: Christian H. Kuhn
Answers.Body: <h2>An answer from a programmer</h2>
  <p>I stumbled across this and thought an answer from a programmer would be useful here.</p>
  <p>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.</p>
  <p>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.</p>
  <p>The client sits in a particular state while you plot your move. We could call that &quot;planning&quot;.</p>
  <p>Then you select a piece, and the client could give a list of moves available to be selected. The &quot;Moving&quot; state.</p>
  <p>Once you select a move, the client can animate the move.</p>
  <p>Then you switch to &quot;waiting&quot; in which the other client performs the same steps.</p>
  <p>Once checkmate occurs or the game cannot continue, we switch to the &quot;scoring&quot; state.</p>
  <p>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.</p>
  <h2>What about AI</h2>
  <p>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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-12-18T12:38:40.523Z
Answers.LastActivityDate: 2022-11-15T12:26:01.770Z
Answers.LastEditDate: 2022-11-15T12:26:01.770Z
Answers.UserDisplayName: speciesUnknown
Answers.Body: <p>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.
  <a href="https://i.sstatic.net/3095i.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/3095i.png" alt="graph visualization of opening"></a></p>
  
  <p><a href="https://www.chessroots.com/" rel="nofollow noreferrer">https://www.chessroots.com/</a></p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-12-18T16:31:47.217Z
Answers.LastActivityDate: 2019-12-18T16:31:47.217Z
Answers.UserDisplayName: user20899
Answers.Body: <p>An old thread but also an interesting one.
  I will focus on the question in the title.
  &quot;Is a Finite State Machine a good way to model chess?&quot;
  To answer this one must note a very important part of the question: &quot;a good way&quot;.</p>
  <p>I normally cringe every time i see such a qualifier in a question or affirmation. Not because &quot;Good/Bad&quot; is wrong in itself. It becomes very valid for the ones that are experiencing/practicing/solving a certain problem, but when &quot;Good&quot; comes from outsiders it becomes something extremely dubious.</p>
  <p>So to answer that question tldr: It depends.</p>
  <p>One can easily argue that most everything can be modelled or seen as a state machine. But is it &quot;good&quot; to do it explicitly for a game of chess?</p>
  <p>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:</p>
  <p>Not a usual practice and nothing exactly wrong with it, it just depends.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-06-20T02:05:55.450Z
Answers.LastActivityDate: 2023-06-20T02:05:55.450Z
Answers.UserDisplayName: user3658510
Body: <p>A very common model in programming is the Finite State Machine (FSM) (see <a href="https://gamedevelopment.tutsplus.com/tutorials/finite-state-machines-theory-and-implementation--gamedev-11867" rel="noreferrer">here for a great worked example.)</a>
  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?</p>
  
  <p>I have no big knowledge of computer science or engineering, or even chess programming, so I was wondering about this question.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-12-16T12:52:30.540Z
Comments.Text: What is a finite state machine?
Comments.UserDisplayName: David
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-12-16T13:48:46.650Z
Comments.Text: I have limited knowledge of this concept, as I say in the question. The Wikipedia entry should give a fairly good idea of what a finite state machine is. The question is obviously intended for those who know what a fsm is.
Comments.UserDisplayName: A. N. Other
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-12-16T14:12:17.663Z
Comments.Text: 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.
Comments.UserDisplayName: Grade 'Eh' Bacon
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-12-16T14:18:40.743Z
Comments.Text: 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.
Comments.UserDisplayName: A. N. Other
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-12-16T18:47:31.697Z
Comments.Text: @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.
Comments.UserDisplayName: mtraceur
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-12-16T19:37:20.303Z
Comments.Text: This question is not appropriate for this site. It's a question that computer science experts would know, not a question that chess experts would know, so it belongs on cs.stackexchange.com
Comments.UserDisplayName: BlueRaja - Danny Pflughoeft
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-12-16T20:37:14.477Z
Comments.Text: Following your reasoning, questions about chess programming wouldn't be appropriate for this site, too, because only software programmers can answer them properly. But perhaps there is one or more computer science expert on this board, that is also a chess expert. For the time being, it seems to me that most answers to my question are insightul and adequate.
Comments.UserDisplayName: A. N. Other
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-12-16T21:11:54.103Z
Comments.Text: @Grade'Eh'Bacon Why do you _care?_ The guy can ask whatever question he wants, leave him alone.
Comments.UserDisplayName: user428517
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-12-16T22:02:41.473Z
Comments.Text: 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.
Comments.UserDisplayName: Zwuwdz
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-12-16T22:13:54.907Z
Comments.Text: This brings an interesting question: what is a game like chess, in the first place? Isn't it a mathematical construct in disguise? The term "game" is something that we coined because it is entertaining and so on, but if we analyze it deeply isn't math behind all this? Why should a mathematician like John Nash care to write in depth about Game Theory, if certain games weren't ultimately math?
Comments.UserDisplayName: A. N. Other
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-12-16T22:17:04.040Z
Comments.Text: Furthermore, please consider that computers can play chess. And aren't computer programs ultimately made of algorithms, i.e. math?
Comments.UserDisplayName: A. N. Other
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-12-16T23:04:23.710Z
Comments.Text: @A.N.Other, Machines can (in theory) be designed to perform many kinds of chess-related tasks: Tell whether a move is legal, pick a good move for a given board position or history of positions, tell whether a given board state belongs to a legal game, etc. But none of those things is the same as saying that the game _is_ a machine. Machines _do_ things. The game of chess doesn't. The game is not a machine in more or less the same way that a list of turn-by-turn directions is not a road trip, or a recipe is not a meal.
Comments.UserDisplayName: Solomon Slow
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-12-16T23:11:33.297Z
Comments.Text: @Solomon, then what is a “game” in the first place, without two players who play it, a series of actions or tasks that are made, and so on and on? The “game of chess” is nothing in itself, it is a mere abstraction. I am talking about all the action behind it in my question.
Comments.UserDisplayName: A. N. Other
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-12-16T23:38:21.447Z
Comments.Text: A quick google search tells us yes, and it has at most [7728772977965919677164873487685453137329736522 states](https://math.stackexchange.com/a/1407631/2333).
Comments.UserDisplayName: corsiKa
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-12-17T00:48:56.847Z
Comments.Text: @A.N.Other, in order for a computer to play chess and use math to do so, something needs to assign value to the pieces and to the pieces' positions. Once values have been assigned then it is easy to do simple addition to determine if a move increases or decreases its score versus its opponent's score. Then it can make the next move, compute the scores, make the next move, etc. How many moves 'deep' a computer looks is the primary strength setting for most computer chess models. But the real intelligence behind them is in creating the values for the pieces and positions.
Comments.UserDisplayName: CramerTV
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-12-17T00:52:14.877Z
Comments.Text: @A.N.Other, cont. But obviously it's a lot more complicated than that - the model isn't simply a huge (but finite) lookup table of numbers (states) to be added together. It's a search tree the computer creates and traverses (in real time) to compute the scores. How deep (and wide) the computer can make the tree is how many moves ahead it can look and evaluate.
Comments.UserDisplayName: CramerTV
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-12-17T06:24:33.907Z
Comments.Text: @A.N.Other Good question but please change headline to match the detailed text: “May chess be considered as a finite state machine?”
Comments.UserDisplayName: Laska
Tags: <engines><rules><software><computer-chess>
Title: Is a Finite State Machine a good way to model chess?
ThreadText: # Is a Finite State Machine a good way to model chess?
  
  (Asked by: username_0 on 2019-12-16)
  
  A very common model in programming is the Finite State Machine (FSM) (see [here for a great worked example.)](https://gamedevelopment.tutsplus.com/tutorials/finite-state-machines-theory-and-implementation--gamedev-11867)
  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.
  
  **Tags:** engines, rules, software, computer-chess
  
  > **Comments:**
  > **username_1**: What is a finite state machine?  
  > **username_0**: I have limited knowledge of this concept, as I say in the question. The Wikipedia entry should give a fairly good idea of what a finite state machine is. The question is obviously intended for those who know what a fsm is.  
  > **username_2**: 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.  
  > **username_0**: 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.  
  > **username_3**: @username_2'Eh'username_2 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.  
  > **username_4**: This question is not appropriate for this site. It's a question that computer science experts would know, not a question that chess experts would know, so it belongs on cs.stackexchange.com  
  > **username_0**: Following your reasoning, questions about chess programming wouldn't be appropriate for this site, too, because only software programmers can answer them properly. But perhaps there is one or more computer science expert on this board, that is also a chess expert. For the time being, it seems to me that most answers to my question are insightul and adequate.  
  > **username_5**: @username_2'Eh'username_2 Why do you _care?_ The guy can ask whatever question he wants, leave him alone.  
  > **username_6**: 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.  
  > **username_0**: This brings an interesting question: what is a game like chess, in the first place? Isn't it a mathematical construct in disguise? The term "game" is something that we coined because it is entertaining and so on, but if we analyze it deeply isn't math behind all this? Why should a mathematician like username_16 Nash care to write in depth about Game Theory, if certain games weren't ultimately math?  
  > **username_0**: Furthermore, please consider that computers can play chess. And aren't computer programs ultimately made of algorithms, i.e. math?  
  > **username_7**: @username_0, Machines can (in theory) be designed to perform many kinds of chess-related tasks: Tell whether a move is legal, pick a good move for a given board position or history of positions, tell whether a given board state belongs to a legal game, etc. But none of those things is the same as saying that the game _is_ a machine. Machines _do_ things. The game of chess doesn't. The game is not a machine in more or less the same way that a list of turn-by-turn directions is not a road trip, or a recipe is not a meal.  
  > **username_0**: @username_7, then what is a “game” in the first place, without two players who play it, a series of actions or tasks that are made, and so on and on? The “game of chess” is nothing in itself, it is a mere abstraction. I am talking about all the action behind it in my question.  
  > **username_8**: A quick google search tells us yes, and it has at most [7728772977965919677164873487685453137329736522 states](https://math.stackexchange.com/a/1407631/2333).  
  > **username_9**: @username_0, in order for a computer to play chess and use math to do so, something needs to assign value to the pieces and to the pieces' positions. Once values have been assigned then it is easy to do simple addition to determine if a move increases or decreases its score versus its opponent's score. Then it can make the next move, compute the scores, make the next move, etc. How many moves 'deep' a computer looks is the primary strength setting for most computer chess models. But the real intelligence behind them is in creating the values for the pieces and positions.  
  > **username_9**: @username_0, cont. But obviously it's a lot more complicated than that - the model isn't simply a huge (but finite) lookup table of numbers (states) to be added together. It's a search tree the computer creates and traverses (in real time) to compute the scores. How deep (and wide) the computer can make the tree is how many moves ahead it can look and evaluate.  
  > **username_10**: @username_0 Good question but please change headline to match the detailed text: “May chess be considered as a finite state machine?”  
  
  ---
  
  ## 11 answers
  
  ### Answer by username_11 on 2019-12-16. Score: 23
  
  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 username_0 external ways like a mobile phone going off should probably be left out.
  
  > **Comments:**
  > **username_12**: I don't think you need to leave out draw offers and username_0 external factors ending the game. Add DrawAccepted and a BoardState+DrawOffered  state for each board state. Plus BlackLoss and WhiteLoss states for username_0 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.  
  > **username_4**: 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.  
  > **username_7**: 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.  
  > **username_13**: @username_7 yes, but the original poster admits to using the terms loosely.  
  > **username_14**: 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.  
  > **username_15**: @username_14 That's easy to handle, at the cost of blowing up the size of the set of states.  
  
  ---
  
  ### Answer by username_16 on 2019-12-16. Score: 21
  
  Finite state machines can be described as the recognizers of [regular languages](https://en.wikipedia.org/wiki/Regular_language). 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.
  
  > **Comments:**
  > **username_17**: @Cruncher seriously, you fool, [how could you possibly think that XML can't be parsed by regex](https://stackoverflow.com/a/1732454/745903)?  
  
  ---
  
  ### Answer by username_18 on 2019-12-16. Score: 13
  
  > 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 username_0 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 username_0 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.
  
  > **Comments:**
  > **username_19**: 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.  
  > **username_20**: @username_19 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).  
  
  ---
  
  ### Answer by username_10 on 2019-12-16. Score: 9
  
  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 username_0 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 username_0 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.
  
  > **Comments:**
  > **username_18**: 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.  
  > **username_18**: 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.  
  > **username_10**: Hi username_18 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.  
  > **username_10**: Added response to main answer  
  
  ---
  
  ### Answer by username_21 on 2019-12-16. Score: 9
  
  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.
  
  
  ---
  
  ### Answer by username_22 on 2019-12-16. Score: 6
  
  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.
  
  
  ---
  
  ### Answer by username_23 on 2019-12-17. Score: 4
  
  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.
  
  
  ---
  
  ### Answer by username_24 on 2019-12-21. Score: 2
  
  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.
  
  
  ---
  
  ### Answer by username_25 on 2019-12-18. Score: 2
  
  ## 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, it's easy to implement those (and many username_0 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 username_0 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.
  
  ## 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.
  
  
  ---
  
  ### Answer by username_26 on 2019-12-18. Score: 1
  
  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://i.sstatic.net/3095i.png)](https://i.sstatic.net/3095i.png)
  
  <https://www.chessroots.com/>
  
  
  ---
  
  ### Answer by username_27 on 2023-06-20. Score: 0
  
  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.
  
  
  ---
  
  