The problem with such sector-based scouting is that Stars universe layout is far from homogenous. I here turn huge normal galaxy into graph with colored edges to give you example:
http://www.hot.ee/dakotk/hugenormal.GIF

The distances less than 50ly are cyan and 50-81.99 green edges. (less than 50 is important to someone who got no Fuel Mizers.)

Like you see, these edges form almost tracks. Best non-penetrating scouting algorithms follow such tracks as good as possible instead of staying in sectors.

Report message to a moderator

m.a@stars wrote on Tue, 07 March 2006 22:37

Sounds good. I've been meaning for a long time to at least try creating optimal scout routes out of nil. Not exactly easy, tho, even if you don't have penscanning.

This is a variation of the 'Travelling Salesman Problem'. A google search will provide lots of material.

Short version: it's NP-complete (solution time for optimal path increases exponentially with the number of Stars), but it should be possible to find a 'good' solution.

One wrinkle is that the fuel/time costs and the various breakpoints (36/49/64/81 etc.) make the travel costs very non-Euclidean, although the triangle inequality still holds. This causes some non-local effects that aren't in the intial TSP - costing an extra year by splitting an 81 year jump into a 36 and a 54 year jump may save enough fuel to save two or more years later on.

Report message to a moderator

Kotk wrote on Tue, 07 March 2006 20:08

m.a@stars wrote on Tue, 07 March 2006 11:44 Seriously, though, I've always wondered why Stars! (or an Stars!-like clone) is not swamped by AI researchers doing moddings and such. Some of the Jeff-made AI-s in game play at newbie level, lot of games made significally later have far worse AIs. But still i doubt there is any reason to be interesting for some AI researcher. Almost all games have "AI players" and "Non-player characters". These parts of software are far from "Artfical Inteligence". They have no goals. Getting to goals has no choices of strategies. Strategies do not raise subgoals. Getting to subgoals have no choices of tactics. No generated decision trees, no logics, no heuristics. Vegetables not AI-s.

Yeah, I know. If only modern games had at least some semblance of Jeff-style AI... My current goal is not any true AI, mind, but just a set of "automaton scripts" which one day a "smart script" can use to emulate what the current Stars! "AIs" do now.

The interesting part is Stars! (or a Stars!-like clone) offers a nice simple/complex playground for anyone interested in game-AI to test his/her skills/ideas.

Once the interface hurdles are solved, anyway.

[Updated on: Wed, 08 March 2006 04:19]

Report message to a moderator

joseph wrote on Tue, 07 March 2006 23:05

The +-20 degrees should have been +-22.5 if I had been being exact. (so 8 scouts instead of 9 - one for each part of the compass). This would mean that the scout would chose its own path but that the AI would not say acidentally send the scout backwards towards its origin (with +-60 scouts could go backwards). Ok I have changed my mind - I want to specify the +- degrees and have a default of 20 (or 22.5) if I dont specify.

I see. Just plain simple outwards scanning.

Might be a good start for later route-improving algorithms.

Report message to a moderator

Kotk wrote on Wed, 08 March 2006 01:43

The problem with such sector-based scouting is that Stars universe layout is far from homogenous. I here turn huge normal galaxy into graph with colored edges to give you example: http://www.hot.ee/dakotk/hugenormal.GIF The distances less than 50ly are cyan and 50-81.99 green edges. (less than 50 is important to someone who got no Fuel Mizers.) Like you see, these edges form almost tracks. Best non-penetrating scouting algorithms follow such tracks as good as possible instead of staying in sectors.

Such a graph has indeed been in my mind often, when considering how most ppl do actually scout their space. Could you please tell me how you generated it? I know the general idea, but I'm too lazy/busy to research the actual algorithm/code.

I wonder if you have any other cool ideas for penscans?

[Updated on: Wed, 08 March 2006 04:41]

Report message to a moderator

Madman wrote on Wed, 08 March 2006 06:48

m.a@stars wrote on Tue, 07 March 2006 22:37 Sounds good. I've been meaning for a long time to at least try creating optimal scout routes out of nil. Not exactly easy, tho, even if you don't have penscanning. This is a variation of the 'Travelling Salesman Problem'. A google search will provide lots of material.

In fact it did. That's what prompted me to attack the problem from a completely different angle, at least for mineral/pop balancing.

Though the "Ant Colony" algorithms do sound promising: start with a straight path outwards and tweak it until max planets are scanned. That's what prompted my "fuel/trip" optimizer script a year ago, as a stepping stone for the greater goal.

Report message to a moderator

m.a@stars wrote on Wed, 08 March 2006 11:17

