Intelligent Behavior Without AI:

An Evolutionary Approach

Neil Kirby

4653 Reynoldburg-New Albany Rd.

New Albany OH. 43054

 

Introduction

This talk describes way to give intelligent behavior to computer operated objects. It traces the evolutionary approach used in the "auto" program of the "bots" family of games. The bots system is described to provide a context, and the results of each step in the evolution are discussed. While the changes made are particular to the auto program, the method is applicable to other programs. The fundamentals of the method are:

    1. Analyze good and bad behaviors.
    2. Quantify parameters to new algorithms.
    3. Apply constant evolutionary pressures by repeatedly testing.

The structure of the method drives the structure for the body of the paper. Most paragraphs start by stating problems found with the program. This is followed by the parameters identified and algorithms used to solve the problem. Finally, the results of the change will be given. The auto program has progressed from hopeless stupidity to well above average play skills without any formal AI methods.

The Basic Approach

The basic approach greatly resembles classical Darwinistic evolution. Start with simplistic behavior, however bad. Simple behavior is best described as whatever is easiest to code. Analyze the failures of the simple methods. If available, observe the differences between successful behavior, especially that of human players, and the failures of the computer players. The most difficult step is to identify the parameters that can be used to control successful behavior. Once this has been done, use regular code to allow the program to react to these parameters. Complete the process by repeatedly testing in play. The ease of fast, repeated play afforded by computerization accelerates the process. This approach is easily observed in the auto program.

The Bots Family of Games

The auto, aero, and bots programs make up the bots family of multiplayer, tactical ground and air combat games. These run under the Unix System V® operating system and are written entirely in the C programming language. Bots and auto deal with futuristic ground combat units loosely comparable to tanks. The bots program is used by human players and auto is the computer managed equivalent. The family of games supports but does not require team play. There are a variety of weapons systems available, each with different characteristics.

The lasers are relatively light in mass, short ranged, and power hungry. Mortars require heavy ammunition, but have great range. Autocannon inflict moderate damage to moderate ranges, but they too require a large amount of moderately heavy ammunition. Missiles have varying ranges and warheads, but they can be shot down by point defenses, and they too, are heavy. Particle beam weapons are highly effective in a narrowly focused range. Aside from mortars and particle beams, most weapons improve as range to target shortens. Further detail are given in appendix 1.

Incoming fire hits one of six armour facings. Armour is ablative; each point of damage removes one point of armour. Once an armour face is destroyed, any further fire hits internal systems such as power, control, life support, weapons, and chassis. Damage to a unit can be repaired if the unit survives.

To be successful in play, a unit must maneuver effectively, fire its weapons , and evade enemy fire. It should distribute enemy fire across multiple armour facings. If team mates are present, a unit should coordinate fire among the team members to combine fire against single enemy units. If a unit takes damage, it should flee until it is repaired. Repair and reload are available every ten game turns. The richness of detail is comparable to Star Fleet Battles® .

Auto units are not allowed to cheat. The behavior code can not access information that a human player in the same situation would not have. This advantage was considered at first, but has proven to be not needed. No auto program was written for aero units.

The Original Algorithm

The original algorithm for autos was quite simple. The closest enemy unit was selected as the target. All other units were ignored. The auto turned to face the enemy and attempted to close. (see Fig. 1) After maneuvers were complete, the unit attempted to fire its weapons. The fire target was the closest enemy within the arc of the weapons fire. The unit would not flee if damaged.

Figure 1: Rotate to face, then move.

There were a number of failures with the original algorithm. Foremost among these was the propensity for the unit to lose its center forward armour and take severe internal damage while the left and right forward armour facings were pristine. The solution to this problem was for the unit to shorten the amount it moved in order to save sufficient mobility to rotate at the end of its motion. (See Fig. 2) This rotation would bring the strongest forward armour to face the closest enemy unit. The parameter that enabled this change was relative bearing. This change typically tripled the survival of all units. It especially allowed units with short range weapons to close to their effective ranges.

Figure 2: Rotate, move, rotate.

The modified algorithm still had major problems. During a long closure, a unit would loose all three forward armour facings, continue closing, and take fatal internals. The fix involved self assessment. Before a unit started maneuvers, it would evaluate the state of its forward armour, internal systems, and ammunition. If all three forward armour facings were below minimum, half of any internal system was destroyed, or if ammunition was gone, then the unit would declare itself to be unfit for battle and flee. It would turn its strongest rear armour towards the closest enemy and move as far as possible. If the unit had a jump pack available, it would jump as far as possible. It would elect not to shoot power based weapons to save energy for mobility. The parameters for this change were simple integer numbers; armour, systems, and ammunition counts. This change increased the long term survivability of the auto units greatly. In rolling terrain, enemy units would simply disappear when they were seriously damaged. Destroying a unit often required a long chase.

