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.

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.

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,

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.

i.e., the minimum among all g(q) such that qF(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

1. g(0) = 0, by defintion.
2. g(1) = 1 since F(1) = {0}. (This is position 0, the only one attainable from position 1.)
3. g(2) = 2 since F(2) = {0, 1}.
4. g(3) = 3 since F(3) = {0, 1, 2}.
5. 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.
6. 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

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

Note

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

Reference

1. E.R.Berlekamp, J.H.Conway, R.K.Guy, Winning Ways for Your Mathematical Plays, v1, A K Peters, 2001.
2. J.H.Conway, On Numbers And Games, A K Peters, 2001
3. 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
4. R.K.Guy, fair game, Comap's Explorations in Mathematics, 1989

Copyright © 1996-2008 Alexander Bogomolny