Better, Simpler Programming Contest [Archive]

Saber Cherry

March 2nd, 2004, 09:41 PM

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:

<blockquote>code:<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>The province can produce 4 types of units, named a, b, c, and d. They are specified in the input file like this:

<blockquote>code:<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>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:
<blockquote>code:<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>(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

March 2nd, 2004, 09:44 PM

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

Pocus

March 2nd, 2004, 09:55 PM

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

March 2nd, 2004, 09:59 PM

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

atul

March 2nd, 2004, 10:28 PM

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

Saber Cherry

March 2nd, 2004, 10:29 PM

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

March 2nd, 2004, 10:32 PM

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 http://forum.shrapnelgames.com/images/icons/icon7.gif

Saber Cherry

March 2nd, 2004, 10:42 PM

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'. http://forum.shrapnelgames.com/images/icons/tongue.gif 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

March 2nd, 2004, 10:44 PM

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

March 2nd, 2004, 10:51 PM

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.

atul

March 2nd, 2004, 11:28 PM

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

<blockquote>quote:<hr />me:
The program will be graded according to how many resources are used (% of total for each type) and how fast it runs.
<hr /></blockquote>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. http://forum.shrapnelgames.com/images/icons/icon10.gif

Just asking questions out of general interest and occasional boredom.

Saber Cherry

March 2nd, 2004, 11:34 PM

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

March 2nd, 2004, 11:42 PM

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

March 3rd, 2004, 12:13 AM

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

March 3rd, 2004, 12:31 AM

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:

<blockquote>code:<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>The province can produce 4 types of units, named a, b, c, and d. They are specified in the input file like this:

<blockquote>code:<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>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:
<blockquote>code:<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>(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

March 3rd, 2004, 03:10 AM

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

March 3rd, 2004, 03:30 AM

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

March 3rd, 2004, 03:44 AM

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

March 3rd, 2004, 03:46 AM

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

March 3rd, 2004, 04:43 AM

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 http://forum.shrapnelgames.com/images/icons/icon7.gif 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 ]

Saber Cherry

March 3rd, 2004, 05:03 AM

(double)

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

Saber Cherry

March 3rd, 2004, 05:03 AM

I get confused about the difference between NP-Hard and NP-Complete. But generally, minSAT-type problems are NP-hard.

Anyway, I did a google search to clear up my confusion...

http://en.wikipedia.org/wiki/Computational_complexity_theory

I sort of recall that "NP-Complete" problems have to have a yes or no answer, and NP-Hard problems can have any answer. So a minimization/maximization that could be rephrased as NP-complete by asking "Is there a solution that scores above 100?" would itself be NP-hard.

It confuses me since I've been told contradictory facts:

NP-C must have a yes or no answer.
NP-H can have any answer.
NP-H is a subset of NP-C.

So I was trying to avoid confusion by saying "NP", but that failed=)

Incidentally, according to that site, Class P is the set of problems solvable in polynomial time, and Class NP is a set of problems that are probably not in Class P. To quote it:

In complexity theory, the NP-complete problems are the hardest problems in NP, in the sense that they are the ones most likely not to be in P.Thus... I think it is correct to call an NP-C problem "NP". But then, it's just some random internet site http://forum.shrapnelgames.com/images/icons/icon10.gif

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

Leif_-

March 3rd, 2004, 05:13 AM

Originally posted by mlepinski:

Which raises the question: Is the problem that Saber Cherry posed NP-Complete?
Well, isn't it just a variant of the knapsack problem, which is known to be NP-complete?

Saber Cherry

March 3rd, 2004, 05:19 AM

Originally posted by mlepinski:
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 (...) 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.That is, indeed, hard to say. There's a way to make it more difficult, BTW, that I was pondering... a "Combined Arms" bonus. The value of a unit would be based on the number you build, so that (for example) the first of any unit was worth 2x the normal value, the second was worth 3/2x the normal value, the third was worth 4/3 of the normal value, and so forth. Not only would this be good for an AI (which would not always produce the same 2 or 3 units), but I get the feeling that it would ensure the problem was NP and not P.

Saber Cherry

March 3rd, 2004, 05:22 AM

Originally posted by Leif_-:
<blockquote>quote:<hr />Originally posted by mlepinski:

Which raises the question: Is the problem that Saber Cherry posed NP-Complete?
Well, isn't it just a variant of the knapsack problem, which is known to be NP-complete? <hr /></blockquote>Hmmm.

It looks like a multidimensional variant of the unbounded knapsack problem (http://www.nist.gov/dads/HTML/unboundedKnapsack.html). Adding the combined arms bonus would change that, though.

mlepinski

March 3rd, 2004, 06:02 AM

Originally posted by Saber Cherry:

It confuses me since I've been told contradictory facts:

NP-C must have a yes or no answer.
NP-H can have any answer.
NP-H is a subset of NP-C.

So I was trying to avoid confusion by saying "NP", but that failed=)

Incidentally, according to that site, Class P is the set of problems solvable in polynomial time, and Class NP is a set of problems that are probably not in Class P. To quote it:

<blockquote>quote:<hr />In complexity theory, the NP-complete problems are the hardest problems in NP, in the sense that they are the ones most likely not to be in P.Thus... I think it is correct to call an NP-C problem "NP". But then, it's just some random internet site http://forum.shrapnelgames.com/images/icons/icon10.gif <hr /></blockquote>I apologize for diverting this thread into a discussion of computational complexity, but I'd like to remind everyone that Phil started it. :->

In any case, the wording on the website you reference is a bit confusing, so hopefully this will help clear up the confusion.

P is the class of (decision) problems solvable in polynomial time by a deterministic (i.e., ordinary) computer.

NP is the class of (decision) problems that are solvable in polynomial time by a non-deterministic computer. (The best way to think about NP is as problems who's answer can be checked in polynomial time.)

Every problem in P is also in NP but it is widely believed that there are problems in NP that are not in P.

NP-Complete are the hardest problems in NP. In particular, if an efficient (deterministic polynomial time) solution were found to any NP-Complete problem, then P = NP.

Every NP-Complete problem is in NP. Therefore, every NP-Complete problem is a decision (Yes/No) problem.

A Problem is NP-Hard if it is at least as hard as every problem in NP. That is, a problem is NP-Hard if solving said problem allows one to solve every problem in NP. (If there is an efficient solution to any NP-Hard problem then P=NP).

NP-Hard problems can be decision problems but they don't have to be. Every NP-Complete problem is also NP-Hard.

So technically, the optimization problem that Saber Cherry proposed can't be NP-Complete because it's not a decision problem. However, one can easily transform any optimization problem into an equivilant decision problem. For instance, instead of asking to maximize value, you can ask, "Is it possible to achieve a value of k?" (which is a decision problem). This is equivalent to the optimization problem because if you had an efficient program to solve the decision problem, you could run it many times (using a binary search) to find the optimal value of k. That is, (assume M is some big number larger than the maximum possible value) you could first run the program to find out if it's possible to achieve M/2. If it is possible to achieve M/2 then you run the program for 3*M/4. If 3*M/4 isn't achievable you would try 5*M/8. (In the worst case this requires running the decision program log(M) times which is polynomial in the size of your problem instance).

Hopefully the above explaination made some things more clear. (I apologize if my earlier post caused some confusion, what I really meant was "Is the decision Version of the optimization problem NP-Complete").

Also, thanks a lot for the unbounded Knapsack link. (I'm not familiar with the proof that unbounded Knapsack is NP-Hard, but I will undoubtably spend time tossing and turning in my bed tonight trying to figure out why this true <grin>).

- Matt Lepinski :->

LaFollet

March 3rd, 2004, 07:37 AM

Ummm.... And here I thought this was a thread about a simple programming problem.... and yet I don't have a clue about half the stuff being said. :S

Oh well, I guess I'll just get back to solving the problem... http://forum.shrapnelgames.com/images/icons/icon10.gif http://forum.shrapnelgames.com/images/icons/icon10.gif http://forum.shrapnelgames.com/images/icons/icon10.gif

EDIT:
I think you're number in the example for Holy is way off... I've never come accross any province with 120 holy...

[ March 03, 2004, 06:02: Message edited by: LaFollet ]

Saber Cherry

March 3rd, 2004, 08:28 AM

Originally posted by LaFollet:
Ummm.... And here I thought this was a thread about a simple programming problem.... and yet I don't have a clue about half the stuff being said. :S

Oh well, I guess I'll just get back to solving the problem... http://forum.shrapnelgames.com/images/icons/icon10.gif http://forum.shrapnelgames.com/images/icons/icon10.gif http://forum.shrapnelgames.com/images/icons/icon10.gif

EDIT:
I think you're number in the example for Holy is way off... I've never come accross any province with 120 holy... Ooops! Thanks for pointing that out, I corrected it. Holy was supposed to be "4" http://forum.shrapnelgames.com/images/icons/blush.gif

And - Yay! Someone is working on the problem http://forum.shrapnelgames.com/images/icons/icon10.gif http://forum.shrapnelgames.com/images/icons/icon10.gif

...however, the number of votes is still listed as 2 for me, both people who won't participate... http://forum.shrapnelgames.com/images/icons/confused.gif

LaFollet

March 3rd, 2004, 09:13 AM

Well this is my approach so far:
1) Load both the resource info and unit info from text files.
2) Sort the units based on their "value"
3) Start using up all the resources that I can to make as many of the highest valued unit that I can. (With the test this is limited by Holy, as it usually is in game.)
4) Use up as much other resources with the next unit with the next highest value.
5) Keep doing this until resources are used up.

