Better, Simpler Programming Contest
 

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:

</font><blockquote><font size="1" face="sans-serif, arial, verdana">code:</font><hr /><pre style="font-size:x-small; font-family: monospace;">resourcetypes=3
resource=gold quantity=120 value=-1
resource=res quantity=88 value=1
resource=holy quantity=4 value=10</pre><hr /></blockquote><font size="2" face="sans-serif, arial, verdana">The province can produce 4 types of units, named a, b, c, and d. They are specified in the input file like this:

</font><blockquote><font size="1" face="sans-serif, arial, verdana">code:</font><hr /><pre style="font-size:x-small; font-family: monospace;">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</pre><hr /></blockquote><font size="2" face="sans-serif, arial, verdana">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:
</font><blockquote><font size="1" face="sans-serif, arial, verdana">code:</font><hr /><pre style="font-size:x-small; font-family: monospace;">a=3, b=1, c=4, d=1
gold=92, res=50, holy=4
value=104</pre><hr /></blockquote><font size="2" face="sans-serif, arial, verdana">(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 ]

Re: Better, Simpler Programming Contest
 

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

Re: Better, Simpler Programming Contest
 

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...

Re: Better, Simpler Programming Contest
 

<font size="2" face="sans-serif, arial, verdana">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! http://forum.shrapnelgames.com/images/icons/icon12.gif

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 ]

Re: Better, Simpler Programming Contest
 

<font size="2" face="sans-serif, arial, verdana">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'. http://forum.shrapnelgames.com/images/icons/tongue.gif 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.

Re: Better, Simpler Programming Contest
 

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.

Re: Better, Simpler Programming Contest
 

<font size="2" face="sans-serif, arial, verdana">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 http://forum.shrapnelgames.com/images/icons/icon7.gif

Re: Better, Simpler Programming Contest
 

<font size="2" face="sans-serif, arial, verdana">Sorry, I was not very clear...

<font size="2" face="sans-serif, arial, verdana">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?

<font size="2" face="sans-serif, arial, verdana">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 ]

Re: Better, Simpler Programming Contest
 

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.

Re: Better, Simpler Programming Contest
 

<font size="2" face="sans-serif, arial, verdana">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.