# Note 2 - Combinatorial Games

## 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 last player to move wins (

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

**Progressively Bounded**: such that the game ends in at most 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 and a transition function . As a directed graph, we have edges where source is and destination is , where transitions to . represents all nodes (states) of a game, and represents all states that state can transition to.

## Subtraction Game

A take-away game.

This game is defined by . Start with 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 . Try to find a pattern. Label every situation.