Z-Machine randomness

I’ve been playing around with my Z-machine library again; Specifically the random number generator. I’m curious if anyone has an opinion on whether or not 64K unique random seeds (meaning 64K unique sequences) is enough? The sequences themselves are quite long before repeating, but when starting a game the sequence will start from the beginning each time.

I’ve been going back and forth on whether to use 16-bit or 32-bit seeds. Slightly less than 32K unique seeds can be set directly through the random opcode, but there’s nothing preventing selecting from a larger number when random is called with a zero operand.

16-bit is easier and uses less memory, but I wonder: Is it good enough? It feels OK from the games I tried, but my testing is hardly exhaustive and mostly focused on older games.

1 Like

That seems perfectly fine. Z-machine games don’t need especially good random number generation, and 32,767 unique sequences is significantly more than your average 80s microcomputer would be able to produce.

1 Like

Are you talking about implementing your own pseudo RNG in Z-code? It’s not really possible in general to say whether it’s enough as that would determine how you’re going to use it. But a 16 but PRNG state is probably adequate for most uses. Xorshift is very easy to implement. Though it only has one actually sequence, just with 64K places to begin that sequence. Is that what you mean, or do you mean 64K actual unique sequences?

My gut feeling is you are correct. My concern was perhaps newer games might be more demanding.

No, I meant the sequences for the underlying interpreter RNG. The complexity of the RNG isn’t really an issue, I was just thinking about the number of possible seeds.

The Z-Machine’s “predictable” mode is actually not predictable at all, and different interpreters will do very different things. It should not be used. If you need a reliable seedable PRNG then you’ll need to implement one yourself.

I think maybe you misunderstood.

I wasn’t referring to the “predictable mode” mentioned in the Standard. I have already implemented my own RNG. The lingering question I had was how big to make the seed space.

Now that you bring up the counting mode mentioned in the standard: I’m surprised…well not that surprised…that different interpreters behave differently here. I have always included a counting mode exactly as described in the standard even though it is only in the remarks and not a formal part of the standard, as the remarks claim it can be useful for testing. Game authors obviously shouldn’t rely on such behavior. Maybe the problem is making it available from z-code via the random opcode. I see no harm in including one which is triggered externally.

We’ll I did ask exactly if you’re implementing your own RNG and you said no! :slight_smile:

So which PRNG method did you implement?

This is the main previous discussion we had on the spec’s suggested incrementing “random” mode: Z-machine RNG

I don’t remember which game it was, but I know there was at least one where an alternating even and odd random implementation caused big issues.

You asked if I was implementing my own RNG in z-code. I assumed that meant within a game. This is within the interpreter itself.

I’ve gone through a number of different ones, but I think I prefer Middle-Square Weyl Sequence. It’s simple and yet has good long cycles and isn’t picky about seeds.

Balances - it was alternating odd/even remainders after division.

2 Likes

Oh, I didn’t know you were making an interpreter! When you said you were working on a library I thought you meant for I6/I7 etc.

:grinning:

Ah, I see the confusion now.

A z-machine library suitable for use by an interpreter front-end. So the z-machine behavior is independent of the the choice of frontend - web, cli, gui, etc.

I’m not very familiar with this one, but it looks okay. I always recommend Xorshift because it’s so simple but makes good numbers. Since implementing it in ZVM I’ve never had anyone report any issues.

But because each interpreter does something different, if someone did want a seeded RNG (like we used in Kerkerkruip) I would still strongly recommend they implement one in their own gamecode. It’s the only way to be both safe and cross-interpreter. And if that’s what we’re recommending, then it doesn’t really matter what the interpreters do. Just choose something good enough that’s compact in code. Which is Xorshift for me. I couldn’t see how compact the one you’re thinking about is.

1 Like

Compact as in code size, or memory?
It’s about five lines. I added another half dozen lines to provide rejection sampling ensuring even distribution no matter what range we’re generating over. It uses two 32-bit numbers for internal state, one of them being the seed. The final result passes all the tests in the NIST Statistical Test Suite. :smiley:

Just for fun, this is the xorshift random from IPDP-10 ITS/MDL (of original Zork fame) using two 36-bit seeds:

MFUNCTION RANDOM,SUBR
	ENTRY
	HLRE	A,AB
	CAMGE	A,[-4]		;At most two arguments to random to set seeds
	JRST	TMA
	JRST	RANDGO(A)
	MOVE	B,VAL2		;Set second seed
	MOVEM	B,RLOW
	MOVE	A,VAL1		;Set first seed
	MOVEM	A,RHI
RANDGO:	PUSHJ	P,CRAND
	JRST	FINIS

CRAND:	MOVE	A,RHI
	MOVE	B,RLOW
	MOVEM	A,RLOW		;Update Low seed
	LSHC	A,-1		;Shift both right one bit
	XORB	B,RHI		;Generate output and update High seed
	MOVSI	A,TFIX
	POPJ	P,
RHI:	267762113337
RLOW:	155256071112

Converted to C#:

        private void btnRandom_Click(object sender, EventArgs e)
       {
           if (txtRHI.Text.Trim() == "" || txtRLOW.Text.Trim() == "")
           {
               txtRHI.Text =Convert.ToInt64("267762113337", 8).ToString();     // Octal-->Decimal
               txtRLOW.Text = Convert.ToInt64("155256071112", 8).ToString();   // Octal-->Decimal
               return;
           }

           long A = long.Parse(txtRHI.Text);
           long B = long.Parse(txtRLOW.Text);

           if (A < 0) A = A + 0x1000000000;            // Convert 64 bits to 36 bits
           B = (B >> 1);                               // Shift low right one bit
           if (A % 2 != 0) B = B | 0x800000000;        // Shift in bit 0 from high to low
           txtRLOW.Text = A.ToString();                // Update low seed
           A = A ^ B;                                  // XOR
           if (A > 0x7FFFFFFFF) A = A - 0x1000000000;  // Use only 36 bits
           txtRHI.Text = A.ToString();                 // Update high seed / result
       }

(I would guess that Infocom used something similiar for their first z-machines.)

1 Like

That sounds very similar to Xorshift in terms of size. The full Mersenne Twister would be overkill for something that will hardly be used, that’s what I meant.

From what I’ve read this is superior to MT, which does not pass all the statistical tests. I used a variant of MT is an old z-machine interpreter I wrote a couple decades ago.