The interesting part is Stars! (or a Stars!-like clone) offers a nice simple/complex playground for anyone interested in game-AI to test his/her skills/ideas.

I have tested my simple amateur AI ideas on lot simpler playgrounds. For example i did windows minesweeper AI.
Optimized the code until it sweeped expert level below 1 seconds in debug mode (unless it hit mine) on 900MHz Athlon, and then a thief stole my computer.

Quote:

Such a graph has indeed been in my mind often, when considering how most ppl do actually scout their space. Could you please tell me how you generated it? I know the general idea, but I'm too lazy/busy to research the actual algorithm/code.

What you mean? How i generated? Silently. Wrote in C++ (2003). Reading xy file algorithm i already had, star map display i already had. Used boost::graph template for graph (but current problem needs none of its features). Algorithm to fill graph is 10-liner that selects all pairs of two different planets, uses Pythagoras for calculating distance between them and if distance fits to conditions then add edge to graph. Most code/time went to displaying that graph on star map later.

Quote:

I wonder if you have any other cool ideas for penscans?

For one example to think about:
1) Draw scanner radius circle around all unscouted planets.
2) measure sweetness of each spot within 81 ly radius to your scout (by how many circles overlap there). Its ~20K spots.
3) choose some sweetest spot and go there.
4) remove the circles for scouted places and back to 2)

Report message to a moderator

Kotk wrote on Wed, 08 March 2006 14:49

m.a@stars wrote on Wed, 08 March 2006 11:17 The interesting part is Stars! (or a Stars!-like clone) offers a nice simple/complex playground for anyone interested in game-AI to test his/her skills/ideas. I have tested my simple amateur AI ideas on lot simpler playgrounds. For example i did windows minesweeper AI. Optimized the code until it sweeped expert level below 1 seconds in debug mode (unless it hit mine) on 900MHz Athlon, and then a thief stole my computer.

Ouch! You didn't have a backup?

Quote:

Quote: Such a graph has indeed been in my mind often, when considering how most ppl do actually scout their space. Could you please tell me how you generated it? I know the general idea, but I'm too lazy/busy to research the actual algorithm/code. What you mean? How i generated? Silently. Wrote in C++ (2003). Reading xy file algorithm i already had, star map display i already had. Used boost::graph template for graph (but current problem needs none of its features). Algorithm to fill graph is 10-liner that selects all pairs of two different planets, uses Pythagoras for calculating distance between them and if distance fits to conditions then add edge to graph. Most code/time went to displaying that graph on star map later.

I'm afraid I wouldn't know how to use any proper "graph" lib if it bit me in the I. But, from what you explain, I gather I'm only lacking the "conditions" to add the edge to the graph, plus perhaps a proper structure for storing such graph.

Quote:

Quote: I wonder if you have any other cool ideas for penscans? For one example to think about: 1) Draw scanner radius circle around all unscouted planets. 2) measure sweetness of each spot within 81 ly radius to your scout (by how many circles overlap there). Its ~20K spots. 3) choose some sweetest spot and go there. 4) remove the circles for scouted places and back to 2)

Yeah, I tried that one long ago. Phase 2 turned out to be the hardest. But I think if I used some kind of graph to weed out most faraway "sweet-spots" things would improve significantly.

Or else try a completely different tack. *sigh*

Report message to a moderator

m.a@stars wrote on Wed, 08 March 2006 16:41

Ouch! You didn't have a backup?

Nay, but then again ... minesweeper was too simple problem even for AI amateur like me. There are 16x30 unknowns that can be "mine"/"no mine". Gradually during playing these turn into knowns, and all known "no mine"s give knowledge about 8 unknowns around them. So profiling did show that most of the time AI was busy "looking" at the board and clicking it, there was no much to think about.

Quote:

But, from what you explain, I gather I'm only lacking the "conditions" to add the edge to the graph, plus perhaps a proper structure for storing such graph.

Conditions i gave already? distance < 50 => cyan edge,otherwise distance < 82 => green edge, otherwise no edge.
Graph is nothing special. Directed edge is pair of integers (source vertex id, destination vertex id) so you need vector of pairs of integers to store all edges. Bidirectional edge is one edge there and one back. If you know all your graph has only bidirectional edges anyway (like on our case) then you may use only one pair for each edge. If you want attributes like colors or weights or distances add same size vector for attributes too. Like i say i used boost template but only for it makes needed storages, iterators and all such crap for me. Actually its real powers were not used.

Quote:

Yeah, I tried that one long ago. Phase 2 turned out to be the hardest. But I think if I used some kind of graph to weed out most faraway "sweet-spots" things would improve significantly.

