Better, Simpler Programming Contest

Saber Cherry · #1 March 3rd, 2004, 03:46 AM

Quote:

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 · #2 March 3rd, 2004, 04:43 AM

Quote:

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 · #3 March 3rd, 2004, 05:03 AM

(double)

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

Saber Cherry · #4 March 3rd, 2004, 05:03 AM

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:

Quote:

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_- · #5 March 3rd, 2004, 05:13 AM

Quote:

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 · #6 March 3rd, 2004, 05:19 AM

Quote:

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.

Saber Cherry · #7 March 3rd, 2004, 05:22 AM

Quote:

Originally posted by Leif_-:

quote:
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?

Hmmm.

It looks like a multidimensional variant of the unbounded knapsack problem. Adding the combined arms bonus would change that, though.