(17B) NIM

[Thomas Klemm]

This implementation of the strategy game Nim is how it was played in the film L'Année dernière à Marienbad using 4 heaps with 1, 3, 5 and 7 objects (e.g. matches or coins).
However it is not played using the misère game condition.

It's a boring game: you always have to start. The calculator always wins.

Code:

NIM:IF(S(INIT):
10×(10×(10×L(A:1)+L(B:3))+L(C:5))+L(D:7)-INIT:
0×
L(E0:MOD(A+
  L(B0:MOD(B:2))+
  L(C0:MOD(C:2))+
  L(D0:MOD(D:2)):2))×
L(E1:MOD(
  L(B1:B-G(B0))+
  L(C1:MOD(C-G(C0):4))+
  L(D1:MOD(D-G(D0):4)):4))×
L(E2:MOD(
  L(C2:C-G(C0)-G(C1))+
  L(D2:D-G(D0)-G(D1)):8))×
IF(L(E:MOD(G(D0)+G(E0):2)+MOD(G(D1)+G(E1):4)+MOD(G(D2)+G(E2):8))<D:
  L(D:G(E)):
IF(L(E:MOD(G(C0)+G(E0):2)+MOD(G(C1)+G(E1):4)+MOD(G(C2)+G(E2):8))<C:
  L(C:G(E)):
IF(L(E:MOD(G(B0)+G(E0):2)+MOD(G(B1)+G(E1):4)+G(E2))<B:
  L(B:G(E)):
IF(L(E:MOD(G(A)+G(E0):2)+G(E1)+G(E2))<A:
  L(A:G(E)):INV(0)))))+
10×(10×(10×A+B)+C)+D-EVAL
)

The game is started by pressing [INIT]. It should display CALCULATING... and then INIT=1357
Now you can change one of the values of A, B, C or D. Then press [EVAL] to see the new values of the heap.

Example:
[INIT]
INIT=1357

6 [D]
D=6
[EVAL]
EVAL=1346

3 [C]
C=3
[EVAL]
EVAL=1331

2 \([\)B]
B=2
[EVAL]
EVAL=1230

0 [A]
A=0
[EVAL]
EVAL=220

0 \([\)B]
B=0
[EVAL]
EVAL=0

If you wanted to play using the misère game condition the last move would have just taken 1 object from heap C.

Explanation of the equation:
The 4 variables A, B, C and D are split into sums of powers of 2. You may think of a binary representation. However as we can use the restrictions A≤1, B≤3, C≤5 and D≤7 we only need:

A = A
B = B0 + B1
C = C0 + C1 + C2
D = D0 + D1 + D2

The X_i are either 0 or 2ⁱ.

We want to calculate the expression: A XOR B XOR C XOR D.
Instead we calculate: (A XOR B0 XOR C0 XOR D0) + (B1 XOR C1 XOR D1) + (C2 XOR D2)
We can do that since 2ⁱ XOR 2^j = 2ⁱ + 2^j if i ≠j.
But in this case we can replace XOR by + and MOD.
Thus we get:

E0 = A XOR B0 XOR C0 XOR D0 = (A + B0 + C0 + D0) MOD 2
E1 = B1 XOR C1 XOR D1 = (B1 + C1 + D1) MOD 4
E2 = C2 XOR D2 = (C2 + D2) MOD 8

Now we have to find X where X XOR (E0 + E1 + E2) < X. Otherwise that would not be a legal move. We use the same trick again and calculate (X0 XOR E0) + (X1 XOR E1) + (X2 XOR E2) instead. As before XOR can be calculated using + and MOD:

E = (X0 + E0) MOD 2 + (X1 + E1) MOD 4 + (X2 + E2) MOD 8


Attachment:
The zip-file contains a state-file for Emu42.