FreeOrion

The calculation formula is only an example. Even though boost does seem to offer dijkstra, bfs, dfs, a* etc. I'm not sure that doing an exhaustive search of the galaxy offers that much more value to justify it.

The shortest path functions in the universe already do use the boost djikstra's algorithm internally.

Reimplementing or reworking things to do a separate shortest path calculation for AI doesn't seem necessary.

Ok, but say that AI owns 5 systems and knows 55 will result in 250 tree searches in the entire search space. Anyway I encountered this:





It looks like the definition in PythonUniverseWrapper.cpp differs from universe.h and the attempted version. What am I doing wrong?

You can probably not bother checking the distance to planets that don't meet certain criteria for colonizability. Regardless, if it's a problem, we can address it.


There's probably a problem in that I've exposed the function as taking a pointer to Universe, but Python objects seem to be treated as references, so I'll try changing that. Edit: I changed it. Try using universe.leastJumpsPath(start_sys_id, end_sys_id, empire_id) with the latest SVN. /Edit

Edit: nevermind I just located this on the API.

Another problem. How do I get systemID from a planetID? I tried getPlanet(planetID).systemID, but it seems to make a mess of things. Using the following allows to work around (at least so far) this but is there a better way?

What goes wrong with getPlanet(planetID).systemID ? Presumably it should work. What happens if you do the second version without the deepcopy?

There is random stuff happening. Amount of unexplored systems starts to vary uncontrollably. Exploring systems does no longer impact the amount of unexplored systems etc. I think it has to do with the leastJumpsPath modifying the system ID or something. However, if that is ok, I'll use the deepcopy version.

Could you be more specific? Are the properties of planet or system objects gotten with getPlanet or getSystem changed, or the values in the Python AIState data structures? The leastJumpsPath and shortestPath functions don't (or shouldn't) modify the gamestate in any way. If it's an issue with just the data in Python, then that should be fixed in the AI scripts.


I'd rather know what is causing weird "random stuff" to happen, and prevent it.

Debug results are from python, I think.



If you wish to see the unexplored systems thing run the "vanilla" version, check the AI_1.txt for the unexplored amount (Number of Unexplored systems:) and do the same with replacing ColonisationAI.py with the one attached. When you comment the lines below and play a turn things return to normal. At least most of the time. Sometimes starting a new game helps. Python coding while the game is running can take while before the changes appear in the logs.

Whether or not a planet's location is "good" is dependent on a number of different factors, many of which may or may not be directly related to the planet's distance to any owned planets. Instead of just inserting a numerical modifier for how distant a planet is, it would probably be better to calculate, independently of one another, such things as:

Within Resource Supply Range? (if not, how long before it can be made so?)
Within Fuel supply range? (if not, how long before it can be made so?)
Proximity to Empire X? (is empire X likely to attack my colony, or defend it?)
Within total range of ships? (how many of my ships have the fuel to get there from the nearest colony?)
Actual time to get there from the nearest colony? (is this likely to change in the near future?)

Each of these questions would increase or decrease the desirability of the planet by a certain value.

If you just "divide desirability by distance squared," the AI's judgement of planets will often be very skewed, since distance, in and of itself, is neither desirable nor undesirable - it's the various consequences of distance which make it so, and these aren't easily summed up with a single number.

_________________
Warning: Antarans in dimensional portal are closer than they appear.

1. Definitely when the grand strategic AI can make such estimations.
2. Same as above.
3. This is a slightly more complicated matter. Actually a little bit more than slightly.
4. This does not seem too important as the quality of the colony should be a clear priority.
5. Same as above.



The point in it was to create some formula to cut down the search space. The distance is sort of an abstraction of these more complex problems. Realistically speaking are there any situations where expansion far beyond supply lines is beneficial? In other strategy games sometimes only useful situations are bottlenecks in the map or gifting a city. Also I have noticed that the colonies get destroyed quite easily when they are too far from the homesystem and new colony ships are not too cheap. I do believe that the AI should be unpredictable, but if the game rules are like tic-tac-toe with 2 markers in line putting the third marker in line makes so much more sense than doing something else.

It doesn't matter whether or not it can make an accurate estimation yet. The point is to establish a solid framework for the AI that can be added to later, rather than having to be rewritten completely. Also, instead of just "within resource supply range", it would be good to calculate the percentage of each physically transferrable resource that's in the section of the empire to which it is currently connected. (In the future,) each of these resources can be weighted based on the empire's estimation of how much that colony is likely to need of a specific resource. Just hack something together that gives a rough estimate of how long it will take to increase resource/fleet supply to the desired system, or even just use a variable based solely on current supply range vs. desired supply range, which can easily be replaced in the future when the AI is able to figure out how long it will take to research stuff, and what it's researching. That's still more sustainable than just having nothing there, since it's easier to expand on in the future.