Anyone have any thoughts? Comments? Suggestions? http://forum.shrapnelgames.com/images/icons/icon10.gif

Leif_-

March 3rd, 2004, 09:55 AM

Originally posted by LaFollet:
Well this is my approach so far:
1) Load both the resource info and unit info from text files.
2) Sort the units based on their "value"
3) Start using up all the resources that I can to make as many of the highest valued unit that I can. (With the test this is limited by Holy, as it usually is in game.)
4) Use up as much other resources with the next unit with the next highest value.
5) Keep doing this until resources are used up.

Anyone have any thoughts? Comments? Suggestions? http://forum.shrapnelgames.com/images/icons/icon10.gif This greedy approach will give you quite good solutions to the problem, but not necessarily optimal ones. The quickest way to find an optimal solution for a handful of units is probably a brute-force search; for slightly larger problems I suppose that stochastic search techniques such as genetic algorithms or simulated annealing will yield decent results quickly.

Norfleet

March 3rd, 2004, 10:07 AM

Originally posted by Saber Cherry:
BTW, that I was pondering... a "Combined Arms" bonus. The value of a unit would be based on the number you build, so that (for example) the first of any unit was worth 2x the normal value, the second was worth 3/2x the normal value, the third was worth 4/3 of the normal value, and so forth. Not only would this be good for an AI (which would not always produce the same 2 or 3 units), but I get the feeling that it would ensure the problem was NP and not P. Well, if you were to offer a combined arms bonus, you should also offer a massing bonus. A single archer is rather useless. Of course, to evaluate this, would then require a longer-term view than single-turn production: Now you're looking at a puzzle of multi-turn strategic production.

