Can Viterbi algorithm be applied to game ?
Author
Hello,
I am working on a project which related to Game AI and I want to make a RPG with machine learning features included.
My idea is that the enemies can learn player's attack and come up with defense or counter-attack but I hardly figure out which algorithm is the best to apply.
As I know, Viterbi algorithm finds a sequence of hidden states and it is used in speech recognition. If the sequence of hidden states change to the observed events and players' attack to the creatures, the creatures will give respond on how they defense themselves and that might be the result I want to.
Is the theory workable?
Can Viterbi algorithm used in the situation?
if anyone has a better idea... or has knowledge of this type of thing and can point me in the right direction, i would appreciate it.
Reference :
http://www.comp.leeds.ac.uk/roger/HiddenMarkovModels/html_dev/viterbi_algorithm/s1_pg1.html
The Viterbi algorithm tries to guess a sequence of unknown past states in a Markov chain given a sequence of related observations; in the traditional communication setting, the states are a sequence of transmitted symbols and observations are the noisy received signals.
Game AI rarely needs to estimate a sequence of past states from a sequence of observations; normally, in order to predict future moves, only the current state of an opponent is important.
Agent state is not subject to a known HMM, unless it is an AI cheating against another AI; the states might be an arbitrary hypotesis, but their transition probabilities must be learned online before a good estimate of the transition matrix can be used for Viterbi decoding.
Even if we needed to estimate a sequence of states and we had an accurate model, the state of an agent is normally too complex; the Viterbi algorithm is suitable for small symbol (state) sets like the bundles of a few bits used in digital communications or the phonemes used in speech recognition.
With 6 integer stats between 0 and 1024 the model needs 2^60 states (in theory) or a difficult quantization of the values (in practice).
The Viterbi algorithm processes each state at each timestep, and the transition matrix has a size equals to the square of the number of states: clearly one would need lossy compression of the transition matrix and cheaper algorithms like beam search replacing full Viterbi decoding.
This is completely unclear.
Game AI rarely needs to estimate a sequence of past states from a sequence of observations; normally, in order to predict future moves, only the current state of an opponent is important.
Agent state is not subject to a known HMM, unless it is an AI cheating against another AI; the states might be an arbitrary hypotesis, but their transition probabilities must be learned online before a good estimate of the transition matrix can be used for Viterbi decoding.
Even if we needed to estimate a sequence of states and we had an accurate model, the state of an agent is normally too complex; the Viterbi algorithm is suitable for small symbol (state) sets like the bundles of a few bits used in digital communications or the phonemes used in speech recognition.
With 6 integer stats between 0 and 1024 the model needs 2^60 states (in theory) or a difficult quantization of the values (in practice).
The Viterbi algorithm processes each state at each timestep, and the transition matrix has a size equals to the square of the number of states: clearly one would need lossy compression of the transition matrix and cheaper algorithms like beam search replacing full Viterbi decoding.
Quote:If the sequence of hidden states change to the observed events and players' attack to the creatures, the creatures will give respond on how they defense themselves and that might be the result I want to.
This is completely unclear.
Game AI is often simplified by the fact that the AI doesn't really have to deduce everything from observations (e.g. via computer vision techniques), but it can "cheat" simply by looking at the game state (e.g. just read off the position of the opponent instead of using Kalman filter and whatnot).
But your AI could, for example, find out the hidden "mental state" of the player from the recent game states. This mental state could then be used to pick a strategy.
- Mikko
Author
Thanks LorenzoGatti and uutee, I feel better on game AI.
However, for academic purpose, I think I would take a try on Viterbi algorithm
To clarify my situation, let me explain my project in details:
What I want to create is a massively mutiplayer RPG platform (just like Diablo, but mine maybe a maximum of 16 :P)
and I would like to apply the algorithm on the monsters for machine learning basis.
How I will apply Viterbi algorithm?
First of all, I would define player's status, the sequences of attacks and environmental factors as the observed states in a Markov model
Then, Viterbi algorithm guess a sequence of these past states and compute out the probabilities of the actions taken by monsters, which the responses are the hidden states(outcome).
The purpose is to let the monsters recognize some types of attacks and 'learn' some kinds of "hidden" action (defense or aggressive approaches) to confront.
For example, players often invoke the same kinds of attack or the attack can cause great damage to the monsters will trigger Viterbi algorithm, thus after attacking the monsters for several times, monsters may probably knows the users' attacks and learn some skills to defense.
The problem concerned is how I can generate the Markov model that can be used to pick a strategy?
Are there any specific considerations on the states declaration subjected to the known HMM?
However, for academic purpose, I think I would take a try on Viterbi algorithm
To clarify my situation, let me explain my project in details:
What I want to create is a massively mutiplayer RPG platform (just like Diablo, but mine maybe a maximum of 16 :P)
and I would like to apply the algorithm on the monsters for machine learning basis.
How I will apply Viterbi algorithm?
First of all, I would define player's status, the sequences of attacks and environmental factors as the observed states in a Markov model
Then, Viterbi algorithm guess a sequence of these past states and compute out the probabilities of the actions taken by monsters, which the responses are the hidden states(outcome).
The purpose is to let the monsters recognize some types of attacks and 'learn' some kinds of "hidden" action (defense or aggressive approaches) to confront.
For example, players often invoke the same kinds of attack or the attack can cause great damage to the monsters will trigger Viterbi algorithm, thus after attacking the monsters for several times, monsters may probably knows the users' attacks and learn some skills to defense.
The problem concerned is how I can generate the Markov model that can be used to pick a strategy?
Are there any specific considerations on the states declaration subjected to the known HMM?
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
