Civ III AI - This explains everything (at least to me)

[Solver]

Seeing the Civ 3 AI as a good one, I bow to Soren for coding somewhat like that alone... what if they really had a few more months and another AI programmer or two? I guess it would then be even better.

Good work !

[Jon Shafer]

Exactly.

Let's just hope that they give Soren some help with IV. Just imagine how that game will be. We might be horrified and delighted at the same time seeing paratroopers landing behind our lines taking cities, while marines land from the coast, as we cry to our mommies!

[Harovan]

Originally posted by Coracle
The reality is that never in Civ 2 did so many people complain about the cheating AI.

Hmmm, let's see who complains about the cheating AI. There's Coracle, Coracle and Coracle... who else?

PS: I forgot Coracle.

[Solver]

Trip, I like the notice of being horrified and delighted at the same time ! When I had a small army and saw many many many units come across the border I was very terrified, and very plaesed .

[BillChin]

Originally posted by monkeyman
What I want to know is whether it is possible to use genetic alogorithms to select and adapt the ai to get a better fit to what happens in the course of a game or series of games? That way, if you start playing in a rut, some variability in the ai might crop up and force you to change your play style. This is in effect what Soren is doing iteratively with each patch, but Soren's manual approach is (somewhat) more predictable in its effectiveness (but not necessarily ala communist collapse of ai in 1.17f). I guess this is also what the CTP mod community is doing. Again, could this approach work out of the box?

I believe it is possible, however, NO WAY IN FOUR MONTHS!!!!

One process for an adaptive AI is to allow fans to write scripts. The Darwinism that takes place on boards like this would lead to a better AI. Poor scripts would be discarded within hours. Good scripts would be learned from and built upon. Each person's script might have a different "personality." With a rich scripting language and a random selector, you get close to a multiplayer environment in single player. That said, writing a script engine is a huge, big project that might require five times the resources devoted to the Civ III AI, plus a major boost in ongoing support costs.

A similar methodology is to have a program that generate scripts or make changes in a data file that have a big effect on the AI. Again, this is probably not feasible with the approach taken and the time and budget given. However, if implemented, have a tournament or ranking system with AI's only. This weeds out the weak AI's.

Again, let me say that Mr. Johnson deserves a big thumbs up for what he has delivered with FOUR MONTHS to code the project and minimal help. My estimate before reading the article, was that he had a year or so to do the coding. (That four months probably felt like a year )

[Dominae]

Originally posted by BillChin
One process for an adaptive AI is to allow fans to write scripts. The Darwinism that takes place on boards like this would lead to a better AI. Poor scripts would be discarded within hours. Good scripts would be learned from and built upon. Each person's script might have a different "personality." With a rich scripting language and a random selector, you get close to a multiplayer environment in single player. That said, writing a script engine is a huge, big project that might require five times the resources devoted to the Civ III AI, plus a major boost in ongoing support costs.

This is an interesting ideat that I had not thought of. The problem, as you mentioned, is designing a scripting language that is powerful enough (yet simple enough, of course) to accomodate all player's creations. This is a monumental task (orders of magnitude more difficult that actually designing the Civ3 AI in the first place). Also, selecting various scripts/personalities at random would in some ways simulate multiplayer, but would not in some ways as well. Humans can adapt to different situations "on the fly". So any scripted AI would suffer from the same problem as the current Civ3 AI: no opportunity for innovation. Finally, considering that Soren is probably a "pretty good" AI programmer, I'm confident that most of the script AI's created by the Civ3 community would have their fair share of weaknesses/stupidities.

Originally posted by BillChin
A similar methodology is to have a program that generate scripts or make changes in a data file that have a big effect on the AI. Again, this is probably not feasible with the approach taken and the time and budget given. However, if implemented, have a tournament or ranking system with AI's only. This weeds out the weak AI's.

"Generating scripts" is no trivial matter. There is a constant trade-off in genetic algorithms with the size of the changes in offspring and the time required to achieve good results: generate "big" changes in the AI, and the system will find some optimal players pretty fast, but they won't be particularly good; generate "small" changes, and the system will find great players in about 2-3 years (or more).


Dominae

[ChaotikVisions]

I for one think the AI in Civ3 is the best i've seen yet, it continues to suprise me and present a challenge. Though it has done some odd things i'll admit, like nuking a size 1 city 8 times, but maybe they just really didn't like the guys in there. The attacks planned by the AI are usually pretty good, just the other day when I dropped 16 units of tanks onto another civs coast and declared war, they used there railroads to destroy every last tank I had, without me even getting to attack one of there citys.

