Ship AIs that talk to each other

[AngleWyrm]

Ever notice how, in the typical RTS, a hoard of units (Scorpion Spam, Zerglings, etc) require micromanagement in order to focus their fire properly? Even then, a player is usually forced by time constraints to bandbox their entire herd, and sequentially target enemies. A waste of firepower in both scenarios. So...What if units could communicate with each other? How could this help? I think best with examples:

Red advances a carrier group onto Blue's planet, with the goal of invading the planet. So we have two lists of combatants, Red and Blue. Red team starts by sorting his enemies list in order of closest to the enemy, and then begins with the conversing:

Red[1] is the lead gun ship, (fighters haven't been released yet), and closest to the nearest enemy, a blue gun ship. Red[1] calculates that it will take five volleys for him to destroy the enemy, and will expose himself to significant return fire doing so. Red[1] examines Red fleet and finds that there is enough firepower to take out that enemy. So Red[1] announces to his fleet that his is now taking bids for a contract on Blue's lead gunship. The contract requires a total of five of his volleys to decimate the enemy in one go.

Next up, Red[2]. Red two first examines the contract board and finds one available (Red[1] did this too, but there weren't any). So Red[2] makes a tentative bid for the contract, offering his firepower as the unit of measure. Then Red[3] gets a turn, and so on through their fleet.

When Red[1] comes up again, he sorts the bids according to firepower (possibly by range as well), and selects the top ones that can make it happen. Then he sends a message to each Red team member who has been selected, making it a binding contract. Then he marks the contract closed on the message board.

When it comes time for a ship to move, it first checks to see if it's in a binding contract, and if so it attacks that target.

Also, if any member of the contract's team loses some firepower (or dies), they flag the contract as 're-evaluate'. the the next member to do evaluations will re-examine if they can still pull it off. If not, that ship announces the contract is null and void, and works on maybe announcing a new contract.

--
This thought gleaned from reading Multi-agent systems, a Modern Approach

[Suicide Junkie]

The main concern is processing time, of course... battles already take long enough.

A simpler version of that would be to have each ship list its current target, and how much damage it expects to do.
When picking a target, each ship would check the list, and not shoot at a particular target if the fleet already has enough firepower targetted on it. ("Enough" being determined by the strategy's overkill factor)

Then, if there are no targets left, the ship should decide whether to hold fire and wait for a good target, or just fire anyways.
Weapons with a short reload, and those with little to no ammo usage would be more likely to be fired anyways, while long-reload or expensive weapons should not be wasted.
How to specify the above fire/hold settings is left as an exercise for the reader.

[AngleWyrm]

I have an older model CPU: An AMD 3200+ that runs at a frequency of 2 Ghz. That's two billion instructions per second.

It's up to the programmer to do speed optimizations where appropriate, which is usually handled by profiling the code and then tightening up the sections that take up the most time.

It could just as easily be the way the program parses text files that is causing it to run slowly. But again, without actually profiling the code, it's all just speculation.

[Patroklos]

In SEII, you could target each ships weapon on a specific target. Or each fighter groups target. Doing this every round was very tedious, but advantageous.

[Will]

AngleWyrm said:
I have an older model CPU: An AMD 3200+ that runs at a frequency of 2 Ghz. That's two billion instructions per second.

It's up to the programmer to do speed optimizations where appropriate, which is usually handled by profiling the code and then tightening up the sections that take up the most time.

It could just as easily be the way the program parses text files that is causing it to run slowly. But again, without actually profiling the code, it's all just speculation.

Well, that's partially right... a 2Ghz CPU has two billion clock ticks per second, but not necessarily two billion operations; the Athlons had a theoretical issue rate of 6x (micro)instructions per clock, for maximum theoretical 12 billion operations per second... however, it isn't often you will decode 6 instructions every clock, and since it is an out-of-order architecture, not every operation that issues will necessarily be completed. If you have a program that is almost entirely cache-resident, then you could probably get it up to 5 or so billion ops/sec.

And these days, it's up to the compiler to do profiling optimizations, not the programmer. The only optimization really left to programmers now are macro-level... i.e. choosing a O(n log n) algorithm over an O(n^2) algorithm.

And yes, I/O is the main bottleneck in computation. Fetching a 512 byte block from disk to memory (usually 512 is the minimum, it can go higher) takes on the same order of time as several million instructions. You can optimize that away to a point, such as by prefetching blocks from disk, but it is not always known what block will be needed, so prefetching doesn't always work. The same for fetching from memory, bringing a page of memory to the cache takes on order of hundreds to thousands of instruction cycles. And then from cache to registers takes on order of tens to hundreds of cycles.

Anyway, with regard to the algorithm itself: it's a standard auction algorithm, fairly common in AI literature. It's popular because it's fairly fast, gets close to optimal results most of the time, and is simple to understand and implement. It is a close relative to the Traveling Salesman problem, so there is no known polynomial time algorithm that will give the optimal solution; auctions get close (minus a few fringe cases) in O(2n). If a system can play a graphical RTS game, it probably can also do this algorithm at the same time, since the graphics take far more processing than the algorithm does.

</computer-nerd>

[PvK]

It's not a processor power problem unless the code is clumsy. It's been done.

[Thy_Reaper]

I think implementing this only makes sense, although I think it has been implemented to a degree already. I asked MM if he could fix the overkill option that didn't seem to be working, and he claimed that ships now take into consideration how much damage has been targetted at a ship, but it's not that easy to test to see how effective this is.

[AngleWyrm]

Will said:
And these days, it's up to the compiler to do profiling optimizations, not the programmer. The only optimization really left to programmers now are macro-level... i.e. choosing a O(n log n) algorithm over an O(n^2) algorithm.

Compilers can do a lot, but the coder should look at a profile as well. In one project (Hat random container), when I profiled the code, I found out that it was spending a lot of time in one particular function call (the update_weights function). With this information, I was able to get a good speed boost by moving one locally constructed variable into a class member position.

[Will]

AngleWyrm said:

Compilers can do a lot, but the coder should look at a profile as well. In one project (Hat random container), when I profiled the code, I found out that it was spending a lot of time in one particular function call (the update_weights function). With this information, I was able to get a good speed boost by moving one locally constructed variable into a class member position.

Yes, but that's still what I would call "macro-level". You're getting the speed boost because instead of calculating a value that doesn't change much n times, you store it in a higher scope and calculate it fewer (one?) times. That's an algorithmic choice, much like choosing mergesort over bubblesort is, only with less dramatic results.

Even then, compilers will do a lot of that within function or method blocks. It can't be done like you were saying up to the class-level, because then optimizations would be changing the data-structure of an object, which breaks compatibility with un-optimized code. But anything that is in a self-contained block with an immutable interface to other code the compiler will optimize better than a human programmer would. So, it's best not to worry about those and focus instead on building good algorithms and data structures.

--edit: and damn! I wish the people I work with commented their code thoroughly like you did. Just a note, you may want to split hat.h into hat.h and hat.cpp, that way if you ever make a change to the methods that don't affect the interface, you don't need to recompile everything that #includes hat.h. It's a habit best learned early, lest you need to recompile and relink thousands of source files instead of just relinking thousands and recompiling one

[AngleWyrm]

Thanks on the comments commentary; I'm a big believer in them too. The best thing I learned on comments is make them read at a higher level than the code they describe.

About the single-file implementation: I had read that templated classes have problems with putting the implementation into a separate file, but I don't remember the specific reason anymore. Seems like it had something to do with the way compilers generate code for each used template-parameter pair.

Have you had a different experience with templated classes? Do they work in a normal two-file header/source layout?

BTW, Happy Birthday!