Formal Game Description

We want to provide a formal, mathematical description of the key elements in a game:

• Game State
• Game View
• Game Setup
• Player Actions
• Victory Conditions
• Progression of Play

---
config:
  theme: neutral
---
flowchart LR;
s((setup)) ==> s0(state 0) === p0[[progress]] ==> s1(state 1) ==> e1{{victory?}} ===|no| p2[[progress]] ==> s2(state 2) ==> v2{{...}}

s0 -.-> v0([view 0])
a0[action 0] -.-> p0
s1 -.-> v1([view 1])
e1 --->|yes| e((end))
a1[action 1] -.-> p2

You can download the godot project that implements this material and play it here.

Game State

The essential information about the game.

• The set of players is $P = \left\lbrace -1, 1\right\rbrace$.
• The set of boards is $B = \left\lbrace -1, 0, 1\right\rbrace^{3 \times 3}$ the set of $3\times 3$ matrices with entries from $\left\lbrace -1, 0, 1\right\rbrace$.
• The set of states is $$ S = P \times B = \left\lbrace (p, b) : p \in P, b \in B\right\rbrace $$
• If $p \in P, b \in B$ we also define the following functions: $$ \begin{align*} s = (p, b) &= state(p, b) \in S &&\text{create state}\cr p &= player(s) &&\text{get player} \cr b &= board(s) &&\text{get board}\cr place(b, x, i, j) &= b’ \in B \text{ such that } \begin{cases} b’_{ij} &= x \cr b’_{mn} &= b_{mn} \text{ for } (m,n) \not= (i,j) \end{cases} &&\text{action outcome}\cr next(p) &= -p &&\text{next player}\cr col(s, j) &= \left\lbrace board(s)_{1j}, board(s)_{2j}, board(s)_{3j}\right\rbrace &&\text{column }j\cr row(s, i) &= \left\lbrace board(s)_{i1}, board(s)_{i2}, board(s)_{i3}\right\rbrace &&\text{row }i\cr dd(s) &= \left\lbrace board(s)_{11}, board(s)_{22}, board(s)_{33}\right\rbrace &&\text{desc. diagonal}\cr ad(s) &= \left\lbrace board(s)_{13}, board(s)_{22}, board(s)_{31}\right\rbrace &&\text{asc. diagonal} \end{align*} $$

Game View

What part of a state $s$ is shown to player $q$?

If $s \in S, q \in P$: $$ view(s, q) = s $$

Other games might show only some part of the full state. For example, imagine a card game; the state describes each player’s hands plus the deck and the stack; but, for each player, only her’s own hand and possibly the cards on the desk are visible.

Game Setup

How does the game starts, i.e., what is the initial state?

$$ setup() = s_0 = \left( 1, \left[ \begin{matrix} 0 & 0 & 0 \cr 0 & 0 & 0 \cr 0 & 0 & 0 \end{matrix}\right]\right) $$

Player Actions

What are the players actions and how do they define the next state.

The effect of action $i,j$ by player $q$ in state $s$ is defined by: $$ action(s, q, i, j) = \begin{cases} s\qquad &\text{ if } \qquad q \not= player(s) &\vee \cr & \qquad i < 0 \vee i > 3 &\vee \cr & \qquad j < 0 \vee j > 3 &\vee\cr & \qquad board(s)_{ij} \not= 0\cr \left(next(q), place(board(s), q, i, j)\right) &\text{ otherwise } \end{cases} $$

Legal actions define a new state while illegal ones keep the state unchanged.

Victory Conditions

When the player $q$ wins the game.

$$ victory(s, q) \Leftrightarrow \left\lbrace \begin{align*} q & \not= 0 &\wedge\cr &\:\Large(& ad(s) &= {q} \vee \cr &&dd(s) &= {q} \vee \cr &&col(s, 1) &= {q} \vee& col(s, 2) &= {q} \vee& col(s, 3) &= {q} \vee \cr &&row(s, 1) &= {q} \vee& row(s, 2) &= {q} \vee& row(s, 3) &= {q} &\:\Large) \end{align*} \right. $$

Here we also define a draw state as: $$ draw(s) \Leftrightarrow \neg victory(s, 1) \wedge \neg victory(s, -1) \wedge \forall i,j \in {1, 2, 3}, board(s)_{ij} \not= 0. $$

Note that e.g. $col(s, 3) = {q}$ states that, in state $s$, all the elements in the third column are equal to $q$.

Progression of Play

Given a state $s \in S$, the progress (next state) that results from action $i,j$ by player $q$ is: $$ progress(s, q, i, j) = \begin{cases} action(s, q, i, j) &\text{if}\quad \neg victory(s, next(q)) \wedge \neg draw(s) \cr s &\text{otherwise} \end{cases} $$

The state only progress if it is not a ending state and the action is legal.