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 TicTacToe 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
Pposition  Nposition 
Every option leads to an Nposition  There is always at least one option that leads to a Pposition 
Pposition is good for the previous player, i.e. the one who has just made a move. Nposition 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 Pposition whereas 1, 2, 3, 5, 6,... are Npositions. In more rigorous notations, let p denote a generic position.
If P is the set of all Ppositions and N is the set of all Npositions, 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 SpragueGrundy 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: 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 lefttoright starting with 0 as above, we get successively
The value of a sum of several games is determined as the NimSum 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 where ^ is the standard XOR operation. In the theory of impartial games XOR is known under the alias of nimsum. The reason for such a usage becomes apparent from the theory of Nim. Furthermore, in analogy with (*), we have NoteScoring generalizes to a broader class of games  Subtraction Games. After you mastered Scoring, this would be a natural next step. Reference
Contact Front page Contents Games Copyright © 19962017 Alexander Bogomolny
