I’m currently hard at work preparing A.I. for this project. I was hoping to have it ready to share today – it works, but I am still polishing the code and working on writing the accompanying tutorial. While you wait, I decided I could share the decision making process I followed while architecting this portion of the project to help whet your appetite.

Intro

There are two main roads I could have taken for implementing AI in this game. I would call one road the Smart A.I. and the other Dumb A.I.. I provided these labels based on the amount of “hand-holding” I would have to provide in order for the computer to make seemingly intelligent decisions.

In the realm of Smart A.I., there are algorithms which could allow me to do little more than tell the computer what the rules of the game are and how to determine a victor. From there, it can simulate its own playthroughs and develop its own strategies based on the resulting data. It may even come up with strategies I had never thought of!

The other path is what I would call Dumb A.I. – note that this doesn’t mean the resulting computer controlled moves will be poorly made, it simply means that it will only make moves as strategically as I can teach it to make. I would be trying my best to help it “think” like I would and make decisions based on the data immediately available.

Smart A.I.

When I first thought about creating A.I. for this project, I had thought it might be fun to do a really “smart” implementation – by this I mean an opponent which “thinks” several turns ahead to make the best use of its abilities and resources. I have experimented with a few different algorithms which are commonly used for strategy games such as “MiniMax” and “Monte Carlo Tree Search”. These are both great systems and I would recommend you spend some time studying each. I am not going to “teach” either system in this lesson, but I did feel it could be beneficial to discuss why I felt they weren’t the best fit for this project.

MiniMax

MiniMax (with Alpha-Beta pruning) is a great system for making sure that a computer opponent picks the best possible move, all without actually having to check every possible branch in a move tree. Since the number of possible moves in a turn for our game is quite large, that would seem like a great feature! However, in order to use this pruning ability, we must first come up with a way to “Score” all the possible moves.

At first you might not think that would be so hard – just sum the hit points of each team and compare them. If you approach the score of a move in this way, then both damaging an opponent and healing a teammate could result in better scores. However, a good tactics game can perform a lot more abilities than merely attacking and curing. How would inflicting a status ailment be scored? Blind is really helpful against a physically strong opponent, and Silence is really helpful against a magically strong opponent, and neither of those tactics would receive a good score with our Hit Point based initial approach. Likewise laying a trap on a tile doesn’t immediately have an effect on either side – how could it be scored?

Attempting to write a system to score moves which take into account all of the possible strategies in a game this large would be difficult, if not impossible, so for now I decided to skip this option.

Monte Carlo Tree Search (MCTS)

MCTS has a lot of great features too. One of the first benefits of this system also happens to be a solution to our previous problem – I don’t have to be able to write a system which can score moves. If I can play a simulation to its completion (i.e. one side defeats the other) then I can simply use the result of the game to determine when one path is better than another. The strategy used to get there didn’t need to be “understood” beforehand, but given enough time it will find and “think” of patterns you may have never considered.

Unfortunately there are several crippling factors for this approach as well. For example, a simulation could theoretically play forever- units could move back and forth blindly on opposite sides of the board, never finding each other, and therefore never complete a battle. Another possible scenario is that by random chance they may keep picking only to heal themselves and or team mates, or pick offensive moves which never reduce hit points.

You can get around the infinite-game problem by limiting the depth of the simulation to a certain number of moves and then rating the overal game. For example, say you played for 50 turns and the battle had not been ended, you could simply mark the game as complete and pick a winner by number of active units and or hit points etc.

There is still another problem – the game tree complexity. Even though MCTS doesn’t have to consider every possible option in order to seemingly pick something “smart”, it needs to be able to consider a “large enough” spectrum of the moves to appear as smart as a human would. The number of required moves to check which would fulfill that requirement is probably far larger than one would imagine.

To put things into perspective let’s consider a very simple game. I read that Tic-Tac-Toe has 255,168 leaf nodes in it’s game tree. This is a super simple game with at most 9 options on the first turn, and with each turn having less move options, and there is a definite end game scenario relatively quickly. Still, I would not have guessed the tree would grow to a couple hundred thousand options.

