Automatic Dice Thrower

Impressive:

The Dice-O-Matic is 7 feet tall, 18 inches wide and 18 inches deep. It has an aluminum frame covered with Plexiglas panels. A 6×4 inch square Plexiglas tube runs vertically up the middle almost the entire height. Inside this tube a bucket elevator carries dice from a hopper at the bottom, past a camera, and tosses them onto a ramp at the top. The ramp spirals down between the tube and the outer walls. The camera and synchronizing disk are near the top, the computer, relay board, elevator motor and power supplies are at the bottom.”

Click on the link and watch the short video.

As someone who has designed random number generators professionally, I find this to be an overly complex hardware solution to a relatively straightforward software problem. But the sheer beauty of the machine cannot be denied.

What I am curious about is what kind of statistical anomalies there are in the dice themselves. At 1,330,000 rolls a day, we can certainly learn something about the randomness of commercial dice.

Tags: , ,

Posted on May 27, 2009 at 6:44 AM • 64 Comments

Comments

anon • May 27, 2009 7:10 AM

Oh, just noticed, this comment box strips everything after a less-than sign. So, security unnecessarily impacting functionality. I’d prefer to have both, and believe it is possible. (Determine input encoding, replace [ampersand] with [amp]amp; and less-than with [ampersand]lt; .

Test tag starts here: end

Sean Ellis • May 27, 2009 7:20 AM

Yes, I see that this would be better served with some software and a decent noise source. But, as a gambling site, transparency is important.

This is why we use machines full of balls for lottery draws in the UK. It’s very difficult to think of a way to game such a simple system, whereas a black box with a button labelled “Pick a number” could be doing any number of nefarious things under the lid. Any afficionado of fruit machine workings will tell you as much.

So, it’s important not only to be open and fair, but also to show that you are open and fair, and if it’s an attractive spectacle at the same time, so much the better.

WarAtHome • May 27, 2009 7:22 AM

What a dinosaur.
Our data center would be first in line to buy a quad + load balancer, but we would need it to support all Dx modes.
The deal-breaker for us is no D20 support, but D4, 8 and 12 support is not much lower of a priority.
Sorry, that’s just how we roll.

Michael Kohne • May 27, 2009 7:46 AM

I don’t think this is so much for the greater randomness as it is for the greater ‘now shut up’-ness. There’s not much room for people to complain. Not that they won’t, but at least he’s made the effort.

Any statistics geeks ask him for a couple million rolls? I’d love to know if the commercial dice he uses (or the entire rolling system) are biased in any way. Just because.

Nicholas Weaver • May 27, 2009 8:06 AM

According to the /. thread, the machine was specifically made because there was always SOMEONE complaining about the software RNG setup, that it would never be “good enough”.

By building a physical machine, even if the properties are NOT quite as good as a well seeded cryptographic pRNG, it acts to shut up the annoying customers who think their bad luck is the fault of the RNG.

wiredog • May 27, 2009 8:24 AM

I would thing a thermocouple and an a/d card would be random enough (especially if you used just the lowest 4 bits) and much less expensive.

Pete Austin • May 27, 2009 8:25 AM

If I wanted to attack this machine in a low-tech way, I’d get someone to sneak in with a little laser pointer and try shining colored light at the place where the dice are read.

Per Lindholm • May 27, 2009 8:31 AM

Human random number generation.

Here is a problem for you. Have you ever thought about what happens in your brain when you are asked to write down a random password or series of random numbers. What is the underlying program for this, is it predictable.

As a test sample you are to write down a series of random numbers between one and hundred. The task then is to see how predictable these numbers are.

Then how good or rather how bad are humans on random number generation and how do the mind choose between these numbers.

David • May 27, 2009 8:40 AM

The pingpong balls for lottery drawing has already been gamed. Someone got to the balls and ever-so-slightly weighted some of the numbers, then heavily played combinations of the others.

Anderer Gregor • May 27, 2009 8:41 AM

I think what we would also learn about is about the randomness of the OCR (ODR?) process … the author already mentions that the “6” usually looks like two blobs for the software. So, if some number (on some dices) is likely to be mixed up with another, or not be recognized at all, this would significanty bias this RNG.
There could even be some a-posteriority bias e.g. if the camera controls gain/brightness by previous images, etc …

phil • May 27, 2009 8:42 AM

“Here is a problem for you. Have you ever thought about what happens in your brain when you are asked to write down a random password or series of random numbers. What is the underlying program for this, is it predictable.”

This is a standard case study used on entry-level statistics student: The teacher divides the class into two groups and leaves the room. One group flips a coin 100 times and notes on a board “1” for heads and “0” for tails. The other group makes up a random sequence of 100 “1” and “0” out of their heads. Upon returning to the room, the teacher is to point out which group did the random flip generation method. The teacher is successful 95% of the time.

Snarki, child of Loki • May 27, 2009 8:46 AM

For those who say “use this hardware RNG, it’s easy!” I suggest you try it first.

I did. Back in the late 70’s, with a random (diode shot noise) pulse generator and a 100MHz counter; collecting a few million pulses over a minute or so, then using the LSB. Ran for months collecting data onto a 1600bpi tape.

And you know what, that damn counter took ~10ps longer to flip from zero to one than from one to zero. And other subtle problems, many of which could be dealt with in software, but the closer you looked, the more problems you found. How many weren’t found?

In theory, PRNG is easy. In practice, it’s not.

I’d think that the dice machine could be used to “predict” the roll, based on what that camera at the top sees. While the trajectory of the die through the machine is complex, it seems at least somewhat deterministic.

NM • May 27, 2009 9:05 AM

I’m concerned about a possible bias in the signal processing algorithm, how can you spot a potential bias in the dices if it’s the reader has a small bias?

FP • May 27, 2009 9:08 AM

@Pete:

If I wanted to attack this machine, I’d sneak in a few doctored dice. Or some that have the desired number on all sides.

I believe in Germany the online offerings of licensed casinos had to offer a live webcam view of their roulette wheel. They couldn’t just display a number and print “you lose.”

Clive Robinson • May 27, 2009 9:33 AM

@ Sean Ellis,

“It’s very difficult to think of a way to game such a simple system, whereas a black box with a button labelled “Pick a number” could be doing any number of nefarious things under the lid.”

Even when the “random” part is “truly random” (whatever that means to you 😉 it is part of a system and humans are usually very bad at designing systems so, gaming is always possible…

An example,

A well known Electronic Random Number Generator has been in use by a majour government for many many years as a method of raising “loans” from the people.

Well various learned mathmaticians hav said that to the best of their abilities/belife the generator is “truly random” and everbody appears happy with that.

Well if you look at the whole system what you find is the following,

1, people by numbers for 1 unit of currancy.

2, They keep their numbers for as long as they wish and redeam them for 1 unit of currancy (the numbers are not reused).

3, The government selects the number of random numbers to be drawn bassed on the total value of the numbers the return rate (say 5%) and a graph of weightings to give one or two big prizes through to lots of small prizes.

Anybody spot anything wrong with this system?

Well the clues are that the numbers are,

1, not reused
2, increasing with time
3, People cash numbers in.
4, Selected by a “true random” number generator.
5, Are issued in sequence.

Got it yet?

Ok the number set is sparse, more so at one end (old numbers) and less sparse at the other (new numbers). This is due to numbers not being reused and people dying or finding better things to do with their money.

Starting to get ideas yet?

Ok ask yourself the question,

“In a sparse database of significant size what are the chances of a random number actually finding a number that is in use?”

Now ask another question,

“As a set number of numbers have to be drawn in a short time scale how do they actualy do it?”

Or to put it another way, The system has to “halt” therfore some method of mapping has to be applied…

Now askyourself the question, just how big is this database and how sparse is it and what are the data processing requirments behind the chosen mapping system…

Now ask yourself,

If I buy 10,000 numbers this month and redeam all but the first and the last add another two units of currancy and by another 10,000 numbers next month and keep doing it what does this do to my odds against your chosen mappimg system…

Fred P • May 27, 2009 9:39 AM

Quite a while ago, I worked for a company that got a proposal to create such a machine (different details, same idea). We rejected it due to complexity.

Per Lindholm • May 27, 2009 9:42 AM

Thanks Phil, I suspected it of being pretty bad. However Im more interested in the predictability of a single person and what future technology enhancements you could make with this knowledge. Hopefully were are predictable in some time period which by we could influence to change actions that could otherwise be fatal, particularly in driving. So predictability would really be good news.

Alex • May 27, 2009 9:47 AM

It’s funny no-one mentionned erosion. Surely after a couple million rolls, the dice would start wearing. But does that add to any original bias, or does it wear it off? AAAAAAH so many questions!

bob • May 27, 2009 9:48 AM

I believe to analyze the dice per se you would need to have only a single die, or perhaps a single pair in the machine, otherwise they would tend to normalize each other.

moo • May 27, 2009 10:21 AM

All your dice suck…

Part 1:
http://www.youtube.com/watch?v=bR2fxoNHIuU&eurl=http%3A%2F%2Fwww%2Eboardgamegeek%2Ecom%2Fthread%2F375045%2Fpage%2F1&feature=player_embedded

Part 2:
http://www.youtube.com/watch?v=PxmkWrDbn34&eurl=http%3A%2F%2Fwww%2Eboardgamegeek%2Ecom%2Fthread%2F375045%2Fpage%2F1&feature=player_embedded

It’s Colonel Lou Zocchi explaining some of the weaknesses in his competitors’ cheaper manufacturing methods for dice. He’s been the leading manufacturer of quality dice for a long time.

Yes, the video is mostly marketing spiel; but its still got interesting stuff in it!

Clive Robinson • May 27, 2009 10:39 AM

@ Alex,

“But does that add to any original bias, or does it wear it off? AAAAAAH so many questions!”

Think about pebbles on the beach what shape are they mainly?

And when they are not why not?

Put it simply, the dice should if they are all from the same manufacture and made of the same batch of plastic effectivly wear evenly…

However you have to ask the question with dice,

Where is the COG?

After all you have 1 hole oposite six holes which sugests that the COG is 5/6ths of the volume of a hole closer to the one hole side than the six.

Likewise you have the 2 opposit the five suggesting its closer to the 2 And likewise to the 3.

Also you would expect the wear to be more pronounced on the side with six holes than the one as it has a effectivly a lower density and smaller surface area…

Therfore you could argue that the six is more likely to keep coming up irrespective of wear…

Greg H. • May 27, 2009 10:42 AM

@Per Lindholm

In the mid-80s, the Journal of Experimental Psychology published a paper that showed that participants can be ‘trained’ to behave randomly. If I remember correctly, the study had some pretty serious methodological shortcomings (I believe the researcher used a pool of 7 participants), but you may be interested in reading the paper.

In case you’re interested, I ran what I remember through Google Scholar and found this:

Neuringer, Allen, “Can people behave “randomly?”: The role of feedback.” The Journal of Experimental Psychology: General. Vol 115(1), Mar 1986.

Tim Maddux • May 27, 2009 10:57 AM

A quick google search turned up this report on dice randomness. Highest values (6) turned up more often than lowest (1) in a numerical model that incorporates the mass losses from the holes in the die face. It notes that Vegas dice are filled with paint of the same density as the plastic used to make it.

http://www.maa.org/mathland/mathtrek_10_26_98.html

I can’t help but think of the scene in “Casino” that shows a character measuring the dimensions of dice with a micrometer.

Clive Robinson • May 27, 2009 10:59 AM

@ NM,

“I’m concerned about a possible bias in the signal processing algorithm, how can you spot a potential bias in the dices if it’s the reader has a small bias?”

It’s actually not that difficult it just takes a very very long time…

Instead of thinking dice, think a coin.

As it’s flipped take the readings as distinct pairs.

If the pair is HT then output a 1 if it’s TH then output a 0 in either case increment the “good counter”. Do not output anything for HH or TT but increment the “bad HH” and “bad TT” counters.

Over a period of time with no bias “Good count” = “bad HH” + “bad TT” and “bad HH” = “bad TT”. If they don’t then you have bias and the ratio of “bad HH” to “bad TT” gives you the direction of the bias and the ratio of the “good count” to HH+TT bad counts gives you the magnitude of the bias when normalised to the total count (GC+HH+TT).

You should of course keep these counts under review during the run to see if the ratios remain constant or vary and this will give you an indication of the wear rate (which I would expect to be an inverse power law).

You can of course use more sophisticated measurments (see “The arte of Computer Science” Voll 2 Second edition for a range of other tests).

JimFive • May 27, 2009 2:02 PM

@Clive
Re: Your description of a bad system.

Your description was very difficult to understand, but you make an assumption. If the numbers are selected by ordinal position (i.e. not by actual number) then the sparseness of the set is irrelevant.

Alternatively, if “redeemed” numbers are ignored (and a new number is chosen) then there is also no problem with this system. (Think of choosing a number 1-5 by rolling a d6 and rolling again if a 6 shows up.)

@David
I don’t think the balls were “gamed” purposely, my understanding is that the paint of the numbers caused certain balls to weigh more and therefore be less likely to get sucked up the tube.

I’ve also read a novel where the lottery balls were gamed by causing certain balls to be statically charged so that they would resist going up the chute.

JimFive

Fraud GUy • May 27, 2009 3:35 PM

@ Clive

IIRC, most casino dice do not have recessed pips, but are solid cubes with the pips filled. I am not sure if the density is the same as the rest of the die material, but filled volume should have much less variance than open volume.

Martin • May 27, 2009 3:36 PM

30 years ago I worked with measurement systems, and one of our customers was the BC lottery commission. I seem to recall that the lottery balls were not like ping pong balls, rather they were made from a somewhat dense solid rubber (or something along those lines). In particular they were much heavier than I had expected.

Each set of balls was regularly and carefully measured for weight, size and bounce, and was retired when any of the measurements fell outside spec, or after the set had been used for some max number of times.

Oh and they were kept in nice felt-lined instrument style cases, crimp-sealed and locked. And stored in a vault. Can’t see how static electricity would have helped anyone…

andyinsdca • May 27, 2009 3:54 PM

@Per Lindholm:
Mentalists use tricks like this all the time and can heavily influence the numbers someone chooses. Look for books by “Banachek” (a well known mentalist and consultant for Penn & Teller) on this.

bltfsk • May 27, 2009 4:12 PM

Researchers buy a random number generator from a well-regarded manufacturer. When it’s delivered, they fire it up. It generates a list of primes.

Can they send it back?

Lu-Tze • May 27, 2009 5:52 PM

@Snarki

Perhaps what you found was that there is no truly random-ess in this (ahem the) universe.

Clive Robinson • May 27, 2009 6:22 PM

@ JimFive,

The problem is that there are a very very large number of numbers involved.

I’m not sure you have grasped the magnitude of the problem in comparison to the technology available to handle the number of numbers involved.

Regard the numbers if you will as being serial numbers on receipts, issued from an apparently infinately large book (ie it keeps growing the number of digits in use).

Each time a person comes along they get issued with the next set of receipt from the book. One for each and every unit of currancy they place on deposit.

When they redeam the receipt it is voided (but the data is kept).

So you have a range of numbers starting from zero upto the currant face number in the book.

After just over 50 years you can imagine that the number on the top of the book is going to be very very large (the number of alphanumeric digits has been enlarged several times and recently was put up from 10 to 11 however the smaller sized numbers are still valid in their own right).

However only a small number are activly in use (a little over 27Billion currently according to the web site).

The size of the database of these numbers and attendent information was just a few years ago to large to fit on any single mainframe database.

The process of compressing the sparse number range down in such a dynamic system is problamatic to put it mildly and invariably such systems did not do it, especialy if they retain the original data on voided numbers.

Although there are a few papers on ERNIE published, I have not seen any on the method of mapping the random numbers to the actual numbers on the recipts (Preimium Bonds). So the method of mapping used is an open question.

When you refere to,

“Think of choosing a number 1-5 by rolling a d6 and rolling again if a 6 shows up.”

Think instead of a dice with 1000 sides instead of six. How many times would you have to roll it to get a number in the range 1-5?

How many times would you have to roll it to ensure getting 3 numbers in the range 1-5, and are you going to be able to do it in ten minutes?

This is what the “halting” problem is about, ie is it “definatly” going to do it each and every time in ten minutes?

The answer is “you’ll be lucky to do it once let alone over and over again”. Hence the reason for needing to generate X number of serial numbers in the range and then “map” them onto active serial numbers.

The simple mapping answer is enter the DB at the randomly chosen number and crawl backwards or forwards till you find an active number.

Therefore if you have deliberatly taken a range of 10,000 serial numbers and redeamed all but the first and last then for the price of two serial numbers you have effectivly covered 10,000 chances. If you take the redeamed money and top it up and go and buy another 10,000 range of numbers and redeam all but the first and last you now have 20,000 numbers covered for the price of 4.

If you keep doing this your odds of winning compared to others not doing it is bassed on the failings in the mapping system used.

Less than 10 years ago a friend tried this against the UK Premium Bond system which has a limit of 30,000 active numbers for any single person (the experiment came about after a discussion one evening on how to break the 30,000 active number limit).

The experiment was actually carried out by my friend (we both put money in but Keith did the donkey work of buying and redeaming the bonds) using a much smaller number range and guess what they showed returns considerably over that you would have otherwise predicted, based on the official “expected return” rate.

However the rules have been changed somewhat and I suspect the method of mapping has probably been improved due to progress in mainframe performance.

The point I was making is that there was potentialy a fault in the system the cost of testing to see if it could be exploited was only fractionaly above that of not testing it.

The increased rate of return over an extended period tended to confirm that there was an issue with the mapping system.

What the problem with the system was/is I have no idea, it was not required to know the speciffics just “black box” test the system to see if the possability was an actuallity.

The result of the test over several years was it was returning a higher than the published expected return rate by an easily measurable amount. Further when compared to a single range of numbers held it was even better (they showed less than the advertised expected return rate).

The question is where we both just lucky or was the system “gameable” the answer is I don’t know, but it worked for us.

Sadly Keith died at an early age of cancer, and his family cashed in his bonds. My personal circumstances changed so I cashed in my bonds as I needed the money (don’t have children unless you want to be poor ;).

So the experiment is no longer running and the rules about how you buy the bonds have changed as well.

Jeremy • May 27, 2009 6:40 PM

@Clive:

I think I’m with JimFive on that one. My first thought for implementation was to have a list of all active numbers, generate a random result between 1 and the size of the list, and use it as an offset into the list. That’s potentially a big list, but they need to have some way of keeping track of which numbers are active or not, so they need to have such a big list anyway. I don’t see any obvious performance or bias problems with this approach, assuming the random number is actually random.

The system you described certainly COULD be implemented poorly, but I see no reason to assume that it IS implemented poorly based only on the specs you listed.

Clive Robinson • May 27, 2009 7:18 PM

@ Fraud GUy,

“I am not sure if the density is the same as the rest of the die material, but filled volume should have much less variance than open volume.”

In “proffesional” or “Casino” dice they holes are (supposadly) filled with a material that has the effect of having the same density and volume.

However from a practicle manufacturing point there are going to be issues with this.

Further again for manufacturing reasons the materials are not likley to be the same so will have different wear rates. So even having the same density and volume and “perfect COG” at manufacture does not mean it is going to stay that way due to wear.

In a Casino wear is not going to be an issue, as they are replaced after a minor number of uses.

With it’s very high daily throw rate you would expect the dice to noticably wear within a short time period in this machine.

As somebody else noted above there have been tests run on “store bought” dice with unfilled holes that do show a bias towards the high numbers.

Not so long ago when recovering from being in hospital I tested ten dice I had bought in a store over a period of a few days in a home made “tumbler” (UK “straight” Pint glass mounted on the rim of a hand cranked rotator, ear plugs an essential feature ;).

Even after a comparitivly short time the results were “walking” in a definate direction suggesting that there was ware occuring.

Oh and the reason I carried out the experiment was to provide a counter argument to a theory proposed by somebody I know.

Basically during WWII the people at “Bletchley” made “one time pads” with tombola equipment. It has been shown that the resulting pads showed sufficient bias to be visable across a few pads to the naked eye.

It has been sugested by a number of people at various times that the WRENS responsable for making these pads where falsifiing the readings (for whatever reason).

Having met one or two of the ladies concerned some years ago it did not strike me as being credible that they where falsifing the results, and I have always put it down to equipment short comings and wear.

However the theory being proposed was one of “droped balls”. That is that a ball or balls would be occasionaly dropped and not put back in the tombola drum. I have not liked this argument for the simple reason that the errors where not significant enough.

Well after a few days of experimentation I showed just how quickly wear actually happens even with modern materials, and importantly with similar levels of bias as shown in the one time pads.

Nowhere near proof positive but enough to kick a leg out from under a weak theory, and it took my mind off of the recovery process 8)

peri • May 27, 2009 9:48 PM

@Clive Robinson, JimFive and Jeremy:

Here is a bit more detail behind JimFive’s ordinal comment. Thanks for the challenge. I will show a number can be chosen with probability 1/N and sketch how to find that number reasonably quickly.

I am assuming there are 26 + 26 + 10 = 62 possible values for each digits and that they started with a single digit range and expanded it to 2, then 3 and are now up to 11.

I would start by keeping an accurate count of how many numbers are eligible to win in each digit range: every time somebody buys a number with i digits, we increment d[i] and every time somebody sells a number with j digits we decrement d[j]. The total number of outstanding numbers N, is the sum (i=1…11) of d[i].

Now when I want to pick one to win all I need is a number, R, chosen from {1,2,…,N}, so each number has the same chance of being picked. It is possible to find out how many digits R’s number has by finding the largest j for which the sum, S, (i=1…j) of d[i], so that S < R; on a list that starts with 0 of all the numbers used with d[i] digits, R’s place, P, on that list is R – S.

For any R whose P is large enough to be a problem to find on a daily basis, or however often numbers are supposed to “win” then we can simply store similar information about the totals of used numbers for particular digits in particular digit ranges in the same way we stored totals for the digit ranges themselves.

An interesting fact: you can also use the d[i] values to find out how sparsely populated each digit range is. If a digit range holds d[i] digits then the percentage of used numbers is 100 * d[i] / 62^i.

Clive Robinson • May 28, 2009 1:21 AM

@ DaveC,

“Clive, are you soliciting help to optimize your Premium Bond holdings? :-)”

