AI: Reworking Exploration

[Morlic]

If I understand the current code in ExplorationAI correctly, we choose an unexplored system based on the distance to the capital and assign the closest scout to it (TODOs are mentioned to match the closest scouts? Not sure what that is about.) and repeat the process until either all systems are covered or all scouts are assigned.

Obviously, this may lead to some horribly inefficient scouting schemes. Worst-case, a single scout would travel through the entire empire to explore one system and then again cross the empire for another system just because it is closer to the empire capital. An inefficient scouting scheme may slow down early game expansion significantly.

I think it is much more reasonable to find suitable systems for each scout instead of finding a suitable scout for a system as this inherently will consider the distance.

I currently have the following exploration algorithm in mind. Before I start implementing it, I wanted to ask for additional ideas or issues that should be considered.

Code: Select all

For each unexplored system:
    Assign a high value if we can reach the system with colonization ships: Make use of MinFuel attribute of ShipDesigner here.
    Potential chokepoints or nodes close to good defensive positions will get a bonus as well
    If early game:
        Prefer points with many unexplored nodes around to speed up finding new colonization sites
    If mid game:
        Prefer single node in hope to find the end of the starlanes and reduce the number of points to defend
    If enemies came from that general direction and an enemy planet is not visible there:
        Increase the rating for that system

For each scout:
    For each unexplored system, calculate a scout-specific mission value:
        Calculate (unobstructed) path from scout location to target system.
        If with current fuel we can't reach the system and afterwards refuel:
            Check if we could go for a refuel now and then target the system.
            If we can:
                Update the distance to the target system including the refuel
            If we can't but refueling now gives us more fuel to work with:
                Update the distance to the target system including refuel weighted by a factor of 1e3 and divided by remaining fuel.
            If we can't and we won't gain any more fuel:
                Use current distance weighted by factor 1e3 and divided by remaining fuel.
        Rating for each scout-system pair is given by SystemValue / WeightedTimeToReachTarget  # includes speed considerations of the design

While AvailableScouts and UnexploredSystems:
Take scout and system with best corresponding rating.
    Check if that system is also the best rated system for another scout
    If not:
        Assign Scout to that System
    If yes:
        Check if switching the first and second best systems of the second-best scout leads to a higher overall value.
        If not: assign Scout to best system
        If yes: Assign Scout to second-best system
    # maybe think of some better and more accurate heuristic here but definitely avoid the O(n!) complexity of comparing all possible choices
    Remove scout and system from list to assign
    Calculate the jump-distance from assigned system to all other unexplored systems.
    Reduce the exploration value of each remaining system based on that distance  # In order to spread the scouts instead of assigning them to neighbouring systems.

"Emergency Exploration" could either be handled explicitly or directly within this algorithm by assigning some high EMERGENCY_EXPLORATION_VALUE to the systems. In the same way, we may define strategic scouting locations to watch enemy movements from a hopefully save location.

[Dilvish]

I'm a bit too tired just now to thoroughly comment on the pseudocode, but certainly the overall idea of focusing on what system should scout X go to, rather than which scout should go to system Y, sounds like a good idea for the general scouting (though probably not suitable for the 'emergency' demand-driven scouting tasks. I think it's been ages since scouting had any real attention, so it's due for some work. Here's a few extra considerations that I've been meaning to try to work in sometime-- keep in mind that pretty much every scout visit to a new system is a bit of a gamble, the scout could easily die. Expanding somewhat on the "Prefer points with many unexplored nodes around" idea (and noting that we get their coords just from basic visibility, what shows up with question marks on the player map), pretty much the highest priority (when possible) should be to send the scout into a system that has been previously visible (so we know there is not a sentry or other similar fixed monster there) but from which the scout will gain visibility into another system that has not previously had partial visibility. We should also check if the scout currently has the derelict detection range boost before deciding where to go-- depending on the surroundings we may want to choose a place withing one turn's distance so it will still have the boost when it arrives, perhaps even backtracking if we expect that to still reveal new system contents. Also, until the empire gets Radar we should probably have the AI somewhat prioritize physically visiting systems-with-asteroids to make sure that more valuable ships don't get sacrificed to Asteroid Snails.

Also, as Mat has rightly pointed out before, once the AI has explored all the readily-explorable systems, it should be willing to let its scouts get stranded outside of fuel range for a bit so that it can explore farther sooner.

[Morlic]

These sound like good ideas.

So when looping over the unexplored systems, we will also find all visible systems in scouting range. Afterwards, these systems will get some rating based on the value of systems they would explore and again some factor of how far away from other unexplored nodes the visible node is so we do not go into some weird one-way road that is separated from the unexplored nodes.

As far as the derelict detection range is concerned: Any ideas on how to detect this? I suppose comparing actual detection range with the design detection range could work? Once that is done, it probably could be covered by the visible-system-loop with enforcing the distance to 1 turn...

Concerning the asteroid snails, this could probably be expanded a little bit further by evaluating how likely it is that ships will enter the system (colonizable planets here and in the following systems etc.) and probably also consider how much it interferes with further exploration.
For detecting the asteroid snails, I think it is enough to move through the system instead of actually visiting it? Could potentially save a turn.


The algorithm I outlined in the OP should already cover the fuel issue but feel free to add some more ideas/considerations of when it is "worth" it to let scouts strand.

[Dilvish]

As far as the derelict detection range is concerned: Any ideas on how to detect this?

The ship has the "DERELICT_SPECIAL2" special actually applied to it.