Combat Odds and RNG

[PieceOfMind]

PoM, does the code preserve the remark to Knuth's "Random Numbers" chapter (Volume 2, 3.1.1)?
Adding such comments usually works better than the testing

Actually, making a "bad" random generator for a game is harder than getting it working in an ok way. My issue w/ random generator(s) in the games is the existence of the former not the performance (distribution, sequence length). I'd rather see a game w/ minimal random factor than having it at every possible step - say map generation and that's it.

A very good point, and I mostly agree. It reminds me of one developer comment for DCS Black Shark - a very realistic helicopter flight simulation - that throwing in random components are usually just to cover up an inadequate model (flight model in this case).

However, randomness is pretty integral to the civ experience IMO. I know a pseudo-RNG is strictly deterministic but even still I think if all combat could simply be determined in advance it would be not a civ game. Also, a RNG is about the only thing stopping the player who is currently having their turn from having the absolute initiative during their turn.

 

[ruff_hi]

If you ask it for a random number between 0 and 99 it will give you one and you have no way of predicting what it could be.

Oh, I don't know about that ... let me take a stab at predicting what the number will be ... I bet(!) that it will be between 0 and 99 100% of the time!

Being suspicious of the RNG in civ is about as logical as being suspicious of the dice when playing monopoly.

This is wrong too - I can always roll a 20 in D&D when I really need it.

The whole 'random v even' thing reminds me of a story about a person who was asked to lay some tiles. They had 950 white ones and 50 colored ones. They asked the person who owned the house how they wanted the tiles mixed and they said 'randomly'. That evening after the tiler had layed the tiles, the person complained because two colored tiles were next to each other.

 

[r_rolo1]

Oh, I don't know about that ... let me take a stab at predicting what the number will be ... I bet(!) that it will be between 0 and 99 100% of the time!

You would lose 2% of the times You would win 100% of the times if you said that the result would be inside [0;99]

@PoM

To say the truth my impression is that nowadays the game developers use RNG not so much to cover inadequate models, but to mimic chaoticity, and and that is definitely the case for Civ IV. OFC that chaos is not randomness, but for what matters simple models + RNG makes most of the times a good "make believe" chaos.

 

[bestsss]

PoM,
Upon reflection, I think there is a slight issue w/ the algorithm in fact. There might be a problem w/ the distribution not being uniform. In particular I mean this part:
* ((unsigned long)usNum)) / (MAX_UNSIGNED_SHORT + 1))
I will try to elaborate further later.

Note: that in no way should be a reason to blame the random generator, though.

 

[ruff_hi]

The LCG RNG used by the game is as follows:

unsigned short CvRandom::get(unsigned short usNum, const TCHAR* pszLog)
{
	...

	m_ulRandomSeed = ((RANDOM_A * m_ulRandomSeed) + RANDOM_C);

	unsigned short us = ((unsigned short)((((m_ulRandomSeed >> RANDOM_SHIFT) & MAX_UNSIGNED_SHORT) * ((unsigned long)usNum)) / (MAX_UNSIGNED_SHORT + 1)));

	return us;
}
with the defines 
#define RANDOM_A      (1103515245)
#define RANDOM_C      (12345)
#define RANDOM_SHIFT  (16)

as reported by DanF5771.

Turns out this LCG is pretty typical and is very common.

To be honest, I am a bit surprised with this RNG ... I expected it to take the form ...

random seed = (last random seed * huge prime number) mod (even bigger prime number)
random number = (random seed) / (same 'even bigger prime number')

 

[dirtyparrot]

That's a common cognitive bias in observing events with known probabilities. People associate evenness with randomness even though they are completely opposite things. A RNG system that doesn't generate streaks is not random at all.

My problem isn't that there are streaks (I think that I've mentioned as much), but the nature/length and frequency of the streaks. For example, you should lose 5 straight 90+% odds battle less than 0.001% of the time. My guess is that it happens more often than that (and ditto for the opposite situation).

 

[PieceOfMind]

