The G-values of various games

Extract

A disjunctive combination of a finite set of two-person games Γ₁, Γ₂, …, Γ_k may be defined thus: The players play alternately, each in turn making a move in one and only one of the individual games. If, in addition, the conditions are imposed that

(i) a player loses if unable to move (in any game),

(ii) the games are impartial, i.e. the allowable moves from any position do not depend on which player is about to play (or on the previous moves, though these can be ‘built in’ to the position if necessary),

(iii) the games are of bounded play, i.e. for each game Γ_i corresponding to any initial position P_j there is an integer b_ij such that the game must terminate after at most b_ij moves, then Grundy (6) has shown that there is a function G(P) (called by him Ω(P)) of the positions P with the following properties:

(1a) G(P) = 0 for a terminal position, from which no move is possible; for other positions G(P) is the smallest non-negative integer different from all values of G(Q_i), where there is a permissible move from P to Q_i,

(1b) for a disjunctive combination of games, G for the combined position is the nim-sum of the G's the individual positions. By the nim-sum, we mean that each separate G is to be written in the scale of 2, as Σa_r 2^r, and then in forming the sum, the a_r's are to be added mod 2 for each value of r, as in the theory of Nim((1), (7), (8), pp. 36–8).