AI Design

Titan is a very hard game for which to write a competitive computer player.

The main reason is the branching factor of battle moves. A chess player typically has about 35 valid moves, while a Go player typically has about 200. But a Titan player during a battle often has thousands or millions of possible legion moves. (There are up to 7 creatures in a legion, with each having up to 27 valid moves, for a worst case of 27*26*25*24*23*22*21 = 4.5 billion legion moves.) Obviously, brute force tree search techniques fail when you don’t even have time to enumerate all the possibilities for a single move, let alone evaluate them all several moves deep.

Another factor is the strategic tension caused by the 7-creature legion height limit. You usually want to kill your opponent’s creatures — except that if his legion is 7-high you might want to avoid killing anything to keep him from replacing it with something better. You usually want to avoid giving your opponent points, but if he’s near a 100-point threshold it might be worth giving up points to a 7-high legion to waste your opponent’s opportunity to acquire an angel. A titan is one of the strongest creatures in the game, so it’s a valuable offensive weapon, but if your titan dies you’re out of the game so it must be protected. Such strategic discontinuities mean that a strong AI will be full of special cases. And exactly when to switch from one plan to another is not obvious.

But the computer has some advantages which can be exploited. It has perfect memory and can be programmed with basic deductive ability, so it can usually know what’s in most of its opponents’ legions. And it can calculate probabilities accurately and quickly.

The Slugathon AI has to make many types of decisions. A few of them, like what color to play or which legion marker to use for the next splitoff, have little strategic impact, so a random choice is fine. But the rest matter and are often non-trivial. There are some very simple heuristics for some game decisions that work well most of the time (only split 7-high legions, always split 5-2 and keep the best 5 creatures together, always carry damage if possible, always acquire an angel if possible, always take the biggest recruit possible, always choose to rangestrike if allowed, etc.), but no simple heuristic will find a good legion move in a battle. So the basic design of the Slugathon AI is random choice where it works, then simple heuristics where they work, and more complicated code where needed.

The first complicated case is splitting 7-high legions. (We have a simple heuristic for the initial 8-high legion, and a simple “do not split” rule for legions with 6 or fewer creatures.) For each of the 6 possible movement rolls, we look at what the potential 5-high child legion could recruit and what enemy legions it could attack. If the recruit is better than the worst creature split off, that’s an indication that splitting helps. If there are any rolls that force combat with a legion that might kill ours, that’s a strong indication not to split. But how do we decide that a legion is a threat? We compare combined point values for all creatures in each legion, modified by fliers and rangestrikers and creatures native to the terrain where the battle would be fought (if the terrain gives natives an advantage), and compare it to our own legion’s point value scaled by an arbitrary number.

The next complicated case is masterboard moves. The server tells us the movement roll and we enumerate all possible moves for each legion, plus the option of not moving. Then we score each move using four factors: the point value of an enemy legion in that hex that we think we can easily kill, the negative point value of our own legion if there’s a bigger enemy legion in that hex that might kill it, the value of any recruit we could muster, and the chance of being caught and killed by any enemy legions that could reach that hex in the next turn. If the overall score for a move is positive then it’s a good move; if it’s negative then it’s a bad move. If it’s the first turn and we have a mulligan remaining and there are not enough good moves for both of our legions, we take the mulligan. The rules require moving at least one legion every turn, so we take our top-scoring move regardless of whether it’s a good or bad move. (Sometimes we have to sacrifice an unimportant legion so that the more important legions can survive.) Having made our one required move, we then recalculate possible moves (because moves to the just-taken hex are no longer valid, and teleport moves are no longer valid if we just used our one teleport per turn), and keep moving legions until we’re out of legions that prefer moving to staying in their current hex.

The next important decision is the order in which to resolve engagements, if there is more than one. The first rule is to fight with angels first, so that they can be summoned into other battles. After that we fight in descending order of legion value, so that more important legions get the first shot at summoning an angel. Other factors that could be taken into account are our current score and the point value of enemy legions, so that we can avoid going over a 100-point threshold with a 7-high legion and losing the chance to acquire an angel.

Once we start an engagement, a fairly easy decision is whether to flee or concede. Currently the AI flees when allowed if completely outmatched by the enemy, and never concedes. It does not currently know how to negotiate, so if neither side flees or concedes it always fights.

