Description

Impartial games are two player games, whose allowable moves depend only on the current state of the game, and not on the player whose turn it is. Although the games you are most familiar with probably do not fall into this class of games, there are many interesting games which do. For games where only a finite number of moves are possible, we can then ask which player should win from any given position, assuming both players know the ideal strategies. Furthermore, what exactly are the strategies we should follow to win? For certain games, these strategies can be described in terms of linear error correcting codes.

In general, an error correcting code describes a way in which messages can be encoded before being transmitted. The resulting message is resilient to changes which may occur during transmission. By this, we mean that the received communication can be correctly decoded, even when it contains some errors. Many different such codes exist, and the best code to use for any given task depends on the specific requirements of the situation.

In this project, we will begin by studying some examples of impartial games. We will learn how to describe the different positions of such games, and from this begin to develop strategies to win these games. We will see how the strategies for certain games may be described in terms of particularly interesting examples of error correcting codes, such as the Golay codes.

Piles of smarties, edited background colour This animation displays a basis for the extended binary Golay code using the geometry of the great dodecahedron. A picture of a mock turtle from Lewis Carroll's Alice in Wonderland, drawn by John Tenniel.
On the left we have some piles of sweets, representing a 7 pile mathematical heap game. In the middle, the extended binary Golay code is captured by the geometry of the great dodecahedron. On the right, a mock turtle from Alice in Wonderland, representing another impartial game.

Prerequisites

Algebra II is a prerequisite for this project. Those students who are also studying Cryptography and Codes III will likely find this helpful, though this is not a requirement.

Resources