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.