Once the fight begins, the decision of how to move our creatures is the most complicated in the entire game. As previously mentioned, the branching factor is overwhelming — we just can’t enumerate all the legion moves. So we need a heuristic to throw away the vast majority of possible moves and only consider a few, while hoping that the ones we consider include some good ones. The heuristic I chose was to initially score individual creature moves in isolation, rather than full legion moves. (Of course this score is less accurate because the creature can’t take its allies into account.) So rather than up to 27*26*25*24*23*22*21 = 4.5 billion legion moves, we only have to consider up to 27 * 7 = 189 creature moves. For each creature, we score all its individual moves and keep only the best 7. (7 because with 7 creatures in a legion, the least important creature may have to settle for its 7th choice if 6 more important creatures take its first 6 choices of hexes.) Once we consider only 7 moves per creature, the worst case is only 7 ** 7 = 823543 legion moves. That still might be too many to evaluate them all quickly enough to avoid boring our opponent, so we randomize the order in which we evaluate them, and stop evaluating when our timer runs out and settle for the best move we’ve found so far. Finally, when we’ve decided on a legion move, we need to decompose it back into creature moves and try to figure out a move order that lets all our creatures reach their assigned hexes legally without getting in each other’s way. This is a simple brute force combinatorics problem: we try every permutation of move orders until we find one that works (any order that works is equally good, so we can stop there), or, if none works completely, we take the one that lets as many of our highest value creatures as possible make their preferred moves.

Strike decisions are easier than movement decisions, because each creature typically only has a few choices. First creatures that are engaged with a single enemy and thus have no choice of targets make their strikes. Then creatures that are engaged with multiple enemies need to compute what they can likely kill. The rule of thumb is to hit the best creature that you and your allies that haven’t struck yet can likely kill this turn, if any. If you can’t kill anything then go after the target that you can do the most damage to. Once all the creatures have computed their possible damage, we have the least powerful creatures strike first, so that the more powerful creatures have more information available when they choose their more important attacks. The AI does not know how to take strike penalties in order to carry; it always strikes at full effectiveness at the primary target.

Carry decisions are similar to strike decisions: the AI chooses to carry to the sole target when there’s only one. If there are multiple targets then it carries to the best one that it can kill. If it can’t kill any, then it carries to the hardest one to hit, since hits on a skill 4 creature are more valuable than hits on a skill 2 creature. (When deciding what to attack, this is countered by the fact that the skill 4 creature is harder to hit, but when deciding to carry this is no longer matters.)

We currently use very simple heuristics for angel summoning and reinforcement: we take the best angel and the best reinforcement (considering only combat value not future recruiting value, so a gorgon beats a cyclops) available.

And we use a similarly simple heuristic for recruiting: take the best creature available, so again gorgon over cyclops. This is good for survival but not always optimal for long-term recruiting, so eventually this should be refined to sometimes take the inferior creature with superior recruiting potential, when safe.

We’ve covered the basic algorithms used, but not the exact evaluation functions for deciding that one hex is better than another. The problem is that there are multiple factors that go into this, and it’s not always obvious which should dominate. For example, a creature that goes into melee with an enemy might damage it or kill it (good), but in exchange exposes itself to being damaged or killed (bad). So we add points for damage that we can do and subtract points for damage we can take. We add points for attackers going forward (because cowering will lead to a time loss), but add points for defenders hanging back (because cowering leads to increased chance of surviving to turn 4 and gaining a reinforcement). We give points for being next to allies, for being in terrain that gives a bonus, etc. It’s clear what is good and what is bad, but figuring out precisely how much of a bonus or penalty to give for each situation is complicated. That’s where machine learning comes in.

The idea behind machine learning is that you randomize some parameters, and then test to see which versions work better, and repeat, in an effort to find the best possible values for the parameters. We have a SQLite database with game results, and calculate a TrueSkill rating for each AI based on its wins and losses against both human and AI opponents. (The AI plays faster than humans and doesn’t get bored or tired, so most of our training games feature all AIs, but games against humans count too.) Each AI has 28 parameters, each of which is a floating-point number, positive for a bonus and negative for a penalty. The initial values were selected by hand, with the initial pool of AIs getting random values within 20% of the default for each parameter. Then those AIs play a bunch of games, and their TrueSkill mu (skill value) and theta (standard deviation of the skill value) gradually change to reflect their wins and losses. (Some of that is undoubtably due to luck, but some of it should be due to their parameter values.) An AI is included in the training pool until its theta goes under 1, meaning we have confidence that its mu value is close to a correct reflection of its skill level.

When we run short of AIs with theta greater than 1, we breed new AIs using a genetic algorithm, where only “mature” AIs with theta less than 1 are eligible to breed, and each AI’s chance of being a parent was proportional to its mu. (Survival of the fittest.) Once we choose two parents for a new AI, we determine the new AI’s parameters from those of its parents. For each trait, there is a 1/3 chance of inheriting the father’s value, a 1/3 chance of inheriting the mother’s, and a 1/3 chance of averaging the two. Finally, after all the new AI’s traits are set, we randomly mutate one trait by up to +/- 20%. This mutation is designed to get away from a local maximum that may not be the best possible value, and to allow values to potentially drift farther away from the initial defaults than would otherwise be possible.

After many training games, we end up with a pool of AIs, some with very high mu which should be good opponents for human players, and some with very low mu which should be retired. But it’s important to keep in mind the limitations of the machine learning system: it’s only tweaking score values within the AI algorithms, not writing new code. It can only help so much; a bad algorithm with highly tuned constants will not beat a better algorithm. (As a great philosopher once said, “You can’t polish a turd, Beavis.”)