Better, Simpler Programming Contest

[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 ]

[Leif_-]

Originally posted by mlepinski:

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

Well, isn't it just a variant of the knapsack problem, which is known to be NP-complete?

[Saber Cherry]

Originally posted by mlepinski:
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 (...) 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.

That is, indeed, hard to say. There's a way to make it more difficult, BTW, that I was pondering... a "Combined Arms" bonus. The value of a unit would be based on the number you build, so that (for example) the first of any unit was worth 2x the normal value, the second was worth 3/2x the normal value, the third was worth 4/3 of the normal value, and so forth. Not only would this be good for an AI (which would not always produce the same 2 or 3 units), but I get the feeling that it would ensure the problem was NP and not P.