Good AI is Critical for the Next Big Step in Civ Games

[Mark_Everson]

I'd like to hear peoples' thoughts on my statement. I wrote a column a long time ago about this. It's called Civilization and its Discontents and I'd like it to be a discussion starter here if anyone is interested . The article is a bit dated in that Civ2 was the state of the art when I wrote it. . .

[a quick snip from the article to state my position]
I think that poor AI is the biggest problem with the whole 4x TBS genre. If you have good AI the micromanagement that is the other major problem can, I think, be taken care of. Furthermore, I think if one company Did put in the effort to make at least a passable AI, while maintaining good gameplay and decent graphics, the advantages would quickly make such AI industry standard. Just this has happened in sports games over the last several years. But When this miracle will happen for Civ-type games I have no idea. The fact that I've waited nearly a decade at this point for them to come through, doesn't give me hope that the industry will come up with the game I want to play anytime soon.
[end quoting from article]

I'm now looking forward to trying GalCiv since its predecessor was vaunted as having good AI. Other than that, we should have the first stab at the Real AI (rather than the placeholder we have now) in Clash of Civs within the next four months or so.

Looking forward to your coments!

[Optimizer]

Making a good AI is much harder in turn-based games than in real-time ones. The computer's strengths are speed, control and immunity to stress. These don't help in turn-based games, since the human player can always get enough time for observing, thinking and carrying out orders.

The AI's solution so far has been cheating, which has got some obvious drawbacks. AI designers have to choose what cheating methods are least disturbing.

[Mark_Everson]

Hi Optimizer, thanks for the comments. BTW, what do you optimize? I do some financial optimization and AI stuff professionally.

I agree with your first point that strat game AI is hard to do. But I think its possible to do Much better than than is currently seen in the genre. It just means doing a lot of work. That does make it not quite as practical in a commercial game as we'd like, since the AI work typically starts fairly late in development.

As an example of what I think Can be done, I'll excerpt a fair chunk of a post I made on the Clash AI. This isn't the only way to go about it, but I think its a way to at least giving the AI a Chance of 'understanding' what is going on in the game. The stuff below is from AI -- the Thread on the Clash forum. This type of approach is called Hierarcical AI

--------------------------------------------------------

Let me give you a very broad-brushstroke view of how I think virtually every level in the AI can work. I believe this approach can work for everything except the top few levels of very broad overall strategy. I have specific models in mind, and/or on paper for virtually all of them, but I don't think going through the specific ones would be of value here. (see Hierarchical AI link below for more detail) Here's how each level of the AI works.

1. Strategy to guide this level comes down from above
2. Rules are used to generate an alternative series of possible best ways to execute the strategy (the number tested depends on processing time). Alternative counter-strategies based on knowledge of the enemy are also formulated (we can cheat on this if absolutely necessary, although I would prefer not to).
3. As much as possible our alternative best strategies are tested against good enemy strategies. This is Not done as a simple mathematical equation, but is rather played out in a simplified world model that we think can capture the Essence of what is important for this level. So it is through simulation, rather than calculation that I hope to capture the interaction of different strategies by competing civs.
4. At this point, if it's required that we stop, we just pick from the best indicated strategies. If there is extra time, there is a large variety of things that can be done. The one that I think is most attractive, is to encode the strategies as as individuals in a population of a genetic algorithm approach. We then pursue more simulations as in 3, but while tweaking the strategies through mutation and crossover. If the rule-based approach can give us any hints as to which are the most productive things to change, the more the better. The chromosomes will not generally contain numbers at all, but contain strategic objects. "Take Berlin", "obtain alliance against the Greeks". A mutation in the strategy might be something like "it would be nice to get an alliance against the Greeks, but it isn't that essential", or "it's Imperative". I'm not sufficiently foolish to think that this approach will very frequently give an answer better than the rule-based approach. However, it has the potential to break the AI out of the rut of always doing "predictable" things.

The hierarchical AI is used to form a bucket brigade for the strategies being considered. The higher strategic thought pours down from "above" (that is the higher level models). We assume in each model that the level above knows what it's doing. Just like the Captain follows the Colonel's orders in an army. However, the Captain knows the situation on the ground, and will occasionally ring up the Colonel and ask them to reconsider if things seem especially ill-advised. When the Captain has done his calculations about how best to achieve the result assigned to him by the Colonel, he then passes his plan down to those below him in the chain of command.

