When is a game tree the game tree of a board game?

Question

This question arises from what I find interesting in the recently asked question What is a chess piece mathematically?

My answer to that question was that mathematically, game pieces are in general epi-phenomenal to the main game-theoretic consideration, the underlying game tree. In this sense, strategic decisions do not involve directly game pieces but only choices in the game tree.

But nevertheless, I think a question remains. Namely, how can we recognize from a game tree that there is an underlying description of the game using pieces moving according to certain rules on a game-playing board? In other words, when is a game tree the game tree of a board game? The game trees arising from board games are a special subclass of the class of all game trees.

For this question, let us consider a game tree to be a finite or at least a clopen tree, all of whose terminal nodes are labeled as a win for one of the players (a slightly more general situation would be to allow some of the terminal nodes to be labeled with a draw). Play proceeds in the game by each player successively choosing a child node from the current node in the game tree, and the game ends when a terminal node is reached. (Of course a more general question would result from allowing infinite plays and using the usual Gale-Stewart conception of games.)

Of course, we can imagine playing a game by moving a piece on the game tree itself, in a way such that the resulting game tree is the same as the given game tree. But in this case, the board of the game would have the same size as the game tree. But in the case of our familiar board games, such as chess and Go, the boards are considerably smaller than the game trees to which they give rise. So what we really want is a board game whose board and number of pieces is considerably smaller than the game tree itself.

In the general case, the size of the game board and the number of game pieces would be connected in certain ways with the branching degree of the corresponding game tree. For example, in chess there are twenty first moves (each pawn has two moves, and each knight has two moves) and twenty second moves, and in general the number of moves does not greatly exceed this, which is on the order of magnitude of the board size, although the size of the game tree itself is considerably larger than this. In general, for our familiar games, the size of the game tree is much larger than its branching degree.

As a test question, if a game tree has a comparatively low branching degree compared with its size, is there always a way to realize it as a board game?

I'm not sure what counts as a board game, but the idea should be that there is a board and pieces that move about on the board according to certain rules, perhaps capturing other pieces, and certain configurations counting as a win, such as capturing a certain king piece or whatever. So part of the question is to provide a mathematical definition of what counts as a board game. What is a board game? Are there comparatively simple necessary and sufficient conditions on a game tree that it be realized as the game tree of a board game?

I would be interested also to learn of general sufficient conditions. How shall we think about this?

Answer 1

Here is one possible answer. An essential feature of any board game, in the way I am thinking about it, is that there are only finitely many game states that are realizable on the board. This fact, combined with a rule about whether repeated states are allowed or cause a draw or whatever, means that in any such board game, there will be only finitely many isomorphism types realized as lower cones in the game tree.

So one possible answer to the question is that a given game tree is the game tree of a board game just in case it has only finitely many isomorphism types of its lower cones.

For the one direction, as I've mentioned, any board game has this property.

Conversely, if a game tree does have this property, we can realize it as a board game by making a "board" out of the finitely many isomorphism types, and a piece that moves from one type to another, according to the rule that such a type is realizable from another for a particular player if and only if the game tree allows it.

Answer 2

This is kind of an elaboration on JDH's answer. A similar problem occurs for more general games with a recursive structure. There are game theoretic models such as stochastic games in which there is a fixed set of states (corresponding roughly to positions on a board) and one often looks at stationary equilibria in which strategies are functions of the states alone.

However, such states are not part of the game-tree and the question is whether one can define them from the tree as an equivalence class of history. In a paper by Maskin and Tirole, they show how to do this under the (for the present purpose) harmless assumption that there are only finitely many actions available at each history and the less harmless assumption that states are separated by calendar time (length of histories). None of these assumptions is necessary, as one can show using some very elementary facts about partitions.

I did so in the second paper of my thesis in economics. There is nothing spectacular here, but one can always find a coarsest partition of histories such that the game "from then on" can be described in terms of the partition cells alone and such that the partition respects natural isomorphisms of subgames. The game need not terminate. In particular, one can always find "board positions" and if there are finitely many such positions, one might call the game a board game.

