(17B) NIM - Printable Version +- HP Forums ( https://www.hpmuseum.org/forum)+-- Forum: HP Software Libraries ( /forum-10.html)+--- Forum: General Software Library ( /forum-13.html)+--- Thread: (17B) NIM ( /thread-1826.html) |

(17B) NIM - Thomas Klemm - 07-13-2014 08:39 PM
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):` 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^{i}.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 ^{i} XOR 2^{j} = 2^{i} + 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. |