{The List} AI

[Fosse]

I hate when I crosspost and the other guy's is way better.

[Nikolai]

A crosspost 13 hours later?

[wrylachlan]

Originally posted by Jamski


This ruined the MoO3 AI. It tryed to spread its forces over many fronts, meaning it was never a real threat on any of them. The Ai should think TARGETS, not fronts. It should have a goal like : get Athens, and defend Rome with x troops. Simple.

-Jam

That's not a problem with an AI thinking in terms of fronts, that's a problem with an AI being bad at thinking in fronts.

[Kuciwalker]

However, targets are how many humans think - so it must be good for the AI.

And I like how the AI was actually different on different levels in GalCiv.

[POTUS]

Originally posted by Nikolai
POTUS: If you can beat Deity, you're NOT the worst Civ player ever, I can assure you!

I've only done it once, unfortunately. All the AI's were peaceful and had no military. After that I discovered that I could select civs that were good, and not just have it random.

[wrylachlan]

Originally posted by skywalker
However, targets are how many humans think - so it must be good for the AI.

And I like how the AI was actually different on different levels in GalCiv.

Maybe I'm inhuman, but I think in terms of fronts. The Greek front, the Russian Front, etc. Within Fronts, I think in terms of targets, like "I want to take sparta" or "it looks like Catherine is getting close to Dover, gotta stop her." But my overall view is, "How am I doing on the Greek front? How am I doing on the Russian Front? How should I apportion the distribution of new troops?"

I guess I'm thinking like this.
1)Analyze each front.
a)How am I doing I doing at achieving my goals for this front?
b)How many more troops would I need for each of the goals?
c)Can I shift troops around on this front to make it happen?
d)Does this front need reinforcements to achieve its goals?
2)How do my fronts compare?
3)Reinforce the neediest fronts with new troops.
4)Reassess and possibly move troops from one front to another.

The reason I think this might help the AI is that it narrows the event window so that the AI doesn't have to figure the "what if" of a specific unit crossing the map to aid in winning a specific target.

All it needs to think about on each of the fronts are the targets, its chance to get them, and how reinforcements would change that percentage. Each front deals with reinforcements exactly the same whether they're new recruits or sent from another front.

Put another way it would be like having multiple AI's each Front is its own AI which executes its targets and requests troops or offers excess troops to the CIV AI which apportions new troops.

I think the modular approach is the way to go.

[MrBaggins]

"Fronts" are another simple to think about, tough to actually model, concept. Humans have an intuitive sense of grouping in a 2d space, and can ignore "clutter" relatively well... so a human can distinguish relative patterns, or troop fronts quite easily.

A machine can't, instinctively. The problem is actually fuzzy and not crisp. To solve the problem, typically you use an influence map. An influence map works quite well for single entities per tile models.

The complexity increases when you wish to model multiple entities per tile, of varying power. You can use scoring and essentially sum the values, to associate them.

Then comes the last challenge... prediction. To deal with a threat, you need to move units before that threat arrives... (well... not with unlimited travel railroads, but this isn't a guaranteed situation.) You thus have to predict where a threat is spacially, and how its shaping up. To do so you must propogate the value of each threat, from its initial position, in all possible directions, and decay the value, over a number of iterations of its movement distance.

This actually gets fairly costly in computational terms. It scales badly with map size and number of entities.

[Shogun Gunner]

Good to have folks knowledgeable about programming reading these threads. Many things seem possible until actually try to do it!

I've seen that responsive from the DBA and programmers in real life....its usually a polite "no" with a bit of scarcastic "do you have any idea what that will cost/size of the hardware system/lines of code necessary to do that?"

Glad you are here to keep us in check MrBaggins.

[Fosse]

Originally posted by Nikolai
A crosspost 13 hours later?

err....

[Shogun Gunner]

Isn't there a statue of limitation on crossposting? Has to be within x amount of time?

[Fosse]

If it makes Shogun Gunner look foolish: within 15 seconds.
If it makse Fosse look foolish: 10 days.

[Shogun Gunner]

ouch!

We've all x-posted...and also been a victim of x-posting.

Really something should be done about this issue!!!!

[okblacke]

I'm going to make the assumption that Civ 4 won't be giving us revolutionary AI--nothing heuristic, adaptive, neural netty, etc. I haven't seen anything to indicate those things aren't prohibitively expensive. (I haven't seen anything to idnicate that they ever won't be prohibitively expensive, but as long as Moore's Law holds, there's hope.)

Having said that, what would be incredibly cool is for the AI to be an external program. This would tie in with some other folks' request for the next Civ to be based in MP. (For myself, I wouldn't want anything to compromise the single player game, but this may help achieve both.) It could also simplify the whole "multi-threading" issue.

