StreetPass Battle maths 
[Saturday 27th February 2016 at 11:25 pm]
Thomas

So one of the extra minigames in StreetPass Mii Plaza is StreetPass Battle, wherein you defeat a succession of opposing empires in a bestofthree succession of battles with a rockpaperscissorslike type system (type disadvantage wipes out half your troops, then largest army wins). There's some skill in that you can choose how your army is split into cavalry/archers/infantry and then pick which group to send into each battle  with care (and careful use of the spy ability) you can defeat much larger opposing armies.
This all falls apart against the final empire which is a straight run of five battles with each side's entire army. The loser of each battle loses half their troops, and whoever's army is biggest at the end wins. I think the AI's play is random here  certainly it's not the same pattern on each attempt, and rockpaperscissors has limited scope for trying to be smart.
Anyway, the other day I realised that the odds change in steps as my army grows  adding ten soldiers won't change them, but adding enough to put me over 50% of the opposing army size will. So I thought a bit more and started working the various odds out...
Let's start with my current army, which contains 138,121 soldiers. The final empire has I believe a fixed size of 290,143. To win I have to end the five battles with more soldiers than the AI  obviously, if I win all five battles then I win because the AI will be left with 290,143 ÷ 2^{5} = 9066 soldiers (give or take a few depending on how the game rounds the numbers). But how many battles do I actually need to win?
The answer is two. After winning the first the AI has 145,071 soldiers which is still larger than my army, but a second win reduces that to 72,535 which is less than my army. But I then have to maintain that lead, so I must at a minimum tie the remaining three battles. All in all (and if my vague memories of probability math are right), this gives me a chance of winning of (⅓)^{2} × (⅔)^{3} = 0.0329 or about 1 in 30ish which is rubbish. Except there's another path to a win  if I win three battles, I can then lose one and still end up on top (with a result of 69,060 against 36,267). That's got a chance of um... 3 wins times 1 anyresult times 1 tieorwin = (⅓)^{3} × 1 × ⅔ = 0.0247 or 1 in 40. Overall my chance of success is 1 in 17ish which is still rubbish, and tells me that there's really no point challenging the AI until I get a few more soldiers.
Like, oh, another 6951 or so (surprisingly easy as your army grows based on the size of armies that you StreetPass). At that point with my 145,072 soldiers I can achieve a win with any of:
One win and four draws (or better) = ⅓ × (⅔)^{4} = 0.0658 Two wins, a loss, and two draws = (⅓)^{2} × 1 × (⅔)^{2} = 0.0494 Three wins and two losses = (⅓)^{3} × 1^{2} = 0.0370
Basically I have to win at least one more time than the AI does. Added up this gives me a chance of victory of 0.152 or better than 1 in 7. So, waiting until I get a few more troops will more than double my chance of success. Nice!
For even more fun, if I hold off until my army is larger than the AI's then the AI now has to win more than me, and I get a 6 in 7 chance of splatting it. So I could just wait until that happens. Or thinking about it, could I expect a win with fewer troops? I've not mentioned that there is a penalty to losing in that 10% of your army runs away, so I'd have to rebuild between battles... but if my army is large enough, then I could run battles backtoback and have a good overall chance of winning one of them. So, if I have 145,072 × 1.1^{6} = 257,003 soldiers (probably a little more  remember, rounding) then I get 7 attempts before dropping below half the enemy size and have a better than 50% chance of seeing one win out of those attempts. Each attempt still only has a 1 in 7 chance of success so my statement earlier about army size and thresholds still applies  in fact, if I'm patient and wait to replenish my army after each loss I can get by with even less troops. If I lose 6 backtoback battles then overall 111,931 soldiers run away, but if I fight 6 battles at 145,072 and wait to rebuild after each one than I only lose 87,043 troops.
So, I think the most economical way to sensibly see a win is to battle each and every time I reach 145,072 soldiers, and that'll likely take 7 battles and cost me 87,043 soldiers from lost battles. Alternatively there's always the brute force approach  if I ever get to 8,224,097 soldiers then I will win, because the AI can win all five skirmishes and I'll still have more soldiers left... but accumulating that many will take ages and many play coins...
The path to world conquest is not easy, but let us give it our all!
Wentworth, StreetPass Battle 

