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.