What I'm thinking is, put someone on AI with the problem of: Here's the data you'll get from the program with every change, now solve the problem with an eye toward various goals.

I don't want to go overboard with detail, but an advantage of treating the AI like a remotely connected player is that user mods could be developed. For most games that wouldn't be a possibility, but Civ has enough die-hards that it's almost a cinch.

It would even be possible for people to try out various AI techniques with Civ as a base. Make for more than a few great graduate theses.

[ok]

[MrBaggins]

Heuristics essentially means evaluating and reacting to feedback. E.G. Defending when attacked, stoping production of settlers when there's nowhere to settle, etc.

Any AI worthy of being called an AI does this.

[Kuciwalker]

If it doesn't use a heuristic, and doesn't use a neural net, wouldn't that mean either a) it moved randomly or b) it created a tree of all possible moves and evaluated them?

[MrBaggins]

Originally posted by skywalker
If it doesn't use a heuristic, and doesn't use a neural net, wouldn't that mean either a) it moved randomly

Not necesarily... you could use predetermined actions, without evaluating your circumstances... this could get ridiculous if it happened at a low level, though.. like a settler trying to move into the ocean, because the AI *ALWAYS* builds one, and moves the first one 5 north, then settles with it.

or b) it created a tree of all possible moves and evaluated them?

Yep... typically minmax trees. The decision space is effectively infinite in terms of a Civ game, though.

A fuzzy logic (as opposed to crisp logic) system can (and has) been used, as well as heuristics, and neural nets (not sure how successful neural net efforts have been in Civ.)

[okblacke]

Originally posted by MrBaggins
Heuristics essentially means evaluating and reacting to feedback. E.G. Defending when attacked, stoping production of settlers when there's nowhere to settle, etc.

Any AI worthy of being called an AI does this.

From "The Handbook of Artificial Intelligence" (Barr and Feigenbaum, Vol 1):

...a brief review [of how "heuristic" is used] may serve as a useful warning against taking any single definition seriously.

Nah, I'm not gonna type all this in. Suffice to say that your definition of "heuristic" is one of the earliest ones but a lot more shallow than what I mean.

Yes, the AI reacts to the current state of the game.

I think it would be cool if it based its strategies on a recall of all the previous moves of the game.

And cooler still if it based its strategies on recall of all previous games played.

That's what I'm getting at. Prohibitively expensive, probably, though you could fruitfully reduce strategies down over time, so that you weren't storing every game with every move forever.

[ok]

[MrBaggins]

It might be "cool" but the descision space doesn't lend itself to it:

Whilst in a limited context you might be able to use an adaptive (typically genetic) solution, you are essentially limited to building, tech choices, and perhaps worker behavior. Since the value of these choices differ hugely, depending on situation, and opposition, you won't always get reliable data, and then you come to the problem of defining the context... storing the original world.

A solution to this might be a repository of MP games and their actions, but the sample size is massive, and with an adaptive algorithm you need to determine relative success and failure... its difficult to determine slight differences in success and failure... and tough to know whether they are due to situation or ineffective tactics, strategy, or just bad rolls.

The sample size of an AI within a single game is insignificant. It would be pointless for an AI to try to improve within a game, since it would be effectively out of context.

Since there are a variable number of entities, you'd need to develop some extensible adaptable system... forget a static genetic solution... and store and crunch massive volumes of data.

Any current traditional adaptive solutions are inapplicable to a general Civ AI (although possible for tech, or worker use)

[okblacke]

I've posted a response to ths twice. It's vanished both times.... What gives?

[Kuciwalker]

Originally posted by MrBaggins
It might be "cool" but the descision space doesn't lend itself to it:

Whilst in a limited context you might be able to use an adaptive (typically genetic) solution, you are essentially limited to building, tech choices, and perhaps worker behavior. Since the value of these choices differ hugely, depending on situation, and opposition, you won't always get reliable data, and then you come to the problem of defining the context... storing the original world.

A solution to this might be a repository of MP games and their actions, but the sample size is massive, and with an adaptive algorithm you need to determine relative success and failure... its difficult to determine slight differences in success and failure... and tough to know whether they are due to situation or ineffective tactics, strategy, or just bad rolls.

The sample size of an AI within a single game is insignificant. It would be pointless for an AI to try to improve within a game, since it would be effectively out of context.

Since there are a variable number of entities, you'd need to develop some extensible adaptable system... forget a static genetic solution... and store and crunch massive volumes of data.

Any current traditional adaptive solutions are inapplicable to a general Civ AI (although possible for tech, or worker use)