Oh ... I joked about that phase 2 thing and need to calculate 20000 times. I think that pen-scanning scouting is geometry problem rather than graph problem. If you have 2 circles they overlap or they dont. Now ... if you have 3 circles that all overlap with each other then there may be (and may not be) region where all 3 overlap. Now if there was such 3- way region and there is 4th circle that has also such 3-way region with each pairs of above 3 then there also exists 4-way region. And ... so on. At some moment you have list of all possible regions. If there are no 5 way regions then there are also no 6 way regions to consider.
Then you take that BOSS 81 ly circle around your JOAT scout, for what you have to analyse these regions. If nothing overlaps with it you take 162 ly circle and so on. Also to simplify your task and have less various regions to consider ... you can limit with say 20 closest unscouted planets to your scout.

Report message to a moderator

Report message to a moderator

Kotk wrote on Wed, 08 March 2006 19:37

Nay, but then again ... minesweeper was too simple problem even for AI amateur like me. There are 16x30 unknowns that can be "mine"/"no mine". Gradually during playing these turn into knowns, and all known "no mine"s give knowledge about 8 unknowns around them. So profiling did show that most of the time AI was busy "looking" at the board and clicking it, there was no much to think about.

Doh. Not exactly my kind of "strategic AI" either.

Quote:

Conditions i gave already? distance < 50 => cyan edge,otherwise distance < 82 => green edge, otherwise no edge.

Sorry, I surely wasn't paying enough attention.

Quote:

Graph is nothing special. Directed edge is pair of integers (source vertex id, destination vertex id) so you need vector of pairs of integers to store all edges. Bidirectional edge is one edge there and one back. If you know all your graph has only bidirectional edges anyway (like on our case) then you may use only one pair for each edge. If you want attributes like colors or weights or distances add same size vector for attributes too.

Looks somewhat similar to what I've already done. I need to put just a bit more work into the matter, it seems.

Quote:

I joked about that phase 2 thing and need to calculate 20000 times. I think that pen-scanning scouting is geometry problem rather than graph problem. If you have 2 circles they overlap or they dont.

Phew. U got me allright with those 20000 times.

I agree about penscan looking more like geometry problem. Trouble is, those circle overlaps take CPU power to calculate...

Quote:

If there are no 5 way regions then there are also no 6 way regions to consider.

Nice. I hadn't considered that one.

Thanks for the explanations. Definitely, I will have to put a bit more effort into the whole matter.

Report message to a moderator

joseph wrote on Wed, 08 March 2006 22:54

Scouts No - you misunderstand. While an algorithum that calculated max stars scouted in min time with specific scout and took that route would be sweet. What I wanted was a "go to this star" + "Try to scout a planet each turn on way" + "do not go more than X (originally 20)degrees out of direction of travel to find a planet" Also - show leaps that use large ammounts of fuel.

No worries. I consider the "higher" algorithm as the goal. But I'd start with the "smaller" scouting all right. In fact, I think I would consider fuel consumption more important than original direction of travel when deciding about taking a detour or not.

I already got a script which breaks down long trips into cheapest/fastest possible components. Perhaps I'll tweak it to include some "scenic detours" for scouting purposes.

Quote:

I am aware that this will miss some planets and that I may want to tweak flight path to optimise. But as regards removing MM it would equate to click on target planet, choose "Scout" orders, (set degree -optional), look at route to see if it has done something stupid (also optional I guess.

That would be my goal, indeed.

Quote:

From what I know of the Traveling Salesman, it would take considerable computer time to calculate the optimum routes and then some sod would shoot down one of your scouts and ruin it all.

Yeah. That's why I'd go with "sub-optimal" calculations, anyway. Having to recalculate often is a pain...

Report message to a moderator

[email

m.a@stars[/email] wrote on Thu, 09 March 2006 11:07]I agree about penscan looking more like geometry problem. Trouble is, those circle overlaps take CPU power to calculate...

Not lot of ... Condition: "If distance between centers is less than 2 radiuses then they overlap." Distance is similar like in non-pen scouting. With 1000 planets there are only half million possible pairs, so some eyeblink time it certainly takes on modern computer (with C++ at least) to consider all possible pairs in huge packed. The graph picture i attached has same complexity and it did not take a second for it to spit it out. Then there is 3-way algorithm and then there is 4-way algorithm but these got all less and less cases to consider.

If you use minor power languages like java, python or visual basic you must probably use some trick to limit the pairs to consider. I know why i love C/C++. Rare need to optimize. I can usually use brute force algorithms that are easy to read and maintain.

[Updated on: Thu, 09 March 2006 11:53]

Report message to a moderator

Kotk wrote on Thu, 09 March 2006 14:16

m.a@stars wrote on Thu, 09 March 2006 11:07 I agree about penscan looking more like geometry problem. Trouble is, those circle overlaps take CPU power to calculate... Not lot of ... Condition: "If distance between centers is less than 2 radiuses then they overlap." Distance is similar like in non-pen scouting. With 1000 planets there are only half million possible pairs, so some eyeblink time it certainly takes on modern computer (with C++ at least) to consider all possible pairs in huge packed. The graph picture i attached has same complexity and it did not take a second for it to spit it out. Then there is 3-way algorithm and then there is 4-way algorithm but these got all less and less cases to consider.

Hhhmmm. Perhaps it's time for me to start playing a bit less and coding a bit more.

Report message to a moderator

Kotk wrote on Wed, 08 March 2006 13:49

For one example to think about: 1) Draw scanner radius circle around all unscouted planets. 2) measure sweetness of each spot within 81 ly radius to your scout (by how many circles overlap there). Its ~20K spots. 3) choose some sweetest spot and go there. 4) remove the circles for scouted places and back to 2)