Chess takes the example a little closer to the level of complexity that our game enjoys. There is a larger board, more pieces, different move rules, etc. I read that there are 10^120 different board combinations – thats huge! Still, Chess doesn’t necessarily force an end, and the number of move options per turn can change, but if you played for say 50 turns deep with an average of 20 possibilities per turn then you would still have, well… a really big number… (20 * 20 * 20 etc – yep really big).

Our game can have a larger board than Chess. It may have less pieces, but the facing direction coupled with a large variety of individual stats, including changeable stats like hit points and magic points, buffs and debuffs, etc, make for a number of board combinations which far surpasses the complexity of Chess.

Just consider a single turn (which actually consists of multiple steps):

1. Move – a unit with a small range of ‘3’ could potentially have ’25’ different targets to move to (including the tile it was already on which is a valid option – not moving).
2. Act – an ability can also have a range, so lets consider another small range of ‘3’ for another ’25’ options. (Granted, not all of the locations would result in a valid target, so some of these could be culled out, but they will still need to be evaluated.)
3. End Facing State – we can pick any of four options to face

That simple (and conservative) sequence is (25 * 25 * 4 = 2,500) options to consider. Still, it is not even the full number of options a single unit could pick from. For example, the unit could choose to attack before or after moving. Units also have more than one ability to pick from and this is all within A SINGLE TURN – imagine how quickly the tree would grow when trying to look multiple moves ahead!

With all of that said, I lack the confidence that it is possible for a modern computer to be able to consider a “large enough” spectrum of the possibilities to make decisions that look smart, and even if it could, I would certainly need to let the AI calculate for awhile – which means it should think on another thread, otherwise the game will appear to freeze. Unfortunately Unity doesn’t support multi-threading, and my architecture is currently bound to it, so either way this is another dead-end.

Dumb A.I.

When I say “dumb A.I.” I am imagining one which does not consider the effects of its choices. It simply makes choices based on whatever it was specifically told to do. For example, it could perform attacks according to a pre-set pattern, which can still look kind-of smart since the pattern was input by a designer, but which may or may not look terribly smart in practice. For example, if the A.I. already had full hit points but decided to heal itself then it would look kind of dumb.

When I thought about it a little more, I realized that there is actually something rewarding about a dumb A.I. in a tactics game. For example, if I siphon all of an opponent’s magic points, and then the opponent attempts to cast a magic spell and therefore wastes a turn, I find the feeling to be very rewarding! Likewise, if I have abilities that let me absorb elemental damage, then it is exciting for an enemy to attack me using that element. Smart A.I. would potentially notice these outcomes and avoid them, thus removing some of my favorite moments of combat, but a dumb A.I. helps a player feel smart!

A dumb A.I. can be implemented with a few fairly simple rules and conditions, and can still easily scale over the course of the game to feel “harder” simply by raising the number of opponents and/or by raising their stats, etc. It is the path I decided to follow, but even within this decision there are plenty of options. I looked at a few systems for inspiration, both of which Final Fantasy has used in the past: the Gambit System from Final Fantasy 12 and then looked all the way back to the simple attack sequence for AI in Final Fantasy 1.

Gambits

Put simply, the Gambit system is a list of abilities to perform, but rather than performing them sequentially, they are performed based on priority. Entries which appear first have the first chance of execution. Each entry also has a condition, and it is only when that condition fails that a lower priority ability would have the opportunity to execute. For example, you could say something like:

1. If an ally is KO’d, use a phoenix down.
2. If my own HP is less than 50%, cast cure.
3. If my target is undead, cast cure.
4. If I have a target, attack

This sequence of the entries in a gambit list would be considered in order – so that the resurrection of KO’d units had top priority in my sample. Of course, most of the time your allies are not KO’d so that step is skipped. If you just started a battle, your HP is probably higher than 50%, so that step is skipped. In special cases you might cast cure to attack an undead, but you might also be out of Magic Points in which case that step could also be skipped until finally you simply attack. In that way, the first action which could be used, would be used, and there would be a certain logic and priority to the actions which are taken.

