3
\$\begingroup\$

I'm working on a rpg, the battle system. I want to compare different scenario with each other.

For example, what if I play move A then move B ? or two times move A ? or ...?

I'm using a tree-structure to generate all possible scenario that can happen during the battle. There is no movement involved, I'm using a battle-system as in FF7, only skill choice matters. 4vs4 units

Trick is, the battle is turn based but not static. There is an Action Point bar for each unit (filling at different speed based on the unit's stats) and the unit with the most Ap (only if > 100) can play. If no unit is > 100, a "turn" will happend and all unit will gain some AP based on their speed. If no unit can play, a new turn will happen...until a unit is > 100 ap.

Each skills takes a different amount a AP to use. At turns 0 for example, we may have a unit with 140 AP that will play two times in a row for 2 actions of 20 AP each. Then other units at 100 AP may play.

It means that when I'm running a simulation of all possible outcome of a battle for my AI, I will have states (node in the tree), that will have a number a turns very different from other and from nodes at the same depth.

I dont know how to compare these nodes at all.

I was using Hp at first, but it is not enought. To prove it, consider the example: 1 vs 1 match. Unit A (opponent of AI) has only 1 move, a small attack that requieres 20 ap. Unit B (AI) has two moves : a small attack that takes 40 ap (and overall hit for very low damage compared to the opponent attack) and a second move that does nothing but consume 20 ap and that move can only be used during the 1st turn.

I will then have to compare two states :

•State 1 : AI use its attack . Opponent his attack. Units are at 60/80 ap respectively. 20 game turns passes and they are now at 80/100 ap. Opponent use his attack. 20 game turs passes and they are at 100/100 again and we are at turn 40.

•State 2 : AI use his move that does nothing. Opponent his attack. Units are at 80/80 ap. 20 games turns passes, they are now at 100/100 and we are at turns 20.

If I compare only HP, In state 1, AI will have an overall score a lower than in state 2 since it got attacked twice in state 1 and 1 times only in state 2.

If I only compare by Hp difference between AI & its opponenent, I would choose state 2 since AI lost less Hp than in state 1.

Running the simulation after state 1 and 2 will continue to show the same difference since after that point, both unit can only use one attack.

In the end, it makes my AI choose a stupid move because she thinks she is less likely to loose selecting it. Granted both move will eventually result in the defeat of the AI since its main attack is weak but I'd like my AI to nonetheless select as its first move, her attack skill and not a skill that does nothing.

I've tried weithing the overall gradient of score between the root state and the state I'm simulating by the number of turns but it does not work in all cases (it greatly depends on the number of turns and the difference between the root).

I was thinking of adding Ap ratio to my evaluation of states but in that example, we can see that in State 1 & 2, units are at the same AP anyway so it doesnt provide extra informations.

Anyone got ideas on how to compares my states from different turns ?

\$\endgroup\$
1
\$\begingroup\$

First, don't look at the absoulte damage numbers, look at the percent of HP. When a combatant lost half of their HP, they are halfway defeated. It doesn't matter if those 50% are 10 HP or 10,000 HP.

Let's take your examples again but look at how much damage is inflicted as percentage of HP. Let's assume that after accounting for all game mechanics, the two attack options by the AI are expected to do 0% and 20% damage to the opponent respectively, and the opponent attack does 30% damage.

In the first example, the opponent lost 20% and the AI lost 60%.

In the second example, the opponent lost 0% and the AI lost 30%.

So how could we rate these?

Approach A: cost-benefit analysis.

A good approach would be to do a cost-benefit analysis where we treat the damage% inflicted as benefit and the damage% received as cost. To turn this into a profitability score, we simply divide benefit by cost.

20 benefit for 60 cost is a score of 0.33. 0 benefit for 30 cost is a score of 0. The AI should take the first course of action.

Approach B: extrapolation

Another approach is to extrapolate: "If this combat goes on like this: how will it end?". Even without simulating the details, we can estimate how many repetitions of this course of action we will survive by dividing our own HP loss by our initial HP. When we multiply this with the damage% inflicted, we know how much HP we inflicted when this is over. In the first case, we take 100% / 60% to find out that we can repeat this course of action 1.67 times before we die. We multiply this with the amount of damage we dealt (20%), and find that the enemy will have lost 33% HP when the combat is over. In the second example we have (100% / 30%) * 0%) and find out that the enemy will have lost 0% HP. Again, the first course of action is better.

By the way: When you look at the math, you will see that both approaches are actually equivalent.

