Better, Simpler Programming Contest

[Saber Cherry]

Preface:

To date, 3 people like the old contest suggestion (not very many), but quite a lot of people said they were interested in formulating the contest (which does not have to be related to, or useful to, Dominions).

If you have an idea for a programming contest that DOES NOT involve hacking, decompiling, or reverse-engineering game files, please post it! Something SIMPLE, but not trivial, would be ideal. For example, a file that generates random leader names, or that predicts which of two units would win WITHOUT doing any combat simulation (just by looking at the stats), would be nice.

NEW CONTEST CONCEPT

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:49: Message edited by: Saber Cherry ]

[Saber Cherry]

Note that this problem seems trivial, but is actually NP, meaning it does not have a known good solution.

[Pocus]

thats depend of the number of differing units you propose. I would probably use a brute force search to find the solution, if you dont throw at us the 1080 units (~) of dom2...

[Saber Cherry]

Originally posted by Pocus:
thats depend of the number of differing units you propose. I would probably use a brute force search to find the solution, if you dont throw at us the 1080 units (~) of dom2...

No, it would be more like a national lineup=) A typical problem might have 2 to 16 units, and no more than 500 gold, 300 resources, and 10 holy. It would take WAY too much work to write the costs for 1080 units!

Probably, there will be about 8 problems, ranging in difficulty from 2 units and ~50/50/0 gold/res/holy up to 16 units and ~500/300/10 gold/res/holy. I expect any solver would solve the first, and break (or take too long) before getting to the Last=)

Note that it is common to use a greedy algorithm to solve NP problems. These give non-ideal (but correct) answers very quickly.

[ March 02, 2004, 20:15: Message edited by: Saber Cherry ]

[atul]

Originally posted by Saber Cherry:
You have 3 resource types (gold, resources, and holy, abbreviated gcost, rcost, and hcost), and some number (n) of units. We will assume all the units are of value corresponding to their cost.

The goal: Make a production queue that minimizes wasted resources!

This assumes all the different kinds of resources have same value when wasted, and no bonus/penalty is put due different troop composition, just by wasted resources? Sorry, too much school work regarding problems like this, it just bugs to see all the variables having same weight of '1'. That is, if I understood the above correctly.

Haven't followed much these programming contest threads, what are the limits as to programming? Has to be stand-alone application? Specific language? For you know, I think M$ Excel has built-in function to do specifically this kind of optimization (I know, wouldn't apply such to the contest).

Not sure, I have feeling there was some systematic and elegant way of doing this with matrix operations or such of some sort. Should look some old school hand-outs to see for sure.

[Saber Cherry]

And Lastly:

Unless anyone can think of an objection, teams and devs will be allowed (encouraged) to participate. Any team would have to have a captain through whom all communication and file transfers would be handled.

[PhilD]

Originally posted by Saber Cherry:
Note that this problem seems trivial, but is actually NP, meaning it does not have a known good solution.

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

[Saber Cherry]

Originally posted by atul:
This assumes all the different kinds of resources have same value when wasted, and no bonus/penalty is put due different troop composition, just by wasted resources? Sorry, too much school work regarding problems like this, it just bugs to see all the variables having same weight of '1'. That is, if I understood the above correctly.

Sorry, I was not very clear...

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

I meant to say that the ideal would be to minimize the wasted percentage of each resource. So if you had holy=4 and gold=100, wasting 1 point of holy would be a 25% waste, and wasting one gold would only be a 1% waste. It would be possible to specify a problem in which the three resources had arbitrary values... but in the interest of keeping things simple, it seems that giving each resource a value of (100/total) would be OK. What do you think? Would you prefer arbitrary values?

Haven't followed much these programming contest threads, what are the limits as to programming? Has to be stand-alone application? Specific language? For you know, I think M$ Excel has built-in function to do specifically this kind of optimization (I know, wouldn't apply such to the contest).

Not sure, I have feeling there was some systematic and elegant way of doing this with matrix operations or such of some sort. Should look some old school hand-outs to see for sure.

There is no easy way to solve this problem quickly. The limits are this:

1) You can use any language, but you must provide the source code for your solution, without any precompiled black boxes. Thus, a prebuilt Excel function would not work.
2) Scripting Languages and spreadsheets are fine if you put in the algorithms yourself.
3) Library functions are fine for simple things like sorting, storing data, hashing, reading files, comparing strings, and such. All code for solving the actual problem should be your own: in other words, don't cheat by finding some linear-combination optimizer. This is pretty subjective; it's a contest for fun, not for any cash prize=)

[ March 02, 2004, 20:43: Message edited by: Saber Cherry ]

[Norfleet]

Well, ideally, it's to your benefit to prioritize maximization of resources and holy. Unused GOLD is not "wasted", as gold accumulates in your treasury, and has non-troop-building uses.

[Saber Cherry]

Originally posted by Norfleet:
Well, ideally, it's to your benefit to prioritize maximization of resources and holy. Unused GOLD is not "wasted", as gold accumulates in your treasury, and has non-troop-building uses.

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.