I like this approach because it could solve some of the extra “dumb” moments of an A.I. – in particular the ones which didn’t give the player a sense of accomplishment. For example, if a unit tries healing itself or another unit which already had full hit-points. When a condition accompanies the action then the action wont look quite as dumb. I also think this could help add a little extra “something” to boss fights where the bosses feel just a little bit harder than a normal enemy.

On the other hand, I wouldn’t want the A.I. to be quite so rigid. I don’t want it to cast blind on you immediately after you had remedied it, or to heal itself immediately when its HP is less than 50%. If it did, then the players might feel that the boss was too hard, and not in a fun way. Ultimately I took some inspiration from the Gambit system, such as pairing a target with an ability, but decided not to implement it as is.

Sequences / Patterns

I must again say thanks for all the great people who put together strategy guides! I was able to reference the “Final Fantasy Game Mechanics Guide” by AstralEsper on gamefaqs to see how Final Fantasy 1’s A.I. played out. The system was basically just a sequential list (with a few other steps and conditions). So for example, on an enemy turn it would decide what to do based on the evaluation of four potential states: Run, Use a Spell, Use a Skill, or Attack. The order of the states is also the priority of the action – if whatever condition is met in order to run, then the enemy will run, etc.

Likewise, the Spells and Skills that an enemy could use were also provided as a repeating list. For example, the enemy named “BigEYE” would always use skills in a repeating: “Gaze-Flash-Gaze-Flash” pattern. The “WzOGRE” (an Ogre Mage) enemy had a more interesting pattern for magic spells: “RUSE-DARK-SLEP-HOLD-ICE2”. Any enemy which didn’t have an entry for spells or skills could still use “Attack”.

The great thing about a sequential pattern is that I can still get a good variety of abilities to be used, and they will be spaced out so that the user has a chance to recover from the particularly nasty ones. Also, there can be something rewarding about “learning” an attack pattern and using that knowledge to defeat an enemy. As a huge plus, it is the easiest of all the A.I. systems to implement.

Of course, I can spice it up a little bit. For example, in my post, Random Encounters and Polymorphism, I mentioned creating recipes for what monsters would appear during a random encounter. It was a list of enemies, where each unit listed would be spawned. However, some of the elements in the list were actually a pair of enemies and within that pair only one of them would be chosen at random. This helped to add some nice variety to the encounters so you didn’t feel like you were always fighting the same battle.

We could provide a similar treatment to our sequential list of abilities for an enemy to use. For example something like the following:

1. Fixed action: Attack
2. Random action: cast Fire or cast Blind
3. … (extend the list with more entries or loop back to the beginning and repeat)

Implementation Details

Knowing that I want to use a particular sequence of abilities is great and helps satisfy a lot of the logic about “what” to use, and “when” or “why” to use it. However, knowing the “how” is going to be much more complex. In a non-tactics RPG the enemies don’t need to be as concerned about distances and angles etc. but those elements can add a great deal of strategy in our game.

For example, let’s say that our sequential list tells us that it is time to cast “Fire”. I now need to determine what targets are within reach as well as which, if any, of those targets do I actually want. I could add some Gambit-like target markers to each entry in my sequential list which could help. This would be useful because the targeters we implemented on the ability effects don’t care about the alliance of a unit – it would be legal to cast fire on any of them, though potentially not helpful. AI targeting on the other hand does care about the alliance of a unit. So even though a particular location could report finding a certain number of targets, there may be better locations that attack a foe without hitting a nearbly ally.

Those extra targeting scripts will be implemented with some additional classes. It will be their job to help find the best locations to move to and the best directions to face and or locations to target for use with the ability we had previously selected.

Summary

In this post, I discussed some pros and cons of various approaches to A.I. and how it could relate to and be implemented in our Tactics RPG project. I explained the thought processes in my head as I decided on a route to pursue. Even though there was no code in this post, I thought it might introduce a few topics to inspire your own learning, and still could provide valuable insight to the development process. Feel free to leave comments and let me know whether or not you enjoyed it!

A.I. takes a long time to implement. Before I share my work I felt it needed more polish time and a bit more in-depth discussion explaining what all the code is doing. Assuming nothing goes wrong, I will begin sharing the actual implementation next. There is quite a lot of content so far, so it may need to be broken down into a few parts. Stay tuned, I think you’re going to love it!