Colonisation AI

The Silent One · **Posted:** Thu Dec 20, 2007 4:51 pm

I've started to devise a colonisation AI. It's basic, but should be perfectly functional. However, due to the lack of python experience and knowledge of the fo/AI-interface on my part, the code is currently rather incomplete.
I may learn some python and try to make myself familiar with the fo/AI interface, but before that I'd like to hear what you think about the concept and if anyone might be willing to support me?

Code:

# Concept for a colonisation AI
# --- Create a list with idle colony ships ---

  # create a list with all stationary fleets of the AI player
  # erase all fleets from the list that have no colony ship   
  # if the the list is empty, the colonisation AI is done

# --- Search for suitable planets ---

  # (1) create a list with all explored systems
  # (2) create a planet list from the system list
    # (2a) Remove planets with enemy ship presence (could also be done on system scale)
    # (2b) Remove planets that are already colonized  
    # (2c) Remove planets that have a colony ship en route
      # get moving fleets of player
      # remove fleets without col ship or with colony ships that do not have a colonize flag
      # remove the remaining colships targets from the planet list

  # (3) Sort planet list with regard to their value
      # every planet is assigned an integer value (its colonisation value)
      # values should be calculated from an easily modifiable table
      # Fertility, Size, Specials, Distance to homeworld should be taken into account
      # sort list by colonisation value

# --- Send a colony ship ---

  # Send colony ships from idle list to the top planets on the planet value list
    # Ships could be assigned to nearest planets
    # Ship mission should be set to 'Colonize'
    # On Arrival, a colony must be founded at the begin of the turn if ship mission is colonize

Geoff the Medio · **Posted:** Thu Dec 20, 2007 5:47 pm

I suggest worrying less about the details of how to do basic filtering, like how to get a listed of explored uncolonized planets... Whether you erase ships from a list if they don't meet criteria, or iterate through the list and add ships that do meet criteria to another list isn't that important.

Instead, you should probably spend more time figuring out the details of the important calculations you'll need to do to rank possible colonization targets.

The Silent One · **Posted:** Mon Dec 31, 2007 8:16 pm

Geoff the Medio wrote:

[...] figuring out the details of the important calculations you'll need to do to rank possible colonization targets.

planet evaluation
- could be made flexible and take the need for population, minerals or research into account
- however, it'd probably more efficient to simply assign every planet a fixed score based on size, hospitality and specials (see below)
- planet should be close to empire/next colonised world

Code:

# size score
tiny    small    medium    large    huge
0       20       40        60       80

# hospitality
terrible   adequate     optimal
0,5        1            2

# specials score
  minerals +20
  artifacts +20
  plague -20

planet_attractivity = size_score * hospitality + special_scores - distance(SL-jumps) * 10

example:
huge, terrible planet ~ medium, adequate planet ~ small, optimal planet

:arrow:

prevent AI to colonize planets too early
The AI should not colonize a planet if only very few systems are explored and more systems can be explored, except if the planet is valuable. Before colonizing, it should explore more systems.

subtract from planet attractivity:
UNEXPLORED_SYSTEMS (in range) / EXPLORED_SYSTEMS * k; (k = 20)

-> early game -> explored_systems small -> planets only attractive if no systems unexplored
-> late game -> explored_systems large -> unexplored systems become irrelevant

:arrow:

suggested planet evaluation formula

Code:

planet_attractivity = size_score * hospitality   + special_scores    - distance(SL-jumps) * 10   - unexplored_systems / explored_systems * 20

The Silent One · **Posted:** Mon Feb 18, 2008 4:03 pm

Just wanted to let you all know that the colonisation AI is at a working state. Currently only size and hospitality are taken into account for planet evaluation. Inhospitable and very small planets are not colonised at all.

If anyone has ideas/suggestions, now would be a good time to bring them forward.

The Silent One · **Posted:** Sat Mar 01, 2008 3:06 pm

If you would like to see my current exploration and colonisation code at work, take a look here:

(3,4 mb animated gif)
http://www.screenshots.cc/out.php/i50_fo.gif

Especially look out for the light green player in the top-left corner; notice how he sends ships out to all the systems nearby; if an attractive planet is found, another ship departs from the home system and colonises the planet.

Things that may be improved are (probably at a later stage, though):
- exploration: only send scouts and battleships to explore, not colony ships; send scouts to systems they are already close to
- colonisation: evaluate specials, maybe implement other means of evaluation

Any thoughts?

pd · **Posted:** Sat Mar 01, 2008 3:43 pm

Looking good. Is that the same AI that came with the latest release?
How did you get the entire galaxy explored at turn 1?

How is the performance? I noticed with the latest release, that turn processing times are quite high, even at a very small galaxy. I've played a game for about 100 turns and the times to process a turn took nearly a minutein the end, even though all my 4 cores seamed to be used.

In that game the dominating AI had even build a Mark IV, which was quite a surprise to me, since it takes quite long to build one, having myself just build Mark IIs.

Geoff the Medio · **Posted:** Sat Mar 01, 2008 4:20 pm

pd wrote:

Is that the same AI that came with the latest release?

No, it's the AI he's developing.

Quote:

How did you get the entire galaxy explored at turn 1?

It's not actually explored, but it's all visible because he's using a custom build I sent him.

Quote:

I noticed with the latest release, that turn processing times are quite high, even at a very small galaxy. I've played a game for about 100 turns and the times to process a turn took nearly a minutein the end, even though all my 4 cores seamed to be used.

I'm not sure about this, but it could be due to rather inefficient algorithms used to find places for ships to explore. Could you load a save that has a minute-long turn time, play a few turns, then load up the AI log file, and then look for the last two instances these two lines in the debug output:

Code:

2008-03-01 08:10:25,074 DEBUG AI : Generating Orders
2008-03-01 08:10:25,965 DEBUG AI : AIInterface::DoneTurn()

The exact numbers and date will vary, but the important thing I'm looking for is the amount of time between the start and end times of a single turn of AI processing. In the above, it's 08:10:25 to 08:10:25, or less than one second (for a small galaxy near the start of the game).

Quote:

In that game the dominating AI had even build a Mark IV, which was quite a surprise to me, since it takes quite long to build one, having myself just build Mark IIs.

The AI in v0.3.8 enqueues one of each ship is knows how to build each turn, so it might have been working on that from the first turn. If it managed to colonize a decent planet with its colony ship, it could have enough PP to build it by the end of a game.

The Silent One · **Posted:** Sat Mar 01, 2008 5:10 pm

pd wrote:

I noticed with the latest release, that turn processing times are quite high, even at a very small galaxy. I've played a game for about 100 turns and the times to process a turn took nearly a minutein the end, even though all my 4 cores seamed to be used.

I don't think the lag is related to the AI, but generally due to a large number of visible systems. I've noticed that not only the turns, but the game itself tends to slow down in large galaxies if all systems are visible. I'll look into the AI aspect of speed though, but I'm almost certain it is not the reason for the long turns.

The Silent One · **Posted:** Sat Mar 01, 2008 5:29 pm

On my machine, the turn processing of a completely visible 100-star galaxy takes ~6.5 seconds. A single AI turn needs ~0.25 seconds, so all AI players together should not use more than 1 second to do their turn; at least at the start of the game. Of course this is no exact scientific analysis, but this should make it obvious that there is a different component than the AI slowing things down.

pd · **Posted:** Sat Mar 01, 2008 5:31 pm

Code:

2008-03-01 18:21:57,500 DEBUG AI : Generating Orders
2008-03-01 18:21:57,640 DEBUG AI : AIInterface::DoneTurn()

From those logs, it seems like The Silent One is right.

Here is also the save game.
The first turn is still rather quick. For the second one I counted till about 45 seconds(not very accurate, I know). For the majority of this time, the turn processing screen said "executing orders of empire 4".

Anyway, I hope this helps. Even with a simple AI like this, flying around and exploring the galaxy is quite some fun already

Geoff the Medio · **Posted:** Sat Mar 01, 2008 5:53 pm

pd wrote:

For the second one I counted till about 45 seconds(not very accurate, I know). For the majority of this time, the turn processing screen said "executing orders of empire 4".

I checked in the task manager while that long turn was running, and the server itself - not the AIs - was using ~90% CPU. I have no idea what's different between the first turn and the second that makes the second take so long though...

Geoff the Medio · **Posted:** Mon Mar 03, 2008 1:12 am

Truely the work of an insane puppet-master...

Phaze · **Joined:** Sat Mar 15, 2008 11:27 am **Posts:** 1

Geoff the Medio wrote:

pd wrote:

For the second one I counted till about 45 seconds(not very accurate, I know). For the majority of this time, the turn processing screen said "executing orders of empire 4".

I checked in the task manager while that long turn was running, and the server itself - not the AIs - was using ~90% CPU. I have no idea what's different between the first turn and the second that makes the second take so long though...

This seems suspiciously close to this bug from SourceForge:

AI orders is taking ages to calculate

When I play several turns in FreeOrion 0.3.8 (Windows Vista 32-bit,
Core2Duo 2.13 GHz, 2 GByte RAM) the enemy empire order calculation is
taking more and more time from turn to turn.

Once I looked on my watch and it took more than 2 minutes.

But I can speed it up by save and then load the savegame before I end my
turn without restarting FreeOrion. If I do so, only the "production and
growth" calculation is taking a moment, but the enemy empire orders are
fast as lightning again. But only for once, if I do not save and load this
savegame it is taking ages again.

etintel · **Joined:** Sun Aug 15, 2010 5:20 pm **Posts:** 32

I stumbled across this little thing:

Code:

# TODO: in planet evaluation consider specials and distance

So the distance weight should be calculated. Are the planets in some tree or do they have neighbors as properties or parameters? How much such the distance weaken the desirability of a planet? I made this calculation with the formula in the image. As it can be seen even the poorest planet is better than the best possible planet at distance of 5. The (tree) search could be stopped when the some assigned cost has been exceeded, because no better planet can exist beyond certain distance boundary which is 4 (I think it should be less) in this case. Or am I looking at this from a wrong angle?

Code:

    # planet size ranges from 1-5
    # should be reworked with races
    if planet.type == fo.planetType.terran: return 2
    if planet.type == fo.planetType.ocean: return 1
    if planet.type == fo.planetType.desert: return 1
    if planet.type == fo.planetType.tundra: return 0.5
    if planet.type == fo.planetType.swamp: return 0.5

This is a generalized case of searching just the neighboring planets from own planets. Obviously there are some strategic maneuvers (like in Civ 4) of colonizing a crappy planet near the enemy and gifting the planet for goodwill, but I think they can be solved in some other way.

Geoff the Medio · **Posted:** Thu Aug 26, 2010 8:10 pm

etintel wrote:

Are the planets in some tree or do they have neighbors as properties or parameters?

Planets are located in Systems, which are connected by starlanes. You can find the shortest path between two systems, or whether they are connected by starlanes, using the Universe's systemsConnected and shortestPath functions exposed to Python.

Quote:

How much such the distance weaken the desirability of a planet?

That's a strategic decision... depends on the AI and its goals and situation, how fast colony ships move, how far systems can exchange resources, etc.

Quote:

Or am I looking at this from a wrong angle?

There are many possible ways to weight planets by distance when deciding where to colonize. Dividing their valuability score by distance squared could work in some situations.

FreeOrion

Colonisation AI

Who is online