Better, Simpler Programming Contest

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

[atul]

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

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]

One thing at a time people!!! There's only so much that can be done.
But I love the ideas.

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.

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

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