I honestly think you won't be satisfied with any solution, because you are trying to solve an impossible problem. Or at least you are portraying the situation that way to us. You cannot quickly simulate the game, or even an approximation to the game, so MCTS is out, and so is anything that requires search; You can't use a neural net or any other machine-learning technique because the rules will continue to change forever and you can't afford to retrain the system (although a simple neural net can be trained in minutes or hours).

I think by now you have a pretty good idea of what your options are. From what you describe, I feel I could personally make MCTS, hand-crafted utility, or NNs to work. Of those, I think hand-crafted utility is your best candidate because it pretty much guarantees no performance problems and it allows for a lot of designer tweaking (so if you are not satisfied with what the AI did in a particular situation, you can debug the problem by dumping the utility for each alternative and you can then modify your utility function to better reflect what you want the AI to care about.

I honestly think you won't be satisfied with any solution, because you are trying to solve an impossible problem. Or at least you are portraying the situation that way to us. You cannot quickly simulate the game, or even an approximation to the game, so MCTS is out, and so is anything that requires search; You can't use a neural net or any other machine-learning technique because the rules will continue to change forever and you can't afford to retrain the system (although a simple neural net can be trained in minutes or hours).

I think by now you have a pretty good idea of what your options are. From what you describe, I feel I could personally make MCTS, hand-crafted utility, or NNs to work. Of those, I think hand-crafted utility is your best candidate because it pretty much guarantees no performance problems and it allows for a lot of designer tweaking (so if you are not satisfied with what the AI did in a particular situation, you can debug the problem by dumping the utility for each alternative and you can then modify your utility function to better reflect what you want the AI to care about.

I've spent a few more hours yesterday trying to debug all I had done so far and realized and there were many flaws I had not spotted before. My evaluation function is so complex and convoluted that I'm havng trouble debugging it, it's becoming more and more like a giant blackbox :/ The issue is that my battle system is complex and trying to evaluate a given situation with precision is a real chore.

I've got also an issue that I understimated but that is starting to prove itself more important than I thought: My game is turn-based but not Player A then B then A then B ect... There is an Action Point metrics in place AND a "turn" variable in battle. The unit with the most AP can play and if no unit has > 100 AP, then a game turn is done (adding AP to everyone based on their speed, updating cooldown, buff effect etc...). In the end, multiple units can play during the same turn. A single unit can play multiple time during the same turn. Actons have different AP cost, so the next time (turn) the unit will play will be based on that cost.

In the end, it means that I've got a tree who's depth is not really significant of how far in the game I am. I was thinking of using the number of turns of each node but the main issue is that if my tree branches doesnt end on the same turn exactly, I won't be comparing the same thing if I compare leaves between each other. I don't have an easy way to say : hey this is turn 28 and this is turn 30, let's compare the value anyway using X aproximation.

So i guess you are right, I'm starting to feel the limitation of each solutions. I'm going to dial back a little and try to use a good old fashion pen & paper to write down every thing I need from my AI and see if I can find a solution that manages to solve most of the behavior I want to it to exibit.

For example: a question that is on my mind, is how a human think about his ressource management (mainly mana). If I've got a spell that works as an execute ( < 20% target hp), I know as a player that it is often wise to keep enought mana to be able to cast it. I haven't found an elegant solution w/o giving the system extra knowledge of the spell to have a behavior like that.

The utility based approach seems nice for behavior decision (move, talk, shoot, find ammo, etc...) but I don’t see it working well for my case where decisions all are based on the same motivation (kill or be killed) and the actions very similar to each other.

That's not entirely true. In either case, you have multiple actions that you can take. In some of the examples in my lectures, there were simply many types of actions. You have many types of actions as well -- they are just more focused on combat. The bottom line is that you want to figure out what the best action to do at that time are... it doesn't matter what the type of action is.

What bothers me more is that it seems the utility based AI you propose could reason with a task priority in mind but doesn't plan ahead. It would not be able to set-up "combo" of skills in contrary to a MiniMax (or MCTS) that would eventually discover it without the need to give our AI extra knowledge about the game. For example: casting a debuff that lower fire resistance then casting a fire spell. A tree based AI would test both cases and see that it's better to cast the debuff, then the fireball. It could probably be added to the utlity based AI as a consideration to the fireball but
To be efficient that means a ***load of considerations for my skills that are basically already used and in place when I simulate a new move since my battle routine takes the fire resistance into consideration when applying damage
The fire debuff skill would still be hard to score unless, again, we add lots of “considerations” like : how many fire offensive spells do me and my allies got, what are these spell efficiency, do they require me to lower the fire res to be effective, etc. Again, it seems very redundant with my current Evalution() function that can already assess this pretty well, using simulations of every units skill on every possible target.

You are correct that it doesn't do any sort of "planning". It is simply a single ply reactive system just like most of the other AI architectures out there (other than GOAP or HTN which are, by definition, planners). However, even MCTS is not a planner, per se. It is only scoring the fact that if you WERE to continue down this branch later you would get these benefits. That's really no different than the other architectures (mine included) where you are going to be reevaluating the next time around anyway. Either way, you are coming up with a way of determining that doing A is a good idea because you could follow up with B -- which is preferable to doing B without A (or B then A). All of this can be codified quite easily through the addition of 1 or more considerations in my IAUS architecture.

I agree, i could use either my evaluation function or a utility based measure and still build-up a tree. The thing that worries me about considerations is that there would be so many to add. The fireball/debuff was an example but even for that situation, there would be so many things for the AI to consider (mainly due to the complexity of the battle system and that for a single spell cast, there is lots of variable interacting (hp,mp, resistances,... probably more than 50-100 for each spell cast)

A small update for those interested:

I've taken a step back and watch a few videos / dozens of power-point and articles about the field of AI algorithm that could help me build a nice AI for my game. yeah moar knowledge !

Just to know what kind of computation I could do, I benchmarked a few on my game engine functions:

- Creating a new gameState (copy of main one, used by the game engine) : 1 ms

- Loading a given gameState (into the main one, used by the game engine): 5 ms

- My current custom evaluation function (rather complex) : 1 ms

- Computing a game's turn : 1 ms

A battle may last between 1 & an infiny number of turns. An average battle is excepted to last a few hundreds of turns (too early in developpement/balance to be more accurate here). That means something like 0.5 second currently to fully simulate a battle playout using random move selection.

I took a look at planners (STRIPS, HTN) [not in-depth yet], but that does'nt seems like a good fit for my problem, so i didn't looked too closely.

I also looked at FSM / HFSM but defining all the logic manually seems like a big no-no and it seems like a pain to manage.

I took a look at behavior trees. I like the concept but I don't see it working for me. Not 100% sure yet on this, I'll probably use a couple of hours in the next days to draft something on paper and see if there is something to salvage here ;o

NNs are an option to build a fancy evaluation function (with the huge draw back of ~days of computations to train it each time I change my game content). And as it is for me only an evaluation function that would allow me to find one move w/o taking into consideration the future.... not great untill I can find a proper solution to include them in.

I went back to MCTS and despite huge worries about what I can get from it du to my poor game engine performance, I like the algorithm general idea. I've got some questions I havent yet found an answer to:

- how many iterations are requiered to find a decent solution (a rought estimation would help me to see if I've got any chance of making it work or no ^^)? (maybe related to depth ?.)

- Could I, after each real turn, keep the same tree generated during the AI of the previous turn but by considering the current node of the move just played as the new root. It would allow me to keep the work done by my AI since the begining of the battle and potentially be a lot more efficient. [that would requiere me to have a perfect determinist value of all states -> use the same random() seed for simulation / real move execution, but hey, for now that will do]

I also realized that the deeper I am in my search, the simpler my evaluation function can be. At depth 1, I need to process a huge amount of information do know how good the position is but lets say, at depth 30, I can start to only look at a few variables (HP mostly) and deduce where the battle is going. It may be way less accurate thatn a full evaluation function but also a few orders of magnitude faster so that's a possibility to keep in mind.

I also need to take into consideration that loading a game state for me is a really slow operation. it means that search in depth will perfom miles better than in width (since in width, i've got to load the parrent state before each child generation or else i'd still be in the newly computed child's state).

Well, that's it for now :) I'll keep digging ! I'll take any idea / tips / article you have (provided it's not too heavy on math ;o)

BTW, meant to mention this earlier, but if you think you need 50-100 input calculations per spell in a utility-based environment, you are doing something seriously wrong. I could give you killer AI in nothing more than about 20 and in many cases 10-15.

I may be missing something then :) My current evaluation function is the closest thing I've got that is an utility AI and it basically uses every character's stats to work out an action's score (got around 100 stats at the moment for each unit and this is expected to grow a bit). To be somewhat meaningful, this evaluation function compute the average output of every skill effect(damage/heal/buff/debuff) that the unit has. It uses that to compute a few threat indicator and an rough EHP value based on what each opponent is capable of ouputing as dps.

These computations requieres all of the 100 stat variable of each unit in the battle field. In the end, my system produce 3 utility functions for each unit ( 2 threat + 1 EHP metrics ). So I can see having only a few utility function but they would still need to reference all these variable to work, does'nt it ?

If you have something as accurate and simpler, could you give me an example of what you mean :) ?

Thanks. I'll be away for 3 days, no internet but a nice pen & paper to find new ideas !

(got around 100 stats at the moment for each unit and this is expected to grow a bit)

Dude... no...

I must confess, I don't know what you are implying there :)

I can see a few things :

1) You are alarmed by the number of stats that characters in my game have, in the game design perspective of things.

2) You think this will make my AI computation just impossible because of too slow ? (or that I should get a simpler model for AI)

