AI Wars

By on November 15, 2010 11:29:29 AM from JoeUser Forums JoeUser Forums

Frogboy

Join Date 03/2001
+1117

To best understand the AI of v1.1 one must first understand the nature of threads.

In a normal game, the players all function in a single thread. There is a while loop in which various components of the game are given the opportunity to to do their part – draw something to the screen, look for player input, update the game state and of course, move the computer AI.

In most games, including v1.0, the AI does all their work at the end of a turn.  This is why in most games you hit the turn and there is a delay, the AI is having to think about and plan what they do.

The challenge, of course, is making sure players aren’t waiting too long between turns, especially if the game locks them out of the UI (which is the norm).

But there is another way: Threads.  Threads allow you to have different things computing concurrently. Even on a single-core machine, threads can make a huge difference. Threads are the reason why Stardock games have historically had such a strong reputation for good AI.  The AI can be calculating strategies while the player moves. There can even be background threads that do nothing but look at the game state and set various flags for the AI to act on when the time is right.

Threads are the reason why Galactic Civilizations II was able to have some of its most infamous diplomatic moments such as “So, I see you’re building up quite a fleet there, so let me guess, you’re going to mass up for an attack, take my planet and then sue for peace? Well, sorry but in the meantime, I’ve been putting ships around your ships..”

In the OS/2 version of GalCiv (back in the 90s) that had cloaked ships, players were greeted with the horrific realization that the AI had surrounded them with cloaked ships and preemptively wiped out their massed fleet.  And this was back when the game was made with 486’s in mind.

Threads rule.

So why not threads?

Why do games (including Elemental v1.0 and other major strategy games of 2010) not use multithreaded AI? Debugging. If multiple things are touching bits of memory, modifying variables, creating or deleting objects it can be a real pain to coordinate.  The bigger the team, ironically, the harder it is to do. 

Plus, truth be told, most people just aren’t that comfortable juggling many threads. It requires a different way of solving a problem. It’s a bit like recursion, they can be hard to envision if you’re not used to it. 

On Elemental, I didn’t have the opportunity to go into that.  On our other games, the only coding part I was responsible for was the AI (except our earliest games).  On Elemental, things went somewhat..differently. By the end of the project I had added lead developer, producer, and design implementer to my hats so the AI had to be done in the more traditional way.

Now that we have Kael to take charge of production, Toby as design implementer and CariElf back as lead developer, I can do for Elemental what I do best: Multithreaded AI development.

Threads: Breaking a problem up into components

When you play a game, what are the things you do? What are the mistakes typical in computerized opponents?

The most obvious is that you’re looking and thinking about your strategy all the time.  So let’s look at the threads we should have in Elemental:

1. Global Strategic AI thread. This is little more than one big while loop that sits in a thread. It’s very low priority and all it does is look at the map and see what sorts of pre-designed situations have been triggered.  Think of it as pattern recognition. If it recognizes a pattern, it sets a flag and the AI in question then begins to deal with it.  This is where players can have the most impact by telling me what sorts of cheese they do to thwart the AI.

If I were writing the Starcraft AI, for instance, this thread would be the one seeing if I’m about to get baneling rushed or if photon canon rushed and deal with it. 

It also sets flags on known items as to whether they should be targeted for control, imbued, recruited, killed, etc.

This is NOT like an expert system or a neural net because the AI is not learning. It is adapting to player strategies but its choice of adaptations is limited to what we (the Elemental community and I) come up with.  Eventually I hope to export this as a C++ DLL for others to play with or better yet make it available in Python but that’s aways off.

2. Player Strategic AI thread. This is the thread that handles deciding what should be built, what strategies it should employ, where it should send its soldiers, what spells it should cast, what type of unit it should design, what technology it should research, what city improvement should be built.

3. Tactical Strategic AI.  The tactical battles are the one part of the game I’m not involved in yet. We have two capable developers handling that.  I won’t be taking that over until the expansion pack.  But that will become another AI thread down the line as a background thread looks at every army group and sets what types of strategies they should employ generally as well as potentially against any enemies that are near by.

Testing the AI

This is my AI map for v1.1 Beta 1. The goal with this map is to teach the AI how to play the game effectively using the v1.1 game mechanics. 

 

image

This battle will be the subject of my  next journal entry.

30 Replies
Search this post
Subscription Options


Reason for Karma (Optional)
Successfully updated karma reason!
November 15, 2010 11:49:10 AM from Elemental Forums Elemental Forums

Spectacular!  The open conversations about development...and implementation of user feedback is exactly why I love Stardock.  Buying a Stardock game, you always feel like you're part of a cool process...and I, for one, thoroughly enjoy knowing my purchase has no ceiling.  Amazing things will continue to be considered and integrated into patches and add-ons.  

 

Thanks for involving us!

 

 

