Sign in to follow this  
kvsingh

Hidden Markov Models instead of FSM in an FPS

Recommended Posts

I have been working on a course project in which we implemented an FPS using FSMs, by showing a top 2d view of the game, and using the bots and players and circles. The behaviour of bots was deterministic. For example, if the bot's health drops to below a threshhold, and the player is visible, the bot flees, else it looks for health packs.

However, I felt that in this case the bot isn't showing much of intelligence, as most of the decisions it takes are based on rules already decided by us.

What other techniques could I use, which would help me implement some real intelligence in the bot? I've been looking at HMMs, and I feel that they might help in bringing more uncertainty in the bot, and the bot might start being more autonomous in taking decisions than depending on pre defined rules.

What do you guys think? Any advice would be appreciated.

Share this post


Link to post
Share on other sites
The problem is not that your rules are hand-crafted, but that you don't have enough of them and likely that each one of them only takes into account a small number of inputs (e.g. Health < x && Player visible). The more relevant information you take into account in more subtle ways, the more complex and potentially realistic your behaviors will look.

To be honest, it all depends on the information you have available to your agent. If you don't have a lot of info in your world model, HMMs, NNs, or anything else for that matter, won't do you a lot of good.

That being said, what other information is available to your agent?

Share this post


Link to post
Share on other sites
Well, the agent(bot) can

1. See anything in it's field of view, which is a square of finite size around the bot. It constantly quiries its field of view for health packs and the player, and knows their coordinates if they are in the field of view.
This is used when the player is deciding between searching for the player or attacking the player.

2. Knows its own health and ammunition count, which are used in deciding whether to flee or attack

3. Has a memory, which is an array which contains the locations of health packs that it encounters. So, even when it is not taking health packs, if one happens to fall in its Field of view, it stores its location in its memory. This can be used when it needs to replenish its health.

4. It can find out if the player is in its Line of sight (this is used in deciding whether to fire or not). It can also tell if an obstacle is in the way.

5 It knows its own state information

Should I be giving more information to my agent?

Share this post


Link to post
Share on other sites
Can it assess another position regarding line of sight and such?

I don't know your world allows, but for example, if you had complex terrain that you can use for cover, and the bot can assess line of sight and hypothetical vulnerability in a given location, you could factor that into your pathfinding algorithm; it would be smart enough, for example, to run through a canyon for cover towards a target, or something.

This is somewhat integrated with your game design.

Does position matter, or is combat maneuvering superfluous?

If it matters, can your bot really assess different positions? Can it see an advantaged position, and plot a safe route to that position?

If it's injured, can it plot a safe route to a known health point giver widget? A safe route back to its team?

At this point it would still be very reactionary, insect-like, unimaginative, but possibly able to give a good impression.

Share this post


Link to post
Share on other sites
I see why you might generalize from FSMs to Markov models for your bots. But what's "hidden;" why are you considering HMMs?

Typically, you use an HMM to model an unknown process. Do you want to use HMMs to model (and predict) the player's actions? That would make sense, though I'm not sure I'd suggest it as the first thing to do.

Share this post


Link to post
Share on other sites
Quote:
Original post by Emergent
I see why you might generalize from FSMs to Markov models for your bots. But what's "hidden;" why are you considering HMMs?

Typically, you use an HMM to model an unknown process. Do you want to use HMMs to model (and predict) the player's actions? That would make sense, though I'm not sure I'd suggest it as the first thing to do.


I'm sorry, I meant Markov Systems. I just want to maybe include a level of uncertainity. I agree it won't give any more intelligence to the bot, but a player who's playing would not be able to predict the behaviour of the bot.

Share this post


Link to post
Share on other sites
Quote:
Original post by JoeCooper
Can it assess another position regarding line of sight and such?

I don't know your world allows, but for example, if you had complex terrain that you can use for cover, and the bot can assess line of sight and hypothetical vulnerability in a given location, you could factor that into your pathfinding algorithm; it would be smart enough, for example, to run through a canyon for cover towards a target, or something.

This is somewhat integrated with your game design.

Does position matter, or is combat maneuvering superfluous?

If it matters, can your bot really assess different positions? Can it see an advantaged position, and plot a safe route to that position?

If it's injured, can it plot a safe route to a known health point giver widget? A safe route back to its team?

At this point it would still be very reactionary, insect-like, unimaginative, but possibly able to give a good impression.



Yeah, I see what you mean. The bot probably does not have enough information.

Nevertheless, will moving from FSMs to Markov systems/ Fuzzy systems help in making the game more uncertain, so that the player is not able to predict the behaviour of the bot?

Share this post


Link to post
Share on other sites
If all you want to do is make the actions of the bot less predictable, all you really need to do is put some fuzzyness in the FSM transitions. Keep in mind, a state in a FSM is only what the bot is doing at any one time. Regardless of the underlying decision process, you are still going to end up in something analagous to a state. A behavior tree, for example, sifts through the tree to find the most appropriate state for the agent to be in at that time. The only different between a FSM and a behavior tree is that the reasoning code is held in a separate place (the tree) rather than putting the transition logic in each state as in a classic FSM.

That being said, you have a number of choices -- even in a classic FSM structure. By simply making your transitions non-deterministic, you are going to achieve a lot of what you are looking for. For example, rather than StateA having transition logic that says "if ConditionB -> StateB" and "if ConditionC -> StateC" you could do something as simple as "if rand() % 3 == 1 then StateB else StateC". As you can see, StateA will transition to StateB 1 out of 3 times and State C 2 out of 3. Obviously, this is a simple example but the point is, not all transition logic needs to be based on deterministic criteria.

