Best practice A.I. - check all possible moves or pick an objective?

Question

I'm looking for some general guidance on how to produce best practice A.I.

The way I understand it, the way A.I. works for games like Go, Chess etc is by considering all possible moves (combinations of moves multiple turns in advance) and deciding which possible move maximises some given score/utility.

However, I very much suspect that this isn't how, lets say, Starcraft works. I am assuming that the A.I. here would not, for each iteration of code, have hundreds of possible directions a given worker/drone can head (and count up the utility derived from being closer to resources, being protected, having increased scouting etc for each of these possible moves).

I am assuming that instead, the game abstracts down the drones options into specific goals, such as: Gather resource X, gather resource Y, scout, fight, flee and determine the expected utility from each of these, and that once the goal has been chosen, the game calculates a simple rule for meeting the goal, which in most cases would simply be move towards the closest resource source, away from the closest enemy etc.

So, questions:

1) Is the above mostly correct? Or are there other ways that best practice A.I. generally works.

2) What is the primary reason for going with an abstraction, instead of considering utility of all possible moves? i.e. computational load, easier to program, tradition etc.

3) How would one go about deciding whether to build a chess style A.I. or a Starcraft style A.I. for a particular purpose? What sort of considerations come to mind?

Answer 1

There is no such thing as "best practice" with AI. There is what works and what does not work for a given purpose. There are techniques that may apply to a given task, which you did a good job of summarizing in your question.

Taking an RTS such as StarCraft 2 for example, different units have different capabilities. Gathers gather resources: they are assigned to pick up resources spent elsewhere. The AI simply needs to figure out "is there another resource nearby if my current one is busy or depleted?" which is a fairly simple task.

Military units may have commands queued up: move here, attack this, stand around and attack anything nearby, etc. The biggest challenge with these types is pathing: how to get somewhere, not what to do.

Finally there is the AI that may control multiple units, which is what comes into play when you play against a computer opponent either in free play or the campaign. These AIs tend to be a combination of preassigned orders (campaign), build orders (free play), and an AI separate from that used for individual units that acts like a player would be issuing commands to multiple units. This is the most interesting of them all, but unfortunately most of these AIs are proprietary and we may not know for sure how they work.

Real-time simulations certainly have time constraints, and an AI algorithm must be powerful enough to act "smart enough" while fast enough not to impact gameplay performance.

To your first point, yes, you summarized things fairly well. To your next two points, the tradeoff is what I described above: does the computer have the time to consider all moves, or at least a large number of moves? Is there an acceptable tradeoff between speed and intelligence? Are there constraints that help with this, such as specific game entities only performing certain actions? Can a player impact this by e.g. giving instructions to units and allowing limited autonomy?

Answer 2

Not an AI expert, but I do know some things about AIs in general, and about chess AIs.

First, let's indeed note that there is no "best practice" for AIs, they can work in many different ways. Some approaches are better suited to some problems, and some problems have many viable approaches.

Now, no, games like chess are definitely not played by considering every possible move up to a certain depth. The problem is that exponential growth is something that's easy to underestimate, but the amount of positions becomes too large to compute. After two full moves in chess (white and black have moved), there are almost 9000 possible positions, and over 9 million after six moves. Considering all the possible moves even up to a fairly small depth is not feasible.

On chess AIs

Therefore the major issue in chess AI is in fact that of which moves not to consider. There are many different approaches again to that problem, one very notable approach being the combination of minimax and alpha-beta pruning. You can read about these on Wikipedia for a simple introduction or other sources for more in-depth considerations. Minimax is essentially an algorithm for considering moves up to a certain depth and then choosing the best move in the current situation, and alpha-beta pruning is an algorithm that removes certain paths from minimax. Then there are further smart improvements like considering moves in a specific order so that some paths may be cut from evaluation sooner. In practice advanced refinements of these techniques are used.

Advances in these heuristics have, in recent years, made chess AIs far more powerful than before. Consider that not so long ago it took a supercomputer to beat a top human. Deep Blue beat Kasparov in 1996, and it was a purpose-built computer. But ten years later, in 2006, Kramnik was playing versus Deep Fritz, and it ran on a powerful Xeon-based computer, but it wasn't a supercomputer or anything special-built, it was a typical high-performance computer like what might be used for a server. And since 2009, the HIARCS chess engine has been able to provide strong results running on mobile devices, almost entirely due to smarter algoritms - the amount of positions considered was very low. By now, only the top tier chess players would stand a chance at beating the best programs available for Android. On a decent desktop computer, even top grandmansters do not stand a chance.

One example of such huge recent advantages is the null-move heuristic. It lets a chess AI consider a null move (that is, not moving anything, which is illegal in chess). The basic idea is that if you could make a null move and still have a strong position, then making a move would likely give an even better position.

Note: end-game tables do get used by chess AIs. For end-game positions with few remaining pieces, they have been solved exhaustively, and so optimal play can be looked up. A current chess AI will always play optimally in a six- or seven-piece endgame position.

On StarCraft

All of this is completely different from how something like StarCraft works. A StarCraft AI is largely about pathfinding (a very challenging problem, and anyone who's played RTS games has probably seen AI "misfires" such as units getting stuck or running around in circles), and about some real-time estimation of the situation. The nature of a RTS game forces the AI to be able to think fast. So the AI would be using various formulas for rough estimation. For example, given its army against an opposing army, it would have some kind of formula that can be quickly used to calculate the expected outcome, and then the AI makes a decision to fight or withdraw based on that. In the meanwhile, the AI aims to keep training workers as long as it's not utilizing resources in the maximum possible way.

Of course, a StarCraft AI can also follow different strategies. It can aim to maximize resources, which would result in something like a fast expansion, or it can aim to minimize time to an attack, which would be a rush. Then there are also other techniques used such as calculation of "danger areas". The AI consders some areas to be in danger, and others to be defended. This guides, for instance, its construction of anti-air turrets.

Chess and StarCraft provide a very good example of how AIs can be very different. A chess AI will sacrifice speed for intelligence - it's normal under tournament conditions to consider a move for minutes. A StarCraft AI will sacrifice intelligence for speed - it has to think quickly enough to provide an enjoyable real-time gameplay experience. A chess AI puts a lot of effort into evaluating positions, a StarCraft AI will do a much more rough estimation of which force is stronger. In chess, the entire position on the board is always known, in StarCraft, there are unknown elements.

StarCraft (both games) has been quite interesting for AI. AIs like Overmind that won the 2010 AIIDE are interesting from a research perspective. You could Google for "Stanford Starcraft AI" to find a few interesting AI projects for StarCraft and the sequel.