quote:

---

Original post by Timkin
the use of neural networks for decision making, when they''re a classification (or function approximation) algorithm... the list goes on.(

---

Just reread your posts and I have to take you up on this point. Sometimes decision making *is* a classification problem and a neural net is a useful tool for this purpose. Not least because it always takes O(n) time to make the decision.

---

Stimulate

Perhaps I''m pointlessly adding fuel to the fire here (woohoo! ), but I think that the predictive system and shot generator should be based on two different decision making systems. If your paddle movement is based on 1-directional movement ala Pong, your strategies are going to be based more on defense (incoming velocity and position of the puck) rather than on offense. The first concern is not missing. You can be getting ready for the greatest shot in the world, but if you miss the puck, it didn''t matter anyway. Here I think Timkin''s Kalman filter could be your best solution. It allows you some unpredictability, but also allows the AI player to make some decent judgements on its shots.

However, if you are trying to recreate the experience of playing against a human player, I think you need to implement the paddle movement in 2D. In real air hockey, you can use your paddle anywhere on your side of the "rink", allowing you to put all kinds of different spin on the puck and really increasing the force with which you can hit the puck. In this case, the Kalman filter will still give you realistic action for intercepting (blocking) the puck from the goal, but may not allow for more tricky shots. I think a Fuzzy Logic based system would fit in here perfectly - "Based on my Kalman filter prediction of where the puck''s going to be in 1/10 sec, my best shots are A (60%), B (35%), C (75%), or D (longshot, really tricky 10%)". I think you need the fuzzy logic system in there to allow for much more human type AI. If the player''s paddle is blocking the right side of the goal, I (the AI player) don''t necessarily want to aim for the open shot, either straight on or banking the puck. I might go for a double bank back to where the puck was originally, but may not be at the time the puck arrives due to predicting a different shot. Of course, now the paddle movement should really be circular on some shots (banking) and straight on others (directly at goal).

After re-reading, to summarize, I think that as a player in air hockey you have about 5 (maybe 6) shots that you can take and have a reasonable chance of scoring a goal. 1 (or 2 depending on the position of opponents paddle) straight on shots, 2 banks shots (1 to either side) and 2 double bank shots. Anything more is pretty hard to do with the size of the table. The computer should estimate the incoming velocity and position of the puck (Kalman filter), and then pick one out of say 5-7 possible shots depending on speed and position of the puck, position of opponent''s paddle, etc.

This is getting really complex, but if you implement your game AI anything like this, I''ll definitely play it.

"I''ve never seen that. I''ve never seen anybody drive their garbage down to the side of the street and bang the hell out of it with a stick. I''ve never seen that."

Hi Zul,

The system I''ve implemented thus far includes relatively free 2d movement of the puck.

So far as the game mechanics are concerned, you''ve just about described the conclusion I''d come to - separating shot generation from incoming path prediction, although both need to combine in order to position the mallet correctly. You want it in place to start the stroke needed to make the shot you''ve decided on.

I''m still looking for a straightforward description of Kalman filters that I can understand well enough to implement one, or something similar, sensibly.

One other idea - which muddies the waters somewhat - would be to allow the generation of a "control" stroke, to kill the speed and spin of the puck before playing an attack stroke...

For a simple game this is getting pretty complex!

I'm sure Timkin may have some better sites, but this one gave me an idea of what it was all about: here

actually, that page is a bunch of links, but this is a good overview: overview

On about the 5th page it gives a general description of the Kalman filter. Then on this page: math equations
they go into the equations of it. It's pretty heavy math if you haven't taken any higher stats courses, so maybe Timkin will be nice and give you a better link

I think the idea of a "control" stroke, is a really good one. Maybe you could have the shot generator include the control stroke as one of it's options, and if the position and velocity of the incoming puck are bad (too fast, bad angles, whatever) the control shot should have the highest fuzzy percentage. You actually should always include the control stroke as a low percentage to simulate the computer player taking a drink or using the can :D

"I've never seen that. I've never seen anybody drive their garbage down to the side of the street and bang the hell out of it with a stick. I've never seen that."

Note: I'm trying to see how many times I can edit this, I'm up to four.

[edited by - Zul on June 11, 2002 12:37:34 PM]

quote:

---

Original post by fup
1) That there is a vast and very real difference between the world of academia and the world of commerce. It is usually the case that a person working in one world cannot understand the motives of a person working in the other.

---

I''m not sure that I entirely agree with that. The games industry is motivated (at the highest levels) by money (like any other industry) and at the lower levels by the desire to produce great games (which usually satisfies the higher level desire to make money). Most people would understand that.

Most people would also understand that academic research is about discovering new and interesting things and finding new ways to apply old things. Many people forget though that academic research always strives to find a use for the things it develops (or we don''t get funding)!

quote:

---

Original post by fup
Just reread your posts and I have to take you up on this point. Sometimes decision making *is* a classification problem and a neural net is a useful tool for this purpose.

---

No, a decision problem is a problem instance in which one must weigh up several choices of actions and choose one based on a value criteria. It may be necessary to solve an associated prediction problem (predict the outcomes of the actions) in order to evaluate the (expected) value of each decision choice, but that is a separate problem and one people often confuse as a decision problem. So, you might use your neural network to evaluate the outcome of a set of input criteria (including control/decision variables), but the actual decision problem is external to this task.

