# 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.

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 *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 *p*revious player, i.e. the one who has just made a move. *N*-position is good for the
*n*ext 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.

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

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

For the game of Scoring with a single chip,

(*) |
P = {k: k = 0 (mod (MS + 1))} and |

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:

*m*inimum

*e*xcludent

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_{1}, p_{2}, ... Then

_{1}) ^ g(p

_{2}) ^ ...,

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

- 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

|Contact| |Front page| |Contents| |Games|

Copyright © 1996-2018 Alexander Bogomolny

65256069 |