Hello everyone,

I'm currently working on a web rpg and I'm at the point where desining an AI make sense. I've read lots of articles / papers but still can't really figure the best approch for my case. I'll take every hint and advice you have

First, a description of my game (i've simplified a few non-important things). It is coded in html / JS (jquery) ; for now its not aimed at mobile but only desktop browser. At its core, it's a strategic idle rpg. The player's main role is to create a team of 4 characters, choose their skills (they can have 6 in total at the same time), choose/customise/improve their item with a huge number of magic properties, choose what talent they will be using and chose an AI for his party.

The player has access to a "gambit" system, similar to the one in FF12 but a bit more complex, giving the player more options to really define a small rule-based AI for each of his character. He can describe fairly complex rules such as telling a character to off-heal if the main healer of its team is silenced or low on mana for example.

Once the player as carefully chosen its skills/talent/items/AI he can go into battle. He simply clicks on a battle zone and then its team will fight without any interaction from him untill he decides to stop. Since it is an idle game, he can farm for a few hours or even days if the game page stays open. His team will chain battles, recover hp/mp bewteen them, gain some xp / gold (that the player can use to improve his items). And when hes strong enought he can move to the next zone.

The game is not meant to have a level cap

The battle in itself is a 4 vs 4 turn-based final-fantasy (6,7,8...) style. Their is no movement involved, only what skill to use at each turn (lets assume monsters got between 3-6 skills).

Their is a Action Point (AP) system in place. The unit with the most AP at any given time can play its turn. If no unit has > 100 AP, a new "turn" happens in battle. A Battle turn basically add a bit of AP to everyone and update the buff/debuff system (for example with buff that deal damage every turn).

For now, the AI of my monsters is non-existant : cast a random skill I got at a random target.

I want the monster's AI to challenge the player, force him to both:

- farm more to aquier better item and become stronger

- make him rethink his whole battle strategy from time to time (he can reset his talent points for a fee, swap item/skills freely and changes his Gambits at any times)

I want to AI to:

- works with any kind of skills I give her withtout having to tweak things for each monster individually)

- versus any kind of oponent stratgegy (more or less efficiently off-course)

The hard thing is I got many constraints:

- the game is fairly complex: each unit has around 100 different kind of stats, at least a demi-dozen buff/debuff on it at any given time, ect... The BattleSystem that compute damage / hit / spell cost ect... works pretty well but it needs acess to lots of datas and do lots of computations to compute the outcome of a particular attack/skill.

- let's face it, my game engine works really fine on its own but is nearly not as effecient (speed-Wise mostl) as it would need to be to brute-force an AI solution

- I'd like the whole AI process to decide a turn for a monster to be around a second or less.

- I cannot really multithread given the amount of data I need to handle and more importantly the way my game engine works. So I need to squeeze AI into my main Update() loop of the game.

- With my game engine, the only way I can compute things (damage, mana cost ect...) is to make the computation on the "live" player group. So I need be make a backup of it and realod it everytime we enter/exit an AI computation phase.

- I dont have lots of room to save variables for the AI bewteen games, that will make difficult to use NNs, genetic algorithm and such.

The only solution I found is an utility-based one (player&monster have acess to every stats of every one):

- create a score for every unit in the game (monsters & players, from the perspective of the AI). This final score will be the weigthed sum of different sub-scoring variable

- simulate each move available and simply use the one that maximise the monsters scoring and/or minimize the player's scoring after the move is done

- for that I can give a direct threat score to every unit of the player taht represent an offensive threat (a dps, a debuffer, a CC-er) and give a indrect threat score to defensive units ( tank, buffer, healer)

- I can also add some "weakness" scoring, that will take into consideration hp / mp / armor and such. It will help focus the weaker units and the one closer to death for example.

- I think it would be "easy" to add some simple behvior modification to the process by simply changing the weigth of each score or its computation internally. For example, I could give a few tags to monsters like "berserk" (AI will then try to lower the weakness score of its oponent more) or "carefull" (AI will value its own weakness scoring system more and will prioritize recovery over damage). I can also give a "importance" factor manually to every monster so AI will try to keep them alive before. But all in all, it stays really simple and I dont see "smarter" behavior emerging from that :/

Ideally, I would use a minimax tree, alpha beta and such to simulate a few moves before choosing the best one but in pratice I'm not sure it will be usefull for my case: Here is why:

- In chess, a battle state is really simple and can be store in memory very efficiently. For my game, storing all the informations of a battle at a given time to be able to simulate every action in a tree leads to huge memory consumption even at very low depth.