I know it''s a find distinction but it''s a necessary one since there are decision methods that don''t require solving an associated function evaluation/classification/prediction problem.

Cheers,

Timkin

Okay, the basics of a Kalman filter (part 1).

Let's start with a simple case: perfect observations on a deterministic linear system.

Suppose you have a puck moving in 1 dimension. You can write a Linear Dynamical System model for the motion of the puck as

x(t+dt) = x(t) + dx/dt(t) * dtdx/dt(t+dt) = v(t) 

Since the system is linear, v(t) must be a constant over the time interval t to t+dt. If it isn't, then x(t+dt) is found by integrating the speed from t to t+dt. Let's stick with the assumption of a constant speed over the timestep for now, since it's all we need for Air Hockey.

If you were to implement a perfect prediction system using calculus you would solve the above equations in the usual manner: choose dt and using known values for x(t) and v(t), compute x(t+dt).

What if you didn't know v(t) though, but you had a former position , say x(t-dt), with which you could estimate v(t). Rather simple isn't it? Using a backwards difference estimate (just a fancy name for something you'll recognise)

       [x(t) - x(t-dt)]v(t) = ----------------              dt 

This should be fairly familiar to most people. If you were implementing a Pong AI you would probably use equations like this to figure out where the puck would cross the axis of movement of the AI paddle. In two dimensions it's no more difficult than adding a second set of equationns for the other dimension, since motion in each dimension is independent of what's happening in the other dimension.

Now, we can rewrite the Linear Dynamical System above so that it is in a linear algebra form. Here s is a vector with s₁ being the position of the ouck and s₂ being the speed of the puck. So,

|x(t+dt)|   |       | = s  (t+dt) = Fs  (t)|v(t+dt)| 

where F is the matrix

    |1  dt|F = |     |    |0   1| 

Noisy observations
------------------

Now, what would happen if the observations you were making on position were done through blurry glasses? Could you tell exactly what the position of the puck was at any given moment? You might say that, "hang on, my eyes aren't blurry, I can see where the puck is at any moment"! I would answer with this: "what are the exact coordinates of the puck on the table given that you can only glance at it"? Get the idea now? Humans don't have perfect information and indeed most measurement devices we use don't give perfect information either. They provide what we call 'noisy' observations of the environment.

So, let's consider a noisy observation on the state of the puck. If the true (unknown/ usually called 'hidden') state is s (t) then we can denote the observation as y(t). (My apologies about the choice of notation but it's standard among many papers on Kalman filters that you might read. x or s often denotes state and y normally denotes observation on state. I'm using s for state)

Let's assume that the observation is some function, H, of the state plus some noise, n. (The function represents bias... like if for some reason you always thought the puck was a bit left of where it actually was. In most instances, the bias is zero so the function is just 1).

So, y(t) = H(s (t)) + n (t)

and in our situation

H = |1  0|andn = n1 

so that H is telling us that we only have an observation on the position of the object and hence noise is only added to this observation. Thus, y is a scalar and not a vector.

So, our full linear dynamical system for the hockey puck is given by

s  (t+dt) = Fs  (t)y(t) = H(s  (t)) + n  (t)  

We can go even further if we want to (but this choice is up to you) and say that the speed of the puck also has some small fluctuations associated with it, but that the average speed of the ball is v(t) (s₂(t)). I won't worry about this for now, but's it's something I'll add on later so have a think about what it might mean for the predictability of the motion of hte puck and hence its predicted position.

For now, the only other thing I want to mention is the noise we added to the observations. It should have zero mean and it needs certain other qualities as well (which I don't really need to explain). A good - and very common - choice for this noise is white Gaussian noise. In other words, noise that has a Normal (bell shaped) distribution.

That's enough for part 1 of this explanation on Kalman filters. I'll post more tomorrow. For now though, please make sure you understand everything above and please ask any questions you like regarding my explanation. Tomorrow I'll explain the basics of linear least-squares estimation and show you how to do it using only matrix operations!

Cheers,

Timkin

[edited by - Timkin on June 14, 2002 1:58:54 AM]

quote:

---

Original post by Zul

"I''ve never seen that. I''ve never seen anybody drive their garbage down to the side of the street and bang the hell out of it with a stick. I''ve never seen that."

---

Completely off topic, of course, but this quote is from one of my very favorite movies of all time. "The ''Burbs" is right up there with "Neighbors" IMO.




Ferretman

ferretman@gameai.com
www.gameai.com
From the High, Cold, Snowy Mountains of Colorado

Hey Steve... you think we can start a PayPal account where we can take up a collection to send Ol'' Timkin to the GDC next year? I know you were lamenting his absence while we were there. Let''s do something about it! I want his ass in a roundtable!

Dave Mark
President and Lead Designer
Intrinsic Algorithm Development

"Reducing the world to mathematical equations!"

Timkin: That's your definition of a decision. Mine goes something like this:

de·ci·sion (d¹-s¹zh“…n) n. 1. The passing of judgment on an issue under consideration

There are many types of decision one can make, and many of them are categorization problems. As in. Is this ball red or black? In answering this question you are making a decision about the color category the ball is in. There is no additional process there, no prediction. No weighing up of actions. It is quite simple. Is the ball red or black?

---

Stimulate

[edited by - fup on June 12, 2002 1:58:15 AM]

This is getting off topic so perhaps we should talk about this in another thread? I''ll start one up called ''Decision Theory'' and we can go to town on the topic!

Timkin