msdos dissasembly

Desmet Irkm · Post by **Desmet Irkm** » Sun Dec 18, 2011 10:39 pm

Maven, I guess with 15-sided die you mean random variable which goes from 0 to 15 with equal probabilities. So, rather a 16-sided die with numbering starting from 0. If you have two random variables X, Y with p(X=i)=p(Y=i)=1/n (n=16 in this case, 0<=i<n), then you get p(max(X,Y)=i)=(2*i+1)/n^2 for the max of both. Multiplying these probabilities by 1000 and rounding (and adding 14 as a base) gives the following table:

Code: Select all

This matches your table quite well. The probability for a 14 is about 0.4 percent. If it never appears in practice, it could also mean that the random number generator they use is not very good, and that two random numbers in sequence are not independent enough. Maybe the sequence "0, 0" never appears in the sequence of random numbers generated. (Hey, ZeroZero, any strange coincidence here?)

So: does anybody know which random number generator they use? Some linear congruential one? (And if so with which parameters?) Or did they roll their own RNG, which was also pretty common in those days?

ZeroZero · Post by **ZeroZero** » Sun Dec 18, 2011 10:46 pm

At least in the C64 version they use their own routine giving two pseudo random bytes

Desmet Irkm · Post by **Desmet Irkm** » Sun Dec 18, 2011 10:48 pm

Do you have this routine disassembled? I think it's not in stuff I got from you...

ZeroZero · Post by **ZeroZero** » Sun Dec 18, 2011 10:50 pm

Nah I didn't bother with that... I guess one pseudo RNG is as bad as any other except todays more modern ones, Mersenne Twister and similars

drifting · Post by **drifting** » Sun Dec 18, 2011 11:17 pm

Desmet Irkm wrote:Maven, I guess with 15-sided die you mean random variable which goes from 0 to 15 with equal probabilities. So, rather a 16-sided die with numbering starting from 0.

The algorithm used in this case is:
(random() % 15) + 1
so the result would be between 1 and 15.

The relevant part of the disassembled function:

Code: Select all

call random
and ah,7Fh
div [bp+arg_0]
inc dx

Desmet Irkm · Post by **Desmet Irkm** » Sun Dec 18, 2011 11:18 pm

I think the Mersenne Twister would be overkill for any game... for Monte Carlo simulations however it's worth the effort...
For simple applications like games I think LCGs are still a good choice, as long the parameters aren't chosen too bad (see e.g. TAoCP)

Here's some interesting stuff I just found in wikipedia:

Nevertheless, LCGs may be a good option. For instance, in an embedded system, the amount of memory available is often severely limited. Similarly, in an environment such as a video game console taking a small number of high-order bits of an LCG may well suffice. The low-order bits of LCGs when m is a power of 2 should never be relied on for any degree of randomness whatsoever. Indeed, simply substituting 2n for the modulus term reveals that the low order bits go through very short cycles. In particular, any full-cycle LCG when m is a power of 2 will produce alternately odd and even results.

The interesting thing is, that they always take the low-order bits in BT.

drifting · Post by **drifting** » Sun Dec 18, 2011 11:41 pm

Desmet Irkm wrote: So: does anybody know which random number generator they use? Some linear congruential one? (And if so with which parameters?) Or did they roll their own RNG, which was also pretty common in those days?

The DOS version uses the timer to generate pseudo-random numbers. The _random function is:

Code: Select all

in al,40h
mov ah,al
in al,40h
add al,ah
add ax, randomSeed
mov randomSeed, ax

ZeroZero · Post by **ZeroZero** » Mon Dec 19, 2011 12:17 am

Lol I don't think the MT is overkill for todays computers, not for any game.
On my machine I create more than a million MT rnds per second (for 32-
bit MT), and the memory used is only a few kB.

Since it has a very "natural" distribution of rnds I think it is one of the
best pseudo RNGs available for any purpose. Only alternative could be
a hardware white noise generator, which really would mean overkill, but
otoh gave REAL random numbers.

Desmet Irkm · Post by **Desmet Irkm** » Mon Dec 19, 2011 2:07 pm

ZeroZero wrote:Lol I don't think the MT is overkill for todays computers, not for any game. On my machine I create more than a million MT rnds per second (for 32-bit MT), and the memory used is only a few kB.

Sure, you can do that on modern hardware. What I mean with overkill: you don't really need the stochastic properties and the resulting complexity of MT in any game. You would use MT in simulations, where using RNGs with shorter periods would give wrong results due to spurious correlations in the generated RNs. In a game it just matters that it looks right and that it feels right, and nobody would ever notice the difference, whether you used MT or a simple LCG. So, if I needed to program a game and I had MT in a library I would just use it; however, if I had to implement the RNG myself, I would not bother with MT, and just code a simple LCG.

