Monday, July 7, 2014

Well, that's random

Why random numbers?

In order to make a fun game of chance, you need random numbers. Dice rolls, card shuffles, or a roulette wheel are no fun if they're predictable.

Mommy, where do randoms come from?

There are mathematical formulas that can provide a stream of seemingly random numbers. These are called pseudo-random number generators, or PRNGs. You start off a PRNG with a truly random "seed" number, from which the PRNG derives a sequence of numbers. Although this sequence gives the appearance of being random, it is completely predictable - each time the PRNG is started with the same seed, it will produce the same resulting sequence of numbers.

It all starts with a seed...

Thus, the initial seed for a PRNG must be truly as random as possible. Computers are great at many things, but being unpredictable isn't one of them - so to get some randomness (or "entropy" as it's called in Information Theory), we need the human touch. In this case, quite literally.

For each of the platforms I'm using for my Retrochallenge entry (Atari 800, Epson PX-8, PDP-11/23+), I wanted to find a suitably fast-changing clock or register that could be used as a seed. To get this value at a random time, you ask the user to press a key to perform some action (e.g., get their initial bankroll - thanks Ian!). After their key press, a value is sampled from the high-speed clock and used as the seed value. As long as that clock is fast enough, then voila, there's your random number seed.

Harvesting the seed

The PX-8 was the most ideal. There is a 614.4 KHz clock that updates a rolling 16-bit register, the value of which can be read with from the BASIC "INP" function. This function reads values from Z80 I/O registers. Since 614.4 KHz will update the value more than 600,000 times per second, it is unlikely in the extreme that a user could predict when to press a key even if they wanted to.

The Atari 800 and PDP-11 were not as good, but still passable. Each have memory-mapped registers that update at 60 Hz. Typically called "ticks", these are internal clocks for the computer's functions. In the Atari, it's part of the ANTIC video chip, and for the PDP-11, it's a component of the line clock. Reading the value of minutes, seconds and ticks after a user key press should provide an ample source of randomness. On the PDP-11, there is a system library function, callable from Fortran, called "GTIM", that provides the current count of ticks. On the Atari, in Forth, the value can be read with "C@", the Forth equivalent of a one-byte PEEK function.

Now we have a seed, how 'bout some numbers?

PX-8 BASIC also has a PRNG built-in. You seed it with the "RANDOMIZE" statement, then use the RND function to get random numbers (fractions 0<=x<1). For Forth and Fortran, I need to provide the PRNGs; however, there are happily some good ones online.

So hey, pal, no counting cards in my RC casino!


MrPiWorld said...

With the seed generation, couldn't you make it count the amount of "ticks" that it takes the user to press a key. I think the Apple II did that (I may be wrong).

Garrett Nievin said...

I ran into a similar issue. I recently built a Spare Time Gizmos SBC-6120, and to learn the PDP-8 assembly language I decided to implement the "2048" game that got so popular on Hacker News recently (there was an Atari 2600 implementation that was very nicely done, which was further inspiration).

So that the player wasn't confronted with the same game conditions each time, the game starts with an initial keypress; while waiting, it just sits in a loop incrementing the random number seed. Since the PDP-8 originally had magnetic core memory, and memory reads were destructive and had to be re-written, it was cheap and easy to have an instruction to increment a memory location. Since the instruction set of the PDP-8 is so minimal, though (3 bits of opcode giving 8 basic instructions), they of course made the increment into an increment-and test: ISZ, or "Increment and Skip if Zero." So my little loop has an ISZ followed by a NOP.

If one wished, one could locate the loop in memory such as to put an interesting pattern on the memory address indicator lights, and load the accumulator first to put something interesting on those lights as well.

I think it would be a fun project to build a switches-and-blinkenlights front panel for an Apple 2...

Emily Grace said...

Real "game of chance". I like card games like Black Jack And for real gamblers it's great stuff