Naturally, if somebody were to actually create a good solution to this problem, he'd have permanently solved the solution of bad unit composition in AIs for every single strategy game in existence!

Torvak

March 3rd, 2004, 10:11 AM

I'd also point out that the value of holy troops depends very much on the pretender. With a rainbow pretender i don't care much about them.

LaFollet

March 3rd, 2004, 04:24 PM

I have to ask, how did you come up with the "value" for the units? Are you just pulling numbers out of nowhere, or are these bassed of of acctual units in game?

And wouldn't it be more beneficial if the code made sure that a percentage was archers, or mounted, or footsoldiers?

I know there was mention of a combined arms approach and how that would increase the value of units over others, to attempt to convince the code to use different types, but why not just make it take a certain percentage of each type?

mivayan

March 3rd, 2004, 05:24 PM

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. Troops cost upkeep however, so you can save money by building troops later if you dont really need them now.

Saber Cherry

March 3rd, 2004, 06:00 PM

Originally posted by Torvak:
I'd also point out that the value of holy troops depends very much on the pretender. With a rainbow pretender i don't care much about them. Yep. That's why the values of the units are variable - once the algorithm is designed, the AI can assign each unit a value, and the algorithm will optimize for those values. So if the AI has Water-9 Fire-9, it can give the "holy" resource a high value (or give holy units a high value), while a pretender with no bless effects could give "holy" a value of zero. The same algorithm would work each time!

