A nasty-looking troll, brandishing a bloody axe, blocks all passages out of the room.

Your sword has begun to glow very brightly.

The troll swings his axe, and it nicks your arm as you dodge.

>

**attack troll with sword**

A good slash, but it misses the troll by a mile.The axe crashes against the rock, throwing sparks!

>

**attack troll with sword**

The troll is disarmed by a subtle feint past his guard.The troll, angered and humiliated, recovers his weapon. He appears to have an axe to grind with you.

>

**attack troll with sword**

A quick stroke, but the troll is on guard.The flat of the troll's axe hits you delicately on the head, knocking you out.Conquering his fears, the troll puts you to death.It appears that that last blow was too much for you. I'm afraid you are dead.

**** You have died **** .

A familiar scene to anyone who has played Zork, the troll room is likely a player's first encounter with random (or pseudo-random if we are being pedantic) behavior in the Z-machine. In fact it is possible to die immediately upon entering the room! While this may not be the best possible use of randomness in a game, it serves as a good example of the Z-machine's ability to generate random outcomes. I've chosen the random number generator as the first Z-machine component to look at in detail because it is relatively simple, self-contained and remains constant throughout the different versions of Z-machine design.

The random number generator is invoked through a single opcode which takes a single operand and stores a result, both of which are 16-bit values. The Z-machine specification outlines the expected behavior in two places: Section 2.4 and the details of the random opcode. What we need to do is look at the operand as a signed value, let's call it 'x', and do one of three things: If x is negative, we seed the generator with -x and return zero. If x is zero we seed the generator as randomly as possible and return zero. Finally, if x is positive we generate a random number 'r' such that 1<=r<=x and return it. Additionally, the author of the specification, Graham Nelson, recommends an algorithm where seed values 1 to 999 change the behavior of the generator from producing random numbers to sequential ones mainly to assist game authors with testing. For example: "random -10" would place the generator in 'counting' mode and subsequent calls to random with positive ranges will produce 1,2,3...,9,10,1,2,3... and so on until the generator is seeded with another value. We now have all the behavior we need to implement an abstract base class. An abstract class allows the actual random number generation algorithm to be replaced if need arises without rewriting our class or risk of losing our recommended behavior. Here's our class:

/// <summary>

/// The Z-machine random number generator.

/// </summary>

public abstract class RandomNumberGenerator

{

private short count;

private bool countingMode;

private int seed;

public event EventHandler<GetRandomSeedEventArgs> GetRandomSeed;

protected int Seed

{

get

{

return this.seed;

}

private set

{

this.seed = value;

if (value > 0 && value < 1000)

{

this.countingMode = true;

this.count = 0;

return;

}

if (value == 0)

{

var args = new GetRandomSeedEventArgs();

this.GetRandomSeed(this, args);

this.seed = args.Seed;

}

this.countingMode = false;

this.SeedGenerator();

}

}

/// <summary>

/// Generates a random number within a given range.

/// </summary>

/// <param name="range">

/// The range of possible results.

/// </param>

/// <returns>

/// A random number within the given range.

/// </returns>

public short Generate(short range)

{

if (range < 1)

{

this.Seed = -range;

return 0;

}

if (this.countingMode)

{

int temp = this.count % this.Seed;

this.count = (short)(temp + 1);

return (short)((temp % range) + 1);

}

return (short)(((this.GetNext() & 0x7fff) % range) + 1);

}

/// <summary>

/// Initializes the generator.

/// </summary>

public void Initialize()

{

this.Seed = 0;

}

/// <summary>

/// Gets the next random number.

/// </summary>

/// <returns>

/// The random number.

/// </returns>

protected abstract short GetNext();

/// <summary>

/// Seeds the generator.

/// </summary>

protected abstract void SeedGenerator();

}

Some explanation:

GetRandomSeedEventArgs is a simple class derived from EventArgs which contains a single read-write property of type int called Seed. This allows the generator to raise an event when it needs a randomly valued seed. This occurs whenever Random is called with a zero operand, or the generator is initialized, which happens at machine startup and during a restart.

The reason we do this: this.GetNext() & 0x7fff is to ensure the result is within the expected range because the return value is signed and could possibly be negative if a derived class implements GetNext() badly. This looks a little ugly, but if we use an unsigned return type we lose CLS compliance.

Now that we have a base class, we can implement a real generator. This one is my C# implementation of the Mersenne Twister - mt19937ar:

/// <summary>

/// The Z-machine random number generator using Mersenne Twister algorithm.

/// </summary>

internal sealed class MersenneTwister : RandomNumberGenerator

