Optimal expand

[Gudradain]

Just a question like that

Imagine that your oponent is doing stricly nothing. Is there an optimal strategy to take all the neutral planet on the map. Meaning that there is 1 strategy that give you more ship after X turn than any other strategy.

[Emi]

of course there is one such strategy. Since the game is deterministic, it is simply the fastest way to get all the planets.

Doesnt mean it is trivial thought. There probably isnt any "do that then do that" simple procedure to follow that works better everytime.

However, u can use pretty trivial heuristics taking into account distance and (growth/nbShips) that have good results

[glevee]

Sorry, can't think of anything that could be better than the obvious......


(take the "closest, fastest growing planet(s) with the least defenders", rinse and repeat...)


How does one determine that? Sorry, you asked a Strategy question.

[Innominate]

[dimkadimon]

I was thinking about a similar problem the other day. Assuming that your opponent does nothing what is the least number of turns you need to capture all the neutral planets?

To simplify things, lets assume that we capture each neutral planet p from a single source and we capture them in one go (sending p.NumShips()+1). The problem can now be formalized as a standard breadth-first tree traversal. The root of the tree is our starting state. State transitions are either "capture planet p from planet s" or "wait 1 turn". In some cases you might be better of waiting. As soon as you reach a state where all neutrals have been captured then you stop. The depth of this goal state is then your answer. At the start (when you have few planets) the branching factor is not too high, however towards the end the branching factor will grow exponentially. You could prune the tree, by only considering planets s that are "closest" to planet p, say the top 5 closest.

[glevee]

The Strategy is that "simple" . . . The devil is in the implementation details (which is last time I checked is tactics). ("simple" is such a fun word. does the ability to state something simply (in a few words) make the thing itself simple??)

There exists some ratio between TravelTime, GrowthRate, and NumDefenders upon which all planets can be ranked (closer,higher,less are best.) There also exists some relationship between YourNumShips and these ranked planets (in terms of both current_ship_usage and future_ship_growth) that determines the optimal attack plan. (all this is balled up in my "quoted" list of attributes, strategy.)

What about tactics?

Lets use Innominate's example (the planets). We have 100 ships and three other planets, what do we attack?? In terms of # of turns it doesn't matter if you take the two 39s or the 65 (you will achieve the necessary number of ships to take the remaining planet(s) on the same turn). BUT, since we care about #ships, it does matter. Taking the two 39's gives us more left over ships when it comes time to take the 65, then we have were we to have taken the 65 first (when it comes time to take the 39's.) and inn's suggestion of binary knapsack would "tell" you to take the 39's first. ("single turn binary knapsack" is optimal in this simple example, and I would agree that it would not always be so. I know there are a couple of people who were/are working with some sort of "multiturn binary knapsack"...)

[RebelXT]

Great topic. Galcon Labs actually has a single player mini-game called Vacuum which goal is to capture all neutral planets as quick as possible.

As DimkaDimon mentioned, exact solution could theoretically be found using a full state space traversal. This appears to be NP-Hard problem somewhat similar to TSP (Traveling Salesman Problem). If we simply assume that all planets are captured sequentially (even if we allow multiple launches/captures during a single turn), there are 20! different ways to capture 20 planets on a map, so it's not possible to solve by just brute force search. Pruning is absolutely the key. There are likely some effective meta-heuristics which would help to come up with a sub-optimal solution iteratively.

glevee: it seems to me what you described in your first post is a greedy method which does not find an optimal solution.

[luismi]

Just use a pair of bees

http://www.popsci.com/science/article/2 ... th-problem

[dimkadimon]

[voidptr]