Game AI the Chris Crawford Way: Point Systems, Danger Fields and Virtual Moves

Atari text screen with three E enemies, two F friends and a dotted path showing unit U advancing towards the enemies; a row of B and T letters records bold and timid decisions

Chris Crawford wrote some of the most admired strategy games on the Atari 8-bit, including Eastern Front 1941, Tanktics and Legionnaire, and he also wrote about how he did it. In The Art of Computer Game Design (written in 1982), he explains the methods he used to give the computer side a convincing mind of its own. He called them "artificial smarts", because they were too modest to deserve the name artificial intelligence. They are still a good model for anyone writing a strategy or war game in BASIC or assembly language today.

What you'll learn: the four ways to balance a human against a computer opponent, what makes computer behaviour seem reasonable but not predictable, point systems, danger and safety fields (with a running demo), coordinating many units, switching between algorithms, and when to simply change the game.

What you need: nothing to read the ideas. Atari BASIC for the demonstration program, which was run in the atari800 emulator.

1. Four ways to make a fair fight

Crawford starts from an uncomfortable fact. A computer is quick at arithmetic but poor at the pattern recognition and judgement that humans are good at, and games are played on human ground. He lists four ways to even things up:

  • Vast resources. Give the computer many weak, simple-minded units, as Space Invaders and Missile Command do. It is easy to program, since one routine runs in a loop for every enemy, and it makes the player the underdog. Its drawback, he notes, is that everyone does it.
  • Artificial smarts. Give the computer real decision-making routines, tailored to the game.
  • Limited information. Hide things from the player, as long as the reason is natural, such as needing scouts to see the enemy. Information withheld artfully tickles the imagination. Information withheld at random just confuses.
  • Pace. Make the game so fast that the human can't think. Crawford discourages this, because it stops the player investing themselves in the game.

Real games mix all four. Even after all his work, Crawford reports that his own computer players still needed a force ratio of at least two to one to hold their own against a human.

2. Reasonable, but not predictable

His two requirements for artificial smarts:

  1. Reasonable behaviour. No driving tanks over cliffs or parking in front of the enemy's guns. He warns against the tempting approach of listing every stupid move and testing for each one, because "the computer can demonstrate unanticipated creativity in the stupidity of its mistakes". It is better to design a general method that avoids absurd moves as a side effect.
  2. Unpredictability. If the player can second-guess the computer, the illusion of intelligence collapses.

The way to get both, in his experience, is to avoid "particular" algorithms that focus on one feature of the situation. "Fire at the closest enemy" is reasonable but predictable. A better rule weighs many factors at once: threat, vulnerability, range, facing, cover and the positions of friendly units, and fires only if the chance of a kill outweighs the chance of being killed. Behaviour that comes from many considerations is still sensible, but much harder to anticipate.

3. Point systems

The practical tool is a point system: give every possible move a score built from many factors, and take the best. Crawford flags two difficulties:

  • Dynamic range. In 8-bit arithmetic a score tops out at 255. If two moves can both reach the maximum, you can no longer tell which is better. Scale the factors so that this almost never happens.
  • Balancing factors. If a hilltop is worth 15 points, what is a road worth? Only deep familiarity with the game answers that, and you can't have it before the game exists. So expect a long period of experimenting.

This is the same idea as the evaluation function of board-game programs, which John White's Writing Strategy Games on Your Atari builds up from chess material counts. Crawford's point is that most games, unlike chess, can't be searched move by move, so the evaluation has to carry all the intelligence.

4. Fields: pattern recognition on the cheap

Human players read a map at a glance. Crawford's substitute is field analysis: a calculated quantity over the map that captures what a unit needs to know. In several of his wargames he used danger and safety fields:

  • Danger at a square is the sum, over every enemy unit, of its strength divided by its range. Big, close enemies are very dangerous, and small, distant ones barely count.
  • Safety is the same sum over friendly units.

A unit compares danger and safety at its own square and decides whether to be bold or timid. Then it looks at each square it could move to and scores danger minus safety. A bold unit moves towards the highest value (towards the fight), and a timid one towards the lowest.

Here is that recipe as an Atari BASIC demo. Three enemies (E) and two friends (F) are placed on a text screen. One computer unit (U) of strength 3 makes 16 moves, leaving a dotted trail, and the top line records each decision: B for bold, T for timid.

