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.
  • is called terminal if .
  • 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 or as follows:

  • : one from where the previous player can guarantee a victory. Note that this means we assume optimal play from both players.
  • : 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 chips. On your turn, you take away chips from the pile, where .


Example

Let us analyze the set .

x 0 1 2 3 4 5 6 7 8 9 10
F(x)
P/N P N N N P N N N P N N

An observation: A position is a position if is divisible by .
This leads us to formulate the following hypothesis:


Proof by induction

We first note that .
Assume that our inductive hypothesis is true .
We show that it is true for .
Recall that we defined the following sets:

Claim: Every is in , and . Read the proof of this in Theorem 1.1.5 in KP.

A winning strategy is a set of moves from that can guarantee a win.


Graphs

A graph is defined as , where is a set of vertices and 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 .
  2. Label each position that has an edge to a -position as .
  3. If a position is not labeled yet, then check the edges. If there exists at least one edge to a -position, label this position . Otherwise all edges lead to -positions, so we label this position .

Homework

Analyze , and give a general rule.


Chomp

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