Hello everyone

 

I am here to gather your opinion, remarks, ideas or any constructive criticism you may have about what I am going to present. Don’t be shy!

 

A bit of background:

I am working alone on an indy web-based game, a simulation of RPG (idle game) where the player controls a group of 4 characters that he can sent into battle and that will fight automatically based on some AI preference that are similar to the FF 12 system (but more complex / powerful). He then earns some experience and resources that he can use to improve his unit’s gear, talents and skills. He has a lot of control on what skills his characters will use and how/when.

 

What brings me here today:

The AI of Monsters. I have the AI settings for players covered (basically a bunch of if/then/and/or/else settings that he can combine and order so that his units will act as he intends in battle). I’ve been working on the AI of monsters for quite some time, made a long break and came back recently to it.

 

Short description of the battle system:

No movement involved. Battle is fully automated. Players setup its units AI settings before battle and monsters are controlled by a separate AI. This is a 4v4 battle, like FF7 with some kind of ATB and any time a unit fill its ATB, it can play and the then the next unit who will fill it will play, etc. The player is completely free of his playstyle and may create very offensive group or very defensive ones. 4 healers or 4 tanks is completely possible.

The battle system is very complex and allows for very varied and sometimes unusual strategies, like killing your own allies to proc an “on death buff” that will be devastating for the opponent.

 

What I want for my AI?

It needs to be fun to fight against and challenging. Ideally, I would like an AI as smart as possible (not omniscient but thinking as a human would). I know that a super-smart AI is not always the best way to make a game fun or challenging but in the context of my game, this is the result I want to achieve. It may seem unfair to have the AI try to kill your squishy while your tank is standing right there but my class design gives the tools to players to counter that so it’s not an issue (tanks are not purely aggro based for example). I want players to always be challenged by AI moves and that they must carefully think about their strategy because if they leave a big hole in it, I want the AI to exploit it.

In practice, it means a few requirements:

• No dumb decision / do not fall into obvious player’s traps
• Exploit obvious flaws of the opponent
• Act in coordination when appropriate with other units
• Able to find who should be their focus in the player’s team (some notion of threat)
• Find the best move to use and if there is some kind of combo possible, use it

These requirements are harder to meet than it looks. The issue is the sheer number of different mechanisms and strategies available to players and to monsters as well. For example, there are many cases where killing or attacking a player unit might be detrimental (units that return damages or that gain power when you hit then for example).

 

What I have tried before?

I have tried or at least reviewed many different AI concepts so far.

-          A simple copy of my player’s AI system (hierarchical if/then/else). It was easy to script as I already have the UI in place for players so I can quickly define a basic AI for any new monster’s group. The main drawbacks are that it needs to be written for every monster group, it does not allow smart targeting and cannot find the best target or the best skill to use. It will also make dumbs decision as the targeting options cannot assess threats at all.

•           I’ve rules out planners since for purely selecting the best pair of (skill, target), they do not seem to match my needs.
•           (H)FSM or BT does not seems to match my needs as monsters do not have states / transition condition that can lead to something useful for me.
•        I’ve ruled out aNNs as they might, with proper training, be able to find the best action at a given time but it’s very tedious to implement and will not solve my need of finding combo or coordinating with other units very well. (plus, let’s be honest, I’d be a bit out of my depth to program them)
•           I have spent an extensive period of time trying with tree searches. Mainly: monte-carlo with random sampling and came to the conclusion that due to the complexity of my battle system, it is excessively costly to compute any kind of reliable data this way.

-        My current AI system is a version of my first one (the same as the players) but with access to some “smarter” targeting function that in theory allow to choose the best target. These functions work by gathering data for thousands of simulated fights during the AI time to play (1 second). It’s a first step to find the best target but not very accurate (lots of big flaws that can be exploited by players) and it is very time consuming and that is something I’m trying to get away from. I do not want to use 100% of the players CPU as I do now.

 

What is my latest idea?