As for thos who think its "inadaquete", why? Is it because the AI has a few cheats to make it better. None of these cheats are large advantages, and certainly not enough to ruin your fun. Is it because some of the AI behavior can be preditced, and you in turn can exploit it? If thats a problem, why are you whining about the AI cheating when you are too? Really, its easy not to exploit the AI, if you do exploit it your just cheating. And if the AI is so dumb, why do you need to cheat against it to win?

[monkeyman]

Originally posted by Dominae


"Generating scripts" is no trivial matter. There is a constant trade-off in genetic algorithms with the size of the changes in offspring and the time required to achieve good results: generate "big" changes in the AI, and the system will find some optimal players pretty fast, but they won't be particularly good; generate "small" changes, and the system will find great players in about 2-3 years (or more).


Dominae

Dominae, thanks for the answer,

So, the question is, is it possible to define AI behaviour effectively as an "energy" landscape? Are the global minima sufficiently different from the local minima to be able to differentiate between the two? If they are different then the random walk process might work...

The other process, generating AI scripts and trading them, becomes almost a game in and of itself. Who can build the best AI? So far, only Soren is playing

It would be interesting to have a set of 8bit sliders (i.e. 0-255) setting priorities on a gradient for each of the AI levels accessible in the editor. With about 20 different priorities, one would have the opportunity to generate some variable behaviour, probably mostly bad, but who knows?

-mm

[Dominae]

monkeyman, I think the problem with the entire random walk process, as applied to Civ3, is that the state space (rather, "energy" space) is immense. Just describing the space would be horribly complicated ; searching through the space would be a nightmare. I'm not expert, but I know enough about this (as I'm sure you do too) that Civ3 is too complext a domain to (at present) be profitably applied to Civ3 (here, I use "profitably" in many senses).

However, I do like your 8-bit slider idea. The process would basically select the best "priorities" in the editor in order to create the optimal AI configuration. Unfortunately, it would not generate any new behaviour, which is what a lot of people are looking for. You could simulate innovative behaviours by having Soren to code a bunch of different options, and let the process choose the best ones. Not knowing which ones the AI will select would (hopefully) keep us on our toes.

Again, you're definitely on to something here.


Dominae

[BillChin]

It would be interesting to have a set of 8bit sliders (i.e. 0-255) setting priorities on a gradient for each of the AI levels accessible in the editor. With about 20 different priorities, one would have the opportunity to generate some variable behaviour, probably mostly bad, but who knows?
-mm

I like this idea a lot. This would be a great way to allow players some control without the huge project of a scripting language. There are already some things in the editor like this such as Aggressiveness, and type of units built. With some interesting sliders and a bit of creativeness, this could add a lot to a game.

For random behavior, one slider might be a chance that the AI builds more cities. The current AI always expands to available space and many human strategies take advantage of this predictability. By having a slider labeled something like Expansion desire, and also a random setting, a human faces more uncertainty.

Another idea for a slider is chance to change other sliders. This could create a play style shift during the game, again making for more uncertainty. For example, an AI slider might indicate Expand to six cities and then slow down greatly, but after 100 turns, the switch flips and they become very aggressive at building settlers and claiming land. In this example, the human may see that the AI only has a few cities and says okay, I'll out build them. Then a few turns later there is a flood of AI settlers and the sure fire human strategy must change.

So maybe for each of twenty of so sliders, have a secondary slider of chance to change that slider . Forty sliders isn't bad at all, and would not add much code, and give players a chance to have more fun (which is the whole point of any game).

[monkeyman]

Originally posted by BillChin


I like this idea a lot. This would be a great way to allow players some control without the huge project of a scripting language. There are already some things in the editor like this such as Aggressiveness, and type of units built. With some interesting sliders and a bit of creativeness, this could add a lot to a game.

For random behavior, one slider might be a chance that the AI builds more cities. The current AI always expands to available space and many human strategies take advantage of this predictability. By having a slider labeled something like Expansion desire, and also a random setting, a human faces more uncertainty.

Another idea for a slider is chance to change other sliders. This could create a play style shift during the game, again making for more uncertainty. For example, an AI slider might indicate Expand to six cities and then slow down greatly, but after 100 turns, the switch flips and they become very aggressive at building settlers and claiming land. In this example, the human may see that the AI only has a few cities and says okay, I'll out build them. Then a few turns later there is a flood of AI settlers and the sure fire human strategy must change.

So maybe for each of twenty of so sliders, have a secondary slider of chance to change that slider . Forty sliders isn't bad at all, and would not add much code, and give players a chance to have more fun (which is the whole point of any game).

