One thing I've been researching lately is how to theoretically build "perfect" AI for a strategy game. My gameplay goal isn't to build unbeatable AI opponents, but I thought if I could figure out how to build a perfect AI player, even if it's impractical with today's technology, that it might teach me how to build the right kind of AI I want.

If we assume a very simplified version of a strategy game (simpler than chess), where each player can allocate a unit of time (a turn) to resource acquisition, unit production, scouting, unit movement, combat, etc., and if the goal is to win the game at all costs (i.e. maximize the chance of victory), then how does one theoretically compute the mathematically ideal strategy? With a simple enough model and perfectly balanced sides, I imagine this should be possible. Perhaps some kind of min-max algorithm could be used, where each AI player attempts to make the best possible move with each time unit while assuming its opponent will make the best possible counter-move.

Sounds ok so far, but I haven't even begun to understand how a computer player could algorithmically assign a value to each possible move. How do you know when it's better to scout the terrain vs. to increase resource production vs. to attack the opponent? Obviously the answer may change based on how these factors in the game are weighted, but how can these choices be related mathematically?

Does anyone know of any resources, books, or articles that address any of these issues?

Interesting problem, I have a few ideas, but I have a question for you. Does your AI have access to the entire gamestate? or is it's view of the opponents the same as a human players. I.e. do they have to search for resources, discover enemy bases, and do all the other things that a normal human opponent would?

Also, If I was to go about making a strategy game AI, the first person I would talk to would be brad wardell. He's an indie of a different breed, but indie just the same. He's very responsive and he also happened to write 5-6 different AI engines for his critically and commercially successful 4x strategy game "Galactic Civilizations".

His AI's play exactly as a human player would with the same view of the game state as another human player, but they can match human players in cunning, even to the point of being extremely difficult without actually "cheating”.

Here's a web page that has a wealth of game programming information that you may find useful. Articles from shortest-paths to economics are covered fairly well. Have a look.

http://www-cs-students.stanford.edu/~amitp/gameprog.html

