Sign in to follow this  
  • entries
    74
  • comments
    187
  • views
    34011

Fuzzy Logic and Gaming

Sign in to follow this  
NickGeorgia

173 views

I was going to put this off for later, but I heard someone in the forums wanted to know, sooo.. Fuzzy logic is an extension to the familiar crisp logic (True or False). In essence, it is about possibility distributions rather than probability distributions. Here I explain a way to "possibly" use fuzzy logic in a game AI. We shall use a simple inference engine called the Takagi-Sugeno (If I'm spelling it right), and you can use others such as Mandani if you so care to look it up.

This is going to be rather terse. A fuzzy logic expert system can be thought of as 4 main parts: Fuzzification, Inference Engine, the Rulebase, and Defuzzification.



As you can see, fuzzy logic represents a mapping from input variables such as velocity, position, acceleration, etc. to some output variables. Fuzzy logic is useful in that it represents uncertainty, but we'll try to incorporate it in a game.

We shall use the Pong game (two paddles on each side, one ball) as the game of reference. Let's say the paddle on the left side of the screen is controlled by the computer using Fuzzy Logic.

=== Sorry about that, I'm sitting in my room with no air conditioning, and it's 95 degrees in here so I tried to get it fixed, but couldn't -- let's continue ===

The first step is to choose which input and output variables we wish to control. Let say for our case the inputs are the velocity of the ball, direction of movement of the ball, and position of the ball, and the computer's paddle location when the ball is headed the computer's direction. Let's make the output the desired direction (up or down) and velocity of the paddle.



The second step is to dissect the universe of discourse into different fuzzy sets. What is the universe of discourse, well it's all the values you think you will need for the inputs and the outputs. Hold on, this is where it gets "fuzzy." For example,



Here we are performing the fuzzification of the inputs. We have created what are known as membership functions which tells us the possibility each value (velocity, position, etc.) belongs to each fuzzy set (fast, slow, etc.) You can use any shape you wish for membership functions just as long as the value never exceeds 1 (maximum possibility), never goes below 0 (minimum possibility), and is single valued at each point. You see the overlap of the different fuzzy sets, that is where the uncertainty comes into play. At those values, we are "fuzzy" on the particular set a value belongs too.

For example,

Consider the inputs:
Position X ball is P/2
Position Y ball is P/3
Velocity X ball is 15 pixels per iteration
Velocity Y ball is -10 pixels per iteration
Position Y Paddle is P/2

The to fuzzify, we use the figure above with the membership functions to calculate the Possibilities:
Position X ball Near C-Paddle (PX1) = 0
Position X ball In the middle (PX2) = 1
Position X ball High Screen (PX3) = 0
Position Y ball Low Screen (PY1) = 0.5
Position Y ball Mid Screen (PY2) = 0.5
Position Y ball High Screen (PY3) = 0
Velocity X ball Fast (VX1) = 1
Velocity X ball Slow (VX2) = 0
Velocity Y ball Down (VY1) = 1
Velocity Y ball Up (VY2) = 0
Position Computer Paddle Low Screen (CY1) = 0
Position Computer Paddle Mid Screen (CY2) = 1
Position COmputer Paddle High Screen (CY3) = 0

There we go, we have fuzzified the inputs. As you can see, the only uncertainty we have is whether the Y Position of the ball is Low or Mid Screen. In this case what do you expect our paddle to do? Since the ball is about middle-X, Low/Mid - Y and the ball is coming fast toward us and the ball is moving downward, then we should move our computer paddle down fast.

Second Step: Rulebase. Now, as you can tell, comes the rule base. I'm not going to make a complete rulebase, but just for demonstration make some rules up (some of these rules come from expert experience in practice, and sometimes we use some learning rules--we are just going to pretend we are experts at Pong and know all the rules).

If the Ball X Position is Near C-Paddle and Ball Y Position is Mid Screen and Ball Y is Up and Computer Paddle is Low Screen then Computer Paddle Velocity = 20 pixels per iteration upward.

If the Ball X Position is Near C-Paddle and Ball Y Position is Mid Screen and Ball Y is Up and Computer Paddle is Mid Screen then Computer Paddle Velocity = 5 pixels per iteration upward.

etc. etc. etc.

Now you may say there will be a lot of rules, not in all applications. You can fiddle with the number of membership functions that divide a universe of discourse and some rules will not make sense or one rule may cover a larger condition space.

Step 3: Inference Engine
Now we want to use the inference engine to calculate the degree of fullfillment for each rule. To do this, we multiply each of the fuzzy values together for each rule (this is the and operation--there are other types of and operations, if there is an or statement you take the max usually). For example,

If the Ball X Position is Near C-Paddle and Ball Y Position is Mid Screen and Ball Y is Up and Computer Paddle is Low Screen then Computer Paddle Velocity = 20 pixels per iteration upward.

and using our calculated values...
Position X ball Near C-Paddle (PX1) = 0
Position X ball In the middle (PX2) = 1
Position X ball High Screen (PX3) = 0
Position Y ball Low Screen (PY1) = 0.5
Position Y ball Mid Screen (PY2) = 0.5
Position Y ball High Screen (PY3) = 0
Velocity X ball Fast (VX1) = 1
Velocity X ball Slow (VX2) = 0
Velocity Y ball Down (VY1) = 1
Velocity Y ball Up (VY2) = 0
Position Computer Paddle Low Screen (CY1) = 0
Position Computer Paddle Mid Screen (CY2) = 1
Position COmputer Paddle High Screen (CY3) = 0

We get DOF = 0*0.5*0*0*0 = 0, so that rule ain't gonna fire.

Anyway, we do this for all rules and we get a Degree of Fullfillment for each rule.

Step 4: Defuzzification
In this step we convert our information to an output, in this case the velocity of the computer paddle. To do this, we need the "then" part of each rule and each of the degree of fulliment measures we just calculated for each rule. Let's just make some up for example sake. Say we had 4 rules with the associated degree of fullfiments.

Rule 1: If blah and blah and blah ... then velocity = 10 (DOF=0.1)
Rule 2: If blah and blah and blah blah ... then velocity = 20 (DOF=0.2)
Rule 3: If blah and blah ... then velocity = 0 (DOF=0.6)
Rule 4: If blah then velocity = -10 (DOF = 0.0)

If we use the center of mass defuzzification process (there are other defuzzification techniques), then we can defuzzificate and get the velocity:

velocity
= [10*0.1 + 20*0.2 + 0*0.6 + (-10)*0.0]/[0.1 + 0.2 + 0.6] = (5/0.9) pixels per second.

There you go, that's the majority of a process using a fuzzy expert system. The steps are:

1. Create the membership functions and rulebase offline somewhere in the darkest corners of your mind.
2. Fuzzify the current inputs (measurements)
3. Use the rulebase you made and the inference engine to calculate the DOF for each rule.
4. Defuzzify using center of mass.
5. Goto step 2.

Now, there is a lot more too it and a lot of different types of fuzzy systems out there. Some can learn the membership functions from data you collected during some game or while actually playing (fuzzy c-means clustering for example). Some can learn the rules as well. If you have both then you got a smart system alright... although you might have 10000 membership functions and 10000000 rules in the end if you don't watch it. Sorry, I couldn't find any trivial algorithms to update the rulebase automatically. We might go back to this once a neural network tutorial is up. Anyway, this is just to get you started on an idea. Just to make the computer a little dumb, you can fiddle with the input measurements by adding a little uncertainty such as adding a random number to the velocity (adding some noise). Well I'm burning up... I may come back and actually read this and find out lots of mistakes, but I hope you get the idea.

On a side note, I heard that a cement company made a fuzzy rulebase to control a cement process. They were selling the rulebase for a lot of money. Fuzzy logic is used in a lot of systems where a model is hard to come by... such as fuzzy washing machines, Joint strike fighters, determining the health of machines or humans, selecting a jury, etc.... whereever there is uncertainty, there is a "possibility" for fuzzy logic.

The Pong example is just an example and you shouldn't try and implement my rules or membership functions, but in all certainty they wouldn't work. Use your own...... :)

Also here is a link to another example if you found this confusing... but they are using Mandani
Sign in to follow this  


8 Comments


Recommended Comments

Have you considered moving these into a series of mini-articles instead of tucking them away as journal entries where they won't be seen/enjoyed nearly as much as they could. :)

Share this comment


Link to comment
Yeah, I have, but I would have to clean up my English and figures and examples for the mods if they were interested. Thanks, though, it makes me feel good people might actually use this.

Share this comment


Link to comment
I just read through your journal for the first time. I have to say that I thoroughly enjoyed reading your entries, and I think that a lot of people would find this information useful.

Share this comment


Link to comment
Shame on you....for hiding your entry in your journal.
Listen to HopeDagger !!

And your writing-style is spot on...down to earth....excellent.


"Surf's up dude!" :P

Share this comment


Link to comment
LOL, thanks Michael. I could probably reach out to more youngsters if I through (or threw) in a little "that's hot!" every now and then.

Share this comment


Link to comment

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now