1
\$\begingroup\$

I am trying to implement some kind of system, that would allow AI to imitate player's action at certain points in similar cases. Case example

Player (hp: 10, mp: 5) used skill [BasicAttack] when in battle

When I set for a bot parameters like hp: 10, mp: 5 and state attack it should use BasicAttack skill because in same case player used that action. (I'd like to have ability to define similar cases like when hp: 11, mp: 6 then bot use BasicAttack too because it is similar to hp: 10, mp: 5 case but whatever)

The question is that what are the basic approaches for such cases? Leaving aside snapshotting of player's state, how can such system be implemented?

So far I have two ideas. My ideas are

1. order player parameters by priority and states and create tree where every node would be
corresponding parameter value. For example node with name [hp] and value [10] will have a
child note [mp] with value [5] thus I can create required paths to actions

2. I have event log with recorded player events. It keeps its record ordered. I iterate over 
it and using pattern matching I compare player parameters and retrieve corresponding player
action

The first approach seems much faster though.

But I'd like to know if there already exist approaches for such systems, in order not to reinvent the wheel as I used to do. Are any?

\$\endgroup\$
  • 1
    \$\begingroup\$ What you describe is a branch of AI/machine learning called "supervised learning." We feed an algorithm example input vectors (eg. player states) and expected output for each (action the player took) - this is called training. Then, we ask the trained AI "what output is appropriate for this new input?" This is a huge field of study, with many different algorithms suited to different problems, depending on their specifics. You should do some basic research in this area, and look to Cross Validated or the AI StackExchange for more details. \$\endgroup\$ – DMGregory Feb 18 '17 at 1:36
  • \$\begingroup\$ @DMGregory wow cool. Did not know about that. \$\endgroup\$ – lapots Feb 18 '17 at 8:54
1
\$\begingroup\$

What you want is to measure frequency of the actions the player performs.

Abstract: Every time the player you want to imitate does an action you take a copy of the (relevant) player state and for that player state, make a counter for the action and add 1 to it. Then use that as probability distribution for the AI agents.


Data structures

What you want is a data structure that provides fast lookup on complex data (the player state).

Below I suggest using locality sensitive hashing, the idea is to take all the variables of the data (the player state) and use them to compute a single value that you can then use as key to lookup in such way that similar items will result in a similar key if not the same.

A simple approach to do this is to keep the order of relevance of the bits of information, perhaps removing a few. For example, if you have hp = 10 and mp = 5, you have (in binary) hp = 1010_2 and mp = 101_2, if we combine by simple XOR we have 1111_2 (15), by removing the last two bits we have key = 11_2 (3).

Other similar values will have the same key, such as (hp = 11, mp = 5), (hp = 11, mp = 6), (hp = 10, mp = 4), (hp = 11, mp = 4), etc... but will also other values that are not that close such as (hp = 15, mp = 0), or even (hp = 70, mp = 75).

Of course, there could be better hashing algorithms, yet, in general this shows that you can't take the collision as a guarantee of proximity, but it will reduce the search space considerably, improving your performance.

Therfore, I'd suggest to combine locality sensitive hashing with the custom search tree which you have already considered.


General Solution

When the player is playing

For example, when the player is battle, with hp 10 and mp 5 and does a basic attack...

  1. Take a copy of the player state (in battle, hp = 10, mp = 5, etc...)
  2. Look if there is a recorded player state close enough※ to that and select it. if there isn't, create a new recorded player state with an associated action dictionary and select that
  3. On the action dictionary for selected recorded player state, look for the action the player performed※※, if it is there add 1 to its counter, if it isn't add the action with value of 1

※: You will need your own definition of close enough. In general, you can think of the player state as a vector space (where each variable you consider is a dimension) then each state is a point and you can measure distance from point to point. You may consider using locality sensitive hashing on the player state to map similar player states. You may also want to consider to represent variables in a uniform scale (for example, instead of taking at hp = 10, take hp = 20%).

※※: You will need to abstract your actions. You cannot consider attack each enemy as a different action, but you may consider distinguishing attacking the weakest enemy, attacking the stronger enemy, etc... Or you may just have attack. There will be a sweet spot of granularity for your game.


When the AI is playing

The AI agent will take its own "player state", look up for similar recorded player states of the player it has to mimic, select the closest one available... and then use the action dictionary as probability distribution to decide what to do.

For example, if the counter says that the player in that recorded state has attacked 20 times, and has healed 10 times and has run away 10 times, then the AI will add a weight of 20 to attack, 10 to healing and 10 to run away, that will result in the AI selecting between attack with a chance of 50%, healing with a chance of 25% and running away with a chance of 25%.

You will need to add the counters to get the total (20 + 10 + 10 = 40), use that to get the probabilities (20/40 = 50%, 10/40 = 25%, 10/40 = 25%), then use the accumulate values (50%, 50% + 25% = 75%, 75% + 25% = 100%) of that as stop marks to a uniform random number generators giving you a number from 0 to 1 (which should be available in your language). Depending on what range the result falls ([0, 0.5), [0.5, 0.75), [0.75, 1)) you choose the corresponding action.

Further reading: Darts, Dice, and Coins: Sampling from a Discrete Distribution.


Inspiration from Drivatars

The method I explain above is based on the talk "Drivatar and Machine Learning Racing Skills in the Forza Series" from nuclai15. In which it is explained that the Drivatar (that mimic real players in games of other players) use a frequency map of the tracks, so the AI will know for each part of the tracks where the player has been how often the player passes over there and how fast. The AI also records other actions such as bumping into other cars which helps to reflect aggressive players.

That will provide information on (for example) what type of curves the player will take on the inner side and what type of curves will take on the outer side, it may also provide information on what parts of the track the player will accelerate, etc...

When the Drivatar needs to play on a track where the player it mimics has not played, it will look for tracks with similar features and use those to model the behavior.


Harmonic Mean

Another interesting thing about Drivatar is that they will give more weight to recent behavior. This allows the Drivatar to improve as their player counterparts improve... it also means that when the player has had a bad performance, it is reflected in the Drivatar.

You may accomplish that by changing the information stored in the dictionaries and how the weights are computed... To do that, you could use the harmonic mean of the time since the action happened it will naturally give more weight to more recent actions (instead of what I suggested above).

In that case you will not store the number of times the action is performed but instead store what action was performed when... although it will mean to store more data and require more computing power to compute the weights.

To alleviate that you can: 1) remove old actions from the record as they will have low weight anyway (perhaps a data structure organized by chunks of time will ease this process) and 2) pre-compute the weights on the client on a natural exit points (e.g.: when the player saves, when a match completes, when the player goes to the peaceful part of the map, etc..) instead of doing it just in time.

In this scenario you would then go over the list of timestamp for each action. For each timestamp subtract it from last time the player was seen. Convert the result to standard units (e.g. seconds). Compute the inverse. Add all the results together (that is the summation of all the inverse values). And finally take the inverse of the summation, and use that as weight... you would then proceed to get the total, accumulate and use the random number generator in the same fashion as described before.


Further Research

Since we want elements that were added long ago to fade away, and since we will be using random anyway, and since we will never get a perfect imitation of a player... We may as well use probabilistic data structures to store the actions such as Bloom filters, Count-min sketch and HyperLogLog.

\$\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.