Game/AI

Very cool stuff, Rob!

It's interesting to think about how HMMs could be used to try to predict player strategies in games where there are discrete dependencies between actions, such as MMORPGs or certain fighting games.

For example, say I'm dueling a druid in World of WarCraft -- I know that certain actions are only possible when the druid is in Cat form, other actions are only possible in Bear form, and others only when he's in Night Elf or Tauren form. Various actions the druid can perform require various amounts of mana (in Night Elf/Tauren form only), certain numbers of combo points and energy points (in Cat form) or a certain amount of rage points (in Bear form). Potentially, a HMM could be useful in helping build an AI player that could guess what the opposing player will try next -- "The druid went into Cat form and started putting combo points on me, so he's probably going to use either the Rip or Ferocious Bite action sometime soon as a 'finishing move' to take advantage of those combo points."

Similarly, it might be useful in a real-time strategy game for predicting what buildings a player will create next ... "I see that player X just built a Library and a Water Mill, so he's probably planning to build either a Dragon Hatchery or a Sages' Tower ..."

I'm not sure how useful either of those would actually be in practice, since the state machines don't really form an interesting graph in either case -- the 'actions' in all of these cases tend to be either a simple tree (in the case of an RTS) or a collection of almost completely independent states with few dependencies (in the case of combat actions in an MMORPG or a fighting game).

Still, though, it's thought-provoking. I'm particularly interested in what kinds of game designs HMMs could inspire, and whether there's an interesting game based on either A) computer players which use HMMs in an interesting way and/or B) creating gameplay that forces the player to use HMMs in an interesting way as part of their internal mental model for gameplay.

In general, it seems like a good technique for games, because it has simple knobs that designers can fiddle with to get the behavior they want. Unfortunately, I can't think of a practical use for it either...

It seems like it is useful for making good guesses from incomplete information. In a way, it codifies assumptions and experience. Maybe you could use it to make your AI more susceptible to bluffs? Like you have a poker game and set up your HMM to over-react to large raises. It would be more interesting than an opponent that just perfectly calculates the probabilities involved.

You could even use different transition functions to create different NPCs. Then the Player would have to try to uncover the "hidden" nature of the model to outplay each NPC.

Maybe I have Player-represention on the brain, but maybe you could use information gathered over multiple hands to build an HMM representation of the Player. "If Player X bets hard on an inside straight, he's probably over-estimating his odds." You touch on this briefly, but it seems like a good model because it finite and managable, and it gets fooled in cool ways when the Player changes his behavior suddenly.

What's your feel for how many examples it takes to build a transition function?