When AI is plenty A, but not so I

Normally one of the parts I like best about writing a strategy game is implementing the computer opponent. Trying to find a balance between heuristics and raw CPU horsepower is almost as much fun as playing an AI-enabled game and losing to it for the first time.

In Praetor, though, the AI is a pain in the ass. The problem is that each player has way too many options.

Consider chess: on the opening move you have 20 different moves from which to choose. A computer player could pick the best first move by simulating the board after each one of those 20 moves, and deciding which of the resulting boards looks the best. Not so bad, right? Just 20 moves to consider--can't take too long. That's called a "1-ply" search.

But regardless of the computer player does first, the second player then gets a turn--and he likewise has 20 moves to pick from. If the computer player wants to consider his opponent's responses, then for each simulated move it makes it needs to consider each possible response by the opponent. That would be a "2-ply" search, and it means the computer would be setting up and studying a total of 400 boards to decide which first move is probably best. As the game progresses the number of options each player has will increase a little because the board opens up, but then it also starts decreasing again as pieces come off the board. If we average those effects and assume that each player always has roughly 20 moves to choose from, then a 3-ply search would require the computer to consider 8,000 boards, and a 4-ply search would involve considering 160,000.

In Praetor, an average piece has about 18 squares to which it can move--maybe limited to 12 in a typical case because of terrain or other pieces being in the way. The player can play cards from his hand, and most cards either let you pick a target piece or square to manipulate. Some pieces have special abilities they can invoke, and others will happen to be within range to attack enemies. And here's the real pinch: most actions a player takes use up some energy, and a player's turn continues until he runs out of it. So instead of just picking which single piece to move or card to play, a player needs to pick what order to do those things in for each turn. Is it better to move then play this card, or play this card then move?

All those options mean that, just a few turns into the game, a player typically has millions of possible ways to play on each turn. Which means that even a simplistic 1-ply brute force search is out of the question (remember, the first release vehicle is a cell phone: not much CPU to spare). So what to do?

Heuristics to the rescue. A modern chess AI for your desktop will easily walk 8- or 9-ply deep--that would be 512 billion chess boards if it were walking that tree brute-force (e.g., considering every option). There's no way that's going to happen, which means chess AIs also rely on heuristics to prune that vast tree of options.

The goal of heuristics is always the same: to quickly identify probably-pointless moves and discard them, so you can reduce the number of choices that you have consider at each stage. With Praetor, since the game tree is so wide, I need to rely on heuristics that prune pretty heavily in order to get good moves in any kind of reasonable amount of time.

The first heuristic I've chosen is the most drastic: instead of considering in depth the result of moving every piece to every square, I'm going to have the computer quickly consider each square and pick exactly one to consider in depth. That immediately reduces the millions-of-options-per-turn to just hundreds-of-options-per-turn. I also plan to heuristically restrict where particular cards can be played: no point in sending a fireball there since it wouldn't hurt any opposing pieces, nor there since it would hurt mine. Sometimes sacrificing a piece would let the AI win the game six moves later on, but most of the time it's dumb so I won't even let it look.