This is wrong too - I can always roll a 20 in D&D when I really need it.

You're joking right? I don't play D&D but I'm guessing the joke involves rolling two 10s on ten or twelve-sided dice?

The whole 'random v even' thing reminds me of a story about a person who was asked to lay some tiles. They had 950 white ones and 50 colored ones. They asked the person who owned the house how they wanted the tiles mixed and they said 'randomly'. That evening after the tiler had layed the tiles, the person complained because two colored tiles were next to each other.

Nice one. That also reminds me about what I think is called the birthday paradox - greater than 50% odds of two people having a same birthday after only having about 21 (I forget the exact number) people present.

You would lose 2% of the times You would win 100% of the times if you said that the result would be inside [0;99]

@PoM

To say the truth my impression is that nowadays the game developers use RNG not so much to cover inadequate models, but to mimic chaoticity, and and that is definitely the case for Civ IV. OFC that chaos is not randomness, but for what matters simple models + RNG makes most of the times a good "make believe" chaos.

True. I haven't looked at how many other games use RNGs. The point with simulations though is that chaotic effects can arise out of perfectly deterministic models and sometimes it is progress to be able to say a certain random element was replaced. I think DCS is a game where the developers are taking just about everything in the flight model in the right direction, though I'm no expert on flight models so can't really offer any accurate criticisms.

To be honest, I am a bit surprised with this RNG ... I expected it to take the form ...

random seed = (last random seed * huge prime number) mod (even bigger prime number)
random number = (random seed) / (same 'even bigger prime number')

I'm not really familiar with all the existing pseudo-RNGs but I'm curious to whether this one has a name and whether it is better for any reason?

I had the impression that when you are working under a finite field then 'relative primality' was what mattered. In that sense, in this LCG c and m are relatively prime but I'm not sure whether that has any relevance to your comment.

My problem isn't that there are streaks (I think that I've mentioned as much), but the nature/length and frequency of the streaks. For example, you should lose 5 straight 90+% odds battle less than 0.001% of the time. My guess is that it happens more often than that (and ditto for the opposite situation).

Strictly speaking a "streak" of wins or losses does not imply a streak from the RNG. When you win several battles in a row the enemy could have landed lots of separate hits during those wins. (Note that there is one RNG call for every combat "round") This definitely makes it harder to objectively test the RNG for the occurrence sequences that would cause several combat wins in a row. Really you would be looking very locally for string or sequences where a 1 or 0 occurred very frequently but not necessarily in a row. This is another one of the statistical tests (I forget all their names) and while I didn't try this one myself, I haven't seen any evidence that the LCG would fail this test.

 

[ruff_hi]

You're joking right? I don't play D&D but I'm guessing the joke involves rolling two 10s on ten or twelve-sided dice?

of course but that didn't stop me feeling like I could roll a 20 with my 20-sided die when I needed it.

Nice one. That also reminds me about what I think is called the birthday paradox - greater than 50% odds of two people having a same birthday after only having about 21 (I forget the exact number) people present.

23 - we did this from first principles in my 2nd year uni probability course - lots of fun.

True. I haven't looked at how many other games use RNGs. The point with simulations though is that chaotic effects can arise out of perfectly deterministic models and sometimes it is progress to be able to say a certain random element was replaced. I think DCS is a game where the developers are taking just about everything in the flight model in the right direction, though I'm no expert on flight models so can't really offer any accurate criticisms.

The primes just give it a long return period.

 

[JujuLautre]

This is wrong too - I can always roll a 20 in D&D when I really need it.

Too easy

"Ok, roll a 20 sided dice; how much?"
"((not even) looking at the dice) Mmmmmh, 20!"

 

[2Tense]

I hope I just missed it, but did you actually test the odds calculator and not just the RNG?

 

[PieceOfMind]

I hope I just missed it, but did you actually test the odds calculator and not just the RNG?

I did some very limited testing. Really no testing is necessary though because the algorithm is correct. It's like telling students to do long multiplication - you can tell they got it right if they used the correct procedure.

