Strategy Game AI in Atari BASIC: Evaluation Functions, Lookahead and Alpha-Beta

Atari text screen showing four small tic-tac-toe boards made of X, O and dots, each followed by a line such as O PLAYS 3 (SCORE 1010)

How does a program "think" about a board game? John White's Writing Strategy Games on Your Atari (Sunshine Books, 1983, published in the US by Hayden in 1984) answers that for Atari BASIC programmers. It works up from a single scoring routine to search trees and alpha-beta pruning, ending with a complete game, Warp Trog. This guide follows White's path, adds a small evaluation-function program you can run, and explains which of these techniques fit in BASIC and which need machine language.

What you'll learn: directed versus "intelligent" moves, evaluation functions and how to weight them, plies and the minimax method, why search depth explodes, alpha-beta pruning, the horizon effect and Turing's rule for captures, and practical speed advice.

What you need: Atari BASIC. The example program was run in atari800. For real-time wargame opponents, see the companion guide Game AI the Chris Crawford Way.

1. Directed moves and intelligent moves

White distinguishes two kinds of computer behaviour. Directed play follows a fixed rule. His first example is an enemy ship that always heads for the player:

1000 IF X>P THEN X=X-MO
1010 IF X<P THEN X=X+MO
1020 IF Y>Q THEN Y=Y-MO
1030 IF Y<Q THEN Y=Y+MO

Here (P,Q) is the player, (X,Y) the enemy and MO its speed. Most action games need nothing more. White's historical example is a mechanical device by the Spaniard Quevedo that played the king-and-rook against king ending by following six rules in strict order, never choosing between moves.

An intelligent move, in White's definition, is one the program selects after considering a number of alternatives. By that definition even tic-tac-toe can be an intelligent game, and the rest of the book is about how to make that selection well.

2. The evaluation function

Everything rests on the evaluation function (EF): a routine that gives a position a single number, positive when it favours the program. White's first EF is the chess material count. Pawn 1, knight and bishop 3, rook 5, queen 9, king 255, with the computer's pieces positive and the opponent's negative, so that an equal position scores zero. Summing an 8×8 array gives the score:

1000 Q=0:FOR I=1 TO 8
1010 FOR J=1 TO 8
1020 Q=Q+A(I,J)
1030 NEXT J:NEXT I
1040 RETURN

Then he refines it with small positional terms. Each pawn earns 0.01 per rank it has advanced, enough to break ties without ever outweighing material. That is the whole art of EFs: a big term for what matters most, and small terms that nudge the choice among otherwise equal moves.

To choose a move with a one-ply search, the program tries each legal move on a copy of the board, scores the result with the EF, undoes it, and keeps the best.

3. A working example: a tic-tac-toe chooser

For a game as small as tic-tac-toe, the EF can score each empty square directly by looking at the eight lines through the board. This program does that and prints the move it would choose in four test positions:

10 REM TIC-TAC-TOE MOVE CHOOSER: AN EVALUATION FUNCTION
20 DIM B(9),L(24),C$(3)
30 FOR I=1 TO 24:READ X:L(I)=X:NEXT I
40 DATA 1,2,3,4,5,6,7,8,9,1,4,7,2,5,8,3,6,9,1,5,9,3,5,7
50 C$="X.O"
60 FOR P=1 TO 4
70 FOR I=1 TO 9:READ X:B(I)=X:NEXT I
80 GOSUB 1000
90 FOR R=0 TO 2:FOR C=1 TO 3:? C$(B(R*3+C)+2,B(R*3+C)+2);:NEXT C:? :NEXT R
100 ? "O PLAYS ";BM;" (SCORE ";BS;")":?
110 NEXT P:END
120 DATA 1,1,0,-1,-1,0,0,0,0
130 DATA -1,-1,0,0,1,0,0,0,0
140 DATA 0,0,0,0,0,0,0,0,0
150 DATA -1,0,0,0,1,0,0,0,-1
1000 REM SCORE EVERY EMPTY SQUARE, KEEP THE BEST
1010 BS=-1:BM=0
1020 FOR S=1 TO 9:IF B(S) THEN 1110
1030 V=0:IF S=5 THEN V=3
1040 FOR K=0 TO 7:A=L(K*3+1):E=L(K*3+2):F=L(K*3+3)
1050 IF A<>S AND E<>S AND F<>S THEN 1090
1060 O=(B(A)=1)+(B(E)=1)+(B(F)=1):H=(B(A)=-1)+(B(E)=-1)+(B(F)=-1)
1070 IF O=2 AND H=0 THEN V=V+1000
1080 IF H=2 AND O=0 THEN V=V+100
1085 IF H=0 THEN V=V+1+O*4
1090 NEXT K
1100 IF V>BS THEN BS=V:BM=S
1110 NEXT S:RETURN

