Lack of randomness sometimes when compiling for Glulx

Authoring Inform 7
1

I’ve been trying to get my head around a curiosity which I had noticed before: when compiling for Glulx, even when the random number generator should be non-deterministic it sometimes is not.

Experimenting further, this seems to be the case when repeatedly calling the random number generator for a range between 1 and 2^n, in which instance the numbers generated seem to always follow one of 2^n distinct but reproducible sequences.

e.g.

"Testing_Choosing_A_Random_Number" by PB

Lab is a room.

The File of PseudoRandom Results is called "PseudoRandomResults".

To say choose the password: say "[one of]Cappuccino[or]Americano[or]Latte[or]Flat White[purely at random]".
Password is a text that varies.
When play begins:
	if the The File of PseudoRandom Results exists:
		read the File of PseudoRandom Results into Table of PseudoRandom Results;
	let t be a pseudorandom sequence of 10 up to 4;
	if there is a randnumber of t in the Table of PseudoRandom Results:
		choose row with randnumber of t in Table of PseudoRandom Results;
		now the count entry is the count entry + 1;
	otherwise:
		choose a blank row in the Table of PseudoRandom Results;
		now the randnumber entry is t;
		now the count entry is 1;
	write the File Of PseudoRandom Results from the Table of PseudoRandom Results;
	showme the contents of the Table of PseudoRandom Results;

To decide which text is a pseudorandom sequence of (q - a number) up to (n - a number):
	let t be "";
	repeat with s running from 1 to q:
		let r be a random number from 1 to n;
		now t is the substituted form of "[t][r]";
	decide on t.
		
Table of PseudoRandom Results
randnumber (text)	count (number)
with 16 blank rows

leads (after 51 runs) to output like:

Table of PseudoRandom Results
(row 1) | 3234132431 | 16 |
(row 2) | 3424412223 | 12 |
(row 3) | 3214332411 | 12 |
(row 4) | 3444212243 | 11 |
(row 5) | – –
(row 6) | – –
(row 7) | – –
(row 8) | – –
(row 9) | – –
(row 10) | – –
(row 11) | – –
(row 12) | – –
(row 13) | – –
(row 14) | – –
(row 15) | – –
(row 16) | – –

i.e. despite each digit being in theory independently randomly generated, in fact they only appear (randomly) in one of 4 distinct sequences each time the story file is opened- and, unhelpfully, the first in the sequence is always 3. Meaning that if during ‘When play begins…’ we are randomly choosing one of 4 passswords, e.g.

To say choose the password: say "[one of]Cappuccino[or]Americano[or]Latte[or]Flat White[purely at random]".

we always get the third password (shown here after 20 runs of the story):

Table of PseudoRandom Results
(row 1) | Latte | 20 |
(row 2) | – –
(row 3) | – –
(row 4) | – –

This happens in similar fashion if there are 8 alternatives, when there are 8 possible sequences and the first result is also always 3 or 7:

Table of PseudoRandom Results
(row 1) | 3618732415 | 5 |
(row 2) | 7468452663 | 8 |
(row 3) | 7428852623 | 7 |
(row 4) | 3658332455 | 8 |
(row 5) | 3238172831 | 4 |
(row 6) | 7888612287 | 8 |
(row 7) | 7848212247 | 5 |
(row 8) | 3278572871 | 5 |
(row 9) | – –
(row 10) | – –

or with 16 alternatives, when there are 16 possible sequences and the first result is always 03, 07, 11 or 15:

Table of PseudoRandom Results
(row 1) | 07080816140102021615 | 17 |
(row 2) | 03060116151110040113 | 11 |
(row 3) | 15121416041302140603 | 7 |
(row 4) | 07081616060102020815 | 12 |
(row 5) | 03060916071110040913 | 7 |
(row 6) | 11021116091510081109 | 12 |
(row 7) | 11100716050710160701 | 13 |
(row 8) | 07160416100902101207 | 8 |
(row 9) | 15120616121302141403 | 11 |
(row 10) | 11101516130710161501 | 13 |
(row 11) | 03141316110310121305 | 11 |
(row 12) | 15040216080502061011 | 10 |
(row 13) | 03140516030310120505 | 11 |
(row 14) | 15041016160502060211 | 5 |
(row 15) | 11020316011510080309 | 8 |
(row 16) | 07161216020902100407 | 2 |