Well, I haven't played around with the build orders in the editor much nor the aggressiveness sliders, although I imagine that this alone would produce some variability, unless they are the dropbox type of the "Often, sometimes, never" variety. Even 1..10 would be better than that...IIRC the agressiveness is a 1..5 scale?

I for one would like the governor to stop asking to build Privateers and I have seen far too many of those built by the ai...

But variability is the spice of gaming when you're talking about AI. And sometimes some really stupid extreme strategy will work if you are in the right place at the right time. Of course variability is more suited to a game with 16 civs than to one with 2. With fewer civs, the more moderate strategies are prob more successful on average game to game.

--mm

[Jaybe]

Originally posted by monkeyman
I for one would like the governor to stop asking to build Privateers and I have seen far too many of those built by the ai...

It is truly amazing the variety of experience that different players have! I have NEVER seen an AI Privateer.

JB

[MBD]

Originally posted by BillChin
One process for an adaptive AI is to allow fans to write scripts. The Darwinism that takes place on boards like this would lead to a better AI. Poor scripts would be discarded within hours. Good scripts would be learned from and built upon. Each person's script might have a different "personality." With a rich scripting language and a random selector, you get close to a multiplayer environment in single player. That said, writing a script engine is a huge, big project that might require five times the resources devoted to the Civ III AI, plus a major boost in ongoing support costs.

I understand this may be asking too much, but can some of you guys who are more familiar with these AI scripts give me an idea of what kinds of things and what the level of detail you would want to see in this scripting language?

[player1]

CTP2 anyone?

[Peter Triggs]

We've missed you player1.

MBD:

Here's a start:

http://apolyton.net/ctp2/modificatio...mization.shtml

But you have to check out the other SLIC documents to appreciate it.

[player1]

Peter,

Has anybody in CTP2 community used anything from SLIC code I wrote for MyMOD (nuke, spies and naval building stratgegies for example).

[Peter Triggs]

I don't know. I think Martin may have incorporated some of your stuff into GoodMod but I don't know if it found it's way from there into any of the other mods.

[kavau]

Originally posted by SwitchMoO


Any mere game company? Try any company, ever. Does anyone think anyone'll develop AI that even comes close to human behaviour? IMO, no. Our brains are just too complex, and then there's the added problem of dynamic personalities, forgetfullnes, moral fibres, and the soul. No, it's just too much for our small in comprehension yet high in complexity brains

Remember that today's chess programs can beat even grandmasters (and world champions, for that matter). I bet if as much effort would be spent on developing a Civ AI as is being spent on developing more powerful chess engines, soon only the most brilliant Civ players could beat the AI.

The reason is that computers are potentially very good at all kinds of games involving randomness and luck. A computer can calculate probabilities just that much faster than any human being. So it would say: "there's a 37.593% chance to win this war now, but if I keep building units for 10 more rounds I could increase the odds to 62.524%". But of course this can't be done in 8 months

[Jaybe]

kavau,
Chess is a SIMPLE game. MUCH simpler than any of the Civilization franchise!

[Mark_Everson]

Originally posted by kavau
The reason is that computers are potentially very good at all kinds of games involving randomness and luck. A computer can calculate probabilities just that much faster than any human being. So it would say: "there's a 37.593% chance to win this war now, but if I keep building units for 10 more rounds I could increase the odds to 62.524%". But of course this can't be done in 8 months

Hi kavau:

We're trying to do something like what you're talking about with the Clash of Civs AI. Without perfect information the sort of calculation you forsee can't be done accurately. And projecting a game with thousands of decision variables ten turns into the future with 5-digit accuracy is a challenging problem

But we're willing to spend years at it if necessary, to get it right. The other advantage we have is that we plan to run the AI in the background during player moves, since Clash is simultaneous. That helps a Lot with heavy-duty simulation of scenarios.


Hey Jaybe:

The reason I think the chess analogy isn't too far off is that while chess has a simpler search space, the objective function is much more sensitive to bad moves. In a civ-type game, if one has a decent strategy, there are lots of large blunders that can be made along the way that can be recovered from. In chess, once you drop that piece, you're toast. So the fitness function is "spikier" requiring a lot more care in the search IMO. I've done just a little AI professionally, and hope to learn a lot more doing the Clash AI.

-Mark

[Coracle]

Originally posted by Trip
Exactly.

Let's just hope that they give Soren some help with IV. Just imagine how that game will be. We might be horrified and delighted at the same time seeing paratroopers landing behind our lines taking cities, while marines land from the coast, as we cry to our mommies!

I sincerely hope Soren has NOTHING to do with Civ 4 since he seems obsessed with this Culture Flipping crap. He couldn't even figure out that roads CAN be used, historically, by invading enemies armies during war.

