Re: Better, Simpler Programming Contest
 

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

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

Just asking questions out of general interest and occasional boredom.

Re: Better, Simpler Programming Contest
 

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

Re: Better, Simpler Programming Contest
 

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.

Re: Better, Simpler Programming Contest
 

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

Re: Better, Simpler Programming Contest
 

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:

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

Re: Better, Simpler Programming Contest
 

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

Re: Better, Simpler Programming Contest
 

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?

Re: Better, Simpler Programming Contest
 

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

Re: Better, Simpler Programming Contest
 

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

Re: Better, Simpler Programming Contest
 

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