Energy Effeciency Programming Challenge (CANCELED)

[Diazo]

Ohhh.

A brain teaser.

First, no time to run is listed, therefore I am ignoring build costs.

Using the calculations listed earlier in the thread means that the every reactor built is 80% as efficient as the previous one, down to a floor of 10%. Note that this means a 3rd Mk III reactor will never get built in a system as a Mk II is more efficient once the 10% floor is hit. (In a one homeworld game.)

Now, note the conditions you have defined in your opening post mean that this is not how I would want it handled in game.

In game, energy demand is always going to go up so I would always want the most efficient reactor built and if I've got overhead I don't care, it will get used up soon enough. However, for the conditions of the challenge here is how I would do it, not going to actually code it out but here are the steps (as I see them):

Note (Output of each mark individually) means comparing the value 3 times, once against the output of each mark level of reactor.

1) (Total Demand) / (# of Planets) = (Demand per Planet), simplify the problem to a single planet to start with.

2) Adjust (Demand per Planet) to (Modified Demand per planet) to account for built reactors. Define cost and efficiency of next reactor built for all 3 marks, accounting for reactors already built and number of homeworlds.

3)  If (Modified Demand per planet) >= (Output of each mark individually) Then Build (Most Efficient Reactor) and goto Step 2, otherwise skip this step and goto step 4. All reactors built as part of this step 3 get built at every planet.

4) At this point, we can no longer simplify things down to a single planet so accounting for the reactors built in step 3, find (Demand Left for Galaxy).

5) Define cost and efficiency of next reactor built for all 3 marks and then:

6) If (Demand Left for Galaxy) >= (Output of each mark individually) Then Build (Most Efficient Reactor) at planet #1. Repeat at next planet until (Demand Left for Galaxy) < (Output of one of the three marks). Save (Most Efficient Reactor) as (Mark Level Partially Built on X planets.)

ERROR TRAP: If (Demand Left for Galaxy) >= (Output of each mark individually) when (Most Efficient Reactor) has been built at (Max Planets) -1 Then ABORT. Step 3 is wrong.

7) Recalculate (Demand Left For Galaxy).

8.) Calculate build path for reactors spread out over planets.
Special: Check for Mk III only: If (All Planets) have Mk III reactors numbers equal to (Homeworlds) + 1 then Mk III NOT VALID.
Special: Keep track of reactors and if reactor is built on every planet, adjust (Next Reactor Efficiency Built) as appropriate.

8a) Is (Demand Left for Galaxy) < 1x Mk I reactor? If Yes, build 1x Mk I and done.
8b) Is (Demand Left for Galaxy) < 2x Mk I Reactor?  If Yes, build 2x Mk I and done.
8c) Is (Demand Left for Galaxy) < 1x Mk II Reactor?  If Yes, build 1x Mk II and done.
Can a Mk III still be built somewhere? (Special check under Step 8.) if NO build Mk II, if YES continue below.
8d) Repeat with (Mk II & Mk I), (Mk II & 2x Mk I), (2x Mk II), (2x Mk II & Mk I), build Mk III if you get this far.

9) Recalculate (Demand left for Galaxy) and goto step 8.

When you hit Done in step 8, calculation is finished and you've got the most efficient setup possible.

Also, page 2 get! 

D.

[vortexion]

Two final pieces of information I need.
One, what is the base cost, resource drain, and energy production for each of the 3 marks of reactors?
Two, what is the exact method used to determine "poor efficiency" production, including >2 reactors of the same mark on one planet, and minimum energy production (if any)?

Once, I have all the info together, I will consolidate it into the first post better.

Here you go:
MK1: build cost 1k/1.5k, drain -5/-5. The Nth reactor of this mark on a planet produces max(5000*(0.8^(N-1)),500) energy: 1 -> 5k; 2 ->4k; .. 12+ -> 0.5k
MK2: build cost 2.6k/7k, drain -15/-15. The Nth reactor of this mark on a planet produces max(40000*(0.6^(N-1)),4000) energy: 1 -> 40k; 2 ->24k; .. 6+ -> 4k
MK3: build cost 7.8k/21k, drain -40/-40. The Nth reactor of this mark on a planet produces max(80000*(0.2^(N-1)),8000) energy: 1 -> 80k; 2 ->16k; 3+ -> 8k.

A little correction on this, MK1 reactors cost 2/2, not 5/5.

Also, my calculations are showing that a MK3 reactor has better efficiency (2000 energy/metal) than a 2nd MK2 reactor (1600 energy/metal) Am I missing something or is this correct, because I've always heard that a 2nd MK2 is better than a MK3.

[Toranth]