{

private const uint TemperingMaskB = 0x9d2c5680;

private const uint TemperingMaskC = 0xefc60000;

private const uint InitializationMultipler = 0x6c078965;

private const uint LowerMask = 0x7fffffff;

private const uint M = 397;

private const uint MatrixA = 0x9908b0df;

private const uint N = 624;

private const uint UpperMask = 0x80000000;

private static readonly ImmutableArray<uint> mag01 = InitializeMag01();

private readonly uint[] stateVector = new uint[N];

private uint stateVectorIndex;

/// <summary>

/// Gets the next random number.

/// </summary>

/// <returns>

/// The random number.

/// </returns>

protected override short GetNext()

{

uint result;

if (this.stateVectorIndex >= N)

{

int kk;

for (kk = 0; kk < N - M; kk++)

{

result = (this.stateVector[kk] & UpperMask) (this.stateVector[kk + 1] & LowerMask);

this.stateVector[kk] = this.stateVector[kk + M] ^ (result >> 1) ^ mag01[(int)(result & 1)];

}

for (; kk < N - 1; kk++)

{

result = (this.stateVector[kk] & UpperMask) (this.stateVector[kk + 1] & LowerMask);

this.stateVector[kk] = this.stateVector[kk + M - N] ^ (result >> 1) ^ mag01[(int)(result & 1)];

}

result = (this.stateVector[N - 1] & UpperMask) (this.stateVector[0] & LowerMask);

this.stateVector[N - 1] = this.stateVector[M - 1] ^ (result >> 1) ^ mag01[(int)(result & 1)];

this.stateVectorIndex = 0;

}

result = this.stateVector[this.stateVectorIndex++];

result ^= result >> 11;

result ^= (result << 7) & TemperingMaskB;

result ^= (result << 15) & TemperingMaskC;

result ^= result >> 18;

return (short)result;

}

/// <summary>

/// Seeds the generator.

/// </summary>

protected override void SeedGenerator()

{

this.stateVector[0] = (uint)this.Seed;

for (this.stateVectorIndex = 1; this.stateVectorIndex < N; this.stateVectorIndex++)

{

var previousValue = this.stateVector[this.stateVectorIndex - 1];

this.stateVector[this.stateVectorIndex] = (InitializationMultipler * (previousValue ^ (previousValue >> 30))) + this.stateVectorIndex;

}

}

/// <summary>

/// Initializes the mag01.

/// </summary>

/// <returns>

/// The mag01.

/// </returns>

private static ImmutableArray<uint> InitializeMag01()

{

var mag01Builder = new ImmutableArray<uint>.Builder(2);

mag01Builder[0] = 0;

mag01Builder[1] = MatrixA;

return mag01Builder.MakeImmutable();

}

}

Some explanation:

For those familiar with this algorithm, you may notice I left out a small section in the GetNext method which initializes the generator with a fixed seed value if you forget to seed the generator before calling it. I think this is a bad idea as it hides the error. Failing to seed the generator produces a string of identical results which is much easier to identify and fix.

You might also have noticed this code contains an immutable array class. The immutable array is something I found a need for in other parts of the Z-machine and have gotten into the habit of using it everywhwere. We'll see it again...

There we go! A complete implementation of the Z-machine random number capabilities.

Why didn't you use the Random class?

ReplyDeleteYou could definitely use the Random class in the derived implementation. The abstract base is used to enforce the z-machine specific behavior.

ReplyDeleteOne reason I used the MT is because it is generally considered a high quality pseudo-random generator. A remark in the specification is what first got me started thinking about it: "It is dangerous to rely on the ANSI C random number routines, as some implementations of these are very poor. This has made some games (in particular, 'Balances') unwinnable on some Unix ports of Zip."

I don't know how good the algorithm used by Random is (I couldn't find any detailed information on it), but I've done some simple testing using dice simulations with Random and the results aren't fantastic.

The Random algorithm in the .NET Framework is based on the "ran3" algorithm here: http://www.fizyka.umk.pl/nrbook/c7-1.pdf, which is in turn based on the algorithm from Knuth's "Seminumerical Algorithms".

ReplyDeleteThanks Eric.

ReplyDeleteIt's interesting that most published algorithms of this kind seem to be written by people allergic to giving variables intelligble names.

In my implementation of the MT I tried to find decent names from the documentation or code comments. I fixed most of them except for a couple, e.g. kk and mag01. I suspect mag stands for magic. :)

Speaking of the "classics", here is an implementation using that exact same very poor algorithm that many systems' ANSI C rand() function use:

ReplyDeleteclass AnsiBrokenRandomNumberGenerator : RandomNumberGenerator

{

private int randx;

protected override short GetNext()

{

return unchecked((short)(((randx = randx * 1103515245 + 12345) >> 16) & 0x7FFF));

}

protected override void SeedGenerator()

{

randx = this.Seed;

}

}

Provided in case you want to make 'Balances' unwinnable.

If you're concerned about forgetting to seed the generator, why not throw an exception? For that matter, why allow the generator to be constructed in an unseeded state? Couldn't you require a seed in the constructor?

ReplyDeleteI felt adding a check for unseeded state and seeding with a constant doesn't really add any value. I could require a seed in the constructor but I'm not that concerned about it really. It gets seeded at machine startup and the code that does so is very simple.

ReplyDelete