I started to study more in-depth the Utility theory as described by Dave Marks (I read his book and watched his GDC AI lectures as well). I liked the idea. I like that I can start on something relatively simple and add more considerations as things progress to handle more and more situations. While my work began as something very close to utility theory, it evolved a bit afterward. Here is what I plan on doing to compute a unit’s best course of action:

 

A – Score every of its move (each move is a pair [skill, target]).

B – Chose the move according to a selection strategy (highest score, weighted random, random amongst the top scores… lots of different selection algorithm can be used there).

 

So far, easy, right? Let’s dig deeper into our first phase of scoring (A), which is the hard part. For all the damage or healing skills:

Step 1: The final scoring of the move [skill,target] will be function of the a “Survival” scoring for the player team and for the enemy team. An example of this relationship could be: Adding all the survival scores of each unit in Team A and divide the result by the addition of all the survival scores for each unit in team B.

Step 2: The survival score of each unit will be its Health after the move we are evaluating, divided by the total damage per turn that we estimate other units can deal to her (minus the total heal it ca receive). [This a step where we can process damage and heal over time as well]

Step 3: This damage per turn estimation will be, initially, the sum for every unit in battle of the damage or heal per second it can deal to that unit. For example: If I’m alone vs 2 bad guy that can deal 1 dmg/turn and if I can deal 1 heal/turn, the damage per turn estimation against me will be 2-1 = 1. [This is not optimal since we are counting the damage of each unit once per enemy unit but it’s a start]

Step 4: To compute the DPS or HPS of each unit, we review the unit’s skills and compute their output against the unit we want to evaluate it against. From that, we construct a skill sequence to maximize the damage output and once we got the optimal skill sequence, we can compute its DPS or HPS output and pass it along for Step 3.

 

It might seem like a lot of work, since, in a world with only damage or healing skills, the DPS or HPS sequence of each unit will be the same in every situation and as such only the damage done or healing done by the skill evaluated would be enough. But…

 

The tricky part comes from buffs and debuffs. If we use the above algorithm, (de)buffs that changes the damage or healing someone does or receive will be evaluated correctly as it will change the damage or heal per second output of units and it would affect the survival score and the final scoring. That is why I chose to include DPS and HPS computations for each unit for each move.

 

This is all fine until we consider (de)buffs that changes the power of other (de)buffs. Like: I cast a buff that double the length of all my future buffs. My algorithm can’t evaluate it correctly. It’s a situation that will be common enough in my game and I want my AI to deal with it. Note: there are more complex situations where a unit could buff a buff that buffs a buff that buff a buff [….] that will end-up buffing a damage or healing skills, but those cases will not be addressed as they will hopefully be rare and too cumbersome to compute anyway.

 

So, my goal is to score properly buffs that: 

•       Buffs the damage or healing output of someone
•           Buffs that buffs a skill that does the above

 

L    Long story short of how I am doing that. I’m using my initial algorithm but while also estimating damage or healing per second change for each dps or hps sequence.To do that I’m evaluating every move of the unit (or every unit in case of AoE but lets keep it simple with single target) that is targeted by the buff. So, we are switching PoV here compared to the initial unit we are evaluating (unless the move evaluated is buffing itself)

-          I’m doing the above in 2 situations:

o   A : After a cast of the buff skill I’m evaluating

o   B : Without the cast of the buff, just like if it was that unit’s turn to play

-          Using a sort of min/max approach: if the unit targeted by the buff is an ally, we will take the best branch of our tree in A and compare it with the same branch (pair [skill,target]) in B. If the unit targeted by the buff is an enemy, we want to lower their maximum score and will select the tree branch that does that in A to also compare it with the same branch in B.

-          The information we extract here are DPS or HPS delta for each sequence of DPS/HPS for each unit vs each other unit.

-          Then, we go back to our steps 1 to 5 and compute our scoring for the move (buff) while using our new dps/hps deltas to get better and more accurate dps/hps sequence for units affected by the buff.

 