I assume there's no problem with actually determining whether or not the planet is currently within supply range?


Since there's no diplomacy yet, all other empires can be considered hostile, and equally so. In other words, use a constant for the likelihood of empire X attacking the colony. A separate calculation for determining the value of this constant (making it a variable) can be added later. Determining proximity can be a simple calculation now, but in the future, should be expanded to include things such as enemy range/speed, the location of enemy ships, whether the nearby enemy system is undeveloped or highly developed, etc.

This is a matter of weighting. Depending on the empire's specific needs, each of the variables that determines planet desirability will have to be weighted differently. If the planet is in high risk of attack, for example, being able to get ships there quickly would be an important factor. Moreover, in the future, the AI should use the various values that determine planet desirability to determine how they can improve that desirability (weighed against the costs of doing so, of course), for example, by researching a tech that increases supply range, or increasing the number of ships that are near the planet in question.

"Abstracting complex problems" is the reason most AIs are so stupid. The AI has to analyze the situation the same way a human would to be effective, and that means taking into account all the issues that are affected by distance, not just distance itself.

Yes. My hope is that spies will be able to travel along resource supply lines that link to any planet on which they are stationed, which means that an outpost outside of supply range might be a good location for a particularly sensitive building, for example.

These considerations should factor into the AI's decision-making process, of course.

Ideally, the AI should always make the best decision. If that means putting the third marker somewhere else to gain a long-term strategic advantage, then that's what I want it to do.

If you disagree with anything I've written, I would love to argue about it, so please speak your mind.

On a semi-related note Geoff, do you plan to make WithinResourceSupply and WithinFleetSupply conditions? It makes so little sense when an Industrial Center is affecting an unconnected system on the other side of the galaxy (not that that happens all that often, mind you). I feel like most such buildings should only affect other colonies within supply range, and there are probably ship effects that should have that condition as well.

_________________
Warning: Antarans in dimensional portal are closer than they appear.

Keep the faith.



I would propose some kind of encyclopedia for tactical and strategic considerations which contains all these aspects. It would be easier to analyze.



How does this equate to colonization?



Quite the contrary, the reason why AI is "stupid" is in it's inability to abstract.



Humans do make abstractions. That is what makes them seem intelligent.



You win tic-tac-toe with three markers in line. Also information is incomplete so assessing trivial probabilities is not possible. What is the best decision?



I have noticed.

Could you please be a bit more clear in your responses? It can occasionally be difficult to decrypt vague sarcastic comments such as the above...

Do you mean something AI readable? Why would you write such calculations into a separate document, then program the AI to read it, when you could just program the relevant calculations into the AI itself? Or did I completely misunderstand?

On a semi-related note, I don't think the AI can read effects groups yet - it's undoubtedly really complicated to implement, but I expect it will ultimately be necessary for making a competent, versatile AI.

Would you colonize a system that's right next to enemy territory if you can't easily get ships there to defend it? Defensibility is a variable that is used to calculate the desirability of a potential colony. Danger of being attacked would be a variable used to calculate the weight of defensibility in the calculation for desirability.

It's all too easy to make the AI abstract complex problems - that's exactly what you propose to do with distance when calculating desirability of planets.

Humans are intelligent because they can abstract complex problems in a way that doesn't greatly compromise the end results of their mental "calculation". This allows us to make seemingly very complex strategic calculations in a very short period of time. Note that the illusion of extreme mental capacity doesn't come from an increase in accuracy, but from an increase in speed, at a slight cost to accuracy. The best way to create a good AI is to try to imitate the structure of human thought while eliminating the uncertainties and abstractions that lead to error. The argument that "Humans abstract, and we're smarter than AIs, therefore distance should go directly into the planet desirability calculation," is not satisfying to me. When you're analyzing a potential colony, do you take into account distance as a single variable (and if so, distance from what?), or do you take into account the greater variety of strategic factors, all of which may be more or less dependent on distance (to various other objects) depending on the circumstances?

Don't avoid the point - you don't win FreeOrion by having 3 markers in a line. Even though having colonies near to each other is usually the best way to go, I want the AI to make a different decision when it's appropriate.

_________________
Warning: Antarans in dimensional portal are closer than they appear.