At this point, auto units were interesting but not threatening. Their maneuvers were highly predictable. At point blank range a unit would close to zero range and stop. Since all motion in bots is simultaneous, a human player would simply step forward and turn around, finding themselves at near zero range facing the back of the auto unit. Fatal internals for the auto unit often soon followed. For long range units such as mortars, and specific range units such as particle beam weapons, continuos closure was especially counter productive. Mortar units have a minimum range requirement, and care very little about range otherwise. In the laser family, where closure improves damage, closure also gives the advantage to the lightest and shortest ranged lasers. The fix was to establish a preferred battle range (known as BRG) for each weapon type. The parameter used with BRG was range.

BRG numbers were tuned during play. While many weapons benefit from close range, BRG was picked to allow both survivability and the ability to inflict damage. Long range units would prefer to stay at range, denying short range units any fire. If a unit found itself too close, it would back up as much as it could. Backing up costs twice as much as forward motion. BRG helped to keep the long range support units out of trouble, and it helped all units survive combat with a shorter ranged unit. Short range units were still too predictable, and easy for human players to destroy. But BRG was the evolutionary step that set the stage for a major milestone in auto evolution.

The First Major Milestone Change: New Maneuver Code

Figure 3: BRG and Mobility circles.

The problem with the maneuver code was predictability. The new maneuver code dealt with the answers to two questions: "Where can a unit go?" and "Where does a unit want to go?" The first question is answered by computing the mobility of a unit, which is based on its power and mass. The unit can get to any point on a circle, centered on the unit, of radius equal to the mobility of the unit. The second question is answered by BRG. Assuming that the target does not move, the most effective place to be is some place on a circle, centered on the target, of radius BRG. (See Figure 3) If the two circles do not intersect, the existing closure code is used. If the circles intersect, there are three possibilities.

Figure 4: Mobility encompasses BRG.

The first possibility is shown in Figure 4. This is the most dangerous case for the target, and the best case for the attacker. This situation is most often seen when a high mobility unit carrying short ranged weapons attacks. The unit will pick a random point on the BRG circle, move to it, and turn to face the target. For the target to evade, it must either move far enough to get out of range, or it must move behind the random point on the BRG circle where the attacker will appear. Neither of these evasions is easy, the first requires good mobility, and the second requires good luck. If the target does move far enough away to deny weapons fire, the attacker will have more power available to move next time.

Figure 5: Mobility intersects BRG.

The second possibility is shown in Figure 5. This is a good case for any attacker. This situation is most often seen when a medium or high mobility unit carrying medium range weapons attacks. The unit randomly picks one of the two intersection points, moves to it, and turns to face the target. Only a target with more mobility than the attacker will be able to out maneuver the attacker. As figure 5 moves towards figure 4, the attacker becomes nearly impossible to evade.

 

 

Figure 6: Mobility inside BRG.

The third case is shown in Figure 6. The mobility circle is inside the BRG circle, which means that the attacker is too close. This is usually the case when a low mobility unit carrying long ranged weapons is closer than desired to an enemy unit. In this case the unit determines if it would get farther away by backing up or by turning away, moving forward, and turning again to face the target. It takes the choice that takes it farthest away and executes those maneuvers.

The parameters for the change were BRG and computed mobility, combined in an effective algorithm. The effect of the first milestone change was dramatic. Attacking units were much more effective (fleeing units were unaffected). Human players could no longer destroy auto units without pause. Close combat maneuvers became very dicey. Novice players had only a 50% chance of winning a one-on-one duel. In single combat, auto units played a solid, if uninspired, game and they never made stupid errors.

The team play of autos still lacked a great deal - they fought as a mob, rather than as a team. Any unit that could see no targets would pick a random patrol point on the map and head towards it. This scattering behavior was good for finding hidden enemy units, but poor for fighting enemy teams. If one unit on a team was engaged, the rest of the team would ignore the combat unless they too could see the target. Evolution continued, as auto units learned basic communications skills. A unit that could see no targets would ask its team for targeting information. The other units (aero, auto, and bots) on the same team would reply with the map coordinates of the targets that they could see. These coordinates could be used the next turn to plot motion. Units that did not require line-of-sight to fire, such as mortars, would fire blindly on the map coordinates given. The effects of this change were twofold. It allowed high mobility units carrying short-ranged weapons to close upon enemy units that they could not see. This meant that once an enemy unit was spotted, all unoccupied autos would head towards it, even in rolling terrain. The second effect was to provide mortar teams with something effective to do. This proved to be an effective change. To the enemy units, it meant to expect mortar fire whenever spotted by any member of the auto team. A particularly nasty combination was to be stalked by an unseen stealth unit that was broadcasting coordinates to its mortar teammates. This change tended to keep mobs of autos together, but they still fought as a mob.

The Second Major Milestone Change: Team Play

