AI

Although Eastern Front (1941) is remembered primarily for its scrolling map, I can take no credit for that; it was built into the hardware. The design element of which I am most proud is the AI for the game. At a time when many wargames were still being written in BASIC, my design boasted two major innovations.

The first of these was the threaded execution. All of the I/O was executed during the Vertical Blank Interrupt (VBI), a routine that executed once each 60th of a second, synchronized with the vertical blank period of the television set. This was the only good time to mess with the display, as changes to the display while the beam was drawing it were likely to yield irritating rips or tears in the image. So I set up all I/O through the VBI routine, which meant in turn that the mainline program the one that executed in the absence of interrupts could operate in the background while the player worked in the foreground. In other words, even as the player was entering his own orders, the program was figuring the Russian move.

The more important innovation, of course, was the algorithm for planning the Russian move. This time, I told myself, I was going to solve the problem of figuring a front line. My initial plan had been to start at one edge of the map, select the closest Russian unit to begin the line, and then somehow trace a line through other Russian units to the opposite edge of the map. This idea broke to pieces against a nasty problem: what to do if the line were broken? If the Germans achieved a complete breakthrough, would my algorithms break down and lead to a total collapse of the Russian position?

This led me to think of the line from the point of view of individual units. Since they might be operating in some isolation, it would be necessary to think of each unit as a fragment of a line; my algorithm then needed only to find a way to link together such fragments.

At the time I was designing the AI, there were no zones of control (ZoC) in the movement system. The concept of the zone of control was developed for board wargames way back in the 1950s. In such games, each unit projected a zone of control into each of the squares (or hexes) adjacent to it. Movement from one ZoC square into another ZoC square was forbidden. With ZoCs, you didn't need a solid front line; you could hold the line with a thin string of units. Yet you could still concentrate lots of units in the spaces to mount an offensive. It was a winning idea, and most board wargames used it. Yet I chose not to use this design construct in Eastern Front (1941). I had initially believed that my unit densities were so high that it would not be difficult to trace a continuous line.

All this meant that my algorithms should be directed toward gap-filling in the line. The overall course of the line, I expected, would remain intact through the game; I needed only find a scheme for plugging holes that might develop.

One of the big questions that bedevil many designers is the problem of whether to design the AI to be bottom-up or top-down. In a top-down design, the AI system starts off by looking at the grand strategic situation, figuring out what needs to be done, and then trickles these decisions down to the individual units. In a bottom-up design, the AI is applied to the individual units without any central coordinating authority. Each unit follows its own nose in planning its move. This type of AI, when it works, yields what is called emergent behavior. When it doesn't work, it yields what is termed a turkey.

I decided on the latter course because I expected that Russian units might face chaotic situations where they would need to think for themselves. Besides, this allowed me to break the problem down into smaller steps that could be addressed in increments, so that the program would not need to complete some monstrous calculation before it could begin the turn.

For this discussion, I will present the system I used in the final version, which used a 5-wide square for analysis. In the initial design, I used only a 3-wide square; later on, it occurred to me that I could improve the overall quality of the AI by simply extending the 3-wide square notions into a 5-wide square. I am proud to say that my code had been so cleanly written that the conversion from 3-wide squares to 5-wide squares went smoothly. So here is what my 5-wide square might look like under analysis (see Figure 18.2).

18.2. Grid for AI computation.

The five rectangular symbols with crosses in them are standard military symbols for infantry units.

The first problem to tackle is, what is the direction of the front line? Does the line trace right to left, or up and down? Given the fluidity of the Eastern Front, I could not assume some standard direction; German units sometimes found themselves attacking toward the west. My answer to this problem was simple and clean: danger is a vector, not a scalar. When evaluating its tactical situation, each unit must first evaluate how much danger it finds itself in and the overall direction from which that danger emanates. The algorithm calculates the overall danger coming from each of the four cardinal directions, and then evaluates the strength of the defensive position against that danger. This is done for each of the four cardinal directions, so the 5-wide square above is, in effect, rotated through each of its four possible orientations.

The details of the algorithm are quite messy, especially because I didn't have hardware multiplication and division. I made use of doubling and halving by the simple expedient of shifting a byte to the right or left, but if I wanted 16-bit precision, I had to carry the bits between the low byte and the high byte. The thrust of the algorithm is to assign points for each column that is occupied, with adjustments for the straightness of the line. This is done by looking at vertical offsets between pairs of units; in a good line, those vertical offsets are minimal. Thus, points are assigned to each square, representing the overall utility of the unit positioning itself there. The unit simply selects the best square and plots a path to it.

The algorithm had a nicely convergent behavior: Each unit determined its objective square, taking into consideration the objective squares of every other unit. As the algorithm ran through more and more iterations, it converged on an ideal move for the Russian player.

"No plan survives contact with the enemy" so goes the military adage. Such was the case with the behavior of units in Eastern Front (1941). Their carefully laid plans were based on the assumptions that the Germans would all cooperatively remain in their original positions. The fact that those Germans did in fact move wrought havoc with the Russian plans but then again, the Russian moves did exactly the same thing to German plans. It's an unavoidable problem in war. My AI made no attempt to anticipate German plans.

LESSON 41

Don't panic. Take the time to evaluate the design as a whole.

Looking back at this old assembly language code from the vantage point of twenty additional years of experience, I see only a few improvements to make. The code ran fast, so I could have stepped up to a 7-wide square to get even better coordination of behavior. The code was insufficiently documented, although I was able to figure out its workings even after twenty years have passed. In particular, I should have given more labels to my constants. The incidence of mysterious values ("LDX #$97", for example) detracts considerably from the cogency of the code.