AI production queue coding/planning

Programmers discuss here anything related to FreeOrion programming. Primarily for the developers to discuss.

Moderator: Committer

Message
Author
User avatar
Dilvish
AI Lead and Programmer Emeritus
Posts: 4768
Joined: Sat Sep 22, 2012 6:25 pm

AI production queue coding/planning

#1 Post by Dilvish »

The topic of reorganizing ProductionAI.py has come up a couple times in the last few weeks. A primary focus has been regarding refactoring to reduce code redundancy and improve readability, but there is other work this code needs that we should keep in mind (and hopefully also make progress on). Since we now appear to have three (woot!) people contributing to the AI and all interested in this aspect, I thought it would make sense to start a discussion thread dedicated to this topic. In particular, I wanted to talk about priority handling, so we might be able to refine some plans for better handling. They wouldn't necessarily have to be implemented as part of any refactoring, but I think this should be kept in mind so it can hopefully be readily supported.

Current recap: Right now the AI handles production priorities in a couple different ways. The handling for buildings is the crudest, where simply they are dealt with first, in rough order of priority, and then queued if there is available PP and possibly moved to the front of the queue. Then ships are handled so long as there is available PP in their Resource Group. Ship types are dealt with in a stochastic fashion based on relative priority in a way intended to accomplish a reasonable blend. In some cases they may get moved to or near the top of the queue. There is also separately (in ColonisationAI and probably InvasionAI) some handling of troopbases (troop ships with a colony base hull), outpost bases and colony bases.

I would like to support a more nuanced handling of priorities and placement within the queue. What comes to mind for me is that rather than having the different bits of item-specific code be directly placing their items in the queue, we would instead first create a planning structure recording specific items at specific build locations with baseline priorities. We'd also have, or recreate, the same info for all the items currently in the queue. They we'd go through and make adjustments to the baseline priorities, and those adjusted priorities would be used to order the items within the queue (and select new items for placement). Adjustments could be based on many things. Things partly completed need some level of priority (in general). If multiples of a thing are being queued, the additional ones could probably take a somewhat decreasing priority. Anyway, I only have general ideas at the moment for just what adjustments would be made, but even with minimal adjustment I think this could allow for a much batter management then the current approach which is much closer to a simple add_at_front/add_at_back choice. So let's have a discussion about this and other alternatives. If we went with this approach it wouldn't have to change the refactoring very much, it's mostly just that the individual routines would be adding to this planning structure rather than simply adding directly to the production queue.

Also, fairly independent of the above is the need to have the AI handle the new colony buildings. A small bit of enabling adjustment was made for the revised exobot colony building, but I think that if we work out an overall handling the exobot building will essentially be just another colony building. It's probably best if (at least initially) the AI didn't build any more colony ships and just uses outposts and colony buildings. Changing the initial fleet to have an outpost ship instead of a colony ship is ok (perhaps even preferred once we get the handling in place), although I would still prefer to have some minimal level of support for a dual scheme handling both colony ships and colony buildings. At the very least the current handling between colony bases and colony ships could probably be adapted. I don't know that this aspect necessarily needs a lot of discussion, and if it does it should probably get a separate thread, but I thought I should at least make a note of it here.
If I provided any code, scripts or other content here, it's released under GPL 2.0 and CC-BY-SA 3.0

Morlic
AI Contributor
Posts: 296
Joined: Tue Feb 17, 2015 11:54 am

Re: AI production queue coding/planning

#2 Post by Morlic »

Giving each item a respective priority and ordering seems like a fair approach to me.

My long-term vision would be that the AI makes some kind of strategic call and says "I need a fleet of Strength X for that and also 3 Troop Pods", evaluates how important this is (i.e. how much do I gain for how much cost) and enqueues the corresponding items with a priority according to that.

If the strategic call needs to be cancelled (e.g. the planet is no longer invadable due to stealth), the priority for the particular items is set to zero. If there are equal items in the queue with less spentPP, the priority will be handed down until the least finished part has priority zero. If the strategic value of the decision changes, the priority is updated as well.
So if the enemy fleet approaching us just got destroyed by some roaming super-monster, we can reduce the priority. The strategic value will automatically change each turn as we will make progress in the queue. When PPs are spent, the cost for the decision is reduced and thus we will end up with a higher priority (thus taking into account the problem with almost finished items should be finished first). Losing 4 Troop ships means we need to build another 4. Which increases the cost and decreases the desire to do so right now.

A strategic call would also include stuff like "I just invaded a planet with good pilot species and want to build my shipyards there" or "I am totally overpowered by the enemy, I need military ships asap" and might include stuff like "Yeah, I might want to colonize that planet at some point but I need to research that Tech first so I do not need the ship to be finished prior to turn X" and "I just got the tech for Solar Orbital Generator, let's build this asap!".

Each turn, all required items for the calls are given the respective priority. Starting with the highest priority, we search the queue for existing items that match and have a lower priority than the call. We prefer the most finished ones. If we found one, we give that entry the respective priority and move on. Elsewise, we enqueue a new item with the priority.

Finally, there would be some baseline desire to build stuff for remaining PP.


So the framework would consist of a list of (Item,Priority)-pairs which then traslates into the queue. The baseline decisionmaking adds entries to that list. At some point in the future, the strategic decisions can also add entries to that list.
If I provided any code, scripts or other content here, it's released under GPL 2.0 and CC-BY-SA 3.0

User avatar
Dilvish
AI Lead and Programmer Emeritus
Posts: 4768
Joined: Sat Sep 22, 2012 6:25 pm

Re: AI production queue coding/planning

#3 Post by Dilvish »

As we seem to have wrapped up at least the major initial push on reworking AI ShipDesign, I thought I'd give this thread a bump. I've started working on some code for prioritizing items on the production queue & perhaps I should go ahead and push that branch to my repo for discussion/collaboration, though what I have so far is not really all that much. It might also be best for this to follow some improved planet evaluation work, so that these priorities could be tied more closely to actual projected value rather than being based on much more generic average expected values.
If I provided any code, scripts or other content here, it's released under GPL 2.0 and CC-BY-SA 3.0