This is basically it. I’ve ran a manual version of the algorithm in 2 different battle settings to test it and see if it gave good results. It worked. Not flawlessly but it worked. Lots of cases will still require tweak and additions to the basic idea but I think its promising. (taunts and CCs are not easy to deal with but it’s manageable)

 

What I like is that I can add more considerations later (as in the utility theory) like: resource cost, general unit strategy (cleave or focus), behavior (careful, lunatic, reckless). While this will still be a bit time consuming it should be a good order of magnitude faster than my current AI. It also does not prevent me from adding hardcoded AI move if I want to “script” more some monsters. Debugging and tweaking might be a bit painful though, especially when fights will involve lots of skills & stats but that’s an issue that most AI for my game would likely have anyway.

 

To come back with my initial goals:

•         No dumb decision / do not fall into obvious player’s traps

o   Not perfect but it should choose the best target whenever possible

   

•        Exploit obvious flaws of the opponent

o   Same as above

•         Act in coordination when appropriate with other units

o   This can be done simply by adding weight to some targets or computing moves for all units of a group before deciding which one to take (for example to take the best move vs a specific unit, on average)

•        Able to find who should be their focus in the player’s team (some notion of threat)

o   It will naturally focus the unit who is the easiest to kill and debuff or CC the ones that deal the more heal/damage. But, to better solve this, we will need to add other considerations to the AI scoring process, It should not be *too* hard    

•       Find the best move to use and if there is some kind of combo possible, use it

o   Combo are very often in the form of buff/debuff setup before an actual damaging or healing skills and my AI can compute up to a 3 moves combo (buff > buff > skill that dmg or heal) which should cover most cases.

 

I’m quite happy with my initial tests. I’m not going to be coding it now. My goal was to reflect on the subject on paper and try to see if designing my AI would be a roadblock or not for my project. There are a few other area I want to design and take time to really think about before getting back to my project full time. I’d love to hear your toughs and feedbacks about my AI ideas. Do you see huge roadblocks I’m missing? Does it sound ok to you?

If you read that far…. thank you and I can"t wait to hear from you guys?