- The solution I came up with is to only store the minimum information I need to re-create that battle state. It reduce drasticly my memory issue but brings up the issue that I've got a fair amount of computation to do each time i load/save a battle state. In other word, each time I simulate a new move, I need to save the current battleState and if I want to generate a sibling, i need to reload the parent's node Battle State.

- Adding to that, when trying to generate a child node from a selected move, the computation process of damages / buff effects ect is also taxing in speed.

- I've got lots a randomness (percentage of critical strike, lots of procs...) that can somewhat be approximate (discarded or taking to average or w/e) when computing a new battle state but it will definitly lead to some mistakes by the AI [its a small issue compared to the other]

- in Chess an average game is like 40-50 tunrs ; in my game it will likely be way more than that and if their is a healer or if the player has chosen a very defensive team composition, it can go in the thousands turns. So, seeing 5-10 turns ahead may not offer much for my AI

- Branching factor will heavily dépends on how much time I use to validate moves but with 6 monsters skills and 4 targets, it's safe to assume at least 10-15 child. The good thing is that for player the branching factor will be very limited, often 1 an at worst 4 (because I know the player's AI, I can be sure of what skill he will player given a certain situation....yeah that's cheating ;o))

What I've tried so far:

- I've created a call for a special AI class that will work its magic for a maximum of 50 ms and then exit its loop so the render process and resume. I cannot really go higher than that or the rendering will be very slow (50 ms is already, at max : 20 fps) but since i've got only damage/heal numbers of animation it's not a big deal. I cannot really go lower than 50 seconds (or not by much at least) because the lower I go, the more process time will be taken by the render() function of my game and thus, the lower time will be available to the ai.

- I've tried to simply save a state and load it as many times as I can during my 50 ms loop to get an idea of my performances. After a few optimisation it is very disapointing I can roughly do that around 1000 times per seconds. If we add the time needed to compute a battle state after choosing a move and the time to call the evaluation function when needed.... i'll be at best at 200-300 node in my tree.

I was thinking of computing each depth level before the next ( with cut-off if needed) but maybe a dive at a certain deep first for the potential best move could be usefull.

All in all, this tree approch is very time-consuming and I'm not sure if it will bring me enought data to really make a smarter decison than what I can do at depth lvl 1.

I've read about FSM and the like but it doesnt seem a good fit for my game. I've also seen the STRIP algorithm but again, it seems more usefull when ou got mouvement involved.

Sorry for the long post, if you got any comments / idea, it will be greatly appreciated !

Regards

I want to AI to:

- works with any kind of skills I give her withtout having to tweak things for each monster individually)

- versus any kind of oponent stratgegy (more or less efficiently off-course)

The first of those requirements suggests an option you haven't mentioned: Monte Carlo Tree Search. I don't quite understand the restrictions you are facing (in particular, I didn't get why you can't use NNs), so maybe you can't run a whole bunch of simulations of the game going forward; but it's a really flexible method that works reasonably well for most games.

The first of those requirements suggests an option you haven't mentioned: Monte Carlo Tree Search. I don't quite understand the restrictions you are facing (in particular, I didn't get why you can't use NNs), so maybe you can't run a whole bunch of simulations of the game going forward; but it's a really flexible method that works reasonably well for most games.

I think I would try NNs if I were you. If you can describe the game situation (or at least the parts of the game situation that would be relevant to a utility function) as a fixed-length array of floats (integers and bools can be plugged in as floats too), you can collect a whole bunch of these situations from games, and label them according to which player won (or whatever other measure of success at the end of the game you want). Once you have a whole lot of these situations recorded on disk, you can train a NN to try to predict the outcome of the game from the array of floats. This can be done offline, and it can be implemented in any language you want, including things like MATLAB. Or I can give you C++ code to do it.

Once you have trained your NN, you can use it as a utility function, or as an evaluation function for alpha-beta, or you could use it after some number of moves in the MCTS instead of running every simulation to the end of the game.

I would start by amassing a large database of games (somewhere between 100K and 1M), to get the whole process started. Use whatever AI you have now to generate the games. If later on you manage to write a stronger AI using the NN, you can iterate the process.

Thanxs for your anwser :) I've read a few articles about NN and now I got a much better understanding of them.

If I'm right, the correct usage in my case of NN is to be evaluate a given situation and give my as output the estimate winning chance of the situation. To start simple, I could use as input every stats of every units on board to the NN and ask one output : the winning probability of that set of input.

When the AI needs to play, I can juste create 1 NN for the current situation and 1 for the situation of every move possible and then look for the NN that has the higher wining chance as output.

If it works and to make the AI even better i can, as you said, use that process in conjunction with other AI technique (tree-based).

Is that correct?

I'm still wondering if/how I can/shoudl include the monster's move (skills) directly as input or output but since every monsters got different skills, it may overcomplicate the situation.

I found what appears to be a good start to get right into the action with the Library "brain.js" (https://github.com/harthur/brain)... I just have to figure out a good input/output set of parameters and see if I can train my NN in real time (I mean, one fight by one fight).

The part about making a database of labelled data to train the NN is important. When you first read about NNs it might seem like you can easily train them as you use them, but that has a lot of problems and I've never seen it work well. The closest thing I've seen that does work is building the database of examples as you go, and train using random samples from the past (like they do here). But separating the generation of the database and the training of the NN is much simpler conceptually and allows you to try many different things in a short period of time.

Also a note about language: The NN is a function that takes inputs and produces output, so you won't have an NN for each possible action, but a single NN to which you feed inputs corresponding to each possible action. If your list of actions has fixed length, you can also make the NN produce one output per action, whose value is the estimated outcome of the game if the given action is taken.

Building my NN on tthe fly would have been much easier, damn :p Since i've got like ~800 inputs, storing a huge number of these might be difficult :/

Regarding your last point, I may has misspoke : What i wanted to say what :

Let's say my monsters got 2 attacks and there is only 2 possible targets. I got 4 move to evaluate. I'll use my NN (only one) and feed it with the resulting new set of inputs that i will compute from the computation of the battle state that would result of our 4 possibles moves. I will then see what final output was the best and select it as my best current move.

I dont think I can use the moves as output since every monster type will have différents moves.

I havent checked it yet but I have to see if adding new input or removing some doesnt invalidate all my NN (I need taht since I will be adding stats in the game from time to time, that will need to be evalutaed as input as well).

800 inputs x 4 B/input = 3200 B/input

That's 3 GB for a million samples. You can by 1 TB for $50.

Where is the difficulty?

I havent checked it yet but I have to see if adding new input or removing some doesnt invalidate all my NN (I need taht since I will be adding stats in the game from time to time, that will need to be evalutaed as input as well).

Well, if you change the rules of the game, you'll have to work on your AI again, regardless of how it's implemented. I suggest you try to settle on what the rules are as soon as possible, allowing only minor modifications later on.

My game will chnage, maybe not by much, but they are definietly bound to evole at some point. When I will be added content to the game, I may want to add a new stat to players/monsters, for example a new type of resistance, resistance to chaos. I want my NN to be able to incorporate that new stat in its Learning process w/o having to recode everything or re-train it completely. I also may have to remove an input later on becasue the stat is gone from the game. Do you think it is gonna be an issue ?

My main issue is regarding training. I could theoricaly build a large data base and parse it on my computer to train my NN. The thing is i'd much prefer to parse a small data base of example and that the NN train itself on each battle the player has done. I'd like to able to do, after each game:

Net.Train (mylast_fightdata, 1) // or 0 for loose

Maybe I can just train my network with a slow Learning rate and very few iterations each time i bring him new inputs? That way, it should evolve toward a better weighting but very slowly... I need something like that.

Another issue that will arise soon is that all my input have no real bouds (they could theorically be +/- infinity), that will be hard to normalize to [0-1] I can probably hardcorde an estimation on the min/max values of my inputs and it could allow me get on the [0-1] range by a simple division but other than that I'm kinda stuck as how to normalize my inputs without a huge traning set.

On a similar matter, since i want to take into account the monsters & players skills, it will probably have to be inputs as well (0/4 as value depending on the number of monster/players that have acess to the skill in the current battle ... it means a lot of input to add and since I will probably add lots of monsters to the game, and lots of new input to add to the existing NN in time :/ i'll try to think of something more elegant taht can still take unit's skill into account!

Hello folks,

After a lot of trials, I still can't get my NN test right.

I tried a simple example on my case. A small NN with 9 variables, the HP of all players / monsters, normalized a bit so that the value are staying low ( in practive, lvl 8 hp var are between 0 and 2 for now and the lvl variable is : player's lvl / monster's lvl and, in my test in the range of [0-75]

After each battle, i send my NN 2 sample to analyse, the hp values (and lvl) and the begining of the fight and the values when the fight ends. I use as out if the player won or not (0-1).

I tried with a different number of iteration / err trehsold or Learning but did not succeed. When I stay in a zone where monter's lvl doesnt change, the NN quickly converge to an acceptable solution but as soon as i change zone (so i change the lvl variable), It converge to a totaly new solution and what hold true before just fails.

I would have except the NN to converge to a more global solution when I introduce him to new zone (so new type of datas) but instead it just seems to froget what he previously learned and start almost from scratch.

as a reminded, I do not store my data, I send him on-the-go each time.

Do you think what I am exeperiencing is normal ? Is it a fault in my usage / coding of NN maybe ? Could you see it working with some adjustement ? I'll take any ideas :)