[asleepathewheel]

Originally posted by Coracle


I sincerely hope Soren has NOTHING to do with Civ 4 since he seems obsessed with this Culture Flipping crap. He couldn't even figure out that roads CAN be used, historically, by invading enemies armies during war.

you really don't have a clue, do you coracle. Have you played the previous games? The AI is a patsy. At least in Civ3, it puts up a good fight.

[BillChin]

Originally posted by MBD
I understand this may be asking too much, but can some of you guys who are more familiar with these AI scripts give me an idea of what kinds of things and what the level of detail you would want to see in this scripting language?

Since I am using this term, and one of the biggest advocates for scripting, I'll give it a shot. For me the best way to understand something is an example. I'll try to outline the relatively easy and powerful Swordsmen Conquest strategy. This is only the opening moves, and only good for small and standard maps, but may give readers a basic idea.

Ancient_Age /* change scripts when changing ages */
Research: Bronze then Iron, then Horseback Riding as priorities
Resources: Claim Iron, claim luxuries, claim horses
Expansion: build 3 production cities, after that look for resource cities
Units: build settlers until 4 to 6 cities depending on resources, after that build warriors or swordsmen
Aggressiveness: attack nearest enemy once 10 units are in the attacking stack

What this might have to translate into pseudocode, may involve flags, sliders or functions such as:

Research (Iron Working) /* make this top priority */
Build_cities (4, 50%, 10 turns) /* build four cities then build attack force, 50% chance, reroll again after each additional city, or after 10 turns of building only military units */
Build_defenders (1, 100%) /* one defender per city, 100% priority */
Build_defenders (2, 30%) /* second defender 30% of the time */
Build_attackers (10, 70% offensive) /* stack of 10 units, 70% offensive rest mixed */
Aggression (10 units, 80%, 75%) /* attack after 10 units are in stack 80% of the time, attack even if enemy appears stronger 75% */
Appease (90%, 20%) /* give in to enemy demands for tribute 90%, but lower this by 20% with each give in */

Well, this might give you an idea or might make your head spin. As I have said before writing a script engine is a huge big project. This pseudo code is off the top of my head, not from a well thought out design document.

I believe scripting may be one of the most cost effective ways to a decent AI. Closed system approaches are always going to have loopholes and fans find them very quickly and then everyone can drive a truck through the loophole.

[LDiCesare]

Despite the fact Mark beat me to posting here, I'll say the Clash of Civilizations strives for good AI, including thinking about genetic algorithms, or rather simulating moves. This should include learning if that is feasible.
Also, scripts are good. I think CtP2 has managed to get good AIs from scripts. (The original CtP2 AI was the lamest thing I ever saw.) Remember that you learn the game, the AI does not, but scripts are a good way to circumvent that, thus they are good. Simply tweaking scripts and randomly modifying one or two figures in a script and playing it several times against the human player woul let the computer learn. Imagine there are 16 AI civs, 4 civs with script 1, 4 with script2 etc. After maybe 2 or 3 games (starts) you can probably infer that script 1 is worth nothing, but script3 has an edge, so you can use a genetic algo here. Whether it will learn faster than player will get bored is another point. Still, if you could share scripts (and experience the program had about script effectiveness) through the network, the AI could get much better faster.
But of course, adapting/mutating script is quite a challenge, and is not done in 8 months...
I insist that the programming was done in 8 months. No programmer in their right mind programs without testing their program. Or if they do, the program never runs. The half/half is actually quite a proof Soren is agood programmer because you usually spend more time debugging than programming...
Anyway I don't know, civ3 won't run on my machine and I won't buy a new one just to get a bigger screen.

[Dominae]

BillChin, your scripting example is good. What is missing, however, is a discussion of how the scripts are exchanged/replaced as new information becomes available. With no adaptability, the AI you described wouldn't be very competitive. Sure, in a vacuum, it could produce a nice little force of Swordsmen, and in a real game it could even put up a nice fight early on. But most of the time the AI would be left wandering around with no one to conquer, or stuck attempting to secure Iron. Any AI needs to have either 1) a bunch of if-then statements to deal with various circumstances (the programmer needs to code these with his or her domain knowledge), 2) a means of proposing alternative actions itself. (2) is really hard to implement, but would mark the existence of a truly "intelligent" AI.


Dominae

[BillChin]