To make it more challenging.
What about the route aspect of the planning ?

In essence your algorithm is trying to determine the "best spot" to go to for each turn.
And each turn is calculated with no reference to how it affects future turns.
e.g you may be able to scout 6 planets this turn, but that leaves you scouting 2 next turn and 1 the turn after.
Whereas scouting only 4 this turn may let you scout 3 next turn and 4 the turn after.

To make it even more complicated the true objective is to maximise the number of planets scouted (perhaps even all planets in a given area) in the minimum time ***(see below).
That is not achieved by maximising the number of planets scouted each turn.

In a real game we make such differences irrelevant for ourselves by setting targets like "I want all planets, except LGM3, scouted in 15 years".
If the furthest planet is 10 years away at Warp 9 then that target is always achievable by building the appropriate number of scouts.
Whether we build 21 or 23 scouts to achieve it seems to matter little in the context of a real game.
If we wanted to scout them all within 12 years then we'd simply build more scouts.
As long as we can achieve our self-imposed target then pursuit of the best solution is close to pointless.

*** In a real game what is the best solution ?
One ideal is to scout all planets in the shortest time.
That is quantifiable and measurable.
However if we want to build our lovely factories then we may decide that taking 5 years longer and building 10 less scouts is a far better use of resources.

Report message to a moderator

mazda wrote on Wed, 15 March 2006 15:58

Kotk wrote on Wed, 08 March 2006 13:49 For one example to think about: 1) Draw scanner radius circle around all unscouted planets. 2) measure sweetness of each spot within 81 ly radius to your scout (by how many circles overlap there). Its ~20K spots. 3) choose some sweetest spot and go there. 4) remove the circles for scouted places and back to 2) To make it more challenging. What about the route aspect of the planning ? ... As long as we can achieve our self-imposed target then pursuit of the best solution is close to pointless.

About my own thoughts. I don't want "best". I'll settle for "good enough". And the 1st step could be just setting up the start and end points for a scoutship and tweak its route to include as many other planets (or "sweetspots") as possible without significantly increasing trip time (or fuel usage).

It would be a somewhat "dumb" algorithm, so most probably you'd need to pick your endpoints to optimize results, but it should handle reasonably well all middle waypoints for any given trip.

[Updated on: Wed, 15 March 2006 10:45]

Report message to a moderator

Report message to a moderator

"Given a number of cities and the costs of traveling from any city to any other city, what is the cheapest round-trip route that visits each city once and then returns to the starting city?"
Thats Traveling Salesman Problem. It takes very lot of time to solve with 1000 Cities. Also it is too abstract. In Stars! the problem is different (more complex):

1 ) There are multiple scouts.
2 ) There are two costs involved (fuel and time).
3 ) Fuel is limited, time limit is unknown.
4 ) Scouts starting resources (fuel) may be different.
5 ) The costs of travel are not strictly convertible. If to increase time usage then fuel usage drops.
6 ) The scouts are mortal. Number of survived/built scouts after 5-10 years is actually unknown to player himself.
7 ) Scouts may start from multiple locations.
8 ) In 15 years it is probably possible to refuel some scouts from unknown (right now) locations.
9 ) Scouts may have different traveling costs (engines and mass).


So what AI can suggest is good place to go with scouts this year and maybe next. Also it can prognose what region is possible to scout with given scouts and given fuel by given time.

[Updated on: Thu, 16 March 2006 12:40]

Report message to a moderator

Report message to a moderator

Report message to a moderator