10 REM DANGER AND SAFETY FIELDS (AFTER CHRIS CRAWFORD)
20 DIM EX(3),EY(3),ES(3),FX(2),FY(2),FS(2),M$(1)
30 GRAPHICS 0:POKE 752,1:SETCOLOR 2,0,0:SC=PEEK(88)+256*PEEK(89)
40 FOR I=1 TO 3:READ X,Y,S:EX(I)=X:EY(I)=Y:ES(I)=S:POKE SC+Y*40+X,37:NEXT I
50 FOR I=1 TO 2:READ X,Y,S:FX(I)=X:FY(I)=Y:FS(I)=S:POKE SC+Y*40+X,38:NEXT I
60 DATA 30,6,9,33,12,6,27,17,8
70 DATA 5,9,6,8,15,5
80 UX=10:UY=11:US=3
90 FOR T=1 TO 16:POKE 77,0
100 X=UX:Y=UY:GOSUB 500:B=(D<=SF)
110 BV=-1E9:IF NOT B THEN BV=1E9
120 FOR DX=-1 TO 1:FOR DY=-1 TO 1
130 X=UX+DX:Y=UY+DY:IF X<1 OR X>38 OR Y<2 OR Y>21 THEN 170
140 IF PEEK(SC+Y*40+X)=37 OR PEEK(SC+Y*40+X)=38 THEN 170
150 GOSUB 500:V=D-SF
160 IF (B AND V>BV) OR (NOT B AND V<BV) THEN BV=V:NX=X:NY=Y
170 NEXT DY:NEXT DX
180 POKE SC+UY*40+UX,14:UX=NX:UY=NY:POKE SC+UY*40+UX,53
190 M$="T":IF B THEN M$="B"
200 POSITION 2+T*2,0:? M$;
210 NEXT T
220 POSITION 2,23:? "E ENEMY  F FRIEND  U UNIT";
230 POKE 77,0:GOTO 230
500 REM DANGER D AND SAFETY SF AT X,Y
510 D=0:FOR I=1 TO 3:R=ABS(EX(I)-X):IF ABS(EY(I)-Y)>R THEN R=ABS(EY(I)-Y)
520 D=D+ES(I)/(R+1):NEXT I
530 SF=US:FOR I=1 TO 2:R=ABS(FX(I)-X):IF ABS(FY(I)-Y)>R THEN R=ABS(FY(I)-Y)
540 SF=SF+FS(I)/(R+1):NEXT I:RETURN

Notes on the program:

  • Range is the larger of the horizontal and vertical distances, which suits an 8-way grid. The +1 avoids dividing by zero. The unit's own strength counts towards its safety (line 530).
  • B=(D<=SF) uses the fact that an Atari BASIC comparison is 1 when true and 0 when false.
  • Characters go straight into screen memory: 37 is E, 38 F, 53 U and 14 . in internal code.

In our run, the unit advanced boldly for fourteen moves, felt the danger outweigh its safety near the enemy group, retreated one step as timid, and then turned bold again. That last flicker is exactly the problem section 6 describes. Change US, the strengths in the DATA lines or the positions and watch the behaviour change. Raising the unit's strength makes it press home the attack, and moving the friends closer makes it braver.

5. Many units: virtual moves

Moving many computer units at once raises a coordination problem. Crawford's first approach was to move units one at a time, each avoiding the others' current positions. He reports that this "replaces collisions with the most frustrating traffic jams". His better method is a virtual move system:

  1. Copy every unit's real position into a "virtual position" array.
  2. Let each unit plan its move against the virtual positions of all the others, then write its own planned destination into the virtual array.
  3. Repeat the whole pass several times, each time planning against the latest virtual positions, until the plans settle.
  4. Only then move the real units.

The units negotiate their way around each other before any of them moves. The Creative Atari review of Eastern Front 1941 noted a related trick: the Russian side's analysis runs while the human is still giving orders, so "the longer the German player takes to form his strategy, the better the Russian strategy will be".

6. Switching algorithms safely

No single routine works in every situation, so designers switch between several. The switch points are dangerous. In Legionnaire, Crawford's barbarians had "run for safety", "approach to contact" and "attack" routines. A bold barbarian would charge, switch to "attack", judge the attack unsafe, switch to "run for safety" and flee, so players watched barbarians charging and retreating without ever fighting. His fix was to merge them into a single "advance to attack" routine with no transitions. The demo above shows a mild version of the same effect at the moment it changes from bold to timid. Some hysteresis, such as requiring danger to exceed safety by a margin before turning timid, is a cheap cure.

7. When in doubt, change the game

The most practical advice of all: if a feature can't be handled well by your algorithm, remove it. In Tanktics, concave lakes trapped the computer's tanks, which drove to the shore, backed off and returned. After a lot of wasted effort on a smarter routine, the solution was to take concave lakes off the map. Experienced designers learn to spot such intractable features early. Everyone else learns it the hard way.

8. Non-spatial games

Simulations such as Hammurabi, Lunar Lander, and Crawford's own Energy Czar and Scram need a different kind of smarts: a stable model of a complex system. His advice is to be wary of more than about four coupled equations (Energy Czar used 48, kept believable only by many constraints), to prefer the same equation applied across an array of values, and to give each equation an empirically tuned damping factor:

new value = old value + (driving factor / damping factor)

Small damping gives lively, bouncy systems. Large damping gives sluggish ones, and can make variables run away when there is negative feedback.

Troubleshooting your own AI

  • Units cluster in corners or freeze: the field has local maxima. Add a small random term, or a term for distance to an objective.
  • Units dither back and forth: too many algorithm switches, or a field that is nearly flat. Add hysteresis, or merge the routines.
  • Behaviour is easy to predict: the score depends on one dominant factor. Add more factors.
  • Two moves always tie at the maximum score: a dynamic-range problem. Rescale the point values.

Further reading

  • Chris Crawford, The Art of Computer Game Design (written 1982; the electronic edition is hosted by Washington State University Vancouver), chapter 6 "Design Techniques and Ideals".
  • "Eastern Front: The Atari Goes to War", in The Creative Atari (Creative Computing Press, 1983).
  • John White, Writing Strategy Games on Your Atari (Sunshine Books, 1983; Hayden, 1984): evaluation functions and search, in BASIC.
  • On this site: Studying the Star Raiders Source Code, the news item on Eastern Front 1941 rebuilt from its source, and Writing a Complete Game in Atari BASIC, Step by Step.

Credits