On AI Design

By Mike

A friend of mine recently asked me to explain AI design, specifically with respect to predominantly Player vs. Player, turn-based games. Duels of the Planeswalkers, we’re looking squarely at you. He wondered how easy or difficult it was to fine-tune it to where it seemed sensibly challenging given the intended difficulty level without being too good. The question demands an answer more detailed than I could contain in the text messages we were trading, so here on Infinite Wrench I figured I’d try to cover the full scoop.

First, the basics. AI as we know it in any game tends to be organized by way of a “finite state machine.” The AI’s potential actions are planned out based on a series of “states” that it can be in. They might be as broad as “moving” or “attacking,” they might be as fine as “aiming,” or “selecting weapon.” The AI goes through a continuous loop until it’s shut down (usually by way of death), stepping through these states. Within each state, it performs an evaluation of its present situation and eventually settles on an action, and then transitions into other states as it is allowed.

In a real-time game, AI may loop through a single state or transition between several of them dozens of times in a second. Additionally, actions may be assigned a “cost” in order to help the AI both to determine a path of least resistance and to keep it from being too smart about things. Think of it as a way of managing action points, essentially saying “you can climb over that wall and fire a pistol, or you can stay down here and fire a machine gun — but you can’t do both.”

AI design of any kind is all about attention to detail. Turn-based games and board games are highly structured and highly abstract, and therefore create a framework that’s ideal for developing very complex AI with excellent situational awareness. The rules for players are extremely orderly and explicit, as opposed to the rules for a simulation, which can be very vague and open-ended, and therefore making something that can act on par with the player can be broken into very explicit building blocks as well.

Attention to detail here is something that’s time-consuming, but straightforward. The states can be organized in terms of phases in a turn, and the potential actions can be organized in terms of legal actions during those phases. The evaluations for those actions don’t require as much heavy lifting as you would see in a more simulation-oriented game; the AI need only look at the board.

Dealing with hidden information, like a concealed hand of cards, or the other half of a game of Battleship, is naturally a challenge, because it depends on deduction, guessing, and psychological mind games that a computer isn’t capable of. Because of this there are any number of places where some R&D and creative abstraction is required to simulate an AI opponent’s capacity for guesswork, but this is still less problematic than in a full-blown real-time simulation, where limiting the AI’s awareness and making it behave realistically is a constant, losing battle involving vision cones, hearing radii, relative distances, pathfinding (OH THE PATHFINDING), and a huge myriad of vaguely defined potential actions.

In short, turn-based AI can be a lot better at a much cheaper price. It’s easier to simulate another player in a highly structured board game than it is to simulate a person or animal in a virtual world. The game’s rules have done the hard part of abstracting and structuring your AI’s actions for you.

But there’s a lot of ways to oversimplify this, something that my friend Joe touched on in a short rant about Duels of the Planeswalkers. His question specifically was: “how do you know how aggressive, or intelligent or cheap to make it without making it unfair or too stupid?” having observed that Duels of the Planeswalkers seems to do only one or the other (having played it, I concur).

There’s several factors that potentially contribute to this.

Factor 1: AI Skill Level

We tend to imagine difficulty on a scale of “easy, normal, hard,” and potentially degrees of difficulty beyond. For players this is an ideal representation of how difficult their playthrough ought to be, but for AI designers this is a vast oversimplification.

You want to present these difficulty options to the player, but you want a much larger sliding scale to provide a higher degree of control — the reason being that, while you’re going to provide multiple difficulty levels, you also want to be able to increase difficulty and AI sophistication throughout a playthrough. It’s actually a much better practice to define a scale along the lines of 1-10 or, better yet, 1-100, or even a byte from 0-255.

Your “Easy,” then, isn’t a single number on this scale; rather it represents a range, say, 0-50, describing the minimum and maximum difficulty an opponent could potentially have assigned to its individual AI. Medium might be something more like 30-100, Hard might be 70-200, and so on. The AI can check its personal difficulty value at various points to determine whether a more advanced action should be taken or not, and this will generally produce a much more sensitive difficulty scale rather than a sharp brick wall.

The difference between the AI knowing whether or not to use Giant Growth as an Instant (during the opponent’s turn — advanced strategy) or not shouldn’t be “do that on medium,” which is too broad. Rather, it should be “difficulty > 40” or something along those lines. Thus, the easiest opponents on medium won’t do it, but more advanced opponents as the player progresses through medium difficulty definitely will, creating a more gradual skill progression within that difficulty.

Factor 2: AI Cheating

Sometimes the answer to that whole, “how does the AI guess or make deductions?” question is “let the AI cheat a bit.” Don’t be so naive as to think the computer doesn’t know exactly where your boats are in that game of Battleship, or that it doesn’t know exactly what deck you’re using in that game of Magic. Probably the reason that Duels of the Planeswalkers doesn’t let you build your own decks is precisely so that you never build a deck that the AI doesn’t know how to deal with.

It probably doesn’t know what exact cards you have in your hand at this moment, but it knows which deck you picked and what to watch out for when it has that Counterspell in its hand — something that most of your friends won’t know without playing you several times. It’s one thing for the AI to say “if I let him play that card I’ll take too much damage, I’d better counter it,” evaluating a card you played at the instant you played it, but it’s another thing completely for the AI to say “I’m waiting specifically for him to play one of the dragon cards that I already know are in the deck. I will only ever counterspell those.” It’s a reasonable strategy if and only if the computer already knows the deck you’re playing, and the only reasonable countermeasure is to know what the computer’s deck is.

