Game Theory

References

Cite

Share

Abstract

This paper is an exploration of game theory. We will focus on combinatorial games and the strategies players may use within the game. In section 2, we will define concepts essential to our study of combinatorial games. We will then explore normal-play games and broad generalizations we can make of all such games in section 3. In section 4, we explore a game called Nim and the Sprauge-Grundy theorem, which allows us to explore an important property of impartial games. 1. Combinatorial Games 1.1. Combinatorial Games. Definition 1.1. A combinatorial game is a game played between 2-players, Louise and Richard. The game consists of the following: (1) A set of possible positions. These are the states of the game (e.g. the starting board of a chess game). (2) A move rule indicating what positions Louise can move to and what positions Richard can move to on their turn. (3) A win rule indicating a set of terminal positions where the game ends. Each terminal position has an associated outcome, either Louise wins and Richard loses (denoted +-), Louise loses and Richard wins (-+), or the game is a draw (00). To play a combinatorial game, a starting position is chosen with a designated player making the first move. The starting position indicates how the game will look like before it is played. Then, the two players alternate in making moves until a terminal position is reached, indicating the end of the game. A terminal position is reached when one of the two players has won the game or when no possible moves can be made and the game ends with a draw. Combinatorial games may range from simple games such as Tic-Tac-Toe to more complicated ones such as Chess. However, these games have no element of randomness, so games such as Monopoly that require the use of a dice or a spinner are not considered to be combinatorial games. Combinatorial games thus rely on the player’s strategy and moves to win, whereas games with probabilistic elements depends on chance and not wholly in the player’s strategy. Example. A common combinatorial game is Pick-Up-Bricks. In this game, a pile of bricks is placed in the center. Each move consists of a player removing 1 or 2 bricks from the pile. The game ends when the pile is empty, and the last player to take a brick wins. 1.2. Game Trees. A game tree is a helpful tool to diagram combinatorial games. A branch is a line that connects two nodes, and each branch represents a player’s move. The point that branches connect are called nodes, and each models a new state of the game. Terminal nodes ones that only have one branch connecting it to another node indicate the possible outcomes. 1 2 JENNIFER YUAN AND SHREYA SINHA Figure 1. Pick-Up-Bricks The topmost node is called the root node, and represents the beginning state of the game. Each branch node is annotated with an L or an R to indicate whose turn it is to play, with L for Louise and R for Richard. Figure 2. Game Tree Of A Tic-Tac-Toe Game Row The depth of a game tree is defined as the maximum number of possible moves from the start to the end of the game (i.e. the longest path from the root node to a terminal node). The path that leads to decisive victory for a player may be called a winning strategy, and ones that lead to a draw outcome is called a drawing strategy.s The power of game tree lies in the fact that it allows us to diagram all possible combinatorial games regardless of how they are played or any other detail specific to them. This allows us to explore broad properties of games, as we will see in the next section. 1.3. Zermelo’s Theorem. An important theorem relating to combinatorial games is Zermelo’s Theorem, which states that in all such games, either Louise has a winning strategy, Richard has a winning strategy, or both players have a strategy that guarantees a draw. There are no combinatorial games in which one player doesn’t have a winning strategy or the game cannot end in a draw definitively. The power of this theorem is not very intuitive, because it means there exists a winning or drawing strategy in games like chess, where people play professionally. Of course, the reason chess is still played is because there are so many possible positions a player can reach within the game that we have no way of documenting all of them, and no way of finding that strategy at the moment.