The only real source of error is rounding and usually the effect of that would be very small. So the odds would usually be correct to within 0.1% as far as I can tell. Exceptions to this are outlined in the OP.

 

[2Tense]

I did some very limited testing. Really no testing is necessary though because the algorithm is correct. It's like telling students to do long multiplication - you can tell they got it right if they used the correct procedure.

The only real source of error is rounding and usually the effect of that would be very small. So the odds would usually be correct to within 0.1% as far as I can tell. Exceptions to this are outlined in the OP.

Sorry the engineer in me says "show me". The long division algorithm may be followed correctly, but the student have started with the wrong numbers.

I started getting very lopsided results in Fall From Heaven II. Granted this is a mod, but I would have suspected that the combat odds calc would stay the same. What really drove home my suspicion was when I was I saw that the lopsidedness decreased with the difficulty setting.

I have been doing some very simplistic tests (I'm devoid of Python skills) lining up units in world builder and having at it. This is rather time consuming so I have only run hundreds of test rather than the thousands it should be, but the results are very clear so far. At Diety, a %50 chance wins only about %20 of the time! At the lowest level (don't have the game or results with me now), %50 wins close to %50.

Again this is using the FFH2 mod. A very simple test with vanilla BtS sees fairly accurate odds.

What would be great is if we could get a Python mod that could keep running statistics or better yet a whole "scenario" that could run though thousands of battles with a reasonable unit combination set and report calculated odds vs. results.

 

[2Tense]

I agree with you of course. I think what dirtyparrot was really asking about was whether the statistical test/s that had been undertaken, whatever it/they may be, accounted for the occurrence of streaks.

In his example, the mean result looks ok of course, but the streaks do not. I reckon an interesting trick question to ask people would be this:

If a person tosses a coin 20 times in a row, which of the following results is the most likely?

A) HTHTHTHTHTHTHTHTHTHT
B) HHHHHHHHHHTTTTTTTTTT
C) HHHHHHHHHHHHHHHHHHHH
D) none of the above




That's a good idea actually. I've written a bit about that before, as you'd know, and I'm sure it would be worthwhile to include another bolded "frequently asked question" that relates to the bestdefender selection.

I'll get to that soon. And by the way, it is yet another thing that sorta gets mixed up with the RNG and combat odds discussions often.

And this is why statisticians get a bad rep...

While is it is very clever to show this example and smugly state all 3 are equally likely, it is in a sense dishonest. It is absolutely mathematically correct, but the devious implication is that a streak of all heads or tails is just as likely as half heads and half tails, and that is absolutely false.

 

[ruff_hi]

While is it is very clever to show this example and smugly state all 3 are equally likely, it is in a sense dishonest. It is absolutely mathematically correct, but the devious implication is that a streak of all heads or tails is just as likely as half heads and half tails, and that is absolutely false.

The problem that you will have difficulty explaining away is that all three are equally likely. The chance of getting a H is 50%. The chance of getting a T is 50%.

So, with a single flip of the coin, your possible outcomes are:

• H
• T

Each of those has a 50% chance of occurring.

Now consider a single coin twice ...

• HH
• HT
• TH
• TT

Each of those has a 25% chance of occurring. However, a H and a T occurs 50% of the time. Specifying the order changes the probability. This situation can be extropolated to multiple tosses of a coin.

• HHHHTHTTTH
• HTTTHHTTHH
• THTTHHHTTT
• TTTTTHHHTH

Here is 4 possible outcomes from tossing a coin 10 times. There are 2^10 - 4 (or 1020) more that I haven't bothered to list. Each outcome has a 50%^10 probability of occurring.

Now, if you asked "What is the probability of exactly 5 heads in 10 tosses of a coin?" The formula for choosing r from n; where order does not matter and no repetitions are allowed is n!/r!(n-r)! The '!' represents factorial. n! = n x (n-1)! So 5! = 5 x 4 x 3 x 2 x 1

