production AI

[The Silent One]

I've done some thinking on how a production AI might work. This is just a rough outline, with some details not clearly worked out, some inefficiencies remain; still, if you'd like to help, take the time to read and point me to mistakes, make suggestions how you think it should work... ok let's go.


Step 1: Calculate needs of empire

The basic question of production management is: what do I need to run my empire? So the AI emperor needs to determine what demands his empire has. Demands as:

- for resources: look if specific resources are required
- for exploration: look if enough scouts are available
- for expansion: look at empire size in relation to other empires/galaxy
- for military, defense: peace-war state, current fleet strength of own empire/other empires
- for shipyards: min 1, depending on empire size; no shipyard => great need to build one

- depend also on personality of AI leader: expansionist, militarist, scientist, economist etc.


Step 2: Create a list that holds all buildable items, figure out which demand(s) they satisfy and how much they satisfy it

The AI will need to know what ships and buildings are available to build. For that reason I'd compose a list that holds all ships and buildings which are available. ShipDesign and BuildingType will be mapped to a productionItem type and written into a list (availableProductionItems). (This has the advantage that the AI won't have to think in categories, it'll be able to just ask itself which item will satisfy its demands and not from which category an item is.)

Code: Select all

type productionItem:
  name = "" # string
  type = (none, ship, building)
  ID = original ID of sb (shipDesignID, buildingType)

  demandsSatisfied = [...] # (none, exploration, expansion, minerals, production, money, science, military, shipyards)
  demandsValue = [...] # list of integer

At this point all items that can not be build for some reason (eg., no location to construct a building or no shipyard available), should be removed.

So now we have all buildable items at hand, but the AI will also need to determine what kind of demand(s) an item satisfies. For this, it will need to know:

- about the purpose of a ship (colonisation, exploration, war, etc); will store in a dictionary what ship purpose a design name belongs to
- as well as the purpose of buildings (do they promote resources, which type?, defense, etc); should be able to [read the buildings effects or] derive this from a list
- recognize shipyards

- As well as how well a productionItem satisfies a demand. (For now, this can just be the cost of a ship/building per turn. Will need to be considered in more detail.)


Step 3: Determine how much the current production queue satisfies the demands.

If the current production queue satisfies the current demands, it shouldn't be changed at all. To determine if it does it will be mapped to a productionQueue type:

Code: Select all

type productionQueue:
  items = [] # list of integers, uses IDs of availableProductionItems: 1, 5, 23...
  numItems = 0 # integer
  demandsSatisfied = [] # list of demandEnum
  demandsValue = [] # list of integers

If the production queue meets demands better > 75% (arbitrary) and no PP are wasted, the AI shouldn't change anything (saves CPU; exit prod AI).


Step 4: Create all different kinds of production queues and look which one meets the current demands best.

The AI could much like a human player intelligently choose different items and put them on the prod queue. However, for now I would recommend a more CPU-consuming, but complete algorithm; I'd use a brute-force algorithm to create all conceivable combinations of productionItems. (Stop point for adding items would be that all PP have been used up.) As a result we'd have a couple of prodQueues with all possible combinations of prodItems.
Suggestion for a non-brute force algorithm by m_k see below.

Then the AI would have to determine if and which of these queues satisfies the empires demands best. So the satisfaction profiles of the queues would be compared to the demand profile.

At this point I'd assign build locations to the winning combination. (This could be done earlier to allow higher flexibility. Will need thought.)


Step 5: Change production queue

Even if a major change needs to be done to the production queue, old projects should be kept so as not to waste production. Projects should only be removed if a design becomes obsolete. Projects that are already being produced do not need to be added again.

1) Move down items of production queue that are not on the new queue (only postpone)
2) Remove items from the new prod queue that are part of the old queue (don't build them twice)
3) Add items that remain on the new queue at the top of the production queue (important projects)
4) Remove items from the production queue that have become obsolete (cleanup)


Suggestions?

[Edit: orbitals removed; components up for review marked blue]

[Geoff the Medio]

ShipDesign, BuildingType and OrbitalType...

Orbitals are going away. You'll only need to worry about ShipDesigns and BuildingTypes for v0.4.

...will need to know:
- about the purpose of a ship (colonisation, exploration, war, etc); should derive this from the ship design name (if it is impossible, from the design)

Presumably the AI will design its own ships, so it can keep track of what the design was for when doing the designing. If copying a design the AI didn't make, which should be possible in some cases, you'll probably have to look at the list of PartType and HullType in the design, which means that the parts individually will have to be understood by the AI, by name. Looking at ShipDesign name isn't likely to be useful, as they can be named anything, and should tend to be named something interesting and human-readable, not something easily parsed by an AI script.

- as well as the purpose of buildings (do they promote resources, which type?, defense, etc); should be able to read the buildings effects or derive this from a list

Looking at the effects is in general not going to be easy... Conditions can be rather complicated, and inferring strategic meaning from them is probably not feasible. You'll have to have a lookup table for BuildingType by name, similar to one for parts and hulls, with custom AI knowledge about them.

- the function of orbitals / recognize shipyards from their name/design

Again, no orbitals.

The AI could much like a human player intelligently choose different items and put them on the prod queue. However, for now I would recommend a more CPU-consuming, but complete algorithm; I'd use a brute-force algorithm to create all conceivable combinations of productionItems. (Stop point for adding items would be that all PP have been used up.) As a result we'd have a couple of prodQueues with all possible combinations of prodItems.

