The only game I have that runs on my 4004 system plays Tic-Tac-Toe, where the computer plays one side. I wrote this some three years ago, but it recently occurred to me that it would be something that would run in TINY BASIC very easily. It is a simple program and although the computer plays aggressively, it is not unbeatable. This program is particularly suited to TINY BASIC because there are only a few variables: we need a nine-element array for the playing board, but that could have been handled by using nine variables. I chose to use the USR function to access nine consecutive memory locations in lower memory (0007 to 000F). That is the only use of the USR function, so if you want to use this program on some other TINY BASIC than mine, you know what to look for.

I did use one other peculiarity of TINY in this program: there are several loops where the index on the loop is W, which takes on the four values 6100, 6200, 6300, and 6400. These are line numbers for the entry points of a subroutine, and the only use of the variable W is in a GOSUB W statement, which selects the corresponding subroutine entry. If you want to convert this program to regular BASIC you will have to fix that part as well as the USR calls.

When I was in high school I worked out a combinatorial solution for this game which could be implemented in relays, and I actually knew somebody who built a Tic-Tac-Toe machine. But when I wrote this program I decided that a heuristic approach would be more fun, so this program does not use the combinatorial approach. The heuristic is a tree-search algorithm of depth one. This is trivial as game programs go, but then, the game is nearly trivial itself. Theoretically the program can be beaten, though I could not find how.

The algorithm is simple. Each empty square is assigned a score representing how good a play in that square is, then the highest score wins. For each row, column, or diagonal going through this square, the score is incremented by 1 if there is an X (the human play) and two blanks, by 2 if all three squares are blank (i.e., the row, column or diagonal is available), by 3 if there is an O and two blanks (aggressive: prefer playing to win than to block), by 20 if there are two X's (must block those), and by 100 if there are two O's (that's a win). This scoring is done in lines 4300-4500.

I wrote the program so that the user can type in the location of the beginning of the interpreter (from which the program derives the address of the Peek and Poke USR routines), then after that it just plays one game after another. Hopefully that minimizes the need to make changes in the code for different processors. One change which owners of TVT terminals might like is to add a line for a Home Cursor operation before printing the playing board. If your TVT recognizes a FormFeed (hex 0C) as the Home function, either of the following will do the job:

2020 LET J=USR(G-11,0,12)
2020 PRINT "[formfeed]";

After writing the program I realized that it is too big for a 4K system in its entirety. So I separated the setup operations (lines 100-500) so that you can load and RUN them, then CLEAR and load the rest. Or you can omit loading the setup entirely, and just set G and P in the direct execution mode to the proper values for your system.

The rest of the program is still too big.

Now comes the big squeeze. I have a nice text editor on my 4004 which allows multiple string substitutions. I ran the program through the editor, making the following substitutions:

LET deleted
PRINT becomes PR
all REM lines removed
delete all spaces (BASIC ignores them anyway)
remove 4th digit of line numbers
  (only makes GOTOs shorter)

By the way, Just as I was getting ready to cheat and put a deliberate bug in the program so it could be beaten, somebody found a way to beat it without cheating. It is not a bug, but a direct result of the way the heuristic evaluates each square. Also, on my 4004 the program evaluates its next move in less than one second, or so fast as to appear instantaneous. In TINY BASIC it takes several seconds, so I put in a line which prints a period from time to time as it thinks. This way you know the computer has not stopped.

This is the whole program; the compressed version followes it. It is now in the public domain, so have at it.

100 REM TIC-TAC-TOE. YOU (X) VS. THE COMPUTER (O)
110 GOTO 200
120 BOARD IS IN MEMORY LOCATIONS 0007-000F
130 .  0 IS EMPTY, 1 IS X. 3 TS O
140 I HAS CURRENT POSITION
150 G IS PEEK ROUTINE ADDRESS
160 P IS POKE ROUTINE ADDRESS
170 F=1 IF YOU PLAY FIRST
180 U IS NUMBER OF UNPLAYED SQUARES
190 Z=1 IF SOMEONE WON
200 REM
210 PRINT "TIC-TAC-TOE. YOU AGAINST TINY BASIC"
220 PRINT "YOU ARE X. I AM O."
230 PRINT "YOU PLAY YOUR TURN BY TYPING THE NUMBER OF A SQUARE."
240 A=0
250 B=0
260 C=0
270 D=0
280 E=0
290 F=0
300 PRINT
310 PRINT "FIRST, ";
320 PRINT "PLEASE TELL ME WHERE THE COLD START IS."
330 PRINT "IN DECIMAL";
340 INPUT I
350 IF I/256*256=I GOTO 400
360 IF I/100*100=I GOTO 330
370 PRINT "NO. NOT HEX.  ";
380 GO TO 330
400 P=I+24
410 G=I+20
420 PRINT "THAT IS ";I/4096;(I-I/4096*4096)/256;
430 PRINT "00 IN HEX.  THANKS."
440 GO TO 500
450 TO CONSERVE MEMORY, LINES 100-500 MAY BE RUN ONCE
460 THEN DELETED (CLEAR) BEFORE LOADING THE REST OF THE PROGRAM
500 REM---ON WITH THE SHOW...
1000 LET F=1
1010 PRINT
1020 PRINT "NEW GAME."
1100 LET I=7
1110 LET I=USR(P,I,0)*0+I+1
1120 IF I<16 GOTO 1110
1130 LET U=9
1140 LET Z=0
1150 IF F=0 THEN GOTO 4010
1160 GO TO 2010
1500 REM X WON.
1510 LET Z=1
1520 LET F=0
2000 REM PRINT GAME STATE
2010 LET I=6
2100 PRINT
2110 LET I=I+1
2120 PRINT " ";
2130 GOTO USR (G,I)*20+2200
2200 PRINT I-6;
2210 GOTO 2300
2220 PRINT "X";
2230 GOTO 2300
2260 PRINT "O";
2300 IF I/3*3=I GOTO 2400
2310 PRINT " |";
2320 GOTO 2110
2400 PRINT
2420 IF I=15 GOTO 3000
2430 PRINT "---+---+---"
2440 GOTO 2110
3000 IF Z=0 GOTO 3100
3010 REM THE GAME IS OVER.
3020 IF F=1 GOTO 3050
3030 PRINT "YOU WIN."
3040 GOTO 1010
3050 PRINT "I WIN."
3060 GOTO 1010
3100 IF U>0 GOTO 3210
3110 PRINT "CAT'S GAME."
3120 LET F=1-F
3130 GOTO 1010
3200 REM INPUT NEXT PLAY.
3210 PRINT "YOUR PLAY";
3220 INPUT I
3230 IF I>0 IF I<10 GOTO 3270
3240 PRINT "PLEASE TYPE A NUMBER BETWEEN 1 AND 9"
3250 PRINT "WHERE YOU WISH TO PLAY YOUR X"
3260 GOTO 3210
3270 IF USR (G,I+6)=0 GOTO 3310
3280 PRINT "THAT SQUARE IS ALREADY TAKEN."
3290 GOTO 3210
3300 REM CHECK IF X WON.
3310 LET U=USR(P,I+6,1)*0+U-1
3320 LET W=6100
3330 GOSUB W
3340 IF J>0 IF L*M*N=1 GOTO 1510
3350 LET W=W+100
3360 IF W<6500 GOTO 3330
3400 REM CHECK IF CATS GAME
3410 IF U=0 GOTO 2010
4000 REM FIND BEST O PLAY
4010 LET I=1
4020 LET T=-1
4290 REM EVALUATE I'TH SQUARE
4300 LET S=0
4310 IF USR(G,I+6)>0 GOTO 4480
4320 LET W=6100
4330 GOSUB W
4340 IF J=0 GOTO 4410
4350 LET J=L+M+N
4360 IF J=4 THEN GOTO 4410
4370 IF J=2 THEN LET S=S+20
4380 IF J=6 THEN LET S=S+100
4390 IF J=0 THEN LET S=S+2
4400 LET S=S+J
4410 LET W=W+100
4420 IF W<6500 GOTO 4330
4430 IF S<T THEN GOTO 4470
4440 LET T=S
4450 LET B=I
4460 REM SAY SOMETHING, SO IT WONT SEEN SO LONG.
4470 PRINT ".";
4480 LET I=I+1
4490 IF I<10 GOTO 4300
4500 PRINT "I PLAY ";B
4510 PRINT
4520 LET J=USR(P,B+6,3)
4530 LET U=U-1
4540 IF T<100 THEN GOTO 2010
4550 REM I WON I WON I WON
4560 F=1
4570 Z=1
4580 GOTO 2010
6000 REM SUBROUTINE TO LOOK AT ONE ROW, COL, OR DIAG
6010 REM I IS THE POSITION OF REFERENCE
6020 REM L,M,N ARE RETURNED WITH CONTENTS OF THE THREE SQUARES
6030 REM ENTER AT 6100,6200,6300, OR 6400...
6040 REM TO EXAMINE ROW,COLUMN,DOWN DIAGONAL OR UP DIAGONAL
6090 REM W=HORIZONTAL
6100 LET J=(I-1)/3*3+8
6110 LET D=1
6120 GOTO 6500
6190 REM W=VERTICAL
6200 LET J=I-(I-1)/3*3+9
6210 LET D=3
6220 GOTO 6500
6290 REM W=DOWN DIAGONAL
6300 IF I-1<>(I-1)/4*4 GOTO 6440
6310 LET D=4
6320 REM BOTH DIAGONALS GO THRU CENTER
6330 LET J=11
6340 GOTO 6500
6390 REM W=UP DIAGONAL
6400 LET D=2
6410 IF I>1 IF I<9 IF I=I/2*2+1 GOTO 6330
6430 REM A DIAGONAL DOES NOT GO THRU THIS SQUARE
6440 LET J=0
6450 RETURN
6490 REM NOW WE KNOW CENTER OF THIS THREE AND +/- OFFSET
6500 LET L=USR(G,J-D)
6510 LET M=USR(G,J)
6520 LET N=USR(G,J+D)
6530 RETURN

100F=1
101PR
102PR"NEWGAME"
110I=7
111I=USR(P,I,0)*0+I+1
112IFI<16GOTO111
113U=9
114Z=0
115IFF=0GOTO401
116GOTO201
151Z=1
152F=0
201I=6
210PR
211I=I+1
212PR" ";
213GOTOUSR(G,I)*2+220
220PRI-6;
221GOTO230
222PR"X";
223GOTO230
226PR"O";
230IFI/3*3=IGOTO240
231PR" |";
232GOTO211
240PR
242IFI=15GOTO300
243PR"---+---+---"
244GOTO211
300IFZ=0GOTO310
302IFF=1GOTO305
303PR"YOU WIN"
304GOTO101
305PR"I WIN"
306GOTO101
310IFU>0GOTO321
311PR"CATS"
312F=1-F
313GOTO101
321PR"YOUR PLAY";
322INPUTI
323IFI>0IFI<10GOTO327
324PR"ONE DIGIT ONLY"
326GOTO321
327IFUSR(G,I+6)=0GOTO331
328PR"TAKEN"
329GOTO321
331U=USR(P,I+6,1)*0+U-1
332W=610
333GOSUBW
334IFJ>0IFL*M*N=1GOTO151
335W=W+10
336IFW<650GOTO333
341IFU=0GOTO201
401I=1
402T=-1
430S=0
431IFUSR(G,I+6)>0GOTO448
432W=610
433GOSUBW
434IFJ=0GOTO441
435J=L+M+N
436IFJ=4GOTO441
437IFJ=2S=S+20
438IFJ=6S=S+100
439IFJ=0S=S+2
440S=S+J
441W=W+10
442IFW<650GOTO433
443IFS<TGOTO447
444T=S
445B=I
447PR".";
448I=I+1
449IFI<10GOTO430
450PR"I PLAY ";B
451PR
452J=USR(P,B+6,3)
453U=U-1
454IFT<100GOTO201
456F=1
457Z=1
458GOTO201
610J=(I-1)/3*3+8
611D=1
612GOTO650
620J=I-(I-1)/3*3+9
621D=3
622GOTO650
630IFI-1<>(I-1)/4*4GOTO644
631D=4
633J=11
634GOTO650
640D=2
641IFI>1IFI<9IFI=I/2*2+1GOTO633
644J=0
645RETURN
650L=USR(G,J-D)
651M=USR(G,J)
652N=USR(G,J+D)
653RETURN