User avatar
Cjkjvfnby
AI Contributor
Posts: 539
Joined: Tue Jun 24, 2014 9:55 pm

Re: AI production queue coding/planning

#4 Post by Cjkjvfnby »

Dilvish wrote:perhaps I should go ahead and push that branch to my repo for discussion/collaboration
Why not :)
If I provided any code, scripts or other content here, it's released under GPL 2.0 and CC-BY-SA 3.0

User avatar
Dilvish
AI Lead and Programmer Emeritus
Posts: 4768
Joined: Sat Sep 22, 2012 6:25 pm

Re: AI production queue coding/planning

#5 Post by Dilvish »

ok, well I've opened up a PR with the initial work I had done, although I want to think through the broader framework some more before deciding if this initial approach is one I want to continue. Morlic, please be sure to note the issue I raise towards the bottom regarding ship designs.

Regarding the broader priority framework-- I want to explore changing nearly everything over to where essentially all decision making (as much as possible, mission assessment as well as production queue decisions) is driven by a kind of risk adjusted Net Present Value assessment. The underlying source of all raw value would be from the ownership of planets; at least currently I'm not seeing any reason to have ships be a raw source of value (though certainly if we ever do implement ships as a ResourceCenter then that would change). First planets would be valued, then various potential missions would be valued, and then building construction would be valued (probably in the context of its ability to change planet values) and ship construction would be valued in the context of the missions they would facilitate.

Planet Evaluation
I envision doing this valuation for every single planet visible to the AI (at least within some potentially-suppliable region) rather than dividing planets up and evaluating subsets of them at various times. The first pass would be for a base value of the planet by itself, pretty much the current evaluation. Once all planets have had their base value calculated, then a pass of assessing defense contributions-- how does owning this planet change local risk dynamics (adds defenses in-system to support other planets or to support a blockade), and then a pass of assessing of supply contribution-- what other planets would be newly brought within supply by owning this planet.

A sort of npv calculation is already currently done in the ColonisationAI for evaluating planets; most of this would not necessarily need adjustment. Right now though it works with a fixed discount rate applicable to all planets, and I want provide more flexibility for a planet-specific discount rate. The discount rate for the primary evaluation of a planet would be based on a risk assessment of the location of the planet, considering enemy threat versus our current military fleet forces in the vicinity. A key change that I am contemplating is that we would not simply generate a value for a planet/species combo-- instead we would probably generate a kind of object or functor which would take a discount rate as a parameter and then return a value for the planet. \

Military Mission Prioritization
Outpost, Colony and Invasion missions are already based on planet values and I don't see them needing to change much (at least in relation to this framework). Military missions are currently prioritized rather roughly, based on the (planet) status in the system under consideration (is the AI Capital there, or a colony, or an outpost/colony target, or an invasion target, or just part of our supply region). I am thinking of changing this to first generate a set of potential missions similarly to how actual missions are generated now, but it would be a fuller set of potential missions, possibly with a mechanism to specify some as alternates to each other. The 'valuation' of the mission would vary somewhat by type -- defense missions would largely be valued by assessing how they change the regional risk profile and what the resulting change in discount rates does to values of self-owned planets in the region. Missions to secure systems for invasions, outposts, etc., would be based on the subject planet value with some additional combat risk adjustment.

Ship Construction
The various potential ship construction projects could be derived from the values of potential missions that were left currently unassigned due to lack of ships. Exploration would probably need a somewhat different approach.

Building ConstructionFor buildings that contribute to resource production (PP or RP) in some way we could come up with an npv assessment of what they would contribute. There are a few in odd categories (Scanners, etc) that don't have a clear connection to resource production but we could come up with some kind of calculation. For ship construction facilities, right now the AI largely builds them at suitable locations (or at least a subset thereof) whenever it can, without a way to determine a priority. I'd like instead to leverage info on potential ship designs to help determine prioritization for such construction (how much more valuable would the ships be that it would allow to be created). We would still (for now at least) need to hard-code requirements (like being built in an asteroid belt, etc), but at least the prioritization could be more fluid.

Regarding ship designs-- right now our ShipDesign code is entirely constrained to dealing with parts and hulls that the AI can currently build (and has facilities for). I'd like to eventually be able to do a more prospective evaluation of designs, and use that resulting information to help prioritize construction of shipyard type buildings, and to help prioritize ship related research.
to eventually have a way to assess potential ship designs that the AI is currently lacking technology
If I provided any code, scripts or other content here, it's released under GPL 2.0 and CC-BY-SA 3.0

Morlic
AI Contributor
Posts: 296
Joined: Tue Feb 17, 2015 11:54 am

Re: AI production queue coding/planning

#6 Post by Morlic »

Dilvish wrote: Regarding the broader priority framework-- I want to explore changing nearly everything over to where essentially all decision making (as much as possible, mission assessment as well as production queue decisions) is driven by a kind of risk adjusted Net Present Value assessment. The underlying source of all raw value would be from the ownership of planets; at least currently I'm not seeing any reason to have ships be a raw source of value (though certainly if we ever do implement ships as a ResourceCenter then that would change). First planets would be valued, then various potential missions would be valued, and then building construction would be valued (probably in the context of its ability to change planet values) and ship construction would be valued in the context of the missions they would facilitate.
While I think such a strategy would be beneficial in various aspects of the AI I think the handling of military fleets requires a more refined approach. As there is no saving up to instantly spam the required amount of warships, it is absolutely necessary to constantly build new warships to deal with future threats eventhough it may be impossible to state a real value for the ships (as this depends heavily on the unknown strength of the enemy fleets and the enemy behaviour).

I think the military fleet strength should be a factor considered besides the planet count. Many planets are worthless if we have no fleet and a strong fleet needs to be traded for planets.

In my opinion, the value function should take the form of

Code: Select all