Links:

The Clash AI Web Page has lots of good stuff. Among them are old discussions and some links on AI.

The Hierarchical AI page has more details on the ideas I sketched out above.

The thread preceeding this one isGeneral AI.

And finally there's the Map AI page on the web site.

[Solver]

Originally posted by Optimizer
Making a good AI is much harder in turn-based games than in real-time ones. The computer's strengths are speed, control and immunity to stress. These don't help in turn-based games, since the human player can always get enough time for observing, thinking and carrying out orders.

The AI's solution so far has been cheating, which has got some obvious drawbacks. AI designers have to choose what cheating methods are least disturbing.

Not exactly. I have seen no good RTS AI. This includes Ensemble Studios games, Blizzard games and Empire Earth. All those AIs absolutely suck unless they cheat.

In Civ3, though, Regent level AI doesn't cheat, but is doing quite a fair game. Monarch level AI doesn't cheat too much and provides a challenge.

[spartak]

I absolutelyu agree with this thread. But if the AI doesn't suck, what would we complain about then?

[jdd2007]

i wish AI wouldnt be so predictable. even if they use the 'best' strategies, its worthless if you know exactly what theyre going to do.

[Lemmy]

I think GalCiv will have one of the best AI's seen in TBS-games, for 2 reasons. The first is that the game won't have multiplayer, they're concentrating on the singleplayer game experience, the AI is a vital part of that.
The second is the design that is used, Civ3 at regent provided a good challenge as Solver said, it could probably be al ot better though, but the big drawback is that it takes too damn long calculate all that. The multithreaded desing pretty much eliminates waiting.

I also think future TBS-games, especially if GalCiv succeeds, will have the same multithreaded design because of the progress with hyperthreading cpu's.

[Mark_Everson]

Originally posted by Lemmy
The multithreaded desing pretty much eliminates waiting.

I also think future TBS-games, especially if GalCiv succeeds, will have the same multithreaded design because of the progress with hyperthreading cpu's.

Agree completely! One of the reasons we went with Java for Clash is because of the threading support. It may not have come out in the blurb I put up above, but our AI is going to think in the background during the player turn also. As you implied, it really is a critical advance.

jdd2007, I think predictable is by definition not a 'best' strategy. At least when there are several fairly attractive options open to the AI it should be able to select semi-randomly from the good ones. A weighted-random choice amongst the few top strategies is probably best.

[DrSpike]

I am not a programmer so I don't know, but it seems to me that an AI that follows rules is only as good as the guy designing it. If that is true you can still have passable AI, with a lot of playtesting and tweaking on the designer's part.......but in my experience the level of both out of the box in recent years has been lacking.

[Mark_Everson]

Originally posted by DrSpike
I am not a programmer so I don't know, but it seems to me that an AI that follows rules is only as good as the guy designing it. (snip)

Hi DrSpike, I threw out a lot of text, but here is the way you get beyond scripted rules:

4. (snip) . . . encode the strategies as as individuals in a population of a genetic algorithm approach. We then pursue more simulations as in 3, but while tweaking the strategies through mutation and crossover. If the rule-based approach can give us any hints as to which are the most productive things to change, the more the better. The chromosomes will not generally contain numbers at all, but contain strategic objects. "Take Berlin", "obtain alliance against the Greeks".

This AI approach allows you to break out of the scripted rules. Its quality is only limited by the time available (how much the player takes at their turn) and the quality of the way we estimate whether a plan is a success. I don't think any commercial games do anything approaching this sophistication, although a few might. Whether we can make it work is a whole other question of course, but I'm confident we can do better than what's out there since we're not scrimping on the AI development time.

Galciv uses a good scripting system for its AI I'm told, I don't know if they do any evolutionary stuff or not.

[DrSpike]

Hmm, interesting. I think there will still be a big role in moulding the AI even using this method though........you addressed part of my point authorititively, but not the rest. Will companies that produce TBS spend enough time moulding their AI? To a point they do now, but not enough for hardcore gamers.......I've seen it time and time again with a wide range of games.

