[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 112: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 112: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 112: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/functions.php on line 4586: Cannot modify header information - headers already sent by (output started at /includes/functions.php:3765)
[phpBB Debug] PHP Warning: in file /includes/functions.php on line 4588: Cannot modify header information - headers already sent by (output started at /includes/functions.php:3765)
[phpBB Debug] PHP Warning: in file /includes/functions.php on line 4589: Cannot modify header information - headers already sent by (output started at /includes/functions.php:3765)
[phpBB Debug] PHP Warning: in file /includes/functions.php on line 4590: Cannot modify header information - headers already sent by (output started at /includes/functions.php:3765)
AI Challenge Forums • View topic - Optimal expand

It is currently Wed Apr 25, 2018 12:08 pm Advanced search

Optimal expand

Share and discuss ideas for your entries here.

Optimal expand

Postby Gudradain » Wed Nov 03, 2010 1:19 am

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.
Gudradain
Cadet
 
Posts: 3
Joined: Fri Sep 24, 2010 3:31 am

Re: Optimal expand

Postby Emi » Wed Nov 03, 2010 1:37 am

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
Emi
Cadet
 
Posts: 3
Joined: Wed Nov 03, 2010 1:28 am

Re: Optimal expand

Postby glevee » Wed Nov 03, 2010 1:40 am

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. :D
glevee
Colonel
 
Posts: 68
Joined: Tue Sep 28, 2010 1:11 am

Re: Optimal expand

Postby Innominate » Wed Nov 03, 2010 4:14 am

Innominate
Captain
 
Posts: 22
Joined: Wed Oct 06, 2010 3:20 am

Re: Optimal expand

Postby dimkadimon » Wed Nov 03, 2010 5:03 am

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.
dimkadimon
Major-General
 
Posts: 263
Joined: Wed Oct 06, 2010 11:34 pm
Location: Adelaide, Australia

Re: Optimal expand

Postby glevee » Wed Nov 03, 2010 4:30 pm

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"...)
glevee
Colonel
 
Posts: 68
Joined: Tue Sep 28, 2010 1:11 am

Re: Optimal expand

Postby RebelXT » Thu Nov 04, 2010 4:27 am

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.
RebelXT
Colonel
 
Posts: 81
Joined: Fri Sep 10, 2010 2:05 pm

Re: Optimal expand

Postby luismi » Thu Nov 04, 2010 11:13 am

luismi
Lieutenant
 
Posts: 16
Joined: Sun Sep 12, 2010 10:50 am

Re: Optimal expand

Postby dimkadimon » Fri Nov 05, 2010 12:36 am

dimkadimon
Major-General
 
Posts: 263
Joined: Wed Oct 06, 2010 11:34 pm
Location: Adelaide, Australia

Re: Optimal expand

Postby voidptr » Fri Nov 05, 2010 8:12 am

voidptr
Brigadier-General
 
Posts: 139
Joined: Sun Sep 12, 2010 7:22 pm

Next

Return to Strategy

Who is online

Users browsing this forum: No registered users and 1 guest

cron