I just lost all 3 of my attacks against neutrals in one turn of a FFA; 2v1,4v2,4v2. It cost me two bonuses and a card piece on the third turn. I was sad.

Statistically, this is about a 1/500 chance. (.13*.13*.11)

It made me curious about other people's misfortune. What are the worst odds that you've hit (best odds that you've missed?), not including 5v1's?

I'd have to dig through the logs for the specifics, but I've lost 10v2 attacks with 75% luck.. Apparently you need something like 13v2 to guarantee the win at that level of luck. It's happened more than once.

I think with 75% luck you can never guarantee a win against 2

I think with 75% luck you can never guarantee a win against 2

Sure you can. If you set luck at 75%, that means that WL will both simulate the attack (with virtual dice) and simply calculate the expected number of kills. Assuming 60% offence kill rate and needing to kill 2 defenders that means 0.75 * Simulated + 0.25 * Average >= 2. Since we're assuming the worst case scenario (in the simulation our armies don't kill a single defender) that becomes 0.75 * 0 + 0.25 * Average >= 2 or even simpler 0.25 * Average >= 2. Filling in the 60% kill rate gives us 0.25 * 0.60 * Attackers >= 2, which becomes Attackers >= 8 / 0.60 = 13 1/3. Now there's one last caveat; you have to "round up" for this to work; we need at least 13 1/3 attacker, so rounding down to 13 is invalid. So, 14 vs 2 (75% luck, 60% kill rate) is a guaranteed victory, 13 vs 2 (with the same parameters) is not.

In all fairness, the change a 13 vs 2 doesn't succeed is "rather small":

• All rolls must fail: 0.40^13 ~= 6.7 * 10^-6
• 13 * 0.60 = 7.8
• 0.75 * 0 + 0.25 * 7.8 = 1.95 (in WL that means a 1 in 20 chance of rounding to 1, 19 in 20 chance of rounding to 2)
• 6.7 * 10^-6 * 1/20 ~= 3.4 × 10-7 ~= 1 in 3.000.000 chance

So yes, you can still guarantee a win. Of course, you could argue 13 vs 2 is a guaranteed win as well... If it fails, you can post here and "win" this thread. :p

I still don't understand why the analysis does not properly reflect the real chances. Not only does it round, it merely "attacks" 2 armies with X amount of armies and checks how many times it succeeds. This'll show a 100% chance to succeed for 8 armies, and sometimes for 7, while it really is 14 (as described above, I calculated it on my own before as well).

I unfortunately don't remember the exact setup, but I've posted it in another thread recently. It was something like having two armies more in my attackers over the defenders (he put down a lot of his reinforcements there), and my failed attack lost me more armies than he did, I believing making him have 1 more army left. Then later on in the turn he attacked me back and not only did he wipe me out, he still kept several armies standing.

http://warlight.net/Forum/Thread.aspx?ThreadID=3153

I still don't understand why the analysis does not properly reflect the real chances.

Probably because the maths is not trivial (in the general case; here it greatly simplifies, details in next paragraph) and more importantly, you have to iterate over a lot of possibilities to do the calculation perfectly. Then again, the analyser runs on the user's computer (not on the server), so it wouldn't cause a bottleneck or anything... I dunno, maybe Fizzer will respond and explain the exact reason.

Anyway, to get to the maths. First order of business, don't take the following as gospel, since I noticed an error in my earlier calculation (two posts above) while writing this... :(

(If WL would ever allow kill rates to be above 100% (one army might kill more than one opposing army), then this whole calculation goes straight into the trash can; the simulation approach on the other hand could easily be updated accordingly.)

