Scoring: An Introduction Into The Theory Of Impartial Games

The game of Scoring is very simple: the board is a strip of several squares (parameter Heap size), on which there are placed several chips (whose number is controlled by the parameter # Counters). Taking turns with your computer you drag chips (one at a time) leftward until all are collected in the leftmost square. The last fellow to make a move wins. (The loser is the first unable to make a move. Are the two conditions really the same?) There is one more parameter (Max step) that determines the maximum allowed length of a single move.

With apologies, the Java is no longer supported by browsers. But the theory outlined below is still valid.

the game os Scoring

A game is impartial if, after a move, there is no way to tell which of the players made this move. Games that are not impartial are called partisan. Chess, checkers and Tic-Tac-Toe are not impartial. Scoring, as well as most of the games at this site, is.

Returning to the game of Scoring, let's solve first the simplest case of a single chip. Assume the maximum allowed move has length 3. I shall number the squares left to right starting with 0. Consider several starting positions (depending on the square occupied by our single chip at the beginning of the game.

Position	Comment

0	Nothing can be moved. The first player loses
1	The first player can win in a single move.
2	Ditto.
3	Ditto.
4	Any move by the first player leaves a position encountered before: whoever has the move can win.
5	There is one single good move for the first player (it's the one that leaves the chip at the square #4) such that regardless of the next (second) player's move, the first player will be able to win.
6	Ditto.
7	Ditto.
8	Any move of the first player leaves a position encountered before: whoever has the next move can win.

Etc. Thus we see that squares 0, 4, 8 are bad to start with while all other squares give you a chance to play a winning strategy. This observation leads to the standard definition:

P-position	N-position
Every option leads to an N-position	There is always at least one option that leads to a P-position

P-position is good for the previous player, i.e. the one who has just made a move. N-position is good for the next player, i.e. the one who is about to make a move. As we saw, positions 0, 4, 8,... are all P-position whereas 1, 2, 3, 5, 6,... are N-positions. In more rigorous notations, let p denote a generic position.

F(p) = {position: one can get from p into a single move}.

If P is the set of all P-positions and N is the set of all N-positions, then the definition is equivalent to

P = {p: F(p) ⊂ N}
N = {p: F(p) ∩ P ≠ Ø}

For the game of Scoring with a single chip, P = {k(MS + 1): k = 0, 1, 2, ...}, where MS is the value of the maximum step parameter. N = {{0, 1, ..., Length-1} - P}. Using modulo arithmetic,

(*)	P = {k: k = 0 (mod (MS + 1))} and N = {k: k > 0 (mod (MS + 1))}.

This completely solves Scoring with a single chip. Adding a chip introduces a new twist.

Indeed, if the two chips are placed on the same square then the second player may assure a win by simply repeating the moves of the first one. This is known as the Tweedledum & Tweedledee Principle. It shows, in particular, that the chips on the board could not be considered independently. Each chip might be looked at as defining a game of Scoring. Chips do not affect each other in the sense that for every chip p, F(p) does not depend on where other chips are located. So, in a sense, we are looking at a sum of several Scoring games. However, in the sum, individual games contribute to the new game while losing their identities.

The Tweedledum & Tweedledee Principle applies only in the case of two chips. However, it's strongly reminiscent of a situation that may arise in the game of Nim.

The general theory has been developed in 1930s by R.Sprague and P.M.Grundy. To describe it we have to define the Sprague-Grundy function. In a multichip game, position consists of several chips. However, F(p), the set of followers, i.e. positions that can be obtained from p with a single move, is well defined. Moving backwards, we define g(p) = 0 for the final position p where all the chips are collected on the leftmost square. Now continue recursively:

g(p) = Mex(g(q)), minimum excludent

i.e., the minimum among all g(q) such that q ∉ F(p). (Somewhat similar construction appeared in the Wythoff's Nim.) This is known as the Mex Rule.

As an example, for a single chip with the maximum step MS = 3 and positions numbered left-to-right starting with 0 as above, we get successively

g(0) = 0, by defintion.
g(1) = 1 since F(1) = {0}. (This is position 0, the only one attainable from position 1.)
g(2) = 2 since F(2) = {0, 1}.
g(3) = 3 since F(3) = {0, 1, 2}.
g(4) = 0 since F(4) = {1, 2, 3}. The values of g on F(4) are {1, 2, 3} and the minimum that does not appear there is 0.
g(5) = 1 since F(5) = {2, 3, 4}. The values of g on F(5) are {2, 3, 0} and the minimum that does not appear there is 1. Etc.

The value of a sum of several games is determined as the Nim-Sum of values of individual games. To determine g(p) assume p is the sum of games with the chips located on the squares p₁, p₂, ... Then

g(p) = g(p₁) ^ g(p₂) ^ ...,

where ^ is the standard XOR operation. In the theory of impartial games XOR is known under the alias of nim-sum. The reason for such a usage becomes apparent from the theory of Nim. Furthermore, in analogy with (*), we have

P = {p: g(p) = 0} and N = {p: g(p) > 0}.

Note

Scoring generalizes to a broader class of games - Subtraction Games. After you mastered Scoring, this would be a natural next step.

Reference

E. R. Berlekamp, J. H. Conway, R. K. Guy, Winning Ways for Your Mathematical Plays, v1, A K Peters, 2001.
J. H. Conway, On Numbers And Games, A K Peters, 2001
Aviezri S. Fraenkel, Scenic Trails Ascending From Sea-Level Nim to Alpine Chess, in Games of No Chance, R. J. Nowakowski, ed, MSRI 29, Cambridge Univ. Press, 1996
R. K. Guy, fair game, Comap's Explorations in Mathematics, 1989

71927398