you''re right, let the personal side of this thread die. Back to Markov Chains. :-)


kiev

Well, it seems that you two (Eric and Kiev) have effectively killed this thread! 8^(

Either that or there is actually no one out there interested in Markov Models for game AI. I had considered developing an example of how to use one in a game, but I won''t bother if no one is reading this thread.

Tim

Continue please. I''ve not really researched AI, and it appears you are doing all the work for me:-)


Stay Lucky, Graham "Mournblade" Reeds,
ICQ: 30514803
http://homepage.dtn.ntl.com/grahamr

Well, I am actually interested by your explanations, as they explain at last what a Markov Model *IS*.
I read a lot of papers on what I could use Hidden Markov Models for, but never what they freaking were... so thanks for that.

Now tell me, I am working on doing a gesture recognition system (it''s an idea I had *before* I saw Black and White )
and I have been thinking about different systems.
I found out about Hidden Markov Models, but they seem very Mathsy for me ... the other choice I have is Neural Networks, but I wonder how on earth I would do it if I allow my users to create their own new gestures... the other last solution I am considering is to try to find a way to do some pattern matching. Basically I analyze the mouse movements according to different criteria, then from that I get a "signature", and I try to match this signature with a table of existing ones; my difficulty here is to find a way to do "fuzzy matching"

So why would I use Markov Models in this context, or maybe what could they bring me ?

youpla :-P

Quote:



Original post by ahw
Now tell me, I am working on doing a gesture recognition system (it''s an idea I had *before* I saw Black and White )
and I have been thinking about different systems.

I found out about Hidden Markov Models, but they seem very Mathsy for me...


Many of the uses of Hidden Markov Models (HMMs) to date have been in the field of engineering where they are used for monitoring (filtering) and prediction of dynamic systems. This has meant that much of what has been written has been presented solely in a mathematical context.

Over the past 10 years HMMs have been found to be a subclass of a more general model, the Dynamic Belief Network (DBN)(or sometimes called a Dynamic Bayesian Network). You will find a lot less mathematics in explanations of these networks. A good starting point for Belief Networks is, as I said, Russell and Norvig''s book. Also, there is a book by Finn Jensen. It''s titled something like "An Introduction to Bayesian Networks". It''s been some time since I picked it up so I could be out on the title. There are more advanced books on the topic however you will find that most of the material published in the field of Bayesian Networks (both static and dynamic) is published in the proceedings of the annual Uncertainty in Artificial Intelligence conference. Just do a web search for UAI proceedings.



the other choice I have is Neural Networks, but I wonder how on earth
I would do it if I allow my users to create their own new gestures... the other last solution I am considering is to try to find a way to do some pattern
matching. Basically I analyze the mouse movements according to different criteria, then from that I get a "signature", and I try to match this signature
with a table of existing ones; my difficulty here is to find a way to do "fuzzy matching"

So why would I use Markov Models in this context, or maybe what could they bring me ?



I think the correct question to ask is what is the best available model for my problem. It seems too apparent to me that many AI programmers are stuck on the buzz words of Neural Net and Genetic Algorithm. There are so many other tools out there (as you have discovered by investigating Markov Models).

It sounds to me that you want an AI tool that can recognise gestures made by the player. I presume the input devices are predominantly the mouse and perhaps the keyboard?

It is difficult to say which tool is most appropriate for the task without first knowing more about what the task is. Could you elaborate a little more on what it is you are trying to achieve and why?

You did say that you were trying to do some fuzzy pattern matching. Learning associations between input and outputs, in the presence of noise, is what artificial neural nets are good at. If this is indeed your task then you would want to investigate them further.

HMMs (and DBNs) on the other hand are useful for monitoring/filtering, prediction, diagnosis, classification, decision making under uncertainty and planning; just to name but a few applications over the past decade!

Let''s first elaborate on your problem and then we can see if ANNs or HMMs/DNBs are the most appropriate tool.

Tim

Hey, Tim. How about writing up an article for GameDev? This is a very interesting topic, and I''d love to hear more about it.

Tres cool.


Stay Lucky, Graham "Mournblade" Reeds,
ICQ: 30514803
http://homepage.dtn.ntl.com/grahamr

Timkin wrote

quote:
I think the correct question to ask is what is the best available model for my problem. It seems too apparent to me that many AI programmers are stuck on the buzz words of Neural Net and Genetic Algorithm. There are so many other tools out there (as you have discovered by investigating Markov Models).

Precisely my point. I don''t want to use ANN just because it''s trendy. I am just looking for a method to solve my problem. If there is a better way to do it than using ANN, then sod it.
Now on the other hand, I am biased towards using something like ANN, because it would give me exprerience in their use. And since my Masters is on AI, this would come handy.

But to describe my idea more :
You simply record the position of the mouse while the user press the mouse button. What you get is a list of (x,y) coordinates.
Now the idea would be to observe this list under different aspects to "recognise" gestures (I don''t use the word picture, because my goal is not image recognition as such).
For instance, one thing you''ll notice is that a gesture is basically ONE line twisting in various directions, until the user release the mouse button. Right ?

First I want to normalize my values. To do that, I could use something like the total length of the segments I have drawn. Scale all the values down so that the total length of the gesture is 1.
Once I have normalized my values I want to analyze relative values, rather than absolute.
My idea is to observe the evolution of one or several parameters during the drawing of the gesture, and use this as a signature for the gesture.
For instance, if I observe the angle of the segments drawn, I get a series of angles. I can then draw a graph of the evolution of the angle, where x would be the position in the list of segments, and y the angle.
Sample this to say, 256 points, with the angle value becoming equal to a [-128 , 128] value (instead of [0,180])
And your gesture has it''s signature...

Now the problem is that when I draw something with the mouse, I will hesitate, or I will have a varying number of points, or my shape will be a bit dodgy, etc (try drawing a circle, for instance).
This is were the "fuzzy matching" comes in.
Should I use something as simple as
"Compare the values of the signature with a database of signatures, calculating a percentage of matching",
or do I go with something more complicated...

Mmmmmh.

Like I said, using ANN would be a good exercise, but if you understand what I am talking about now, you can see that there are several ways to go.
What''s your opinion.

(Oh, and since you mention Bayesian Networks, could you describe that too ... I ran into the word tons of times, but can never find a simple one-line description of what it is).

youpla :-P




Sancte Isidore ora pro nobis !

Timkin:
I agree with Grahamr, you really should write an article about this, its a very interedting topic, and these threads don''t stay up for long.

------------------
It''s me again!

quote: Original post by Taharez

Timkin:
I agree with Grahamr, you really should write an article about this, its a very interedting topic, and these threads don''t stay up for long.

------------------
It''s me again!

If you are having trouble reading previous threads, then consider reseting the control at the top of the AI Forum, to show all topics (or just go back some number of days).

Eric

Yes, Timkin you are very very interresting.

Why English rules?? C pas très malin tout ça!