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

Game State

The essential information about the game.

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

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{array}{ccc}0& 0& 0\\ 0& 0& 0\\ 0& 0& 0\end{array}\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{array}{llc}s& \text{ if }q\ne player(s)& \vee \\ & i<0\vee i>3& \vee \\ & j<0\vee j>3& \vee \\ & board(s{)}_{ij}\ne 0& \\ \left(next(q),place(board(s),q,i,j)\right)& \text{ otherwise }& \end{array}$$

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)\iff \{\begin{array}{rlrlrlrlr}q& \ne 0& \wedge & & & & & & \\ & (& ad(s)& =\{q\}\vee & & & & & \\ & & dd(s)& =\{q\}\vee & & & & & \\ & & col(s,1)& =\{q\}\vee & col(s,2)& =\{q\}\vee & col(s,3)& =\{q\}\vee & \\ & & row(s,1)& =\{q\}\vee & row(s,2)& =\{q\}\vee & row(s,3)& =\{q\}& )\end{array}$$

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

[!IMPORTANT] 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{array}{ll}action(s,q,i,j)& \text{if}\neg victory(s,next(q))\wedge \neg draw(s)\\ s& \text{otherwise}\end{array}$$

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