< Day Day Up > |
11.1 Rule-Based System BasicsRule-based systems have two main components: the working memory and the rules memory. The working memory stores known facts and assertions made by the rules. The rules memory, or rules, for short, contains if-then style rules that operate over the facts stored in working memory. As rules are triggered, or fired in rule-based system lingo, they can trigger some action or state change, such as in a finite state machine, or they can modify the contents of the working memory by adding new information called assertions. Example 11-1 shows how the working memory for a real-time, strategy-game technology tree might look. Example 11-1. Example working memory
For this example, we made each element in working memory a TMemoryValue type that can take on any one of four values: Yes, No, Maybe, or Unknown. The idea here is to keep track of the computer opponent's current perception of the state of technology of the player opponent. A value of Yes implies that the player has the particular technology, whereas a value of No implies that she does not. If the player meets all the criteria to gain or posses a certain technology, but the state has yet to be confirmed by a scout, the value of Maybe is used. If the computer knows nothing about a particular technology capability for the player, Unknown is used. The computer can gather facts on the player's current state of technology by sending out scouts and making observations. For example, if the computer sends out a scout and sees that the player has built a temple, Temple would be set to Yes. Using a set of if-then style rules, the player can infer the state of technology for the player, before a scout confirms it, given some known facts. For example, referring to Figure 11-1, if the player has woodcutters and stonemasons, she is capable of having a temple. In this case, Temple is set to Maybe. A rule for this scenario might look like that shown in Example 11-2. Example 11-2. Example temple rule
Inference can work the other way as well. For example, if the player has been observed to have a priest, the computer can infer that the player also must have a temple, and therefore also must have a barracks, a woodcutter, and a stonemason. A rule for this scenario might look like that shown in Example 11-3. Example 11-3. Example priest rule
You can have many more rules for this type of technology tree. Example 11-4 shows a handful of other rules you can write. Example 11-4. More example rules
As we stated already, these aren't the only rules you can write for this example. You can develop several more, covering all possible technologies shown in Figure 11-1. The idea here is that you can write such rules and execute them continuously during the game�that is, each iteration through the game loop�to maintain an up-to-date picture of the computer opponent's view of the player's technology capabilities. In this example, the computer can use this knowledge in other AI subsystems to decide how to deploy its attack forces and defenses. This example should give you a basic idea of how a rule-based system works. It really comes down to a set of if-then style rules and a set of facts and assertions. Note, however, that very often developers do not build rule-based systems using actual if-statements such as those shown in this section. We discuss alternatives a little later, but basically hardcoding the if-statements makes a certain type of inference hard to achieve. Further, developers often use scripting languages or shells so that they can create and modify rules without having to change source code and recompile. 11.2.1 Inference in Rule-Based SystemsIn the previous section we took a look at the main components of rule-based systems and showed how you can use such a system to make inferences in a real-time strategy game. In this section we're going to take a slightly more formal look at making inferences using rule-based systems. Our aim here is to distinguish between the two basic algorithms for making inferences and to introduce some standard rule-based system lingo in case you decide to dig further in the technical literature for more information on rule-based systems. (We give some references at the end of this chapter.) 11.2.1 Forward ChainingThe most common inference algorithm for rule-based systems is called forward chaining. This algorithm consists of three basic phases. The first phase involves matching rules to facts stored in working memory. You do this by checking the if-parts of each rule to see if they match the given set of facts or assertions in working memory. For example, in our technology tree example, if the working memory indicates that Peasants = Yes and Woodcutter = Unknown, we know the first rule shown in Example 11-4 matches and potentially can be fired. When a rule is fired, its then-part is executed. Potentially, more than one rule can match a given set of facts in working memory. In this case, we have to figure out which rule to fire. This leads to the so-called conflict resolution phase. In the conflict resolution phase we have to examine all the matching rules and figure out which one we want to fire. We can make this decision in many ways. A common approach is to fire the first matching rule. Sometimes you can pick one at random. In other cases, the rules are weighted and the one with the highest weight is selected. We're going to take this latter approach in our fighting example. After the conflict resolution phase is executed and a rule is selected, we fire the rule. Firing a rule simply means executing its then-part. The rule might assert some new facts in working memory, such as in the rules in Example 11-4. It might trigger some event or call some other function that does some sort of processing. After these three phases are executed, the whole process is repeated until no more rules can be fired. When this happens the working memory should contain everything the rule-based system can infer given the starting facts. Don't worry if this is a bit nebulous at this point. Things will become clearer when we get to the fighting example. 11.2.2 Backward ChainingBackward chaining is sort of the opposite of forward chaining. We still have working memory and rules memory, but instead of trying to match if-parts of rules to working memory, we try to match the then-parts. In other words, in backward chaining we start with some outcome, or goal, and we try to figure out which rules must be fired to arrive at that outcome or goal. Consider the technology tree example one more time. Let's say the outcome is that the player has cavalry units�that is, Cavalry = Yes. To figure out how the player arrived at acquiring cavalry we can backward-chain to see which rules must be fired to set Cavalry to Yes. Looking at Figure 11-1, we see that to have cavalry, the player must have had a blacksmith. A rule for this situation might look like the code shown in Example 11-5. Example 11-5. Cavalry rule
Continuing, if the player has a blacksmith, she must have had barracks. If the player had barracks, she must have had a woodcutter, and so on. We can continue this sort of logic backward up the technology tree from the goal, Cavalry = Yes, through all the rules and facts that are required to arrive at that goal. This is backward chaining. In practice, backward chaining is recursive and more difficult to implement than forward chaining. Further, hardcoding if-statements such as those in our illustrative examples makes it difficult to match the then-parts of rules to facts stored in working memory during backward chaining. In the fighting example, we'll look at how to implement rule-based systems without actually hardcoding if-then style rules. |
< Day Day Up > |
No comments:
Post a Comment