Introductory Combinatorial Game Theory

Lesson 7 (Numbers)
As promised, we shall introduce the concept of numbers in combinatorial game theory. We have already seen the simplest example : 0 = { | }, where neither player has a valid move. Now we shall define 1 = {0 | }, i.e. a game in which the Left player has a single move, while the Right player has none. From here we may continue to define a game for any positive integer m: m = 1 + 1 + ... + 1, where the game 1 = {0 | } is repeated exactly m times in the summand. It is then easy to derive the following recursive notation: m + 1 = { m | }. Thus, in the spirit of Hackenbush, we have:



Similarly, we may define the negative numbers as -1 = { | 0} and -m = (-1) + (-1) + ... + (-1) (the game -1 is repeated m times), so that the corresponding Hackenbush games are:



Intuitively, if m is a positive integer, then the game m refers to a game in which player Left has m free moves while Right has no available moves at all. Similarly, -m refers to a game in which Right has m free moves while Left has no available moves.



Fractions


G
G + G + (-1)

Let us look at the Hackenbush configuration G above. If Left starts, he takes away the only blue edge leaving nothing behind. On the other hand, if Right starts, he takes away the top red edge leaving behind a single blue edge. Thus the game is denoted by G = { 0 | 1 }. It seems reasonable to take the average and say that the resultant game G = 1/2. Indeed, we shall justify this notation by noting that G + G + (-1) = 0, i.e. that the game above is a second-player-win. The proof for this is straight-forward (do it!).


H
H + H + (-1/2)

Similarly, consider the game H above. If player Left starts, he has only one possible move, which leaves a zero 0 = { | }. On the other hand, if player Right starts, he may leave either 1/2 or 1. On an intuitive level, a larger value means a larger advantage for Left, so Right should rightfully choose 1/2 (i.e. eliminate the topmost edge). Thus, the game is { 0 | 1/2, 1 } = {0 | 1/2} (later we shall prove rigourously that such an omission is indeed logically valid). Again, we may show that {0 | 1/2} + {0 | 1/2} + (-1/2) = 0, hence it makes sense to say {0 | 1/2} = 1/4. Hence, the above game sum may be written as :


In general, we may show that the H1 component of the above game is of value 2-n. This shall be done by induction: suppose we have already proven for the cases 1, 2, ... n-1. Now for the case of n, note that the game H1 may be written as { 0 | 20, 2-1, ... 2-(n-1) }, which by our omission principle, may be simplified to { 0 | 2-(n-1) }. Using our simplification, we may now show that the above combined game H1 + H2 + G = 0. Note that by our induction hypothesis, G = -2-(n-1). Our analysis of the game may be then divided into the following cases (note first that H1 > 0 because Left definitely wins):

  1. Left starts.
    1. If he makes a move in the G-component, then he may leave behind -1, -2-1, ... or -2-(n-2) in that component. By the omission principle described earlier, Left's best option is to leave -2-(n-2). Right may then respond with a move from H2 to 2-(n-1). The game sum is now H1 + 2-(n-1) - 2-(n-2) = H1 + G. We shall look at this game instead.
      1. If Left makes a move at G, his best choice is to leave -2-(n-2). Right may now respond in H1, giving 2-(n-1). The game sum is now 2-(n-1) + 2-(n-1) - 2-(n-3) < 0, hence Right wins.
      2. If Left makes a move at H1, he must leave 0 behind. The game sum is now simply G < 0, hence Left was penalizing himself by making such a move.
    2. If Left makes a move in the H1 component , he must leave behind 0. Right now responds with a move at H2, leaving 2-(n-1). The game sum is now zero, and it's Left's turn. Hence Right is headed for a win.

  2. Right starts.
    1. If Right starts with a move at G, he leaves a zero game behind, and the sum is H1 + H2 > 0. So Left wins.
    2. If Right starts at H1, his best move is to remove the topmost edge, leaving behind 2-(n-1) = -G. The game sum is now (-G) + H2 + G = H2 > 0. Hence Left wins.

In short, we have { 0 | 2-m } = 2-(m+1) for all positive integers m.



Simplifying Expressions

As we have used umpteen earlier, simplistically speaking, if G > H, then G is more advantageous to Left than H. Conversely, if G < H, then G is more advantageous to Right than H. Consider the following game with options: G = { V, W, X | Y, Z }. Suppose W >= X. Then player Left prefers scenario W to X, hence we may drop X from the above expression to give G = { V, W | Y, Z }. Similarly, if Y <= Z, we may drop Y from the expression to give G = { V, W | Z }. We shall now rigourously prove this, i.e. if W >= X, then

{ V, W, X | Y, Z } - { V, W | Y, Z } = { V, W, X | Y, Z } + { -Y, -Z | -V, -W } = 0.

Again, we may perform the analysis on a case-by-case basis:

  1. Suppose Left starts.
    1. If Left's move is V, W, -Y or -Z, then Right promptly responds with a move in the other component: -V, -W, Y or Z to give a zero game. Hence, Left wins.
    2. If Left's move is X, then Right may respond with -W in the other component to give a non-positive game sum: X - W <= 0. Since Left starts, Right can win.

  2. Suppose Right starts.
    1. If Right's move is Y, Z, -V or -W, then Left responds with -V, -W, Y or Z to give a zero game. Left wins.


Let us look at another form of simplification: reversible moves in a game. Suppose again we have the game G = { V, W, X | Y, Z }, where Right’s move to Y is reversible. What this means is that from Y, player Left has a move (to, say, D) which is at least as good for him as G (i.e. D >= G). When that happens, we may replace option Y with all the right options of D. The following diagram graphically depicts the process:


Note that we cannot delete a reversible move, rather we replace a reversible move by the relevant options. Let us now supply the necessary proofs, for the claim G = { V, W, X | P, Q, R, Z }, or in other words,

{ V, W, X | Y, Z } + { -P, -Q, -R, -Z | -V, -W, -X } = 0.


  1. Suppose Left starts.
    1. If Left's move is V, W, X or -Z, then Right responds in the other component: -V, -W, -X or Z to give a zero game. Right wins.
    2. Suppose Left's move is -P (say), leaving behind an overall sum G-P in which Right gets to start. The analysis is then a little tricky. Since G + (-D) is a non-positive game, Right wins if Left gets to start. In particular Right wins if Left makes a move in component -D, leaving -P. Hence, in the game G-P, if Right starts first, he gets to win.

  2. Suppose Right starts.
    1. If Right's move is -V, -W, -X or Z, Right retaliates with V, W, X or -Z to give a zero game and wins.
    2. If Right's move is Y, then Left responds with D. After that Right's options of P, Q and R may be countered with -P, -Q and -R respectively.

At first glance, it seems this process only serves to complicate matters by introducing more options, but these options are all much simpler than the initial one. Hence we may apply the first principle to remove redundant options. We may now summarize our above simplification techniques here:

  1. If player Left has options W and X such that W >= X, then we may delete X from the list of options. Similarly, if player Right has options Y and Z such that Y >= Z, then we may delete Y.

  2. Suppose player Right's move to Y, is such that Left can respond with D with D >= G, then we may replace Y with all of Right’s options from D. Similarly, if player Left's move to W, is such that Right can respond with E where E <= G, then we may replace W with all Left's options for E.





Back to the main page...