Originally posted by LaFollet:
I have to ask, how did you come up with the "value" for the units? Are you just pulling numbers out of nowhere, or are these bassed of of acctual units in game?There are 5 possibilities here. It is not a "solved" problem yet, but rather "the other half" of this problem.

1) People could look at each of the 1080 units (or just each of the units in a national lineup) and assign them fixed values. Then, when the game runs, a "Heavy Cavalry" always has a value of, say, 51. This would take a bit of human work and be subjective.
2) The game could dynamically adjust values of units by tracking them. In other words, every unit could start a game with a value based on their resource cost, or based on (1) above. But each turn, that cost would be adjusted by the success rate: If all the Heavy Cavalry units had (overall) 35 deaths and 76 kills, then heavy cavalry would be valued at 76/35, or 2.17. Whereas if Militias had overall 346 deaths and 13 kills, they would be given a value of 13/346=.037. That way, units that are useful in the current strategic climate would be favored.
3) Numbers could come from the Combat Simulator. Unfortunately, that only works for melee units, and ignores some factors like trample and routing.
4) Somebody could develop an algorithm that assigns a value to a unit based on its stats and special abilities. This would be objective, but imperfect. Probably the best bet, though.
5) I'm sure there are others=)

Originally posted by LaFollet:
And wouldn't it be more beneficial if the code made sure that a percentage was archers, or mounted, or footsoldiers?

I know there was mention of a combined arms approach and how that would increase the value of units over others, to attempt to convince the code to use different types, but why not just make it take a certain percentage of each type?No. This problem is intended to be perfectly generic, objective, and pure. That way, it can apply to any game regardless of the game's specifics, and solves a clearly-defined problem.

What you suggest can be done within the existing problem statement: Create 3 new resources, "bows", "saddles", and "boots", and give archers, cavalry, and soldiers a cost of 1 in that respective Category. Then give those resources a very high value, and give the province a certain number of each (maybe 2 bows, 4 boots, and 1 saddle) so that the algorithm will attempt to produce a minimum of 2 archers, 4 soldiers, and 1 cavalry each turn. It is best to keep the overall problem and algorithm as simple as possible and achieve complex results by adding parameters to the specific case.

Originally posted by Norfleet:
Well, if you were to offer a combined arms bonus, you should also offer a massing bonus. A single archer is rather useless. Of course, to evaluate this, would then require a longer-term view than single-turn production: Now you're looking at a puzzle of multi-turn strategic production.Any army produced in a single turn is virtually useless. There are ways to make the solver more powerful, but only at the expense of complexity in both the algorithm and description... Perhaps, if this contest has a good response, a 2nd generation contest could be proposed, with additional factors considered.

Originally posted by Norfleet:
Naturally, if somebody were to actually create a good solution to this problem, he'd have permanently solved the solution of bad unit composition in AIs for every single strategy game in existence!Well, that's the goal=) Wouldn't it be neat to make a program / algorithm useful to all queued-production strategy games in existance?

LaFollet

March 3rd, 2004, 06:35 PM

Originally posted by Saber Cherry:
<blockquote>quote:<hr />Originally posted by LaFollet:
I have to ask, how did you come up with the "value" for the units? Are you just pulling numbers out of nowhere, or are these bassed of of acctual units in game?There are 5 possibilities here. It is not a "solved" problem yet, but rather "the other half" of this problem.