A more complicated, but very effective and reasonable-looking, method is what I describe in my book. By analyzing the various available choices, scoring them somehow based on their attractiveness at the time, and then using those scores -- not to always pick the winner -- but to seed weighted randoms (where the weights are based on the scores), you can have dozens, or even hundreds of potential actions in play. The good ones will be chosen more often than the bad ones because their weights will be greater. The bot will not be entirely predictable, but it will look reasonable at any given time. Rather than being able to say "he will now do this" before the fact, you will be able to say "that made sense" after the fact.

Share this post


Link to post
Share on other sites
Quote:
Original post by InnocuousFox
If all you want to do is make the actions of the bot less predictable, all you really need to do is put some fuzzyness in the FSM transitions. Keep in mind, a state in a FSM is only what the bot is doing at any one time. Regardless of the underlying decision process, you are still going to end up in something analagous to a state. A behavior tree, for example, sifts through the tree to find the most appropriate state for the agent to be in at that time. The only different between a FSM and a behavior tree is that the reasoning code is held in a separate place (the tree) rather than putting the transition logic in each state as in a classic FSM.

That being said, you have a number of choices -- even in a classic FSM structure. By simply making your transitions non-deterministic, you are going to achieve a lot of what you are looking for. For example, rather than StateA having transition logic that says "if ConditionB -> StateB" and "if ConditionC -> StateC" you could do something as simple as "if rand() % 3 == 1 then StateB else StateC". As you can see, StateA will transition to StateB 1 out of 3 times and State C 2 out of 3. Obviously, this is a simple example but the point is, not all transition logic needs to be based on deterministic criteria.

A more complicated, but very effective and reasonable-looking, method is what I describe in my book. By analyzing the various available choices, scoring them somehow based on their attractiveness at the time, and then using those scores -- not to always pick the winner -- but to seed weighted randoms (where the weights are based on the scores), you can have dozens, or even hundreds of potential actions in play. The good ones will be chosen more often than the bad ones because their weights will be greater. The bot will not be entirely predictable, but it will look reasonable at any given time. Rather than being able to say "he will now do this" before the fact, you will be able to say "that made sense" after the fact.


Thanks a lot! That's exactly what I needed!

Share this post


Link to post
Share on other sites
Quote:
Original post by Emergent
Quote:
Original post by InnocuousFox
some fuzzyness in the FSM transitions.


In academic circles this would be called a Markov Chain.

It sounds less intimidating this way. Also, this is a broader concept. For example, the transition percentages may or may not be used based on conditional logic. If ConditionA is in place, switch to StateA, but if it is not in place, select from B, C, and D based on some weighted criteria. If ConditionA is based on external input from the game state or the user, that breaks the concept of a pure Markov Chain.

Incidentally, Brian Schwab (ex-SOE, now Blizzard) and I are doing a session at the GDC AI Summit about the pros and cons of randomness in games.

Share this post


Link to post
Share on other sites
Quote:
Original post by InnocuousFox
It sounds less intimidating this way.


I like this as a reason; people do tend to tune out when they hear scary-sounding jargon. It's my hope that, if people read, say, your accessible description, and then hear "by the way; that thing you read about? That's all [jargon word] is," then the jargon gets less scary, and previously-inaccessible literature opens up.

Quote:
Also, this is a broader concept. For example, the transition percentages may or may not be used based on conditional logic. If ConditionA is in place, switch to StateA, but if it is not in place, select from B, C, and D based on some weighted criteria. If ConditionA is based on external input from the game state or the user, that breaks the concept of a pure Markov Chain.


We'd call that a controlled Markov Chain.

Quote:
Incidentally, Brian Schwab (ex-SOE, now Blizzard) and I are doing a session at the GDC AI Summit about the pros and cons of randomness in games.


Interesting.

Your abstract reminds me of a popular book I read recently, The Drunkard's Walk; he talks about, among other things, studies in psychology that show how people are systematically unable to identify or to generate random sequences. In particular, your phrase "mitigating some of the problems that truly random sequences can generate" reminds me of the iPod shuffle issue (mentioned in the book), where Apple had to change its shuffle algorithm to make it "less random" in order for people to believe that it actually was "random" (What exactly the change was, he doesn't say; I will guess that they switched from generating an i.i.d. sequence of songs to generating a random permutation, or something like that, to avoid repeats.)

The phrase "randomness in games" also reminds me of that fact that, although not all games have Nash equilibria in pure (deterministic) strategies, all games do have Nash equilibria in mixed (probabilistic) strategies -- the prime example being Rock Paper Scissors, where the only equilibrium is for both players to pick uniformly at random. I feel that this gives a nice theoretical justification for why, sometimes, behaving randomly is the best thing to do. (Of course, common sense also tells you that unpredictability is good.)

Anyway, I'm getting away from the original purpose of this thread. Still, sounds like an interesting topic.

Share this post


Link to post
Share on other sites
Quote:
Original post by Emergent
Your abstract reminds me of a popular book I read recently, The Drunkard's Walk;

Brian and I have both read it and will be using a couple of the examples from it at the beginning to "set the stage".

His part of the lecture, in particular, will be about how, in a basketball title he did at SOE, people were bitching about "hot streaks" and "cold streaks" that players went on despite the fact that it was all just random numbers thrown at "67% shooter". (e.g. "He shoots 67% from the floor -- how can he possibly have missed 5 in a row?!?") You can use techniques like "random without replacement", etc. to get away from that.

Share this post


Link to post
Share on other sites

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

Sign in to follow this