Archived

This topic is now archived and is closed to further replies.

AJFleming

AI Ideas for Air-Hockey Simulator

Recommended Posts

AJFleming    122
Hi all, I''ve been playing around with an air-hockey simulation (dull and boring I know, but it''s a simple enough domain for a first attempt at a simulation-style-game.) I''ve got a basic front-end, the physics more or less as I want it, and the control code written and all of it plays happily together. I''m now looking at implementing some simple AI for the game. I''ve been giving it some thought and digging around on the net a bit, but I can''t seem to find a simple starting point. I found a really useful paper on machine learning for air-hockey simulations, but it seems a little heavy-duty for what I''m looking at. Basically, I''m looking for a simple heuristic which won''t result in the opponent being completely unbeatable! Anyone got any ideas or comments? cheers, Adam...

Share this post


Link to post
Share on other sites
AJFleming    122
quote:
Original post by InnocuousFox
Wouldn't it just be a modified Pong AI?



Apologies to anyone who read my response before I editted it... Just done some digging around looking at Pong AI and I can ask questions a little (!) more intelligently now

From what I've seen, all the Pong alorithms appear to be defensive - which isn't going to make for a fun air-hockey simulation. They also appear to assume one-dimensional movement which isn't the case in my system.

However, the various resources I've found (mostly here on the Forum) have given me a couple of ideas to work with.

Has anyone seen any examples, or would anyone have any suggestions on how Pong-style AI might be extended to a more complex game (such as air-hockey - or table-football which is the next project ) ? How do people generally approach problems such as this, where in the real world a game is based more heavily on reaction time and physical factors (like how hard you hit something)? It seems to me that it's relatively easy to write AI systems with complete knowledge, but which would be unbeatable - even if real-world limits on bat-movement and the like are imposed. So how do you go about toning down the intelligence of a system?

My apologies if any of the above sound like newbie questions - I haven't really tried writing AI systems for games before...

cheers,

Adam...

[edited by - AJFleming on June 10, 2002 5:22:08 PM]

Share this post


Link to post
Share on other sites
IADaveMark    3741
Well, I''m thinking Pong AI would be mostly math and geometry. Calculate the current path of the puck and move to intercept. Advances to that would be then calculating a slightly different position so that your round paddle and direction of stroke would send the puck in a direction other than a direct (mirror)reflection. Advances to that would be pre-calculated but randomly selected shots (direct, bank left, bank right, double bank) to throw off the human player. All of this would have to include a +/- error to humanize it. *shrug*

Dave Mark
President and Lead Designer
Intrinsic Algorithm Development

"Reducing the world to mathematical equations!"

Share this post


Link to post
Share on other sites
AJFleming    122
Hi IF,

thanks for your comments.

One problem that I can see though - each shot type (straight, single deflection, double deflection etc) would have an infinite number of possible strokes to effect it - especially since the physics model of this system (kind of) takes account of spin during collisions. I guess some kind of stroke-generation engine would be required in order to make the system work. This would allow for further "humanisation" though - if different strokes could be characterised as "easy" "hard" "agressive" etc...

Hmmm, have to give this some more thought...

cheers,

Adam...

Share this post


Link to post
Share on other sites
IADaveMark    3741
Yeah... that''s your best bet.

Step 1: What is the path of the puck?
Step 2: What sort of shot should I take?
Step 3: Calculate the intercept point of the puck path and the stroke path in order to generate the proper angle, spin, etc.
Step 4: Fuzzify step 3 in order to humanize the outcome.

Dave Mark
President and Lead Designer
Intrinsic Algorithm Development

"Reducing the world to mathematical equations!"

Share this post


Link to post
Share on other sites
a person    118
simple pong ai:

