AI Combat Odds

[Iustus]

Ok, this time I think I did find a bug, I am not sure how significant it is, but it is a true bug.

	iDefenderOdds = ((1000 * iDefenderStrength) / (iAttackerStrength + iDefenderStrength));
	iAttackerOdds = ((1000 * iAttackerStrength) / (iAttackerStrength + iDefenderStrength));	
	[COLOR="SeaGreen"]// note: iDefenderOdds + iAttackerOdds  = 1000[/COLOR]

(I added the comment). Well, the fact is that some times these two add to 999, not 1000. This means that in some cases the wrong percentage is being used (but it is only slightly off).

Looking at the code for combat, which uses the defender odds only (it rolls 0-999, if the number is in the iDefenderOdds range, then the defender wins, otherwise the attacker wins), this means the attacker gets the round off, so it should be:

	iDefenderOdds = ((1000 * iDefenderStrength) / (iAttackerStrength + iDefenderStrength));
	iAttackerOdds = 1000 - iDefenderOdds ;	
	[COLOR="SeaGreen"]// note: iDefenderOdds + iAttackerOdds  = 1000[/COLOR]

or in the case of the actual code:

	iDefenderOdds = (((GC.getDefineINT("COMBAT_DIE_SIDES") * iDefenderStrength) / (iAttackerStrength + iDefenderStrength));
	iAttackerOdds = (GC.getDefineINT("COMBAT_DIE_SIDES") - iDefenderOdds;	
	[COLOR="SeaGreen"]// note: iDefenderOdds + iAttackerOdds  = (GC.getDefineINT("COMBAT_DIE_SIDES")[/COLOR]

This would fix this (minor) round off error. It is possible that this has a large accumilation effect, since it can be added in quite a few times if there are a lot of possible first strikes involved. I would have to see the numbers to be convinced though.

Whether it is a very minor bug, or a big one, it does seem to me to be a real bug in getCombatOdds

-Iustus

 

[Iustus]

I posted this bug to the SDK bugs thread I started in the bug reports forum:
bug report post

In doing so, I found what looks to me like another bug. The defender is given a 1 in 1000 bonus chance to win a combat in updateCombat, by what looks to me as a bug using <= when < should be used. If the intent was to give the defender that extra edge, then getCombatOdds needs to add one to iDefenderOdds, before calculating iAttackerOdds. The details are in the bug report post.

-Iustus

 

[ClassicThunder]

Wow thanks you've alread done all the hard work for me! I've loaded up the project and as soon as I edit and test the .dll I'll release it for testing. But thanks again Iustus.

 

[Iustus]

From an optimization standpoint, I am not sure there is a lot that can be done with getCombatOdds and preserve its accuracy. It is possible to improve the loop to slightly reduce the number of times looped. But I do not think it is worth doing.

The super fast, approximate case, used by the AI, does not loop at all, (nor does it even need to do the complicated combinatorial math even once.)

My theoretical optimization uses the fact that there are some first strike combinations which are the same, you do not have to calculate them multiple times.

The important factor here is that the current function loops (attacker.FirstStrikeChances * defender.FirstStrikeChances) times.

Lets look at this, in the case of 4 chances for each, plot each chances, subtract. Negative numbers mean the defender gets more first strikes, zero is equal number, and positive numbers are attacker getting more first strikes.

	0	1	2	3	4
0	0	+1	+2	+3	+4
1	-1	0	+1	+2	+3
2	-2	-1	0	+1	+2
3	-3	-2	-1	0	+1
4	-4	-3	-2	-1	0

Now, there are five 0s on this graph. They are all going to result in the same fractional odds in the loop. We are computing the same number 5 times and adding it together.

It is a pretty simple function to determine f(4,4, 0) = 5 duplicates, f(4,4, +1) = 4 duplicates, f(4,4, -2) = 3 duplicates.

Using this, we could reduce the loops from (attacker.FirstStrikeChances * defender.FirstStrikeChances) to (attacker.FirstStrikeChances + defender.FirstStrikeChances + 1).

While, in the abstract, this sounds great, going from a n squared algorithm, to a 2n agorithm.

But the problem is that as far as I can see, the maximum number of first strike chances a unit can have in the default game is 4.

This means that:
AI optimized function: no loops, no complex math
existing function: max 16 loops on complex math
potential optimization: max 9 loops on complex math

This is not enough of an improvement over the current method to be worth doing, certainly not enough to make it worth using this much more complex function every time the AI wants to know the odds.

---

If someone wants to pursue whether the displayed odds are correct, probably the best thing to do is to just port this function, and the actual combat function into a little app, then run the combat about a million times on a set of inputs and compare it with the calculated odds.

I suspect with the two fixes I mention above, the odds would be correct. I am curious how far off the odds are with both bugs, as at first glance, they seem to me to offset each other to some extent.

If you were going to do this, in the default game, the max number of first strikes is 5, and the max number of first strike chances is 4. (Technically, with 5 strikes, you can have max 3 chances and max 4 strikes when you have 4 chances).

If someone wants to do this, feel free to PM me if you want some more guidance on what inputs you should use.

-Iustus

 

[ClassicThunder]

Okay I've made the changes to the sourse code but when I try to compile the code I get an error.

CvGameCoreDLL fatal error LNK1120: 1 unresolved externals

How do I fix this? I get it even when I use the code I didn't edit.

Thanks, ClassicThunder

 

[Iustus]

You might want to check the main thread about how to build the SDK.

That said, what is the external that you get the error on? It should say the name of the symbol.

What environment are you building the SDK in? (Visual Studio 2003 or Visual Studio.net 2003 are preferred)

-Iustus

 

[ClassicThunder]

I'm using Visual Studio.net 2003 and here's the error code.

   Creating library Final Release/CvGameCoreDLL.lib and object Final Release/CvGameCoreDLL.exp
LINK : warning LNK4199: /DELAYLOAD:OleAcc.dll ignored; no imports found from OleAcc.dll
CvDLLWidgetData.obj : error LNK2019: unresolved external symbol __imp__GetKeyState@4 referenced in function "public: void __thiscall CvDLLWidgetData::doResearch(struct CvWidgetDataStruct &)" (?doResearch@CvDLLWidgetData@@QAEXAAUCvWidgetDataStruct@@@Z)
../Assets/CvGameCoreDLL.dll : fatal error LNK1120: 1 unresolved externals

Also which type of .dll am I suposed to make it into: Static Library, StandardWwindows Libraries or MFC Shared DLL?