[SDK] Lead from Behind

[phungus420]

Hey, how is this modcomp coming along? I'm highly interested.

Also use whatever core you want. My reccomendation would be to use the standard 3.19 source, or BBAI to make merging easier. Especially the BBAI core if you intend on implementing the high value unit protection logic (which I'd love to see), the reason a BBAI core would be good to build that out of is because BBAI would likely include it by default if you program it. Course, since I plan on merging in this modcomp, I'm fine with you building it in a RevDCM core, as that would make merging easier from my perspective. But there are alot of other modders out there that would be interested in your source code, so that's why a BBAI or standard 3.19 SDK would probably be best.

 

[UncutDragon]

Hey, how is this modcomp coming along? I'm highly interested.

I'm basically done coding, just debugging (which can be a pain when you're allocating memory ...). Should have a working version soon, then I'll do some time tests, and let you know how it looks.

 

[Roland Johansen]

That's 8.5 seconds to compute 4 million odds ... it seems reasonable to me, but I guess we'll see when I try it in the game.

Computers today can do a massive number of calculations in a short amount of time. no doubt about that. I'm just wondering when I select my stack of 150 units, press ALT and hold the mouse over my opponents stack of 150 units, how long will it take to see the odds of my best attacker against the opponents best defender. We will have to assume that both stacks hold units with varying strengths, first strikes and hitpoints. I agree that this is close to a worst case situation, but of course the game has to behave well in worst case situations. It would be a problem if players play the game during the earlier ages without problems and then will have to wait several seconds to see the odds of their big stack in the late game. It's the kind of problem that will only show its ugly head during late game wars with huge armies (typically more an issue for big maps) and may thus be overlooked by many players.

Another issue could possibly be the interturn times where the AI will have to do the comparison between the 150 unit stacks multiple times before one of the stacks is destroyed.

I do agree that the approach to store the results of parts of the calculation is a smart move. I even talked briefly about caching results but hadn't thought about this approach. It's a good way to severely limit the amount of computations, I'm just wondering if it will be good enough in the worst case situations.

Could further limitations in the amount of computations be reached by some heuristics? For instance, if the defender has the choice between two units A and B:
A 10, 1 first strike, 100 hp
B 7, 1 first strike, 100 hp
then its obvious that the odds for A will be better. Still, the game will presently needlessly calculate the odds for B.
There are many of these situations. In practice, when an experienced player looks at the defenders in a 150 unit stack and compares them, he/she might end up with some 5 units which might be the best defender and will have to use a calculator to see which one is the very best. But he/she won't have to compute the odds for all 150 units. And this is just based on some simple heuristics like the one I mentioned above. It mainly involves ordering the units on strength, first strikes and hitpoints against various attackers.

The same could be done for attackers.

It of course does make the programming more difficult. Depending on how many heuristics are used, it could even become pretty hard.

 

[UncutDragon]

Computers today can do a massive number of calculations in a short amount of time. no doubt about that. I'm just wondering when I select my stack of 150 units, press ALT and hold the mouse over my opponents stack of 150 units, how long will it take to see the odds of my best attacker against the opponents best defender. We will have to assume that both stacks hold units with varying strengths, first strikes and hitpoints. I agree that this is close to a worst case situation, but of course the game has to behave well in worst case situations.

I agree, in the end test apps mean nothing, it's whether it's playable - as I said, we'll see what's like in the game. I do have some preliminary numbers - right now, it looks like it'll take roughly 2.5X what it does now.

Could further limitations in the amount of computations be reached by some heuristics? For instance, if the defender has the choice between two units A and B:
A 10, 1 first strike, 100 hp
B 7, 1 first strike, 100 hp
then its obvious that the odds for A will be better. Still, the game will presently needlessly calculate the odds for B.

It's a thought - I'll see what I can do with that.

One simple change I have done is to return the calculated odds for the best defender. In the existing code, it compares two units, and just returns true/false to indicate which is best ... then that unit is passed back in to compare with the next, and everything's recomputed. By simply returning the odds I already computed for the best unit (along with the true/false), and passing it back in with the next call, I can reduce the time considerably on large stacks.

Anyway, I tested with a stack attack - I actually did 368 vs 318, to give me a reasonable length of time for a test. My results:

current code: 32s
my code using strength: 19s
my code using odds: 72s

I'll keep looking at it, see if I can bring that down some more - maybe with those heuristics checks.

 

[Roland Johansen]

Anyway, I tested with a stack attack - I actually did 368 vs 318, to give me a reasonable length of time for a test. My results:

current code: 32s
my code using strength: 19s
my code using odds: 72s