If it's neither of these, can you elaborate on what you means?

If it's 1 :

I'll agree that a big number of stats isn't necessary to have a complex / engaging battle system. However, my game is like a battle/strategy simulationand these stats do bring depth to what the player control and can tweak. They are all explained in détails in the character's sheet and are all suposed to be meaningfull (to a degree). Battle doesn't require player input as he defines it's group strategy before hand so there is no burden of having to remenber what stat does what in real time.

If it's 2 :

The number of stat doesn't add too much raw computation in the end but it starts to be painfull when I have to copy/ load entire battle-state. I do get away with that for now since I only copy buffs / debuffs on the characters and not their entire list of stats [buff/debuff are the only things that can make a stats change between two battle-state]. That beeing said, I'd love to have a simpler battle model I could use for my AI. It would solve two of my biggest issues : computing a game's turn is slow & saving/loading a state is slow too for now.

My next focus will likely be to try and optimize my game engine and then try to use MCTS to see if it can give any decent results despite my slow-ass engine ;o)

Keep the 100 stats, but find a way to present them to the player, either in a grouping or hierarchy that gives him a simplified overview.

Yeah... too many stats. Read some material on psychology of choice. Once you have more than 10 or 20, people shut down on processing them all. Additionally, there is no way that you will ever be able to balance that adequately from a game design standpoint.

Start much smaller and then gradually ramp it back up if you can handle it from both a design and logistic standpoint.

Keep the 100 stats, but find a way to present them to the player, either in a grouping or hierarchy that gives him a simplified overview.

For now, I'm not worried about the negativ speed impact my unit's stats have on my AI. Regarding their usefulness / presentation to the player, I've already started to make a small hierrarchy to display them cleanly to the player :) But that is something I'll take a hard pass way later on in my dev cycle.

That beeing said, It is entierly possible that I'll revamp my stat system later on if testing shows that some stats are too "obscur" or just don't seems significtant / or don't represent intereseint gameplay choice.

I want my AI to work independently of that mostly : meaning that I want it to work with a 10 stat system or a 100 stat system regardless.

It is worth noting that the 100 number is "inflated" by the fact that I got 6 element in the game ( fire,ice,light...) and that some stats like resistance, mastery, resistance penetration (flat), resistance penetration (%) are declined in 6 differents stat each time (one by element). Wheter or not it's a good idea is mostly a game design question and for now i'd like to focus on the A.I sides of things :)