AI Game Development

Rule-Based AI

In this chapter we're going to study rule-based AI systems. Rule-based AI systems are probably the most widely used AI systems for both real-world and game AI applications. In their simplest form, rule-based systems consist of a set of if-then style rules that are used to make inferences or action decisions. Technically, we've already looked at one form of rule-based system on finite state machines. There we used rules to handle state transitions. We also looked at another type of rule-based system in the previous chapter on fuzzy logic.

In this chapter, we're going to look specifically at rule-based systems that commonly are used in so-called expert systems. Examples of real-world, rule-based expert systems include medical diagnosis, fraud protection, and engineering fault analysis. One advantage of rule-based systems is that they mimic the way people tend to think and reason given a set of known facts and their knowledge about the particular problem domain. Another advantage of this sort of rule-based system is that it is fairly easy to program and manage because the knowledge encoded in the rules is modular and rules can be coded in any order. This gives some flexibility both when coding the system and modifying the system at a later time. These advantages hopefully will become clearer to you as we move through the material in this chapter. Before we get into the details, though, let's discuss a couple of game examples that can use rule-based systems.

Imagine you're writing a real-time strategy simulation game involving the typical technology tree, whereby players must train peasants, build facilities, and harvest resources. An illustrative technology tree is shown .

Figure 1. Example technology tree

What we aim to do here is enable the computer opponent to keep track of the player's current state of technology so that the computer opponent can plan and deploy offensive and defensive resources accordingly. Now, you could cheat and give the computer opponent perfect knowledge of the player's state of technology. However, it would be fair and more realistic to have the computer gain knowledge and make inferences on the state of the player's technology in much the same way that the player will have to so that she can assess the computer opponent's state of technology. Both player and computer will have to send out scouts to collect information and then make inferences given the information as it is received. We can achieve this using a fairly simple rule-based system, as you'll see in this chapter.

Let's consider another example. Say you're writing a martial arts fighting game and you want to give the computer the ability to anticipate the player's next strike so that the computer opponent can make the appropriate countermove, such as a counter strike, a dodge, or a parry. The trick here is to somehow keep track of the player's strike patterns—combinations of kicks and punches—and to learn which strike most likely will follow an observed set of previous strikes. For example, if during the fight the player throws a punch, punch combination, what will the player most likely throw next: a punch, a low kick, or a high kick? We can use a rule-based system to achieve such anticipation. We'll come back to this example in much more detail later in this chapter.

Game Situation

When making a strategic decision in a deathmatch game, players consider many aspects of the game world. The concepts behind both factors and features are introduced in greater depth in , "Fighting Conditions," which covers decision making for weapon selection.

Influential Factors

The most important factors in the decision are those depicting combat situations and the progression of the fight. Strategic decisions have an even broader scope than weapon selection, so additional factors of the game are considered.

Player State

Decisions are very subjective by nature. Aspects of the player's status play an important role in influencing the outcome. For example, both health and armor levels may affect tactical decisions, as do weapons and ammunition available. To a lesser extent, other items in the inventory may become factors of the decision.

Enemy Status

In deathmatch games, strategies revolve around the other player(s), too. Visible properties of the enemies, such as their position or orientation, contribute the decision because they affect the player's situation in the game. As well as the relationship between players and their situation in space, the observed weapons and estimated health can become decision factors.

Environment Layout

The terrain affects the movement of all players, as well as the projectiles. The layout of the world can serve as cover and secure an escape, but can also trap the players and make them vulnerable. The disposition of the items is space also affects the best tactic. As such, high-level decisions should take the role of the environment into account.

Features of the Decision

Although factors are aspects of the game that could potentially be taken into account, features are used as inputs to the problem. Features are relevant bits of information required to make the best decision. Different properties of the environment, situation, and progression of the combat are used as features in the decision.

A set of features can be considered as an array of floating-point values corresponding to the strength of the feature: F = [f₁,f₂,K,f_n]. This strength value is easily understood when constrained to the range [0..1]—interpreted as either a probability or plausibility (fuzzy degree of truth). The decision process can take into account either interpretation as long as all the values are consistent.

Fuzzy Logic

In 1965 Lotfi Zadeh, a professor at the University of California Berkeley, wrote his original paper laying out fuzzy set theory. We find no better way of explaining what fuzzy logic is than by quoting the father of fuzzy logic himself. In a 1994 interview of Zadeh conducted by Jack Woehr of Dr. Dobbs Journal, Woehr paraphrases Zadeh when he says "fuzzy logic is a means of presenting problems to computers in a way akin to the way humans solve them." Zadeh later goes on to say that "the essence of fuzzy logic is that everything is a matter of degree." We'll now elaborate on these two fundamental principles of fuzzy logic.