Hopefully a good chance remains with projects like yours, and other labours of love. Hope for all our sakes it goes well.

[Mark_Everson]

Originally posted by DrSpike
Hmm, interesting. I think there will still be a big role in moulding the AI even using this method though........

Yep A long open alpha and beta will help with that, but when you come down to it, its the time and creativity invested that will do it or not.

you addressed part of my point authorititively, but not the rest. Will companies that produce TBS spend enough time moulding their AI? To a point they do now, but not enough for hardcore gamers.......I've seen it time and time again with a wide range of games.

I agree. The big guys will only change when they are put at a competitive disadvantage by not having it. However, it may always be true for the bulk of gamers that they'd rather have the clocks invested in sexy graphics. I can't predict the way the market will bounce. . . But I think for at least the 10-20% that are hard core and stick with a good product that a niche market can be served by products with good AI if it doesn't compromise gameplay. Really good AI should improve gameplay immensely IMO.

Hopefully a good chance remains with projects like yours, and other labours of love. Hope for all our sakes it goes well.

Me too!

[DrSpike]

Originally posted by Mark_Everson

Really good AI should improve gameplay immensely IMO.

Amen to that. Personally I'd prefer more resources there than on outward appearance.....but we both know which way the trend is going.

[War4ever]

you can't create an ai that responds properly..its always based on options/probability/ etc......too many options confuse the ai like it confuses the human, except good players learn to adapt to similar situations..

you want a good ai, create one which learns from each game and adapts to the situation based on experience, not on a bunch of data which gives it too many options.

the ai also doesn't take enough chances in the game, which is what seperates great players from average players.

until the ai can learn from its mistakes, and counter punch a human, it will always lose

[Mark_Everson]

Hey War4ever:

Originally posted by War4ever
you can't create an ai that responds properly..its always based on options/probability/ etc......too many options confuse the ai like it confuses the human, except good players learn to adapt to similar situations..

Good AIs can also in principle be designed that focus on the most salient aspects of the situation. Not exactly with the same creativity that a human would have of course. But the computer can crunch numbers better, which can be turned to its advantage in some circumstances. Its just a Lot of work to do a really in-depth hierarchical AI, so it hasn't been done in commercial games to my knowledge. The AI can in principle look at a Lot more options than the human does.

you want a good ai, create one which learns from each game and adapts to the situation based on experience, not on a bunch of data which gives it too many options.

In principle this can be done, but it would take Forever to converge to a good experiential base for the AI that way using a GA or some similar approach IMO. The problem is designing a suitable objective function. In games where there's only a few decisions and a resolution is quickly reached, you can ascribe an advantage in principle to each move. Or at least you can know that a bundle of say three moves resulted in a win 63% of the time or some such. You can then use this to build crude reasoning based on experience for the AI. The decision space is so vast and nonlinear in a civ-type game that it would IMO take a database of probably tens of thousands of games at a minimum to evolve a decent experience base. YMMV.

the ai also doesn't take enough chances in the game, which is what seperates great players from average players.

Yep, that's another problem with the conventional AIs. I'm planning to put a risk-aversion parameter into the AI in Clash. Based on its level of toleration of risk and its strategic situation the AI should be able to decide whether its time to go for broke, or grin and bear it.

until the ai can learn from its mistakes, and counter punch a human, it will always lose

I just flat out disagree. The parameter space is far too vast to do the AI this way practically. Given the sizes of the decision spaces for such games it would be forever lurching one way or another due to brave extrapolations based on recent experience. You could do this sort of thing for a few parameters that affect what the AI does, but that's a pale shadow of what you'd like. And it would indeed be very cool if it worked. Maybe in 2025 it'll be practical.

We had a similar discussion on the Clash forum a few years (!) ago. It was about 4/5 of the way down the General AI thread, if you're interested. Starts with a post by Richard Bruns, his first in that thread.

Cya,

Mark

[alva]