Then again, it might know every individual card in your deck, its deck, the exact order in which those cards will be drawn, and what’s in both players’ hands. It might have specific card combos on file that it’s waiting for, and when planning to play certain cards it might check the top 3 cards to see if another card in its key combo is coming up so that it knows when to save a card and when to play it with ridiculous acuity.

It’s hard to say what the case may be, suffice it to say that either of these options and virtually anything in-between is a cheap shortcut that results in a seemingly superhuman, precognitive opponent with an unfair advantage. On the other hand, deductive reasoning and strategy recognition is extraordinarily difficult in a game that’s as diverse as Magic, which has an extensive metagame…

… But then, Duels of the Planeswalkers is Type II, with a limited portfolio of cards and well-documented strategies among the Magic community at large as well as the Wizards staff for the few expansions that Type II uses at any given time. The play styles for Magic, meanwhile, are diverse, but not that diverse, and it isn’t unreasonable to say to the AI “if you don’t recognize a strategy, just follow your own game plan and don’t bother trying to adapt.”

Surely the AI could have been given metagame recognition skills and some modicum of playstyle recognition, recognizing whether it was looking at burn, control, stompy, horde, defensive, etc. within the first five turns or so (if it lasts that long). If the computer guesses your strategy wrong, guess what? That’s incredibly satisfying! That’s the kind of thing you love to do to screw around with real life players!

That’s one of these little touches that I don’t think a lot of AI programmers realize — sometimes the key to making a satisfying AI to play with isn’t so much making them smart or challenging, it’s making them stupid, albeit in a realistic way that players find satisfying to exploit. Any game studio should be so fortunate, however, to have the luxury of being able to research and implement this. As I’ve said before, sometimes you have to settle for “good enough,” and this is probably the first place a digital board game designer is going to cut corners in the interest of getting the game done or insuring a sense of challenge.

Factor 3: AI Play Style

Not all players get pleasure from playing and winning in the same way, which is a foundational aspect of Magic: The Gathering. Anyone familiar with the game knows that each color — red, black, blue, green, and white — represents a range of play styles in itself, including different sets of creatures, spells, and enchantments. These include concepts like “burn,” wherein you aim to do the most direct damage as possible to another player, “control,” wherein you aim to control how your opponent plays their hand, “stompy,” wherein you emphasize large, heavy-hitting creatures over small ones, and many others. This would be what you would call a deck play-style, in that it emphasizes the way a player’s deck is put together and what their ideal conditions are to set up a win.

In addition to this, the designers of Magic condensed players’ overall play-styles; the ones that emphasize how they think of any deck, not just the one they’re currently playing. They named these Timmy, Johnny, and Steve. “Timmy” refers to the power gamer, the wide-eyed kid who gets blown away by how cool and powerful a card is and just has to have it and, more importantly, use it. “Johnny” is the strategist; he wants to win, and win on his terms, and typically looks at the deck as a whole rather than any individual card. “Steve,” on the other hand, is an oddball experimentalist who just likes screwing with people, emphasizing unconventional combinations of cards that he found.

All of these concepts are way too abstract and high-level to go into any great depth about in this article specifically, mainly because of the breadth that this grid of play-styles represents. Again, this is probably a big reason that Duels of the Planeswalkers only allows for a range of customization of pre-made decks rather than letting players build their own from scratch. It’s certainly why the AI uses pre-made decks. However, the above information covers the broad strokes of information you’d need to understand in order to develop AI for this type of game — both what the AI has on hand, and how it prefers to use it.

The issue with trying to condense all of this into a single AI is just how massive it could get. There are an awful lot of conditional checks that you could be running, and some functions could get to be hundreds of lines of code long. This is where high-level code can come in handy — one of the fortunate things about interpreted code is that it can be composed on the fly, saving a lot of this kind of effort. In the world of Java, for instance, it’s common to parse XML and then build a new class on the fly from the data contained within. With a suitable high-level scripting language for AI, it wouldn’t be all that big of a problem to do the same here, procedurally building an AI class from info like “Blue/White Control, Steve-Type Player.”

Were this factor taken fully into account, it would be much easier to make an AI player seem a bit more “human,” in that it wouldn’t always necessarily go for the most optimal strategy. The deck-strategy would be optimal, but the player-strategy would outline a set of preferences modifying the cost of making one move or another. In short, you could create an AI player that really wants to get their biggest monster out and hasn’t got a lot of patience to do otherwise, ignoring good options and leaving itself open by tapping tons of mana, versus one that’s extremely pragmatic and deliberate about its resources, possibly to such a fault that it barely plays high-power cards. You could break this down into numerous different attributes, but the bottom line is that you have a means of deciding how the AI works based on player psychology just as much as practical consideration.

Factor 4: Polish and Testing

Now for a harsh dose of reality: none of the above tips help. The best-planned AI you can think of can fall apart horribly if it isn’t thoroughly tested and polished. The more complex it is, the harder it is to test and polish, and it can reach a singularity point where you’re never finished writing it. This is when you start cutting corners and think about settling for “good enough.” Duels of the Planeswalkers probably has very thoughtful AI programming put into it, but there’s only so much time to do these things and only so much that can be revealed about it through testing before it’s unleashed upon hapless gamers. Practical constraints on time and budgeting always win out, period, especially on a licensed project.

So, if you’re like my friend who texted me about this in the first place, cut the developers some slack. I know what it’s like to be under that kind of pressure, an I can assure you I probably wouldn’t have been able to implement a good third to two-thirds of what I’ve outlined in this article, which is all theoretical nonsense anyway. Remember, I haven’t programmed any of this myself — all I’m doing is raising a discussion.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s