Better, Simpler Programming Contest

[atul]

Originally posted by Saber Cherry:
Sorry, I was not very clear...

quote:

---

me:
The program will be graded according to how many resources are used (% of total for each type) and how fast it runs.

---

Oops, sorry, how stupid of me, missing that part in brackets. Must be the late hour... Anyway, that makes sense.

Just occured to me, wouldn't it be reasonable to be able to assign some arbitrary value to different units, as in 'this is better than that'? For I get the feeling that if all units are equal and only gold/res/holy is taken into account the resulting armies would be very much like the current AI likes (loads of LI) if you give normal dom-values as input (higher gold than resources). Like final goal = Max(units' values - resources lost), your original proposition would be where all units have value of zero. Or maybe that would just be unnecessary complication. Things are good to be kept simple.

Originally posted by Saber Cherry:
in other words, don't cheat by finding some linear-combination optimizer.

Don't worry, didn't cross my mind. Anyway much that you wrote was total greek to me, as I'm not too much into computers. Currently being schooled to be one of those who just use programs like this competition's results without caring how it technically works. Ignorance is a bliss.

Just asking questions out of general interest and occasional boredom.

[Saber Cherry]

Originally posted by atul:
Just occured to me, wouldn't it be reasonable to be able to assign some arbitrary value to different units, as in 'this is better than that'?

Good idea. My problem is this:

Only one person has voted. What does this mean? Is the problem not interesting enough, or already too complex?

At any rate, giving each unit a "value" and changing the problem definition to maximize "value produced" instead of minimizing "resources wasted", or do some combination, would be interesting. And probably more useful.

Anyone else have a thought on that subject?

[Torvak]

Why make it a contest and not some kind of board project. Call it board forge or whatever and i think more people will participate.

[Saber Cherry]

Originally posted by Torvak:
Why make it a contest and not some kind of board project. Call it board forge or whatever and i think more people will participate.

Hmmm. What do you mean by "Board Project"? A single conglomerate effort of everyone who wants to participate? The main problems in that case are that only one language could be used, and disagreements might arise, etc.

Is the "Contest" nature turning people off?

[Saber Cherry]

MORE GENERIC CONTEST RESTATEMENT

You have 3 resource types (gold, res, and holy), and some number (n) of units. Each unit and resource has a specified value.

The goal: Make a production queue that maximizes value, within resource constraints.


Example:

Your province has the following resources:
Gold 120, Res 88, Holy 4

This is specified in the input file like this:

code:

---

resourcetypes=3

resource=gold quantity=120 value=-1

resource=res  quantity=88  value=1

resource=holy quantity=4   value=10

---

The province can produce 4 types of units, named a, b, c, and d. They are specified in the input file like this:

code:

---

unittypes=4

unitname=a gold=5  res=3  holy=0 value=5

unitname=b gold=7  res=12 holy=0 value=8

unitname=c gold=12 res=2  holy=1 value=17

unitname=d gold=22 res=21 holy=0 value=15

---

The program will find a combination of a, b, c, and d that maximizes value. In this example, you get 5 points for building each "a" and 17 points for building each "c". You also get 1 point for using each "res", 10 points for using each "holy", and lose a point for using each "gold".

In other words, your total score, for this input, would be:

5*(#a built)+8*(#b built)+17*(#c built)+15*(#d built)-1*(#gold used)+1*(#res used)+10*(#holy used)

Sample Output:

code:

---

a=3, b=1, c=4, d=1

gold=92, res=50, holy=4

value=104

---

(these resource numbers indicate the number used)

value=15+8+68+15-92+50+40=104, unless I made an error.

The score would then be calculated according to the equation, with a higher score better. The value of resources and units would, thus, be arbitrary, so that the algorithm could be used to optimize the queue for any resource-using game!

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

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