It seems to me that a very general case for "finite memory games" is the case of a "non-deterministic finite memory game with $n$ players". I made this classification many years ago (about 5 or 6) mostly out of concern of conceptual (not mathematical) classification. And I hope people see the answer in that light. The advantage of this formulation is that it can be quickly be specialised to more specific cases as the need arises. The version I describe here is not fully general (for the sake of brevity), but general enough that one can easily see how to make it more general if need arises. At the same time, I will admit complete ignorance of usage of this term in economics, combinatorics, mathematics etc. Below we consider a description of a "non-deterministic finite memory game with a single player". Some further assumptions are (that can be relaxed if required): **(i)** From every state there is a path to both "Win" and "Lose" state (should become quite clear soon). This condition is probably a little restrictive (especially when we might have more than one player), but makes the description below fairly short. Shouldn't be difficult to relax this condition. **(ii)** In principle, the game is of perfect information. That is, at least in principle, the player can always figure out which state of the game is the player currently occupying. Making a generalisation to accommodate for both (i) and (ii) isn't that difficult but I have tried to keep things simple (so the basic idea can be explained in a not too long answer). Now here is the description: **(a)** We have a finite set of states denote by set $S$. The game always includes a "Win" and "Lose" state. If there are $n$ number of (main) states, then we have $M=\{s_1,\,s_2,\, s_3,....,\, s_n\}$ (main states only) and $S=\{s_1,\,s_2,\, s_3,....,\, s_n,\, Win ,\, Lose \}$. The state $s_1$ could possibly be thought of a start state. **(b)** We have a finite number of actions for the player. So if there are $m$ number of actions, we can denote them as: $A=\{a_1,\, a_2, \, a_3, \,...., a_m \}$ **(c)** From each (main) state $s_i$ **and** for each action, there are finite (but potentially more than 1) arrows that lead to other states (possibly including $s_i$ itself). Hence we can think of a **transition function** from $M \times A$ to **subsets of** $S$. An example w.r.t. (b). If we think of a computer game being played with a controller with just two buttons A and B for example, then the set of actions $A$ can naturally be thought of as $A=\{doNothing,\, pressA,\,pressB,\, pressAandB \}$. At the end of each clock cycle, the game is updated according to the action of the player. An example w.r.t. (c). In a single player game of a traditional computer version of tetris (that's the most natural example I can think of), the randomiser that hands the pieces/tetrominoes can be thought of as adding the non-determinism (in a natural way). Of course, this might differ a bit from the actual specific implementation, but we are talking about a conceptual analysis. Now, as far as (elementary) mathematical analysis is concerned (without accounting for any time-complexity concerns), each state in the set $M$ of main states can be marked as $W$ or $WL$. A given state $s_i$ being marked $W$ means that the player can "always" win the game from that state if he plays well-enough (winning the game means reaching the "Win" state). A given state $s_i$ being marked $WL$ means that no-matter how well the player plays from this point on, a win can't be guaranteed. Though while writing this it occurred to me a significant concern could also be whether it might be possible (just by chance) to be promoted to a $W$ marked state (from a state marked $WL$). Similarly each individual transition in the transition function (described in (c)) can also be marked. Each transition can be marked as one of $w$, $wl$, $l$. A transition being marked $w$ means it only leads to main states marked $W$ or to the "Win" state (one can suitably account for arrows from a given state to itself). A transition being marked $wl$ means that it leads to at least one state marked as $WL$. A transition being marked $l$ means that it only leads to the "Lose" state. One can (using the previous two paragraphs) devise a general naive algorithm (ignoring computational complexity) that can mark all the states and transitions in any "non-deterministic finite memory game with a single player" (and hence a perfect strategy too ... if one exists from the start state). To see, how flexible this definition is (and how it can be easily accommodated for most variations in "finite memory games"), here are few examples: **(1)** First lets come back to board games like "chess" or "go". We might wish to generalise our notion for two (or more) players. Basically the "Win" state for one player will become "Lose" state for the other (and viceversa). More generally, the number of markings of states will also increase I think (I haven't looked at this variation in detail before so I can't comment). I have not described that generalisation here, but it shouldn't be difficult to see that it can be made with some effort. Let's think about a bit for the set $A_1$ or $A_2$ (actions for player-1 or player-2) for a game like Go. For an $n \times n$ board the set of actions (for any player) can be thought of as a set consisting of $n^2$ elements (as the board is getting filled some of the actions no longer change the game state .... meaning they become redundant). A similar case can be made for chess (each piece has finite number of possible moves .... once a piece is thrown out of the board, all the actions corresponding to it no longer change the game state). **(2)** Consider a computer version of tetris with the feature of endless play included. We can simply modify our above definition to "remove" the "Win" state entirely and just keep the "Lose" state. Now instead of each main state being marked as "W" or "WL", it is only marked as "O" (guaranteed possible to orbit or play forever with perfect play) or "OL" (not guaranteed possible to play forever). **(3)** Sometimes computer games can also have bugs which can put player in an endless situation --- when the actual goal was just to "Win"(reach the end) or "Lose"(gameover screen). As far as I know, this was actually the case in a rather well-known genesis game. To accomodate this kind of possibility we admit the possibility that from a given state there may be no path to either of the "Win" or "Lose" states. The classification of main states will also increase from just $W$ and $WL$. **(4)** Finally there is the issue of perfect information. Fog of war in RTS game is rather conventional example. But for the sake of our case, consider a board game with "fog of war". In that case the player can't know the complete state of the game with certainty (because he can't view all of the board). These kind of issues can also be handled with the some modification to basic definition described above (possibly by making a distinction between "player state" and "game state"). I think the player state could then be idealised as a finite set of game states. But I haven't thought about this situation that much. **(5)** I haven't thought that much about probabilistic concerns (each arrow in a transition marked with a probability), but they might probably significantly complicate the maths. --- Obviously this answer doesn't address the (more) mathematical aspects that are specific to board games ..... and neither the computation complexity concerns (that people might have for practical reasons). In some sense, I would just note briefly though that a very similar question can be raised also for computer games (possibly mathematically more useful to pose for more specific genre) .... as has been raised for board games here .... once one regards them as finite memory games. **Edit:** Made number of corrections on various points.