Matchbox Tic-Tac-Toe

Type
Education
Category
Machine-learning demonstration (MENACE)
Author
Joseph Hafner
Published in
Antic, April 1984 (Vol. 3, No. 1)
Year
1984
Language
Atari BASIC
Requirements
16K RAM with cassette or 24K with disk, Atari BASIC; joystick in port 1 or the console keys; optional printer, disk or cassette for saving what it has learned
A brown GRAPHICS 2 screen with a tic-tac-toe grid, the prompt DO YOU WANT TO GO FIRST (YN), and a status line counting wins, loses, draws and patterns

About the program

"It's an uncanny experience to watch your computer get better at the game with practice," Joseph Hafner wrote. His program is an introduction to artificial intelligence, based on an experiment by the English biologist Donald Michie in 1960. Michie built MENACE, the Matchbox Educable Noughts And Crosses Engine, from about 300 matchboxes, each labelled with a tic-tac-toe position and filled with coloured beads, one colour for each possible move. To play, he found the box for the current position, shook it and drew a bead at random. If the matchboxes won, beads of the chosen colours were added. If they lost, those beads were taken away, and after a draw they were put back. Good moves became more likely and bad ones died out.

Hafner was an electronics design engineer with ten years of experience who had also taught programming. He suggested keeping a chart of results so you could see the computer improve.

Typing it in

A few strings contain inverse and control characters ({inv}…{/inv}: press the Atari key before and after), including the prompt in line 440. Line 140 creates the "matchbox" string MB$ with 5,700 bytes, room for 300 boxes.

How to play

At the start, answer Y to recall earlier learning from disk or cassette, or N to start fresh. Then choose who goes first. X always moves first. Move the cursor round the board with the joystick or SELECT, and place your mark with the button or START. Between games, OPTION lists the learned patterns or saves them to a file.

Hafner's advice: don't try every combination at once. Repeat one or two openings until the computer has mastered them, and let it go first, because "it seems to learn much faster that way". After 20 games or so the improvement should be obvious.

How it works

  • Matchboxes in a string. Each box is 19 bytes of MB$: nine bytes for the board pattern, nine bead counters (one per square), and one byte that remembers which "bead" was drawn this game.
  • Symmetry. BOARD$ holds all eight rotations and reflections of the current board, and the ALT table maps squares between them. Mirror images share one box, which saves storing more than 4,500 patterns.
  • Learning new positions. The boxes aren't built in advance. When lines 1280–1370 meet a position they don't recognise, they add a new box. Lines 1380–1410 then pick a move at random, weighted by the bead counts.
  • Reward and punishment. After a win, line 760 adds R=2 beads to each move used. After a loss, line 860 removes P=1. A draw (line 630) changes nothing. These values, and the weighting factor, are set in line 310 for you to experiment with.
  • Running out of beads. Hafner beat the program 32 times in a row, and it was left with no beads at all in one box. Line 1420 now resets that pattern and starts it again. Testing this, he won 55 games straight before it found the right moves and beat him.

Changes from the published listing

One change, so the program also runs under Altirra BASIC, the free replacement BASIC built into many emulators. Altirra BASIC adds a command called MOVE, so it rejected the published lines that use that word as the start of a variable name. The variable is renamed everywhere in the program. The new name is the same length, so the memory layout is unchanged and the program behaves exactly as published on genuine Atari BASIC. If you type it in from the magazine, the original names work fine on a real Atari.

Published Now Lines
MOVE MOVX 1100, 1110, 1130, 1260, 1380, 1400, 1420, 1430, 1440
MOVENUM MOVXNUM 400, 540, 1250, 1350

Listing