or with 2 alternatives, when there are only 2 possible sequences, both starting with 1, 2

Table of PseudoRandom Results
(row 1) | 1222212221 | 19 |
(row 2) | 1212112211 | 18 |
(row 3) | – –
(row 4) | – –

As I understand it, the random number generator is provided by the interpreter, and the interpreter may depend on an OS function, so others’ mileage may vary. I get similar results with both Glulxe and Git on a Windows 10 laptop in the Windows IDE, and directly running Windows Glulxe 0.6.0 (Windows Glk 1.52) but I see it in Lectrote 1.4.5 only with Git- not with Glulxe or Quixe.

This code as written runs with 6M62, but I see same phenomenon with 10.1.2. This behaviour is not seen when compiling for Z-machine.

@zarf , any thoughts? What is behind this observation, and what is the best way to circumvent it while using the IDE?

EDIT: code fixed to work around a bug preventing compilation in Ver 10.1.2

7 Likes
2

Well, the simplest way to circumvent it is to use your own PRNG. That’ll ensure a good distribution across all interpreters. There’s an implementation of xorshift here.

Of course, you still need to get a good seed somehow. But an interpreter that doesn’t provide any randomness whatsoever is a pathological case, and even then you can use the RTC if you really need to. (Though a pathological interpreter could sabotage that too, I suppose…)

1 Like
3

I did a quick test in I6, and I did not see this problem. The interpreter is seeded by default with the time (in seconds), so unless you run it twice in the same second, you get different output.

But when I tested your code in I7, I did see the same output every time! (This was testing with 9.3.)

So this is a problem somewhere in I7’s randomness guts.

EDIT: Actually I didn’t entirely catch what you were doing with the data file. Let me look at this again.

4

Yeah, when I run this on Mac, the results are as random as desired. Unless you run it a lot of times from a script, because then most of the runs are in the same clock second and get the same random seed.

I know DavidK recently put in a change to Glulxe’s default RNG for Unix: Optionally use built-in RNG for OS_UNIX by DavidKinder · Pull Request #30 · erkyrath/glulxe · GitHub

I don’t know if that affects this behavior though.

5

I suspect not, because repeatedly calling the Glulx @random L1 S1 opcode with L1 equal to 4 leads to exactly the same result :thinking:

Indeed, repeatedly calling @random L1 S1 with any L1 which is 2^n leads to a sequence of S1s with one of 2^n defined sequences of S1%(2^n), exactly as when using an Inform 7 phrase.

Although S1%(2^n)… seems predictable, S1/(L1/(2^n))… appears not to be, so that’s one possible solution: this appears to work for for 9.3/6M62-

Section - Fix Glulx PRNG (for Glulx only)

Include (-
Replace random;

[ random range result mod;
		mod = MAX_POSITIVE_NUMBER-(MAX_POSITIVE_NUMBER % range);
		@random mod result;
		result = (result/(mod/range))+1;
		return result;
];
-) before "Definitions.i6t".

Unfortunately, it doesn’t seem so straightforward to replace Inform 6’s inbuilt random() function in 10.1.2- the ... replacing "random" syntax inserts the function into the compiled I6 code but doesn’t replace the inbuilt random(). Any ideas how to achieve that? Replace random; is not permitted syntax in inclusions or kits, it would seem.

6

You don’t have the “Make random outcomes predictable when testing” setting enabled do you?

In your auto.inf, what is RNG_SEED_AT_START_OF_PLAY set to?

Edit: Well I can see this happening when compiling to 6M62 within 10.1, and that setting isn’t enabled. Very odd. It happens for both Glulxe and Git, though they each have a different set of 4 numbers they generate. From my testing it only happens when you restart the interpreter - restarting from within the game produces good numbers.

Quixe seems unaffected. As does Windows Git.

I suspect there’s an issue with the RNG in the IDE terps. I don’t think it’s the Inform 7 code forcing the RNG into a seeded state. There is startup code which does that, but I’m pretty sure it’s not running.

7

Here’s something of a gaffer tape non-I6 workaround that can be easily implemented across the board in 6M62 and 10.1.2:

Summary 
Section - Fix the Glulx/Git pseudo-random number generator bug

