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

----------------

Miscellaneous other thoughts:

If pileSizeOne > pileSizeTwo >= pileSizeThree what pile should you take from?

Deduce that if there are winning moves that involve removing different numbers of stones, then
	pileSizeOne == pileSizeTwo > pileSizeThree
(as in example above)

Could record how many winning moves there are in each position by dependency

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?


----------------------------

Workshop plan:

Experiment / play with construal

	First use version of construal with no game mechanics: grasp rules of the game
	Second stage - add the binary represeentations
	Third stage - add the Nim-Sum extension
	
Familiarise with observables

	whose turn it is? have you finished your turn? have you cheated?
	whether won or not? who won?

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


Add restriction incrementally

How construal constructed
		
Many interface perspectives
	
To be done

[Concept - multiple choice questions with 'answers' given by definitions
	Provide an observable list sublist selector "Show observables"
	Scheme
		- every attempt at an answer costs
		- correct answers earn coins
		- correct answer may involve selecting text responses and definitions
		
	Use progressive disclosure of observables/definitions
]