Turn based RPG AI : how can I handle risk / reward ?

I have little experience here, but my first guess is to reduce the weight of second and further successes. If you continue after the first success/fail, you're planning with less certainty, so any success there should weigh less, since you may never get there.

This may mean that after a few win/losses, there is no point in continuing further look ahead, as the weight is too small.

Currently, you basically abort any fail, and only search win steps. I don't know whether "fail" means death (in which case aborting the search doesn't actually cut anything), but if you live after fail, you may want to consider a more balanced search between win/loose, but less deep (since win/loose further away doesn't mean much).

Minimax is not a reasonable choice for a game where actions have random outcomes. Try MCTS instead.

I’ve tried to find a “clean” solution to this but every ones I think about still has big flaws.
As my AI is kind of slow, I’d like to avoid adding a layer of complexity to it. I can compute things a bit differently but I cannot compute much more scenarios that it is already handling.

sounds like you're hitting the limits of complexity that your chosen AI implementation method can handle without undue work on your part.

it might be time to consider a different system.

Thanx you 3 for your inputs !

I have little experience here, but my first guess is to reduce the weight of second and further successes. If you continue after the first success/fail, you're planning with less certainty, so any success there should weigh less, since you may never get there.

This may mean that after a few win/losses, there is no point in continuing further look ahead, as the weight is too small.

Currently, you basically abort any fail, and only search win steps. I don't know whether "fail" means death (in which case aborting the search doesn't actually cut anything), but if you live after fail, you may want to consider a more balanced search between win/loose, but less deep (since win/loose further away doesn't mean much).

In my game a "fail" just means that a skill will miss its target, it doesn't mean the loss of the game, far from it :) I don't see how weigting nodes at a more depth would give me a different result, since, If i understodd correctly you would weigth for example all node at depth 2 at 95%, all nodes at depth 3 at 90%,all nodes at depth 4, 85%, etc... How does it affects the one an AI would choose?

I may have forgotten to add an information about this: my AI game tree is rebuilt from the new game state after each move. I don't build one at the begnining of a fight and stick with it, so if I compute moves at a big depth and they are innacurate (for now it is not the case), it will only affect the next move decision of the AI. After that, i'll rebuild a new tree.

Minimax is not a reasonable choice for a game where actions have random outcomes. Try MCTS instead.

I've read a bit more about it. If I'm not mistaken, it should generally lead to better performance than my MiniMax alpha/beta but it wont solve my current issues (unless it can expand so many nodes that I can separate my hit/miss scenario into two nodes each time... but since I got lots of random numbers: chance to hit, chance to crit, lots of proc chances (x% to stun, x% to silence etc...) it would mean a really high number of node to explore, even for MCTS.

The algorithm also seems to requiere, when choosing a node, to be able to expand it to a win or loose state. In my game, expanding nodes that way (even for one move) is really slow too I must simulate all the computations the game engine normally does when registering a new move (and there is a LOT going on). Since that is one the two things holding me back time-wise, I think it would be more efficient to store a new node with that information (as I do now) rather than trying to find an end-point and kind of wasting all the game states computed to get there, don't you think ?

There is also the issue that a fight in my game can end in a unpredictable number of moves, as low as one, but most likely a few hundreds and possibly never end in some cases (extreme case: two healer with infiny mana fighting each other ;o). I could use my current evaluation function after X playout and call it a probable win or a loss based on this but again, my eval function is slow and I can't halp to think that it would be a "waste" to use it and not store that information.

I may missing important things here but so far it doesn't seems like a fit for my game :/

I’ve tried to find a “clean” solution to this but every ones I think about still has big flaws.
As my AI is kind of slow, I’d like to avoid adding a layer of complexity to it. I can compute things a bit differently but I cannot compute much more scenarios that it is already handling.

sounds like you're hitting the limits of complexity that your chosen AI implementation method can handle without undue work on your part.

it might be time to consider a different system.

It is quite possible. I'm opened to any suggestion :)

MCTS as mentioned above, or just completely rework it into a hand-authored utility-based system. At that point, you use formulas to score each potential action based on how reasonable it is. That could include hit %, damage it will do, amount of "mana" remaining, how much health you have left (which might increase or decrease the priorities of different actions), etc. You come up with a single score for each action, then chose the one that scored the highest.

For more on utility-based systems, see my 2 AI Summit lectures here.

Also, this AI Summit lecture shows an architecture that we developed around utility that implements similar to what you might want.

I've read a bit more about it. If I'm not mistaken, it should generally lead to better performance than my MiniMax alpha/beta but it wont solve my current issues (unless it can expand so many nodes that I can separate my hit/miss scenario into two nodes each time... but since I got lots of random numbers: chance to hit, chance to crit, lots of proc chances (x% to stun, x% to silence etc...) it would mean a really high number of node to explore, even for MCTS.

The fact that there are lots of random events in your simulation shouldn't be a problem for MCTS. Perhaps the "Tree" part of MCTS would be difficult to use effectively, but Monte Carlo simulations could still be performed.

The algorithm also seems to requiere, when choosing a node, to be able to expand it to a win or loose state. In my game, expanding nodes that way (even for one move) is really slow too I must simulate all the computations the game engine normally does when registering a new move (and there is a LOT going on). Since that is one the two things holding me back time-wise, I think it would be more efficient to store a new node with that information (as I do now) rather than trying to find an end-point and kind of wasting all the game states computed to get there, don't you think ?

If your game is too slow to simulate, you could still use MCTS by simplifying the rules used in the MCTS. After all, my mental model of how the world works is a vast simplification of the actual Physics running the world, and yet I can make meaningful decisions in my day-to-day life based on my simple model. Your agents could do the same thing, and map the game to one that is simpler and much faster to simulate.

There is also the issue that a fight in my game can end in a unpredictable number of moves, as low as one, but most likely a few hundreds and possibly never end in some cases (extreme case: two healer with infiny mana fighting each other ;o). I could use my current evaluation function after X playout and call it a probable win or a loss based on this but again, my eval function is slow and I can't halp to think that it would be a "waste" to use it and not store that information.

That sounds like a potential game-design flaw. It's good to be able to guarantee finite games. There is usually some resource that is being depleted as the game progresses (perhaps mana and health points of the participants). Still, you could simulate a number of moves and then use an evaluation function to decide how happy you are with the outcome, instead of simulating to the end of the game. MCTS can accommodate that.


One more architecture to consider is an artificial neural net (ANN). A few years ago I would have told you myself that this is a terrible idea, but ANNs have improved a lot lately (people use the term "deep learning", which is short for "neural nets now work"). However, they are not the magic bullet that they appear to be at first, and you need significant expertise to make them work well.

If you are interested in exploring ANNs for your game, I can go into some detail of how they can be used.

To IADaveMark:

I've finally took some time to watch your 3 AI summit video Dave. It was a great watch

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. What you suggest is (to simplify), to evaluate my possible actions based on a weighted scoring system of “considerations". I've done that already in my evaluation function: it averages hit chance and such to give me a value of threat for each unit based on each of its skills.

My evaluation function basically scores the result of the action instead of the action itself but it has the same effect (I can tell which one is the best for a given turn). For now I'm subject to RNG since I create my tree based on one possible outcome of a skill but I could use the kind of averaging modeling I used in my evaluation function to the Tree creation. That would leave me with some flaws thought: the more in depth I'll search, the farther from the truth my approximation will be [I’m pretty sure I’m forgetting another big flaw here because if I weren’t this would probably be a decent solution]

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

1. 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
2. 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.

To Alvaro:

The reason I cannot use MCTS is because my move generation is a slow process. Most examples I’ve seen have a very simple game data representation that they can modify really fast to generate a new state. In my case, a BattleState is over a thousand variables (float, not Boolean). For each move I’ve got to save the current state / generate the new one / revert to the old one. I’ll avoid the loading state / reverting if I do a full depth playout but it is still way too much work to be done.

Regarding the battle that may never end, it is by design. It probably won’t happen very often but is a very likely scenario. Not a big issue since as you said I could use my evaluation function after a while and use that to back-propagate a win/loss. The thing with RNG cases and any tree based structure is that to be somewhat exhaustive, I’d need, for a single move, to generate every combinatory possible of my different RNG factor. That is like a factorial branching multiplier for each node. Way too much for me :)

Concerning NNs, you already convinced me to try it 1-2 month ago. I gave it a try but came to the conclusion that it was not for me since I want the AI to be able to adapt in real time (even if I trough some new content at it) without the need to build-up knowledge (~in our case: the NN coefficients) before-hand.

In my game a "fail" just means that a skill will miss its target, it doesn't mean the loss of the game, far from it I don't see how weigting nodes at a more depth would give me a different result, since, If i understodd correctly you would weigth for example all node at depth 2 at 95%, all nodes at depth 3 at 90%,all nodes at depth 4, 85%, etc... How does it affects the one an AI would choose?

I aimed to suggest you use chance of win/fail as multiplication factor of the sub-tree.

Say you have 80% chance of winning. The result from the 'win' subtree thus counts for 0.8, and the result from the 'fail' side counts for 0.2. Since at each level you multiply by such a factor, its significance goes down real quickly, but you explore both sides.

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

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

(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)

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.

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 :)