1. Game Trees
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 assume optimal play.
You can play the game below.
Lata’s turn to move.