1) People could look at each of the 1080 units (or just each of the units in a national lineup) and assign them fixed values. Then, when the game runs, a "Heavy Cavalry" always has a value of, say, 51. This would take a bit of human work and be subjective.
2) The game could dynamically adjust values of units by tracking them. In other words, every unit could start a game with a value based on their resource cost, or based on (1) above. But each turn, that cost would be adjusted by the success rate: If all the Heavy Cavalry units had (overall) 35 deaths and 76 kills, then heavy cavalry would be valued at 76/35, or 2.17. Whereas if Militias had overall 346 deaths and 13 kills, they would be given a value of 13/346=.037. That way, units that are useful in the current strategic climate would be favored.
3) Numbers could come from the Combat Simulator. Unfortunately, that only works for melee units, and ignores some factors like trample and routing.
4) Somebody could develop an algorithm that assigns a value to a unit based on its stats and special abilities. This would be objective, but imperfect. Probably the best bet, though.
5) I'm sure there are others=)<hr /></blockquote>I wasn't particularly asking for the big picture of values, just the ones in the test case. http://forum.shrapnelgames.com/images/icons/icon10.gif (But I'd have to say that way #2 sounds very interesting. http://forum.shrapnelgames.com/images/icons/icon10.gif ) Cause the program I made came out with 4c 3d with a score of 110 (113 for the units and -3 for resources), and when I pluged in data from a game I'm playing now all it made was Black Hunters. http://forum.shrapnelgames.com/images/icons/icon9.gif
(which is why I'm now trying to force it to make a combined arms aproach)

Originally posted by Saber Cherry:
<blockquote>quote:<hr />Originally posted by LaFollet:
And wouldn't it be more beneficial if the code made sure that a percentage was archers, or mounted, or footsoldiers?

I know there was mention of a combined arms approach and how that would increase the value of units over others, to attempt to convince the code to use different types, but why not just make it take a certain percentage of each type?No. This problem is intended to be perfectly generic, objective, and pure. That way, it can apply to any game regardless of the game's specifics, and solves a clearly-defined problem.

What you suggest can be done within the existing problem statement: Create 3 new resources, "bows", "saddles", and "boots", and give archers, cavalry, and soldiers a cost of 1 in that respective Category. Then give those resources a very high value, and give the province a certain number of each (maybe 2 bows, 4 boots, and 1 saddle) so that the algorithm will attempt to produce a minimum of 2 archers, 4 soldiers, and 1 cavalry each turn. It is best to keep the overall problem and algorithm as simple as possible and achieve complex results by adding parameters to the specific case.<hr /></blockquote>It wouldn't be as simple as adding in more resources, at least with my first program, it would take too much computer power to find the "best" use of all those resources. (Unless you math majors out there want to give me the best way to combine 16 different value sets...)

Saber Cherry

March 3rd, 2004, 07:05 PM

Originally posted by LaFollet:
I wasn't particularly asking for the big picture of values, just the ones in the test case. http://forum.shrapnelgames.com/images/icons/icon10.gif (But I'd have to say that way #2 sounds very interesting. http://forum.shrapnelgames.com/images/icons/icon10.gif ) Cause the program I made came out with 4c 3d with a score of 110 (113 for the units and -3 for resources), and when I pluged in data from a game I'm playing now all it made was Black Hunters. http://forum.shrapnelgames.com/images/icons/icon9.gif
(which is why I'm now trying to force it to make a combined arms aproach)Oooh, a working solver already! http://forum.shrapnelgames.com/images/icons/icon10.gif

I think that the best way to achieve a "combined arms bonus" is like this:

Value of 1st unit of a type=(base value)*f1
Value of 2nd unit of a type=(base value)*f2
Value of 3rd unit of a type=(base value)*f3

...etc, where f1, f2, f3...fn are decreasing. For example, if a "militia" had a base value of 10, and f1=2, f2=1.5, f3=1.33, f4=1.25, etc:

Value of queue:
1 militia = 10*2 = 20
2 militia = 20+10*1.5 = 35
3 militia = 35+10*1.33 = 48
4 militia = 48+10*1.25 = 61

This would result in a much more balanced queue, and the AI would be less likely to flood the battlefield with a single type of valuable unit that could be countered with a simple tactic.

A few examples of fn (the factor for the value of the nth unit of a type) are:

0) Currently, of course, fn=1 for all n.

1) fn = (n+x)/n
That's the example shown above, where x=1: fn = 2/1, 3/2, 4/3, 5/4... 1

2) fn = 2 if (n = 1), else 1
: 2, 1, 1, 1, 1... 1

3) fn = 1+(11-n)/10, minimum 1.
: 2, 1.9, 1.8, 1.7, 1.6, 1.5 ... 1.1, 1, 1... 1

Of course, there are other ways to achieve combined arms bonuses. But this one would be especially easy to add to a "brute force approach".

