Nim: The Ultimate Binary Game
Jim Butterfield, Associate Editor
The Best way to beat the computer in this classic strategy game is to know how to convert numbers from decimal to binary. The accompanying program was written in Commodore BASIC and runson any Commodore eight-bit computer. With minor modifications, it could also be adapted to work with other versions of Microsoft BASIC.
"Nim" is one of the simplest games ever invented, yet successful play requires at least an intuitive grasp of binary numbers, the system used by all digital computers.
Here‘s how Nim is played. You take a bunch of objects (toothpicks, matches, coins, whatever) and arrange them randomly in three or more piles. You and your opponent alternate taking turns. During a turn, a player may take as many objects as he or she wishes from any one pile (but only from one pile). The player taking the last object wins.
That‘s a description of the standard game of Nim. Several variations exist. In one variation, the player taking the last object loses. In another, there is a maximum number of objects that may be taken during a turn. The program presented here plays all three versions of the game, switching the rules from one game to the next. Type the program in and save a copy before you run it. The program should run as listed on any eight–bit Commodore computer, and with minor modifications on any eight–bit computer.
Simple Play Theory
The classic game of Nim (last object wins, pick any number) has a very elegant playing strategy that requires knowledge of binary numbers. (If you are not familiar with the binary numbering system, see "From Decimal to Binary," accompanying this article.)
Count the number of objects in each pile, and write down each number, one above the other, in binary. For example, if there are three piles of objects, containing three, four and five objects, respectively, you would write
3 1 1 4 1 0 0 5 1 0 1
Note that the binary numbers are lined up on the right side, just as we would arrange conventional numbers. Now, you should ask, does every column (not row) have an even number of 1's in it?
If the answer is yes, you're stuck. The best you can do is make some random move and hope your opponent stumbles when he or she plays.
But if the answer is no, you have a winning play. The play is to take from a pile in such a way so that all columns have even parity— an even number of 1's.
Let's look at the example given above. The right column has two bits set, so that's even parity. The middle column has only one bit set. That's an odd number, so you have a winning play.
It takes some time, at first, to examine the possible moves. In this case, it turns out there's only one move that produces even parity. Here's the move: Take two from the first column, leaving
1 1 4 1 0 0 5 1 0 1
Examine the columns of the binary numbers, and you'll see that they all contain an even number of bits (zero or two in this case). Your opponent now has no satisfactory play.
Let's carry this game through to its conclusion. Suppose your opponent takes four objects from the largest column, leaving one. Line up the numbers again:
1 1 4 1 0 0 1 1
Your play to restore even parity is obvious. Grab the entire pile of four to leave:
1 1 0 0 1 1
What can your opponent do now? Not much. On the next turn, he or she must take the lone piece from either one of the piles, after which you will take the last object from the remaining pile and win.
Variations
The classic game has a clear and easy strategy. The task becomes more complex when we limit the number of objects that may be taken on each play. Extra difficulties arise when we decide that the player taking the last object will lose instead of win. But the basic game strategy remains, built upon a foundation of binary numbers.
I won't go into the extra theory and strategy here. If you're interested, you can examine the program to see what makes it such a good player.
The Good And The Bad
You might find it dull to play against a computer that wins every time, so the computer has been given an IQ. The computer asks at the beginning of the game if it should play the best it can. If you you reply N for no, it will sometimes make mistakes, giving even an inexperienced player a chance to win.
Even if you don't know binary, you can become skilled at this game—you'll begin to spot winning combinations. Be forewarned: Every time the computer loses a game, it becomes a better player. So the next game may not be as easy.
Eventually, if you master the theory of play, you will be able to beat the computer every time. That's because the computer, after setting up a random board, asks you whether you want the first move. If you have a good play, take the first move and make it. If you don't seem to have a good move, pass the first move to the computer.
Program Notes
One odd expression in the program implements exclusive OR. Unlike the standard OR operator, exclusive OR is true only when one operand is true and the other is false (the standard OR is also true when both operands are true). Exclusive OR can be simulated with the AND, OR, and NOT operators:
X = (A OR B) AND NOT(A AND B)
If your specialty is machine language, the 6502 processor has an exclusive OR (EOR) command built in.
If you are interested in figuring out how the program works, you'll need to understand the roles of some variables. R is the playing rule—if it is 1, the last player wins, if it is 0, the last player loses. N9 is the maximum number of objects you are allowed to pick up. If you are allowed to choose any number of objects, N9 is set to 99.
From Decimal To Binary
The binary numbering system is used by computers because each bit—the smallest unit of storage in a computer's memory—can have only two states, 0 or 1. These two states correspond to the off and on states of the electronic switches that make up the brain of the computer. Just as it is easy for us to do decimal (base 10) math with our fingers, so it is easy for computers to do binary (base 2) math.
The binary and decimal systems are just two different ways of looking at the same thing: numeric quantities. Instead of saying, "Look! There are seven (base 10) trees," we could just as correctly state, "Look! There are 111 (base 2) trees." The trick is learning how to convert from one base to another.
Perhaps the simplest way to convert from base 10 to base 2 is to construct a value box (at first on paper, but eventually in your head). Here's a value box that will convert numbers from 0 to 255 in decimal.
Now let's pick a number to be converted. We'll use 20.
Going from left to right, find the first number in the value box that is less than or equal to 20. In this case, the number is 16. Color in the box under the number 16.
We have represented 16 of the 20 objects that we wish to represent. Subtract 16 from 20—we have 4 more objects to represent. Continue scanning across from left to right. We pass 8, but since 4 is less than or equal to 4, we color in the box under the 4, When we subtract 4 from 4, we get 0, so we have now completed our conversion. All of the empty boxes represent 0s, and all of the filled boxes represent 1s. The result is 00010100. We can write binary numbers without leading zeros (those to the left of the first significant digit), so decimal 20 is 10100 in binary.
The array A() holds the playing board. P() is the original (previous) board, in case you want to play the same game over again. S() is a scrambling array, to give the computer's strategy a little variety. If the computer player has more than one possible winning move, it might pick either one, depending on the contents of S().
Playing Against Humans
If you play this game against another person, remember that psychology is an important part of your playing style. You should make your moves without hesitation if possible. This is especially true when you don't have a winning move—you don't want to tip off your opponent that you may be in trouble.
And don't take a piece of paper and start writing out numbers in binary. Learn to do it in your head. It's a good step to computer literacy.
Nim
For instructions on entering this program, please refer to "COMPUTE!'s Guide to Typing In Programs" elsewhere in this issue.
XQ 100 PRINT"{CLR}{2 DOWN}" : PRINT TAB(17)" "{RVS} NIM"
KE 110 J = RND (-T1)
ED 120 DIM A(5), P(5), S(5), N(5)
JK 130 FOR J = 1 TO 4 : S(J) = J : NEXT J
ME 140 H$ = "{HOME}{13 DOWN}"
EG 150 C$ = H$ + "{35 SPACES}" + H$
EP 160 PRINT CHR$(8);CHR$(142)
RH 170 PRINT"RULES : "
MG 180 PRINT"{2 SPACES} EACH PLAYER PICKS AS MANY ITEMS"
SG 190 PRINT"{2 SPACES} AS DESIRED FROM ANY ONE ROW"
HD 200 PRINT
GF 210 PRINT"THE WINNER IS THE PLAYER WHO PICKS"
RB 220 PRINT"THE LAST ITEM."
PG 230 PRINT
ED 240 PRINT"WE EACH PALY IN TURN."
DH 250 PRINT
PX 260 X$ = "N" : INPUT "SHOULD I PLAY MY BEST GAME" ;X$
QE 270 I = .5 : IF X$ = "Y" OR X$ = "YES" THEN I = 1
HK 280 PRINT
CD 290 IF I = 1 THEN PRINT"PUNY {SPACE} HUMAN1{2 SPACES} YOU HAVEN'T A HOPE."
XX 300 IF I < 1 THEN PRINT"MAYBE I'LL LET YOU WIN ONE OR TWO GAMES.
FC 310 FOR J = 1 TO 500 : NEXT
RK 320 R = 1 : N9 = 99
CB 330 T = 0
HQ 340 FOR J = 1 TO 4
XC 350 A(J) = INT (RND(1) * 7 : T = T + A(J)
XR 360 NEXT J
PS 370 IF T < 4 THEN 330
EB 380 FOR J = 1 TO 4
BA 390 P(J) = A(J) : K = INT(RND(1) * 4) + 1
DG 400 NEXT J
BG 420 M = 0 : M0 = 0
MH 430 PRINT"{CLR}{DOWN}PLAYER TAKING LAST ITEM";
SS 440 IF R = 0 THEN PRINT "LOSES"
DB 450 IF R = 1 THEN PRINT "WINS"
CE 460 PRINT
GF 470 IF N9 = 99 THEN PRINT "PICK AS MANY AS YOU LIKE"
EQ 480 IF N9<99 THEN PRINT "YOU MAY PICK NO MORE THAN" ;N9
SH 490 PRINT
XJ 500 R9 = 0 : T6 = 0 : T8 : T9 = 0
SG 510 FOR J = 1 TO 4
EB 520 PRINT CHR$ (J + 64); " : ";
FQ 530 FOR K = 1 TO 9
PR 540 C = 209 : IF K>A(J) THEN C = 32
PF 550 PRINT CHR$(C);"";
MM 560 NEXT K
JE 570 PRINT : PRINT
RM 580 K = S(J)
MB 590 N = INT (A(K) / (N9 + 1)) : N(K) = A(K) - N * (N9 + 1)
KJ 600 IF N(K) = 1 THEN T8 = T8 + 1 : T3 = K
QF 610 IF N(K)>1 THEN T9 = T9 + 1 : T4 = K
DF 620 IF A(K)>T6 THEN T6 = A(K) : T5 = K
DR 630 NEXT J
BB 640 IF M>0 THEN 680
PE 650 PRINT C$;
JF 660 X$ = "N" : INPUT" DO YOU WANT THE FIRST MOVE";X$
BM 670 IF X$ = "Y" OR X$ = "YES" THEN M0 = 1
RF 680 M = M + 1 : IF M0 = 1 THEN 900
QJ 690 T = 0
EM 700 IF R = 1 THEN 770
KC 710 IF T9 = 0 AND T8 = 0 THEN 800
QC 720 J12 = T3 : IF T9>0 THEN J1 = T4
JA 730 X = N(J1) : IF T8 = INT (T8/2) * 2 THEN X = X - 1
AX 740 IF X = 0 THEN 770
BJ 750 IF T9<2 THEN 870
BE 760 REM CONVENTIONAL ANALYSIS
RK 770 FOR J = 1 TO 4
KJ 780 T = (T OR N(J)) AND NOT (TAND N(J))
BJ 790 NEXT J
JR 800 IF J1 = T5 : X = T6 : IF X>N9 THEN X = N9
HC 810 IF T = 0 THEN 870
EM 820 FOR J = 1 TO 4
KK 830 K = S(J)
BM 840 TO = (T OR N(K)) AND NOT (T AND N(K))
EF 850 IF TO <N(K) AND (N(K) - T0)<N9 THEN J1 = K : X = N(K) - T 0
AQ 860 NEXT J
KX 870 IF RND (1)>I THEN X = INT(RND(1) * T6) + 1 : J1 = T5 : IF X>N9 THEN X = N9
BK 880 PRINT C$; "I TAKE&rdqup; ;X; "FROM ROW";CHR$(J1 + 64)
GP 890 GOTO 1000
EE 900 PRINT C$;"CHOOSE A ROW {SPACE} (OR {RVS} G{OFF} TO GIVE UP) : ";
XE 910 GET X$ : IF X$ = "" THEN910
KX 920 IF X$ = "G" THEN MO = R : GOTO 1140
HC 930 J1 = ASC(X$) - 64 : IF JL<1 OR J1>4 THEN 900
HG 940 IF A (J1) = 0 THEN 900
FS 950 PRINT C$;"HOW MANY FROM ROW"CHR$(64 + J1);" : &rdqup; :
BX 960 GET X$ : IF X$ = "&dquo; THEN 960
BB 970 X = ASC(X$) - 48 : IF x<0 OR {SPACE}X>9 THEN 960
GP 980 IF X = 0 OR X>A(J1) OR X> N9 THEN PRINT "????" : FOR J = 1 TO 500 : NEXT : GOTO 900
CK 990 PRINT X
EE 1000 PRINT "{HOME} {2 DOWN}"
FJ 1010 FOR K = 1 TO JI : PRINT : PRINT : NEXT K
CX 1020 PRINT TAB (3);
BS 1030 FOR K = 1 TO X : PRINT " - "; : NEXT K
JK 1040 A(J1) = A(J1) - X
GG 1050 T = 0
PX 1060 FOR J = 1 TO 4
FR 1070 IF A(J) < > 0 THEN T = 1
HS 1080 NEXT J
PM 1090 M0 = 1 - M0
PK 1100 FOR J = 1 TO 750 : NEXT J
MB 1120 PRINT "{HOME} {4 DOWN}"
AD 1130 GOTO 500
JC 1140 PRINT C$;
DR 1150 IF R = M0 THEN W0 = W0 + 1 : PRINT "I WIN!"
GK 1160 IF R < > M0 THEN W1 = W1 + 1 : PRINT "YOU WIN!"
JH 1170 PRINT
MG 1180 PRINT "THAT MAKES" W1; "GAME;"
DX 1190 IF W1 < > 1 THEN PRINT"S"
PC 1200 PRINT " FOR YOU"
CD 1210 PRINT "AND";WO; "FOR ME."
BG 1220 IF I<1 AND W1 > W0 AND R < > M0 AND R1 = 0 THEN GOSUB 1380
MJ 1230 PRINT
JP 1240 R1 = 0
GQ 1250 X$ = "Y : " : INPUT "PLAY AGAIN" : X$
QB 1260 IF X$ = "N" : OR X$ = "NO" THEN END
SC 1270 X$ = "N" : INPUT "SAME GAME AS LAST TIME" ; X$
QJ 1280 IF X$<> "N&rdquo AND X$ <> "NO" THEN 1350
CD 1290 IF RND (1)>.35 THEN 330
SM 1300 IF RND (1)>.6 THEN 1330
CC 1310 R = 1 - R : R9 = 5 : PRINT : PRINT "{RVS} RULE CHANGE"
SG 1320 FOR J = 1 TO 500 : NEXT J
CG 1330 IF RND (1)<.6 THEN N9 = INT (RND(1) * 4) + 3 : IF N9>5 THEN N9 = 99
QB 1340 GOTO 330
CC 1350 R1 = 1
JC 1360 FOR J = 1 TO 4 : A(J) = P(J) : NEXT J
MD 1370 GOTO 420
RC 1380 I = I↑.75
HG 1390 PRINT "DON'T FEEL TOO SMART."
SE 1400 PRINT "I CAN DO BETTER!"
RK 1410 RETURN