I'm developing a turn based RPG game where combat is semi-tactical. Each combatant has a selection of moves available to them, which do a range of things from damaging their opponent to buffing their own stats or activating special abilities (like shields, healing, etc). So the problem I'm trying to find a solution for is, what's the best way to evaluate the moves and make the right decision for the right moment? At the moment, my only real thought is to score each move based on things like damage potential, chance of success, how much failure would leave the combatant vulnerable to retaliation, etc. The only problem here is that the AI would then choose the same few moves over and over. I thought about adding in some random points to the scoring system, but then it wouldn't be much better than randomly choosing the moves. Can anyone think of a good system that would both choose the right move for the right situation, but also not choose the same omves over and over?

hmmmm depends how many options there are each move google min-max algorithm for one posibility but if there are lots of options each move this will be to slow

This is a problem frequently encountered with move-based AI. The optimal choice one turn is often the optimal turn for the next few. Even worse, certain spells/techniques will be permanently rendered usesless with the aquisition of new ones as the valuation algorithm deems it universally, if slightly, less effective.

Your first aim should be to design the RPG so that the optimal move is never the same twice in a row, and so that the player (and the enemy) is rewarded for using a broad subset of their available move vocabulary per battle. This way, not only will your AI be less one-dimensional, but the player won't get bored so quickly, having to use the 'best' move over and over.

But sometimes even if this is done, the outcome still isn't random enough - successive battles will often result in the same sequence of moves. So what you could do to make the AI less predictable is, each turn, compile a list of avalable moves with their associated value (from whatever valuation you are using). From this list, eliminate the unproductive moves, say those with a value less than 70% of the best move, then choose from what's left, perhaps using the normalised value as a probability weighting. This would prevent the AI from doing something totally stupid (if the AI's health is full, it won't try to cure itself) but do something more useful; most likely, but not necessairly, the best move.
You're then free to tweak the weighting distribution and the threshold to trade off between unpredictability and optimality.

Regards
Admiral

The min-max algo sounds very similar to the scoring system I already have planned out. The problem still remains that the AI will likely then only choose from a small number of moves, ignoring other possibilites.

The game at the moment has three types of move available (with 3-5 moves in each category) and these are attack, defence, spells. Attack moves are the damage dealing moves, defence moves boost the combatants stats so they can better withstand attacks and spells are a whole variety of stuff.

I'm leaning towards simplifying it. Instead of trying to evaluate each move, I might make it so the AI decides if it should be attacking, defending or buffing itself. From there, a potential moves list could be randomly chosen from, without sacrificing the decision making.

edit: posted this as TheAdmiral was posting his :)

The idea of normalizing/weighting the good moves and discarding the bad ones sounds like it might just work. Especially if I combine it with the idea of simplifying the first step in the deicision making.

The game is already designed to prevent repetition in that each move, once used, is unavailable for a few turns after that, forcing players/the AI to at least use a small number of moves. The more powerful the move, the longer it is out of use for. The only thing that worried me would be the AI choosing the same few moves over and over, but with Admiral's weighting idea, I can hopefully tweak the AI to not seem so predictable.

Minimax usually involes searching more than 1 move ahead... for this type of game I don't think that would give much benefit.

What minimax is about is trying every possible move, then considering each possible move (all of them) that can be made in return, and so on until the AI runs out of time or reaches a certain limit. Then evaluates the position... who's got the most health etc.. and see which path results in the best position.

For Chess this is effective. For your type of game I don't think it will give much of an intelligence boost relative to programming time.

TheAdmiral made a very good suggestion. Adapting slightly one of the benefits of minimax (predicting your opponent) might also be of benifit. Maybe consider what move the opponent might make in regards to your move (eg if a beserk attack reduces your defence for a while, which makes a x% threshold chance the opponent will single-hit you, then reduce its score). Combining this with his suggestion should create a good opponent.

Good luck!

Damocles, is the AI right in only choosing a handful of moves?

Ie, is the AI's best chance of success (beating the player) based off of "blast the player before the player can react" or "buff myself to the point where the player can't hurt me"?

Next, do you want the AI to play optimally? In my opinion, you want the AI to present a puzzle to the player.

You could do something as simple as a two-layer RPS game.

Top layer:
Buff
Attack
Defend

Depending on what your opponent does, one of the above moves is optimal.

If the opponent attacks, defending beats it.
If the opponent defends, buffing beats it.
If the opponent buffs, attacking beats it.

If both sides do the same move, they tie.

