Becca's Introduction (Finally)

Almost each and every one of us has played some sort of game in our lives before. In addition, we have experienced a loss or a win during a game. Have you ever played someone in a game and it seems they just cannot lose? Well if may be this person has studied Combinatorial Game Theory at some point in his or her life.

This branch of applied mathematics is the study of a particular type of games. This typically involves two players and it is assumed that both players know all there is to know about how to play the game. In order to find a winning strategy, Game Theory becomes a means of determining such strategy. In other words, Game Theory takes on the task of finding how to beat even the best player (Demaine & Hearn).

In games studied in game theory, there are several distinctions commonly made. First, it is understood that in normal play, the winner of each game is determined by the last player to make a legal move. However, in what game theorists call miseré play, the goal of the game is reversed. Thus, the loser of the game is the last player to make a legal move (Demaine & Hearn). In addition, there is a clear distinction between impartial and partial games. Impartial games are when the same opportunities of moves are given to each player while partial games are when game play is not equal based on perspective of the players (i.e. chess is a partial game because each of the players are faced with different play opportunities at each turn) (Demaine & Hearn).

One particularly famous and well studied and relied upon Theorem in the field of Combinatorial Game Theory is the Sprague-Grundy Theorem. This states that every finite impartial game under normal play “is equivalent to an instance of the game Nim” (Demaine & Hearn). To better understand this, let us look at the game of Nim itself.

Nim, in normal play, is an impartial game, which is played with two players, A and B. Say there are three piles of objects with an arbitrary number of objects in each pile. The only condition of number of objects in the initial piles is that no pile may contain the same number of objects as another. Play begins and Player A may choose one pile in which he or she wishes to remove objects from. Player A can remove at least one and up to the entire pile. It is only necessary that from only one pile are objects removed in a single turn and at least one object is taken during a turn. After Player A removes a number of objects, it is Player B’s turn with the same conditions of play. The player with the last legal move wins. In other words, the player who removes the last object is declared the winner (Bouton). As mentioned earlier, in miseré play, the player who takes the last object is declared the loser of the game.