I'll keep looking at it, see if I can bring that down some more - maybe with those heuristics checks.

Oh, that looks pretty good, a lot better than I had expected. I do expect that it depends lot on the type of units in the stack. If the units differ a lot, with no 2 being the same (which would be rare in such large stacks), then I would expect your code to become relatively slower as the caching isn't helping that much. On the other hand, a stack with mostly the same units might be evaluated even quicker with your code.

 

[UncutDragon]

Oh, that looks pretty good, a lot better than I had expected. I do expect that it depends lot on the type of units in the stack. If the units differ a lot, with no 2 being the same (which would be rare in such large stacks), then I would expect your code to become relatively slower as the caching isn't helping that much. On the other hand, a stack with mostly the same units might be evaluated even quicker with your code.

At the moment, I have two stacks of identical units. At some point, I'll try making the units vary a bit, but I actually don't expect it to make much difference.

Keep in mind that the cache isn't really that big - from my test app (which covered a pretty wide spectrum of possibilities), there was only about 9500 numbers cached. By comparison, I added a counter to the code, and that 368v318 combat required over 27M odds. So no matter how diverse the stacks are, the vast majority of those odds will be calculated just from the cache.

Which is actually an interesting tidbit ... I would've expected a little more than 13M odds (just based on 368x318 + 365x317 + 364x316 etc). Which makes me wonder where the extra calls are coming from ... might be something there if I can find it.

As for the heuristic checks, I hit a rather big problem with that ... I sort of shot myself in the foot there The problem is the whole 'more valuable' concept I introduced ... Even if unit A is obviously better than unit B, if one of them is more valuable, I may still want to pick B as the defender. Which makes heuristic checks only really of value for comparing units of equal value ...

In any case, I did find another big speed improvement (and a simple one at that!). Whenever the code was retrieving the COMBAT_DAMAGE or COMBAT_DIE_SIDES settings, it was doing a lookup using the string. Simply by doing that lookup at startup, and storing it in a variable, I was able to cut the time literally in half!

My times today:

current code: 30s
my code using strength: 16s
my code using odds: 33s

So time is looking pretty good! I do still need to do a lot of testing though.

 

[Roland Johansen]

At the moment, I have two stacks of identical units. At some point, I'll try making the units vary a bit, but I actually don't expect it to make much difference.

Keep in mind that the cache isn't really that big - from my test app (which covered a pretty wide spectrum of possibilities), there was only about 9500 numbers cached. By comparison, I added a counter to the code, and that 368v318 combat required over 27M odds. So no matter how diverse the stacks are, the vast majority of those odds will be calculated just from the cache.

Which is actually an interesting tidbit ... I would've expected a little more than 13M odds (just based on 368x318 + 365x317 + 364x316 etc). Which makes me wonder where the extra calls are coming from ... might be something there if I can find it.

I'm not quite sure anymore what you're caching, but maybe you're letting 2 units (attacker and defender) die per battle in your approximation which is about a 2 to 1 factor.

Could you explain again what you're caching?

As for the heuristic checks, I hit a rather big problem with that ... I sort of shot myself in the foot there The problem is the whole 'more valuable' concept I introduced ... Even if unit A is obviously better than unit B, if one of them is more valuable, I may still want to pick B as the defender. Which makes heuristic checks only really of value for comparing units of equal value ...

Clear. A pity though.

In any case, I did find another big speed improvement (and a simple one at that!). Whenever the code was retrieving the COMBAT_DAMAGE or COMBAT_DIE_SIDES settings, it was doing a lookup using the string. Simply by doing that lookup at startup, and storing it in a variable, I was able to cut the time literally in half!

My times today:

current code: 30s
my code using strength: 16s
my code using odds: 33s

So time is looking pretty good! I do still need to do a lot of testing though.

Looking good.

 

[UncutDragon]

I'm not quite sure anymore what you're caching, but maybe you're letting 2 units (attacker and defender) die per battle in your approximation which is about a 2 to 1 factor.

If the attacker wins, there's one less defender - and since a unit can't attack twice, there's one less attacker to consider as well. And I happen to know in my little test, the attacker will win most of the time. So getting twice the number of odds expected just didn't make sense ...

In any case, I found the culprit: in CvUnit::canMoveInto, it was calling getBestDefender - but all it actually cared about was whether there was someone to fight. So instead I'm calling a new hasDefender method that simply checks if a valid defender exists and returns a true/false - no change to the gameplay, but got rid of those extra odds calculations ... and cut the combat time in half again!

Could you explain again what you're caching?

OK, basically I cache values for the following combination of parameters:

NumFirstStrikes (Attacker-Defender) (ranges from -7 to 7)
AttackerRoundsNeeded (ranges from 1 to 17)
DefenderRoundsNeeded (ranges from 1 to 5)
AttackerOdds/16 (ranges from 1 to 32)

(Note that those ranges aren't hard-coded in any way, and my caching code doesn't try to predict what I'll need - I simply grow my arrays as needed)

For AttackerOdds > 500, I flip it and calculate defenders chance instead (which also effectively limits DefenderRoundsNeeded to 5, since defender odds >= 500 means defender damage >= 20). I also only calculate for multiples of 16 and do a weighted average of the two closest values. (e.g: If I need odds for 123, I'd do odds(112) + (123-112)*(odds(128)-odds(112))/16).

In theory that's 40800 odds that need to be cached - however, in practice a lot of those numbers simply never come up (e.g: if AttackerRoundsNeeded is very high, you can be sure AttackerOdds is very low). I went back to my test app, and modified it a bit to cover (I think) every possibility, and it caches 12630 values.

Anyway, I do have one more change I'd like to do - the code that determines the best attacker still bases it on strength. The funny thing is, that code actually tries to factor in the number of rounds needed, so is probably more accurate than the best defender code was. But I'd still like to change it to use odds instead, and adjust based on 'more valuable'. (Since it's already doing a lot of the work needed to get the odds anyway, I don't expect this to slow things down very much)

 

[UncutDragon]

Just thought I'd give everyone an update - I did modify the best attacker code to use odds and factor in the 'most valuable'. As I expected, it didn't increase combat time by much (1s). So with all the changes, that 368v318 combat now takes 16s!

I wanted to do a good test of accuracy and stability, so I merged in AIAutoPlay (just temporarily - I'll take it back out later). I also modified the best defender code to compute the odds both ways, and compare the result. Let it play through about a half dozen large/epic games - no crashes, and odds were never off by more than 2.

With one exception: selecting a seige engine while defender is below the combat limit results in attacker rounds needed being zero ... the standard algorithm will still calculate odds for that case, but I simply return 1000 (100% chance to 'win'). So in this case, my algorithm will be way off the standard algorithm ... however, since combat isn't allowed, those odds will never be displayed or used. So it really makes no difference, and saves wasting memory to store these useless 'odds' in the cache.

I also added some counters, just for interest sake: in a large/epic game, I'd get around 800,000 calls to lookup odds, and store less than 4000 odds in the cache.

So anyway, things are looking good. I'm happy with the speed and accuracy, and of course stability. I just need to go back to testing specific scenario's to make sure the 'most valuable' code is doing what's it supposed to (it's been awhile since I tested that - need to make sure I didn't inadvertantly break something - and of course make sure the best attacker changes are working correctly)

 

[Afforess]

Wow. This modcomp has really evolved from it's original setup. I've definitly changed my mind about this, and can't wait for your release so I can stea... use it in my modmods.

You've done some truly great work here.

 

[PieceOfMind]

Just thought I'd give everyone an update - I did modify the best attacker code to use odds and factor in the 'most valuable'. As I expected, it didn't increase combat time by much (1s). So with all the changes, that 368v318 combat now takes 16s!

I wanted to do a good test of accuracy and stability, so I merged in AIAutoPlay (just temporarily - I'll take it back out later). I also modified the best defender code to compute the odds both ways, and compare the result. Let it play through about a half dozen large/epic games - no crashes, and odds were never off by more than 2.

With one exception: selecting a seige engine while defender is below the combat limit results in attacker rounds needed being zero ... the standard algorithm will still calculate odds for that case, but I simply return 1000 (100% chance to 'win'). So in this case, my algorithm will be way off the standard algorithm ... however, since combat isn't allowed, those odds will never be displayed or used. So it really makes no difference, and saves wasting memory to store these useless 'odds' in the cache.

I also added some counters, just for interest sake: in a large/epic game, I'd get around 800,000 calls to lookup odds, and store less than 4000 odds in the cache.

So anyway, things are looking good. I'm happy with the speed and accuracy, and of course stability. I just need to go back to testing specific scenario's to make sure the 'most valuable' code is doing what's it supposed to (it's been awhile since I tested that - need to make sure I didn't inadvertantly break something - and of course make sure the best attacker changes are working correctly)

Sounds good. I'm still following the thread by the way. It should still be compatible with ACO since ACO is only called in a mouse over event and all other calls for odds calculations use the default algorithm, which will be replaced by yours I guess.

 

[phungus420]

Please remember to take into account Heros/Legend units which some mods add. These units are highly valuable, but don't have high levels, as they usually start with a few promotions. A good way to add value to these units would be to check the MaxGlobalInstances of the unit, and also value by the number of promotions a unit has instead of level.

 

[UncutDragon]

Wow. This modcomp has really evolved from it's original setup. I've definitly changed my mind about this, and can't wait for your release so I can stea... use it in my modmods.

You've done some truly great work here.

Thanks ... and of course you're free to stea ... use it Also, while I haven't really looked at the AI, the changes to best attacker code should benefit the AI to some extent.

Sounds good. I'm still following the thread by the way. It should still be compatible with ACO since ACO is only called in a mouse over event and all other calls for odds calculations use the default algorithm, which will be replaced by yours I guess.

Yes - while technically you could use the cache, it would be a bit convoluted, and (for a mouse-over event) not really worth the effort. Should just be a straight merge, no need to edit the code at all.

Please remember to take into account Heros/Legend units which some mods add. These units are highly valuable, but don't have high levels, as they usually start with a few promotions. A good way to add value to these units would be to check the MaxGlobalInstances of the unit, and also value by the number of promotions a unit has instead of level.

While I don't have anything to value promotions, I do have it taking limited units into account now - and the values are weighted. So for example, you could make limited units worth 2 and leave experience at 1, then a limited unit would be considered more valuable than one with more experience.

Although there is one particular promotion I decided to include - Medic. Though it's not based on the specific promotion but rather the ability to heal.

 

[phungus420]

I suppose what I'm asking is to take a look at FFH2 or LoR, and add in some sensical code to deal with World Wonder style units. In both these mods there are certain units that can only be built once (like world wonders), but they are not excessively more powerful, usually +1 or 2 strength from units available at the time, with certain combat bonuses and they often start with a few free promotions. Under the code you've presented it sounds like the AI wol't really consider the true value these units have.

 

[UncutDragon]

I suppose what I'm asking is to take a look at FFH2 or LoR, and add in some sensical code to deal with World Wonder style units. In both these mods there are certain units that can only be built once (like world wonders), but they are not excessively more powerful, usually +1 or 2 strength from units available at the time, with certain combat bonuses and they often start with a few free promotions. Under the code you've presented it sounds like the AI wol't really consider the true value these units have.

I haven't looked at them in detail, but I would assume you're setting iMaxGlobalInstances in CIV4UnitClassInfos.xml? If that's the case, it's considered a limited unit (limited means at least one of MaxGlobal/MaxTeam/MaxPlayer is set), so will be treated as more valuable - by my code at least. As for the AI in general, I'm not really looking at that for this mod.

 

[phungus420]

OK, yeah I know both FFH and LoR use the MaxGlobalInstances tag, just wanted to make sure the degree of valuing the unit was good. Although you definatly want to let the limited units defend if they are a good choice. Basically I think it should be valued as highly as units with the Leader promotion.

As for the AI in general, I'm not really looking at that for this mod.

Oh, you know that might be a good concept for a future project

 

[UncutDragon]

OK, yeah I know both FFH and LoR use the MaxGlobalInstances tag, just wanted to make sure the degree of valuing the unit was good. Although you definatly want to let the limited units defend if they are a good choice. Basically I think it should be valued as highly as units with the Leader promotion.

I haven't played around much with the value settings - you'd really have to play through a lot of games to see how they play out. But I'm thinking along the lines of 2 for leader and limited, 1 for experience and healer. In any case, those settings come from an XML file, so it'll be easy to adjust.

As for letting them defend, I'm still using a 'sliding scale' for that - though of course I had to modify it now that I'm using odds. I settled on a valuable unit's ranking being: odds + (odds-850). So with an 85% chance of winning, there's no adjustment. Better odds than that, and it becomes more likely to defend - worse odds, less likely.

Oh, you know that might be a good concept for a future project

Maybe

 

[UncutDragon]

OK, version 1.0 is now available to download!

Give it a try, and let me know what you think. I'm especially interested in any feedback regarding the 'more valuable' calculation and adjustment - I've tried using what I think is reasonable, but that kind of thing is best determined through use.

 

[Afforess]

OK, version 1.0 is now available to download!

Give it a try, and let me know what you think. I'm especially interested in any feedback regarding the 'more valuable' calculation and adjustment - I've tried using what I think is reasonable, but that kind of thing is best determined through use.

Merging it right now, will comment later.

I however, will be making it a gameoption for those players who like the old BTS way.

Edit: Apparently, you already made it enable-able in the global defines. Nice work.

 

[Ninja2]

Very nice! I will include this in the next version of Merged Mod.