Angband.oook.cz
Angband.oook.cz
AboutVariantsLadderForumCompetitionComicScreenshotsFunniesLinks

Go Back   Angband Forums > Angband > Development

Reply
 
Thread Tools Display Modes
Old July 20, 2013, 10:44   #1
rhutson
Rookie
 
Join Date: Jul 2013
Location: In the Misty Mountains
Posts: 23
rhutson is on a distinguished road
Why the Angband random number generator is currently limited to 28 bits explained

I recently downloaded Angband v3.4.1, and I couldn't help but be curious to see how the RNG had changed (in z-rand.c). I see that RNG v2 has been replaced with RNG v3, but that the 28 bit code remains. I'm guessing that no one has changed it since they don't know why it was written in such an odd way.

For reference, following are excerpts from the current code:
HTML Code:
        /* Partition size */
        n = (0x10000000 / m);
  ...
                while (1) {
                        /* Get the next pseudorandom number */
                        r = WELLRNG1024a();

                        /* Mutate a 28-bit "random" number */
                        r = ((r >> 4) & 0x0FFFFFFF) / n;

                        /* Done */
                        if (r < m) break;
                }
        }
Before Ben and I changed the code, random numbers were generated with the library's random() function and implemented in the simple random() % N style. But then I discovered a "bug" in the BSD random() function being that the 4 lower bits of "random" numbers actually followed only one of 4 sequences depending upon how the RNG was seeded.

Specifically, for all values of N,

srandom(N); while(1) printf("%ld\n", random() & 0xF);

would print the same sequence of numbers as:

srandom(N%4); while(1) printf("%ld\n", random() & 0xF);

