Better, Simpler Programming Contest

[Norfleet]

Originally posted by Saber Cherry:
I disagree. I try to end my turns having used all my gold. Carrying gold over does not earn interest, and unless you are saving for something, going many turns in a row without spending all your gold will generally put you at a competitive disadvantage. If all units were 0 resources and 0 holy, an ideal solution would spend all the gold, so you could have troops - not save all the gold and build nothing.

Carrying over RESOURCES doesn't earn interest either, and don't even get to keep the resources! While obviously, there's a point at which you are clearly underspending to the a level where you're not competitive, if you're fully utilizing your resource output to create an effective army even without draining all of your gold, there's nothing wrong with this: Keeping a gold reserve is actually beneficial, since in the event of an emergency, you'll have resources you can draw on: If you've already spent all your gold on troops, you can't hire mercenaries(which can appear anywhere in your empire, making them a very good emergency response force), build a lab or temple, build a fort, etc.

[Graeme Dice]

How do you want us to account for the extra three or so resources that are left at the end of each purchase. Should we apply them to the next turn as happens in game?

[Saber Cherry]

Originally posted by Graeme Dice:
How do you want us to account for the extra three or so resources that are left at the end of each purchase. Should we apply them to the next turn as happens in game?

To clarify, the contest changed from the first post to the redefinition, at Atul's suggestion.

Just optimize for a single turn, and do not exceed the limit for any resource - nothing carries over. However, depending on the values assigned to the resources, you get points or negative points for the amount of each resource you use - so the specific amount of each resource you use is still quite important.

[Saber Cherry]

Originally posted by Norfleet:
Carrying over RESOURCES doesn't earn interest either, and don't even get to keep the resources! While obviously, there's a point at which you are clearly underspending to the a level where you're not competitive, if you're fully utilizing your resource output to create an effective army even without draining all of your gold, there's nothing wrong with this: Keeping a gold reserve is actually beneficial, since in the event of an emergency, you'll have resources you can draw on: If you've already spent all your gold on troops, you can't hire mercenaries(which can appear anywhere in your empire, making them a very good emergency response force), build a lab or temple, build a fort, etc.

Yeah. I changed my mind=) The original "Use all resources" was too simplistic, so now you can assign a value to each resource and each unit. And since gold is intrinsically valuable and storable, while the others are not, it would be assigned a negative value (you are penalized for using it, but you still have to).

[mlepinski]

Originally posted by PhilD:
Let's nitpick a little: just saying the problem is NP does not mean no good solution is known. Every P problem is also NP. What you're thinking of, most likely, is NP-complete.

And yes, I do teach CS, rather on the theoretical side

Thanks Phil, this was also my first reaction when I read Saber Cherry's original post. (I have also taught thoery of computer science).

Which raises the question: Is the problem that Saber Cherry posed NP-Complete?

It's clear to me that the problem is NP-Complete if you allow an arbitrary number of resource types (instead of only 3 - gold, resources and holy) or if you restrict so that you are limited to building at most one copy of each unit in a single turn.(which makes no sense in the context of Dominions where I often want to build many lowbowmen each turn). (Note: In either of these cases there is a simple reduction to subset sum.) However, it is unclear to me whether the specific Dominions-inspired problem (with exactly three resources and the ability to buy many copies of the same unit) is NP-Complete.

- Matt Lepinski :->

[ March 03, 2004, 02:45: Message edited by: mlepinski ]

[Saber Cherry]

(double)

[ March 03, 2004, 03:03: Message edited by: Saber Cherry ]

[Saber Cherry]

I get confused about the difference between NP-Hard and NP-Complete. But generally, minSAT-type problems are NP-hard.

Anyway, I did a google search to clear up my confusion...

http://en.wikipedia.org/wiki/Computa...plexity_theory

I sort of recall that "NP-Complete" problems have to have a yes or no answer, and NP-Hard problems can have any answer. So a minimization/maximization that could be rephrased as NP-complete by asking "Is there a solution that scores above 100?" would itself be NP-hard.

It confuses me since I've been told contradictory facts:

NP-C must have a yes or no answer.
NP-H can have any answer.
NP-H is a subset of NP-C.

So I was trying to avoid confusion by saying "NP", but that failed=)

Incidentally, according to that site, Class P is the set of problems solvable in polynomial time, and Class NP is a set of problems that are probably not in Class P. To quote it:

In complexity theory, the NP-complete problems are the hardest problems in NP, in the sense that they are the ones most likely not to be in P.

Thus... I think it is correct to call an NP-C problem "NP". But then, it's just some random internet site

[ March 03, 2004, 03:05: Message edited by: Saber Cherry ]