Sign in to follow this  

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

This topic is 759 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hello!

 

I’ve got a game design AI related issue I’m having trouble to solve and I’d love to have you guys input on this :)

 

A bit of background on my game:

 

I’m designing an idle/incremantal RPG with a turn based battle system similar to FF7. The player can setup pre-determined rules for his party that the game engine will then execute (very much like the FF12 gambit system: a bunch of if/then/else do that).

 

I am now working on the monster’s AI. I’ve settled for a chess-like approach to the problem: Create a tree of all possible game state by listing at each unit’s turn, each possible move/skill she can use. And then, parse that tree and find the best move for the AI. I used a custom evaluation function to assess leaf nodes and value how good/bad the situation is for the AI.

 

I’ve managed to build up my AI data tree quite nicely and it can also use a MiniMax algorithm to find a good move to play. I’ve got unrelated issues to this topic (mainly my AI is way too slow and can only expand fully like 100 nodes, but this shouldn’t really matter for what I am coming here).

 

The issue:

 

For now, my AI use fixed random seed to simulate a unit’s turn and then use the same seed for the real turn. It allows me to know exactly how the game will pan out during my simulation.

 

The main things affected are everything that is percentage based:

  • Chance to hit mainly
  • Skill with a proc chance (ex: 10% do to this, 90% to do nothing)

My AI knowing what this random numbers will be, know if his next move is going to fail for example. It then chose a move that will either not miss or is just buying her time until the RNG seed is more favorable to her. If all skill would fail this turn, she then simply chose the one that cost her the less resources so she can maintain her advantage. It is smart of her but it means that the AI will likely never “miss” an attack or only use proc based skill when they will actually proc.

 

For example, it kind of transform a spell that has “X% chance to do Y”, to a spell that has “100% to do Y but has a cooldown of 1/X% turns”. This is not what I want.

 

I want my AI to use actions and sometimes miss. 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. Example: I cannot split every percentage roll into 2 sub branch tree: passed / fail. It would solve most of my issues but will be too time consuming for me.

 

Some of my ideas:

 

1 -   Leave it that way and make a design feature: fighting an AI that can “predict” the future can be a challenge in itself, maybe even an interesting one if balanced properly. For example The AI may never miss a skill but if the player uses skills that reduce the monster’s chance to hit it may lead the AI to be forced to make poor choice in the end if it really has no other options. Not my favorite option but still worth exploring.

 

2 - Changing our RNG seed dynamically so that any random generated during the simulation of a move/turn will not be the same when the turn is really played. Easy to do. The simulation will be “realistic” but In the end inaccurate. It reflects a possibility that could happen but not the real one. The more depth we explore, the farther we will deviate from the real output of the game since we will be re-rolling every random number. In these cases, if the AI selected a move because during simulation because it seemed good, it would still have a chance to fail when the move is really made (that is main advantage of this method). But it doesn’t solve the inverse case where if the AI think it will miss an attack, will still discard it for other safer moves, leading here to eventually make stupid moves : if the AI got only an attack and the possibility to skip turn, it will skip its turn which make no sense.

 

3 – Change my simulation function to try and average every proc based on percentage. For example: instead of hit/miss I could multiply the damage done by the hit% chance and make it always hit. In average it gives the same damage. It does solves the issue of a “miss” since the AI will chose the best choice regardless of that. The thing is, the more depth we analyze, the farther we will end up from reality (making our decision process more fragile) and some procs are really hard to average with accuracy (stupid example to illustrate: a skill that has 5% chance to kill a character). It is also something that would require extensive recoding and that I’d like to avoid if possible.

 

4 – Use the same RNG in simulation and the real turn but while deciding what moves to choose, dumb down my AI and add a X% of chance to choose a different move than the best one. It allows us to somehow force the AI to select a move that will miss its target for example. I don’t really like dumbing down my AI on purpose that way. It could make her chose very stupid moves while an optimal one was the obvious choice (ex: a target can be finished with a simple attack but since the AI knows it will fail, it will skip its turn -> it’s counter-intuitive to what a player would do, a player would try to finish off the target, not knowing if the hit will land or not, but he will try if he has a decent hit chance). It also poses the issue of how to chance that X% to select a different move…not a trivial task at all if we want to be as realist as possible.

 

5 – Some other ones I already forgot :/

 

In the end, my problem is heavily tied to risk assessment. Trying to find how human assess these risk/reward situation would definitely help me in making the AI do the “right thing”. I want it to appear “smart” and avoid her making choices that the player can label as poor easily. The optimal move are often debatable but the really bad ones tends to stand one and that’s what I want to stay away from.

 

If you got ideas on all this, or question, don’t be shy :)

Share this post


Link to post
Share on other sites

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

Share this post


Link to post
Share on other sites


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.

Share this post


Link to post
Share on other sites

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

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites

To IADaveMark:

 

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

 

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.

Edited by Ey-Lord

Share this post


Link to post
Share on other sites


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

Share this post


Link to post
Share on other sites


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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites

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)

Share this post


Link to post
Share on other sites

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)

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites

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 !

Share this post


