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.