First introduce the RBS (Rule Based System). It is easy to see from the literal, which refers to a rule-based system, and the neuron network is different, which is another branch of artificial intelligence. The method used to solve the problem is based on the following form:
The current state is input, the orchid region is the process of manual intelligence processing, and the output is an event, and the event itself will affect the state change. This article tells the algorithm theory and specific C / C implementation of matching and results filtration.
To match, you should first determine the matching format, then how to determine, let's take a look at the following logic statement:
If A and B, or C D, then how such a statement is embodied in the computer. Yes:
IF (a and b) or c then d, see such a structure, reminds us of an Expression Tree that describes the arithmetic expression. Well, then let's try to save such a logic with a tree structure:
Among them, orange represents the matching element, and the purple red represents the logical relationship between the two elements, and finally the result of the logic of this logic. It seems that there is no problem, and it is a very rule of two-fork. When the logic is getting more and more, there is no relationship between several people without any relationship. So actually, in fact, many logical elements have not changed, that is, the three relationships of ABC, but the logical relationships have changed, or some cases have no logical relationships, but the result D is different. So what kind of way we use this forest in this case?
Here will be described here, 90% of large commercial RBS systems are all RETE algorithm-based models. Then let's see how the RETE algorithm is defined.
The original intention of the RETE algorithm was to organize the results into a tree after the first time, and then search this tree before searching the forest, see if I can find the information of interest, the purpose is to start To a buffer role. But, in fact, we can build the entire forest into a tree in memory when we start, and all the matches can be searched from compiled trees.
Let's take a picture of the principle of the RETE algorithm:
The picture on the left is a logic mentioned earlier:
IF (a and b) OR C THEN D
The figure on the right is another logical that slightly modified:
IF (a and b) and e kil
So how do we compile these two trees to form a tree:
At this time, if the input is a and b, then the result of the exact match is D. The result of the fuzzy match is all the associated results of all and the AND logic operator with black thick border, including D and F.
Next, look at how the specific structure is implemented in actual programming languages. The reason why I use a distinct color to separate the matching element, matching operation symbols, and matching results, is clearly distinguished between the three relationships. It is not difficult to see from the figure that some of the above three:
1. Matching elements are not connected nodes
2. A matching element may be connected to multiple matching operators or operations
3. One operator is more than two nodes, and the access node may be a matching element or an operator.
4. One operator can be connected to multiple arithmetic nodes or calculation results
5. An operation result can have multiple access from the operational operator or an arithmetic element.
6. The result of the calculation does not have a node
And because the access node of the operator is limited, information is required to hold the access node on the operator. Then when actual search matches, input is a logical information, then find the first logical element in the logic in the RETE tree, then search for whether there is a matching operator in the receiving node of the element, if not, Continue to search all results related to this matching element, calculated as blur matches, and set the fuzzy index to 1 (after the result filtering phase discussed to the related use) So after a related search is performed, it will generally get Excessive results, but the final decision can only be selected from the neutral, so how to filter the results. Although in theory, different filtration mechanisms are set according to different situations, and some of the comparison of General Filter algorithms are first told.
1. The priority setting method, this is an effect on the setting of the started fuzzy index, but it can only filter out blur matches, and other filtrations need to be filtered for exact matching.
2. Recent time access method, search for the results of the last visit, this method is for the results of the original RETE algorithm search, not suitable for what we said in the process of generating a good tree.
3. Minimum matching method, the output result of an input is the least, the more specified the specific, and continue to search in those results.
4. Initially matching the method, when searching the tree, after the precise match, follow the precedence search, return the result of the first search.
5. The grouping method is divided into more than one group according to different types, so that it can be compiled into a plurality of trees to form a forest, and then search only in a fixed group when searching.
6. Do not repeat, exclude recently accessed results, then continue searching in the remaining results.
7. Historical data sorting method, sort all historical access information, return the number of access to the number of access.
8. Random method, I should know the name. =)
Then arrange some of the judgment priority elements that have been added to the design rules database, which can consist of the results filtering mechanisms that meet their requirements.
Let's take a look at the application of RBS in some FPS games: (taken from some FPS games)
Action Selection
IF Enemy and Health_low Then Retreat
IF Enemy and not distance_close the pursue
IF Enemy Then Dodge
If True Then Not Retreat and not pursue and not dodge
Movement
Movement
IF Collision and Enemy Then Move_Avoid
If Retreat Then Move_FLEE
IF pursue kilove_seek
IF dodge kilove_side
If True Ten Move_forward
WEAPON SELECTION
WEAPON SELECTION
IF Enemy and distance_far THEN USE_ROCKETLAUNCHER AND USE_RAILGUN
IF Enemy and not distance_far then use_chaingun and use_hyperblaster
View Control
View Control
IF Enemy Then Look_nemy and Fire
If OBSTACLE_FRONT AND OBSTACLE_LEFT AND OBSTACLE_RIGHT THEN LOOK_BEHINDIF OBSTACLE_FRONT AND OBSTACLE_LEFT THEN LOOK_RIGHT
IF OBSTACLE_FRONT AND OBSTACLE_RIGHT THEN LOOK_LEFT
IF not health_full and health_item the look_health
IF not armor_full and armor_Item Then Look_Armor
If True Then Look_around