More like a couple billion of prodQueues, if there are more than ten or so potential buildings or ships, and about twenty potential build locations, and order matters... I don't think brute forcing all possible queues is feasible.

Edit: Also, any research or production AI is unfortunately going to be a victim of the relatively early and unbalanced state of game content such as techs, buildings, ship parts and hulls, etc. Much of this stuff will change significantly before we even start balancing things. For now, you may need to just focus on getting a framework for production / research / ship design AI working, with easily modified "knowledge" data files the AI uses to understand the game content.

[The Silent One]

Orbitals are going away. You'll only need to worry about ShipDesigns and BuildingTypes for v0.4.

Good to know.

Presumably the AI will design its own ships, so it can keep track of what the design was for when doing the designing. If copying a design the AI didn't make, which should be possible in some cases, you'll probably have to look at the list of PartType and HullType in the design, which means that the parts individually will have to be understood by the AI, by name. Looking at ShipDesign name isn't likely to be useful, as they can be named anything, and should tend to be named something interesting and human-readable, not something easily parsed by an AI script.

Sure. There could easily be a dictionary that stores ship design names and the designs purpose, e.g. designNameToShipFunction["Mark I"] == battleship.

Looking at the effects is in general not going to be easy... Conditions can be rather complicated, and inferring strategic meaning from them is probably not feasible. You'll have to have a lookup table for BuildingType by name, similar to one for parts and hulls, with custom AI knowledge about them.

I thought we might need some help files like that; what I don't like about this is that it'll require maintenance whenever a building/part/hull is changed/introduced, but it's probably still easier than writing a tremendous effects parser for the AI.

More like a couple billion of prodQueues, if there are more than ten or so potential buildings or ships, and about twenty potential build locations, and order matters... I don't think brute forcing all possible queues is feasible.

The building location is currently not being taken into consideration during the prodQueues creation (building locations are just determined for the winning prodQueue). Do you happen to have a suggestion for a smart algorithm that avoids brute-forcing? Anyway, I'll think about this and try to come up with something less CPU-intensive.

[...] research or production AI is unfortunately going to be a victim of the relatively early and unbalanced state of game content such as techs, buildings, ship parts and hulls, etc. Much of this stuff will change significantly before we even start balancing things.

You're definately right. The priority is to get the framework set up, secondly to teach the AI to build ships (I'll write a simple check if a design is a battleship, scout or colony ship), and only as balancing is progressing to write the support files for buildings, hulls and parts we were discussing above.

Any comments concerning the demand system?

[m_k]

Step 4: Create all different kinds of production queues and look which one meets the current demands best.

The AI could much like a human player intelligently choose different items and put them on the prod queue. However, for now I would recommend a more CPU-consuming, but complete algorithm; I'd use a brute-force algorithm to create all conceivable combinations of productionItems. (Stop point for adding items would be that all PP have been used up.) As a result we'd have a couple of prodQueues with all possible combinations of prodItems.

Like Geoff said, brute force could take hours on this. I would suggest some sort of greedy algorithm in nearly linear time for creating the queue, something in the line of: (numbering doesn't resemble yours)
1.Calculate demands like you said in form of a list of (positive) numbers and calculate the sum of all demands sumDemands (or norm the needs so that their sum equals 1)
2.For each item A already in the building queue reduce every demand i by: A.demandsValue/A.sumDemandsValue * A.productionPointsUsed/productionPointsAvailable * sumDemands
3.1.Find the greatest demand and add the production item satisfying this demand the most and add it to the queue.
3.2.Reduce the demands as in the step above.
3.3.Repeat step 3 until all production points are used up.
4.Save the leftover demands and add them to the new demands in the first step next turn.

Using this system the production points will be devided approximately in the same way as the demands are. The leftover demands should sum up to zero, so they will never dominate the new demands calculated while still accumilating so that in the long time used PP are exactly proportional to the demands.
Of course how much an item satisfies demands can't be static, so for example constructions taking longer time when there is nothing to be finished in the near future or using really unoptimal PP (like 5 PP being available for a 30PP per turn project) will have to have their "demand-satisfyability" reduced.
I'd postpone postponing to a later stage, maybe it is possible to treat the continuation of production items like new items but give them a bonus in step 3.1 according to PP already spent.

I believe that such a system could also be used for the research AI, and I hope that my rambling was intelligible for you.

[The Silent One]

This is an interesting approach and so far I don't see why this shouldn't work. I'm currently rather busy and I also need to finish some other AI aspects, but I hope to be able to get to this on the next weekend or shortly after.
Are you interested to take an attempt at the research AI? Or to do some initial thinking on a ship design AI?
Anyway, thanks for your input!

[m_k]

Are you interested to take an attempt at the research AI? Or to do some initial thinking on a ship design AI?

Both sound interesting and I can already see some smaller problems coming up with both of them. I think I'll try to think up something regarding both of them and do some initial testing and then post my results.

[OndrejR]

-initial production AI - ship designs which can attack and colonize are added to production queue if is empty

needs commit

[Geoff the Medio]

committed

[OndrejR]

In patch I posted there is also file PlanetUtils.AI, which wasn't committed. Here is patch with only this file.

[Geoff the Medio]

I forgot to add the file to SVN tracking before committing. New patch not really necessary.