Surreal Numbers and Games/Games

From Wikibooks, open books for an open world
Jump to navigation Jump to search

Introduction[edit | edit source]

Suppose we have two players, call them Left and Right, playing some game with the following properties:

  • No element of chance or luck is involved
  • No information is hidden from either player
  • Players make legal moves alternately
  • Games cannot continue indefinitely; every legal move moves the game closer to a state where one or both players have no legal moves

Thus, Go is a game of this kind, as is chess or othello. But poker is not, because it has elements of luck and hidden information. Neither is football, because that too has elements of luck and play does not proceed as alternating moves.

At any stage of the game we can consider the situation to be the set of all legal moves available to Left (denoted by ), together with the set of all legal moves available to Right (denoted by . Every legal move Left has moves the game to simpler state, and similarly for Right. We denote the state of the game by .

The Domino Game[edit | edit source]

A good example of a game like this is the Domino Game. The game begins with a collection of squares joined at their sides in some configuration. Left removes one 2x1 (vertical) rectangle from the set, and Right removes a 1x2 (horizontal) rectangle. The first player not to have a legal move loses.

Consider the game consisting of only a single square, or no squares at all. Clearly neither player has a legal move, so the state of this game is . Does this look familiar? It should; it is the surreal number 0. Thus, here 0 indicates a first player loss; if it your turn to move, you lose. What about if we stared with a vertical 2x1 rectangle of squares? In that case, Left has a legal move and taking it reduces the game to one with no legal moves for anyone. Thus Left's set of legal moves is . Right has no legal moves at all, so this game is . This is the surreal number 1.

Exercise 1

Show that the game corresponding to a horizontal 1x2 rectangle is equal to the surreal number -1.

If we start instead with three squares arranged in an L shape, what do we get? Each player has one legal move, which reduces the game to one with no legal moves for anyone. It is therefore equal to . We briefly met this object on Day 1 of The Beginning and found that it is not a valid surreal number. It is a perfectly legitimate game, however, and corresponds to a first player win.

So far we have considered only cases where players have only one legal move or no moves at all. What if there is a choice to be made? Consider a tetris L-shape with its long edge vertical. If it is Left's turn to move, he can take the top two squares. That would be foolish, because then Right will take the other two squares and win, but it is nevertheless a legal move; -1 is one of Left's options. Or Left could take the corner. Then neither player has any legal moves; 0 is the other of Left's options. If it is Right's turn to move, she can only take the bottom two squares and leave Left to win by taking the other two. Her only option is 1, ie. Left victory. This game therefore corresponds to . We recognize this as the surreal number 1/2.

Exercise 2

Show that the game corresponding to a horizontal 1x4 rectangle is equal to the surreal number -2.