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 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.

  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.