1. Introduction
Since the evident of Fuzzy logic, it has been applied to several applications such as feature detection, control theory, classification, and clustering. Fuzzy logic provides approximation methods for dealing for dealing with information that is approximate. Such information does not have well-defined boundaries. Humans can effectively deal with the information with imprecision and vague boundaries.
Traditionally, such approximate information is dealt with precision, which can be computationally expensive. Fuzzy logic provides mathematical tools for dealing with imprecise information in the manner similar to humans.
While defining AI for computer games it could be better if the linguistic terms are define in a fashion similar to humans. Expert knowledge can be easily transformed in to a machine understandable language [1]. For example, consider a speed of a vehicle, it can be slow, medium, or fast. Suppose if the range or universe of discourse of the vehicle is between 0 to 120 mph, then sets for the speed of vehicle can be define using sets such as:
Slow = {0, 1, 2, …, 40}
Medium = {41, 42, …, 80}
Fast = {81, 82, …, 120}
One way of graphically displaying these crisp sets is by considering membership of an element as 1 if an element belongs to a set and 0 otherwise. Figure 1 shows the representation of these crisp sets.
Figure 1. Example of classical Set
It is obvious that speed of 90 or above can be considered as fast, and speed lower than 30 is slow. According to sets in figure 1, if we consider the borders someone driving at speed of 80 will be considered as driving with medium speed, and 81 will be considered driving fast. Moreover, different experts might now even agree with this numbers. It will be even difficulty to define rules with the hard boundaries. Fuzzy sets allow different elements with varying degree of membership, and fuzzy rules can be defined using these sets for decision making. Fuzzy system allows the translation of vague terms such as distance, and speed into in to system inputs and outputs [2].
In rest of the paper, we present an overview of fuzzy system demonstrating its application to game AI.
2. Fuzzy Sets
In classical set theory, an object is an element of a set or it is not. Fuzzy sets allow every object to be an element of a set, but with varying degree of membership. Consider a fuzzy set Speed in figure 2, speed of 81 can belong to both the sets Medium and Fast, but it belongs to the set Medium with membership 0.3 and Fast with membership 0.7. Speed of 81 is considered more to be fast then it can be considered medium. While speed of 5 will have definite membership value 1 in set Slow, and membership value 0 in Medium and Fast, meaning speed of 5 is definitely slow, and cannot be considered either Medium or Fast.
Figure 2. Example of Fuzzy Set
Let U be a classical universal set, called universe of discourse. A fuzzy set A is described by a membership function μA(x) mapping every element of U to the unit interval [0 1].
A = {(x, μA(x)) | x ∈ U, μA(x) ∈ [0, 1]}
Core of the fuzzy sets are the membership function. Membership functions can be defined in multiple manners. Various types of membership functions are triangular, trapezoid, and s-curve.
Again consider sets representing seed of a vehicle. Figure 2 graphically represents fuzzy sets Slow, Medium, and Fast represented by left shoulder, trapezoid, and right shoulder membership functions respectively.
3. Fuzzy Linguistic Variable
A fuzzy linguistic variable is a collection of fuzzy set which represents a similar concept. For example, fuzzy sets Slow, Medium, and Fast represents linguistic variable Speed.
Speed = {Slow, Medium, Fast}
This is more intuitive representation for a human. The information, such as speed of vehicle is slow, is efficiently encoded in digital form. Consider a fuzzy linguistic variable Distance with universe range from 0 to 500 which signifies distance from a target. Distance encapsulates fuzzy sets Far, Medium, Close. Figure 4 shows the membership function of fuzzy sets in the linguistic variable Distance.
Figure 4. Fuzzy Linguistic Variable Distance
It would be easy for a knowledge engineer to specify distance with fuzzy sets, such as Distance is Close, compared to specifying distance in units, such as Distance is 10 KM. It would be even easier to specify rules using such data structures.
4. Fuzzy Rules
Fuzzy rules are set of if-then rules with antecedents and consequents as fuzzy sets in fuzzy linguistic variable.
IF antecedent THEN consequent
Consider a scene where we need to control the speed of a boat trying to reach the target location. Above mentioned linguistic variables, Speed and Distance, can be used to define rules which will control the speed of a boat. Such rules can be defined as following:
Rule 1: IF Distance is Near THEN Speed Slow
Rule 2: IF Distance is Medium THEN Speed Medium
Rule 3: IF Distance is Far THEN Speed Fast
In the same manner rules with multiple antecedents and multiple consequent can be defined. We can determine the speed that needs to be set given the distance of the boat from the target.
5. Fuzzy Rule Inference
Fuzzy rule inference is a three step process:
- Fuzzification: determining the membership value of the crisp input in the different fuzzy sets of linguistic variable
- Fuzzy rules: apply fuzzy rules to the fuzzified input in order to determine the fuzzy output.
- Defuzzification: usually fuzzy output is converted back to a crisp value, especially for game, to be used in the application
Consider the example of controlling the speed of a boat. Suppose that current distance of boat is about 25 miles from target. Figure 4 shows the fuzzification of the input (25). Values 25 belong to Near and Medium fuzzy set with membership 0.8 and 0.2 respectively. Although not shown in the figure 5, values 25 also belong to fuzzy set Far, but with membership value 0.
Next step is to apply all the fuzzy rules. For each rule determine the confident in the consequent of the rule based on antecedent of the rules. In our example there is only one antecedent, therefore the confidence if the membership value of the input. For rule 1 with antecedent Near confidence for the input will 0.8 for Speed Slow. Similarly, for rule 2 confidences in Medium is 0.2, and 0.0 for Far in rule 3.
Figure 4. Fuzzy rule inference
Figure 5. Defuzzification
Based on the level of confidence each consequent is clipped and then combined in to a single fuzzy set as shown in figure 5. Finally, the output fuzzy set is defuzzified for getting the crisp value. A standard method for defuzzification is to calculate the center of gravity of the output fuzzy set. As shown in figure 5, this would yield the speed of a boat which is approximately 20 mph.
Even if there is more than one antecedent we still follow the same process, except after fuzzification in order to determine the level of confidence we take into consideration the operator between the antecedents. If there is an AND operator between the antecedents then minimum of the membership value is taken as level of confidence, or if there it is an OR operator then maximum of all the membership value if taken as level of confidence.
Other examples of the fuzzy logic usage in games can be found in [1] and [3].
7. Conclusion
Fuzzy Logic provides a flexible and powerful tool for handling and processing approximate information. Fuzzy system model reduces the time and effort of game programmers require for configuring crisp values. Also, the number of rules needed in a game for decision making can be significantly reduced using a fuzzy system.
Future work should include incorporating fuzzy rules with an expert system. Expert systems are widely used in industries for simplifying complex decision making processes. A fuzzy expert system can give more power of expression to experts and can handle different form of inputs from different experts.
8. References
[1] M. Buckland. Programming game AI by example, Wordware Publishing, Inc., 2005, pp. 415-456
[2] Adnan Shaout , Brady King , Luke Reisner . Real-Time Game Design of Pac-Man Using Fuzzy Logic. The International Arab Journal of Information Technology (IAJIT), 2005.
[3] Ian Millington, and John Funge. Artificial Intelligence for Games, Second Edition. Elsevier Inc . pp. 371-395 2009.
Note: Extracted from CS 487 Fall 2011 class presentation report.