As I don’t hold any bond any longer the answer would be no.

Mind you I do like the implied idea behind “optimize your…”.

The simple fact is that as the WiKi article you point to says, recent changes to the effective return rate (supposadly due to the credit crunch) has caused a bit of an upset.

Now here’s a question for you…

If the real rate of inflation on basic energy costs and food is running at near double digits, and the majority of investments are paying less than a single digit, is your avarage waged bod better of putting money into investments or food into the freezer?

JCG • May 28, 2009 1:34 AM

I saw this on Slashdot, and naturally someone complained that the machine rolls only D6’s.

So I said that’s no problem, you can generate D4, D8, D20, whatever you want, by rolling several D6’s, adding them, and then taking the result modulo 4, 8, 20, or whatever.

Trolling for crypto geeks. I am an evil, evil man.

Clive Robinson • May 28, 2009 2:07 AM

@ peri,

Hmm…

Not sure which of our two posts jimfive would find least clear 8)

However it’s early in the morning here and I have not had a cup of eye opener yet, so I’ll come back to it once Iv’e ingested some devil’s brew.

@ jimfive,

Back in the first year of the UK bond there where according to “official” figures 100 million bonds issued ERNIE could only produce 2000 numbers an hour. “He” was designed by a team from the old Post Office research labs at Dolis Hill, and a team member was Tommy Flowers who is better known for his work on Colosus at Bletchly which was arguably the worlds first digital electronic computer (to do anything usefull 😉

50 years ago there where no electronic computers with anything like the ability to store or process 100million records. So the database would have been searched by humans on a card file index…

As with all things bueracratic things are oh so slow to change and I would be surprised if the system became “computerised” (in a way that we would currantly understand) before the mid 1980’s.

ERNIE is recently in “his” fourth incarnation but still apears to be based on “Pink Noise” from thermal effects in electronic devices.

Bernie • May 28, 2009 5:58 AM

I’m getting tired of this “person” who keeps posting about Bruce Schneier not having a Ph.D. degree (which I don’t know if it is true or not). I’m starting to think that it is a bot or someone in a third world country getting paid 45 cents/hour trying to subtly influence people into buying no-study, instant dip1omas.

To the poster: If you are a real person trying to make a serious point, let me tell you that you sound like a child. You seem to have a very limited understanding of the world (and the inability to make a point). I, too, saw the world in simple black and white when I was young. As I got older, I came to understand that just about everything is more complicated than I thought.

Anonymous • May 28, 2009 6:22 AM

@Bernie

Don’t worry about asdf. The moderator is on that.

But I’d sure like one of them no-study diplomas if you’ve got one Bernie. I’ve shelled out about 30k, 3 years of my life and STILL have to study.

Do you got a post office box?

Gerv • May 28, 2009 6:31 AM

This system actually doesn’t eliminate the need for an RNG. Read carefully how the detector works – it detects individual coloured pips, and reassembles them into rolls. So 4 yellow plus 8 green plus 15 blue => 2, 2, 4, 4, 5, 5, 5. See the problem yet? His detector doesn’t detect the order of the dice in the tray. And so unless he wants to provide the rolls from each tray in numerically ascending or descending order (!), he has to shuffle that list. And that requires an RNG.

Max • May 28, 2009 7:48 AM

Gery, the text says that it only uses the colours, but if you look at the video, the computer program shows the correct number below each die. So perhaps the algorithm has been improved.

JimFive • May 28, 2009 9:41 AM

@Clive
How to do it by hand, 50 years ago.

Two card file cabinets, one for redeemed bonds, one for outstanding bonds.
When a bond is bought it’s card is put in the outstanding cabinet (in order). When it is redeemed it is moved to the redeemed cabinet. Keep track of how many cards are in each drawer using a log book, Or (preferably, but more labor) balance the cabinet drawers so that each drawer contains the same number of cards. To select winners: Add up the number of outstanding bonds from the log books, select a random number <= the total and select the bond in that ordinal position. (If there are 100 outstanding, you select a number from 1 to 100, the number on the bond is irrelevant) Finding the card is just a matter of adding up the totals until you find the proper drawer and then counting through to find the proper card, and ERNIE only needs to generate one number.

RE: getting 1-5 on a d1000
This would be done with modulo and woud only require one roll. (Or a few depending on the relationship between your die size and your desired domain.)

While it is certainly possible that the process was screwed up by using a hash collision type algorithm that doesn’t mean the idea is unworkable, just that it was implemented badly.

JimFive

Anonymous • May 28, 2009 9:45 AM

@fp. Replacing the dice is more likely to leave dna evidence. Also if an attacker is caught with a laser pointer he might claim it was carried by mistake – not so a pocketfull of dice!

Also I’ve never trusted any webcam since watching the original “Mission Impossible” TV series, where they regularly defeated cameras with replay attacks etc.

Bryan Feir • May 28, 2009 11:32 AM

Re: Casino dice and holes, filled in or otherwise:

My grandmother used to take regular trips to Las Vegas, and the dice she bought at the casino shops didn’t usually have holes in them at all, just dots painted on. The name of the casino was painted around the 1 spot, which might compensate for the extra weight of paint on the 6 spot side. And, of course, the dice were replaced regularly to avoid anything being worn off, which was why the gift shop was selling them so cheaply.

Assuming there was any appreciable weight difference based on the paint, these dice should actually have the inverse bias from the dice with pits.

Eventually, though, we start to get into manufacturing tolerances: even if you try to make a perfectly good die, it may have little internal density differences that give it a bias. This is another reason for swapping the dice out regularly; as long as there is no bias by design, different dice should be different enough to average out any individual issues over the long run.

Moderator • May 28, 2009 11:51 AM

Asdf does not appear to be from some diploma mill (although the thought that he might be trying to sell Bruce a fake doctorate is pretty funny). Most of his comments come from a well-regarded U.S. institute of technology. I used to imagine he was a grad student who, every time he got stuck on his dissertation, would try to unmask Bruce as a no-Ph.D.-havin’ poseur in order to prove to himself that a Ph.D. means everything. “People without doctorates can’t really achieve anything, so all the hell I’m going through for mine must be totally worth it!” Something like that.

But someone in that position would have given up when it became clear that nobody cared about the “scandal.” And a garden-variety troll would have changed tactics. It’s becoming increasingly clear to me that asdf believes diplomas are the only measure of achievement because he doesn’t think people can learn anything outside a formal classroom context, and he doesn’t believe in learning outside classrooms because he himself is incapable of it. How else do you explain his total inability to adjust his message here in response to feedback?

All that’s left now is to see if he can respond to simple operant conditioning. If I delete his messages and you all ignore him, will his behavior change? Or will he still keep doing the same thing over and over, like a moth beating itself to death against a porch light? Let’s watch.

Clive Robinson • May 28, 2009 3:46 PM

@ JimFive,

Hmm the movment of one hundred million cards in the first year alone would sugest not using two filing systems. Likewise totting up ledger information etc.

Also as you describe it, your system cannot be run in paralel only sequentialy, which makes me think it is not a workable system with one hundred million records and a search every month by hand.

Then there is the problem of traceability against fraud etc.

I think an ordinal/compressed system like you suggest has one heck of an overhead to carry with it for no real gain, which makes me feel it was not a system that would have been considered for long or even used.

It would be nice to find out how they did it in the early days as I suspect there is quite a bit we could learn from it even today.

Personaly I would suspect that avoiding fraud via traceability and the ability to do searches in paralel would rate highly in any design choice.

Also the work involved with moving redeamed cards just smells like nightmare problems…

Of necesity ERNIE’s random number selection is compleatly unrelated to the mapping of the numbers into the bond database.

ERNIE just selects Ndigit numbers at the rate of one every two seconds. Each Ndigit number being aproximatly equivalent to 27bits for the 100million bonds in the first year.

So ERNIE was probably running at a little over 100,000 bits/hour which for late 1950’s technology (thermionic valves and neon tubes) is actually quite impressive (oh you can actually see ERNIE 1 in the London Science Museum in the ground floor display hall behind the space display hall).

The official website indicates ERNIE has paid 9billion GBP in 145million prize payouts over the 50years (which does not sound right). So on average it has been running, 240,000 prizes a month (definatly sounds wrong). Which means ERNIE 1 would have been run for atleast 120hours a month every month for the first 15 years.

Therefore It would be unlikley that it produced a list of numbers much bigger than the number of prizes to be awarded.

Any number ERNIE produced that was greater than the total number of bonds would be quickly rejected so it was probably run for something like 6 days solid to get sufficient Ndigit numbers.

(I do not know what is done about duplicates I’ve not seen any refrences to it).

Due to the length of time it would take to generate the numbers The process of mapping the numbers to the bonds would begin almost as soon as ERNIE produced them.

I suspect that the numbers where pacelled out into small lots to do the hand searching.

I think you misunderstood what I was getting at with the d1000 example.

What I was saying is that you need a dice with atleast as many sides as there are bonds issued. However in the sparse areas only 0.5% of them may be valid, and you need to reliably get hits on them.

Therefor how many times would you have to roll the dice to get a 100% hit on one of the five numbers?

Without mapping the answer would be anywhere between 1 and infinity (but probably under 400 times 99.5% of the time if I remember my basic stats correctly).

Even 200 times to get one valid number it sounds like mapping must be used…

With the slow speed of ERNIE this means that you have to use a mapping process that is simple to use by hand by many people at the same time (which I think rules out the ordinal system you described).

As I said I do not know how they did it but an ordanal system such as you describe just sounds like it has to many potential pitfalls and require excessive labour and time. And not mapping would have ment putting out so many numbers from ERNIE tha there would not have been the time to do it or search them.

What I do know is that a very limited experiment run over a number of years was returning a higher rate of return than the published return.

Therefore I’m plumping on the simplest likley explanation (Occams razor) which is a non compressed DB with a simple mapping system.

Anonymous • May 28, 2009 10:14 PM

Trying to paint a no PHD over Schneier is pretty laughable.

Schneier, having a very proven history of computers and serious crypto math ability, would easily qualify for a PHD or two. I wouldn’t put it past one with such skillset, to bang out many other PHD in history, psych, etc, if one wanted.

Actually, I would hope that such trolls would at least try a better way to discredit somebody. Such low trolls diminish serious security work and dedication that some aspire to.

Andrew • May 29, 2009 8:49 AM

Researchers buy a random number
generator from a well-regarded
manufacturer. When it’s delivered,
hey fire it up. It generates a list of
primes.

Can they send it back?

Posted by: bltfsk

Similar to a question I often ask people: “If a weatherman says there’s a 20% chance of rain, and it rains, was he right?

Bill the Lizard • May 29, 2009 9:37 AM

It seems like having dice with six different-colored faces would remove any difficulty in scanning the values. It would also have the added benefit of removing any question of bias caused by pips (the dots or dimples on the face of standard dice).

scramasax • May 29, 2009 12:30 PM

I did some work on that because I play wargames that use a lot of D6.

Most of the commercial dice that we find in games have a little bias. The major factor is the difference in size lenght of a side. So if the size between the 4 and the 3 side is smaller than the size between the other number the 3 and the 4 will happen more often than the 1,2,5,6. By measuring a bucket of dice bought in a store you can classify them. This is minimal but a percent or part of a percent of chance can be gain. Casino dice are rejected if they have a difference of more than 2/10000 in the size of the dice for each side

Casino dice have hole filled not with paint but with the same material that the dice is made but with a different color. So the density is not a problem for casino dice. Heat can be a problem it it change the density

Dice are transparent to make it more difficult to load dice. I have seen people use bucket of water to see if the dice fall more often on the same side. There is also dice caliper that if the dice are loaded will more often finish to roll on the same side.

JimFive • May 29, 2009 1:33 PM

@Clive
It must be remembered that (50 years ago) those pieces of paper are already being handled. The personnel and the systems for handling that volume of paper were already in place. As a manual problem this seems to be much simpler than normal business accounting.

The ordinal mapping that I suggest is straightforward and eliminates any problem with sparse areas of the dataset as well as issues due to the slowness of the RNG (as there can be no misses). I will agree that there may be issues with repeatability (accountability).

JimFive

peri • May 29, 2009 4:14 PM

@Andrew: “If a weatherman says there’s a 20% chance of rain, and it rains, was he right?”

Great question! It is a very elegant way to illustrate to lay people the subtle difference between the claims “I don’t think it will rain” and “I think the chance of rain is only 20%.”

Roger • May 30, 2009 7:49 AM

@scramasax:

Interesting, but in a casino game, the possibility that a die might be biased is not helpful to the gambler unless the bias is greater than the house’s advantage.

Casino dice games have a house advantage that typically ranges (depending on the game, and the house rules) from 4% to as much as 25%. Apparently it is possible to load or shave a die to generate a bias that strong, and in sufficiently poor quality toy dice it may occur simply through poor quality manufacturing, however such a strong bias would also be statistically trivial to detect.

Curt Sampson • May 31, 2009 1:57 AM

By the way, curiosity inspired me once to look into what the “20%” figure that came from the weather bureau really meant, and it appeared to be, “on 20% of days with meteorological conditions similar to this one, it rained.”

cjs@cynic.net

Paul • June 1, 2009 7:02 PM

Laser pointers and substitute dice aside, surely a simpler point to attack would be the wi-fi (!) connection that uploads them to the server in lots of 1000, or failing that, the server storing a couple of weeks of rolls.

There is no need to subtley influence the outcome of the rolls when you can read the whole lot from a file. Maybe his wi-fi is impenetrable, maybe his server is too, but if you cracked it, you do get the whole box and dice…

randomjoe • June 1, 2009 9:21 PM

@Clive:

Suppose I have a database (or list or pile of paper documents or whatever) listing every active premium bond. This is sorted by premium bond number. There is one document per holding, not per bond, so someone who bought 10,000 bonds all at once only has one entry; someone who has bought 500 bonds 50 at a time would have 10 entries.

I can obviously go through them in order and count the number of active bonds. Call this N. I need this number anyway to figure out how many prizes of what value to award.

I can now generate a random number R in the range 1 <= R <= N.

I now go through the bond records again, in order, counting the number of active bonds as I go. When the count reaches or exceeds R, I grab the details of the person who’s holding caused the count to reach or exceed R and I mail them the prize. This is totally fair.

For P prizes and H bond holdings this algorithm is O(PH) time, and requires O(1) extra space (assuming the O(H) database already exists).

This is totally feasible even with paper records – the prize drawings are only monthly, so there’s no rush.

There are obvious optimisations where I write the cumulative count onto the bond as I go through (if the bond holding has an A4 cover page there’s plenty of space for me to write many months worth of cumulative totals); or I can make a separate index which maps cumulative totals to specific bond numbers. I can then do a binary search to find the winning bond. These are both (O(H) + O(P log H)) time and O(H) space.

Glyn Gowing, PhD • June 15, 2009 12:41 PM

@Bernie,

As someone with a PhD in in the field, I have the HIGHEST respect for Bruce and I am very careful to convey that to my students. Bruce has proven himself as one of, if not THE, best in the field.

The best people are not always the ones who had the opportunity to go to college. The best malware hunter I know has only an associate’s degree.

A PhD degree is a supposed to be a validation of your abilities as recognized by other experts in your field with appropriate qualifications. I do not know a single person with a PhD in InfoSec who does NOT have the highest respect for Bruce and all he has done.

He has been busy DOING security. As someone inside the academic arena as well as being out in industry (I’m an adjunct professor and full-time in industry) I can tell anyone reading this that Bruce has more “street cred” than just about anyone.

Glyn Gowing, PhD • June 15, 2009 12:44 PM

@Moderator,

In respect of your wish not to encourage ASDF, please delete this post and my previous post.

I just wanted to speak up as someone WITH a PhD in the field that everyone that I know has the highest respect for Bruce and all he has accomplished.

syberghost • June 19, 2009 7:53 AM

This will not silence the people hunting for phantom statistical anomalies among insufficient sample sizes. It will merely cause them to start arguing between Chessex and Crystal Caste instead of algorithms.

Leave a comment

Login

Allowed HTML <a href="URL"> • <em> <cite> <i> • <strong> <b> • <sub> <sup> • <ul> <ol> <li> • <blockquote> <pre> Markdown Extra syntax via https://michelf.ca/projects/php-markdown/extra/

Sidebar photo of Bruce Schneier by Joe MacInnis.