On the second layer, have multiple "flavours" of move. Let's call them
Life/Fire/Water for the sake of having some names to grab on to.

Fire beats Life beats Water beats Fire

If you attack with Fire and he defends with Life, you lose the top level game and win the secondary game. So some damage gets through. You still burn resources to attack.

If you attack with Fire and he defends with Water, you lose the top level game and lose the secondary game. Not only do you not do damage, the opponent damages you with a counter attack! You also burn resources to attack.

...

Now that you have this double-structure, there are 9 moves that you can choose from.

Attack Fire
Attack Life
Attack Water
Defend Fire
Defend Life
Defend Water
Buff Fire
Buff Life
Buff Water

Now, the enemies can have a restricted set of the above moves -- which allows players to learn weakenesses -- and AIs that are not always optimal. Different monsters can have different AIs, and players can learn how to defeat them.

(Orcs are dumb -- if you attack one turn, they will defend the next turn 70% of the time. So attack them, get them to defend, and then buff yourself while they waste their move.)

A creature's AI would consist of a function that maps the battle state (how many HP/buffs/mana each side has) and past move choices for both sides into a distribution of move choices. A predictable AI would gimp the AI, simply because the other player could beat him.

On top of that double Rock Paper Sissors game, you can have spells that do different things, and some people won't have a strong "Fire Attack" but will have a strong "Water" and "Life" attacks. All of these things add to the complexity of deciding what to do.


Note that if a player gets enough "buffs" off in a row (and aren't disrupted by their opponents attacks), their attacks will penetrate their opponent's defences -- and if a player manages to turtle against opponents chain-attacks effectively, the waste of resources that the other is engaged in should allow them to beat their opponent.

Ie -- a fight in which you buff/defend for the first 3 minutes, but constantly outsmart the opponent, should result in you building up enough of a power advantage that when you finally start attacking, the opponent's defend's won't be strong enough to prevent their defeat.

...

Write the game so that the AI being predictable cripples the AI, then make some AIs that have flaws and others that are damn good.

Thanks for the replies. The system I currently have in place works on two fronts:

To start with, a high level decision is made between Attack, Defend and Buff. These decisions are based on a weighted random distribution, allowing for some unpredictability, but generally sticking to the themes given (ie. stupid characters attack a lot and almost never buff). In addition, active effects that alter attributes are used to alter the weights, so you don't get silly decisions like a blinded character trying to fight.

The second phase is to create a list of potential moves from that high level category, and each individual move is scored based on a series of checks. Each move has it's own base score to represent the best standard option, then on top of that it adds in how much damage can be inflicted/how much buffing or healing can be gained, chances of success, consequences of failure, resource costs to make the move. Then the highest scored move gets chosen. This way, as the caharcter loses health, the score for a healing move increases. If the character's attributes are lessened by an enemy attack, moves that rely on those attributes lose score. This keeps combat more fluid and less predictable. The player can't rely on hitting the AI with some weakening effect, then abusing his weakended stats. The AI should react and either attempt to buff those stats back up or defend the areas that are vulnerable.

The sad thing is that even though all this goes on under the hood, when playing the game the AI tends to either feel very random or very predictable. Still, it's better than a purely random move selection.

You have scored several sub-moves. Rather than always picking the one with the highest score, have you considered picking from all the moves evaluated, but with a probability proportional to the score? That would favour the best move, but if you had two options that were close, it would be more like 50/50 between the two. This might make your AI feel less predictable for the player.

Oops, I forgot to mention that part of the scoring code :) Each move does have a small random factor - the scores are increased by a small random chance value which equates to about 25% adjustments. So two similarly scoring moves will be chosen on a roughly 50/50 basis, but if one move is more than 25% higher than its nearest competitor, it will almost always be chosen. This way, the big hitter moves do get chosen a lot, but because each move becomes out of action for a few turns after use, and each character only has one or two power moves, the combat remains varied.

human players use certain paterns of moves?
these patterns could be pre-recorded and then tokenised to allow a random variation of moves chosen, for example
TOKEN_DISABLE
could mean a sleep spell, or a spell to blind the player etc. anything which disables the player. A grass monster might have more than one disable move, and could choose randomly perhaps with one of the algorytms you guys have described above.
each set of tokens can represent a strategy which the character follows, in the same way a a human player would. TOKEN_ATTACK could mean any kind of attack, or something more specific such as TOKEN_FIRE_ATTACK might be involved.
each stragety can have a trigger, or if no triggers have occured the AI can simply attack the player or do something randomly.