Tech: Programming Randomness

Subject: Tech: Programming Randomness
From: bobad
Date: 03 Mar 09 - 01:25 PM

I recall having heard somewhere that it is not possible to program randomness into a computer.

Does anyone know if this is a fact?

The reason I ask is that I've been playing an on-line form of Scrabble and am beginning to notice what appears to be repeating patterns of letter distribution that seem to defy the laws of probability. If the letters are allocated by a preset formula then the game becomes one of chance rather than skill, assuming equivalent skill levels, and the element of challenge is greatly reduced. This would make the game less appealing to me.

Subject: RE: Tech: Programming Randomness
From: treewind
Date: 03 Mar 09 - 02:02 PM

It shouldn't be hard to program better randomness that you'd notice playing scrabble. Maybe it's just a bad pseudorandom number generator.

Pseudo-random number sequences that run to billions of cycles before they repeat are quite easy to generate. Event the simplest in common use has 65535 different states.

It is possible to generate truly unpredictable numbers too, based on natural phenomena or influences outside the computer. Times between user keypresses, hard drive seek times and timings of packets received from the internet are all used for this purpose, and some computers have electrical white noise generators (like an amplifier with the gain turned up so it hisses) as the basis for number sequences that are truly unrepeatable in any practical way.

Anahata

Subject: RE: Tech: Programming Randomness
From: Mick Pearce (MCP)
Date: 03 Mar 09 - 02:03 PM

bobad

It is possible to program a very good approximation to randomness on a computer (if by this you mean an essentially Uniform distribution - equal chances to everything).

The methods used in general will repeat, but only after a very (and I mean very) great number of times.

The common older form of generators (linear congruential type) even with a long period did suffer from serial correlation between consecutive numbers ("Random numbers fall mainly in the planes" was the title of a famous paper by Marsaglia about this, plotting adjacent pairs of numbers and showing that rather than being distributed all across the plane they tended to appear in lines).

The more modern generators (shift reduce methods), especially in forms like the Mersenne Twister and its relatives have extemely long period and don't suffer from the serial correlation problem.


That being said, an unaware system could use a very poor random number generator (back in the 60s and 70s the standard IBM library routine used a poor form of congruence generator). I would expect modern libraries to have decent generators, but you really need to know the details to tell.

Mick

Subject: RE: Tech: Programming Randomness
From: Uncle_DaveO
Date: 03 Mar 09 - 02:16 PM

As I understand it, any "random number generator" has to have SOME given number(s) to start from. In order to make a random sequence come out of the random number generator, one needs at least one and preferably more independently occurring number(s) for the built in protocols to work on.

One approach might be for the program to look on the web for the current atomic clock time as one datum. It would be unlikely and very difficult indeed for someone on line to pick an exact (down to milliseconds) time to start the game.

If there are two players for your Scrabble game, the program could ask for each player to secretly type in let's say a seven-letter word. The program would use the numeric equivalent of each of those words. Now you have three independent variables, none known to both of the players; each player would control the word (s)he typed in, but not the atomic clock time and the other player's entered word.

So the program takes those three generated numbers as a basis for its random number generation for that game.

Even if the two players play each other again, the game start time would be different, and the program could require that each player put in a new and different word, perhaps of a different length.

I can think of a number of other refinements that would contribute to randomness, such as periodically renewing the time that worked on the previously entered word-number-values. Or using different figures from within the time-number value(say the second and fifth figure) to activate alternative random number protocols even in the course of a game.

I'm not sure whether even these sorts of dodges would create a "TRUE" random number sequence in an ideal theoretical sense, but the sequence would be a good approximation of random, as the result was perceived by the players. None of the above suggestions should be beyond the ability of a competent programmer.

Dave Oesterreich

Subject: RE: Tech: Programming Randomness
From: Mick Pearce (MCP)
Date: 03 Mar 09 - 02:57 PM

Dave

The number used to initialise a random number generator (the seed) is important. From any given seed the random number generators will produce the same sequence of pseudorandom values. In many simulations you actually want to be able to do this, so that you can generate the same sequence of events and try processing them in different ways. In other cases - such as generating random letter sequences for scrabble games - you probably do not want the same sequence every time, so you will use a different seed every time (or continue the random number sequence from where you last left off - the periods are quite long; one of the Mersenne Twisters I mentioned has period 2^19937-1, which is quite large!). System clocks and various other happenstance events, such as those mentioned by you and by Anahata, have been used to generate seeds for the random number generators.

Mick

Subject: RE: Tech: Programming Randomness
From: GUEST,.gargoyle
Date: 03 Mar 09 - 04:10 PM

bobda - this really is not a TECH worthy question - you should know better - it belongs below the line.

