Table of Contents

Recap

  • Combinatorial Games: 2 players with turns, complete information. Each player has the same set of moves, and there is no randomness. There are no ties.
  • \(x \in X\) is called terminal if \(F(x) = \emptyset\).
  • Normal Play: Player on whose turn is faced with a terminal position loses.
  • Misère Play: Player on terminal position wins.

Combinatorial Game Analysis

To analyze a game, we classify all positions as \(P\) or \(N\) as follows:

  • \(P\): one from where the previous player can guarantee a victory. Note that this means we assume optimal play from both players.
  • \(N\): one from where the next player can guarantee a victory.

Under Normal Play, all terminal positions are P positions. Conversely, under Misère Play, all terminal positions are N positions.

Subtraction Games

These are the simplest take-away games. The game begins with \(n\) chips. On your turn, you take away \(k\) chips from the pile, where \(k \in \textrm{ subtraction set } S\).

Example

Let us analyze the set \(S = \{1, 2, 3\}\).

x 0 1 2 3 4 5 6 7 8 9 10
F(x) \(\emptyset\) \(\{0\}\) \(\{0, 1\}\) \(\{0, 1, 2\}\) \(\{1, 2, 3\}\) \(\{2, 3, 4\}\) \(\{3, 4, 5\}\) \(\{4, 5, 6\}\) \(\{5, 6, 7\}\) \(\{6, 7, 8\}\) \(\{7, 8, 9\}\)
P/N P N N N P N N N P N N

An observation: A position \(x\) is a \(P\) position if \(x\) is divisible by \(4\).
This leads us to formulate the following hypothesis:

\[x \textrm{ is a P-position } \iff x \equiv 0\ (\textrm{mod } 4)\]

Proof by induction

We first note that \(\forall x \in \mathbb{Z}^+, x = 4k, 4k + 1, 4k + 2, 4k + 3\).
Assume that our inductive hypothesis is true \(\forall k,\ 0 \leq k < n\) .
We show that it is true for \(m=n+1\).
Recall that we defined the following sets:

\[P = \{x \in X \textrm{ s.t. x is a P-position}\}\] \[N = \{x \in X \textrm{ s.t. x is a N-position}\}\]

Claim: Every \(x \in X\) is in \(P \cup N\), and \(P \cap N = \emptyset\). Read the proof of this in Theorem 1.1.5 in KP.

A winning strategy is a set of moves from \(x\) that can guarantee a win.

Graphs

A graph is defined as \(G = (V,E)\), where \(V\) is a set of vertices and \(E\) is a set of edges connecting the vertices. We can define a graph on our state space, which (upon inspection) is a DAG since all states can only transition into smaller states.

A Recursive Algorithm to Label Positions

(Ferguson) Recursive Algorithm to Label Positions:

  1. Label all the terminal positions as \(P\).
  2. Label each position that has an edge to a \(P\)-position as \(N\).
  3. If a position is not labeled yet, then check the edges. If there exists at least one edge to a \(P\)-position, label this position \(N\). Otherwise all edges lead to \(N\)-positions, so we label this position \(P\).

Homework

Analyze \(S={1,3,4}\), and give a general rule.

Chomp

Invented by David Gale. Related to divisor game (Frederik Schuh). Chomp.