For 5 heads from 10 coin tosses ... 10! / 5! x 5! = (10 x 9 x 8 x 7 x 6) / (5 x 4 x 3 x 2 x 1) = 30240 / 120 = 252. There are 2^10 possible outcomes (1024) so your probability is 252 / 1024 or 24.6%

The real question I have with the civ4 random number engine is how random it is. I will be running some tests on that this week and putting up some results.

 

[PieceOfMind]

Sorry the engineer in me says "show me". The long division algorithm may be followed correctly, but the student have started with the wrong numbers.

I started getting very lopsided results in Fall From Heaven II. Granted this is a mod, but I would have suspected that the combat odds calc would stay the same. What really drove home my suspicion was when I was I saw that the lopsidedness decreased with the difficulty setting.

I have been doing some very simplistic tests (I'm devoid of Python skills) lining up units in world builder and having at it. This is rather time consuming so I have only run hundreds of test rather than the thousands it should be, but the results are very clear so far. At Diety, a %50 chance wins only about %20 of the time! At the lowest level (don't have the game or results with me now), %50 wins close to %50.

Again this is using the FFH2 mod. A very simple test with vanilla BtS sees fairly accurate odds.

I should add that I have not looked at the FFH mod in terms of odds or RNG. It's quite possible the creators of the mod fiddled with combat mechanics and did not correctly take into account how it would affect combat odds. All of the claims I have made in this thread relate only to unmodded BtS and to some extent the earlier versions including vanilla and Warlords.

What would be great is if we could get a Python mod that could keep running statistics or better yet a whole "scenario" that could run though thousands of battles with a reasonable unit combination set and report calculated odds vs. results.

In my honest opinion, that would be a waste of time. Better would be to run statistical tests on the actual RNG used by the game aka the LCG. I have done a couple of the simplest statistical tests on the RNG and have found it produced adequate random strings of numbers under various criteria.

I have attached a document containing the formulas I derived that calculate combat odds. They allow you to work out combat odds for most battles. The forced withdrawal of siege units was not yet included but the adaptation for such combats was not difficult.

As a maths graduate myself I appreciate and respect the position of a skeptic or a critical thinker and I've no problem with anyone wanting to convince themselves of the correctness of the formulae, but I guess all I can do is offer my word.

Towards a General Combat Odds Calculator (pdf)

 

[PieceOfMind]

And this is why statisticians get a bad rep...

While is it is very clever to show this example and smugly state all 3 are equally likely, it is in a sense dishonest. It is absolutely mathematically correct, but the devious implication is that a streak of all heads or tails is just as likely as half heads and half tails, and that is absolutely false.

Actually my impression is that statisticians don't get the bad rep. It is the people who misuse statistics who give the art of statistics a bad rep. The main fallacy that is propagated in the popular media all the time is that a statistical corollation implies a causal link - probably the main thing that makes statisticians cringe every time.

I had the privilege of being taught by a practising statistician and was amazed at how much the discipline is misused outside of the circle of statisticians.

Anyway, regarding the question I posed earlier, I did say it is a trick question. Usually trick questions are called that because they don't enlighten people but instead frustrate them because they fall victim to some fallacy.

