## Combinatorial Games

First, let’s take a look at some combinatorial games.

### Penalty Kicks

• Penalty Kicks is a Zero Sum Game
• Payoff for this problem (numbers indicate probability of scoring):
 Player \ Keeper L R L 0.5 1 R 1 0.8

### Prisoner’s Dilemma

• Prisoner’s Dilemma is a General Sum Game
• Payoff for this problem (numbers indicate time in jail):
 Prisoner 1 \ Prisoner 2 Silent Confess Silent (1, 1) (-10, 0) Confess (0, -10) (5, 5)
• Nash equilibrium says they will (Confess, Confess)
• Example of individual rationality.
• (Sidenote: Pareto optimality works for group)

Requirements to be a combinatorial game: 1

• 2 players
• No ties; there is a winner and game ends
• Taking turns (no simultaneous play)
• Impartial (no differences in moves available to players)
• No randomness
• No hidden information
• Ending Conditions: The game will end in a position where one of the players cannot move. There are two types of endings:
• The last player to move wins (Normal Play).
• If last player to move loses (Misère Play)

The games we will study are called progressively bounded impartial combinatorial games, or PBICG. The games will have a fixed set of positions $$X$$ and rules that dictate how to get from $$x \in X$$ to $$y \in X$$. If you can go from $$x$$ to $$y$$, then we say that $$y$$ is a follower of $$x$$, and we write $$y \in F(x) \subseteq X$$. Terminal positions in a game are ones that have no followers. In other words, $$f(x) = \emptyset$$. The game ends when one of the players is at a terminal position on their turn.

Progressively Bounded: $$\forall x \in X, \exists B(x) < \infty$$ such that the game ends in at most $$B(x)$$ moves. In other words, from any valid start position, there is a bounded set of possible moves that all terminate the game. This can be thought of as a directed graph.

• Ferguson’s notation: We start with a graph $$x$$ and a transition function $$F$$. As a directed graph, we have edges where source is $$x$$ and destination is $$y$$, where $$x$$ transitions to $$y$$. $$X$$ represents all nodes (states) of a game, and $$F(x)$$ represents all states that state $$x$$ can transition to.

## Subtraction Game

A take-away game.

This game is defined by $$S=\{1,2,3\}$$. Start with $$n$$ chips. On your turn, you take away 1, 2, or 3 chips.

Take the example of 3 chips. This is an example of an end position since the game can be ended in one move.

Take the example of 4 chips. It doesn’t matter what the player does, since the game is unwinnable.2 In other words, the previous player can guarantee a win.

## Homework

• Write down what happens in the above subtraction game when $$n=1, 2, ... ,10$$. Try to find a pattern. Label every situation.

1. We will not be studying partisan games. A good book to read about other kinds of games is Winning Ways for your Mathematical Plays, by Berlekamp.

2. We assume no human error.