\$\endgroup\$
  • \$\begingroup\$ Sorry if this was not clear :/ I'm already using percentage of HP and not flat values. My evaluation function do something very similar, taking into account both percentages. The thing is that, when the simulation is run, it will check what happens after the first turn (for good reasons). And the more in-depth you will in my example, the less relevant the initial move becomes and the more chances I got that my AI select the initial "wrong" move because it lacks a proper way a comparing states at a different turn. \$\endgroup\$ – mydi Oct 23 '15 at 13:15
  • \$\begingroup\$ @mydi Why do you look at the rating of the first node in the decision tree at all? You should only compare the leaf-nodes of the decision tree because it's the end result that counts (unless you want to do alpha-beta pruning to sort out obviously bad branches early as a performance optimization) \$\endgroup\$ – Philipp Oct 23 '15 at 15:06
  • \$\begingroup\$ When my tree is done, I use the value of my first set of nodes because the MCTS alogrithm works that way, you kind of bubble up a win chance for each node with it. But looking only at leaves and taking the MAX would give the same result. The big issue is that in a loosing game, the more depth I search, the worse the situation is looking, thus my AI is trying to delay its own death. I also tried using a gradient approach like you mention (dmg/cost).It fails on my test case. \$\endgroup\$ – mydi Oct 23 '15 at 16:39
  • \$\begingroup\$ @mydi The AI trying to delay its own death seems like quite logical behavior when in a hopeless fight, and in a common RPG most fights will be hopeless for the AI. When you want the AI to be entertaining, you could instead make it optimize for maximum damage to the player while ignoring the damage it takes itself. \$\endgroup\$ – Philipp Oct 23 '15 at 16:52
  • \$\begingroup\$ If the AI prolonging it's survival is bad behavior, maybe take the AI's HP out of the equation entirely? My guess would that the AI should consider any state where the player's HP is lower to be a superior state. Simple as that. \$\endgroup\$ – tandersen Oct 23 '15 at 18:13
0
\$\begingroup\$

tl:dr; Read the first and very last paragraph

With this approach, your AI will likely attempt to always use the optimal strategy, but the way you code it can easily lead to abuse. So, when considering how to evaluate "the best state for the AI" keep these examples in mind:

Example 1: (the problem you currently see)

Player team is full of extremely high DPS classes. The AI evaluates that it is impossible to kill the player team so it only uses defensive skills in order to stay alive as long as possible.

Solution: Either take into account future encounters if you already know what they will be (that will be harsh on the player btw), or change your evaluation of the game states. (Covered in the bottom section)

Example 2: (The scapegoat)

Healers tend to be the weakest member of a traditional RPG. If enemies always select the target who they can do the most damage too, the healer may always be targeted. To counter this, one other character in particular is kept soft and vulnerable in comparison to the others, and only provides utility to the rest of the team. The AI always targets this character because it does the most damage to it. The player can plan on this and since he can just heal the soft character after the fight, the player doesn't really care about that character getting hurt because they serve no vital function to the team.

Solution: Use some randomness, or evaluate the "threat" of given members of the party. Threat is hard to evaluate - but MMO's such as WoW can serve as at least one example - where damage and healing amount can cause a lot of threat, and tanks have to spend skills raising their threat or taunting in addition to their (lower) damage. Many combat systems similar to yours use a weighted randomness depending on the person's position in the party (front vs. back)

Example 3: (The Boss who always uses the "Ultimate Move")

Bosses, and even some lower minions, tend to have one move that outshines the others for the AP cost. If the AI is always using the most optimal move - it may seem as if all the monsters in the game only have one skill!

Solution: Allow for some deviance from the "optimal strategy", or put some kind of restraints on the AI not to use certain moves more than x-times out of y-times.

Example 4: (Toying with the player)

The reverse situation than you are seeing now, might be if the AI has essentially defeated the player, but stalls the battle in order to fully heal itself. In both end cases, the player is dead, but in one the AI has full health, that makes it clearly the better choice, right?

Solution: Make time the secondary factor when evaluating two end states where the player is dead, and ignore factors such as the AI's health in that circumstance.


As just these 4 examples show, always choosing the optimal strategy for the AI is difficult, time-consuming(CPU-wise), and generally results in either unintentional player behavior or unfun/frustrating AI behavior. This is why many times RPG games simply use weighted-randomness or specific skill patterns to decide the AI behavior.

But... To finally get to your actual issue at hand,

Do not compare the state of the game at different game turns. You could solve it in either direction: either compare at turn 20, in which case your AI sees that it was attacked once and did damage with his skill vs. did no damage, or compare at turn 40, where it sees that it could accomplish more than one thing (in this case two worthless attacks) vs. one major attack (where the major attack does more damage) - but the fact it was attacked twice shouldn't matter because it's the same in either case. The second is more difficult but is more flexible and can lead to better AI strategy.

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