Notation:
[#Atk] = Number of attackers
[#Def] = Number of defenders
[Atk%] = Offence kill rate
[Def%] = Defence kill rate
[Luck%] = Luck percentage
[Total] = The chance of the attack succeeding, taking everything into account; basically, this is the value you'd use for the analyser graph

The calculation consists of a few parts:

First we calculate the expected number of kills (the no-luck case). This is easy: [Expected] = [#Atk] * [Atk%].

Then we calculating the simulated number of kills (dice rolls). This is not so much hard as it is much work:

• if [#Atk] < [#Def]
  There are not enough attackers to kill all defenders: the attack is a guaranteed failure, no calculation needed.
  [Total] = 0

• if [#Atk] = [#Def]
  Attack succeeds only if all attackers kill a defender and at least one defender does not kill an attacker. [If all defenders kill an attacker, no armies are left and, as a special exception, one defender is magically resurrected; this is why 1-vs-1 attacks (or actually x-vs-x attacks in general) are a terrible idea.]

  All attackers kill a defender = [Atk%]^[#Atk]
  At least one defender does not kill an attacker = 1 - no defender doesn't kill an attacker
  No defender doesn't kill an attacker = ( 1 - [Def%] )^[#Def]
  [Simulated] = [Atk%]^[#Atk] * ( 1 - ( 1 - [Def%] )^[#Def] )
  [Total] = [Luck%] * [Simulated] + ( 1 - [Luck%] ) * [Expected]

• if [#Atk] > [#Def]
  Now the "fun" really hits the fan... ;) The good news is that the special exception cannot occur (there are not enough defenders to kill all attackers, so if all defenders die, there will automatically be at least one attacker left to occupy the territory).
  The attack succeeds if the number of killed defenders is at least as high as the number of defenders. Unfortunately that means we have to iterate over all possible numbers of defenders getting killed and summing those values...

  The attackers killing exactly "i" defenders:
  [Simul-i] = [Atk%]^i * ( 1 - [Atk%] )^( [#Atk] - i )

  Factoring in luck is a joy as well. When WL has to round a number of kills from a fractional number to an integer it doesn't use normal rounding, it uses "stochastic rounding": a value of x.25 will be rounded to x with 75% chance and to x+1 with 25% chance. That gives us:

  • if [Luck%] * i + ( 1 - [Luck%] ) * [Expected] < Floor ( [#Def] )
    [Total-i] = 0
  • if Floor ( [#Def] ) <= [Luck%] * i + ( 1 - [Luck%] ) * [Expected] < Ceil ( [#Def] )
    [Total-i] = ( 1 - Frac ( [Luck%] * i + ( 1 - [Luck%] ) * [Expected] ) ) * [Simul-i]
  • if Ceil ( [#Def] ) <= [Luck%] * i + ( 1 - [Luck%] ) * [Expected]
    [Total-i] = [Simul-i]

  Now we still have to take the summation over all "i":
  [Total] = Sum(0<=i<=[#Atk]) [Total-i]

I dunno, maybe Fizzer will respond and explain the exact reason.

On second thought, I think I do know the exact reason all of a sudden. :p

I'll leave this here for one or two days, then if nobody found any errors (please, if you checked this in any detail and didn't find any errors, say so as well; if nobody mentions errors, it might very well be because nobody could make head or tails out of this... :s ), I'll whip up a quick-and-dirty stand-alone analyser to see if the results indeed look plausible.

Knoebber, you can guarantee a win with any luck percentage except for 100%

even at 99% luck, if you attack with 334 armies against a neutral, your minimum is 334 * 0.6 * 0.01 = 2.004 armies killed

The attackers killing exactly "i" defenders:
[Simul-i] = [Atk%]^i * ( 1 - [Atk%] )^( [#Atk] - i )

Or actually, [Simul-i] = [Atk%]^i * ( 1 - [Atk%] )^( [#Atk] - i ) * ( [#Atk] nCr i )... *shame on me*

Nobody's crazy enough to check it? :p

even at 99% luck, if you attack with 334 armies against a neutral, your minimum is 334 * 0.6 * 0.01 = 2.004 armies killed

I'd love to see the face of my opponent when his 333 vs 2 attack fails! :D

Well, I've got good news and bad news... The bad news is that you probably should not look at those calculations of mine, they're not actually very accurate (mostly, I got enormously confused between which values represent numbers of armies and which values represent chances, then proceeded to make an utter mess of it)...
On the bright side though, you don't have to worry about it any more, since I've fixed them and build a nifty little program around it which produces (to the best of my knowledge) accurate results, except for x-vs-x attacks; that's still broken (as in, it doesn't correspond to the built-in analyser at all and since that one simulates using the regular game code, I trust it's accurate).

Features

Useful stuff

• Completely configurable number of attackers, defenders, offensive kill rate, defensive kill rate and luck percentage (exactly matching the allowed values in WL's game creation screen).
• Shows two decimal places (more than makes sense to pay attention to, but rounding to whole percents as the built-in analyser does is a little too aggressive for my taste).
• Can graph for different number of attackers (to answer the question: how many armies do I need to attack with?), just like the built-in analyser.
• Can graph for different number of defenders (to answer the question: how many armies do I need to defend against a counter-attack?), this is a feature I've always missed in the built-in analyser.
• An optional "always on top" feature, so you can click in the main WarLight window without losing the analyser. :)

Fun stuff

• Makes a distinction between chances shown as 0.00% due to rounding and "Fails" for an attack which cannot possibly succeed. The same goes for the distinction between 100.00% and "Succeeds" for a guaranteed victory.
• The success percentage is colour-coded to give a rough estimate of how good an idea it is to try that attack.
• When graphing it also tries to show how many armies you need for an attack (or a defence!) which is guaranteed to succeed (or hold). If it takes too long to figure out (or when you use 100% luck) this will be left out.
• Accessible without hitting "Re-do orders" / creating a new game on Small Earth in another tab just to be able to use the analyser. :)

Getting it

You can download it here. I haven't really thought about making it open source or anything (definitely not until I get that x-vs-x bug fixed though), but if you're interested, let me know and I'll see how much work it is to clean up the code. In case you're wondering, it's written in Borland Delphi 7 (that's an Object Pascal compiler). Bug reports and feature requests are welcome, but I'm not sure when (and if...) I'll get to them. And of course this comes without any warranty at all.

thanks for correcting me perrin/rvw

I haven't really thought about making it open source or anything

You should open source it, at the very least because it's not advisable for people to run arbitrary exes that are posted on internet forums, which will limit its use.

Also, if you can fix the x vs x issue, and also make the performance acceptable with large numbers (it doesn't need to be super fast, but it shouldn't take hours), I'd be interested in replacing the current analyzer with your code, if you wanted to permit it. I think it would be cool to give accurate odds instead of approximate odds that it gives today.

Whoa, RvW, Fizzer himself is interested in your code! Next time you can put "Warlight Ceator" below your name and get cash for every new member!

You should open source it, at the very least because it's not advisable for people to run arbitrary exes that are posted on internet forums, which will limit its use.

In theory I agree, but in practice...? If I post the source and the exe, how many people will inspect the source to verify I didn't hide any nasty surprises and then compile it themselves from the clean source? After all, what stops me from posting clean sources and a compiled version with "bonus content"?

Didn't expect you to be interested at all before I got the details fixed, that's why I left out these details from my previous post:

Currently, for any specific calculation the answer pops up at once. Graphing is near-instantaneous for reasonable numbers. However, it does take too long to graph higher numbers, simply because there's a lot of iterations to work through (plotting for 5000 defenders takes approximately 25 seconds on this, quite fast, machine). However, I haven't worried about optimization too much yet, for instance using a step-size of 10 would speed it up by a factor of 10. Also, currently I do all calculations first, then plot in one go; calculating and plotting side-by-side would give the impression of being faster, as well as considerably reduce memory usage.

Technical limitations:

• I'm using the "Extended" type for floating points, do you have access to that in whatever language the WL client is written in (not just on the regular client, but on the mobile clients as well)? Limiting to doubles would cause more severe restrictions.
• I can allow a maximum of 16378 attackers. Within the calculation I depend on the nCr function, which simply grows very rapidly (exponentially in fact); with 16379 or more attackers to simulate it overflows even the Extended floating point type. I'd have to look into a reasonable approximation for bigger numbers; the current "Sorry, that's not supported" is not acceptable.

Practical limitations:

• I didn't sleep last night and had a very busy day today; don't expect an update within at least 24 hours of this post. :(

@Moros:
Thank you, but I think "WarLight code snippet donor" would be much more accurate. Still appreciate the compliment though! :D

Besides, given the amount of time I spent on this (it will probably end up being two or three days at the very most) and the amount Fizzer spent and keeps spending on WL, my share would be waaaaaay behind the comma. And that's not even taking into account that most (probably all) membership money goes to server and bandwidth costs (I'd be very surprised if Fizzer manages to make a profit on WL), so it'd be a fraction of a percent of nothing, which (after rounding ;) ) comes out to nothing. Further, even if Fizzer uses my code, I wouldn't be the only person to help with WL; not that I know of any other people having donated code, but I do know a bunch of people donating in different ways... they're called "map makers". And last but not least, I think Fizzer, me and the map makers all have something in common: we don't do the work for profit, but because we like it.

(Please pretend I formulated that a lot better; I would've if I had actually been awake, but didn't want to keep you waiting until whenever that happens for this revelation. :p )

If I post the source and the exe, how many people will inspect the source to verify I didn't hide any nasty surprises

You only need one. Just one diligent person who can build it with the same compiler and verify the binaries. The theory is with open source that at least it is verifiable, and I'm sure people check this with the bigger open source projects and would raise the open source alarm if something malevolent was in there. Of course, a small project like this likely won't get checked, but it's better than nothing.

I'd be very surprised if Fizzer manages to make a profit on WL

Indeed, it's never been profitable. That's the next thing I need to address once the mobile version is done :)

not that I know of any other people having donated code

No one has yet - I've had many people offer over the years, but so far everyone has bailed once they realize that working on a game isn't like playing one - it's actual work.

If I get this sorted out well enough for you to include it into WL itself, there's no need for a stand-alone utility anymore. Either way, before sharing the code I'll definitely need to clean it up a bit; there's enough crappy code "out there" as it is. :(

I feel kinda stupid... The common case (number of attackers > number of defenders) is just flipping a weighted coin; a very well known problem: the binomial distribution. Sure, it requires some post-processing (factoring in luck, rounding to integer army numbers correctly, etc.), but the bulk of the work, the summation over the number of armies getting killed, should be replaceable by a direct formula. And at least I'm now sure the problem with high numbers of attackers can be solved; for large N, the Binomial Distribution can be approximated very well with the Normal Distribution.

@Fizzer:
Can you tell me which mathematical (or, more specifically, probability) libraries the WL code has access to? Or better yet, link me to the documentation so I can search for useful functions?
Of course I can hit Wikipedia, MathWorld and WolframAlpha to track down the formula's myself, but if there is a freely available library which will allow you to simply call BinomialCDF ( N, p, x ) then there's no reason for me to reinvent the wheel.

You have to admit it looks cool :)

@Fizzer:
Is the blog post Technology behind WarLight still accurate? Because when I look, haXe's math routines seem, to be quite frank, rather limited... This might get more interesting than I expected.
(On the plus side, if I have to "dumb it down" this far anyway, at least I won't have to bother looking for Pascal equivalents of haXe libraries. ;) Oh yes, every cloud has a silver lining!)

@Moros:
Custom tags would indeed be an incredibly useful feature:

Are you putting it on Uservoice or should I? ;)

@Fizzer:
Is the blog post Technology behind WarLight still accurate? Because when I look, haXe's math routines seem, to be quite frank, rather limited... This might get more interesting than I expected.
(On the plus side, if I have to "dumb it down" this far anyway, at least I won't have to bother looking for Pascal equivalents of haXe libraries. ;) Oh yes, every cloud has a silver lining!)

@Moros:
Custom tags would indeed be an incredibly useful feature:

Are you putting it on Uservoice or should I? ;)

Well, if everyone could pick their own tagline to display beneath their name, a bunch of trolls would pick names like: "WarLight Creator" or "WarLight Admin"
I think if you achieve something great, like getting first on any ladder, or make 5 maps with a rating above 4, you could have a tagline like that.

Here's an example:

Although with players like Zeaban the list could get very long.

Okay, started over pretty much from scratch. At least for the time being I ditched the whole GUI stuff and went old school: who remembers the command line? :) I now have a little utility that works on just about anything, the only remaining limitation is a maximum of 16378 attackers to prevent overflows in the calculation. (Technically there is no limitation of the number of defenders, but if its larger than the number of attackers, the attack always fails.)

I've semi-extensively tested this against the built-in analyser using 60/70/25 (thanks to single player level 1), 60/70/75, 10/90/75 and 90/10/75. For the most part, my results match very closely (yet not perfectly of course). In those last two cases my results where quite different when the number of armies involved was not very small, but I'm pretty sure that's because the WL analyser is wrong (giving a 100% chance of success in the top graph when the expected number of kills, in the bottom graph, is considerably lower than the number of defenders; that can't be right).

You can get the compiled version here (obviously, still no warranty of any kind). I'm not ready yet to open source the whole thing, but the essential part is this:

function KillAllChance ( Attackers, Defenders: Integer; Offence, Defense, Luck: Real ): Real;
var
  nCr: Extended;    // Always an integer, but often much larger than MaxInt
  i: Integer;
  ExpectedKills: Real;
  // No need for an ExpectedChance; the expected number of kills is always the same
  SimKills: Real;
  SimChance: Real;
  TotalKills: Real;
  TotalChance: Real;
  SumChance: Real;
begin
  nCr := 1.0;
  SumChance := 0.0;

  ExpectedKills := Attackers * Offence;    // Constant, might as well calc before loop
  for i := 0 to Attackers do
  begin
    // Keep track of nCr (if i = 0 then it has already been initialized before
    // entering the loop)
    if 0 < i then
      nCr := ( nCr * ( Attackers + 1 - i ) ) / i;

    SimKills := i;
    SimChance := IntPower ( Offence, i ) * IntPower ( 1.0 - Offence, Attackers - i ) * nCr;
    TotalKills := ( 1 - Luck ) * ExpectedKills + Luck * SimKills;

    if TotalKills <= Defenders - 1 then
      TotalChance := 0
    else if TotalKills < Defenders then
      TotalChance := Frac ( TotalKills ) * SimChance
    else
      TotalChance := SimChance;

    SumChance := SumChance + TotalChance;
  end;

  Result := SumChance;
end;



function AttackSuccessChance ( Attackers, Defenders: Integer; Offence, Defense, Luck: Real ): Real;
begin
  if Attackers = Defenders then
  begin
    Result := KillAllChance ( Attackers, Defenders, Offence, Defense, Luck ) *
              ( 1 - KillAllChance ( Defenders, Attackers, Defense, Offence, Luck ) );
  end
  else
    Result := KillAllChance ( Attackers, Defenders, Offence, Defense, Luck );
end;

Obviously, "&lt;=" should be "less-than-or-equal" and "&lt;" should be "less-than", but I can't convince markdown not to double-encode HTML entities... :(

The program linked above has support to output intermediate results in a nice table.

BTW, I deleted the original (the link a few posts above is now dead), because I know it sometimes gives incorrect results (such as for x-vs-x attacks) and I generally have little confidence it doesn't contain more bugs.

Fizzer:

-- Practical stuff --

I think this should be easily portable to haXe, since it only uses very basic mathematics (+, -, *, / and exponentiation to an integer power). The only problem is that, as far as I can tell, haXe has no support for extended precision floating point numbers; can you confirm this? While it is of course possible to use double precision, that would mean I'd have to recheck the upper limit on attackers and verify no problems occur with the nCr calculation.

Currently, any calculation (even for 16378 attackers) takes less than a second. Of course there'll be a performance hit once this runs within Flash, but I expect it will still be much faster than the current code.

How much of a problem is it to bluntly disallow analysing army numbers over 16k? The current analyser is slooow when you ask it to do that, but at least it gets the job done eventually.

-- Theoretical stuff, might not be too relevant --

I can optimized the calculation (at the cost of added complexity; it's actually faster above approximately 250 attackers, hitting 40 or 50 times faster somewhere around 5000 attackers). But, for that I need a statistics library. Good news is, I found one (it's rather old; the site everyone links to doesn't exist any more, I had to pull it out of the Wayback Machine...). It does "dumb down" all the statistics to elementary operations, but it makes extensive use of extended precision floats, so I'm not attempting to "port" that double precision unless you tell me you actually think it's important. Of course, once I have that library, I can also allow even bigger numbers by approximating with a normal distribution (again, not sure if that's worth the effort; how often do attack of 16k+ armies happen on WL?). A final snag might be the license, all it says is:

StatUnit and ISU are still (July 1995) public domain software. The only
condition is that you do not distribute your own modified versions
without explicit reference to their origin and full documentation of the
modifications.

Copyright: Tue Tjur
Copenhagen Business School
Department of Management Science and Statistics

        e-mail tuetjur@cbs.dk

It feels like that is intended for source distribution; I'm not sure how WL would comply with the "full documentation of the modifications" demand. (I haven't tried emailing that address yet by the way.)

Just to be perfectly clear: the code I posted above does NOT contain any of Tue Tjur's code. Also, the program I linked does NOT contain any of his code either. Only the optimised version (which is only on my computer at the moment) and the support for huge army numbers (16k+, currently unimplemented) would require his code.