Didn't read the whole post, but the people that don't don't visit these kinds of forums, will have a much harder (fun?) time with for example Civ3 then the rest of us. The AI is good, but the programmer is not playing against 1 person, he doing so against a couple of thousand all sharing their tactics.
Not to mention that the AI has to be flexible enough to work for all maps and has no idea what to expect, we do.
We decide which victory options don't fit our playing style and can turn them off if want to.
We don't like the start, hmm, ok, let's restart.
etc...

[DrSpike]

Originally posted by Mark_Everson
In principle this can be done, but it would take Forever to converge to a good experiential base for the AI that way using a GA or some similar approach IMO. The problem is designing a suitable objective function. In games where there's only a few decisions and a resolution is quickly reached, you can ascribe an advantage in principle to each move. Or at least you can know that a bundle of say three moves resulted in a win 63% of the time or some such. You can then use this to build crude reasoning based on experience for the AI. The decision space is so vast and nonlinear in a civ-type game that it would IMO take a database of probably tens of thousands of games at a minimum to evolve a decent experience base. YMMV.

Eloquently put..........and exactly what I meant about computers playing chess. The deterministic nature of the game makes for more implementable objective functions. The decision space, whilst vast, is more suitable for computer analysis.

[CapTVK]

Originally posted by jdd2007
i wish AI wouldnt be so predictable. even if they use the 'best' strategies, its worthless if you know exactly what theyre going to do.

Making an " unpredictable" AI (e.a that continually will come up with smart strategic/tactical surprises) is a lot harder than making a predictable good one.

[Lemmy]

I just flat out disagree. The parameter space is far too vast to do the AI this way practically. Given the sizes of the decision spaces for such games it would be forever lurching one way or another due to brave extrapolations based on recent experience. You could do this sort of thing for a few parameters that affect what the AI does, but that's a pale shadow of what you'd like. And it would indeed be very cool if it worked. Maybe in 2025 it'll be practical.

If it's done intelligently i think it's possible, the decision space can be confined by using parameter ranges instead of using exact parameter values.
It's true that it will need a lot of games before it is a good AI, but the AI can be trained while beta testing. And first tries with certain parameters don't even have to be bad if there still is a basic Civ AI present.

[Solver]

Lemmy, too many possbilities. The people who program AI just can't imagine every single thing that can happen within a civ game.

[DrSpike]

He was, I think, referring to previous posts about making AI adaptive.

[Lemmy]

He was, I think, referring to previous posts about making AI adaptive.

Yes, i was. An adaptive AI would be a solutionto the problem that there are too many possibilities for the programmer to see.

[Solver]

Adaptive AI isn't possible to build on our current tech basis, still!

[DrSpike]

Maybe, maybe not......see Mark's post. I'm not trying to be rude but have you actually read any of the posts in this thread besides your own?

[Solver]

Yup . Actually I never read my own posts... still such an AI is not possible .

[Lemmy]

Originally posted by Solver
Yup . Actually I never read my own posts... still such an AI is not possible .

What problems do you see with it then?

[Lemmy]

Actually, if it is imposisble, i'd argue that it isn't becuase of our tech, but because of the programmers ability and time.

Adaptive AI wouldn't require much processor power, it's basically looking things up, and saving new things. It would require more space, but the space needed can be brought down by an efficient design, for example by not saving all cases, but only the most "important" ones, and keep averages for the remaining cases.

[LDiCesare]

Lemmy, learning AIs are possible, but what do they learn? In a Case-based reasoning example, you need to code a comparison function to compare two cases, and may also need adaptation to adapt the previous solution to the current one.
The comparison function would be pretty awful to code in a civ-like game. Additionnally, new situations would arise which would be hard to manage, and CBR produces predictable responses.
Now adapting AI is possible within limits if the game has a set of "rules" which can all be adapted (mutated...).

[Lemmy]

The comparison function would be pretty awful to code in a civ-like game. Additionnally, new situations would arise which would be hard to manage, and CBR produces predictable responses.

Yeah, i realized that in my latest post, about the programmers ability.
Though it would be nice to expirement with it, in a dumbed down version of civ.....Civ3 maybe
Very nice actually now that i think about it, since i never programmed an AI before.
I'll add it to my list of projects to do...which is growing quite long now

[Solver]

What problems do you see with it then?

Not enough knowledge to mimic any real 'learning' patterns.