This means that the commonly used random() & 1 could only follow one of 4 sequences. (It's odd that no one noticed the bug for so long.)

I did a little research into the algorithm used in random(), and it was documented that the upper bits were "more random" than the lower bits, but not to the degree of my discovery. Soon after I publicized the bug in random(), a CERT alert was issued about random() and TCP packet sequence numbers. I'm guessing that wasn't a coincidence as I know that software engineers from Sun Microsystems were playing the game at that time.

My solution to the problem was to use the same algorithm but to rewrite the random() code in a different manner (for copyright reasons) and to include my code into the game (for portability reasons). Then I shifted off the useless 4 lower bits of the pseduorandom number. I had been waiting for an excuse to use my unbiased partitioning algorithm, so that got incorporated in as well. Before the partitioning code, "randomness" was somewhat proportionally correlated with the size of the maximun random number requested (N). After the partitioning code, "randomness" was inversely proportional to the size of N. (Which was desirable since I don't recall large random numbers ever being requested.)

As a new RNG has been incorporated in Angband, which presumably is better than the previous one, there shouldn't be any reason to restrict the RNG to 28 bit numbers. (A search indicates this has caused a problem in the past.) If Angband's developers want to retain the unbiased partitioning code, it's trivial to change it to a 31 bit RNG. (Change two constants and then shift r >> 1 instead of r >> 4.) The

The game should work as well as the WELL RNG without the partitioning code. I wanted an unbiased RNG, and Angband still has one. I hope that the partitioning code is retained, yet I am willing to point out that it is optional.

Last edited by rhutson; July 22, 2013 at 03:14.
rhutson is offline   Reply With Quote
Old July 20, 2013, 17:03   #2
Derakon
Prophet
 
Derakon's Avatar
 
Join Date: Dec 2009
Posts: 8,500
Derakon is on a distinguished road
That's very interesting! Thanks for the information and the brief history lesson. Also, it's always nice to see another "old" dev return. Welcome back!
Derakon is offline   Reply With Quote
Old July 20, 2013, 22:41   #3
Magnate
Angband Devteam member
 
Join Date: May 2007
Location: London, UK
Posts: 5,057
Magnate is on a distinguished road
Send a message via MSN to Magnate Send a message via Yahoo to Magnate
Quote:
Originally Posted by Derakon View Post
That's very interesting! Thanks for the information and the brief history lesson. Also, it's always nice to see another "old" dev return. Welcome back!
Seconded - many thanks for the explanation. d_m implemented the WELL RNG but I don't see any reason not to keep the partitioning code.
__________________
"3.4 is much better than 3.1, 3.2 or 3.3. It still is easier than 3.0.9, but it is more convenient to play without being ridiculously easy, so it is my new favorite of the versions." - Timo Pietila
Magnate is offline   Reply With Quote
Old July 21, 2013, 03:32   #4
rhutson
Rookie
 
Join Date: Jul 2013
Location: In the Misty Mountains
Posts: 23
rhutson is on a distinguished road
Quote:
Originally Posted by Magnate View Post
Seconded - many thanks for the explanation. d_m implemented the WELL RNG but I don't see any reason not to keep the partitioning code.
You're both welcomed! I was having a discussion on another forum in which I reminisced, "I remember going to campus to play Moria on a Dec terminal." That reminded me of Angband, so I decided to see what had become of the game.

I'm glad that we're in agreement on the partitioning code. Before the RNG was a function call, it was implemented as a C macro. Requests for a random number with a constant such a RANDOM(8) could be optimized by the compiler to avoid the use of a division assembly language instruction (or modulus if the assembly language had that). There was concern at the time that the combined overhead of a function with a division in it would slow down the game for some players. I've been playing for 2 1/2 hours now, and Angband has ony used 1 minute and 25 seconds of CPU time on a 5 year old Mac mini (2.4 GHz Intel Core Duo). I'd say that the game is sufficiently efficient.

Correction: That was an 1 hour and 25 minutes of CPU time, which is much more sensible than my prior claim. Obviously I need to be using larger fonts.

I must say that I am having a lot of fun. I've forgotten a few commands, but when it comes to game playing tactics that's like riding a bicycle. I'm coming across some new features. This is reminding me of the first time that I played Angband. I chose a human ranger (as that was my first character), and Farmer Maggot has dropped me a nice short bow.

Thanks to Ben for saving the game, and to all of the subsequent developers for your work!

Last edited by rhutson; July 21, 2013 at 06:19.
rhutson is offline   Reply With Quote
Old July 21, 2013, 11:33   #5
Pete Mack
Prophet
 
Join Date: Apr 2007
Location: Seattle, WA
Posts: 4,980
Donated: $40
Pete Mack is on a distinguished road
There's a lot more choice in playing Angband these days, much less roguelikes in general. If you ever played rogue proper, I'd give Sil a chance. It's a much more direct descendant than Angband, although it is derived from the (much-improved!) Angband codebase.

And I agree: Welcome back!
Pete Mack is offline   Reply With Quote
Old August 13, 2013, 10:50   #6
jrodman
Apprentice
 
Join Date: Feb 2009
Posts: 56
jrodman is on a distinguished road
I think this type of weakness in system rand functions was fairly common at some point. I ship some software on hpux and aix so I still don't trust system rand for anything other than some vaguely varying number. I use the openssl rand for useful values.

Then again my software doesn't need rand very often.
jrodman is offline   Reply With Quote
Old June 20, 2016, 08:40   #7
brbrbr
Adept
 
Join Date: Sep 2015
Posts: 104
brbrbr is on a distinguished road
I am not developer, but very interested:

1) It's year 2016 and the 28 bit mutation remains. Maybe it's time to remove it from z-rand.c as rhutson suggested ????

2) void Rand_init(void)
{
/* Init RNG */
if (Rand_quick) {
....
Rand_state_init(seed);

Is it a bug? Rand_state_init initialize the COMPLEX rng, but it seems to be invoked withing QUICK rng block.

3) There seems to be error in z-rand.h function randint0
If the intention is to generate 0 < X < M, then definition should be:
#define randint0(M) ((s32b) Rand_div(M+1)),
not
#define randint0(M) ((s32b) Rand_div(M)),

The bug means all randint0 generate 1 lower values.

Last edited by brbrbr; June 20, 2016 at 12:21.
brbrbr is offline   Reply With Quote
Old June 20, 2016, 12:24   #8
AnonymousHero
Veteran
 
AnonymousHero's Avatar
 
Join Date: Jun 2007
Posts: 1,365
AnonymousHero is on a distinguished road
Quote:
Originally Posted by brbrbr View Post
2) void Rand_init(void)
{
/* Init RNG */
if (Rand_quick) {
....
Rand_state_init(seed);

Is it a bug? Rand_state_init initialize the COMPLEX rng, but it seems to be invoked withing Rand_quick = TRUE block, which is the opposite.
Without looking at the code at all... not sure why Rand_quick even exists any more. Modern machines should be fast enough to use WELLRNG for all random number generation.

(Maybe it's something to do with having to force a seed and WELLRNG being slow at that?)

Quote:
Originally Posted by brbrbr View Post
3) while (1) {
/* Get the next pseudorandom number */
r = WELLRNG1024a();

It seems ineffective to cycle through random values, until you find one, which is less than M.
You're certainly right that using a while loop to do this is absolutely horrible for performance -- not sure why it's done this way (but see below). I'm sure there are much more efficient ways to do it, though I don't know the right search keywords to find an appropriate algorithm on Wikipedia.

Quote:
Originally Posted by brbrbr View Post
Would it be much faster to do
r = WELLRNG10245 % m +1
???
Yes, but that method can lead to bias in that the resulting values are not perfectly uniformly distributed across the entire interval. The problem becomes obvious if you look at the whole output range of WELLRNG -- let's assume 32 bits -- and then look at what happens of you map all the numbers in that range using f(x) = x % m. Now, if (2^32 % m == 0) then everything is fine and every "point" on the [0, m-1] interval is hit exactly the same number of times. In any other case, you'll have some "points" on the [0, m-1] interval which get hit once more than some of the other points. This leads to (very subtle) bias in the output.

The "while (1)" method doesn't suffer from this bias.

I'm not sure if this actually matters in practice for a game like Angband, but it obviously matters for statistical applications.
AnonymousHero is offline   Reply With Quote
Old June 21, 2016, 08:14   #9
brbrbr
Adept
 
Join Date: Sep 2015
Posts: 104
brbrbr is on a distinguished road
Quote:
Originally Posted by AnonymousHero View Post

Yes, but that method can lead to bias in that the resulting values are not perfectly uniformly distributed across the entire interval. The "while (1)" method doesn't suffer from this bias.

I'm not sure if this actually matters in practice for a game like Angband, but it obviously matters for statistical applications.
Ok, that explains why simple modulo was not used.

Now, I have an issue understanding the "Rand_div" code.
For example:
Code:
/* Partition size */
n = (0x10000000 / m);
The usual call for randint is with m=100(decimal), that means the partitions are not of same size, which MAY bias the random number generator.

It would be much cleaner and faster to use unbiased modulo code:
Code:
#define RAND_MAX=0xFFFFFFFF; 
while(1)
{
  r =  WELLRNG1024a();
  if (r < RAND_MAX - RAND_MAX % m)
    return r % m;
}
That code will run 1 time most of the time. Unbiased.


The other issue is more serious, I think.
randint0 return values from 0 to m-1, not from 0 to m.
For example, the "desperate" spell chance calculation
randint0(100) < 50 gives max 99<50, not 100<50
Which is, probably OK, because 0 is also a valid value.
I havent' checked all the code for all randint0 calls, just worried the description is not correct and function may be misused.
brbrbr is offline   Reply With Quote
Old June 21, 2016, 13:03   #10
AnonymousHero
Veteran
 
AnonymousHero's Avatar
 
Join Date: Jun 2007
Posts: 1,365
AnonymousHero is on a distinguished road
Quote:
Originally Posted by brbrbr View Post
It would be much cleaner and faster to use unbiased modulo code:
Code:
#define RAND_MAX=0xFFFFFFFF; 
while(1)
{
  r =  WELLRNG1024a();
  if (r < RAND_MAX - RAND_MAX % m)
    return r % m;
}
That code will run 1 time most of the time. Unbiased.
Yup, that method occurred to me a few minutes after posting . AFAICT it should work for unbiased uniform randomness.

The code has an error in the #define (there should be no "="), and may have other issues wrt. overflow -- not sure without thinking about it a bit more.
AnonymousHero is offline   Reply With Quote
Reply

Tags
rng


Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)
 
Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump

Similar Threads
Thread Thread Starter Forum Replies Last Post
Random map generator. LostTemplar Development 0 May 16, 2013 22:05
Limited Iron Man Mode EpicMan Vanilla 3 December 4, 2010 06:10
Random number generation? Chud Vanilla 21 November 8, 2010 19:00
Mechanic idea for a variant...monster generator Jude Variants 44 November 19, 2008 21:44
Angband Variant without random levels? TJA Variants 32 August 18, 2007 17:47


All times are GMT +1. The time now is 06:10.


Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2018, vBulletin Solutions Inc.