Explorations with the Tweaker

[I like Serena]

8. What are the chances of getting a hero. It seems that sometimes this chance is unreasonably low. Is that new with Insecticide 1.40h?
Who else has ideas whether or not these chances are off?

I've been exploring OSG and "the Source" (Vanilla and Insecticide) to find out what chance we have on gaining a hero. My conclusion is:

(Contents moved to 2nd post in this thread as a "spoiler".)

[I like Serena]

I've just tweaked my Famous on and set Fame to 200 at the beginning of a new game in Vanilla.
That should give me 10% per turn on an item, 10% chance on mercenaries, and 10% chance on a hero.
But only after about 40 turns a hero showed up. The chance of that happing should be about 1%!! That is, negligible.
What the heck is going on?

[kyrub]

How many opponents do you have, how many heroes do they have?

EDIT: Hmm, no, you're right, this is strange.

[luddite]

Maybe there's a fixed limit where the game doesn't allow heroes to show up for the first 30 turns? Also, just to make sure- you did have enough gold, right?

[kyrub]

I've just tweaked my Famous on and set Fame to 200 at the beginning of a new game in Vanilla.

How much money did you give to yourself, ILSe?
(The game could have tried to give you the bigger heroes that cost more than 100 or 150 based on your 200 fame. Remember the choice of hero happens first, and the game checks for money only after that - if you are short of cash, no hero.)

[I like Serena]

How much money did you give to yourself, ILSe?
(The game could have tried to give you the bigger heroes that cost more than 100 or 150 based on your 200 fame. Remember the choice of hero happens first, and the game checks for money only after that - if you are short of cash, no hero.)

Good point, I hadn't thought of that.
But still, I started with a Dwarven city, meaning I was swimming in gold which I didn't spend. However, it was probably less than 40 turns that I had enough money.
I'll ttry again to make sure.

EDIT: I tried again with vanilla as well as Insecticide 1.40h.
I started with 10000 gp, 200 fame and famous.
Result is 9 heroes in 60 turns (15%) for Vanilla and 6 different heroes in 40 turns (15%) in the same game for Insecticide.
Furthermore 3% mercenaries and 5% items for Vanilla, and 5% mercenaries and 5% items for Insecticide.

My conclusion is that the mechanism is not broken.
Insecticide yields the same results as Vanilla and the percentages are close enough to 10% each to satisfy me.
Weird though that the random generator does not do exactly the same, but yields very similar results in different runs of the same game!

[Jtm]

Weird though that the random generator does not do exactly the same, but yields very similar results in different runs of the same game!

Would you like to elaborate what you mean by this? I do not follow.

The game pseudorandom generator is likely to be based in linear congruential generator (LCG) with Borland C++ parameters (a, c and m). Pseudorandom numbers with LCG are generated with formula of x_new = (a * x_old + c) mod m, where a = 22695477, c = 1 and m = 2^32.

The formula, as you can see, is very simple and fast. Unfortunately the quality of randomness produced by this method is very limited, especially with low-order (right-most) bits. Therefore, I fear MoM probability tests may favor certain numbers more than others, which may have an effect on the results.

I've decided to investigate LCG(22695477, 1, 2^32) and compare the results with randomness theory and Mersenne Twister, currently one of the most used pseudorandom generators in the academic world and proven very reliable. Going to use some pseudorandom tests because I want to know how well does the LCG perform when generating numbers such as 0-99 (assuming this is the way MoM does it when testing probabilities!).

For interested: random number generation basics.

EDIT: So in short, I'm worried about pseudorandom quality and its possible effects on the game 'random' events.

[I like Serena]

Well, I'm worried about random number generation in MoM as well.

I've looked up and traced the code. I can give you the assembly-code if you're interested.

It turns out that typically a random number is determined of n = 10, 15, 100 (percentage), or the number of cities, available spells, or available heroes.

The routine itself if full of shift-operations and rotate-operations, but in the end it seems to put 9 random bits into a number, yielding a number between 0 and 511.
This number is divided by the number n, and the remainder + 1 is returned (1-n).

I don't really know what this will do for random number generation, but is seems to me that low values will have a slightly higher probability than high values.

In other words, when you get a hero, you have a slightly bigger chance on a cheap hero. It would also mean that the chance that a hero comes walking in, should be slightly more than the percentage defined (a low roll of the dice yields a hero).

[I like Serena]

I've finally gotten the information I was looking for on the chances on getting a hero.
It turns out that the chance at the start of the game is 0.9% per turn.
Details are in the top posts.

[Jtm]

I don't really know what this will do for random number generation, but is seems to me that low values will have a slightly higher probability than high values.

In other words, when you get a hero, you have a slightly bigger chance on a cheap hero. It would also mean that the chance that a hero comes walking in, should be slightly more than the percentage defined (a low roll of the dice yields a hero).

Me and ILSe together came up with a C++ implementation for MoM pseudorandom number generator reverse engineered from the assembly code of MoM. So to speak, it was not an easy task. ILSe also deviced an excel version for the generator.

Here are first test results for a simple test for the number distribution. Theoretically numbers should be uniformly distributed (with true randomness that is). To me it seems the pseudorandom number generator is slightly biased and favours the low-end numbers. Going to test it further. In the meantime check the numbers below and comment.

Code:

For instance, I generated 1 billion numbers with range of [1, 10]:
Hit counts per number:
101541157, 101569208, 99635352, 99611700, 99596012,
99612485,  99585801,  99622267, 99627150, 99598868

Or 10000 numbers with range of [1, 100]:
123 112 129 116 119 129 131 111 122 120 (1...10)
126 122  88  97  98  96  78  95  98  92 (11...20)
85   95  91  95 100 105  90  91 102  98 (21...30)
105  97 100  95 100 100  91 110  94  92
94   87  99 116  91 106 109 103  96 108
112  92  90  90  80 103 110  88  84 100
91   93 112 102 106  92  92 106  93 109
91   92 102  76  93 131 100  89 118  85 (71...80)
111  99  85 107 103 112 112  93  89  77 (81...90)
90  104  87  85 112  97  99  78  100 91 (91...100)

I think this would be Insecticide issue because I'd classify problems with random number generation as a bug if not a serious one. In my opinion it requires fixing if it is proven to affect the gameplay. Either me or ILSe is likely to begin a new thread on Insecticide Patch forums concerning this issue.