value = f( planetsValue * (const+militaryFleetRating)^p)
Where the parameter p would tune the relative importance between the two factors we want to consider and the constant provides the early game expansion boost. This form of function could potentially ensure that we have enough military strength (which could also factor in how easy to defend our empire actually is and not only a raw fleet strength).
Planet Evaluation
I envision doing this valuation for every single planet visible to the AI (at least within some potentially-suppliable region) rather than dividing planets up and evaluating subsets of them at various times. The first pass would be for a base value of the planet by itself, pretty much the current evaluation. Once all planets have had their base value calculated, then a pass of assessing defense contributions-- how does owning this planet change local risk dynamics (adds defenses in-system to support other planets or to support a blockade), and then a pass of assessing of supply contribution-- what other planets would be newly brought within supply by owning this planet.

A sort of npv calculation is already currently done in the ColonisationAI for evaluating planets; most of this would not necessarily need adjustment. Right now though it works with a fixed discount rate applicable to all planets, and I want provide more flexibility for a planet-specific discount rate. The discount rate for the primary evaluation of a planet would be based on a risk assessment of the location of the planet, considering enemy threat versus our current military fleet forces in the vicinity. A key change that I am contemplating is that we would not simply generate a value for a planet/species combo-- instead we would probably generate a kind of object or functor which would take a discount rate as a parameter and then return a value for the planet. \
[/quote]

I think an important point you forgot is the vulnerability of the planet. If the planet is at an exposed position, it requires additional defensive resources or can't even be held at all. Unless we are in a strategic advantage already, we should prefer even slightly worse but safe planets inside the empire boarders or ones that reduce the number of nodes to defend/cover or only increase by the least unless there is no enemy around in which case we probably want to gain more breathing and breeding room.

This is different from the point you mentioned below about planet assessment as this would take into account a more global strategic worth instead of only local and current threats. Otherwise these sounds like good ideas to me.

Ship Construction
The various potential ship construction projects could be derived from the values of potential missions that were left currently unassigned due to lack of ships. Exploration would probably need a somewhat different approach.
Add in the mentioned approach towards military fleet strength and I agree.
Building ConstructionFor buildings that contribute to resource production (PP or RP) in some way we could come up with an npv assessment of what they would contribute. There are a few in odd categories (Scanners, etc) that don't have a clear connection to resource production but we could come up with some kind of calculation. For ship construction facilities, right now the AI largely builds them at suitable locations (or at least a subset thereof) whenever it can, without a way to determine a priority. I'd like instead to leverage info on potential ship designs to help determine prioritization for such construction (how much more valuable would the ships be that it would allow to be created). We would still (for now at least) need to hard-code requirements (like being built in an asteroid belt, etc), but at least the prioritization could be more fluid.
If we use visibility around the planet as a safety factor, scanners would automatically increase the planet's value if needed, I suppose. This could also be a good baseline for building additional scouts to scout relevant boarders.
Regarding ship designs-- right now our ShipDesign code is entirely constrained to dealing with parts and hulls that the AI can currently build (and has facilities for). I'd like to eventually be able to do a more prospective evaluation of designs, and use that resulting information to help prioritize construction of shipyard type buildings, and to help prioritize ship related research.
to eventually have a way to assess potential ship designs that the AI is currently lacking technology
As far as the design framework is concerned, this should be trivial. Basically, we can add two parameters to optimize design: One list of hulls and one list of parts that the AI should include in their designs eventhough not researched. Default is an empty list for production planning. Then the list gets merged with the available hulls/parts and I think the rest is fine as is.
Some more details/nuances can surely be added based on our final requirements but that shouldn't be too hard.

I think the bigger issue is how to read out the information of which building/tech unlocks which hull/ship part. Not hardcoding this stuff would be preferable.
If I provided any code, scripts or other content here, it's released under GPL 2.0 and CC-BY-SA 3.0

User avatar
Dilvish
AI Lead and Programmer Emeritus
Posts: 4768
Joined: Sat Sep 22, 2012 6:25 pm

Re: AI production queue coding/planning

#7 Post by Dilvish »

