Robotics Reference
In-Depth Information
position
Pile A 6
Pile B 4
Pile C 3
Pile D 2
the binary representations
12
of the numbers in each pile are
Pile A 110
Pile B 100
Pile C 011
Pile D 010
The next step of the algorithm is to add each column of binary numbers,
but to write the totals as decimal numbers, which gives us
Total of first column
=
1
+
1
+
0
+
0
=
2
Total of second column
=
1
+
0
+
1
+
1
=
3
Total of third column
=
0
+
0
+
1
+
0
=
1
The algorithm specifies that if all the totals are even numbers, then the
player who moves next will lose, assuming correct play by both sides.
13
But if all the totals are not even numbers, as is the case here, then the
player who moves next can win if (s)he finds the correct move. (The
winning play is to remove all 3 matches from pile C, leaving the config-
uration 6, 4, 2, which is a loss for the player who must make the next
move.) If no move exists that leaves all the column totals even, then it is
not possible to play a move that guarantees a win. In this case the best
play is probably to remove a single match from the largest pile, thereby
giving your opponent the most complex choice possible and hence max-
imizing his chances of making a mistake.
Because there is an algorithm for finding the correct move, perfect
play in Nim can be “programmed” quite easily. But the Nimotron was
not a programmable machine so the “programming” had to be accom-
plished using relays. There was a lamp corresponding to each “match”
12
For those readers unfamiliar with binary numbers, the binary 110 of pile A represents: 1
2
2
×
+
2
1
2
2
1
0,
etc
13
There is an exceptional case. If all the remaining piles have one match each, the next player to
move will lose if the decimal total is odd and will win if the total is even.
×
+
0
=
4
+
2
+
0. The binary number 100 in pile B represents: 1
×
+
0
+
0
=
4
+
0
+