What do you think, should combined arms be added to the problem statement? If so, I would favor solution 1, fn=(n+x)/1, where "x" is specified in the specific case to solve. That would allow "x" to be specified in a problem instance as "0", or "no combined arms bonus".

Saber Cherry

March 3rd, 2004, 07:16 PM

By the way, here's another sample problem. I will name it "Abysia".

INPUT:

<blockquote>code:<hr /><pre style="font-size:x-small; font-family: monospace;">resourcetypes=3
resource=gold quantity=245 value=-1
resource=res quantity=158 value=0
resource=holy quantity=4 value=6

unittypes=5
unitname=humanbred gold=15 res=11 holy=0 value=29
unitname=battleaxe gold=20 res=27 holy=0 value=53
unitname=morningstar gold=20 res=30 holy=0 value=58
unitname=salamander gold=70 res=1 holy=0 value=42
unitname=lavawarrior gold=55 res=30 holy=1 value=91</pre><hr /></blockquote>(oops! original input had unittypes=4.
And on second thought, I added more resources to make it more interesting... reflecting, say, turn 5, when you're draining resources from the adjacent mountains.)

And yes, the values are numbers I made up. Perhaps I'll put in the combat sim numbers...

It's interesting to note that for a problem like this - if the solver supports unlimited resource types - you can add another resource, "magic". Salamanders would have a magic cost of 1, and magic would have a resource value of -8, so that the cost of magic leadership would be factored into the equation. The -8 comes from the fact that a beast trainer costs 80 gold and has magic leadership of 10, and the quantity of magic would be 10, because you can only produce one beast trainer per turn (this makes the assumption that beast trainers are the best magical leader).

[ March 03, 2004, 17:45: Message edited by: Saber Cherry ]

atul

March 3rd, 2004, 07:59 PM

Originally posted by Saber Cherry:
What do you think, should combined arms be added to the problem statement? What about... another program altogether?-> I've got the picture that while the objective of this program would be to maximize the value of one turn's production, the whole problem of combined arms spans over several turns' recruitment.

So, what I had in mind before reading this day's discussion, was a program that would count different values every turn anew. And, well...

Originally posted by Saber Cherry:
2) The game could dynamically adjust values of units by tracking them. In other words, every unit could start a game with a value based on their resource cost, or based on (1) above. But each turn, that cost would be adjusted by the success rate:While I like this one, I think there's a slight problem with looking at success rate. Example: You've just recruited a huge number of longbows, but first thing happen to send them against fliers on 'attack archers'. Result, your longbows are massacred with minimal kills, and the algorithm never lets you recruit them again to redeem themselves. Ok, that was simplistic, but I hope made my point.

In addition, there are troops that are supposed to be sent to be massacred, like those ultra-cheap R'lyeh's lobotomized atlantians or C'tis's lesser lizards. (this is represented by cheapness which is taken into account by program, but hard to say without testing how well it does)

What I'd think would be nice would be some sort of combination of your different proposition, mainly 1) and 2), with different weights (of course http://forum.shrapnelgames.com/images/icons/icon10.gif ) to each part. This would take account what happens during the game, but would also benefit from subjective experience of people (if everyone thinks Man should be about longbows and wardens, then so be it, and so on) and thematic correctness.

And the point why I was writing this, lest I forget (almost did). One more thing for the value-evaluation: number of different troops already existent. The target composition could be from a priori decided values, and a big boost would be given to troop type that is underrepresented.

Like in previous example, longbows would have large value boost for being a minority (and a slight penalty for doing so badly). This would keep the overal troop composition more consistent (no so big fluctuations as single troop types get both killed and have their prod values reduced at the same time) but allow a long-term change.

Ok, that went nearly off the subject. But no-one forces anyone to read these, so...

Saber Cherry

March 3rd, 2004, 08:11 PM

Originally posted by atul:
What about... another program altogether?

...

One more thing for the value-evaluation: number of different troops already existent. The target composition could be from a priori decided values, and a big boost would be given to troop type that is underrepresented.

