Better, Simpler Programming Contest

[Saber Cherry]

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

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"

And - Yay! Someone is working on the problem

...however, the number of votes is still listed as 2 for me, both people who won't participate...

[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?

[Leif_-]

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?

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]

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]

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]

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]

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.