The board is an array with 1 for the computer (O), −1 for the human (X) and 0 for empty. The squares are numbered 1–9, left to right and top to bottom. The weights do the thinking:

Term Points Why
Completes a line of O's 1000 Winning beats everything
Blocks a line of X's 100 Must block before anything else
Line still open to O 1 + 4 per O already in it Build towards future wins
Centre square 3 The centre is on four lines

Comparisons count for 1 when true in Atari BASIC, so line 1060 counts O's and X's in a line in one statement. In our run the program completed its own line (score 1010), blocked a threatened line (106), opened in the centre on an empty board, and against X in two opposite corners chose an edge (square 2), which is the correct defence to that trap. It found that defence without "knowing" it, because the open-line terms happen to favour the edge in that position. This is White's point: a well-balanced EF produces good play that you never coded explicitly.

4. Looking ahead: plies and minimax

One ply only considers the program's own move. Looking further means building a tree: the program's possible moves (first ply), the opponent's replies to each (second ply), the program's answers to those (third ply), and so on. Scores come from the EF at the leaves and are "backed up": at plies where the opponent moves, take the minimum (the opponent will choose what is worst for you), and at the program's plies take the maximum. This is the minimax method.

The cost grows fast. White's arithmetic: with ten moves available at each turn and a tenth of a second per evaluation, one ply takes a second, two plies ten seconds, four plies a thousand seconds, and eight plies more than three years. He concludes that a BASIC program can barely search beyond two plies. BASIC is slow, so each evaluation takes a second or two, and Atari BASIC has no recursion (a subroutine can't call itself with fresh local variables), so a separate move generator is needed for each level of search. Machine language removes both limits.

5. Alpha-beta pruning

Alpha-beta, discovered in 1959, gives exactly the same result as minimax while scoring fewer positions. The idea: once you know one move guarantees a certain score, any other move where the opponent has a reply that does worse than that can be abandoned as soon as that reply is found. There's no need to examine the rest of its replies. White's advice is blunt: minimax should never be used without the alpha-beta modification. It works best when good moves are tried first, which is why Warp Trog sorts its first-ply moves by score and uses a "killer" heuristic to try strong replies early.

6. The dangers of a fixed depth

Two traps await any fixed-depth search:

  • Unfinished exchanges. White shows a chess line where a 3-ply search sees a favourable capture sequence and plays it, missing the queen loss on the next move. He cites Alan Turing's remedy: keep searching any line until no further captures are possible, reaching a "Turing-dead" position, before trusting the evaluation.
  • The horizon effect. A program facing an unavoidable loss may make delaying moves, such as a pointless check, that push the loss just beyond its search depth. It then thinks the danger has gone. White notes that even strong commercial chess programs suffered from it.

7. Making it fast enough in BASIC

White's practical advice for Atari BASIC game AI:

  • Recode before anything else. His board-drawing example went from six seconds to one by rethinking the loops, before any machine code.
  • Put the most-called routines at the start of the program, because BASIC searches for line numbers from the top.
  • Use variables instead of repeated constants.
  • Keep the board in an array that is larger than the playing area. Warp Trog's 6×6 board lives in an 8×8 array, so moves need no edge checks.
  • Move to machine language for the move generator and evaluation once the design works. Within BASIC, Warp Trog shows what is possible: a 2-ply search with alpha-beta pruning and move sorting that normally takes under fifteen seconds a move.

Troubleshooting your own game AI

  • The program misses obvious wins: the win term isn't large enough to beat the sum of the smaller terms. Keep a clear gap between levels, as with 1000/100/1 above.
  • It plays well, then blunders: a fixed-depth or horizon problem. Extend the search where captures are pending.
  • Too slow: reduce the number of moves considered (generate only sensible ones), sort moves so alpha-beta prunes more, or move the inner loops to machine code.
  • Always the same move: add small random variations to tied scores.

Further reading

  • John White, Writing Strategy Games on Your Atari (Sunshine Books, 1983; Hayden, 1984): chapters on the evaluation function, search in depth, advanced methods, openings, endgames, draughts, chess and Warp Trog.
  • Chris Crawford, The Art of Computer Game Design, chapter 6.
  • On this site: Game AI the Chris Crawford Way, Making Atari BASIC Faster (and Smaller), Sorting and Searching in Atari BASIC.

Credits