Got to love how all of my favorite Nintendo franchises are coming to mobile. First it was Pokemon Go, then Fire Emblem Heroes. I’ve pretty much been playing it nonstop for the past week and a half, which is pretty good, since I was worried the game would get a little grindy after a while. It does, but the core gameplay of moving your little mages and swordsmen around on a grid map is fun enough that I don’t mind.

At first I was worried that the little 8×6 grids wouldn’t offer enough variety to stay interesting, or would be too small to inherently strategic. Thankfully after a week I can say that’s not the case, and several gameplay tweaks from the console games make the strategy just as compelling, if in little bite-sized chunks.

Also in the past week I went back and reviewed old knowledge from an Artificial Intelligence class I took in college. Specifically, it was entirely learning how to program an application that would play Chinese Checkers, and play it well. No Terminators (though I did take a theory class as well.) And it got me thinking, would it be all that difficult to program an application that could play Heroes?

Probably not. At least, not any more difficult than the Chinese Checkers program I learned on. Fire Emblem makes it easy as it’s grid based, like a traditional board game, and turn based, like a traditional board game. The complexity of board games like this is determined by the number of possible game states. That is, every possible combination of game pieces on the board. For an 8×6 board with 8 movable game pieces, a high estimate would be 48*47*46*…*40, or roughly 6×10^14. For comparison, Chinese Checkers has about 10^23, and chess has 10^47, and those are considered to be estimates closer to the actual number of possible states rather than a high estimate.

It’s not a perfect comparison, and does leave off some calculation of complexity based on game logic (like how in Heroes, you have to move four pieces per turn instead of one) but the game certainly appears to be in the realm of doable. But… maybe not on an iPhone.

As cool as all that is, most video games don’t really take it into account for two reasons. One, most video games are more complex than chess and checkers, and two, most video games aren’t trying to inhumanly kick your butt. They might be hard, but not “look 15 moves ahead” hard.

One of the mainline Fire Emblem games may have a map somewhere around the size of 20×20, and have dozens of pieces on the board, making its complexity somewhere in the order of more than the number of atoms in the known universe. (Numbers get big quick.) Because of this, a typical Fire Emblem game will have a much simpler greedy algorithm. A greedy algorithm makes locally optimal choices in hopes that it results in a globally optimal play. E.g. the AI takes the first game piece in a list, determines what the best move for that piece is, makes it, and goes on to the next piece, instead of looking at all possible combinations of moves and determining which is best. Not only is this much simpler to calculate, but it gives a slight advantage to the player, as most players can usually come up with a slightly smarter strategy. Some smart ordering of the list of pieces to make their turn can give a little more strategic depth to the greedy algorithm, but the AI can still only look one move ahead at any given time. This still runs into problems like one game piece potentially blocking another piece. In older Fire Emblem games, if a computer controlled piece couldn’t reposition itself to attack or move towards the nearest enemy, it would just sit and do nothing.

So I was tickled surprised when I was playing Heroes and an archer, which can only attack two spaces away, moved out of the way, out of its own attack range, so an up close fighter could attack. This suggests that the AI was using something more complex than the typical greedy algorithm. Is the game taking advantage of its smaller state-size for more complex AI? Let’s take a look at an example.

In this fight, I have from left to right on the bottom: Marth, the red swordsman; Cherche, the green wyvern rider; Clarine, the healer; and Robin, the blue mage. My computer controlled opponent has: Lucina, the red swordswoman; Camilla, the green wyvern rider; Takumi, the archer; and their own Robin. In this game, red characters are strong against green characters, who are strong against blue characters, who are in turn strong against red characters. Takumi and Robin can only attack at characters two spaces away.

The enemy’s Robin isn’t very strong, so I decide to move my characters up and to the left to meet the more threatening enemy characters first.

The enemy Lucina and Camilla move down two spaces, Takumi moves left two spaces, and the enemy Robin moves left and down. Interestingly, this puts Lucina within attacking distance of my Robin, whom she is weak to. But it also puts her as close as possible to Cherche, whom she is strong against. Takumi on the other hand moved left. Both moving left and moving down would put him equidistant to Cherche, who he is strongest against.

I decide to spend my turn waiting instead of putting myself forward to attack. The enemy Camilla simply moves down as she makes a beeline for my Robin, whom she is strongest against. However, the enemy Lucina decides to go to the right, away from Cherche and the rest of my characters waiting in ambush. This suggests that the AI is not simply making a greedy assessment.

If I attack with Robin, he’ll block Marth from being able to attack Camilla. But…

If I attack with Marth, he’ll block Robin from being able to attack Lucina or Takumi. In this surprisingly defensive play, the computer minimized my ability to attack and knock out its characters. If the AI was simply “move towards character I’m strongest against” this wouldn’t have happened.

I decide to take out Camilla and move Robin behind Marth. I also move Cherche down to avoid Takumi’s arrows, which she is weak against.

This ended up being a poor move. I lost the match.

Here’s a second scenario. Chrom, the red swordsman, can only attack Robin, who he can’t do much damage against. However, if he moves up out of the way, then Fae, the green dragon girl, can move into his spot and attack for a lot of damage. Will he do it?

Nope. Instead he attacked at close range, then Takumi attacked and got himself knocked out in the counter attack, and then Fae pulled Chrom back one space. This goes against my original hypothesis, as it doesn’t seem to be considering all possible scenarios. Or maybe it is, but what the computer considers a good play isn’t what we as players believe is a good play.

What is a good play to a human player? Probably one that maximizes damage done to the opponent characters, knocks out as many of the opponent characters as possible, and moves your characters closer to other characters they have an advantage over. At the same time, we want to minimize damage done to our characters, avoid getting them knocked out, and keep them away from characters who they are weak against.

But unlike games like chess and checkers, there’s an inherent imbalance to Fire Emblem. Not all characters are equal, and sometimes one side can be so lopsided that it’s impossible to do any damage to the opponent. In this case, the computer might start playing coward. The best play is to prolong the defeat and run away, which isn’t very fun for you the player. So instead, the computer must favor a highly offensive strategy for the sake of not being a poor sport.

Based on this we can make a few observations:

• The computer will always move its characters to minimize the distance between them and foes that they’re advantageous against, while also maximizing the distance between them and foes that they’re disadvantageous against.
• The computer will always attack a foe that is in range, regardless of consequence.
• If multiple foes are in attack range, the computer-controlled character will attack the foe it is most advantageous against.
• The computer always favors knocking a foe out.
• The same character doesn’t always move first.
• If multiple characters can attack the same foe, the computer will favor attacking with first with characters that cannot be counterattacked, then characters with color advantage.

Based on these observations, this is what I hypothesize:

• The computer calculates one turn ahead. It goes over every possible combination of moves for its four characters to determine the best scenario. To determine the best scenario, the computer uses these weights for every move, in order of most important to least important:
• Knocking an enemy character out.
• Attacking an enemy character that cannot counter attack.
• Doing damage to an enemy character.
• Attacking regardless of damage output.
• Using a skill.
• Moving towards the enemy character that character has an advantage over.
• Avoiding being attacked by the enemy characters.
• Avoiding enemy characters the character has a disadvantage against.

Note that this isn’t necessarily a straight checklist. In an extreme case, the computer may pass up knocking out an enemy character out because the sum of other, lesser important actions outweighed the one knock out action. This is one possible explanation for the second scenario.

Obviously this isn’t what’s best for the computer, nor does it match what usually goes on in the player’s mind. But it is enough for the game to give you a swift kick to the rear if you’re, say, getting screenshots for a blog post instead of paying attention.