110 DIM MARK$(2),MB$(300*19),LINE$(5),BOARD$(72),FNAME$(15),J$(3)
120 DIM WIN$(24),INDEX(8),ALT$(72),PLAYS(4)
130 MARK$=CHR$(ASC("X")+32):MARK$(2)=CHR$(ASC("O")+32)
140 MB$(1)="{CTRL-,}":MB$(5700)="{CTRL-,}":MB$(2)=MB$
150 MB$(1,9)="         ":FOR I=10 TO 19:MB$(I)="{CTRL-D}":NEXT I
160 LINE$="{CTRL-R}{CTRL-S}{CTRL-R}{CTRL-S}{CTRL-R}"
180 WIN$="{CTRL-A}{CTRL-B}{CTRL-C}{CTRL-H}{CTRL-I}{CTRL-D}{CTRL-G}{CTRL-F}{CTRL-E}{CTRL-A}{CTRL-H}{CTRL-G}{CTRL-B}{CTRL-I}{CTRL-F}{CTRL-C}{CTRL-D}{CTRL-E}{CTRL-A}{CTRL-I}{CTRL-E}{CTRL-C}{CTRL-I}{CTRL-G}"
200 FOR I=0 TO 8:READ A:INDEX(I)=A:NEXT I
210 DATA 1,2,3,8,9,4,7,6,5
225 ALT$="{CTRL-A}{CTRL-B}{CTRL-C}{CTRL-D}{CTRL-E}{CTRL-F}{CTRL-G}{CTRL-H}{CTRL-I}{CTRL-G}{CTRL-H}{CTRL-A}{CTRL-B}{CTRL-C}{CTRL-D}{CTRL-E}{CTRL-F}{CTRL-I}{CTRL-E}{CTRL-F}{CTRL-G}{CTRL-H}{CTRL-A}{CTRL-B}{CTRL-C}{CTRL-D}{CTRL-I}{CTRL-C}{CTRL-D}{CTRL-E}{CTRL-F}{CTRL-G}{CTRL-H}{CTRL-A}{CTRL-B}{CTRL-I}{CTRL-C}{CTRL-B}{CTRL-A}{CTRL-H}{CTRL-G}{CTRL-F}{CTRL-E}{CTRL-D}{CTRL-I}{CTRL-E}{CTRL-D}{CTRL-C}{CTRL-B}{CTRL-A}{CTRL-H}{CTRL-G}{CTRL-F}{CTRL-I}{CTRL-G}{CTRL-F}{CTRL-E}{CTRL-D}{CTRL-C}{CTRL-B}{CTRL-A}{CTRL-H}{CTRL-I}{CTRL-A}{CTRL-H}{CTRL-G}{CTRL-F}{CTRL-E}{CTRL-D}{CTRL-C}{CTRL-B}{CTRL-I}"
270 FOR I=0 TO 4:READ A:PLAYS(I)=A:NEXT I
280 DATA 96,184,175,272,254
290 XL=8:XH=XL+4:YL=3:YH=YL+4
300 WINS=0:LOSES=0:DRAWS=0
310 R=2:P=1:D=0:WFACTOR=1
360 GOSUB 2010
380 GRAPHICS 2:POKE 756,226:SETCOLOR 0,0,0
390 BOARD$(1)=" ":BOARD$(72)=" ":BOARD$(2)=BOARD$(1):GOSUB 930
400 MOVXNUM=0:HUMAN=0
410 ? "WINS=";WINS;" LOSES=";LOSES;" DRAWS=";DRAWS;
420 ? " PATTERNS=";LEN(MB$)/19
430 POSITION 2,0:? #6;"do you want to go"
440 FOR I=0 TO 1 STEP 0:POSITION 5,1:? #6;"first{inv}^{/inv}yn{inv}_{/inv}  "
450 FOR J=0 TO 1 STEP 0:IF PEEK(53279)=3 THEN GOSUB 2110
460 IF PEEK(764)<255 THEN J=2
470 NEXT J
480 OPEN #2,4,0,"K:":GET #2,A:POSITION 14,1:PUT #6,A+32:CLOSE #2
490 IF A=ASC("Y") THEN HUMAN=1:CMPTR=2:I=2
500 IF A=ASC("N") THEN CMPTR=1:HUMAN=2:I=2
510 NEXT I
520 PLAYER=2
530 FOR I=0 TO 19:FOR J=0 TO 1:POSITION I,J:? #6;" ":NEXT J:NEXT I
540 PLAYER=PLAYER+1-2*(PLAYER=2):MOVXNUM=MOVXNUM+1
550 POSITION 6,0
560 IF PLAYER=HUMAN THEN ? #6;"your move":GOSUB 1010
570 IF PLAYER=CMPTR THEN ? #6;" my move ":GOSUB 1250
580 GOSUB 1480
590 ON WIN GOTO 540,610,700,720
610 POSITION 6,0:? #6;" a  draw "
620 FOR I=19 TO LEN(MB$) STEP 19:J=ASC(MB$(I)):MB$(I,I)=CHR$(0)
630 IF J THEN J=I-10+J:A=ASC(MB$(J)):A=A+D*(A<255):MB$(J,J)=CHR$(A)
640 NEXT I
650 DRAWS=DRAWS+1:RESTORE 680
660 FOR I=1 TO 10:READ A,B:SOUND 0,A,10,8
670 FOR J=1 TO B*20:NEXT J:SOUND 0,0,0,0:NEXT I:GOTO 380
680 DATA 40,1,0,1,53,1,53,1,47,2,53,1,0,2,42,1,0,1,40,1
700 ON HUMAN GOTO 840,740
720 ON CMPTR GOTO 840,740
740 POSITION 6,0:? #6;" i  win  "
750 FOR I=19 TO LEN(MB$) STEP 19:J=ASC(MB$(I)):MB$(I,I)=CHR$(0)
760 IF J THEN J=I-10+J:A=ASC(MB$(J)):A=A+R*(A<150):MB$(J,J)=CHR$(A)
770 NEXT I
780 WINS=WINS+1:RESTORE 810
790 FOR I=1 TO 19:READ A,B:SOUND 0,A,10,8
800 FOR J=1 TO B*20:NEXT J:SOUND 0,0,0,0:NEXT I:GOTO 380
810 DATA 81,1,81,1,81,1,81,2,162,3,162,1,144,1,121,1,81,3,81,1,76,1
820 DATA 81,1,81,2,91,2,81,2,91,2,108,1,102,1,136,5
840 POSITION 6,0:? #6;" you win "
850 FOR I=19 TO LEN(MB$) STEP 19:J=ASC(MB$(I)):MB$(I,I)=CHR$(0)
860 IF J THEN J=I-10+J:A=ASC(MB$(J)):A=A-P*(A>0):MB$(J,J)=CHR$(A)
870 NEXT I
880 LOSES=LOSES+1:RESTORE 910
890 FOR I=1 TO 11:READ A,B:SOUND 0,A,10,8
900 FOR J=1 TO B*20:NEXT J:SOUND 0,0,0,0:NEXT I:GOTO 380
910 DATA 193,4,193,3,193,1,193,3,162,3,173,1,173,3,193,1,193,3,204,1,193,5
930 POSITION XL,YL+0:? #6;BOARD$(1,1);"|";BOARD$(2,2);"|";BOARD$(3,3)
940 POSITION XL,YL+1:? #6;LINE$
950 POSITION XL,YL+2:? #6;BOARD$(8,8);"|";BOARD$(9,9);"|";BOARD$(4,4)
960 POSITION XL,YL+3:? #6;LINE$
970 POSITION XL,YL+4:? #6;BOARD$(7,7);"|";BOARD$(6,6);"|";BOARD$(5,5)
980 FOR I=100 TO 10 STEP -5:SOUND 0,I,10,8:NEXT I:SOUND 0,0,0,0
990 RETURN
1010 CX=XL:CY=YL:BLANK=32:MARKER=20
1020 LOCATE CX,CY,A:IF A=BLANK THEN GOTO 1060
1030 CX=CX+2:IF CX>XH THEN CX=XL:CY=CY+2
1040 IF CY>YH THEN CY=YL:CX=XL
1050 GOTO 1020
1060 POSITION CX,CY:PUT #6,MARKER:GOSUB 1170
1070 POSITION CX,CY:PUT #6,BLANK
1080 ON KEYIN GOTO 1090,1030,1100
1090 GOSUB 1170:ON KEYIN GOTO 1060,1030,1100
1100 MOVX=INDEX(3*((CY-YL)/2)+(CX-XL)/2)
1110 BOARD$(MOVX,MOVX)=MARK$(PLAYER,PLAYER)
1120 GOSUB 930
1130 FOR I=0 TO 63 STEP 9:J=ASC(ALT$(I+MOVX))
1140 BOARD$(I+J,I+J)=MARK$(PLAYER,PLAYER):NEXT I
1150 RETURN
1170 IF (PEEK(53279)<>7) THEN FOR J=1 TO 20:NEXT J
1180 IF (STRIG(0)=0) OR (STICK(0)<>15) THEN FOR J=1 TO 20:NEXT J
1190 FOR I=1 TO 10
1200 IF (PEEK(53279)=5) OR (STICK(0)<>15) THEN KEYIN=2:POP :RETURN
1210 IF (PEEK(53279)=6) OR (STRIG(0)<>1) THEN KEYIN=3:POP :RETURN
1220 IF (PEEK(53279)=3) THEN GOSUB 1710
1230 NEXT I:KEYIN=1:RETURN
1250 IF MOVXNUM<>9 THEN GOTO 1280
1260 FOR I=1 TO 9:IF BOARD$(I,I)=" " THEN MOVX=I
1270 NEXT I:GOTO 1110
1280 FOR I=1 TO LEN(MB$)-10 STEP 19:I1=I:I2=I1+8
1290 FOR J=1 TO 64 STEP 9:J1=J:J2=J1+8
1300 IF BOARD$(J1,J2)=MB$(I1,I2) THEN POP :POP :GOTO 1380
1310 NEXT J
1320 NEXT I
1330 I=LEN(MB$)+1:MB$(I)=BOARD$(1,19):? "  NEW PATTERN"
1340 FOR J=1 TO 9:K=I+J+8:MB$(K,K)=CHR$(0)
1350 IF BOARD$(J,J)=" " THEN MB$(K,K)=CHR$(5-INT((MOVXNUM+1)/2))
1360 NEXT J
1370 MB$(I+18,I+18)=CHR$(0):J1=1:J2=9
1380 INDEX=I+9:MAXWEIGHT=0:MOVX=0
1390 FOR I=INDEX TO INDEX+8:WEIGHT=ASC(MB$(I))*WFACTOR*RND(0)
1400 IF WEIGHT>MAXWEIGHT THEN MAXWEIGHT=WEIGHT:MOVX=I-INDEX+1
1410 NEXT I
1420 IF MOVX=0 THEN ? "  PATTERN RESET":I=INDEX-9:GOTO 1340
1430 MB$(INDEX+9,INDEX+9)=CHR$(MOVX)
1440 FOR J=J1 TO J2:IF MOVX=ASC(ALT$(J)) THEN MOVX=ASC(ALT$(J-J1+1)):J=J2
1450 NEXT J
1460 GOTO 1110
1480 PLAY=0:WIN=1
1490 FOR I=1 TO 22 STEP 3
1500 SUM=ASC(BOARD$(ASC(WIN$(I))))+ASC(BOARD$(ASC(WIN$(I+1))))+ASC(BOARD$(ASC(WIN$(I+2))))
1510 IF (SUM=360) OR (SUM=333) THEN POP :GOTO 1590
1520 IF PLAY THEN GOTO 1560
1530 FOR J=0 TO 4
1540 IF SUM=PLAYS(J) THEN PLAY=1
1550 NEXT J
1560 NEXT I
1570 IF PLAY THEN RETURN
1590 IF SUM=360 THEN WIN=3
1600 IF SUM=333 THEN WIN=4
1610 IF (WIN=1) AND (PLAY=0) THEN WIN=2
1620 RETURN
1710 TRAP 1820:OPEN #4,8,0,"P:"
1720 FOR I=1 TO LEN(MB$)-10 STEP 19
1730 J=INT(I/19)+1
1740 IF J<1000 THEN J$=""
1750 IF J<100 THEN J$=" "
1760 IF J<10 THEN J$="  "
1770 J$(LEN(J$)+1)=STR$(J)
1780 PRINT #4;J$;"  ";MB$(I,I+8);"  ";
1790 FOR J=I+9 TO I+18
1800 PRINT #4;ASC(MB$(J));" ";
1810 NEXT J:PRINT #4:NEXT I:CLOSE #4:RETURN
1820 CLOSE #4:GRAPHICS 0
1830 FOR I=1 TO LEN(MB$)-10 STEP 19:J=INT(I/19)+1
1840 IF J<1000 THEN J$=""
1850 IF J<100 THEN J$=" "
1860 IF J<10 THEN J$="  "
1870 J$(LEN(J$)+1)=STR$(J):? J$;" ";MB$(I,I+8);" ";
1880 FOR J=I+9 TO I+18:? ASC(MB$(J));" ";:NEXT J:? :NEXT I
1890 ? "  PRESS ANY KEY TO CONTINUE GAME."
1900 IF (PEEK(764)=255) AND (PEEK(53279)=7) THEN 1900
1910 GRAPHICS 2:POKE 756,226:SETCOLOR 0,0,0:POKE 764,255
1920 POSITION 6,0:? #6;"your move":GOSUB 930:RETURN
2010 GRAPHICS 0:OPEN #3,4,0,"K:":? " Recall previous learning?";
2020 GET #3,A:? CHR$(A);:CLOSE #3
2030 IF A<>ASC("Y") THEN RETURN
2040 ? :? " What dev:filename";
2050 INPUT FNAME$
2060 TRAP 2080:OPEN #3,4,0,FNAME$
2070 FOR X=1 TO 5700:GET #3,DD:IF DD=155 THEN POP :GOTO 2078
2072 MB$(X)=CHR$(DD)
2074 NEXT X
2078 CLOSE #3:RETURN
2080 ? :? " Sorry, unable to open that file."
2090 ? " Please try again.":GOTO 2010
2110 ? :? " Save current learning."
2120 ? " What dev:filename";
2130 INPUT FNAME$
2140 TRAP 2160:OPEN #3,8,0,FNAME$
2150 PRINT #3;MB$:CLOSE #3:RETURN
2160 ? :? " Sorry, unable to open that file."
2170 ? "WINS=";WINS;" LOSES=";LOSES;" DRAWS=";DRAWS;
2180 ? " PATTERNS=";LEN(MB$)/19
2190 RETURN

Download

The original program from the Antic disk, to LOAD or ENTER instead of typing it: MATCHBOX.BAS.

Credits