Surreal Number - Application To Combinatorial Game Theory

Application To Combinatorial Game Theory

The surreal numbers were originally motivated by studies of the game Go, and there are numerous connections between popular games and the surreals. In this section, we will use a capitalized Game for the mathematical object {L|R}, and the lowercase game for recreational games like Chess or Go.

We consider games with these properties:

• Two players (named Left and Right)
• Deterministic (the game at each step will completely depend on the choices the players make, rather than a random factor)
• No hidden information (such as cards or tiles that a player hides)
• Players alternate taking turns (the game may or may not allow multiple moves in a turn)
• Every game must end in a finite number of moves
• As soon as there are no legal moves left for a player, the game ends, and that player loses

For most games, the initial board position gives no great advantage to either player. As the game progresses and one player starts to win, board positions will occur where that player has a clear advantage. For analyzing games, it is useful to associate a Game with every board position. The value of a given position will be the Game {L|R}, where L is the set of values of all the positions that can be reached in a single move by Left. Similarly, R is the set of values of all the positions that can be reached in a single move by Right.

The zero Game (called 0) is the Game where L and R are both empty, so the player to move next (L or R) immediately loses. The sum of two Games G = { L1 | R1 } and H = { L2 | R2 } is defined as the Game G + H = { L1 + H, G + L2 | R1 + H, G + R2 } where the player to move chooses which of the Games to play in at each stage, and the loser is still the player who ends up with no legal move. One can imagine two chess boards between two players, with players making moves alternatively, but with complete freedom as to which board to play on. If G is the Game {L | R}, -G is the game {-R | -L}, i.e. with the role of the two players reversed. It is easy to show G - G = 0 for all Games G (where G - H is defined as G + (-H)).

This simple way to associate Games with games yields a very interesting result. Suppose two perfect players play a game starting with a given position whose associated Game is x. We can classify all Games into four classes as follows:

• If x > 0 then Left will win, regardless of who plays first.
• If x < 0 then Right will win, regardless of who plays first.
• If x = 0 then the player who goes second will win.
• If x || 0 then the player who goes first will win.

More generally, we can define G > H as G - H > 0, and similarly for <, = and ||.

The notation G || H means that G and H are incomparable. G || H is equivalent to G−H || 0, i.e. that G > H, G < H and G = H are all false. Incomparable games are sometimes said to be confused with each other, because one or the other may be preferred by a player depending on what is added to it. A game confused with zero is said to be fuzzy, as opposed to positive, negative, or zero. An example of a fuzzy game is star (*).

Sometimes when a game nears the end, it will decompose into several smaller games that do not interact, except in that each player's turn allows moving in only one of them. For example, in Go, the board will slowly fill up with pieces until there are just a few small islands of empty space where a player can move. Each island is like a separate game of Go, played on a very small board. It would be useful if each subgame could be analyzed separately, and then the results combined to give an analysis of the entire game. This doesn't appear to be easy to do. For example, you might have two subgames where whoever moves first wins, but when they are combined into one big game, it's no longer the first player who wins. Fortunately, there is a way to do this analysis. Just use the following remarkable theorem:

If a big game decomposes into two smaller games, and the small games have associated Games of x and y, then the big game will have an associated Game of x+y.

A game composed of smaller games is called the disjunctive sum of those smaller games, and the theorem states that the method of addition we defined is equivalent to taking the disjunctive sum of the addends.

Historically, Conway developed the theory of surreal numbers in the reverse order of how it has been presented here. He was analyzing Go endgames, and realized that it would be useful to have some way to combine the analyses of non-interacting subgames into an analysis of their disjunctive sum. From this he invented the concept of a Game and the addition operator for it. From there he moved on to developing a definition of negation and comparison. Then he noticed that a certain class of Games had interesting properties; this class became the surreal numbers. Finally, he developed the multiplication operator, and proved that the surreals are actually a field, and that it includes both the reals and ordinals.