Originally posted by Dominae
BillChin, your scripting example is good. What is missing, however, is a discussion of how the scripts are exchanged/replaced as new information becomes available. With no adaptability, the AI you described wouldn't be very competitive. Sure, in a vacuum, it could produce a nice little force of Swordsmen, and in a real game it could even put up a nice fight early on. But most of the time the AI would be left wandering around with no one to conquer, or stuck attempting to secure Iron. Any AI needs to have either 1) a bunch of if-then statements to deal with various circumstances (the programmer needs to code these with his or her domain knowledge), 2) a means of proposing alternative actions itself. (2) is really hard to implement, but would mark the existence of a truly "intelligent" AI.

Dominae

You are correct that programming constructs such as if-then-else, while loops, are good ideas to include in a scripting language. You are also correct that contigencies such as no iron or no enemy near by, are needed. Maybe place a big while loop around it and change gears once Horseback Riding is researched or change after a certain number of cities are built, or a certain number of turns are played. This is not a big deal, but may have been unclear to some readers, so thanks for the chance to clarify the point.

Example:
While Cities_in_Empire < 8 use Swordmen Conquest module

If a company is going to do scripts, several weeks or months of input would be incorporated into the design document. A lot of new stuff would be added as scripts are found to be inadequate. It is a dynamic process. New patches might include new functions, sliders, flags, or whatever fans might think up, as well as new scripts.

Proposing alternative actions within the AI is a good idea. This might be similated by a random chance to do certain things or a random chance to load a totally different script file.

There are easy ways to approach a problem and hard ways. Frame the problem in a way the computer can solve, instead of a way that the computer has little chance at solving and the AI has a much better chance of looking intelligent and playing a decent game. The task itself, a decent 4x game AI, is not hard. I see it more as a problem of time and resources than technical or programming issues. Humans can make the task very hard, by framing it in certain ways, but I believe this is a choice, not something inherent to this particular task.

[SirSebastian]

IIRC, chess "AI" works less as a real AI, and more like, "Okay, calculate every possible outcome up to X turns into the future ... okay now force the game down the best path for the computer player by moving this piece." In other words, Civ AI rocks Chess AI =P

[Dominae]

BillChin, thanks for the reply; I'm in complete agreement with all your points. The fact of the matter is, the current Civ3 AI is implemented in a way very similar to what you're describing (as far as I know). The main idea you're proposing is to let the player community write their own scripts in a new scripting language. I've never played CtP much, but the idea seems to have some merit. I think that main problem will be how to pool scripts together to create a interesting and challenging AI. In other words, there needs to be some code to pick and choose the scripts; this is the code that will make or break the AI, IMO.

Just a little example, which is an extension of yours. If the script dicates that whenever a civ's number of cities is below 8 the "Swordsmen conquest" script is called, a number of problems come to mind. When the ninth city is built, what happens to the Swordsmen? It seems necessary to have the next script mention what is done with standing forces (or are the Swordsmen disbanded?). If a civ gets bumped from 12 cities to 8 cities (through war, most probably), does it go back to the "Swordsmen conquest" script? If so, the new Settlers built via the script may not have anywhere to go anymore (all the land has been claimed). I'm sure you can imagine other scenarios.

My point is not that the script idea is bad. Rather, the scripts need to complex enough to be useful, regardless of the state of the game (or of many state variables). Or, the algorithm that selects the scripts needs to be make "smart" choices regarding scripts (thus creating the need for a "meta-AI"). I would much prefer seeing the second case come to life.


Dominae

[Peter Triggs]

Happy Birthday, Soren

[MBD]

BillChin, thanks for your responses from me too.

I agree that using scripts can be a good way to quickly develop a reasonably competent AI for a Civ-type game. There’s still a lot about where scripts fit into the whole AI that I’m not sure about. I was wondering what you think about a couple of potential problem areas –

First, the inputs. For the right script to be used, the AI has to be able to convert the player’s game position into something the AI can use, possibly like a set of (weighted) values. Does that make sense?

Second, the current situation. This relates to the first point. In order to choose a script, you have to understand the position you’re in. If you express the player’s position too specifically, it may seem to the AI that every position is unique, which makes it harder for the AI to learn from past experience. OTOH, if you express the player’s position at too high a level, crucial information may get left out. How do you find the balancing point?

Third, the changing situation. Over the course of the game, some things become less important, while others become more important. Once the AI player has developed a defensible core of cities, survival becomes less imperative, and the AI can turn its attention to expansion. I suppose this gets back to changing the weighted values associated with the player’s position, right?

Fourth, the value of each script. In order to work well, it seems like you’d want to have multiple scripts available all the time, and then choose the best one. But that brings up the problem of determining which one is best. (“Good judgment comes from experience; experience comes from bad judgment”) In other words, how would you try to figure out which script gets you the most “bang for the buck” at any given point in the game?