Like in previous example, longbows would have large value boost for being a minority (and a slight penalty for doing so badly). This would keep the overal troop composition more consistent (no so big fluctuations as single troop types get both killed and have their prod values reduced at the same time) but allow a long-term change.That would work quite well. In that case, every unit could have a base value, specified by Users, or by some algorithm that generates a number from the unit stats ("basevalue"). Then, each turn, the AI could generate a multiplier for a unit type based on its rareness and success rate ("valuemult"). These generate the current value for each unit that turn ("currentvalue"). Then, the algorithm would run as originally specified, optimizing for the highest "currentvalue" - and the problem of multiple turns would go away, since the "currentvalue" of an underrepresented unit would keep increasing each turn until the algorithm started building them.

That way, this problem is kept simple and solvable, and the "combined arms / mutiple turn optimization" is pushed into another, much simpler algorithm: just generate a value multiplier based on success rate and rareness.

I'd like to point out that if your first bunch of longbows were wiped out by fliers, that might indicate your enemy was routinely using fliers on "attack archers", and thus halting archer production would be wise=)

atul

March 3rd, 2004, 08:34 PM

Originally posted by Saber Cherry:
I'd like to point out that if your first bunch of longbows were wiped out by fliers, that might indicate your enemy was routinely using fliers on "attack archers", and thus halting archer production would be wise=) http://forum.shrapnelgames.com/images/icons/tongue.gif
Agreed, poor example, just had to come up with something in a hurry. But if you were to halt the archer production, you would need to have a way of deciding when to start it again.

if(x kill all y) then (no y) until (x is driven to extinction) ? Loop enough times and it wouldn't produce anything anymore.

Maybe that would be a broader question of AI logic as a whole. :>

LaFollet

March 3rd, 2004, 08:35 PM

One thing at a time people!!! There's only so much that can be done. http://forum.shrapnelgames.com/images/icons/icon10.gif
But I love the ideas. http://forum.shrapnelgames.com/images/icons/icon10.gif http://forum.shrapnelgames.com/images/icons/icon10.gif http://forum.shrapnelgames.com/images/icons/icon10.gif

The only problem is that to get the current value of a "unit population" would require getting that information from Dominions, which we can't do without decompiling it, which I'm QUITE sure is against the EULA...

But I also know that this program only has application inside of Dominions, so I'm still going to make it, and it's still going to produce a "balance" of units on the first turn.

And I'd just like to note that by using a "unit population" reinforcements would be made for armies who suffered casualties in any of their Groups, and would be made at the same time that further "balanced" armies were being made. http://forum.shrapnelgames.com/images/icons/icon10.gif

LaFollet

March 3rd, 2004, 09:25 PM

Alright, my current program produces these results from the new test data:

1 lavawarrior
1 morningstar
2 battleaxe
1 salamander
3 humanbred

Gold Remaining: 15
Resources Remaining: 10
Holy Remaining: 3

Score for units: 384
Score for Resources: -224 (Edit from -72 cause it was wrong)

Total Score: 160 (Changed cause of Edit)

Original Test data produced these results:

4 c
1 d
2 b
6 a

Gold Remaining: 6
Resources Remaining: 17
Holy Remaining: 0

Score for units: 129
Score for Resources: -3

Total Score: 126

I added in a simple calculation to make units that cost more gold and resources combined will be added less frequently then those that cost less. What do you think of the results? http://forum.shrapnelgames.com/images/icons/icon10.gif

[ March 03, 2004, 20:33: Message edited by: LaFollet ]

Saber Cherry

March 3rd, 2004, 09:45 PM

Originally posted by LaFollet:
Alright, my current program produces these results from the new test data:

1 lavawarrior
1 morningstar
2 battleaxe
1 salamander
3 humanbred

Gold Remaining: 15
Resources Remaining: 10
Holy Remaining: 3

Score for units: 384
Score for Resources: -72

Total Score: 312

(...)

I added in a simple calculation to make units that cost more gold and resources combined will be added less frequently then those that cost less. What do you think of the results? http://forum.shrapnelgames.com/images/icons/icon10.gif Hmmm....