Reason for Karma (Optional)
Successfully updated karma reason!
November 15, 2010 12:00:11 PM from Elemental Forums Elemental Forums

This was a great read.

I look forward to more updates on your progress.

Reason for Karma (Optional)
Successfully updated karma reason!
November 15, 2010 12:08:29 PM from Elemental Forums Elemental Forums

Very nice!! Thanks a lot for all the infos.

Just a quick Q: Did i get it correctly that, the Global AI oversees the full map and all strategic AIs can access all flags set by it? It would be much cooler to only provide each player AI with flags on information within their line of sight, wouldnt it?

But maybe thats already in there, then appologies for the question

Reason for Karma (Optional)
Successfully updated karma reason!
November 15, 2010 12:23:59 PM from Elemental Forums Elemental Forums

Stuff, like this is why I decided to give my money to Stardock for EWoM, now.  As opposed to however long it takes to get it where it needs to be!

Reason for Karma (Optional)
Successfully updated karma reason!
November 15, 2010 12:25:17 PM from Elemental Forums Elemental Forums

Question: how hard would it be to make an AI that is capable of learning?

 

I think that's the next step in AI, and one that I really want to see someday.

 

 

Reason for Karma (Optional)
Successfully updated karma reason!
November 15, 2010 12:52:00 PM from Elemental Forums Elemental Forums

Brad, 

Great insight!   As others have stated it is this type of information about the game that keeps me coming back to Stardock games.    

 

On another note:  Please don't shy away from putting out the c++ dll.  Some of us software developers would love to play around and help out if we can by adding our own variations to the ai.   

 

Looking forward to the battle report.  

Reason for Karma (Optional)
Successfully updated karma reason!
November 15, 2010 12:56:22 PM from Elemental Forums Elemental Forums

Great read! Thank you.

Reason for Karma (Optional)
Successfully updated karma reason!
November 15, 2010 12:57:12 PM from Elemental Forums Elemental Forums

I want to know how the AI will handle user made content? Will it be similar to the way it is currently handled in 1.09?

Reason for Karma (Optional)
Successfully updated karma reason!
November 15, 2010 1:18:24 PM from Elemental Forums Elemental Forums

Brad, while doing the AI thing, do you think you could skim over how the AI selects mounts? I tried adding stronger mounts but the AI never used them. I will quote this from the dev request thread in the modding forums:

Quoting Heavenfall,
While I was doing the expandedmounts mod I came across a very specific problem. The mod, in its non-public stage, added 5 world resources that you could build improvements on. These mimicked the functions of stables for horses and/or wargs, but added new types of resources used for new types of mounts.

No matter what I did, the AI would never ever use the mounts. So I sent a whisper to Cari_Elf and asked how the AI selects mounts, and was informed that the AI, in 1.09e, simply selected the "first one on the list". I asked if the list was sorted in any way, for example through availability through resources and/or added strength and the reply was that it wasn't.

I guess my request would be that the "mounts" type list has some kind of sorting applied, so that it chooses the strongest available mount for the unit. That would be the small request. For example, drakes were intended to give the rider 2 strength, 2 dexterity, 2 combatspeed and 3-5 hitpoints. A brute, for comparison, was going to give 1.5 combat speed, 2 strength and 2 hitpoints.

The big version of the request would be that there was some sort of system that allowed modders to tell the game AI what items were powerful and what weren't. For example, a modded armor might have a low defensive value but a strong ability it unlocks (like combat regeneration). That item might be much stronger than another item with only higher defensive value, but the item with the higher defensive value would always be chosen by the AI. Ideally, this "power value" would be optional, like the <Shopvalue> tag - it can be included, but doesn't have to be.

 

Reason for Karma (Optional)
Successfully updated karma reason!
November 15, 2010 1:26:52 PM from Elemental Forums Elemental Forums

Another excellent thread. This stuff keeps me interested while waiting for 1.1

Reason for Karma (Optional)
Successfully updated karma reason!
November 15, 2010 1:47:12 PM from Elemental Forums Elemental Forums

Hope.

Reason for Karma (Optional)
Successfully updated karma reason!
November 15, 2010 1:54:54 PM from Elemental Forums Elemental Forums

Very cool read!

I like the look of that map by the way. Release that!

Reason for Karma (Optional)
Successfully updated karma reason!
November 15, 2010 1:57:39 PM from Elemental Forums Elemental Forums

The threaded AI sounds great, it should decrease the thinking time of the computer. But I'm interested to know how the actual AI is improving in the 1.1 patch. Have there been any major changes to the AI? Have any player strategies been implemented (I remember people uploading their saves so you could see how they were winning)? In general, how much smarter is the AI in this patch over the previous one (i.e. will I get my butt kicked a lot faster on harder difficulties, or is that coming later in a patch)? Thanks.