Answer 3

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" states. 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).

[EDIT2:] However, I was viewing this thread again and it seems to me that there is one further distinction that is worth making (and shows how many distinctions can be made even in this simplest case). Suppose we run the algorithm for the above mentioned game and the algorithm tells us that the start state is $WL$ (but not $W$). Hence we will know from that we have no definitive way of winning (with 100% chance). So is there something else we can add? I think there is atleast one point that can be added.

Suppose the player hates to lose (and if there is any risk of losing, the player would want the game to go on forever). Now the player would want to know whether the game could be made to go on forever with some strategy. It seems that this can be handled too. However, notice there is one further slightly subtle aspect still. We know that the start state is marked $WL$. However, this doesn't tell us (by itself) that we might have few "chances" of being promoted to a state marked $W$ at some points! But once again we would want to know that in case those "chances" all go against the player (player isn't promoted), whether after that the player would still be able to force the game to go on forever! Because ideally, if the game could be made to go on forever after taking all the chances (of being promoted), that's what the player should be doing.

This probably needs to be worked a bit further to make it more rigorous, but I am reasonably confident that the basic idea in above paragraphs is correct. [END]

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) [EDIT2] My example w.r.t. to "chess" and "go" was described rather badly (and hence this re-wording). Let's first think of entirely different examples first. A reasonable analogy for generalisation of the above single player game could perhaps be written as "simultaneous non-determinisitic game of two players". One might think of a computer game like "Frozen Synapse"(https://en.wikipedia.org/wiki/Frozen_Synapse). The details are not too important. Another example, could be suppose a board-like game (not too different from checkers or chess) being played online by two different players from different locations. None of the players can see the other's board, but both move there pieces in the same turn and click the finalise button after decision. The game turn proceeds after both players have clicked on finalise. The "non-deterministic" qualification means that we are allowing for some possible "roll of dice" (even for a specific combination of both players' action).

Now let's think a bit about how we can modify the above scheme for a game like chess for example (which is "turn-based" as opposed to "simultaneous" .... and well involves no roll of dice either). We can just colour all the game states as either "white" or "black" (the start state would be coloured "white" indicating that it makes the first move). Let's think about a bit for the set $A_1$ or $A_2$ (actions for "white" and "black" respectively). For example, the set $A_1$ can be made to correspond to all possible moves of individual pieces (and hence $A_1$ will be finite). Similarly for the set $A_2$.

If a state is coloured white (meaning white's turn) then any action from that state is an element of $A_1 \times A_2$. Let $a_1 \in A_1$ and similarly let $a_2, \, b_2 \in A_2$. Observe that on a state coloured white both $(a_1,a_2)$ and $(a_1,b_2)$ will lead to the same state. Furthermore, after an action is selected the next state will be one coloured black.

Finally we do need to account for the fact that once a piece (say a "white piece") is thrown out of the board, the elements corresponding to it in $A_1$ lost their "meaning" (and perhaps can be put equivalent as default to some other action). But I guess that's really an artifact of the way "domain" of "transition function" is defined. Maybe that can be handled in a more natural way?

The summary of that simply is that for two or more players, the "simulaneous" version is general enough that it can "include" the "turn-based" somewhat naturally (though with some artifacts). [END]

(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 possibility to play forever with any strategy .... but with enough luck on our side possible to reach a state marked "O") or "L" (guaranteed to lose eventually from this point).

(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 accommodate this kind of possibility we admit the possibility that from a given state there may be no path to either the "Win" state or the "Lose" state (meaning you are stuck forever without any possibility of winning or losing). 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.

Answer 4

This isn't a full answer but some setup and initial attempt.

Maybe we can formalize a class of "board games" that we're happy with first. I'd propose that:

• A board is a set of locations.

• A piece occupies a single location on the board at a given time. Probably each piece "belongs" to exactly one player.

• A move consists of placing a new piece on the board at some location, removing one from the board, and/or moving a piece from one location to another. (e.g. capturing in chess does two of these things)

• A history is a list of past moves.

• The "rules" specify, for a given history, which player is to move and which moves are legal at that time.

Now I am pretty happy with this definition, but the problem is (as has been noted) an arbitrary game tree can be phrased as a board game in this way.

But I think we get closer with this restriction:

(consistency) the set of legal moves depend only on the board position, not the history.

and even farther with

(simplicity) each piece's set of legal moves depend only on the occupancy status of the board's locations, not the identity of the pieces there.

Edit: I think we can come up with some better "simplicity" condition having to do with a simple set of rules for each piece, but formalizing it seems tricky to me.

Of course castling, en passant, and 3-repetition-draw don't satisfy this (edit: nor does e.g. a pin of a piece to the king), so it technically rules out chess. But I think these restrictions make it easier to think about your question.

From here we could say that a board game tree always has each node labeled by the board "position" (set of current pieces and their locations) and history of moves. At each node, its moves are labeled by pairs (piece, location) consisting of pieces that can legally be moved (including those that may be newly placed on the board, as in Go) along with a legal destination location. Furthermore if we have the consistency and simplicity conditions, then these do not depend on the history, only the board position, and can be calculated "simply" from that position for each piece.

Answer 5

[Edit: Two quick downvotes let me fear that my answer is likely to be misunderstood. I do want to be constructive. But my reasoning leads me to the conclusion that the a priori statement "The game trees arising from board games are a special subclass of the class of all game trees" is not so obviously true: If we look for a precise definition of board game which satisfies the requirement of being compatible with full-fledged chess, Go, Chinese checkers (example of a multi-player board game) and several other popular board games, then one has to realize that it is very difficult to propose restrictions which would not allow almost any game to be satisfy the definition of a board game.]

The question given in the title isn't well posed until we find consensus on a definition of what is a board game. This is actually the main problem, and it turns out to be quite difficult to find a definition which is at the same time somewhat restrictive w.r.t. other non-board games, and nonetheless compatible with those existing games which are considered *board games" by common sense and established dictionaries. To illustrate what I mean, we may notice that even the most "basic" requirements given in earlier answers turned out to be too restrictive:

(1) The finite number of possible constellations: as mentioned somewhere, one could well imagine pieces which grow in (whatever) "strength" without limit. (From the piling up of pieces to denote kings in checkers, its only one step further to imagine a kind of promotion that allows a player to attach an arbitrarily large number to any of his pieces).

(2) A move = piece taken from one location to another, possibly removing another enemy piece: obviously, an arbitrary number of enemy pieces might be removed (as in Go).

• Io include moves similar to castling in chess, the definition must potentially allow several pieces from different locations to move at once into possibly any other location.

• To include promotions, pieces must be able to be changed into any other of the (as said earlier, possibly infinitely many) pieces.

(3) Also, many of the most popular board games involve throwing dice (which was the case for chess for a long time, not so long ago), asking and answering questions to the other player(s), ....

So, in short, it appears that, in a satisfying definition of a board game,

(a) a "state" of the "board" must comprise more than just a finite number of locations, a possibly variable number of possibly infinitely many distinct pieces (which may be on the board or not), and in addition to the game history, also an arbitrary number of possibly ordered (or possibly infinite) collections of questions and answers.

(b) possible "moves" must include almost arbitrary transitions from one such state to virtually any other state of the board, i.e., in particular, an arbitrary number of pieces can change its location on (or off) the board, in the spirit of Go moves, castling, etc.)

We see that the physical board and the "pieces placed on that board at a given moment" are only a very small part of a possible "state". So it becomes questionable whether restrictions can be found preventing almost any game from being a board game according to a satisfyingly general definition of the latter, i.e., compatible with the most popular board games.

So it is legitimate to wonder whether the notion of "board game" can make a strict logical sense (as opposed to the obvious intuitive sense), unless of course we don't require it to be compatible with real-world chess, Go, Chinese checkers and common popular board games using dice, heaps of questions and/or instructions, etc.