What does the statement "problems are presented to computers in a way similar to how humans solve them" really mean? The idea here is that humans very often analyze situations, or solve problems, in a rather imprecise manner. We might not have all the facts, the facts might be uncertain, or perhaps we can only generalize the facts without the benefit of precise data or measurements.

For example, say you're playing a friendly game of basketball with your buddies. When sizing up an opponent on the court to decide whether you or someone else should guard him, you might base your decision on the opponent's height and dexterity. You might decide the opponent is tall and quick, and therefore, you'd be better off guarding someone else. Or perhaps you'd say he is very tall but somewhat slow, so you might do fine against him. You normally wouldn't say to yourself something such as, "He's 6 feet 5.5 inches tall and can run the length of the court in 5.7 seconds."

Fuzzy logic enables you to pose and solve problems using linguistic terms similar to what you might use; in theory you could have the computer, using fuzzy logic, tell you whether to guard a particular opponent given that he is very tall and slow, and so on. Although this is not necessarily a practical application of fuzzy logic, it does illustrate a key point—fuzzy logic enables you to think as you normally do while using very precise tools such as computers.

The second principle, that everything is a matter of degree, can be illustrated using the same basketball opponent example. When you say the opponent is tall versus average or very tall, you don't necessarily have fixed boundaries in mind for such distinctions or categories. You can pretty much judge that the guy is tall or very tall without having to say to yourself that if he is more than 7 feet, he's very tall, whereas if he is less than 7 feet, he's tall. What about if he is 6 feet 11.5 inches tall? Certainly you'd still consider that to be very tall, though not to the same degree as if he were 7 feet 4 inches. The border defining your view of tall versus very tall is rather gray and has some overlap.

Traditional Boolean logic forces us to define a point above which we'd consider the guy very tall and below which we'd consider the guy just tall. We'd be forced to say he is either very tall or not very tall. You can circumvent this true or false/on or off characteristic of traditional Boolean logic using fuzzy logic. Fuzzy logic allows gray areas, or degrees, of being very tall, for example.

In fact, you can think of everything in terms of fuzzy logic as being true, but to varying degrees. If we say that something is true to degree 1 in fuzzy logic, it is absolutely true. A truth to degree 0 is an absolute false. So, in fuzzy logic we can have something that is either absolutely true, or absolutely false, or anything in between—something with a degree between 0 and 1. We'll look at the mechanisms that enable us to quantify degrees of truth a little later.

Another aspect of the ability to have varying degrees of truth in fuzzy logic is that in control applications, for example, responses to fuzzy input are smooth. Using traditional Boolean logic forces us to switch response states to some given input in an abrupt manner. To alleviate very abrupt state transitions, we'd have to discretize the input into a larger number of sufficiently small ranges. We can avoid these problems using fuzzy logic because the response will vary smoothly given the degree of truth, or strength, of the input condition.

Let's consider an example. A standard home central air conditioner is equipped with a thermostat, which the homeowner sets to a specific temperature. Given the thermostat's design, it will turn on when the temperature rises higher than the thermostat setting and cut off when the temperature reaches or falls lower than the thermostat setting. Where we're from in Southern Louisiana, our air conditioner units constantly are switching on and off as the temperature rises and falls due to the warming of the summer sun and subsequent cooling by the air conditioner. Such switching is hard on the air conditioner and often results in significant wear and tear on the unit.

One can envision in this scenario a fuzzy thermostat that modulates the cooling fan so as to keep the temperature about ideal. As the temperature rises the fan speeds up, and as the temperature drops the fan slows down, all the while maintaining some equilibrium temperature right around our prescribed ideal. This would be done without the unit having to switch on and off constantly. Indeed, such systems do exist, and they represent one of the early applications of fuzzy control. Other applications that have benefited from fuzzy control include train and subway control and robot control, to name a few.

Fuzzy logic applications are not limited to control systems. You can use fuzzy logic for decision-making applications as well. One typical example includes stock portfolio analysis or management, whereby one can use fuzzy logic to make buy or sell decisions. Pretty much any problem that involves decision making based on subjective, imprecise, or vague information is a candidate for fuzzy logic.