Reason for Karma (Optional)
Successfully updated karma reason!
November 15, 2010 1:59:05 PM from Elemental Forums Elemental Forums

Love reading this sort of thing. I have been writing games for 25 years but nothing this big and so it is really nice to see how the experts do stuff. Thanks for sharing.

Reason for Karma (Optional)
Successfully updated karma reason!
November 15, 2010 2:16:06 PM from Elemental Forums Elemental Forums

Quoting Lord Xia,
Hope.
Anew?

Reason for Karma (Optional)
Successfully updated karma reason!
November 15, 2010 2:19:56 PM from Elemental Forums Elemental Forums

really cool.........

Reason for Karma (Optional)
Successfully updated karma reason!
November 15, 2010 2:30:56 PM from Elemental Forums Elemental Forums

Quoting Lord Xia,
Hope.

Yup.

Good to have you back where you belong, Frogboy.

Reason for Karma (Optional)
Successfully updated karma reason!
November 15, 2010 2:32:54 PM from Elemental Forums Elemental Forums

How interesting, this has dispelled the mystery behind what is meant exactly by multi-threaded AI.  Cant wait to try it out in the beta.

Reason for Karma (Optional)
Successfully updated karma reason!
November 15, 2010 2:34:20 PM from Elemental Forums Elemental Forums

Quoting bboybutzemann,
Very nice!! Thanks a lot for all the infos.

Just a quick Q: Did i get it correctly that, the Global AI oversees the full map and all strategic AIs can access all flags set by it? It would be much cooler to only provide each player AI with flags on information within their line of sight, wouldnt it?

But maybe thats already in there, then appologies for the question

That's how it works. One thread goes through each AI and looks at what they know about.

Reason for Karma (Optional)
Successfully updated karma reason!
November 15, 2010 2:36:43 PM from Elemental Forums Elemental Forums

Just hope this game can reach in reality what we all want it to be.

Reason for Karma (Optional)
Successfully updated karma reason!
November 15, 2010 3:00:51 PM from Elemental Forums Elemental Forums

Quoting ,
The most obvious is that you’re looking and thinking about your strategy all the time.  So let’s look at the threads we should have in Elemental:
1. Global Strategic AI thread. This is little more than one big while loop that sits in a thread. It’s very low priority and all it does is look at the map and see what sorts of pre-designed situations have been triggered.  Think of it as pattern recognition. If it recognizes a pattern, it sets a flag and the AI in question then begins to deal with it.  This is where players can have the most impact by telling me what sorts of cheese they do to thwart the AI.

Did ya consider letting that work for the player?

Lets say on the lowest two difficulty levels you can activate "the advisor" who once in a while notifies you of stuff you should take seriously.
That would help players when learning the ropes.

It wouldn't have to spill all it's secrets and patterns. Some wouldn't be structured right for human use anyway and you wouldn't want to train the player to exploit the AI too well. =P

Reason for Karma (Optional)
Successfully updated karma reason!
November 15, 2010 4:47:09 PM from Elemental Forums Elemental Forums

Sounds great from what is there.  I had one question based on how the AI will makes its decisions.

Does the Player Strategic AI thread take the Faction's "personality" into account when making decisions? Or will it simply make the "best" decision?  For example, will all AIs decide to research or build up more military if the Human starts building up military or will military factions focus on military and diplomacy factions focus on diplomacy?  Or this this more of a "down the road" type thing?

Reason for Karma (Optional)
Successfully updated karma reason!
November 15, 2010 5:17:01 PM from Elemental Forums Elemental Forums

Sounds great from what is there. I had one question based on how the AI will makes its decisions.

Does the Player Strategic AI thread take the Faction's "personality" into account when making decisions? Or will it simply make the "best" decision? For example, will all AIs decide to research or build up more military if the Human starts building up military or will military factions focus on military and diplomacy factions focus on diplomacy? Or this this more of a "down the road" type thing?

I think it would be cool if you could set some kind of flag for each AI player so that you can tailor the AI to your game. Something like warlike/diplomatic/expansive. This would allow players to customize how the AI approaches the game.

Reason for Karma (Optional)
Successfully updated karma reason!
November 15, 2010 5:33:32 PM from Elemental Forums Elemental Forums

Why do games (including Elemental v1.0 and other major strategy games of 2010) not use multithreaded AI? Debugging. If multiple things are touching bits of memory, modifying variables, creating or deleting objects it can be a real pain to coordinate. The bigger the team, ironically, the harder it is to do.

That just screams 'Haskell!' and transactional memory

Reason for Karma (Optional)
Successfully updated karma reason!
November 16, 2010 6:41:33 AM from Elemental Forums Elemental Forums

Great read! Thanks a lot!

Reason for Karma (Optional)
Successfully updated karma reason!
Stardock Forums v1.0.0.0    #108432  walnut2   Server Load Time: 00:00:00.0002407   Page Render Time: