I am currently working with a small indie team to make a game in Unity3d. Its combat engine is a spiritual successor to Final Fantasy Tactics (for the original PlayStation). This means the combat is squad-based, square-tiled, and turn-based. Turns are on a per-actor basis, not per-player. Furthermore, There is a very high level of customization to actors which lends itself well to unexpected behaviors (of the good sort).

Example game play starts at 0:30



I have a while before I am ready to write the AI (currently the only programmer, working on fixing that), but as it is an area of personal interest I have tried to think of what tools I know can be applied to this problem.

I have come up lacking. I have tried thinking of brute force with culling, but ended up with an overly complicated approach that would get stuck in local maxima. I thought of HSM / FHSM / decision trees, but Id almost need a separate tree for each job skill combination (15 choose 2 = 105).

Note: In this game you can change "Jobs" (classes) at will out of battle. A primary game mechanic is that you have access to the active skills of two of these jobs at a time.

I can't pay for AIGameDev, but would like some help from anyone here who may be able to give me some pointers.

However, be aware that I have little practical experience, due to a bad habit of biting off a lot, and getting overwhelmed. I don't think its *necessarily* a problem with my grasp of the material, but mostly anxiety. Therefor, simplicity in implementation *is* a consideration for me.

I have a few questions about the nature of the game:
1) Do you have a "board" representation with which you can describe the current situation exactly and decide which moves are available to the player at any given moment?
2) Is there any randomness or hidden information in the game?
3) How many moves does a player typically have available?
4) Are turns always alternating between the players?

Quote: Original post by alvaro
I have a few questions about the nature of the game:
1) Do you have a "board" representation with which you can describe the current situation exactly and decide which moves are available to the player at any given moment?
2) Is there any randomness or hidden information in the game?
3) How many moves does a player typically have available?
4) Are turns always alternating between the players?

4)
Turns are NOT alternating. Individual actors get turns based on their speed score (further modified by 2 buffs, 1 debuff, and if they chose to forgo movement and/or action last turn). Thus, it is possible for a given player (human or AI) to have several actors under their control have their turns sequentially. Time freezes during an actor's turn.

3)
A specific actor has two active skill sets to select from. A skill set is generally between 10 and 15 skills.

2)
Hidden information - not at the moment. I was considering obfuscating the target of charging skills (most skills execute immediately - some skills must be charged for N clock ticks). All other variables are exposed to AI and player. The player may even browse the AI actors' skill lists and equipment. Additionally, an estimate of the order of future turns, based on current game conditions, is available.

Randomness, however, yes. Damage of a specific skill from/to a specific pair of actors is typically constant (change the actors involved, the damage changes, generally deterministically), however success rate is variable due to a number of conditions. There exists the (small) chance of critical hits, as well as other examples of randomness in damage. For example, one skill effects a 5 tile AOE. From those 5 tiles, 6 tiles are chosen randomly, and damage dealt to the unit on that square is proportional to the number of times that square was chosen.

1)
Not sure what you mean by a board representation. In case I was unclear, watch the video, this is a tactical RPG. In general the game space is rectangular, where every square tile within is a valid potential target for movement. An actor can move to a square as long as you are within the actor's move radius (measured taxi-cab style), and no intermediate tile traversal has a height discrepancy greater than the actor's "jump" score (simply a measurement of their aptitude at moving vertically - Archers can reach high spots, whereas a heavily armored Knight may be unable to without being buffed with Float, which removes this check). Many skills, aoe's and normal abilities, have a restriction on the height discrepancies they will work at.

On some occasions, the map may feature a bridge. In this case it is possible to move to the bridge or underneath it. This means that an actor's XY position alone is insufficient to decide where the actor is on the map.

Most actors will be able to have ~25 movement options available to them per turn (the board in the video is 117 tiles large). Furthermore, they may execute one of 20-30 skills, which may target tiles on the board within the respective skill's range. This may be as many as 25 targets.

Clearly, 5^6 = 15,625 per ply is too large of a search space without major pruning.

All in all, the game is complex. This is why I have been having a hard time deciding how to approach it. Thank you for your time.

The huge branching factor and the fact that there is randomness in the results of an attack means that minimax-style algorithms probably won't work too well. This looks like a perfect situation to apply MCTS.

The basic plan is the following:
* Make a simple playing policy that is really cheap to run and has some randomness to it. It doesn't have to be very smart, but it's good if it can identify some situations where there is an obvious move. (note: by "move" I mean any decision, including picking an action)
* From the current situation, evaluate each possible move by running many "playouts" (simulations of the rest of the game) using the simple playing policy to pick moves from any player. Keep stats to measure how often a particular move lead to a win.
* Pick the move with the best stats.

There are a few refinements that will likely improve the quality of play significantly:
(1) Use the stats you already have to explore good moves more often than bad ones.
(2) Make your simple playout policy smarter (while keeping it fast!)
(3) Remember stats of the success of moves at other nodes in the tree, not just the root.

