Howdy ya'll. Hope you don't mind the length of this post, but was sitting here brainstorming about how an empire-wide AI might work and thought this would be the thread to post it in. I do apologize for the detail, but I felt that examples help to clarify the concept. That being said, here goes. . .
***WARNING: VERY LONG POST***
I haven't really had the chance to take a look at the game's source yet (waiting for it to download while I'm writing this post), so some of the methods I suggest might not be feasible / whatever. If so, can just add code to make them feasible (ain't open source grand?
That being said, here's a method that I think might work for an empire wide AI, broken down into steps that the AI would follow and how the AI would evaluate its position on the map and what have you. I'll be breaking down the AI's turn into three distinct phases: study, plan, execute
I - Study
This is the phase when the AI looks at what its opponents have done and tries to interpret it. Because it's really hard to examine and interpret every move that a human makes, perhaps the AI could look at:
1) Distribution of firepower
This category would be a weighted value, corresponding to the amount of firepower a player could bring to bear on the closest AI-controlled system, tempered by the distance each ship is from that system. A high number on a large number of the AI's sectors means that an attack from that direction is likely.
For example, say that a player controlled 30 Mk. I. assault ships and had 18 of them in a sector adjacent to an AI's system, and another 4 in sectors with distance=2 from that same AI-controlled system, and the rest had distance=4 from that AI-controlled system, the value would be the sum of all ship's firepower rating / their respective distances from a single system. In this case, let's say the firepower of a single assault ship is 5. We would have (5*18)/1 + (5*4)/2 + (5*8)/4 = 110 against that sector.
Once we have found this value, we would run the same algorithm again, except this time we would run it for the AI's ships and subtract that value from the value we found for the sector (we'd also add one to the distance to reflect the fact that ships need to be in a sector to defend it). Say for the sake of argument that the AI has 31 ships, 15 of which with a distance=1 (they're in the sector), 4 ships with a distance of 2, 7 ships with a distance of 3, and the rest with a distance of 4, we'd have (5*15)/1 + (5*4)/2 + (5*7)/3 + (5*5)/4 = 75 + 10 + 11.6 + 6.25 ~= 103
These number could be saved for a few turns to study shifts in fleet distribution (indicate attacks, etc.)
The net firepower for that system would be -7, or the AI would not be able to get as much firepower to that system as quickly as a human could. By studying the distribution changes as mentioned above, the AI could watch for fleet shifts that might signal attacks and respond appropriately.
Perhaps once a fleet of ships have commited to a space lane, they could be treated as if they were already in their destination sector for the purposes of this method?
Time to run is number of ships * number of border systems (systems not surrounded by sectors controlled by the same player) * time it takes to find shortest distance from a ship to any given sector
2) Cultural analysis (if culture will play a role in the final game)
Culture would be better handled by individual systems in my opinion, but perhaps the AI could handle it in the following way:
Record the culture gains by player sectors and record how they've changed (average gained over the past 10 turns, record that for the past X turns to watch for cultural attacks on a given sector. To determine attacks, could normalize with respect to what has been gained over the past few turns (I.E. if sector A has seen an increase of 500 culture points by its neighboring sector, but sector B has only seen an increase of 20, it's probable that there's something weird going on against sector A).
3) Sector weight
Watching these distributions is all well and good, but the AI will need to make decisions when it all comes down to it. What should it fight for? What shouldn't it? That's where sector weights come into play.
I would propose that a sector be weighted by the % of all ships that have come from that sector both over the past X turns along with game-long along with the % of empire-wide production that comes from that sector.
Also, border sectors would be of higher weight than non-border sectors; it's easier to keep a solid perimeter than it is to have to go hunting through every system you own while looking for people that may have slipped past your defenses. Or at least that's how it should work in theory
4) Taking all this crap and doing something with it
By analyzing all this information, the AI can determine:
I) How aggressive / passive every player seems to be in various ways (high distribution of firepower over a small number of planets could imply that somebody probably likes to expand slowly)
II) What a player's overall strategy is (opponent is aggressive expand, passive culture. . . play defensively and try to win the person's people over with the intergalactic statue of liberty or perhaps the Pyramids at Polaris?)
III) What the state of the galaxy is. If force distributions are both moving toward each others' borders, for example, you could probably assume that two empires are building up for war.
II - Plan
The AI uses this phase to consult its personality and look up a few things:
A) "Should I be proactive or reactive (aggressive / passive)?"
B) "How certain am I that a player is doing X?" (learning component of the AI, perhaps? but I'll save that for another post)
C) "Okay, if player X is doing this, what does my schema tell me to do?"
So, using the information it gathered from step 4) above, the AI begins to think (or something like that). For example, if the AI notices that forces are moving toward each other and there's a relatively undefended border nearby, what's to stop it from declaring war on somebody and helping itself to a few planets before negotiating for peace again? ( that particular strategy works great vs. AI players in civ; might be fun to turn the tables
) It creates high-level plans with relation to each player, and then determines the best way to carry them out.
For example, say that player A and player B are at war. player C, our AI player for the moment, sees that player A left an open border to its galactic north. Next turn, BAM! player C invades the open northern border.
More specifically, player C notes that the aforementioned firepower distribution favors it by some margin and then goes. These margins could be largely determined by a player's personality (I.E. an aggressive species would be more likely to pull off a lightning-fast invasion and blow through five systems, and might be able to twist an opponent's arm to get a cease-fire again). Also, an AI might simply contact a player and say, "Hey, you idiot, you left your borders open. Pay me X / Give me X and I'll let you live."
Note that these plans are long-term plans, which is why this plan is seperated from the Execute phase below.
III - Execute
Execute is when an AI player can take the plans it formulates and make 'em happen. Much of this is relegated to independent governor AIs (like the kind in alpha centauri or whatnot) simply because those particular AIs should be tuned such that micromanagement isn't required. Ideally, anyway.
This phase will example what was determined during the Plan phase and determine exactly how to do it / how much should be done. Here's where tree searches come in handy; by analyzing a few moves deep, we can come up with an idea of how many ships we can produce before a war ends, etc. Prediction will play a big role in this process. To make it a little easier on the AI players, perhaps the whole AI-runs-on-the-player's-turn concept could be borrowed from GalCiv. Otherwise, tree searches could take a while (depth 4 search with so many possible moves is a scary thought). You could hack off parts of the search tree with heuristics and probabilities, but there's still a lot to look at there. Don't get me wrong, though; trees are the best way I know of to get a semi-accurate picture of what's going in the short term. Long term relations don't change quite so quickly, so it's a whole lot easier to get away with not using trees in the Plan phase.
There is one more vital component to throw into the mix: trust.
In my mind, trust would factor into the Study phase. . . treaties would increase trust and give bonuses to the various computed statistics perhaps, while previous broken treaties would take away from that up to a certain point. Trust would be easier to regain at easier difficulty levels, and some personalities would naturally be more trusting than others.
This could be implemented as a trust table contained by an AI player that contains the current trust level for any other player. Higher trust would be worse, but any given trust entry for another player would decrease at a rate corresponding to the difficulty level of the AI along with their personality.
Diplomacy would be largely related to trust. A larger trust value would mean that somebody isn't as trustworthy, and therefore shouldn't be trusted. Also, perhaps to encourage cooperation between species, intergalactic goodwill, etc., you could introduce the concept of a contract.
Contracts would be enforced by the Senate (the body mentioned in another post somewhere). If a contract were to be broken, you could introduce penalties that would be stipulated at the time the contract was signed (I.E. a peace treaty between two nations, with the stipulation that, should either side break it, they would be responsible for reparations paid to the Senate AND to the victimized party in the amount of X. . . a way to get around the whole 'never trust someone again' thing). People would the option to A) withdraw from the senate, a decision causing them to be slapped with a trade embargo + exile from the senate for a set number of turns or B) pay the reparations in turn-ly increments.
Just ideas / concepts, some of which were borrowed from games (think I mentioned it when I did that, though I can't be certain; sorry if I missed something!) Hope this is useful to somebody.
Also, great job so far! Game looks neat.