Expert systems solve problems that are usually solved by specialized humans. For example, if you go to a doctor, he will analyze you (either by asking you a set of questions or doing some analysis himself), and according to his knowledge, he will give you a diagnosis.

An expert system could be the doctor if it had a broad enough knowledge base. It would ask you a set of questions, and depending on your answers, it would consult its knowledge base and give you a diagnosis. The system checks each of your answers with the possible answers in its knowledge base, and depending on your answer, it asks you other questions until it can easily give you a diagnosis.

For a sample knowledge tree, take a look at Figure 20.1. As you can see, a few questions would be asked, and according to the answers, the system would follow the appropriate tree branch until it reached a leaf.

Figure 20.1. An expert system's knowledge tree

Very simple medical expert system this could be. Note that this is all just pseudocode, based on a fictional scripting language, and will not compile in a compiler like Dev-C++ or Visual C++. This is not intended to be a functional example, just a glimpse at what an expert system's scripting language might look like.

Answer = AskQuestion ("Do you have a fever?");
if (Answer == YES)
 Answer = AskQuestion ("Is it a high fever (more than 105.8 F)?");
 if (Answer == YES)
     Solution = "Go to a hospital now!";
 end if
 Is Sick?
 NO  YES
 Has a fever?
 NO  YES
 Has problems breathing?
 NO  YES
 High fever?
 NO  YES
 Send home
 . . . Lung Infection Do more analysis . . .
else
 Answer = AskQuestion ("Do you feel tired?");
 if (Answer == YES)
  Solution = "You probably have a virus, rest a few days!";
 else
  Solution = "Knowledge base insufficient. Further diagnosis needed.";
 end if
else
 Answer = AskQuestion ("Do you have problems breathing?");

 if (Answer == YES)
  Solution = "Probably a lung infection, need to do exams."
 else
  Solution = "Knowledge base insufficient. Further diagnosis needed.";
 end if
end if

As you can see, the system follows a set of questions, and depending on the answers, either asks more questions or gives a solution.

Fuzzy logic expands on the concept of an expert system. While an expert system can give values of either true (1) or false (0) for the solution, a fuzzy logic system can give values in between. For example, to know whether a person is tall, an expert system would do the following (again, this is fictional script):

Answer = AskQuestion ("Is the person's height more than 50′ 7″?");
if (Answer == YES)
 Solution = "The person is tall.";
else
 Solution = "The person is not tall.";
end if

A fuzzy set would appear like so:

Answer = AskQuestion ("What is the person's height?");
if (Answer >= 5′ 7″)
 Solution = "The person is tall.";
end if
if ((Answer < 5′ 7″) && (Answer < 5′ 3″))
 Solution = "The person is almost tall.";
end if
if ((Answer < 5′ 3″) && (Answer < 4′ 11″))
 Solution = "The person isn't
else
 Solution = "The person isn't tall.";
end if

The result would be fuzzy. Usually a fuzzy set returns values from 0 (false) to 1 (true), representing the membership of the problem. In the last example, a more realistic fuzzy system would use the graph shown in Figure 20.2 to return a result.

Figure 20.2. Fuzzy membership.

As you can see from the graph, for heights greater than 5′ 7″, the function returns 1; for heights less than 4′ 11″, the function returns 0; and for values in between, it returns the corresponding value between 5′ 7″ and 4′ 11″. You could get this value by subtracting the height from 5′ 7″ (the true statement) and dividing by 20 (5′ 7″ –4′ 11″, which is the variance in the graph). In code, this would be something like the following:

Answer = AskQuestion ("What is the person's height?");
if (Answer >= 5′ 7″)
 Solution = 1
end if
if (Answer <= 4′ 11″)
 Solution = 0
else
 Solution = (Answer - 5′ 7″) / (5′ 7′ - 4′ 11″)
end if

You might be wondering why you don't simply use the equation only and discard the if clauses. The problem with doing so is that if the answer is more than 5′ 7″ or less than 4′ 11″, it will give values outside the 0 to 1 range, thus making the result invalid.

Fuzzy logic is extremely useful when you need reasoning in your game.

Using genetic algorithms is a method of computing solutions that relies on the concepts of real genetic concepts (such as evolution and hereditary logic). You might have had a biology class in high school that explained heredity, but in case you didn't, the field of biology studies the evolution of subjects when they reproduce. (Okay, maybe there is a little more to it than that, but we are only interested in this much.)

As you know, everyone has a blood type, with the possible types being A, B, AB, and O, and each of these types can be either positive or negative. When two people have a child, their types of blood will influence the type of blood the child has. All that you are is written in your DNA. Although the DNA is nothing more than a collection of bridges between four elements, it holds all the information about you, such as blood type, eye color, skin type, and so on. The little “creatures” that hold this information are called genes.

What you might not know is that although you have only one type of blood, you have two genes specifying which blood type you have. How can that be? If you have two genes describing two types of blood, how can you have only one type of blood?

Predominance! Certain genes’ information is stronger (or more influential) than that of others, thus dictating the type of blood you have. What if the two genes’ information is equally strong? You get a hybrid of the two. For the blood type example, both type A and type B are equally strong, which makes the subject have a blood type AB. Figure 20.3 shows all the possible combinations of the blood types. From this table, you can see that both the A and B types are predominant, and the O type isn't. You can also see that positive is the predominant type.

Figure 20.3. Gene blood type table.

So, how does this apply to the computer? There are various implementations that range from solving mathematical equations to fully generating artificial creatures for scientific research. Implementing a simple genetics algorithm in the computer isn't difficult. The necessary steps are described here:

And thus you will have a child that is the product of the two best subjects in the population. Of course, to make a nice simulator you wouldn't use only two of the subjects—you would group various subjects in groups of two and mate them to form various children, or offspring. Now I'll explain each of the steps.

You first need to use the initial population (all the subjects, including creatures, structures, or mathematical variables) and set them up with their initial values. (These initial values can be universally known information, previous experiences of the subject, or completely random values.) Then you need to order the information to a bit vector, as shown in Figure 20.4.

Figure 20.4. Bit vectors (or binary encoding) of information—the virtual DNA.

Although some researchers say that an implementation of a genetic algorithm must be done with bit vectors, others say that the bit vectors can be replaced by a function or equation that will analyze each gene of the progenitors and generate the best one out of the two. To be consistent with the DNA discussion earlier, I will use bit vectors (see Figure 20.4).

You now have to calculate the fitness of each subject. The fitness value indicates whether you have a good subject (for a creature, this could be whether the creature was strong, smart, or fast, for example) or a bad subject. Calculating the fitness is completely dependent on the application, so you need to find some equation that will work for what you want to do.

After you calculate the fitness, get the two subjects with the highest fitness and mate them. You can do this by randomly selecting which gene comes from which progenitor or by intelligently selecting the best genes of each to form an even more perfect child. If you want to bring mutation to the game, you can switch a bit here and there after you get the final offspring. That's it—you have your artificial offspring ready to use. This entire process is shown in Figure 20.5.

Figure 20.5. Mating and mutation of an offspring.

A good use of this technology in games is to simulate artificial environments. Instead of keeping the same elements of the environment over and over, you could make elements (such as small programs) evolve to stronger, smarter, and faster elements (or objects) that can interact with the environment and you.

Neural networks attempt to solve problems by imitating the workings of a brain. Researchers started trying to mimic animal learning by using a collection of idealized neurons and applying stimuli to them to change their behavior. Neural networks have evolved much in the past few years, mostly due to the discovery of various new learning algorithms, which made it possible to implement the idea of neural networks with success. Unfortunately, there still aren't major discoveries in this field that make it possible to simulate the human brain efficiently.

The human brain is made of around 50 billion neurons (give or take a few billion). Each neuron can compute or process information and send this information to other neurons. Trying to simulate 50 billion neurons in a computer would be disastrous. Each neuron takes various calculations to be simulated, which would lead to around 200 billion calculations. You can forget about modeling the brain fully, but you can use a limited set of neurons (the human brain only uses around 10 percent of its capacity for conscious thought) to mimic basic actions of humans.

In 1962, Rosenblatt created something called a perceptron, one of the earliest neural network models. A perceptron is an attempt to simulate a neuron by using a series of inputs, weighted by some factor, which will output a value of 1 if the sum of all the weighted inputs is greater than a threshold, or 0 if it isn't. Figure 20.6 shows the idea of a perceptron and its resemblance to a neuron.

Figure 20.6. A perceptron and a neuron.

While a perceptron is just a simple way to model a neuron, many other ideas evolved from this, such as using the same values for various inputs, adding a bias or memory term, and mixing various perceptrons using the output of one as input for others. All of this together formed the current neural networks used in research today.

There are several ways to apply neural networks to games, but probably the most predominant is by using neural networks to simulate memory and learning. This field of artificial intelligence is probably one of its most interesting parts, but unfortunately, the topic is too vast to give a proper explanation of it here. Fortunately, neural networks are becoming more and more popular these days, and numerous publications are available about the subject.

The first, and probably simplest, deterministic algorithm is random motion. Although random motion can't really be considered intelligence (because it's random), there are a few things you can make to simulate some simple intelligence.

As an example, suppose you are driving on a road, you reach a fork, and you really don't know your way home. You would usually take a random direction (unless you are superstitious and always take the right road). This isn't very intelligent, but you can simulate it in your games like so:

NewDirection = rand() % 2;

This will give a random value that is either 0 or 1, which would be exactly the same thing as if you were driving. You can use this kind of algorithm in your games, but it isn't very much fun. However, there are things to improve here. Another example? Okay. Suppose you are watching some guard patrolling an area. Two things might happen: The guard could move in a logical way, perhaps a circle or straight line, but most of the time he will move randomly. He will move from point A to B, then to C, then go to B, then C again, then D, then back to A, and repeat this in a totally different form. Take a look at Figure 20.7 to see this idea in action.

Figure 20.7. A very bad guard.

His movement can be described in code something like this:

Vector2D kGuardVelocity;
Vector2D kGuardPosition;
int kGuardCycles;

/* Initialize random velocity and cycles */
kGuardVelocity[0] = rand () % 10 - 5;
kGuardVelocity[1] = rand () % 10 - 5;
kGuardCycles = rand () % 20;
while (GameIsRunning)
{
 // If we still have some cycles with the current movement
 while (kGuardCycles- > 0)
 {
  A
  D
  C
  B
  kGuardPosition += kGuardVelocity;
 }
 // Change velocity and cycles
 kGuardVelocity [0] = rand () % 10 - 5;
 kGuardVelocity [1] = rand () % 10 - 5;
 kGuardCycles = rand () % 20;
}

And you have your guard. You might think this isn't very intelligent, but if you were only playing the game, you would simply see that the guard was patrolling the place, and you would think that he was being intelligent.

When you are trying to catch someone, there are a few things you must do. First, move faster than him, or else you will never catch him, and move in the direction he is from you. There is no logic in running south if he is north of you.

To solve this problem and add a little more intelligence to your games, you can use a tracking algorithm. Suppose the guard spots an intruder. He would probably start running toward him. If you wanted to do this in your game, you would use the following code:

Vector2D kGuardVelocity;
Vector2D kGuardPosition;
Vector2D kIntruderPosition;
int iGuardSpeed;
// Intruder was spotted, run to him
Vector2D kDistance;
kDistance = kIntruderPosition - kGuardPosition;
kGuardVelocity = kDistance.Normalize();
kGuardVelocity *= iGuardSpeed;
kGuardPosition += kGuardVelocity;

This code gets the direction from the intruder to the guard (the normalized distance) and moves the guard in that direction by a speed factor. Of course, there are several improvements you could make to this algorithm, such as taking into account the intruder's velocity and maybe doing some reasoning about the best route to take.

The last thing to learn with regard to tracking algorithms is about anti-tracking algorithms. An anti-tracking algorithm uses the same concepts as the tracking algorithm, but instead of moving toward the target, it runs away from the target. In the previous guard example, if you wanted the intruder to run away from the guard, you could do something like this:

mrVector2D kGuardVelocity;
mrVector2D kGuardPosition;
mrVector2D kIntruderPosition;
mrUInt32 iGuardSpeed;
// Guard has spotted the intruder, intruder run away from him
mrVector2D kDistance;
kDistance = kGuardPosition - kIntruderPosition;
kGuardVelocity = -kDistance.Normalize();
kGuardVelocity *= iGuardSpeed;
kGuardPosition += kGuardVelocity;

As you can see, the only thing you need to do is negate the distance to the target (the distance from the guard to the intruder). You could also use the distance from the intruder to the guard and not negate it, because it would produce the same final direction.

A pattern, as the name indicates, is a collection of actions. When those actions are performed in a determined sequence, a pattern (repetition) can be found. Take a look at my rice-cooking pattern, for example. There are several steps I take when I'm cooking rice:

And presto, I have rice ready to be eaten. (You don't mind if I eat while I write, do you?) Whenever I want to cook rice, I follow these steps or this pattern. In games, a pattern can be as simple as making an object move in a circle or as complicated as executing orders, such as attacking, defending, harvesting food, and so on. How is it possible to implement a pattern in a game? First you need to decide how a pattern is defined. For your small implementation, you can use a simple combination of two values—the action description and the action operator. The action description defines what the action does, and the action operator defines how it does it. The action operator can express the time to execute the action, how to execute it, or the target for the action, depending on what the action is.

Of course, your game might need a few more arguments to an action than only these two; you can simply add the necessary parameters. Take another look at the guard example. Remember that there were two things the guard might be doing if he was patrolling the area—moving randomly (as you saw before) or in a logical way. For this example, assume the guard is moving in a logical way—that he is performing a square-styled movement, as shown in Figure 20.8.

Figure 20.8. A good guard patrolling the area.

As you can see, the guard moves around the area in a square-like pattern, which is more realistic than moving randomly. Now, doing this in code isn't difficult, but you first need to define how an action is represented. For simple systems like yours, you can define an action with a description and an operator. The description field describes the action (well, duh!), but the operator can have various meanings. It can be the time the action should be performed, the number of shots that should be fired, or anything else that relates to the action. For the guard example, the operator would be the number of feet to move. Although this system works for many actions, you might want to introduce more data to the pattern. Doing so is easy; you simply need to include more operators in the action definition. A simple example could be

class Action
{
public:
string Description;
string Operator;
};

To make your guard pattern, you could do something like this:

Action GuardPattern [4];
GuardPattern[0].Description = “MoveUp";
GuardPattern[0].Operator = “10";
GuardPattern[1].Description = “MoveRight";
GuardPattern[1].Operator = “10";
GuardPattern[2].Description = “MoveDown";
GuardPattern[2].Operator = “10";
GuardPattern[3].Description = “MoveLeft";
GuardPattern[3].Operator = “10";

And your guard pattern would be defined. The last thing you need to do is the pattern processor. This isn't hard; you simply need to check the actual pattern description and, depending on the pattern description, do the action like so:

mrUInt32 iNumberOfActions = 4;
mrUInt32 iCurrentAction;
for (iCurrentAction = 0; iCurrentAction < iNumberOfActions;
iCurrentAction++)
{
   if (GuardPattern [iCurrentAction].Description == "MoveUp";
   {
    kGuardPosition [1] += GuardPattern [iCurrentAction].Operator;
   }
   if (GuardPattern [iCurrentAction].Description == "MoveRight";
   {
    kGuardPosition [0] += GuardPattern [iCurrentAction].Operator;
   }
   if (GuardPattern [iCurrentAction].Description == "MoveDown";
   {
    kGuardPosition [1] -= GuardPattern [iCurrentAction].Operator;
   }
   if (GuardPattern [iCurrentAction].Description == "MoveUp";
   {
    kGuardPosition [0] -= GuardPattern [iCurrentAction].Operator;
   }
}

This would execute the pattern to make the guard move in a square. Of course, you might want to change this to only execute one action per frame or execute only part of the action per frame, but that's another story.

Fuzzy logic uses some mathematical sets theory, called fuzzy set theory, to work. Fuzzy logic is based on the membership property of things. For example, while all drinks are included in the liquids group, they aren't the only things in the group; some detergents are liquids too, and you don't want to drink them, do you? The same way that drinks are a subgroup—or more accurately, a subset—of the liquids group, some drinks can also be subsets of other groups, such as wine and soft drinks. In the wine group, there are red and white varieties. In the soft drink group, there are carbonated and non-carbonated varieties.

All this talk about alcoholic and non-alcoholic drinks was for demonstration purposes only, so don't go out and drink alcohol just to see whether I'm right. Alcohol damages your brain and your capacity to code, so stay away from it (and drugs, too).

Okay, I'll stop being so paternal and get back to fuzzy logic. Grab a glass and fill it with some water (as much as you want). The glass can have various states—it can be empty, half full, or full (or anywhere in between). How do you know which state the glass is in? Take a look at Figure 20.9.

Figure 20.9. Group membership for a glass of water.

As you can see, when the glass has 0 percent water, it is totally empty; when it has 50 percent water, it is half full (or half empty, if you prefer). When it has 100 percent of its size in water, then it is full. What if you only poured 30 percent of the water? Or 10 percent? Or 99 percent? As you can see from the graph, the glass will have a membership value for each group. If you want to know the membership values of whatever percentage of water you have, you will have to see where the input (the percentage) meets the membership's graphs to get the degree of membership of each, as shown in Figure 20.10.

Figure 20.10. Group membership for a glass of water for various values.

Membership graphs can be as simple as the one in Figure 20.10, or they can be trapezoids, exponentials, or other equation-derived functions. For the rest of this section, you will only use normal triangle shapes to define memberships. As in Figure 20.10, you can see that the same percentage of water can be part of two or more groups, where the greater membership value will determine the value's final membership.

You can also see that the final group memberships will range from zero to one. This is one of the requirements for a consistent system. To calculate the membership value on a triangle membership function, assuming that the value is inside the membership value (if it isn't, the membership is just zero), you can use the following code:

float fCenterOfTriangle = (fMaximumRange - fMinimumRange) / 2;
/* Value is in the center of the range */
if (fValue == fCenterTriangle)
{
 fDegreeOfMembership = 1.0;
}
/* Value is in the first half of the range */
if (fValue < fCenterTriangle)
{
 fDegreeOfMembership = (fValue - fMinimumRange) /
   (fCenterTriangle - fMinimumRange);
}
/* Value is in the second half of the range */
if (fValue > fCenterTriangle)
{
 fDegreeOfMembership = ((fMaximumRange - fCenterTriangle) - (fValue -
  fCenterTriangle)) / (fMaximumRange - fCenterTriangle);
}

And you have the degree of membership. If you paid close attention, what you did was use the appropriate line slope to check for the vertical intersection of fValue with the triangle.

The last topic about fuzzy logic I want to cover is fuzzy matrices. This is what really makes you add intelligence to your games. First, I need to pick a game example to demonstrate this concept. Anyone like soccer?

You will be defining three states of the game.

Although there are many other states, you will only be focusing on these three. For each of these states, there is a problem state for the player. You will be considering the following:

Using these three states, as well as the previous three, you can define a matrix that will let you know which action the player should take when the two states overlap. Figure 20.11 shows the action matrix.

Figure 20.11. The action matrix for a soccer player.

Using this matrix would make the player react like a normal player would. If he is clear and doesn't have the ball, he will try to get in a favorable position for a goal. If he has the ball at a shooting position, he will try to score. You get the idea.

But how do you calculate which state is active? It's easy—you use the group membership of each state for both inputs, and multiply the input row by the column row to get the final result for each cell. (It's not matrix multiplication; you simply multiply each row position by the column position to get the row column value.) This will give you the best values from which to choose. For example, if one cell has a value of 0.34 and the other cell has a value of 0.50, then the best choice is probably to do what the cell with 0.50 says. Although this isn't an exact action, it is the best you can take. There are several ways to improve this matrix, such as using randomness, evaluating the matrix with another matrix (such as the personality of the player), and many more.