Would it be possible to take a genetic algorithm, have it play a whole lot of games, and then just use the resulting AI as the AI for the game (so it doesn't evolve further)?

[MrBaggins]

Maybe... assuming you could get a sufficient sample size (probably not) and encode the data (GA's are just the typical form of EA, which have shown most success, but have limited capacity to define an expanding situation, such as a civ game.) NN's are extensible and so are the current solution to a non-finite system such as Civ.

Here's a snippet from a piece in gamasutra a while back

Interestingly enough, some developers (roughly 20 percent of attendees) were experimenting with Artificial Neural Networks (ANNs) as a learning technology. ANNs have cropped up often in the AI roundtables as a potential solution to the learning-AI problem, but there are some interesting challenges in using the technology in games that have discouraged most developers to date. Historically, using ANNs within a game presents the developer with two particularly thorny problems: First, it can be very difficult to identify meaningful inputs and match them to outputs that make sense within the context of the game; and second, most ANNs learn through a technique called "supervised learning," which requires constant developer feedback. While it is possible to build ANNs that can learn unsupervised, there's no guarantee that they won't "go stupid" and become completely helpless players.

Most developers are trying to avoid these problems by training their ANNs exclusively during the development phase, then freezing them before the game actually ships. This allows them to let the AIs learn while playing against the development team and play testers without the risk that a shipping AI might wander off into some Rain Man universe of perception. The downside to this, of course, is that the game doesn't learn anything from the player, and so the whole effort boils down to an automated form of AI tuning (ultimately similar to using genetic algorithm to try to tune various game AI parameters). A developer of an upcoming sports game announced that he was working on a way to integrate unsupervised learning ANNs into his game, although he planned to include an option to reset the AI should the player feel it had become feeble-minded (or too strong a player, as the case may be).

One big problem with learning AIs that caused much amused discussion at the roundtables was the fact that a learning AI is, by definition, unpredictable. This leads to huge problems when it comes time to do quality assurance testing on your game — how can anything be tested reliably if it behaves differently from game to game? How can a developer fix a bug if it's impossible to recreate the conditions that led to a certain behavior?

On a closely related vein, several developers noted that they were attempting to find AI technologies that would do a better job at strategic-level thinking and planning. To date, most strategy games do an adequate job at the tactical level — identifying cities or units to attack, taking advantage of unprotected assets, and so on — but do a lousy job at developing and implementing grand strategy. The problem, from a programmer's point of view, is basically one of optimization.

Most war games (ignoring for the moment most first-person shooters and RPGs, since they are primarily tactical in the extreme), whether real-time strategy or turn-based, do a much better job of optimizing small, tactical situations over larger, strategic ones. This leads to AIs that fight battles well but still manage to lose the war, often because they overlook solutions glaringly obvious to the human player. A large part of this situation is simply the result of the historical inclination of developers to build AIs at the unit level; for example, in a Civil War game, a cavalry unit might decide to attack an artillery unit without the presence of any other support. This in turn leads to an AI that often overlooks obvious attacks in favor of frittering away its forces. Adding in an ability for a unit to call for help balances things out somewhat, but that's still a far cry from strategic-level thinking.

Additionally, there's the problem that strategic-level planning may be very good for the war effort overall, but very bad for the individual unit. One example of this might be a brigade ordered to hold a vital mountain pass in the face of overwhelming enemy attack — the war might be won because the delaying action bought the time necessary to get reinforcements to the area, but the unit itself isn't likely to survive. An AI built to handle only unit-level thinking is going to have a hard time making this kind of trade-off. Chess game AIs are perhaps the one exception to this rule, but they're cheating, since most chess programs draw upon databases of thousands of games and simply pick the highest-scoring move available at that moment.

Many developers present felt that the time had come to redress this imbalance and were looking to a number of AI-related technologies for help. Some were building on the same techniques used for learning algorithms by using databases of previously-successful moves to develop plans for similar future moves. Others were looking at tools such as Influence Maps (see sidebar "Influence Maps in a Nutshell") to provide ways for their AIs to "see" the grand strategic picture. A few were hoping simply to solve the problem the same way most chess programs do, which is to build large databases of opening strategic moves based on feedback from play testers and the development team.

Interestingly enough, a vocal minority of developers felt the move towards developing better strategic AIs was primarily a waste of time, particularly in games in which players can't easily see the other side's forces. The theory they put forth was that if the player can't see what the computer is doing, why waste time on elaborate strategic AIs in the first place? A few well-placed but thoroughly plausible unit placements (via judicious cheating on the part of the AI) would go a long way towards providing the player with an enjoyable gaming experience. Many of this group felt that the mere appearance of a tank deep behind enemy lines would be ascribed a meaning by the player if the attack came at a particularly vulnerable time. They based this opinion on the reams of e-mail they had received from players that raved about the intelligence of the AIs in their games, when the AI was, in fact, cheating outrageously just to keep up.

[Merp]

I believe the AI should be rule-based, and importantly should moddable by the community.

I don't have a lot of faith that at release the AI will be optimal. The reason is that evaluating the AI takes a lot of playtesting, something that game developers never do enough of.

For this reason, I believe that the AI should definately not exist as hardcoded within the engine, but instead be stored as scripted rules within separate text files. The game Jane's Fleet Command had the ai rules separated out like this into doctrine files. The result is that modders could not only correct flaws in the original AI but could also support mods in other areas.

All or most the above ideas from other posters could be expressed within these rules. The same scripting language could expose other non-ai elements to the evil hands of modders, such as the interface and informational screens.

Furthormore, the AI should have hooks to allow these rules to be applied at different levels of evaluation such as national, continental, regional, city and unit. Information flows up from the unit and city level, and commands and methods flow down. For those with some programming experience, I am imagining an object-oriented paradigm that could simulate polymorphism and generalisation.

The primary point I would wish to impress upon the reader is that the AI should be moddable. The greater ease of customisation, extension and correction, the better.

[Mark_Everson]

FWIW, here's my list of what the AI needs to do in a civ-type game to get the breakthrough many of us want. Many of these have been mentioned already above. We're not going to get anything like this out of Civ4 :

AI that thinks in 'Levels' about strategy, from very high level down to small details. This is an Hierarchical approach

Levels will go from very abstract pictures of the world at high levels, down to pretty accurate copies of the world, for small things

Corrections will be made in the higher level AI to incorporate information from the more detailed AI levels below it

As much as possible, design the world models in the game so they are easier for the AI to handle

Use good rules-of-thumb (heuristics) as a firm base for AI actions

As much as possible evolve unique strategies Beyond the heuristics using Genetic Algorithms

Test AI strategies as much as possible using Monte Carlo techniques (copy the world as that AI sees it; how does the strategy play out in the copies?)

Threaded AI that can take advantage of any time not used by the world model and the interface

Allow the player to give the AIs any arbitrary advantages that they deem necessary

More details for those who want them are on the Clash of Civilizations AI page.

[Nikolai]

Updated! Mark: Could you differentiate between what's new in your post please?

[LDiCesare]

Of course Mark would show uo here.

Aboutu rules: You don't need scripted rules to get the ai to work, you need scripted input to the ai.
For instance, right now in Clash (well, on my machine, and Mark's), the (military) ai has 2 levels (not yet enough to be called hierarchical, but then...). The highest level can precise a breakdown of various 'attitudes': Which proportion of military resoures should be used for what. This proportion is defined in script. Each attitude, in which the objectives are themselves defined, is defined in a text file. This doesn't require 'rules' to make moddabke ai. Of course, rules or triggers are needed in order to allow specific orders to be given to the ai like 'take city XXX' instead of 'take most promising opponent square'.
Tuning of parameters, not even going as far as rules, should be made in script (how much aggressive, how many losses are allowed, what value is given to something or other...).
The rules should come from 'if' clauses which are IMO outside the ai but can influence it: An "If capital taken then" trigger can be useful for modders to tune ai (so you would build a new palace for instance) or to cause whatever events a modder may think of.

One thing I'd like ai's to consider is the value of techs based on what the civ will do with it rather than on its research value modified by a scripted factor (e.g. military tech = high cost, as in civ or galciv). An ai should put little or no value to a tech which lets it build units that are not better than those it already has (for instance chariots are not a priority for aztecs in civ3, thus wheel tech shouldn't be bought except for its value as a prerequisite for other techs).

(edited for clarity - may not be clear enough even with that)

[Brent]

I want to be able to tell one of my units to explore in a general direction or to go to a specific destination but tell it whether to stay out of rival territory.

[VetLegion]

The theory they put forth was that if the player can't see what the computer is doing, why waste time on elaborate strategic AIs in the first place? A few well-placed but thoroughly plausible unit placements (via judicious cheating on the part of the AI) would go a long way towards providing the player with an enjoyable gaming experience

I bet there were Brian Reynolds or Sid Meier at that table. This is the way most of their Civ games work. And they work surprisingly well, meaning, I have yet to see an AI that is designed to make only "thought out" decisions and performes significantly better than their (mostly random) AI's. Civ III doesn't count as it was simplified, but GalCiv seems promising in this regard.

[Nikolai]

I just realized I haven't made a spare place for the list in case the original post is getting too long.

Done.

[Kuciwalker]

Originally posted by MrBaggins
Maybe... assuming you could get a sufficient sample size (probably not) and encode the data (GA's are just the typical form of EA, which have shown most success, but have limited capacity to define an expanding situation, such as a civ game.) NN's are extensible and so are the current solution to a non-finite system such as Civ.

What the article was saying was basically what I was suggesting - just get a supercomputer or a bunch of desktops and have the AI play itself constantly for, say, a month then freeze the final product and hope the players don't get whupped.

[MrBaggins]

and the Easter Bunny and Santa Claus do the QA, right?