if(ball.x>paddle.x)
movePaddleRight();
else
if(ball.x movePaddleLeft();

it is only unbeatable if the paddle can move as fast as the ball, ussually there is some "trick" shot in which you move the paddle as it collides to cause the ball to have greater velocity. done enough times and the cpu cant keep up. you can improve this by allow slower reaction time (ie the cpu waits longer before moving the paddle), slower paddle speed, randomness in cpud movement (ie sometimes the cpu overshoots the ball and must adjust).

ai is just the mimicing of something just like physics in games. it dont always need complex algorithms. heck gravity is a complex reaction of forces on mnay objects dependent on mass, distance, etc. in games, its reduced to a simple constant since its a suitable replacement. not all things can be simplified as nicly, but most can be simplfied with acceptable results.

Share this post


Link to post
Share on other sites
Zul    542
If you want to tone down the AI as you said, you could do it like Innocuous Fox said - Calculate the best path of the puck and have the AI player try to hit it there, but randomize it a little. Then you could have difficulty levels by increasing the chance that the AI player can actually produce the perfect shot. Say the "Hard AI" player has an 80% chance of making the perfect shot, while the "Easy AI" player has more like a 40% chance. That way the dumb player can still get lucky It might be kinda fun to implement that way.

"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."

Share this post


Link to post
Share on other sites
Timkin    864
Several people have talked about adding a random factor to the response function of the CPU paddle to ''humanise'' the game play. There is a better way. Add uncertainty into the predictability of the CPU.

The basic idea is that you provide noisy observations on the position of the puck at different times (every frame, every 5th frame, every 20th frame,... whatever interval you choose). The CPU then has to predict the puck velocity and respond to it. How it responds is a tactical procedure. What shot it attempts to play is a strategic procedure.

Anyway, to get back to the filtering. Implement a simple linear Kalman filter to predict the velocity of the puck given observations on position. The output of the filter applied to a linear system is the mean and covariance of a guassian distribution on position and velocity.

Once you have these, you can use the prediction step of the algorithm to predict the position and velocity at any future time. In the absence of observations (during prediction) the uncertainty in the predicted posterior distribution will be proportional to the prediction time interval... so the longer ahead of time the prediction, the more uncertainty. The closer the puck gets to the paddle, the better able the system is to predict the point at which the puck will cross a certain point.

You can use the predictions to plan shots. The earliest predictions will give a feel for where the puck is going to end up and with what trajectory. Given the uncertainty in speed, direction and position of puck, there might be a couple of different return shots that are appropriate. A choice could be made based on the ''set up time'' for the shot, which would be inversely proportional to the speed of the puck. Or perhaps on some other constraint that enabled the system to respond quickly in defensive situations (where the puck is coming in fast), or set up a complex shot if more time allowed (where the puck is coming in slow).

This would then approximate how humans play games like air hockey.

If you need advice on implementing a kalman filter, just holler.

Cheers,

Timkin

Share this post


Link to post
Share on other sites
IADaveMark    3741
Something important in what Timkin mentioned... you should not give the computer exactly accurate knowledge of the state of the puck... especially with regard to the spin. Therefore, as the computer is updating it''s idea of the trajectory, a serious spin prior to a carom would put a bit of a question on the angle of the rebound.

In addition to that, you MUST limit the reaction time, acceleration and speed of the computer paddle. It should take a moment to react (partially accomplished by only sampling the trajectory every X frames), it should have to slow, stop and reaccelerate to change direction of travel as well as slowing to a stop, if desired, prior to contacting the puck, and it should also have a maximum paddle speed. All of this lends to very accurate feel for the computer controlled paddle.

Dave Mark
President and Lead Designer
Intrinsic Algorithm Development

"Reducing the world to mathematical equations!"

Share this post


Link to post
Share on other sites
Ferretman    276
quote:
Original post by Timkin
Several people have talked about adding a random factor to the response function of the CPU paddle to ''humanise'' the game play. There is a better way. Add uncertainty into the predictability of the CPU.

The basic idea is that you provide noisy observations on the position of the puck at different times (every frame, every 5th frame, every 20th frame,... whatever interval you choose). The CPU then has to predict the puck velocity and respond to it. How it responds is a tactical procedure. What shot it attempts to play is a strategic procedure.

Anyway, to get back to the filtering. Implement a simple linear Kalman filter to predict the velocity of the puck given observations on position. The output of the filter applied to a linear system is the mean and covariance of a guassian distribution on position and velocity.




I should think that a Kalman filter is overkill for this particular problem, given what Innocuous Fox noted earlier (and the even simpler example of Pong AI posted by another participant. The biggest issue when one is playing air hockey against another person is more the speed of the puck''s movement than anything else, IMO.

I do like the idea of adjusting the AI so that it has to predict over varying number of frames, and as another poster noted it certainly shouldn''t have exact knowledge of the puck''s spin. That might be a good area for the AI to use a bit of fuzzy logic--the AI player would know the puck has "a lot" or "a little" spin, but not precisely how much.

Just some random thoughts there. Neat problem....I don''t know if I''ve ever actually seen an air hockey computer game, now that I think about it.






Ferretman

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

Share this post


Link to post
Share on other sites
Timkin    864
quote:
Original post by Ferretman
I should think that a Kalman filter is overkill for this particular problem...



A Kalman filter is definitely not overkill in this situation... it''s a simple technique and corresponds to linear least squares estimation of the trajectory. The only reason you do it in a Kalman filter (as opposed a statistical approach) is that it provides the optimal least squares estimate with the minimum of computation (a set of matrix operations).


quote:
Original post by Ferretman
I do like the idea of adjusting the AI so that it has to predict over varying number of frames, and as another poster noted it certainly shouldn''t have exact knowledge of the puck''s spin. That might be a good area for the AI to use a bit of fuzzy logic--the AI player would know the puck has "a lot" or "a little" spin, but not precisely how much.



The one thing that people in the game AI field really need to get a grasp on is the difference between uncertainty and vagueness. It seems apparent that many don''t understand the difference.

Uncertainty is a state of knowledge about the world. The world is in a particular state but your knowledge of that is limited and confused by a lack of certainty in that state. This is basically the situation humans find themselves in. If you want to make your AI more human-like then incorporate uncertainty into the AI.

Vagueness on the other hand is a statement about the state of the world. Jack is tall is a ''vague'' statement because it is talking about the degree to which Jack belongs to the set of ''tall'' people. This is not uncertainty held by an external viewer, although ascribing numbers to vagueness is often a subjective matter (although it shouldn''t be technically).

Fuzzy Logic is a method for describing vagueness and definitely NOT a method for describing uncertainty. There are very sound arguments for why Fuzzy Logic does not, can not and should not be used to describe uncertainty.

Using Fuzzy logic in this situation is a fudge and is not appropriate. If you want the AI to have uncertainty, then use an uncertainty representation (like probability theory) If you want the world to be vague, then use Fuzzy Logic.

It seems to me that people should not rely on a few known techniques and try and bend their game to a technique, but rather look at the problem to be solved and find the best solution.

In this game, if you want uncertainty in the knowledge of the state of the puck, use probabilitiy theory. If you want to classify different states of the puck into a few discrete classifications (perhaps for decision making) then use fuzzy logic. The two techniques are used for completely different tasks.

Cheers,

Timkin

Share this post


Link to post
Share on other sites
IADaveMark    3741
OOHHHH... pissing contests are good!

I happen to know that I didn''t refer to using a FuSM... just made the comment that the hard numbers can be "fuzzied up a bit" through a +/- randomization. In addition, Ferretman''s reference to "fuzzy" was similar to mine. He simply stated that the computer would have a perception of ranges of spin ("a lot of spin or a little spin"). This is not entirely off base.

Methinks that you have allotted the use of the word "fuzzy" to a specific connotation in your world (maybe it''s that silly Ausie language you chaps speak!) and therefore overreacted a bit. The point that both of us were trying to make is still valid... that the computer should not know EXACTLY what is happening at all times... therefore your uncertainty... or, put another way, the computer has a rather fuzzy view of the world.

Dave Mark
President and Lead Designer
Intrinsic Algorithm Development

"Reducing the world to mathematical equations!"

Share this post


Link to post
Share on other sites
Timkin    864
quote:
Original post by InnocuousFox
OOHHHH... pissing contests are good!



Er, no. I don't see this as a pissing contest. I'm just trying to make a point about something...

quote:
Original post by InnocuousFox
In addition, Ferretman's reference to "fuzzy" was similar to mine



Well, Ferretman specifically talked about using Fuzzy logic, whereas you mentioned fuzzification. My last post was in response to the suggestion of using Fuzzy Logic.

quote:
Original post by InnocuousFox
the computer should not know EXACTLY what is happening at all times... therefore your uncertainty... or, put another way, the computer has a rather fuzzy view of the world.



No, no, no, no, no!!!

Fuzzy in terms of AI has a VERY specific definition and it has nothing to do with knowledge held about the world. This is one of my biggest gripes with the game industry... they use fuzzy logic in situations where it is quite simply the wrong thing to do... and your use of the word fuzzy led Ferretman to reinforce the idea of using fuzzy logic to represent uncertainty.

In your case Dave it's just a point of terminology. I would say you've used the wrong terminology to describe randomness/uncertainty... and no it's not an Aussie thing, it's an AI thing. In Steve's case it's a suggestion of using Fuzzy Logic to represent uncertainty in the knowledge held about the level of spin of the puck. As I explained in my last post, that's the wrong tool for the job: fuzzy logic is not appropriate for such a task. Probability theory is. If you want the formal reasons why I would be happy to elaborate on them.

I'm sorry if I came across badly in my last post. That wasn't the intention, although I will admit that a little of my ire at the misuse of AI techniques arose and that obviously came across in my post. My apologies to all concerned.

Cheers,

Timkin

[edited by - Timkin on June 11, 2002 1:47:00 AM]

Share this post


Link to post
Share on other sites
fup    463
I don''t think this is entirely about misuse of AI techniques, this is about misuse of semantics. The word ''fuzzy'' seems to have all sorts of meanings for programmers nowadays and many of them have nothing to do with set theory.

The thing is Timkin, if developers use what they call ''fuzzy logic'' in their games and it works, then... it works. In the commercial world that''s all that matters. It''s not misuse if it works, whatever people want to call it,, and however much you think it''s fudged. Bosses don''t care about elegance and formal theory, they just want to see results.

Steve: I have actually seen airhockey on the PC. It was networked too. I saw it about 4 years ago, it came as part of some obscure compendium of windows games. It was a pretty awful piece of coding though if my memory serves me right.




Stimulate

Share this post


Link to post
Share on other sites
Timkin    864
quote:
Original post by fup
The thing is Timkin, if developers use what they call ''fuzzy logic'' in their games and it works, then... it works.



But how much time and effort is wasted trying to get the spanner to work on the round nut, or the screw? Choosing the right tool for the job makes things a hell of a lot easier, makes the results a lot better, saves time and saves money... and it''s really these last two that publishers care about. It should be the first two that programmers are concerned about... but they seem to forego these in favour of using a ''buzz word'' technique as I call them (Fuzzy logic, GA, neural network), regardless of how inappropriate it is for the task.

BTW: As to what ''works'', I''d say that something that implements fuzzy logic to represent uncertainty doesn''t work... it''s just that the programmer keeps adding fudges until it looks like it works. I could give other examples as well (not directed at specific people/organisations)... the use of GAs for learning, when they''re a blind search algorithm... the use of neural networks for decision making, when they''re a classification (or function approximation) algorithm... the list goes on.

(rant on)
Too many people post to these forums saying I have problem A and I want to get neural network B (or fuzzy logic C) algorithm to solve it. This is not the way to go about doing AI, developing games, doing science or any problem solving scenario! Look at the problem and find the RIGHT solution to it. In the end it will save you time, money, effort and heartache!

So, when I suggest the right tool for the job (and I know it''s right because I would generally be considered an expert - or close to it - on uncertainty and belief revision) and someone says it''s overkill and suggests a spanner for a round nut, I think that''s not only inappropriate but also the wrong message to get across to people trying to develop AI for games. Just my opinion of course and I''m sure the industry will keep its head in the sand and continue to tighten screws with spanners regardless of what I think.
(rant off)

Cheers,

Timkin


Share this post


Link to post
Share on other sites
Timkin    864
I''m getting a little defensive. Again my apologies. I just get the feeling that people are discounting what I am saying because people have applied fuzzy logic to these sorts of problems in the past and gotten it to work. I''m just trying to say that just because they got it to do something doesn''t make it the right way to do it, nor the best way to do it.

Enough said on my part. I won''t post any more to this thread except to answer questions as I don''t think I''m going to convince the world it''s wrong and I''m right!

Cheers,

Timkin

Share this post


Link to post
Share on other sites
AJFleming    122
Wow!

Thanks for all the responses guys, you''ve definitely given me some things to think about...

The consensus - as far as I can tell, is that some form of predictive system is required - the system will observe certain values about the puck and use these to generate a predicted position and then determine (in some way) the best shot to play, and the movement of the puck required to play that shot.

This breaks down into two areas - the predictive system and the shot generator.

Timkin, I''ve done a little research on Kalman filters and have managed to confuse the hell out of myself! Can you point me at, or give me a quick overview on what they are, how they work and so on... My stats background is a little rusty - so use little words please

I''m a little unclear as to what you''re suggesting as well... It sounds like you''re talking about providing noisy observations to a perfect prediction system - is this correct? I assume you''re referring to velocity as an observation, albeit a derivative of perfect observations of location... So how do you introduce the noise?

I''d be inclined to make use of the spin-factor to increase the uncertainty of the system as well. Perhaps just considering direction of spin and leaving considerations of speed of spin completely uncertain.

I guess I can leave the shot generation for the moment... If I can make the system consistantly play one class of shots (direct attacks probably) then adding additional shots can be considered and added later...

cheers,

Adam...

Share this post


Link to post
Share on other sites
fup    463
Timkin: I agree with everything you''ve said in your last few posts and I understand your frustration. In my post I was trying to point out two things:

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.

2) That so called ''esoteric'' techniques such as fuzzy logic, GA''s, and neural nets are frequently misunderstood by games developers/programmers. They seem to have little idea of their capabilities and shortfalls and so they are either often proffered as a solution where they are innapropriate or dismissed as a solution when they *are* appropriate. I''m sure you have seen this sort of thing time and time again.

I don''t think people discount what you have to say, I certainly don''t and I''m sure many regulars don''t either. So keep posting!





Stimulate

Share this post


Link to post
Share on other sites
fup    463
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

Share this post


Link to post
Share on other sites
Zul    542
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."

Share this post


Link to post
Share on other sites
AJFleming    122
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!

Share this post


Link to post
Share on other sites
Zul    542
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]

Share this post


Link to post
Share on other sites
Timkin    864
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

Share this post


Link to post
Share on other sites