AI Wisdom Book (http://www.amazon.com/exec/obidos/ASIN/1584500778/102-4139947-1838567)

Very good book. Chapters are basicly split into the different problems you come across with AI in games. Mainly aimed at FPS / RTS games with a pretty even split between both as well as some stuff on racing games and other genres. All the information in here is from a game design point of view with some source and examples included on the CD. I'm in no way affiliated with the editor of the book, nor have I contributed to the book in any way. All the articles are written by various game design / programmers. Check it out, makes an interesting read and also gives you some handy hints and solutions to common AI issues.

At the highest level, there are two problems associated with strategic A.I. based on Zero-Sum game theory.

The first problem, move generation is about searching and describing all possible moves for a given player at any given time. (If you want to better understand this, I suggest doing this with pen and paper for tic-tac-toe). For something like an RTS game, you couldn’t possibly calculate all the possible moves for all players for N-ply in real-time.

The good news is you can use alpha-beta pruning to cut-off all unenforceable-undesirable branches of the game tree (i.e. When you know you can do better, stop searching a worse off branch). The bad news is there will be far too many possibilities past a N number of ply (search levels) as this leads closer an closer to infinity.

The second problem, The Scoring Function is about estimating an accurate score for any game state. In a prefect game, you would predict all possible moves for all players, and thus solve all possibilities. (Then you would know if you can force the game into a win for you, a tie, or a loss for you.)

Realistically you search a certain number of ply (for a real-time game, this would be a combination of time and movements) ahead and then use a score estimating function to score the game. How you implement that for an RTS could be based on two obvious things: Physical Score ( Resources+Uints+Building etc) and Positional Score (Where those units are positioned on the game map and what that values at)

The physical score is easy to calculate, assuming you assign value for each resource. The Positional Score is more difficult, because you need to use the environment such as the units relative distance to your other units, the terrain type it rests on etc.

There are some good articles and post mortems on Gama Sutra (http://www.gamasutra.com) and in the Game Developer Magazine (past issues). The Game Programming Gems Series and AI Game Programming Wisdom books have some good articles about RTS architecture - you’ll need to get them if you don’t already have them.

From what I know, almost all recent RTS style games use (at some level) scripting to make them appear intelligent. Your best bet is scripting base and unit building, and then using real-time scoring to adjust your units actions.

Wow, I packed a lot into this post.

Michael Sikora
Guardian Light Studios (http://www.guardiangames.com)

@Dan: I'm actually looking at this as a problem where two AI players challenge each other. But they would both be subject to the same rules and (virtual) interface as human players. In this case I'm assuming that there's a fog of war, whereby the contents of an unscouted tile aren't known to the players. But once a tile has been scouted, it is permanently revealed. So scouting provides permanent information once it's been done.

Scouting should really be done periodically to update gamestate data. If the computer player could still see resources being depleted by the opponent at a previously scouted but currently non-visible area, that could be considered as cheating.

The AI could assume the resources etc are still at those locations, but should consider re-exploring to confirm the old data, much like a guard patrol.

Perhaps a value could be given to the overall figure for possible remaining resources out of the overall found resources i.e. it is safe to assume that 75% of resources are still going to be there. However, maybe have a variable for each resource/whatever that increases with time. The longer it has been there are not been reconfirmed, then the likelihood that it is still there is greatly reduced. This would also provide you with the locations to re-explore, as those areas of interest would have the highest chance of a changed-state / oldest visited.

As for determining some kind of score for what your perceived move might be (so as to try and suprise the enemy) I would try and keep track of how much I knew the enemy had seen. If an enemy scout is seen at one side of your camp, it would be possible to caluclate how much of your army / land he had seen, and what part of it was still invisible. Calculations for the perceived move should be based on this figure (with exprapolation for the hidden and unexplored world)

-Z-

Here's an alternative method I thought about ( i haven't tried but i'm pretty sure it'll give some interesting results. )

Play the game with multiplayers, log all the information, generate some statistics out of that, generate a look up table, and use this look up table as a computer AI.
The cool thing is that you can autobuild this look up table as the player plays ( it's actually using the player's AI to generate the computer AI )

Of course, it's easier said than done...

Just my 2 cents.
pat.

Steve, I think you are looking for genetic algorithems.

The idea is basically, generate a DNA of the properties and priorities youre looking to adjust, like (scout 7, harvest 2, defend 10 ...) and clash the generated AIs youve created.

what you do afterwards, is create a next generation AI from the AIs you tested according to their success. Meaning you hybrid the last generation properties and priorities according to its winnings. do that while combining a random element to create a variety of qualities.

why do this darwinistic approach?
because there are varius of ways to achieve victory, and even when everyone has property of attack=10, the next generation will have other different qualities.

anyway, lookup for genetic algorithems.

http://www.gameai.com/

Depends on the strategy games, but I found that studying real world tactics and strategies (combat, economy, diplomacy, etc) provides you with a better way to create a good strategy AI. Currently working on a squad based game and all the AI code is simple wnough without using advanced AI techniques, but is able to perform outstandingly well due to the relationship of actions (from squad) and events (world) and using goals (level info).

edit: I forgot to mention that I spent about one month doing research on military and police behaviours, reading available manuals and watching old news of riots, war, etc. This made it alot easier to model the AI on the game. Heck I even bough a rifle for field targeting shooting and to see how movement with and without a gun (along with concealment) is different.

Let me add another plug for the AI Wisdom book and Amit's page as well. Genetic algorithms sound right for tuning your scoring function or even brute force if the search space is small enough. But I think that the better way to go with Akura's suggestion. Mimic the behaviors of excellent players. BTW the game you describe does not strike me as simpler than chess. Limited fog of war, resource acquision, unit production - sounds much more complicated (at least from an AI standpoint) and even chess hasn't been "solved" yet.

Jack

I once read a great article about squad based AI handling, but alas I can't find the link anymore.

It was basically talking about hierarchical levels of control. So instead of one AI that does everything, there are multiple AI systems running each with their given abilities and control sets.

One superior AI would dish out the commands to the lesser AI controllers according to needs based rules. EG we need food, tell the econmy AI to get food. Then the economy AI would be responsible for sending gatherers out to find food and report back tot he superior AI when enough food is gathered.

The article then went on to discuss military AI in the same manner, whereby a "general" would control the next tier of AIs such as the captains. The captains would control a battalion and the saergents would control indivudal groups. So the general would say "attack point A" and ther captains would divvy up the troops into groups assigning seargents to each and then give them specific orders (EG group A attack direct, groups B and C flank). Then the seargents are responsible for immediate stimulus response actions such as defending the artillery or striking at the bowmen with cavalry, etc.

If you take the ideas above and apply them with the genetic algorithms ideas suggested before, you could develop a very strong AI. The hardest part will be getting a good balance in the superior AI that controls all other AIs. The needs system needs a lot of tweaking by someone that knows the game inside out. GA for needs based AI tends to result in purely offensive AIs unless they are programmed expertly.

Sounds ok so far, but I haven't even begun to understand how a computer player could algorithmically assign a value to each possible move. How do you know when it's better to scout the terrain vs. to increase resource production vs. to attack the opponent? Obviously the answer may change based on how these factors in the game are weighted, but how can these choices be related mathematically?



What you're describing is similar to the basic chess move evaluation functions. It's a composite of a variety of factors. In chess, for instance, losing a piece is bad. Putting the opposite king in check is good. Making a move that prevents you from being able to castle later is bad. Each of these conditions has a weight. For every move, all of the conditions are checked for added together, giving a final value for that move. Different games will have different conditions.

For your game, for instance, you may assign a value for how far away a unit is in from it's home base, how many friendly troops are nearby, how much damage a unit has and whether or not the base is under attack.

Tweaking the individual values would normally be time consuming and difficult to gather metrics on, but if you could setup a harness where two AI players play each other, then it's much easier. Make a tweak to one of the AIs and run ten games. Was there a significant advantage? Another tweak, ten more games, check the result.

I have links for quite a few articles on chess engine development that I can post later (they're on the other machine). If your game is turn based, you can't go wrong with looking at chess.

I agree with Gilzu, I was going to propose genetic algorithms. This might have a pitfall - training a genetic algorithm takes many, many iterations to converge, so you will probably do AI vs AI for the training. This might produce AI players that are very good against other AI players but not against humans! The best way to do this is to train the algorithms vs real humans, but it may take too long.

To get done AI like that you would have to be familiar with at least one of these two phrases:
-fuzzy logic
-game theory

:)

Originally posted by JackNathan
Let me add another plug for the AI Wisdom book and Amit's page as well. Genetic algorithms sound right for tuning your scoring function or even brute force if the search space is small enough. But I think that the better way to go with Akura's suggestion. Mimic the behaviors of excellent players. BTW the game you describe does not strike me as simpler than chess. Limited fog of war, resource acquision, unit production - sounds much more complicated (at least from an AI standpoint) and even chess hasn't been "solved" yet.


I meant mainly that the unit types would be simpler than chess. I.e. only one type of unit which moves 1 title per time unit, has one attack per time unit, always does 1 HP damage, and costs 1 unit of resources to create. So the game is reduced to having only one resource, and one unit type, and perhaps a single structure (a home base) to defend. I thought that by studying a dumbed down model of a strategy game, it might give me some ideas on how to expand the ideas to a more complex one. For instance, if I could gain a relative understanding of the indirect relationship between scouting and resource acquisition, I think it would allow me to build a better AI player who also has an understanding of this relationship.

Originally posted by gilzu
Steve, I think you are looking for genetic algorithems.


I thought about using GAs for this, and I've done some simple experiments with them. My Comp Sci degree involved a specialization in AI, so I'm familiar with most of the common AI techniques. What I don't like about GAs is the potential for gaps in the AI players' knowledge base. When a GA-generated player tackles a human player, there's a good chance the human will come up with a novel approach that the GA never experienced. And then that same tactic may end up being successful every time.

Nature has evolved many different species, but most are no match for man, as we're driving many of these species to extinction every day without even trying. So I'm concerned that if a game AI is evolved without any contact with human players, it will simply not be prepared. And of course the problem is that contact with human players is extremely time consuming.

I think GAs could work in limited subsets of the AI though, such as squad-level tactics.

Originally posted by damocles

It was basically talking about hierarchical levels of control. So instead of one AI that does everything, there are multiple AI systems running each with their given abilities and control sets.

A couple years ago I gave a talk on this subject to the Los Angeles ACM, explaining how a tiered game AI could be broken into strategic, tactical, and unit-level AI. Since the talk was given near LAX, many of the attendees were aerospace engineers who'd been involved in DoD projects. So during the questions period it was no surprise that someone asked if the AI for a strategy game could be adapted to real-world military applications.

I said that it wouldn't adapt directly because the goals of game AI are incongruent with military goals. Game AI is designed to entertain, while military AI would want to ensure an efficient victory. I added that if game AI were used in the field, you'd lose all your battles, but they'd be realy fun to watch. :)

Originally posted by Morphecy
To get done AI like that you would have to be familiar with at least one of these two phrases:
-fuzzy logic
-game theory


I've studied both. One approach I was considering would be an expert system where the rules are based on fuzzy variables. I.e. "if resources are low and resource gathering priority is low, then increase resource gathering priority to medium." So the top-level strategic AI would work this way, and then it would dispatch commands to a tactical-level AI, which would do the computing necessary to implement them or to report back that they can't be accomplished. This would require a bunch of different evaluator functions to compute the fuzzy variables.

The benefit of this approach is that a human being could more likely write the rules to cover all the high-level strategic situations. For instance, what would a human player do if resources are high, units are high, camp is well-defended, and enemy is weak and nearby?

I understand what you're trying to do Steve, reduce an RTS to a deterministic system and then write a system that can plot the shortest/best/most effective path to a victory condition. The problem is that the possible actions, resource acquisition, scouting, moving, attacking, and unit production do not lend them selves well to a deterministic rule based system.

I know you're familiar with GA's and ANN's and they do provide a partial solution. But the problem with that path is that those algorithms need to be trained. They need a start condition and an ideal solution so that they can minimize error in their system. After repeated training against a large set of data they being to produce "Reasonable" results. However this doesn't really solve your problem. You still have the issue of trying to determine what the ideal result of each initial condition is so that you have valid data to train your algorithms with.

One suggestion is to have a human player play some games perfectly and record the results as an input set, but we all know that's impractical and for the most part impossible. I think what you are looking for is an elegant way to turn this very simple RTS system into a deterministic system. Frankly I don't think that's possible. Simply because there is no easy way to assign the relative value of scouting vs. attacking for instance.

There may be some formula needToScout = timeSinceLastScout - ((numberOfEnemiesDiscovered / totalGameTime) * someScalar). However I don’t believe these simple formulas can be generated without a fair amount of statistical analisis to get the correct scaling factors as well as the correct variables that influence somethign like the need to scout. Once you have those formulas defined then it becomes almost trivial to write a deterministic system for what to do next.

I’m no mathematician, not by a long shot, but in short I don't believe there’s an elegant way to evaluate the 5 or 6 simple choices at any given state in the game and know their long term consequences. Or even know what the "perfect" move is given the available data, because the evaluation formulas for the weights associated with each more are very difficult to come up with. DeepBlue tried to do this with chess, and did it by evaluating every possible game combination and doing some evaluation of the probabilities of each occurring based on the current game state. It took a while for it to make a move, you can't be doing that 4-5 times a second in an RTS. Even a simplified one, plus that doesn't really help you understand what the best move is at any given time.

Another factor is that the AI system will have to make the best move on the amount of information it has available to it. That may not be the best move overall since it may not have accounted for the huge army amassing just outside it's base in the fog of war.

So I don't think there's an elegant solution to your initial question.

Just in my observations from playing RTS games, I believe the approach that most games take to AI players is to have them play similar to human players. There are several different AI strategies, Rush, Turtle, Mid game assault, Late Game assault etc. The AI starts the game with one of these strategies in mind. Now it's much easier to do the evaluations of what to do next, because it's not based on the available data as much as it is the AI's strategic stance. For instance, if it's an early rush, there's a very high need to produce units and locate the enemy. And a smaller need to build buildings and find new resource sites.

If it's a mid or late game assault tactic, the needs for locating more resources expanding and scouting need to be more balanced so that they can accomplish all these tasks. If the AI suffers a huge loss or its current strategy isn't working, It can switch over to the base building + unit production AI, or the "Attack his base while he's in mine with all my remaining forces" AI. The various AI systems now take care of the move to move details because they are now goal based, or need based depending on how you look at it. But the needs are defined by the goals not the set of available information on the game field. This makes it much easier to make moves.

The only evaluations that need to be done is to determine what is the best possible tactic to switch to when one AI system isn't working. This can also be goal based; you can give your AI's personality. One always retreats and defends, the other always attacks or some place in between. With testing you may actually be able to discover some optimal AI changing tactics; it's certainly more feasible then trying to discover the optimal move for every move in the game.

If you have the means to get to Austin TX by August 21st there's always the AI Game Development Workshop:

http://dmc.ic2.org/conf2003/index.php

Perhaps you should allow a slight 'cheat' for the AI? The goal, as you said is to make the game fun. Unlike for a military application, where it is to win as quickly and as efficiently as possible. Build a reactive AI that always knows what the other player is up to, but is a couple steps behind it all the way. That way, no matter the strategy employed by the opponent, the AI will be able to not only have a halfway decent counter, but will be a challenge every time.

Consider a case where there are two unit types. Archers and infantry. Each is a counter to the other and each has the same power, movement, etc. If a player builds a ton of archers every game, maybe the AI should 'know' what he's doing and simply build some infantry to counter. That doesn't mean the AI needs to go 1 for 1 with the enemy, just enough to sort of keep up in terms of production.

This sort of AI strategy would never allow the player to completely overrun the AI and would let it be challenging all the time. Just because it has knowledge about something it shouldn't, doesn't mean it needs to act upon that knowledge. You can build in a randomness factor as well, so that there's a 90% chance it builds the counter, and a 10% chance it does something else. Over the course of time, the AI should be theoretically 10% worse off than the player, but still provide a good challenge.

Special cases would be needed to tell it to attack regardless of what the opponent is doing, or if there's a current tie, maybe there's a 1 in 10 chance the AI goes all out and tries to defeat the player. But it provides for a challenge every time without being overwhelming every time.

Just my thoughts here. I realize that giving the AI access to information it shouldn't know may be the route you're trying to avoid, but as I said, you don't need to have the AI act on all of the information.

I'm with Dan on this one.

The search space, even for a very simplistic "single unit" is still relatively high. As you increase the number of units and possible interactions you increase the mathematical complexity of the interations.

I think Dan has the most workable approach, especially if youre wanting to complete a game and not a theoretical exercise :)

Its basically a problem of trying to prune down the search space (in this case the graph of possible good moves) from the given state to a target goal state. Not a simple solution by any means.

Although GA's and NN's all sound good and funky, they all have issues and when its just a "good game" your trying to give the player, I think theyre overkill to some extent.

Effectively theyre just better methods of giving you a weighted random number into a possible set of actions. How you feed that is up to you, at the underlying level youre going to want to have some method of translating the overall plan into agent objectives and have the agent take care of the details.

Hopefully someday I'll get to play with this more. Right now Ive got a game to ship!

Phil.

Originally posted by Dexterity
I've studied both... ...fuzzy variables.

The benefit of this approach is that a human being could more likely write the rules to cover all the high-level strategic situations. For instance, what would a human player do if resources are high, units are high, camp is well-defended, and enemy is weak and nearby?

Okay, good. You have the main idea clear in you head. But what occurs in that point is a matter of psychology: You could have people with low/medium/high morality, forgiviness, urge-to-win, friendliness, creativity etc. and pick certain traits that would be useful - for example in my situation (if I play strategy games with my friends) I have quite low "urge-to-win" and my "forgiviness" rate is high (that's why I lose so often - but I really don't care, as long as it's creative playing and fun). That would make me think: "okay I'm winning now, but I give him a second chance to gather some troops etc. - I'll just sit and wait". (this makes me think... I guess I have never won a strategy game with my friends :))

But, on the other hand - if my friend (very high urge-to-win, which goes beyond other traits) would be in that situation he would propably attack systematically and kill my troops one unit after another - and he would win.

As you self said: success is about the burning desire ;)

Of course there are as many ways to solve this as there are people... here's how I would go about it:

1. Make a clear distinction between the AI-players' AI (strategy) and the units' AI (tactical). The strategy part is what is described here.
2. Use A-star pathfinding as the basic algoritm for the strategic AI
3. Timeslice the processing, spreading the workload over several seconds
4. When doing processing, start off by gathering information on how the world looks at the moment. Compile this information into a pathfinder node.
5. Start off the pathfinder, dynamically creating new nodes that represent the state of the world if specific decisions were made.
6. The overall strategy to use at any given time is given by whatever node in the pathfinder looks most promising so far.
7. After processing for a while (a few seconds?), start the pathfinder over, to incorporate the changes in the world.

All of the above is very straightforward. The hard part is the cost calculation and the heuristic estimates used by the pathfinder. These will require a very deep knowledge about how the game plays and how different decisions affect the balance and chances of victory. These two functions is what's going to require a lot of tweaking and testing.

And another point: game ai is not really about "artificial intelligence", it's all about "perceived intelligence". If the player thinks that the computer is playing intelligently that's better than if the computer really is playing intelligently, but is perceived to be stupid.