Exercises with Nim

Key observables:

	activePile, pileSizeOne, pileSizeBinaryStringOne, pile1able
	pileSizeMax (why do we want to know this?) - consider dependency map 'pileSizeMax|nimSumLength|pileSizeOne'

Aim of the game is to be the player who removes the last stone

Confirm that in a position with two piles of equal size you are lost with best play

Understand the Nim-Sum

Realise that when there are 2 piles of equal size, the player with the move wins

A. The number of stones to be removed in making a winning move is the number whose binary representation is the Nim-Sum. Consider, for instance:

5 6 7

101
110
111
===
100 [= binary rep of 4]

Can take 4 away from any one of the piles to get a winning position, and these are the only winning moves.


B. Once you know the number of stones to be removed in a winning move, you can take them from any pile that is large enough.

This was true of the example above, but is false in general. Consider:

4 6 7

100
110
111
===
101 [= binary rep of 5]

Take 5 from the 7, and this leaves Nim-Sum 0:

100
110
010
===
000

Take 5 from the 6, and the Nim-Sum is non-zero

100
001
111
===
010



C. There may be two or more winning moves, and these do not necessarily involve removing the same number of stones.

3 6 6 --> 0 6 6 wining position - have removed 3 coins. Cam also play 3 6 6 --> 3 5 6, removing only one coin.

011
110
110
===
011 [= binary rep of 3]

011
101
110
===
000

Automate a player - what action would you use for this?

Consider [as in think about] a variant of Nim-Coin where
	a. the denominations of the coins can be different
	b. the rules for removing coins are the same (i.e. don't depend on the value of the coin)
	c. you can exchange the coins in a pile for a combination of fewer coins with the same value before taking your turn
	
Does this variation affect what positions are one and lost?

1 5 4 --> 1 1=<5> 4 --> 1 1 0

is valid move that leads to a winning position

But 

001
101
100
===
000

is otherwise a losing position

What observables would we need to change to implement this?