Edna Lynx

Join Date 03/2006

Artificial Inteligence and CPU Times

I just read a journal entry from Mr. Big Boss at Stardock and I have to disagree with the information about AI algorithm, CPU times and stuff.

I can understand that it is very limiting having to write algorithm that must be executing in timely milisseconds but, but in my humble opinion, more important that produce fast algorithm is to make them time efficient.

In the world of multi-threading, much can be made while the player is taking its turn. The AI characters can perform a lot precalculations before is their time to play.
In my experimental AI code, I like to split the AI into smaller pieces of code I call agents.
The main AI analyse information provided by those agents (wich by turn have that information pre-calculated) and them take decisions based on them.

The result is a very code efficient and realistic AI code. I say realistic because the communiction between the agents and main AI may result in interesting misunderstandings and this will result in unpredictable results. By unpredictable I don't mean buggy, but simply hmm... unpredictable, they may not take the same decision in very similar situations.
To improve unpredictability, another think I like to do is, when aplicable, limit the communication between the agents to the main AI to "subjective opinions".

For example (in the context of GalCiv2), if the main AI need to improve production is may ask a planet about their production capacity and instead of returning a number, the planet would simply answer: my production capacity is "very high" or "low" or "at maximum capacity". The main AI would then use this information to decide if is would ask the planet to improve do something or switch to another planet.

Another advantage of this model is that it is very easy to implement new features since it is just a matter of adding new agents and reconfigure the main AI to consider the new parameters.

Thanks for listening...

Kisses from me,

Edna

Locked Post

Advanced Search

Watch this post

Do not email me updates for this post Email me updates for this post

Successfully updated karma reason!

Xan

Join Date 01/2003

+29

The AI in GalCiv IS multithreaded.

It's one of the things that the game is famous for.

Just do a google search. While the player is moving, the AI is calculating. That's one of the reasons why there's little time between turns.

I found this right away on Google:
http://www.strategy-gaming.com/reviews/gal_civ/

One characteristic of the early GalCiv was multithreaded AI (a technology possible even in early versions of OS/2), and the newest incarnation makes good use of it as well. While most strategic games have to do a terrific amount of number crunching to run the AI after you press “next turn”, GalCiv is uniquely different: the AI is running all the time in separate ‘threads’ in the background. In fact, GalCiv has been hailed as the first computer game to use Intel’s new hyperthreading to good effect. (Note: you don’t need a hyperthreaded processor to run the game, but if it’s available the multithreaded AI will take advantage of it to run even faster.) When you hit “next turn” – even in the later game stages on huge galaxies where hundreds of ships and planets are all doing their thing – it processes quickly, even with the meager minimum / recommended system requirements.

This was apparently true in the OS/2 version.

Next time you want to call out the AI deveoper you should know what you're talking about.

Successfully updated karma reason!

Xan

Join Date 01/2003

+29

I still can't believe that someone would have the gall to come on and tell someone how to write a computer AI without having bothered to see if their "great idea" had been used for decades by the same developre.

Simple google search for GalCiv and multithreaded AI and you get a lot of talk about it.

here's another:
http://pc.ign.com/articles/096/096013p1.html

Brad Wardell: Okay you're playing Civilization and you're about to double-cross the Mongols or whoever and so you put all of your tanks around their city, right? And then you make your attack. Well in GalCiv the AI, because it's multithreaded, can do a scan and it can recognize certain patterns of behavior and say, "Oh, well this guy's slowly surrounding my star system with his heavy battleships, that means he's going to attack and based on what he had done before this is how many he'll probably have to have in order to successfully take it. So I'll move stealth ships, which are cloaked ships (you can't see him) and surround him. And at the right moment I'll make a preemptive attack."

From a programming point of view, that's not rocket science, but it takes a lot of calculating time to do it -- to actually go through and say, "Okay he has eight battleships around my star system and he's going to attack." But if you're multithreaded you can have the AI thinking between turns and slowly come to that conclusion without it affecting the player's experience. So when they're playing a game and all of the sudden they get zinged and they see this they go "Wow I can't believe the AI is so smart or so good." It's just that we had the time to calculate it whereas in a single threaded game, a typical strategy game, you hit the turn button, the computer starts thinking and you can't really do too much because the player's just sitting there waiting. But if we're doing our calculations while the player is moving and they aren't even aware of it, then we can do a lot more fancy stuff.

In other words, the AI not only already operates in its own background thread but always has since the first version for OS/2.

Successfully updated karma reason!

Well all I can say is let us know when you write your 4X TBS game with this fantastic *agent* based AI and we'll be sure to look it up. Theory is fine but in practice a lot of these sorts of things just do not work when dealing with a complex environment. Sure for a couple of tasks with very well defined rules what you suggest would work. But I'm willing to bet that if you had to modify it to handle more dynamic situations you'd start to understand just how complex it is to say optimize a planetary layout not just with the best buildings for the planet but the buildings that help out the overall empire as well.

You might want to check out a web site called The Game AI Page: Link. There is a lot of research out there in terms of game AI. However since most companies think of AI last in terms of scheduling for the most part a lot of the pomising things that could be done are not. If nothing else GC2 probably had more AI development done by probably a factor of 10 then any other game in the last decade.

Successfully updated karma reason!

The AI in GalCiv IS multithreaded

Where in my post do I say it is not?

I still can't believe that someone... bla bla bla... "great idea" had been used for decades by the same developre.

Did you ever heard about evolution? Improvement?

Successfully updated karma reason!