You probably heard wrong. Random generation is something a computer excells at.

The release of "Pretty Good Privacy" aka PGP launched a criminal investigation by the US government into its young creator....(facinating history of the still young public internet...and a connection to Garrison Keller)

To reach a random "seed" as noted above - phone books have been a source of random numbers...i.e. last five digits of every 50th number beginning on a page opened by chance, before "published random tables" and before computer generators. Phone books also may provide a common source for two unknown parties to share a common key.

The modern desk top computer provides a statistical processor that thirty-five years ago cost hunderds of dollars for a few minutes use and required several pounds of "punch cards" not to mention hours of tabulation.

(BTW - Hasbro dropped their lawsuit regarding one version of the on-line game)

Sincerely,
Gargoyle

Subject: RE: Tech: Programming Randomness
From: pavane
Date: 04 Mar 09 - 02:36 AM

Gargoyle: There are SOME musical applications. My program HARMONY generates random tunes in the style of jigs and reels, complete with chords.

But here, we are almost all talking about Pseudo-Random numbers, the series of which is totally predictable if you know the seed and the algorithm (and the arithmetic precision used). It takes the white-noise generator approach to get close to real Random numbers. The UK Premium Bonds draw from the 1950's used "ERNIE", which stood (Still does?) for Electronic Random Number Indicator, working on that principle.

HARMONY uses the built-in random number generator in Visual Basic, seeded from the system clock. I have no idea how random these numbers are, but I have never seen the same tune generated twice!

Subject: RE: Tech: Programming Randomness
From: GUEST,.gargoyle
Date: 04 Mar 09 - 06:08 AM

Pavane that is quite an intriguing idea. You even transposed Mr. bobad's question into a musical thread.

To help the quizically inclined this is the location for HARMONY (please no Blue Clicky it hides the beauty of a webpage's nomenclature such as yours in South Wales.

http://www.greenhedges.com

Thank you for the work you put into creating the application.

If you want to go to extreams of knowing the "seed" and the algorithm and saying it is predictable....I guess the same could be said for the statistical method of phonebook genereation...if you knew the year, and the city, and the page, and the sequence spaceing.

I spent well over a full hour at the "Enigma Code Machine Exhibit" in the "War Museum" in London. Fascinating!!! And it does prove your statement of totally predictable if you know

Sincerely,
Gargoyle

I am happy to see HARMONY runs on old platforms. (Ancient of days long past crude "hack" for 30 day timed/out shareware-programs was to advance the computer clock several years ahead when installing the software and returning to standard time. Usually worked well.....

Subject: RE: Tech: Programming Randomness
From: pavane
Date: 04 Mar 09 - 06:20 AM

Harmony was originally WRITTEN on old platforms (MSDOS/Quickbasic)
Thats why it can't be ported onto MAC/LINUX/anything else except by running WINDOWS as a guest O/S

And I put in a fix which should stop that old hack - you are welcome try it and let me know.

By the way, there aren't many songs with GARGOYLE in the lyrics, but here is one:

Saga of Suzie Grapevine and Pusher Joe (Mike Absalom, c1967)

(Having jumped out of a 15th floor window after shooting Joe):

(Spoken) "down she went, bouncing off the window ledges and the little concrete GARGOYLES put there by the Notting Hill housing trust.

Down, down, down, down, down - for the first time in her life Suzie Grapevine was going down ... SPLAT"

Subject: RE: Tech: Programming Randomness
From: pavane
Date: 04 Mar 09 - 06:22 AM

And if you look closely, I only ask a donation for registration. Pay as much as you like (Or think it is worth)

Subject: RE: Tech: Programming Randomness
From: GUEST,.gargoyle
Date: 04 Mar 09 - 06:38 AM

Thank you - that was a good laugh.

I love the days of the old shareware and especially MS-DOS.

I believe I know your "fix" and the old-school "fix to the fix" but lets not go into "old web-war games."

I saw the suggested donation and it is fair. My interest is to experience the "random music generator" in jig time...then probably explore some more.

Sincerely,
Gargoyle

Subject: RE: Tech: Programming Randomness
From: pavane
Date: 04 Mar 09 - 07:26 AM

The tune generator is only supposed to be a bit of fun!
Each time it makes a bad one, just run it again.

By the way, due to a known bug, it is best to load an existing tune FIRST - any tune, doesn't matter which one. Only use the generator AFTER that. (Something to do with path not found I think)

Subject: RE: Tech: Programming Randomness
From: Nigel Parsons
Date: 05 Mar 09 - 11:05 AM

Pavane:
"ERNIE", which stood (Still does?) for Electronic Random Number Indicator,
"Electronic Random Number Indicator Equipment", hence the acronym! (checked Here
Cheers
Nigel