First, let’s take a look at some combinatorial games.
- Penalty Kicks is a Zero Sum Game
- Payoff for this problem (numbers indicate probability of scoring):
|Player \ Keeper||L||R|
- 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 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.
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.
- Write down what happens in the above subtraction game when . Try to find a pattern. Label every situation.