2
$\begingroup$

What I would like to do is improve upon projects like 'RNG plays pokemon'. There, a computer produces a random sequence of inputs that are transmitted to an emulator and played in-game. Though this seems really pointless, the computer managed to beat the game that way.

However in this project, buttons are pressed at random, so the behaviour of the character is very far from what you would expect from a human player. What I would like to do is to be able to produce a series of inputs that 'look like' one produced by a human player.

A good way to do that may be to record a sequence of inputs as played by a human player, use this data in order to produce a Markov Chain.

However I think a human player may exhibit a behaviour that is not easily taken into account by a Markov Chain. For example in order to double jump, it is generally a bad idea to have the second jump right after the first. So a typical sequence of inputs would look something like this (where f=forward and j=jump) f-f-f-j-f-f-f-f-f-f-f-f-f-j-f-f-f

This sequence of inputs may be common when the game is played by a human, but in order to have a Markov Chain produce such a sequence of inputs, it means that the states have to correspond to sequences of inputs of length (at least) 10, hence a huge state diagram.

Is there an alternative to (or a variation of) Markov chains that can take this kind of behaviour into account?

NB: English is my 2nd language so I apologize if this question is poorly worded...

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ What you may not realize is that there are ininitely many possibilities, Markov Chains being one (which may or may not be suitable). You'll have to specify more closely what you need in order to get good answers. One rather obvious idea: use different models for menu, combat, walking, ... $\endgroup$
    – Raphael ♦
    Sep 10 '15 at 9:54
  • $\begingroup$ @Raphael You are right, I will stick with the first example. $\endgroup$
    – Maxime Lucas
    Sep 10 '15 at 11:48
3
$\begingroup$

A Hidden Markov Model could be useful here. Basically you have a Markov Chain of internal states (e.g. "i just jumped", "i'm running", "i'm ready to jump again") and for each transition of the internal state it generates an action (e.g. "f" or "j") according to a distribution that is different for each internal state. You will need to figure out how many different internal states you need, and then you can learn the model from the data.

If you want to model a bunch of different things inside the hidden state (running/not running, has weapon/doesn't have weapon, ...) you can switch to some kind of recurrent neural net (e.g. LSTM)

Improve this answer
$\endgroup$
0
$\begingroup$

A Markov chain is a probabilistic generalization of a DFA. There is also a probabilistic generalization of a pushdown automaton. If you like, you can think of this as a probabilistic context-free grammar, where each production in the grammar has a probability associated with it, and out of all possible productions you choose one according to the probabilities. Such things can potentially model longer-range patterns, and there's work in learning them. I'm not sure they'll actually be useful for your specific goal of mimicing English, though.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.