Better, Simpler Programming Contest

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

[Saber Cherry]

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]

Originally posted by Saber Cherry:

quote:

---

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=)

---

I wasn't particularly asking for the big picture of values, just the ones in the test case. (But I'd have to say that way #2 sounds very interesting. ) 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.
(which is why I'm now trying to force it to make a combined arms aproach)

Originally posted by Saber Cherry:

quote:

---

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.

---

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]

Originally posted by LaFollet:
I wasn't particularly asking for the big picture of values, just the ones in the test case. (But I'd have to say that way #2 sounds very interesting. ) 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.
(which is why I'm now trying to force it to make a combined arms aproach)

Oooh, a working solver already!

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]

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

INPUT:

code:

---

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

---

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

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

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=)