[This fixes a bug with the pseudo-random number generator of the Glulx and Git interpreters shipped with the Windows IDE up to at least Ver 10.1.2]
[The bug causes partially-predictable sequences of values to be generated when a random range is 1 to 2^n wide, e.g. 1 to 4, 1 to 16 etc.]
[After any given number of calls to the PRNG the values will follow within one of 2^n distinct and predictable sequences, although which of the 2^n sequences they will follow is not predictable in advance]
[This does however mean that at certain points in the sequence the result is completely predictable- when all sequences have the same value-, e.g. for the first random number generated with the Glulx PRNG, if the range is 1-4 the result is ALWAYS 3, because all 4 potential sequences start with 3]
[
(sequence 1)   3424412223...
(sequence 2)   3214332411...
(sequence 3)   3444212243...
(sequence 4)   3234132431...
]
[This means for example that if we start the game by 'randomly' picking one of 4 passwords, or saying one of 4 phrases 'purely at random' it will invariably be the 3rd password that is picked, or the third phrase that is said.]
[similarly, the 4th time the PRNG is run, if the range is 1-4 the result is always 4, the 10th time the result is always 1 or 3 etc.]
[Furthermore, if it is possible to establish which sequence is being followed and from where, ALL subsequent results are ENTIRELY predictable]
[This faulty behaviour appears intrinsic to the PRGN algorithm and is independent of how it is seeded]
[Other versions of Git and Glulx in the wild may use different PRGN algorithms, or may use different operating system algorithms, and may not be affected by the bug at all.]
[It is easy to test for this with the Glulx interpreter:
	
First when play begins: say "This story is brought to you by the number [one of]1[or]2[or]3[or]4[purely at random]."

If the bug is present, the number will always be 3.

Or for Git:

First when play begins:
	let n be a random number between 1 and 32633;
	let n be a random number between 1 and 32633;
	say "This story is brought to you by the number [one of]1[or]2[or]3[or]4[purely at random]."

If the bug is present, the number will always be 4 (the third number in all 4 sequences is 4, for the Git interpreter).
]
[One workaround is to prime randomisation before play beegins by calling the PRGN a random number of times, so that it is unknown both from where, and in which, of the potential fixed sequences subsequent results are being drawn.  This will work well for situations likely to arise in IF, where the random range is likely to be quite low- under 1000]
[Another approach is to replace I6's random() function to eliminate this bug, which can be easily done before Ver 10 but is not so straightforward thereafter.]
[This fix adopts the former approach and should work for any version of Inform 7 shipped with the affected Glulx or Git interpreter]
[Again, due to the quirks of the PRNG, it's more effective to choose a prime number (possibly simply an odd number) for the upper bound of the number of times the PRNG will run during priming]
[And, with Git, we also need to 'warm up' the PRNG before even calling our high prime random range]

The prime the random number generator rule is listed after the seed random number generator rule in the startup rules.
The prime the random number generator rule is listed before the update chronological records rule in the startup rules.
This is the prime the random number generator rule:
	let dummy be a number;
	repeat with n running from 1 to 100
		now dummy is a random number between 1 and 4; [warm up the RNG for Git]
	let b be a random number between 1 and 32633; [a high prime number, but not so high as to cause a significant delay to start-up]
	repeat with n running from 1 to b:
		now dummy is a random number between 1 and 4; [range used here makes no difference]

EDIT: updated to ensure proper working for Git- see post below

8

That was my conclusion. @DavidK, any thoughts?

9

Have people tested with the version of Glulxe post David’s patch (June 30)?

10

I haven’t got a Unix OS installation up-and-running to test on, unfortunately. As I understand it, if compiled for MacOS/Win32 the terp’s internal RNG is always used.

I assume that if compiled to use a Unix OS RNG rather than the terp’s built-in, this interesting ‘feature’ would disappear…

11

I can confirm however that the latest stand-alone version of Glulxe compiled for Windows ( 0.6.0.153 still has the bug.

12

This is the Gluxe terp’s RNG- I don’t know if someone more qualified that I could say if this explains the observed behaviour?

#ifdef COMPILE_RANDOM_CODE

/* Here is a pretty standard random-number generator and seed function. */
static glui32 lo_random(void);
static void lo_seed_random(glui32 seed);
static glui32 rand_table[55]; /* State for the RNG. */
static int rand_index1, rand_index2;

static glui32 lo_random()
{
  rand_index1 = (rand_index1 + 1) % 55;
  rand_index2 = (rand_index2 + 1) % 55;
  rand_table[rand_index1] = rand_table[rand_index1] - rand_table[rand_index2];
  return rand_table[rand_index1];
}

static void lo_seed_random(glui32 seed)
{
  glui32 k = 1;
  int i, loop;

  rand_table[54] = seed;
  rand_index1 = 0;
  rand_index2 = 31;
  
  for (i = 0; i < 55; i++) {
    int ii = (21 * i) % 55;
    rand_table[ii] = k;
    k = seed - k;
    seed = rand_table[ii];
  }
  for (loop = 0; loop < 4; loop++) {
    for (i = 0; i < 55; i++)
      rand_table[i] = rand_table[i] - rand_table[ (1 + i + 30) % 55];
  }
}

#endif /* COMPILE_RANDOM_CODE */
13

That patch should not be relevant, that should only affect a build with both OS_UNIX and COMPILE_RANDOM_CODE defined. With OS_UNIX defined on its own, Glulxe will use the POSIX random() function.

In the past Glulxe and Git on Windows have both used the rand() that comes with Visual C++ (or with msvcrt in the case of GCC) which is pretty terrible. At some point we switched to the one in the Glulxe code, I don’t recall where Zarf got that from.

So, what needs doing to double check is to build the latest Glulxe and Git on Windows, and run some test cases. That is something I can do, but not right now.

Another thing worth doing is checking if this behaviour is seen on Unix using the RNG code in osdepend.c in Glulxe, i.e. compiling with COMPILE_RANDOM_CODE enabled.

1 Like
14

In the interests of Mad Science I reimplemented the Glulxe RNG code in inform 6 and ran the same test against that, bypassing all the built-in random functions. Same result.

Conclusion: this is an inherent weakness of the Glulxe/Git RNG algorithm combined with the method used by Glulxe/Git to convert the raw RNG output to a range 1 to n, presumably by use of a remainder operator/function.

1 Like
15

At some point we switched to the one in the Glulxe code, I don’t recall where Zarf got that from.

I don’t recall either. I’m sure I just searched around the Internet. I am willing to stipulate that it is bad, although I don’t know if it’s worse than rand().

So, when I said I saw random output on Mac, I forgot that I always compile Glulxe with OS_UNIX. So I’m using the POSIX random(), as David said – not rand()! The random() function gives excellent results.

The problem with relying on random(), or any OS-provided RNG, is that it’s hard to get consistent test results across different platforms. So I guess we want to move to a single, consistent, but more modern RNG algorithm?

16

I guess so- but ideally it would also perhaps move to being part of Inform itself rather than being interpreter-dependent. I’m guessing a potential barrier to that is that the Z-machine and Glulx don’t inherently have access to the real-time-clock as a source of ‘random’ seeding?

17

I still don’t understand how these results are happening, but it is concerning. And surprising that it wasn’t noticed until now.

Some interpreters are already using high quality RNGs, for example Quixe. The issue is more for the C terps. Implementing something like MT in JS would be much slower and wouldn’t make a difference to the quality of numbers produced.

What if there was a new Glulx gestalt which would indicate that the RNG doesn’t have this flaw? We could then change Inform7 to test the Gestalt and use it’s own RNG (perhaps an Xorshift one) if the interpreter can’t be trusted.

18

I can only assume that randomness rarely plays a vital narrative role in IF for reasons oft-rehearsed (even @GrahamNelson got it in the neck after Reliques of Tolti-Aph as I recall)!

EDIT And it’s only very obviously evident if you call the RNG with a particular range at a point where all potential sequences have the same value- as with the very first call with Glulxe and a range of 1-4

19

We didn’t notice this when working on Kerkerkruip, but that would be because it doesn’t request lots of random numbers of the same range in a row.

But it’s really surprising no one noticed that the “one of … at random” phrase always gives the same result if it’s called during startup.

20

True, but only if there are exactly 4 alternatives and the interpreter is Glulxe. I first noticed this some time back when randomly displaying one of four images at startup, but didn’t look into it properly at the time.

I came back to it because of the recent thread involving randomly choosing one of 4 passwords at startup.

1 Like