ZeroZero wrote:Since it has a very "natural" distribution of rnds I think it is one of the best pseudo RNGs available for any purpose. Only alternative could be
a hardware white noise generator, which really would mean overkill, but otoh gave REAL random numbers.

MT is good, but I would doubt that "for any purpose". E.g. cryptographic applications have different needs on RNGs, especially as prectitability is concerned. For creating real numbers also different methods exist, since e.g. scaling integer valued RNs to [0,1] usually results in a not optimal distributions around 0 (see e.g. the RNG used in matlab).
See also this post (http://groups.google.com/group/comp.lan ... 0a4424068/) from George Marsaglia:

The Mersenne Twister (check Google) is an excellent RNG, with k=624. But it requires an elaborate C program and is slower than many RNGs that do as well in tests, have comparable or longer periods and require only a few lines of code.

Maven · Post by **Maven** » Mon Dec 19, 2011 9:33 pm

A fifteen-sided die would have the numbers from 1-15 on it. No zero. Which is what we see from the code Drifting posted.

When I first ran the distribution, I finally recognized the pattern, which is where I came up with the integer square root algorithm I thought it was using. The actual code has a routine with three parameters--How many sides on the die, How many dice to roll, and How many dice to count. As it rolls each die (looping on the second parameter), it puts the number in an array. Then it goes through the array (looping on the third parameter) picking the highest one left to add to the total.

Interestingly enough, for the parameters we are using (roll two dice and pick the highest one) it gives the exact same distribution as the integer square root algorithm.

Using the clock for a random number generator can have disadvantages. Sure, it's truly random if there is a wait for keystroke between randoms. However, my program to roll a thousand characters feeds the program keystrokes, so there's no real random there. Also, generating two randoms in a row will be an issue. Which is exactly what the program does rolling attributes. So I guess the distributions would be a little bit off.

However, for the purposes of the program, I think it's good enough. It looks like they just wanted a little bit better chance to roll high numbers, so you wouldn't have to roll 216 times if you wanted to max three attributes.

Caracas · Post by **Caracas** » Tue Jan 03, 2012 2:31 pm

Just adding this info here, though it's not related to any of the previous...

at $26FE6 in the extracted bard.exe:

Code: Select all

E8 03 D0 07 A0 0F 58 1B 10 27 20 4E

I believe this to be the cost of the spells in the review board.

E8 03 is in fact 03 E8 which is 1000
D0 07 would be 07 D0 which is 2000
A0 0F would be 0F A0 which is 4000
58 1B would be 1B 58 which is 7000
10 27 would be 27 10 which is 10000
20 4E would be 4E 20 which is 20000

Maven · Post by **Maven** » Thu Jan 05, 2012 4:45 am

Either there is something wrong with the random number generator, or drops are not even close to random.

I just played a few hours of a beginning game, repeatedly killing the Samurai Statue. With the exception of one drop of a staff, early on, I am only getting Halbards and Plate Armor. After more than 80 of these drops, I'm getting discouraged. What do I do to get something my Bard can use?

Caracas · Post by **Caracas** » Thu Jan 05, 2012 9:46 am

Sell all the halbards and plate armor and buy shiny stuff at Garths

I hadn't noticed that yet on the samurai statue and I killed quite a few when leveling up chars... I'll keep an eye on it as well.
I assume this is the DOS version, right?

Maven · Post by **Maven** » Thu Jan 12, 2012 1:10 am

Has anyone done any analysis on when the bad guys repel spells? I've seen it happen at low levels on Repel Dead-type spells, but I'm wondering more about Hypnotic Image, Stone Touch, and Death Strike.

I'm building a party of not-too-high-level but high-battle-count characters, and I'm wondering if I get the battle count high enough to always strike first, if I can just cast Hypnotic Image on each group every turn and keep the bad guys from even attacking me. How likely are they to resist the spell?

drifting · Post by **drifting** » Thu Jan 12, 2012 6:46 am

Hypnotic Image, Stone Touch and Death Strike all use the same mechanism for repelling spells (Stone Touch and Death Strike actually use the same function).

A player's "saving throw" value is calculated like this:
1. Character level divided by 2 with a maximum of 18
2. Add 2 if a Luck Shield is equipped
3. Add a class bonus of 1-3 for non-Paladins and 1-6 for Paladins based on the Paladin level
4. Add a luck bonus for each point higher than 15. (18 = +3, 17 = +2, 16 = +1)
5. Add 2 to get the character "save" value.

A monster's value is calculated like this:
1. Take the monster index number (Kobold is 1, Hobbit is 2, etc) and divide by 8
2. Add a random number between 0 and 7.

The spell is repelled if the character's save value is less than the monster's value.

The same calculation is used if the player is attacked by a monster. The character repels the attack if the monster's value is less than the character's value.

The highest value a monster could attain would be 22. That would be and index of 120 or higher plus the maximum 7.