Having said that, the question still does hint at a common fallacy that many people fall for. I think I said this earlier in the thread as well, but if you produce a random string of 100 coin tosses (whether you use a RNG or real coin it doesn't matter) and then afterwards you look at the string, combing it for irregularities, chances are high that you'll find one. But if you were to go and calculate the odds of that particular irregularity you'd discover the odds of that occurrence were low.

Retrospectively analysing a random string is a bad idea unless you are careful in how you do it. People frequently complain when they experience a streak but how many people do you hear complain about the lack of streaks? This alone should be enough to suggest that the collective intuition cannot be trusted.

The point with the trick question was that all of those outcomes are extremely unlikely. Your judgement of why it was misleading was based entirely on the fact that you were counting the tails and heads and using the fact that you are more likely to be close to the mean than any other value. Anyone who is actually confused by that question should humbly admit their probabilistic intuition is not infallible.

 

[TheMeInTeam]

Actually my impression is that statisticians don't get the bad rep. It is the people who misuse statistics who give the art of statistics a bad rep. The main fallacy that is propagated in the popular media all the time is that a statistical corollation implies a causal link - probably the main thing that makes statisticians cringe every time.

Statistics don't lie, but interpretations of them surely do. This really annoys me too but it is a very common error made even by those in my family...well some of them. Of course, sometimes stats interpretations can be manipulated deliberately. Remember, at one point in time, the world was flat, supported by a giant turtle (turtles all the way down). Evidence to the contrary was squelched...and people on average know little enough about statistical outcomes today to buy similar if less barbaric manipulations.

As for losing, it sucks. Combat w/o overwhelming #s or taking advantage of fixed damage (or impossible-to-retaliate situations like fighters against rifles) has some inherent risks, and they're usually low. But man, does it suck when the low odds finally happen.

But then you have those games like the one where my choking quecha killed an axe...I forgot to check the odds on that one but I can't imagine them being stellar .

The point with the trick question was that all of those outcomes are extremely unlikely. Your judgement of why it was misleading was based entirely on the fact that you were counting the tails and heads and using the fact that you are more likely to be close to the mean than any other value. Anyone who is actually confused by that question should humbly admit their probabilistic intuition is not infallible.

The trick question was easy enough. But I strongly doubt anybody can keep mental tabs of outcomes in civ IV with enough intuition to accurately detect whether the RNG is operating proplerly .

 

[ruff_hi]

But I strongly doubt anybody can keep mental tabs of outcomes in civ IV with enough intuition to accurately detect whether the RNG is operating proplerly .

I have a game report somewhere (cannot find it at the moment) where I used the BUG logger to keep track of all of the battles (BUG logger records the probability of victory as well as the result). I extracted the information, grouped the battles into deciles (0% to 9.99% chance of victory as the first bucket) and then plotted victory percentages against these deciles. The line I got was pretty straight, running from around 5% up to about 95%.

Sure, that is only 1 games worth of data but it was (IIRC) an ALWAYS WAR game that I won.

 

[TheLazyHase]

Statistics don't lie, but interpretations of them surely do. This really annoys me too but it is a very common error made even by those in my family...well some of them. Of course, sometimes stats interpretations can be manipulated deliberately. Remember, at one point in time, the world was flat, supported by a giant turtle (turtles all the way down). Evidence to the contrary was squelched...and people on average know little enough about statistical outcomes today to buy similar if less barbaric manipulations.

And in addition, people are naturally terrible with statistic and randomness. What look random for an human is something not even near to a real random thing. Human will every time try to find reasons and link everywhere, even if nothing really point out a link. It's most of the time very beneficial, but if anything it mean that human perception cannot be trusted for finding what is random or unrelated.

 

[r_rolo1]

And this is why statisticians get a bad rep...

While is it is very clever to show this example and smugly state all 3 are equally likely, it is in a sense dishonest. It is absolutely mathematically correct, but the devious implication is that a streak of all heads or tails is just as likely as half heads and half tails, and that is absolutely false.

Sorry but you are being ( maybe inconsciously ) devious here

The question Piece of Mind made is clear as water: shows 3 particular outcomes and ask which one is more likely. He never asked if it was more likely to get a straight heads or tails instead of a mess with half tails and half heads ... Like my teacher in thermodynamics said when explaining Boltzman statistical explanation of the 2nd law of Thermodynamics " There ia very restrict number of ways of having a bedroom tidy, but there is a very big number of ways of having a bedroom in a mess , and that is why most of the rooms will become a mess without a conscious effort to tidy them. But any of those diferent ways of being a mess is as much unique as the the ones of being tidy, and that is the explanation for people that are used to have the bedroom in a mess get sudently lost if other person goes there and changes their mess into a diferent one "

In other words: you confused ( consciously or not ) one very specific way of having a mess with having a mess in general and then blamed the person that asked the question of being devious. Not cricket, my friend, not cricket....