1. Game Trees

Acknowledgements

This write up is based on material from Sections 0.1 — 0.3 of Kyle Burke and Craig Tennenhouse’s textbook on Playing wiht Discrete Mathematics. The interactive games were generated with assistance from ChatGPT (the May 12 version).

Main Ideas

We are going to play some games, and analyze them! Informally speaking, our games consist of:

• two players who take turns to play
• a setup that describes the state of the game at the beginning
• a ruleset that describe the moves that are available to the players, and a description of how these rules affect the state of the game
• a winning condition: typically, the player who has no valid moves loses

For now, there will be no probabilities involved (so Poker does not fit the bill above), and no skills required to execute the moves (so Cricket is not our kind of game here).

The two players have several names by which we may refer to them:

• first player, second player
• left player, right player
• Alice, Bob
• Lata, Raj

A winning strategy for any player is a powerful thing: it’s a way for the player to respond to every move of the opponent in a manner that guarantees a win. You can think of a strategy as a function that maps game states to valid moves, and a winning strategy is a strategy which, if followed, always ends in a win for the player employing it. Instead of saying “Player X has a winning strategy”, we will just say “Player X wins”, or in question form, “Does player X win?” — even though it may be technically possible for a player to throw a game, we will always assume optimal play unless mentioned otherwise.

Subtraction

Here’s our first game:

Subtraction

Subtraction is a game played on a heap of tokens. The game begins with N tokens on a pile.

• Each turn, the current player can remove either 1,2, or 3 tokens from the pile, provided enough tokens exist.
• When the pile is empty there are no available moves.
• The player with no valid moves left loses.

You can play this game below: the number of tokens that we start with is chosen randomly, so you should have a new game every time you referesh this page :)

Lata’s turn to move.

Here’s a more general version of the game where the number of tokens you are allowed to remove is not 1,2,3; but 1, a and b, where a and b are distinct numbers chosen randomly between 2 and 10. As before, it is a new game every time you referesh this page.

Lata’s turn to move.

Let us refer to the player whose turn it is as the current player, and the player who is up next as the other player. Coming back to the (1,2,3)-Subtraction game, note that:

• If there are no tokens, the position is losing for the current player.
• If the number of tokens is 1, 2, or 3, the position is winning for the current player.
• If the number of tokens is 4, the position is losing for the current player. (Why?)

Can you generalize the reasoning above?

Game Trees

A game tree is a useful representation of game states over all possible progressions of game play from the start. In particular:

• The root represents the starting state of the game.
• If the state of the game represented by a node x has t valid moves — say m_1, \ldots, m_t for the current player, then:
  • x has t children y_1, \ldots, y_t
  • the node y_i represents the state of the game that is obtained from x if the move m_i is made by the current player

Note the the leaf nodes are terminal states of the game, this is where there are no moves remaining to be made. Observe that:

• Every leaf node is a losing position for the current player
• An internal node is winning for the current player if and only if it has a child node that is losing for the current player (Why?)

You can build out the game tree for (1,a,b)-Subtraction starting with n tokens, by supplying the values of a, b, and n below. The red nodes represent positions that are losing for the current player (equivalently, winning for the other player), while the green nodes represent positions that are winning for the current player (equivalently, losing for the other player).

Heads up!

Note that the nodes collapse on click, but unfortunately do not retain the correct color state on collapse.
This is a caveat that should be fixed soon!

a:            b:            n:           

---

Summary

What we saw here:

• The concept of a turn-based, two-player game with perfect information.
• The notion of winning strategies and positions.
• The idea of a game tree.

Next time, we will discuss decomposing games into “disjoint unions” of smaller games.