Up (idea)

Up, written as an arrow pointing up, or in ascii as ^ (caret), is a value in combinatorial game theory. By convention, the two players in a combinatorial game are called Left and Right, and Left has a miniscule advantage in a game of value up. Symmetrically, the reverse of up, where Right has the advantage, is called Down, and is denoted by a downward-pointing arrow or a lowercase v.

In a game with value up, Left has a move to a game of value zero, while Right has a move to a game of value star. These must be the unique best moves available for each of the two players.

A simple example occurs in Domineering; the following position has value up:

   ====
   |  |
   =======
   |  |  |
==========
|  |  |
=======
   |  |
   ====

If it is Left's turn, she must place a vertical domino, and up to symmetry she has two options. She can either place the domino in the middle, leaving the following position with no moves for either player:

   ====
   |  |
   =======
      |  |
====  ====
|  |   
=======
   |  |
   ====

or she can place the domino toward the top or the bottom, leaving

      ====
      |  |
==========
|  |  | 
=======
   |  |
   ====

Since no one can play in the square that is all by itself, this turns out to have value * (see star for analysis).

On the other hand, if it is Right's turn, there is essentially only one move, which also leaves a corner tromino with value star and a single detached unplayable square.

So this game can be written diagrammatically as {0,*|*}, where the values to the left of the pipe are the values of the positions to which Left can move, while the values to the right are the values of the positions to which Right can move.

It turns out that although 0 and * are confused with one another, and in certain situations one might want to move to a * instead of a 0 position, that one never wants to move to the * from this game. Technically, we say that the option to * reverses out. This means that the unique best move for Left is to a position of value 0, while the unique best move for Right is to a position of value *, so this is in fact up.

Following is a clobber position, also of value up. Here Left's pieces are represented by X and Right's by O. A period denotes an empty square.

.....
.XXO.
.....

Now, the only move for Left is to

.....
.X.X.
.....

which has no move for either player, so has value zero. The only move for Right is to

.....
.XO..
.....

Here there is still one move for either player, but no more than that, and this position is easily seen to be {0|0}=*. So the original game has options of value 0 for Left and * for Right so itself has value up.

Positions of value up also occur in more common games such as chess and go but the analysis can be more complicated. Up also occurs in simple forms in hackenbush and konane.

One final note on up is that the value up is born on day 2, meaning that every option (0 and *) of up was born on or before day 1, and at least one of the options was born on day 1 exactly. This condition merits its own writeup, and will not be discussed further here. Suffice it to say that this makes up a very simple game; there are fewer than 30 games born by day 2.