## Two nice facts about games.

Posted in Math by pgadey on 2014/03/29

Since giving my talk last week about games, I’ve been on a bit of a mathematical gaming kick, and would like to share some of the gems I’ve come across. We’ll give a beautiful argument due to Gale about his game Chomp, and an exceedingly clever argument due to Hochberg, McDiarmid, and Saks which applies Sperner’s lemma to the Game of Y.

Chomp.

Chomp was invented in 1974 by David Gale. The game consists for an $n \times m$ grid of stones which we identify $\{ 1, 2, \dots, n \} \times \{ 1, 2, \dots, m \}$. Two players alternate taking turns. On a player’s turn they remove a stone $(x,y)$ and all stones $(x', y')$ with $x' \geq x$ or $y' \geq y$. That is, they remove all stones that are above or to the right of $(x,y)$. A player loses if they pick up the stone $(1,1)$. It’s clear that the game tree is finite, and the game can’t end it a draw. Thus, either the first or second player has a winning strategy.

Theorem: The first player always has a winning opening move.

If $(n,m)$ is a winning opening move, then we’re done. Otherwise, assume that the first player mistakenly plays it, and then the second player plays $(i,j)$. This move is a winning move since the second player played optimally. However, $n \geq i$ and $m \geq j$ so the first player could have played $(i,j)$ to the same (winning) effect.  So — The first player had a winning move, ie. $(i,j)$, all along.

This is a very nice, and somewhat tricky, proof. Usually strategy stealing arguments require some kind of monotonicity of moves to work. For example, in Hex, you have to check the (non-obvious) fact that placing a stone can’t hurt your position. In Chomp, however, this is built in to the structure of the game. This proof feels more ‘constructive’ than most non-constructive proofs.

The Game of Y.

The Game of  Y is a generalization of Hex invented by Ea Ea when he was a graduate student at The University of Michigan. It has some flaws, but it feels the game that should be considered the ultimate connection game. It’s elder sibling, Hex, however owns that title and also doesn’t suffer from such a strong first player advantage. Y is played on a triangular grid composed of hexagons. Players alternate taking turns placing stones of their colours on unoccupied hexagons. Whoever forms a group of stones which is connected to all three sides of the triangular board wins.

Theorem. When the board is completely filled with stones, at least one player has a winning connection.

Suppose not.  Order the sides of the board $\{1, 2, 3\}$. By hypothesis, each group of stones then has a well defined side of the board to which it is not connected. In particular each group has a least such side. Note that this gives a labeling of the hexgons in the triangular grid. This labelling is a Sperner labelling by construction. The vertex opposite side $1$ is labelled $1$, since that is already connected to sides $2$ and $3$. All hexagons along edge $1$ are labelled $2$ or $3$. We now apply Sperner’s lemma. We conclude that there is a triangle of pair-wise adjacent hexagons labelled $1, 2, 3$. By the pigeon hole principle, two of the stones are of the same colour. These two stones therefore belong to the same group, and have different labels, a contradiction.

This argument is from: Robert Hochberg, Colin McDiarmid, Michael Saks. On the bandwidth of triangulated triangles, Discrete Mathematics, 138 261-265 (1995).

Tagged with: , ,