<blockquote>code:<hr /><pre style="font-size:x-small; font-family: monospace;">unittypes=5
unitname=humanbred gold=15 res=11 holy=0 value=29
unitname=battleaxe gold=20 res=27 holy=0 value=53
unitname=morningstar gold=20 res=30 holy=0 value=58
unitname=salamander gold=70 res=1 holy=0 value=42
unitname=lavawarrior gold=55 res=30 holy=1 value=91</pre><hr /></blockquote>I would say the output is non-optimal http://forum.shrapnelgames.com/images/icons/icon10.gif

For example, adding 2 morningstars and removing 2 battleaxes gives you the following results:

1 lavawarrior
3 morningstar
1 salamander
3 humanbred

Gold Remaining: 15
Resources Remaining: 4
Holy Remaining: 3

Score for units: 394
Score for Resources: -72

Total Score: 322

...and simply removing the salamander would increase the score:

1 lavawarrior
3 morningstar
3 humanbred

Gold Remaining: 85
Resources Remaining: 5
Holy Remaining: 3

Score for units: 352
Score for Resources: -2

Total Score: 350

So it produces a valid output, but is not quite optimal yet http://forum.shrapnelgames.com/images/icons/icon12.gif

Actually... in retrospect... something is wrong with your "resources" number. Are you using the correct values? For "Abysia" I set them at gold=-1, res=0, holy=6, so using 230 gold and 1 holy should result in a resource score of -1*230 + 6*1 = -224.

Scott Hebert

March 3rd, 2004, 10:27 PM

While I find all of this intriguing, unfortunately I know nothing of 'real' computer programming. However, I would be willing to try to work out 'base values' for units.

Something that may help is to base unit value off of something that I would refer to as 'survivability', and this value would be calculated as

HP/Min((Avg. Dmg. - Prot.), 1)

As you can see, Survivability is the average number of hits one can take before dying. While this favors heavy infantry... I believe that is the current trend among players. I'd like to factor Morale in as well, but I'm not sure how.

Let's take an example of HI and LI. Both have 10 HPs, and let's assume that the HI has Prot of 11, the LI has Prot of 6. Finally, let's assume the average damage in this game is 12.

The HI would have a SUR value of 10/(12-11), or 10. The LI would have a SUR value of 10/(12-6), or 1.67. This would mean that HI is worth 6 times as much as LI, from a pure survivability standpoint.

Now, one method of determining average damage that I think would be interesting is to have it compute the average damage of all units that he is aware of. By 'aware of', I would mean that it would calculate based on all National units of nations that it is in contact with. If it can access ind. province's information, it would also include their information as well.

I kind of like, though, how giants skew everything. http://forum.shrapnelgames.com/images/icons/icon12.gif With giants in the game, the computer would probably tend to produce LI.

Anyway, more later.

Bayushi Tasogare

LaFollet

March 3rd, 2004, 10:27 PM

I never said it was optimized, I just said that it was the current results, which is pretty nice mix of units, if not the best mix of units for the resources provided, and as far as resource cost go, I think I forgot to count spent gold against and unspent gold for... Not really the what I've been focusing on. http://forum.shrapnelgames.com/images/icons/icon10.gif
Also, you can increase the score by removing the salamander, but that's only because the resources the salamander use are more valuable then the salamander is, but that's just using the current "value" system, which isn't what we've agreed on using anyways. http://forum.shrapnelgames.com/images/icons/icon10.gif

The real point of this is the fact that this queue design will allow for all types of units that can be produced to be produced, not adding in the possiblity of using "unit population" numbers.

EDIT
Not what I thought it was, had the resource score values hard coded, even though I had the values being loaded with all the other data. http://forum.shrapnelgames.com/images/icons/icon10.gif Will fix and edit the results post.

Edit
Been playing around with the delay I built in, made it so it can be changed to emphasize the value, resources, gold, or holy. All this does is change how long a unit will wait to be added into the queue so that units with less of whatever the emphasized resource is will be made more often. These are the best results got by emphasizing Holy:

1 lavawarrior
2 morningstar
2 battleaxe
1 salamander
1 humanbred

Gold Remaining: 25
Resources Remaining: 2
Holy Remaining: 3

Score for units: 384
Score for Resources: -214

Total Score: 170

Also worthy of note, 7 units are produced this way, with the max units produced with "emphasizing" being 8 with a score of 156

[ March 03, 2004, 21:14: Message edited by: LaFollet ]