Let me see if I did my math correctly:

Energy output of each mark reactor, by number present on a planet:
               1             2            3             4             5             6             7            8             9             10           11           12
Mk 1        5000       4000       3200        2560       2048       1638        1310       1048        838         671         536          500   ...
Mk 2        40k         24.4K      14.4K      8640       5184        4000   ...
Mk 3        80K        16k          8k   ...

Energy output per resource input (5/15/40, if you want to count m+c, divide these numbers by 2):
              1             2            3             4            5              6            7             8             9             10           11           12
Mk 1       1000       800         640         512         409          327        262          209         167          134         107         100
Mk 2       2666       1626       960         576         345          266
Mk 3       2000       400         200


As we quickly see, the Mk 2 lowest efficiency (266) is higher than the Mk 1 #7 and the Mk 3 #3 reactors.  This means that you will never build a seventh Mk 1 or a third Mk 3 on any planet.
 
Using the table above, the greedy algorithm of taking the most efficient reactor at any given time gives a build order of:
23212112113212222222....


For the multiple planets case, apply this build order to each planet, then build on the planet with the fewest total number of reactors.  For the multiple homeworld case, repeat each entry in the build order once for each homeworld (aka, 2HW: 22332211...).  Finally, to get your minimum reactor input costs for a given energy level, follow this build order until you surpass your energy desired level, then remove the last reactor built and replace it with the lowest mark reactor that will get you over the target energy level.

Build costs are highly outweighed by the ongoing resource costs (Build costs for Mk1, Mk2, and Mk3 are surpassed by operating costs in roughly 4, 5, and 6 minutes respectively).  Even so, the build costs (2.5k vs 9.6k vs 28.8k) vs the number to equal the highest level (Mk 3) reactor (16, 2, 1 ignoring efficiency) is greatly in favor of the Mk2.

[Cyborg]

I'm tickled pink that my energy complaint has finally evolved to the point where we are making a game out of how silly it is. I have a feeling it's not going to survive the next expansion as it is now. 

I don't really see the challenge in this, though. We already solved it many times. Now we are just talking about greedy solutions for the fun of it or something?

If you provide some input files, that would make the game equal, and we all should get the same answer. It would just be a matter of art, at that point.

[keith.lamothe]

I'm tickled pink that my energy complaint has finally evolved to the point where we are making a game out of how silly it is.

I was figuring it was only a matter of time before you provided a reminder that programming a computer to make change out of a dollar isn't exactly NP-Hard

[vortexion]

Let me see if I did my math correctly:

Energy output of each mark reactor, by number present on a planet:
               1             2            3             4             5             6             7            8             9             10           11           12
Mk 1        5000       4000       3200        2560       2048       1638        1310       1048        838         671         536          500   ...
Mk 2        40k         24.4K      14.4K      8640       5184        4000   ...
Mk 3        80K        16k          8k   ...

Energy output per resource input (5/15/40, if you want to count m+c, divide these numbers by 2):
              1             2            3             4            5              6            7             8             9             10           11           12
Mk 1       1000       800         640         512         409          327        262          209         167          134         107         100
Mk 2       2666       1626       960         576         345          266
Mk 3       2000       400         200
 

I'm getting some slightly different values. For a second MK2 reactor, the energy output I get is 24k (and 1600 efficiency), 24.4k would be 61% of the original. Perhaps that was just a typo, because the later values in that row look right. Also, MK1 reactors cost 2/2, not 5/5.

As we quickly see, the Mk 2 lowest efficiency (266) is higher than the Mk 1 #7 and the Mk 3 #3 reactors.  This means that you will never build a seventh Mk 1 or a third Mk 3 on any planet.

Not true, if you need only 500 more energy, your best bet is to build a MK1 reactor, not a higher one.

[Diazo]

Bah, throw my great big wall of text of with the wrong values will you? 

But my earlier comment about always wanting the most efficient reactor stands. Okay, I only need 10k more energy right now, but I'm going to need more in a few minutes.

I'm not going to mess around trying to calculate out the most efficient energy production when it's only worth maybe +/- 10 to my resource flow.

Cap out at 6 Mk I, 2 Mk III, build more Mk II.

D.

[TechSY730]

OK, while many of the algorithms above don't quite take into account all of the definitions of "best" configuration as given in the problem, they should be easily modifiable to do so. (Basically, once remaining energy needed to be produced gets to around 2*Mk. III energy production, you need to start looking at other things rather than most efficient first or else risk getting a slightly less optimal configuration)

And all of the algorithms above are greedy, and large parts of them are "naively" greedy (aka, can determine the next step by a single factor lookup)