Traditional logic practitioners argue that you also can solve these problems using traditional rules-based approaches and logic. That might be true; however, fuzzy logic affords us the use of intuitive linguistic terms such as near, far, very far, and so on, when setting up the problem, developing rules, and assessing output. This usually makes the system more readable and easier to understand and maintain. Further, Timothy Masters, in his book Practical Neural Network Recipes in C++, (Morgan Kauffman) reports that fuzzy-rules systems generally require 50% to 80% fewer rules than traditional rules systems to accomplish identical tasks. These benefits make fuzzy logic well worth taking a look at for game AI that is typically replete with if-then style rules and Boolean logic. With this motivation, let's consider a few illustrative examples of how we can use fuzzy

Defining the Search Area

The first step in pathfinding is to define the search area. We need some way to represent the game world in a manner that allows the search algorithm to search for and find the best path. Ultimately, the game world needs to be represented by points that both the game characters and objects can occupy. It is the pathfinding algorithm's job to find the best path between any two points, avoiding any obstacles. How the actual game world will be represented depends on the type of game. In some cases, the game world might have to be simplified. For example, a game which uses a continuous environment would probably be made up of a very large number of points that the game characters would be able to occupy. The A* algorithm would not be practical for this type of search space. It simply would be too large. However, it might work if the search area could be simplified. This would involve placing nodes throughout the game world. We then would be able to build paths between nodes, but not necessarily between every possible point in the world. This is illustrated in Figure 1.

Figure 1. Simplifying the search area

The tanks in Figure 1 are free to occupy any point in their coordinate system, but for the purposes of pathfinding, the game world is simplified by placing nodes throughout the game environment. These nodes do not correspond directly to every possible tank position. That would require too many nodes. We need to reduce the nodes to a manageable number, which is what we mean when we say we need to simplify the search area.

Of course, we need to maintain a list of the connections between the nodes. The search algorithm needs to know how the nodes connect. Once it knows how they link together, the A* algorithm can calculate a path from any node to any other node. The more nodes placed in the world, the slower the pathfinding process. If pathfinding is taking too many CPU cycles, one alternative is to simplify the search area by using fewer nodes.

On the other hand, a game that uses a tiled world would be a good candidate for the A* algorithm, assuming, of course, that the world isn't unreasonably large. It would be a good candidate because essentially the world already would be divided into nodes. Each tile would be a node in the search area. This is illustrated in Figure 2.

Figure 2. Tiled search area

Tiled environments, such as the one shown in Figure 2, are well suited to the A* algorithm. Each tile serves as a node in the search area. You don't need to maintain a list of links between the nodes because they are already adjacent in the game world. If necessary, you also can simplify tiled environments. You can place a single node to cover multiple tiles. In the case of very large tiled environments, you can set up the pathfinding algorithm to search only a subset of the world. Think of it as a smaller square within a larger square. If a path cannot be found within the confines of the smaller square, you can assume that no reasonable path exists.

Bresenham algorithm

if (deltaCol >deltaRow)

    {

     fraction = deltaRow *2-deltaCol;

     while (nextCol != endCol)

      {

       if (fraction >=0)

        {

         nextRow =nextRow +stepRow;

         fraction =fraction -deltaCol;

        }

       nextCol=nextCol+stepCol;

       fraction=fraction +deltaRow;

       pathRow[currentStep]=nextRow;

       pathCol[currentStep]=nextCol;

       currentStep++;

      }

    }

   else

    {

     fraction =deltaCol *2-deltaRow;

     while (nextRow !=endRow)

      {

       if (fraction >=0)

        {

         nextCol=nextCol+stepCol;

         fraction=fraction -deltaRow;

        }

       nextRow =nextRow +stepRow;

       fraction=fraction +deltaCol;

       pathRow[currentStep]=nextRow;

       pathCol[currentStep]=nextCol;

       currentStep++;

      }

     }

    }

The initial if conditional uses the values in deltaCol and deltaRow to determine which axis is the longest. The first block of code after the if statement will be executed if the column axis is the longest. The else part will be executed if the row axis is the longest. The algorithm will then traverse the longest axis, calculating each point of the line along the way. Figure 1 shows an example of the path the troll would follow using the Bresenham line-of-sight algorithm. In this case, the row axis is the longest, so the else part of the main if conditional would be executed.

Figure 1 . Bresenham tile-based chase

Figure 1 shows the troll's path, but of course this function doesn't actually draw the path. Instead of drawing the line points, this function stores each row and column coordinate in the pathRow and pathCol arrays. These stored values are then used by an outside function to guide the troll along a path that leads to the player.