It sounds like we are in agreement about what is a generally good direction to head, though I'm not quite following on some of the specifics you indicate you think should be different.
Morlic wrote:I think the handling of military fleets requires a more refined approach. As there is no saving up to instantly spam the required amount of warships, it is absolutely necessary to constantly build new warships to deal with future threats eventhough it may be impossible to state a real value for the ships (as this depends heavily on the unknown strength of the enemy fleets and the enemy behaviour).
It sounds to me like you are talking about a refinement to the risk assessment rather than to the overall approach, and further that you seem to be overlooking some newish aspects of risk assessment that includes assessing enemy supply lines. So already some enemy threat is assigned even if no enemy warships have ever been visible. It seems to me that it already addresses the basic issue you raise about prospective threat, and of course could be further refined. (I also did already have some code that established some baseline threat even when there was no enemy signs whatsoever, but I found that didn't seem to work well and for quite a while now that contribution has been set to zero). Perhaps I am misunderstanding you though; if you continue to think so then please try clearifying.
I think the military fleet strength should be a factor considered besides the planet count. Many planets are worthless if we have no fleet and a strong fleet needs to be traded for planets.
I'm not sure what you are referring to there by planet count, but as for fleet strength I think that was already part of my proposal, in a couple different ways, both in regards to basic valuation of the ownership of a planet and with regards to combat risk when attempting to secure unowned planets or capture owned planets:
Dilvish wrote:The discount rate for the primary evaluation of a planet would be based on a risk assessment of the location of the planet, considering enemy threat versus our current military fleet forces in the vicinity.... Missions to secure systems for invasions, outposts, etc., would be based on the subject planet value with some additional combat risk adjustment.
Although you did propose a very specific formula,

Code: Select all

value = f( planetsValue * (const+militaryFleetRating)^p)
it's not really clear to me how you propose it to fit into the framework I proposed or how you propose to adjust the framework to use your formula. Where is this calculated value meant to fit in? It seems meant to be a risk-adjusted derivation from an earlier-pass planetsValue; are you suggesting that this first tier "planetsValue" not be derived involving a risk-adjusted discount rate, and instead assess risk purely by the strength of our fleet presence? Whether as an augmentation of the earlier level of risk assessment, or as a full replacement for it, could you explain more about how/why you think this would be a more effective way to value the planet itself (as opposed to assessing various missions)? Or was it meant as a way to value the missions? I fully agree that evaluation of missions should include an assessment of our fleet presence; for military missions I expected that it would be captured during the step of evaluating how a prospective military mission would alter the local risk profile. Outpost/colonization missions also currently have a small bit of assessment of fleets and risk, which I'm looking at changing a bit even prior to this framework in order to minimize situations where an outposting mission might be launched prior to military forces being available to secure the destination. Is that where you anticipate using this calculated value, when assessing sending out an outpost/colonization mission?
Morlic wrote:I think an important point you forgot is the vulnerability of the planet. If the planet is at an exposed position,
No, I certainly didn't overlook that--
Dilvish wrote:The discount rate for the primary evaluation of a planet would be based on a risk assessment of the location of the planet, considering enemy threat versus our current military fleet forces in the vicinity.
To clarify, enemy threat assessments already include issues beyond mere enemy fleet presence, specifically they now include assessment of enemy supply lines. I'm sure the risk assessment could be further augmented in various ways (such as topology of starlane connections for example), and a more involved assessment of regional threat. If you think I am misunderstanding your point, then again, please clarify.
It requires additional defensive resources or can't even be held at all. Unless we are in a strategic advantage already, we should prefer even slightly worse but safe planets inside the empire boarders or ones that reduce the number of nodes to defend/cover or only increase by the least unless there is no enemy around in which case we probably want to gain more breathing and breeding room. This is different from the point you mentioned below about planet assessment as this would take into account a more global strategic worth instead of only local and current threats.
Perhaps the key thing here again is that it seems to me you misunderstand the risk assessments already done, which I was expecting to keep doing-- as mentioned above they are not limited to "only local and current threats", there are multiple types (well, two types at least) of regional threat assessment done already. So I'm not really seeing how this is any different.
Building Construction
If we use visibility around the planet as a safety factor, scanners would automatically increase the planet's value if needed, I suppose. This could also be a good baseline for building additional scouts to scout relevant boarders.
Yes, those both sound like good ideas.
I'd like to eventually be able to do a more prospective evaluation of designs, and use that resulting information to help prioritize construction of shipyard type buildings, and to help prioritize ship related research.
As far as the design framework is concerned, this should be trivial. Basically, we can add two parameters to optimize design: One list of hulls and one list of parts that the AI should include in their designs eventhough not researched. Default is an empty list for production planning. Then the list gets merged with the available hulls/parts and I think the rest is fine as is.
Some more details/nuances can surely be added based on our final requirements but that shouldn't be too hard.
I'm glad the basic idea makes sense to you. One aspect that you might have not bothered commenting on since it seems also fairly trivial is that beyond sometimes passing in a list of parts that haven't been researched, I believe we would need a flag to bypass the whole _can_build() part/hull filtering process.
I think the bigger issue is how to read out the information of which building/tech unlocks which hull/ship part. Not hardcoding this stuff would be preferable.
Knowing what gets unlocked by techs is easy; there is already some reporting done of that by the ResearchAI. Dynamically determining what buildings or other location requirements a part or hull may need is a much more messy issue-- adding enough Condition parsing to the AI and AI Interface to mere determining what buildings have to be present at the subject planet would be reasonably feasible, but there are sometimes other location requirements as well whose absence might not prohibit the building but would make it far less valuable (or even effectively useless). I am sure we'll want to start off with simply hardcoding such content details, and later can look at adding some more dynamic assessment of the content.
If I provided any code, scripts or other content here, it's released under GPL 2.0 and CC-BY-SA 3.0

User avatar
MatGB
Creative Contributor
Posts: 3310
Joined: Fri Jun 28, 2013 11:45 pm

Re: AI production queue coding/planning

#8 Post by MatGB »

Some observations on priorities that might help this one. In my current game I'm at war with a relatively successful AI, that has a reasonable number of growth techs. I've just captured the capital (it's Gysache). 5 planets in the system, including a large toxic, an inferno and a terran. Elsewhere, the AI has colonised a fair few small/medium toxic worlds with Gysache. For me when I'm playing, the highest priority is to fill up as best as possible systems I have a base in, partially as it's cheaper and quicker, partially because 5 planets with defences is a lot harder to break and take than one. That toxic world in the homeworld system should be colonised VERY early, not immediately, obviously, but as soon as SubHab is researched.

I suspect, but can't know and I've reloaded a few times so the log's overwritten, that the AI looked at the planets there when they became visible, they weren't useful then, so were ignored, and not rechecked later.

That doesn't explain the second issue, different AI, remnants of a Trith empire that's away from the main core, I'm just exploring it (using scouts I built at the Trith homeworld). They have two systems, the new capital is Derthrean with asteroids and a gas giant. The neighbouring system is Sslith. Their homeworld is a tiny planet. In the same system is a Huge tundra world. The Sslith have multiple shipyards including an incubator, clear evidence the AI has held this world for some time. Despite neither world being set to industry, a new Industrial Centre has been built on the Derthrean homeworld. But the huge good environment world for those Sslith is untouched.

Planning priorities should say "industrial centre pointless right now, need more warships/colonies" and build them as a high priority, and "huge world in the home system of a native that can use it" should scream out colonise me now immediately on conquest.
Mat Bowles

Any code or patches in anything posted here is released under the CC and GPL licences in use for the FO project.

User avatar
Dilvish
AI Lead and Programmer Emeritus
Posts: 4768
Joined: Sat Sep 22, 2012 6:25 pm

Re: AI production queue coding/planning

#9 Post by Dilvish »

MatGB wrote:For me when I'm playing, the highest priority is to fill up as best as possible systems I have a base in, partially as it's cheaper and quicker, partially because 5 planets with defences is a lot harder to break and take than one.
Yes, the AI already values a colony 1.5 times as much if it already owns some other planet in the system (and in most cases that should indirectly carry over to evaluating an outpost as well). I'll take a look at increasing that by a fixed amount as well and also having it apply more directly to outposts.
I suspect, but can't know and I've reloaded a few times so the log's overwritten, that the AI looked at the planets there when they became visible, they weren't useful then, so were ignored, and not rechecked later.
No, it reevaluates them every turn; there must have been something else going on there.
That doesn't explain the second issue, different AI, remnants of a Trith empire ... The neighbouring system is Sslith. Their homeworld is a tiny planet. In the same system is a Huge tundra world. The Sslith have multiple shipyards including an incubator, clear evidence the AI has held this world for some time. Despite neither world being set to industry, a new Industrial Centre has been built on the Derthrean homeworld. But the huge good environment world for those Sslith is untouched.
As we've discussed before, when an empire's capital has been captured it scrambles to rebuild a number of buildings without good assessment of priorities for them. That's something that should automatically be dealt with much better by this new framework we're discussing; if it's still a problem afterwards I'll try to look at it a bit more then. In this case it sounds to me like the colony base for that huge planet is probably on their build queue, but they have very low production output and other projects (like the Industrial Center) kept getting put before it. If you still have a savegame and could check for the presence of that an outpost base on their buildqueue at that tiny sslith planet that would be helpful. If it's not on their queue at all I might try to take a look into it, but if it's just a construction prioritization problem then I'll expect it to get dealt with by this new framework. This scenario also raises the issue of Focus determination-- I've noticed a number of other situatons we well there the AI had taken research focus where they pretty clearly should have had Industry focus, but revisiting that will have to be put off for later.
If I provided any code, scripts or other content here, it's released under GPL 2.0 and CC-BY-SA 3.0

Morlic
AI Contributor
Posts: 296
Joined: Tue Feb 17, 2015 11:54 am

Re: AI production queue coding/planning

#10 Post by Morlic »

As you never explicitly stated your approach, we may have some different context. So let's clear that up. So far I considered an algorithm along these lines:
1. Calculate a rating for the current situation.
For each mission:
2. Project the rating if the mission succeeds (remove destroyed ships from value calculation but add captured planets -- or update threat assessment after military movement).
3. Multiply the projected rating by some risk factor (e.g. how likely is it that our colonization ship is destroyed before it reaches destination?)
4. NPV of that mission is rating_after_mission - rating_before_mission normalized by some cost function (however that is defined in the given context)

Mission with best NPV is chosen. Repeat algorithm until all fleets/missions/PP/RP etc. are assigned (probably update the base rating after each call for the assumption that the previous mission succeeded).

So the rating of the situation before/after the mission would be given by the formula I suggested. Planet evaluation would proceed as envisioned by you. I want to add an additional rating for our fleet strength on a strategic level (comparing it to enemy techs and ship count etc. even if not in close contact with them yet). Both then combine to an overall rating of our empire situation.
So I guess in some way it could be considered as a single additional modifier to your approach using planet ratings but I think it is distinct enough to be called differently.

The idea is to let the threat assessment still affect the planet value. In this way, the distribution of our military resources is easily handled and cases where we are drastically behind in military and need to build ships as soon as possible are caught as well.

However, I consider military fleet strength to be another resource that should be considered besides pure planet value. How do you evaluate trading 10 military ships for 2 planets? In your suggestion so far, there is no inherent value of military ships if they are not currently needed to defend against threats or for imminent invasion missions. I do not believe this reflects the ingame reality. Building up a military fleet takes time and thus the game is heavily momentum based in nature. If the enemy fleet is stronger than ours, we will lose planets. Even if we start building right away, it will take time to match their strength and the enemy may reinforce its fleets as well. So we will lose planets until we caught up.
So on the defensive side, having a baseline fleet reduces the time the enemy can roam around in our empire and wreak havoc.On the offensive side, an initially larger fleet will keep the momentum on our side to the same effect.
Falling behind in military strength thus is a fatal mistake that must be avoided at all costs. The proposed formula adds a mechanism that balances out expansion versus a usable military fleet. It provides a mean to figure out when to trade fleet for planets. When to expand and when to actually build some more military instead of taking that planet which gives us only 1% more population.

This is a very recurrent theme in games in general: How do you value momentum versus long-term effects. With the given formula it is easy to adjust this behaviour for the AI tuning only two parameters.
Note that tuning our preference for military strength should also imply tuning of invasion priority as the risk/cost reduces significantly with military superiority so this is potentially a really powerful switch allowing to implement different AI personalities and also some relatively simple entry point for future adaptive AI / machine learning.




As far as my other point is concerned: Basically it comes down to me considering the current threat assessment to be mostly done only on a tactical scale neglecting important strategic elements such as shape of the empire (concave/convex, circular/elliptic), starlane topography as you mentioned (number of nodes we have to defend) and so on. Nothing too much oriented towards the suggested framework in particular but more or less a general thought for future implementation.


@Shipdesign:
No need to override _can_build(). That function is only called at the beginning of the turn to find the buildable parts/hulls per planet. After that all buildable hulls/parts are cached and no further checks are implemented (well probably somewhere in ProductionAI but that does not matter at all for the function call in question).
If I provided any code, scripts or other content here, it's released under GPL 2.0 and CC-BY-SA 3.0

User avatar
Dilvish
AI Lead and Programmer Emeritus
Posts: 4768
Joined: Sat Sep 22, 2012 6:25 pm

Re: AI production queue coding/planning

#11 Post by Dilvish »

As you never explicitly stated your approach, we may have some different context. So let's clear that up. So far I considered an algorithm along these lines
It seems our context for discussion is close enough. Although not in a numbered list, I thought I was being fairly explicit; at least you have managed to glean my intent pretty well; I don't have much to comment on your list of steps 1-4. Although the value name NPV implies it, I would like to be more explicit about the time valuation aspect-- we may not start out estimating and using the time expected to accomplish the mission, but I would like to move to that eventually. The planet valuations are an NPV estimate for owning the planet now, and for two otherwise equally rated missions (or construction projects, much of this would apply to them as well), if one could be expected to be completed in half the time of the other, the faster one would be more valuable. It could be that you were expecting that to be covered by the cost function you mention; your expectations for that weren't totally clear to me.
(probably update the base rating after each call for the assumption that the previous mission succeeded).
Some way to assess other pending missions will be good; the exact manner might need to be more complex, but all that could be explored as a later stage.

Code: Select all

value = f( planetsValue * (const+militaryFleetRating)^p)
So the rating of the situation before/after the mission would be given by the formula I suggested. Planet evaluation would proceed as envisioned by you. I want to add an additional rating for our fleet strength on a strategic level (comparing it to enemy techs and ship count etc. even if not in close contact with them yet). Both then combine to an overall rating of our empire situation.
I can see how an overall strategic level rating of our overall fleet relative to estimates for enemies would contribute to an overall rating for our empire situation, but it's not clear to me how that relates to your formula and how using this formula to value missions would contribute to the assessment of those missions. If the fleet rating in your formula is some empire wide strategic rating, then won't it be the same for all potential missions? Even if it is just based on the number & details of ships expected to be used for this mission, then it seems like it will favor missions that have higher fleet requirements over ones that have lower requirements. If it is instead based on the fleets already at the destination, then what does this really contribute beyond what is covered by the threat/risk adjusted NPV estimates for the target planets? Coming back to this again with reference to your later words about "the risk/cost reduces significantly with military superiority", I see another possibility -- that you mean it purely as a way to assess two different approaches to accomplishing the same mission, one with more military support than the other. But this formula will absolutely always favor more military support, the more the better, so if that is what you meant then how would it actually help allocate limited military resources?
The idea is to let the threat assessment still affect the planet value. In this way, the distribution of our military resources is easily handled and cases where we are drastically behind in military and need to build ships as soon as possible are caught as well.
I'm not seeing how this particular formula makes distribution of military resources any easier, nor really how it would contribute to the situation of catching up when we're behind on fleet strength-- I think any empire level assessments like that are best dealt with directly in the military ship priority assessment, not by adding some bias to all mission ratings.
Morlic wrote:In your suggestion so far, there is no inherent value of military ships if they are not currently needed to defend against threats or for imminent invasion missions.
We seem to be having some recurring significant communication problem here. It seems to me like you are not understanding me, but I recognize that it likely seems to you that I am not understanding you. I will do my best to clarify myself and where the point of misunderstanding appears to me to be, and you please do likewise. I am hopeful that the actual scope of disagreement is quite small, but at the very least a bit of work is needed to get some clarity.
I 'm having trouble getting meaning from that statement other than a little sliver that seems best focused on very specifically. As I had already tried to clarify in my previous post (and will try a little more now), 'threat' no longer is used to denote only enemy forces and planets, I use it as the umbrella term for assessing where the presence of our military ships would have value--
Dilvish wrote:enemy threat assessments already include issues beyond mere enemy fleet presence, specifically they now include assessment of enemy supply lines. I'm sure the risk assessment could be further augmented in various ways (such as topology of starlane connections for example), and a more involved assessment of regional threat.
So I have a hard time reading your statement as other than "In your suggestion so far, there is no inherent value of military ships except where they have value." The only sliver of real meaning that I see to extract from this statement is to promote a bias in favor of military ship construction that is largely or entirely independent of the observed situation. To the extent that is your meaning, then let us please focus very clearly on that; to the extent this misses your meaning then I'll have to ask for more clarification.

In this post you also wrote a lot about the value of having military strength on hand prior to specific need for it, but that seems to me something we are in agreement about, and I didn't see what perceived misunderstanding on my part you were trying to address with that. I've already written about some aspects of my existing efforts to try to make an anticipatory assessment of military ship needs. Mostly I want that to be tied to observable aspects of the situation the AI finds itself in-- the strongest threats are actual ships, more tenuous is enemy supply capability. You may or may not have noticed that in various places the code also assesses the sparseness of the universe (empires with respect to systems) so that even if no enemies have been seen some element of risk can be assigned to the mere knowledge that they exist with some expected range of time/distance until first contact. Right now that gets incorporated into the priorities for outposts and colonies, which is close to the same thing as incorporating it into the military ship priority, but it could certainly go directly there as well. The military ship construction priority calculation also has an inherent bias in it which goes up over time, and I did not intend to suggest that would be done away with (though of course everything is subject to tuning and refinement).

So those are the ways that the AI currently assigns anticipatory value to military ship construction, and the ways I would envision further refining it-- most of it based on assessment of location/region needs, a small bit based on non-location specific risk assessment (which could also include assessment of enemy technology, etc.). As I had also mentioned, I previously experimented with adding a small threat bias to systems where the AI has some colony presence, but it didn't work out well and is currently effectively disabled.

You have now clarified that your primary intention for your proposed formula was regarding mission valuation, and then by extension, if I understand you correctly, it would contribute to a pro-military construction bias. Having the presence of military fleets be a direct and monotonically increasing contribution to mission value seems to me like it would have a result very very similar to the location-specific direct threat bias approach I had tried and found to not work well-- I just couldn't get the parameters tuned well to the point that it seemed to help without too often leaving ships just sitting around on a mission that was effectively doing nothing, well inside safe territory. It could be that either or both of those approaches might be adjustable to work well, but my experience makes me wary of it, and I don't see any reason to think that your flavor of it would be easier to adjust well than my former attempt. Perhaps we can largely bypass this point of not-yet-agreement, though-- it seems to me that the threat concept and risk-adjusted valuation framework are probably flexible enough to allow you to try working with a contribution that works out at least very similarly to what you propose or perhaps even identically (though as discussed below I'm starting to feel more fuzzy on just what you intend to use for the fleet rating in the formula). So my proposal would be that we plan for the threat assessment and/or risk adjustment stages to (try to) be flexible enough for you to experiment with the formula you propose. If it just won't fit into that framework then it could be an optional extra stage of value adjustment, sure, to make it easy for you to experiment with it to try getting the parameters tuned to a point where it is helpful to use in the regular code.
The proposed formula adds a mechanism that balances out expansion versus a usable military fleet. It provides a mean to figure out when to trade fleet for planets. When to expand and when to actually build some more military instead of taking that planet which gives us only 1% more population.
These decision points are already covered by the framework, as you yourself described it in the steps 1-4, particularly in light of the previous explanation I gave about assessing mission risk and before/after risk/threat sensitive npv calculations. I'm afraid I don't see how your formula contributes at all to the decision of whether or not it is a good use of resources to try capturing a planet-- can you explain that with any example, perhaps, or at least in more detail?
This is a very recurrent theme in games in general: How do you value momentum versus long-term effects. With the given formula it is easy to adjust this behaviour for the AI tuning only two parameters.
So, in your formula, you have a constant additive parameter and a power factor parameter. According to what I think are my two best estimates of your intention for the formula, increasing the power factor would make the AI either favor throwing more ships at a given mission, or else favor missions where there is already a preponderance of fleet strength. The former I don't really see as momentum though-- it just seems like aggression/risk-taking since it has nothing to do with where the next mission is. The latter is probably correlated to local momentum, but since it doesn't take nearby opposing fleets into account it seems like it is just simply a poor proxy for the risk-assessment for the mission. Either way I don't see how this contributes anything beyond the risk assessment that is already contemplated.
If I provided any code, scripts or other content here, it's released under GPL 2.0 and CC-BY-SA 3.0

Morlic
AI Contributor
Posts: 296
Joined: Tue Feb 17, 2015 11:54 am

Re: AI production queue coding/planning

#12 Post by Morlic »

Some of your follow-up questions are based on false assumptions you made when trying to understand my intentions, so I am not going to answer all of them but focus on what I consider to be the core and if you still have trouble understanding what I meant, let's focus on what I write here and follow up on that. Alternatively, restate your previous questions if you still think they are relevant and I did not adress them.

The fleet rating is supposed to be empire-wide and is indeed intended to assign a (mostly) situation-independent value for ships (both for new productions and existing ships).

Fleet missions would only be affected if during the process there would be built additional ships and/or ships are expected to be destroyed. In the latter regard it would act as an implicit cost-function (state the ships you expect to lose, exclude them from the fleet rating calculation and the overall rating of the mission is automatically adjusted). Note that while missions including to build military ships get the bonus from having another military ship available (and thus changing the fleet rating), the cost will increase accordingly so there is no net preference for military missions as long as the baseline desire is satisfied.

The second purpose is to provide that baseline for ships. Basically, any building order can be compared to "does this yield more overall value than simply building a military ship instead". The baseline is implicitly based on the overall state of the empire in other regards (i.e. the planetsValue).


I understand that the current threat evaluations has some factor based on "unknown" / baseline threats. However, I think it is mandatory to decouple the value of military ships from threat assessment at least partially. The threat assessment would primarily serve to distribute the available military ships and also detect a severe shortcut of ships for the current situation (say an enemy fleet we can not counter at the moment)

I want to outline the problem I see in the alternative case that you suggested:
Consider that we use the threat assessment system to define the baseline desire for military ships: We have some expectancy of threat based on universe settings (sparseness of the universe etc.). We want to minimize the local threat and thus build military ships. However, this requires the threat to be of such a magnitude that it is more desired than building alternative items, i.e. it has to be a large value. The problem is that in this case we are also very reluctant to move the ships away from their respective locations as the local threat then would increase significantly. Alternatively, a small threat value would allow us to use the ships in other missions freely but also means that we are very unlikely to build new military ships.

In consequence, we should decouple the threat assessment (where do we move the ships) from the baseline desire (how many ships do we want unless missions or threat demands for more) as it is implied by my function. This allows to give all border planets an inherent low threat based on the probability we will encounter an enemy in that direction to distribute our military forces correctly while keeping the military ships that are moved to the front due to this base level threat are free to be used for any other mission.

Eventhough I consider this to be fairly trivial and you probably realized it, let me mention some of the implications of my formula explicity. Assume the asymptotic case of a negligible constant and a small change of the rating due to a possible decision compared to its current value, i.e. it is enough to take into account only first order terms in terms of a taylor expansion.
For that case, the relative change of the rating (note that only the relative change is of any meaning in the algorithm) is given by

Code: Select all

relative_change_overall_rating = relative_change_planet_value + p * relative_change_fleet_rating
This implies that we will choose whatever option is most cost-efficient to increase the relative values of our planets or our rating of military fleet weighted by p. As the relative change obviously scales reciprocally with the current value, when maximizing the overall rating, the algorithm will balance planet value (which is a measure for expansion) and the fleet strength. I think this is a very natural and logical approach.



NB:
As far as the term "momentum" is concerned that I used in my last post: I should have mentioned I talk once more about the strategic side of it and not about local/tactical momentum. The latter is if we have local fleet superiority. What I am talking about is overall strength. Basically, local momentum is easy to overcome by sending a fleet there which is bigger. Assuming a 2-player setup for simplicity, it is possible for the stronger player to counter each attack with more ships and regain local momentum limited by the number of turns the ships need to reach the target.
Strategic momentum, however, is given by the current number of ships which can be distributed (and thus be used to generate/counter local momentum). It is related to momentum as the superiority persists until the enemy builds an even stronger fleet which takes time even with higher production.
If I provided any code, scripts or other content here, it's released under GPL 2.0 and CC-BY-SA 3.0

User avatar
Dilvish
AI Lead and Programmer Emeritus
Posts: 4768
Joined: Sat Sep 22, 2012 6:25 pm

Re: AI production queue coding/planning

#13 Post by Dilvish »

Thanks for taking the time to explain that more. Since you clearly feel very strongly that this would be a significant benefit to the AI, I'll drop my previous preference that we first explicitly try to simply accommodate the same interests purely through the underlying framework I proposed, and we can just plan on this as an optional extra stage which can be tweaked via AI configuration parameters (choosing an additive constant of 1 and a p of zero, for example, would make it a no-op). It does still seem to me that, from what I understand, these cited interests would already be met by the underlying framework, but we don't really need to resolve that now. I recognize that the underlying framework I have proposed, to which you would add this, is really more of a sketch rather than a clear specification, which hinders fully resolving questions like this at this time. It's easy enough to implement something that allows both avenues to be explored and then we can just see how things play out.

I will go ahead and make note of the areas I still have questions/doubts while they are on my mind. There is no compelling need for you to respond to these now, but when it comes time to write up the code and add comments and whatnot then perhaps you could keep these in mind then & hopefully address them some with the code comments.
Morlic wrote:The fleet rating is supposed to be empire-wide and is indeed intended to assign a (mostly) situation-independent value for ships (both for new productions and existing ships). Fleet missions would only be affected if during the process there would be built additional ships and/or ships are expected to be destroyed. In the latter regard it would act as an implicit cost-function (state the ships you expect to lose, exclude them from the fleet rating calculation and the overall rating of the mission is automatically adjusted). <snip> ... For that case, the relative change of the rating (note that only the relative change is of any meaning in the algorithm)
If the relative change in fleet strength expected to be cause by the subject mission is all that matters, then it is unclear to me why it should handled/obtained by manipulating an empire-wide fleet rating. It's also unclear to me how this would be different than the costs that are already accounted for in step 2 (and possibly 3).
Note that while missions including to build military ships get the bonus from having another military ship available (and thus changing the fleet rating), the cost will increase accordingly so there is no net preference for military missions as long as the baseline desire is satisfied.
I'm afraid I don't follow. What 'baseline desire' do you refer to here?
The second purpose is to provide that baseline for ships. Basically, any building order can be compared to "does this yield more overall value than simply building a military ship instead". The baseline is implicitly based on the overall state of the empire in other regards (i.e. the planetsValue).
Although this description of the valuation emphasizes the comparison to military ship construction, that seems to me like just another way of looking at the underlying framework, different in wording/emphasis but not in substance.

I understand that the current threat evaluations has some factor based on "unknown" / baseline threats. However, I think it is mandatory to decouple the value of military ships from threat assessment at least partially. The threat assessment would primarily serve to distribute the available military ships and also detect a severe shortcut of ships for the current situation (say an enemy fleet we can not counter at the moment)
It is your view that threat assessment can only detect "severe" shortages? It seems to me it can detect any assessed shortage, and as I will point out yet again, not just for a known enemy fleet but also for whatever potential fleet we choose to estimate they might have. I note it seems you also ignored my point about the existing priority factor which adds some bias in favor of building military ships. Right now it is purely a function of time, but would best be understood to represent an empire-wide threat contribution and could take other factors into account as we have discussed (enemy techs, etc.).
I want to outline the problem I see in the alternative case that you suggested: Consider that we use the threat assessment system to define the baseline desire for military ships: We have some expectancy of threat based on universe settings (sparseness of the universe etc.). We want to minimize the local threat and thus build military ships. However, this requires the threat to be of such a magnitude that it is more desired than building alternative items, i.e. it has to be a large value. The problem is that in this case we are also very reluctant to move the ships away from their respective locations as the local threat then would increase significantly.
Even currently, a portion of the threat assessment is at a regional basis, comparing regional threat to regional defense forces. Local threat which is mobile contributes to regional threat, but some factors (currently enemy supply) are considered to contribute to regional threat but not to local threat, and so create a demand for the general presence of defensive forces but allow a great deal of flexibility in the exact location of those forces. In the framework I proposed those forces would be distributed in a fashion to maximize our assessment of the risk-adjusted net present value of colonies. I don't see how adding your proposed formula leads to any better distribution (it's not really even clear to me just what changes to the distribution it would make, but perhaps I need to make the underlying framework more concrete before any such differences could really be determined/discussed).
If I provided any code, scripts or other content here, it's released under GPL 2.0 and CC-BY-SA 3.0

Morlic
AI Contributor
Posts: 296
Joined: Tue Feb 17, 2015 11:54 am

Re: AI production queue coding/planning

#14 Post by Morlic »

Dilvish wrote:Thanks for taking the time to explain that more. Since you clearly feel very strongly that this would be a significant benefit to the AI, I'll drop my previous preference that we first explicitly try to simply accommodate the same interests purely through the underlying framework I proposed, and we can just plan on this as an optional extra stage which can be tweaked via AI configuration parameters (choosing an additive constant of 1 and a p of zero, for example, would make it a no-op). It does still seem to me that, from what I understand, these cited interests would already be met by the underlying framework, but we don't really need to resolve that now. I recognize that the underlying framework I have proposed, to which you would add this, is really more of a sketch rather than a clear specification, which hinders fully resolving questions like this at this time. It's easy enough to implement something that allows both avenues to be explored and then we can just see how things play out.
I agree. We seem to be of the same mind about general points that need to be considered in the framework and only disagree on implementation issues. With some code and ingame-behaviour to base a discussion on, things will get clearer for both sides anyway.
If I provided any code, scripts or other content here, it's released under GPL 2.0 and CC-BY-SA 3.0

Morlic
AI Contributor
Posts: 296
Joined: Tue Feb 17, 2015 11:54 am

Re: AI production queue coding/planning

#15 Post by Morlic »

So I went ahead and started to implement some ProductionQueueManager which allows to assign priorities to items and keeps the production queue sorted accordingly.

https://github.com/Morlic-fo/freeorion/pull/5/files

I haven't done any work on assigning "reasonable" priorities yet and there are more functionalities yet to be implemented (adjusting priority of an item in the queue etc.).
Anyway, I think this is a good time to ask for some general feedback and suggestions concerning the framework now that not too much work has been done yet.
If I provided any code, scripts or other content here, it's released under GPL 2.0 and CC-BY-SA 3.0

Post Reply