As such, I am canceling this contest, and will post a "harder" variant of it in not too much longer.

[TechSY730]

To many of you pointing out that my definition of "best" configuration or the inputs given (like target energy to reach, instead of just I need more energy) are not exactly practical for an in game determination, I know. This was not about an practical game energy mangement algorithm, but rather a fun little variant on the change problem.
Sadly, it turned out that the values AI war uses currently leads to a degenerate, greedy solution.

[TechSY730]

I'm tickled pink that my energy complaint has finally evolved to the point where we are making a game out of how silly it is.

I was figuring it was only a matter of time before you provided a reminder that programming a computer to make change out of a dollar isn't exactly NP-Hard

Well, while the change problem isn't hard, in the general case, the greedy algorithm does not work.
Sure, it works for the denominations used in US currency (.01, .05, .10, .25, 1.00, 5.00, 10.00, 20.00, and 100.00), but it will not work in all sets of denominations. (Take for example, say the denominations are .01, .06, and .07, and you have 12 cents in change to give. The greedy algorithm, biggest denomination first, will give 1*.07, 5 * .01, but that is not optimal. The optimal is 2*.06)

Similarly, the most optimal energy configuration is not always "greedily solvable", but it is for some sets of energy reactor definitions. Sadly, the sets of values that AI war uses has been shown to be similarly "greedily" solvable like the US denominations are for the change problem.

The revised versions of this problem will give the definitions of each Mk. level in the input file, so no such assumptions about the input or pre-observations like 2 Mk. II reactors on the same planet is more energy/resource efficient than a Mk. II + Mk. I. There is no telling how to "prune" the state space ahead of time.

[Diazo]

Hmmm.

I thought my solution covered that case (your coin example) but I'll wait until you post your next version before I spend any more time on it, want to get a good chunk of time in on updating the wiki tonight.

D.

[TechSY730]

Hmmm.

I thought my solution covered that case (your coin example) but I'll wait until you post your next version before I spend any more time on it, want to get a good chunk of time in on updating the wiki tonight.

D.

Your algorithm is very close to being able to find the optimum in the general case. Just a little adaptation is needed.
I think (but I am not sure) that your algorithm may fail to meet something like the 3rd or 4th tie breaker criteria, but its a very good algorithm, and still is linear time (especially if you precompute some extra lookup tables ahead of time for when you need to search for more than just energy/resource-rate efficiency)

[rickynumber24]

Techsy, I really think you need to think a little more closely about one other aspect of the challenge you are providing.  In the arbitrary case, I have a strong feeling this is equivalent to the knapsack problem.  (Actually, I suppose, based on the terms Wikipedia provides, this is more precisely the bin packing problem  Once you manage to get all of the greedy loopholes out of the challenge, you're going to end up with two choices: nonpolynomial (generally exponential) precise solutions and polynomial-time approximations.  Based on your previous comments, you don't seem to be willing to accept approximations, though.

If you are going to score things, I think it would be interesting to score them in both time and space, though.

[Hearteater]

This sounds like it could use perl golf scoring: Fewest characters in the solution wins!

[TechSY730]

Techsy, I really think you need to think a little more closely about one other aspect of the challenge you are providing.  In the arbitrary case, I have a strong feeling this is equivalent to the knapsack problem.  (Actually, I suppose, based on the terms Wikipedia provides, this is more precisely the bin packing problem  Once you manage to get all of the greedy loopholes out of the challenge, you're going to end up with two choices: nonpolynomial (generally exponential) precise solutions and polynomial-time approximations.  Based on your previous comments, you don't seem to be willing to accept approximations, though.

If you are going to score things, I think it would be interesting to score them in both time and space, though.

Actually, you are right. The general form of the problem I posted (having arbitrary reactor mark definitions) is reducible to the Cutting stock problem. Since in this case, we have to stick to integers (we cannot build, say, half a reactor), one of the sub problems turns into a linear integer programming problem, which is known to be NP-hard.

However, some sets of "unit definitions" lead to some simplifying observations, allowing us to severely prune the state space. Sometimes enough to take it out of NP-hard space for inputs using such definitions.
AI war's current reactor definitions are one such set of definitions. As several people have pointed out, there are many observations (like 2 Mk. II reactors on the same planet is more energy/resource efficient than a Mk. II + Mk. I) you can make in this specific case that prunes the state space enough to actually make this linearly solvable.

Sort of interesting how the energy system is supposed to lead to a very difficult to figure out puzzle, but the devs managed to choose a set of values for the reactor definitions with the right set of properties to allow for a trivially easy solutions.

So yea, the revised version is not coming. I don't really like giving NP-hard problems as programming challenges.