Link to post
Share on other sites

 


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

 

blink.png

 

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)

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites

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

Share this post


Link to post
Share on other sites

it might be time to consider a different system.
 
 
It is quite possible. I'm opened to any suggestion
 

 

https://en.wikipedia.org/wiki/Expert_system

 

any types of AI can be used to make the decisions in the expert system.  use the best AI type at each decision point.   that may be simple rule based behavior, or something more complex, such as output from a planner module.   build it up as a hierarchy of expert systems/modules. one overall module, and separate modules that specialize in specific types of decisions (fight or flight ?, select weapon, who's the greatest threat, etc).  then you just need an expert to "write the rules of behavior".   as game dev, one would assume that "expert" would be you <g>.

 

i find this approach allows you to tackle the problem the way you would as a human player, and simply make the AI do what you would do if you were playing the AI side yourself. it doesn't limit you to the constraints and weaknesses of a given type of AI, as it uses a variety of types as needed. i find that behavior trees and hierarchical finite state machines seem to be the AI types which are most often the best choice for a given decision module in the system.

 

the weakness of this approach is that the AI will never be better than the expert programming it.  not that big a deal really. you're building the game, so until it get into the hands of some rabid fanboy who spends six months playing it all the time, odds are you'll be the best player out there.

 

a quick example:

this is the basic AI for band members in caveman at the moment:

 

1. are there badguys nearby?

 

if badguys nearby:

1. if in a shelter (tent, etc), leave shelter.

2. if doing an action (eating, crafting , etc), stop the action.

3. determine target

4. if cornered (pinned between terrain and PCs/NPCs/badguys), attack

5. if in collision recovery, do collision recovery

6. if taking fire, respond to taking fire (attack if have target, else flee)

7. if have target within 20 feet: if target is stronger, flee - else attack.

8. if have orders, follow orders (attack, follow, move to, stand, flee, maintain distance, etc)

9. if half dead, flee

10. if have target (beyond 20 foot range): if target is stronger, flee - else attack.

11. if fatigued, rest.

12. if none of the above, stand (do nothing).

 

there's a similar set of rules for "no badguys nearby".

 

the game has a number of different types of AI:

bandmember (PCs under AI control)

hostile (hostile NPCs)

friendly (neutral NPCs)

companion (volunteer followers)

warrior (hired followers)

pet (domesticated wild animal followers)

predator (when hungry, eat carcasses. hunts weaker targets if no carcasses).

avian predator

defend (stand your ground)

avian defend

maintain distance (keep a safe distance from threats)

avian maintain distance

defend location (defend a specific location)

 

each has its own set of rules of behavior and its own expert system.

 

at the lower levels it has things like "graze" behavior (used by maintain distance AI and a few others) which uses a finite state machine to transition between flocking, wandering, migrating, and stand behaviors.

 

the "expert" part comes in when you write the code for "attack" or "respond to taking fire", etc. IE how to attack - with what weapons? or how best to respond to taking fire from a known or unknown source. then you simply use more little expert systems with their AI type of preference, that do nothing but decide how to attack or how to respond to taking fire, etc. eventually you end up with a hierarchy of expert systems, perhaps using a variety of AI types, with each little module an expert at making one decision, be it high level or low level. 

Edited by Norman Barrows

Share this post


Link to post
Share on other sites

For all intents and purposes, that's the same thing as a utility system. The advantage of the architecture in my lectures is that it is completely homogeneous and data-driven. You don't have to write separate AI modules for different types of decisions. It has most of the same power as an expert system but is far less cumbersome to develop and maintain.

Share this post


Link to post
Share on other sites

Risk/reward ....  one fundamental way to make a situation where the risk/reward is clearer (logicwise)  is to have a rule mechanism  where  once you get involved in a fight, you cannot leave it  (gives more importance to maneuvering before engaging).  or take some major defnsive penalty if you do.

Share this post


Link to post
Share on other sites

Hello again smile.png

 

I've been working on that for the last couple of weeks and here is what happended :

 

My game engine overwall was slow, very slow. I spend a lot (too much) time optimizing every function that was taking too much time. The task was basically to optimize the whole game structure since 90% of my code related to battle was beeing called over and over...

 

My game engine performance improved vastly since last time but sadly I'm nowhere near the level of performance I'd like :/

 

I've removed all my utility based AI form my code and decided to give MCTS a try. Mixed results so far.

 

If I disregard some issue in certains browers (love you IE...), with a simple fight with a low number of skills/buffs/other costly mechanisms, I can run the MCTS process around 1500 time during my AI phase (1.5 seconds). That means 1500 node created, 1500 playout (limited to 30 turns), and 1500 evaluations.

 

If I skip the playout phase, I can process around 8.000 times my MCTS. On the contrary if I set it to do a maximum of 300 turns during the playout, it will process around 200 times my algorithm.  (300 turns is about the number of turns that my test-battle takes to go to a win/loss situation)

 

So far it takes OK-ish decisons (using the 30-turns max playout) but still takes somme silly decisions sometimes.

 

I can't help to think that running 1500 times a MCTS algorithm is too low to have something decent. At the same time, i've optimized my code as best as I could and cannot find anywhere else to gain speed at the moment. Which is kinda of scary because I anticipate that under real circumstances, the AI will run even slower (having more things to check than with my test setup).

 

For now, one of the main issue besides speed of execution is that it has trouble handleing RNG.I've stopped using fixed random seed (it was way too time consuming to be viable). That means that if my AI test a move and roll a "miss" on the attack, it will likely discard the branch in favor of another attack that did not miss. The issue is not really that it selected that second attack but more that it avoided the first one based on a false idea of its sucess. it basically means that to be chosen, that attack have to pass a hit-check during the AI phase AND another one during the move processing for real. Hit chance double-dip = bad design here.

 

I've found a not-so-elegant solution that doesnt solve the issue entirely by at least diminish its impact : Only for the root of my tree (the unit I need to take a decision for in the end), I will add 2-3 times a node for each possible move. So if that move is a fireball, the AI will created 3 children resulting from the cast of a fireball on a target. If one hit and two misses for example, the AI will focus on the hit-branch for that spell and is more likely to select it in the end. At the same time, if my hit-chance was really low, I've got good chances that my AI will miss 3 times and doest not select the move.

All in all, it has many flaws (mainly the number of nodes added cannot be balanced properly vs the percentage of each RNG stat so it will still be RNG-dependant ... just a bit less that with only 1 node per move).

 

I'm open to any kind of better solution for this !

 

I think that with more processing power (for example if I was able to compute 15.000 moves per AI phase), the MCTS will likely be able to go much further down the tree and over the course of XXX turns, see that a fail for a move at depth 1 is not a big deal since everything after that can also fail or not and with a big number of turns evaluated, the hit/miss of each moves kinda averages down each branch.

EDIT: I was wrong here, giving it more time doesnt solve the underlying issue.  I need to find a better way to solve the RNG nature of the moves.

 

One thing to note about my tree, is that since i know with certainty what moves the player will make, i've done a tree with only the monter's position in it. When creating a children node, I process turns untill a monster's unit should play. That allow me to have less node in my tree overall and go deeper/faster into the game.

 

I haven't tried yet to do a lot of optimization on the logic on the MCTS itself (like added domain knowledge and such) but I will come to it soon. A few questions I've got about that :

- it is worth it to add more than 1 children per expanding phase ?

- it is useful to do more than one evaluation per MCTS run ?

- should i initiliaze the number of win/simulation used during the selection process to something closer to the parent's value or keep 0/0 ?

 

I'm currenctly trying to find a way to prune entire branches based on game knowledge but so far I've failed to find easy to asses situation where I could prune a move with quasi-certainty.

i'm also thinking about using some faster-less accurate versions of the real one I use during the processing of a normal moves. This would allow me to gain speed, potentialy a lot by skipping some computation that have less effect on the end results) but it will comes with a potentialy huge loss of accuracy overall and may lead the AI to do stupid things. For example; if I decide to remove every life/mana leech computation for the AI process. It will be faster but will fail to properly evaluation situation where monsters or players heavily rely on leech.

 

I like the MCTS idea but my lack of processing power worries me a lot ^^

 

If you have ideas / suggestions / remarks / criticsm / questions, do not hesitate smile.png

 

EDIT : It turns out that even if I allow my MCTS to run for longer than planned, it still doesnt give me decent results. So i'm shifting my focus from game engine optimization to try and fix-up a MCTS version than can give decent results even if it is under a long time frame to start.

One of my main issue is how to handle the non-deterministic states of my moves. I've read a few papers about this but I'm still in the dark. Some suggest determinizing the game information and run a MCTS tree on that, repeat the process N times to cover a broad range of possible game states and use that information to take your final decision. In the end, it does multiply by a huge factor our computing time since we have to compute N times a MCTS tree instead of one. I cannot rely on that since over the course of a fight I've got thousands of RNG element : 2^1000 MCTS tree to compute where i already struggle with one is not an option :)

 

My idea of adding X children for the same move doesn't seems to be leading to a good answer either. It smooth the RNG curve a bit but can shift it in the opposite direction if the value of X is too big/small compared to the percentage of a particular RNG. And since I got multiple RNG par move (hit change, crit chance, percentage to proc something etc...) I cannot find a decent value of X that satisfies every cases. More of a badband-aid than anythign else.

 

Likewise adding 1 node per RNG tuple  {hit or miss ,crit or not,proc1 or not,proc2 or not,etc...}  for each move  should cover every possible situations but has some heavy drawbacks : with 5 RNG mecanism only that means 2^5 node to consider for each move, it is way too much to compute. If we manage to create them all, we could assign them a probability ( linked to the probability of each RNG element in the node's tuple) and use that probability during our selection phase. This should work overall but be really hard on the cpu :/

I also cannot "merge" them in one single node since I've got no way of averaging the player/monsters stat's value accuractely based on two different game state and averaging the move's result during the move processing itself is doable but requieres a lot of simplifcation that are a pain to code and will hurt our accuracy really fast anyway.

Edited by Ey-Lord

Share this post


Link to post
Share on other sites

This topic is 759 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this