Targeting was still based on the closest enemy that could be fired at. In team play, a lone unit could distract part of a team of autos and play Pied Piper while the rest of the Piper's team destroyed the other part of the auto team. The Piper might not survive, but while it was being destroyed, multiple enemy units would be destroyed, tipping the battle against the autos. The second milestone change was increased team play. Team play was based on the concept of the team target. The enemy unit that appeared to be hurt the most would be designated as team target. This designation was based on the volume of fire an enemy had absorbed. The team target would always be the preferred target for motion control. If the team target met certain criteria, it would be the preferred target for fire as well. The criteria was that the team target had to be between the minimum and maximum effective range for the weapons fired. The results were often devastating and occasionally quite strange. The devastating part stemmed from the fact that a single unit, often already damaged, could now take all the mortar, long range missile, autocannon, and much of the short range laser fire that an entire team could inflict. The strange part would happen when an auto unit would move directly past and ignore a closer target in order to help destroy the team target. If the team target was not a viable target, each unit would fire as before, usually at the closest target.

Mishaps in team play were now fatal. Teams of experts were now doing well to achieve a kill ratio of 2.5:1 in favor of the experts. Novice teams required two to five times numerical superiority to win. The parameters used had been developed in earlier stages of evolution.

Evolution continued as details were refined to solve minor problems. One problem was that autos would only use a jump pack to flee or to cross water. This meant that they would often have an unused jump pack at reload time, when a new jump pack would be available. The fix was simple; units still carrying a jump pack that were near their reload time would be free to jump to increase their mobility. The parameter used was the units turn counter, which already existed. This change made it dangerous to rely on predictions about the mobility of an auto unit. A fast moving unit that had been moving four ranges per turn would suddenly jump eight and move four more for a total of twelve ranges of motion when only four were expected.

The final changes involved dealing with aeros. Bots and autos usually move one to four ranges per turn. Aeros need to move at least ten to retain airspeed, and speeds of twenty to fifty are normal. Normal altitudes for aeros typically run from eight to twenty ranges of altitude. The first problem aeros created was that autos would attempt to set up motion based on an aero target. Since the motion algorithms are optimized for non-moving targets, using an aero to set up motion was ineffective for units with a short BRG. It was ineffective for units with a long BRG if the aero was close by since the bearing of the aero would change dramatically. Even if perfect predictive algorithms were available, only units with a long BRG have sufficient range to hurt aeros at altitude. The important changes were range based. All units that had a BRG of 25 or higher would prefer any visible enemy aero to all other targets for fire and motion. Units with lower BRG would ignore aeros when plotting motion, but if an aero was somehow in acceptable range, it would be the preferred fire target. At reload time, autos remembered if they had seen any aeros since last reload and changed their hardpoint weapons mix to prefer anti-aircraft missiles. The changes were effective. The much maligned mortar unit provided greatly needed flak fire. Other less popular long BRG units gained a new role. The advent of the stealth anti-aircraft missile battery eased the problems ground units had with aeros.

There are still a number of deficiencies with the auto program. Complex terrain tends to mystify autos, especially urban terrain and bridges. An auto unit will occasionally present weak or down armour towards one enemy while fighting another. This single mindedness also shows up when a damaged unit flees. Motion directly away from the closest enemy, which is always correct in one-on-one, can be fatal when intermixed with an enemy team.

Observations About The Process

A number of observations are worth examining. The first of these is that the process of analysis and synthesis is regenerative. The initial BRG change set the stage for the first milestone change (maneuver code). BRG also led to min/max range, which when coupled with communications led to the second milestone change (team play). Some of the other analysis that went on made it possible and more probable that algorithms could be generated to improve poor behavior.

Not as obvious in the paper is the fact that intensive testing helps drive the process. The entire evolutionary cycle mentioned above took place at lunchtimes over the course of a year. The playtesting allowed the author to observe human behavior in order to model it, and it clearly showed any deficiencies in the algorithms.

One very hopeful point is that simple methods often suffice. The long closure code and the code for flight is quite simple but has proven to be very effective. The early code which had numerous deficiencies was still interesting and fun. Between the first and second milestone changes, there was at times the semblance of team behavior by default. If a given enemy unit was the best or only target available to a team, the entire team fired upon it. In rolling terrain this would be fatal as one unit encountered groups of enemy units.

A final point is that the code is well behaved. It is small, runs quite rapidly, and is easy to follow. The behavior control parts of the code do not require any extensive calculations. The code is short, only two files. In fact, the auto program has less source and a smaller executable than the bots program. The increase in size from automation are more than offset by the reduction in size gained by deleting the user interface. The control flow of the code is relatively easy to follow, and therefore easy to modify.

Conclusions:

The evolutionary method is a viable alternative to exploring AI methodologies. The method is universally available to programmers who have sufficient time for repeated testing. It is well suited to game programs where the computer and human players deal with the same objects and information - the programmer can model computer behavior on successful human behavior. The method fails when the programmer can not identify the keys to changing poor behavior and the default simple methods are ineffective. For the multiplayer, tactical combat games that this author has written, the methods have produced effective code that is fast, compact, and often pleasingly simple.