I'm not an expert of this kind of game, but I'd expect the rules to be less flat than a simple race of dealing damage and healing damage. You mention a few "wrinkles" like action timers and a nasty bonus when a unit dies, and other plausible ones include defenses to avoid being hit and reduce damage, conditional bonuses (e.g. attack types vs. different targets), additional resource types (e.g. "magic points" that can be spent to use magic or drained away), restrictions to actions (e.g. stunning the opponent, throwing a heavy magnet to disable the opponent's steel sword),

This kind of tactical landscape requires planning, although in probabilistic form: playing well should involve setting up a good combination of defenses, buffs and adverse conditions for the opponent, and maintaining or developing it, before and between using the most damaging attacks (as opposed to starting with a good move and repeating it until victorious or bored).

You mention strategic principles that disguise planning (what is the situation going to be in the future?) as choosing actions smartly (what should I do right now?): 

• coordinating units means planning the moves of all units in the team together, which is clearly strictly better than pretending other units are doing nothing
• looking for combos and exploiting flaws mean looking for a good final state when the combo is done or the flaw is exploited: not even special cases of pursuing an objective over the course of many moves.
• in the same vein, not falling into traps is only an extreme, obvious instance of not doing measurably bad moves
• focus on the right targets means that disabled and defeated enemies are a good thing: it should be implicit

I'd frame this AI as, more or less, minimax exploration of the game tree, very deep, with cheap heuristic or in many cases exact rules to exclude bad moves very aggressively, and cheap heuristic functions to evaluate states (total team hit points would be a good starting point).

Hello Lorenzo Gatti, thank you for your input

I've explored minmax tree explorations in depth ( bad pun intented ) and came to the conclusion that my game parameters were too complex to get anything usable from it. Even with a simple heuristic (HP), the cost of saving/loading game state was huge, the cost of computing actions was also too big, and the fact that we have 8 units on the battlefield and random elements everywhere (requiring chance node or similar approach)... all that makes for a tree search that even with many simplifications (that would lead to issue later on) were not going to work.

 

This is why I reverted to what I'm describing in my post. In the end, the idea is to plan a sequence of moves (skill + target) that will maximize the chance of victory. There is no movement at all, this is why I ruled planners out. Most examples I've seen of them where very hight level tactical based or movement based or both.

 

You are however correct that my proposed AI do not plan well at all. It should be decent to find the best move NOW and the best few moves to string together if necessary but planning for multiple moves (especially the ones from the player team ) is not included. It should however be enough to have some kind of simple coordination between the enemy untis as when they are evaluating a buff, they will select the best situation if it enables a better move or combo for their teamate. This is far from perfect but it's a start.

You might be overestimating the impact of random elements on simulation cost: in many cases like an attack dealing more or less damage you only need to follow the highest or lowest possible result because any other outcome is strictly better, without estimating averages or complete random distributions.

Quote

the cost of saving/loading game state was huge

Can you elaborate? What game state are you processing? Maybe some inappropriate rules increase simulation cost without adding significant gameplay value.

On 10/16/2019 at 4:01 PM, LorenzoGatti said:

You might be overestimating the impact of random elements on simulation cost: in many cases like an attack dealing more or less damage you only need to follow the highest or lowest possible result because any other outcome is strictly better, without estimating averages or complete random distributions.

Can you elaborate? What game state are you processing? Maybe some inappropriate rules increase simulation cost without adding significant gameplay value.

Using a min/max approach for random elements has its benefits but it seems to me that it will very quickly create game states that may be very far from what the reality is. There will be lots of "procs" in my battle system, so lots of "have X% chance to do Y". If a unit has multiple of these, like 20% to become immune to the next attack for example and if you treat this as either 0 or 100, the end result of the AI will be based on states that are too extreme to matter.

Anyway, even without taking the random element into consideration at all, a tree-search AI was going to be too slow for me.

To answer your question on cost: when simulating battles, i would use my "normal" game engine and load in memory the state I wanted to evaluate or take action on.[using short-cut computations was ruled out since it would, like for random element, very quickly create situations that were too far from reality]. When I've done my evaluation and/or created the next game state by simulating an action. I would save the state as a node of my tree and move on the next node to evaluate (depth-first was more efficient since I wouldn't need to load gamestate as frequently, I could just use the one in memory and process on more turn from it).

My issues where both in term of CPU and in term of memory (but more on CPU). I had two choices on what data to save. My goal was to be as fast to save/load and as fast to use as possible.

 - Saving very few variables (hp,mp,cd...) and the (de)buffs on units and then calling my function that recompute all the units stats (armor, resistance, dodge and so on) based on the buffs.

- Saving all the variable already computed (~100 per units) to avoid having to recompute them (while still saving buffs)

I tested both version and the first one was a bit slower than the second version (who has a larger memory inprint).

 

In both cases, saving/loading a game state and processing a turn (which involve lots of computations to see what damags is done, buffs update and so on), was too slow for me to compute enought nodes for a tree search to really give a decent result. I spent way too long trying to optimize my code to be faster and gaveup after realizing that I would need something at least 100 times faster (while keeping a good accuracy) than what I had to get decent result

 

Long story short : I'm not doing tree searches anymore and I'm trying to move to the utility-based idea i've written in my OP

It is a very interesting idea, I think you should go with the development. It should be very cool! 

17 hours ago, RCD2000 said:

It is a very interesting idea, I think you should go with the development. It should be very cool! 

Thank you My current goal is to assess if I can spot any major roadblock for the developement of the game and if not, to resume it at full speed (I'm even considering going part-time at my job for that) ... but before diving in, I need to be carefull and make sure I've got all my hot-topic covered ; one was AI.