Well all I can say is let us know when you write your 4X TBS game with this fantastic *agent* based AI and we'll be sure to look it up.

Thanks for you replay, Cyber... finally an inteligent comment.

Theory is fine but in practice a lot of these sorts of things just do not work when dealing with a complex environment. Sure for a couple of tasks with very well defined rules what you suggest would work. But I'm willing to bet that if you had to modify it to handle more dynamic situations you'd start to understand just how complex it is to say optimize a planetary layout not just with the best buildings for the planet but the buildings that help out the overall empire as well.

I understand your cepticism, Cyber, but this theory was tested with complexity levels much greater than this game. This work was first developed to simulate a real economic system and were designed scale the complexity levels with the number agent layers (vertically) and horizontally with the number of agents at each level. Off course CPU processing grows but not proportionally.

You might want to check out a web site called The Game AI Page There is a lot of research out there in terms of game AI. However since most companies think of AI last in terms of scheduling for the most part a lot of the promising things that could be done are not.

This is the worse problem of our current economic system. I will check the site though.

Thanks for your reply,

Kisses from me...

Edna

Successfully updated karma reason!

Edna, sounds like you can be a valuable addition to the Stardock dev team...

Successfully updated karma reason!

As complex as an economic system can be to model you still are talking about only one aspect of a this game system. Sure there are a lot of variables to consider but for the most part a forecast system does not imply *thinking* mearly number crunching. Also did this economic system have to decide what areas to develop, allocate the proper resources, and then oversee the project to ensure it stayed on budget? And for that matter did it drive your car home? You see an AI designed for a well defined set of rules is much easier to build then something that must cope with several very different tasks and not take hours to give an answer back.

I'm only skeptical because unfortunately a lot of times on public forums you get people who read a few phrases on a web site and then try to pass themselves off as some sort of expert. So without web sites and/or games that use it to prove what you are saying is viable I take it with a grain of salt

. I keep up with this sort of stuff simply because it fascinates me how complex it can get code wise to even attempt to get a computer to do what a human find trivial in terms of function. Number crunching yeah a computer can thump anyone but have it try to explain what those numbers mean

.

Also there have been games in the past that tried to use a supposed *neural net* agent setup that you describe. Can anyone say Battlecruiser 3000 AD?... anyway in all cases it failed horribly. But the research does continue so there is hope that one day someone will make the sort of breakthrough that quite a few people were expecting this AI to be. There is a game developers conference every year where they discuss these sorts of AI issues. And out of none of those meetings has there ever been the sort of AI you describe. So either you know something they don't or what you describe just won't function in a game situation. It's real easy to say *I would do it better* without actually having to back it up.

Successfully updated karma reason!

Brad did say that they did make sacrifices in the AI to make it quicker. Personally I would prefer the AI was better than quicker. Even a slower AI would probably be a lot quicker than a human player.

Successfully updated karma reason!

They've already posted that an option is coming to give the CPU more time to think if you want. So we'll see what happens when that change goes through

Successfully updated karma reason!

I would suggest a "simple" thing to stardock.
Expose the data about the game objects to be scripted or even better to be executed by an external dll. Allow that same script to call actions that human players would trigger.
Then I will show you what can be made.

Thank you for your reply, Cyber.

Kisses from me...

Edna

Successfully updated karma reason!

I think I've seen other requests that SD make the AI something that can be modded but honestly don't think I've seen an official reply about that. If they hadn't planned on making that sort of option available I doubt they would rewrite the entire AI structure just for this sort of thing. So I hope you said *simple* with a bit of sarcasm

.

Aside from that really there is no need. I'd be happy with any game that uses what you suggest. While not trival to build to be sure something that proves what you say is viable would not need to be pretty or even a *commercial* type game. Something as simple as just a oh I don't know... a planetary building AI would be interesting. Have it decide what to do with oh I don't know say 30 different planets all with varing numbers of tile to build on with say just the core planet buildings (factory, lab, farm, morale, influence, econ, and starpot) and lets see a) how long it takes to put the planet together and

how well it manages the empire with different strategies in mind. Say tell it you want a conquest strategy empire or an influence strategy or a research strategy. That can be wrapped up in a simple MFC program probably in an afternoon. Oh and it has to do it within just a few milliseconds for all 30 not each.

Then to get more complicated you tell it it has a budget to worry about. Then you add the pattern recognition to attempt to figure out given a fixed board of squares what a player may be thinking based on ship placement on those squares. And thats still only 3 of the dozens of things the AI in this game has to cope with. All with no x->y->z scripting.

Then we'll talk

And beyond all that even if you don't personally have the expertise to build a game nor the capital to put together a company to do so there isn't anything stopping you from wrapping this wonderful AI into a 3rd party library for game devs to use. There are already several such AI packages though admittedly they are usually limiting and really designed for only one genre of game. But if what you have is so revolutionary it would blow everything else off the map.

Successfully updated karma reason!

I recall reading that their first response was that they didn't think modders could do a good job as they did. But later Brad i think mentioned that once they are done with the patching (which will be what? In a year?), they might consider exposing the AI system for modders to tweak.

Successfully updated karma reason!

Hi dear,

No... it was not sarcasm. Actually I didn't meant them to rewrite the AI, but actually allow external code to be executed in answer to certain events. This way I could test my AI theories without them have to rewrite anything.

To expose events and data to some extent is not a complicated task. I think they could do that, but not for because of only me.

Kisses from me...

Edna

Successfully updated karma reason!