(3) gives this algorithm a tree-search flavor.

Try to read a little about how this is done in computer go, and feel free to ask more questions.

Is the customization part affecting the AI units or only the player units? If the AI units are predetermined, you may get away creating simple scripts for individual units. It will also be easier to get the behavior you want for a particular encounter. The result may not be as grand from a technical standpoint, but it will give personalities to the enemies, which will look better from a player point of view. A generic AI tend to produce generic looking enemies, which is boring.

Quote: However, be aware that I have little practical experience, due to a bad habit of biting off a lot, and getting overwhelmed. I don't think its *necessarily* a problem with my grasp of the material, but mostly anxiety. Therefore, simplicity in implementation *is* a consideration for me.

Are you averse to rewriting the AI at some point in the future to use one of these fancy techniques? Based on the above quote it's almost certainly far more important just to get something up and running. As a start you could simply take the Fire Emblem route, where most characters simply wait until an enemy comes in range, then attack, and if their HP is low enough and they have access to healing, retreat and heal. Then you just slowly build your decision tree from there. Fire Emblem makes this extremely simple system go quite far with clever level design and placement of enemies, almost like a puzzle.

Besides, you have to have an "Easy" option for difficulty level anyway.

@work, therefore brief:

MCTS looks like what I need. Will investigate further after work.

Not at all afraid of rewriting AI. Speed of development time isnt a problem at the moment.

All actors are customizable. Customization of the human's actors are done between battles. The AI's actors are sometimes preset (in the case of bosses and some generic units in plot battles), but are often randomly generated (as is the case in random battles, and some plot battles).

To further complicate things, some skills are only found on bosses.

Difficulty is closely modeled after FFT and FFT v1.3, its community-modded successor (I even have access to their full battle mechanics equations). I found the original FFT fun and barely difficult at the the age of 12. I find the modded FFT v1.3 fun and very difficult at my current age of 23.

Any AI I implement will be above the "Doom style" simplicity of how you described Fire Emblem.

Must return to work now. Again, thanks. MCTS looks very promising.

(Note... this is more for Alvaro than anyone else, but relevant nonetheless.)

Hmmm... I'm wondering if you could pull this off without MCTS, though. If you make the decision tree hierarchical and apply context-dependant utility weights to each decision layer in the tree, the search space is pared down horizontally. That is, by type of action first and then the specifics of that type later. That way, you aren't considering all the possibilities at once.

I'm just now in my hotel in LA for E3 and I've been on planes all day so I might not be in the best shape to make a call. I'll think about this later.

Either way, I would have to say it looks like a job for Dave's Book!

Quote: Original post by InnocuousFox
(Note... this is more for Alvaro than anyone else, but relevant nonetheless.)

Hmmm... I'm wondering if you could pull this off without MCTS, though. If you make the decision tree hierarchical and apply context-dependant utility weights to each decision layer in the tree, the search space is pared down horizontally. That is, by type of action first and then the specifics of that type later. That way, you aren't considering all the possibilities at once.

Yes, I thought of this type of approach after I posted the other one. I would think from a game designer's perspective it's better because it allows using "rules" (or something with a similar feel to it). It would also be easier to understand and explain why the AI is doing what it's doing than with MCTS. However, it's not the first thing I thought of because it's not the way I am used to doing things.

I come from a background of hardcore chess and go programming, where you aim for best possible play, and rules like "capture the queen with a smaller piece if you have a chance" are a recipe for disaster: You'll find your program losing because it doesn't consider queen sacrifices, and this will happen a lot more often than you would expect. I bet in this game any simple rules would have exceptions with similarly catastrophic results, if one were to play it competitively. But perhaps (unlike chess) the appeal of the game is not in the obsessive refinement of the player's tactical and strategic abilities. If you are going for a lighter, less brainy experience, perhaps some ruled-based (or utility-based) system would be fine. And it might make for more predictable and exploitable opponents, which can be fun even if it's a different type of fun than what you get from chess.

So in my opinion it comes down to what the objective is: Strongest AI possible? Or an experience that can be tuned by the game designer?

Have fun in L.A., Dave.

I believe MCTS is what I need. I *think* I have a hold on it. A few questions (more complicated ones to come when I am not time limited):

How many playouts will I need to run / how many playouts per possible move? Is there any way of estimating the order of playouts without testing? I hear 500+ playouts is good for Connect Four - I have a much larger search space.

How can I keep the AI strong on weak hardware without running up the amount of time the AI has to think each turn? By our release date, Unity3d will publish to Windows/Mac desktop, iPhone/iPad/iPod, Android, Wii, and PS3. The iPhone processor is something like 400MHz.

It is possible that for some playout strategies the game state would reach equilibrium, where neither side is able to win. Since most games would last no more than N turns, is it reasonable to call a playout a loss after N*M turns, where M>1?

What if no playouts return victory? Pick a random move, or have a default one? (this question is mostly just me pondering)

[Edited by - the_absent_king on June 16, 2010 4:34:15 PM]