We are concerned with Combinatorial Games (or Mathematical Games) consisting of two-player games with complete information (the players knows all the information about the game), no chance moves (no dice), a number of, usually finite many, positions, and the output is strictly win/lose or draw/draw. A play wins a game by making the last move in the normal play, and loses by making such a move in the misère play. A game is drawn if no player can win but there is always a next move available. Notice although "tied" and "drawn" are often used indiscriminately, it is suggested that "tied" mean a game is ended but nobody is winning by the rules, whereas "drawn" mean a game will not end. We usually use Left and Right to represent the first and second players. A game is impartial if every position is available to both players, otherwise it is partizan. Tic-Tac-Toe (Noughts-and-Crosses) is partizan but it fails to be a game because ties are possible. Ties are also available in Chess, but Go can only be drawn. Nim is an impartial game played with heaps of beans. each person chooses a pile and removes at least one bean, maybe all the beans, from the pile.

Here we only consider impartial games with finitely many positions (so the game will eventually end) in normal play convention.

If we follow the notations for mathematical games, each game G can be inductively defined as

G = { GL | GR }

where GL and GR are sets of Left and Right options. Further more,

-G = { -GR | -GL }, G + H = { GL + H, G + HL | GR + H, G + HR }

For impartial games, we always have GL = G R. So for nim heaps with 0, 1, and 2 beans, their values are

*0 = { | } = 0, *1 = {0 | 0} = *, *2 = {0, * | 0, *} = *2

respectively. For a nim heap of size n, its value will be

*n = { *0, *1,..., *(n-1) | *0, *1,..., *(n-1) }

It is obvious that the sum of two nim heaps of the same size is 0, namely first player loses, because whatever he does to a heap, the second player can simply mimic his move on the other heap. Eventually when there is nothing left, it will be the first player's turn, and he can only take the embarrassment of losing. Therefore any nim value is its own negative.

If we know the nim values of all the options of an impartial game, i.e.

G = { *a, *b, *c, *d,... | *a, *b, *c, *d,... }

then its value will be *m, where m = mex{a, b, c, d, ...}, the Minimal EXclusive value, is the least nonnegative integer that is not in the set {a, b, c, d, ...}. To see this, consider G + *m, the combination of game G and a nim heap of m beans. If the first player makes a move in G, say to *a. If a < m, then the second player can move from *m to *a, and thus the game becomes *a + *a = 0, and the first player loses. On the other hand, if a > m, by the definition of nim values, *a can be moved to *m, and the first player still loses. Now the only choice left is to move in the nim heap *m, but the result is the same. For any number *m' that he can move to, we must have m' < m and therefore m' is in G.

This inductively proved the Sprague-Grundy theorem [Sprague 1935-1936; Grundy 1939] which states that every position in an impartial game is equivalent to a Nim heap, and therefore the nim values are often referred as the values of the Sprague-Grundy (or Grundy) function. Finding the winning move from any position in an impartial game is the same as finding the next position whose value of Sprague-Grundy function is 0, because whichever position the next player moves to, the first player can move to another position whose value of Grundy function is 0. We call these positions P-positions (Previous player wins), otherwise N-positions (Next player wins). As a footnote, we mention that nim-addition is known as binary addition without carry, or XOR (exclusive or), e.g.

*2 + *3 = *1, *4 + *6 = *2

Some of my results on Chomp are available here, or maybe you want to try it first. You can also check my results on Wythoff's Game here. Unfortunately, there is no known website that hosts such a game online. Maybe I will write one once I get free. Do not hold your breath though.