PDA

View Full Version : Random numbers and Games



Solfe
2015-Jun-20, 03:19 AM
Funny question about not understanding "random".

I play a game online where a random number is generated to determine success of a given action. It is a complicated game, just assume we are talking about hitting a target with a bow based on a number 1 to 100.

I also play a game where a die (actually 2 ten sided dice for 1 to 100 numbers) is rolled to make this same sort of determination when it is needed, by me personally.

In a third game, there is a special tournament rule where a referee has a list of pre-rolled random numbers (using a die in advance of play) and when a die should be rolled, the referee states the number from his list and crosses it off, and proceeds to the next number for the next "roll". This game is really cut throat, and issues with "unfair" dice can break the game in short order.

Assuming the dice used are "fair" in each scenario, the value ranges are the same (1-100) and the random number generator is as fair as the dice, is there any difference between each method of randomly generating numbers?

I ask because I have seen the "random number generator" accused of being biased, yet don't see any bias myself. It seems like a pretty good method of generating numbers to me. The second method of me rolling a die seems to be different, but less "random". Perhaps this is a case of my memory being flawed. The third method seems to be "the worst", because the referee could accidently view a future number and wince or smile, biasing the player into taking ill-advised actions.

Question 2: Could my three different opinions of these random numbers be accurate or it is a poor hunch about what random really is?

DonM435
2015-Jun-20, 03:32 AM
I've done a few sports simulations driven by computer-generated random numbers, and found that when you were doing thousands and thousands of replications, the numbers would eventually repeat themselves and produce the same results over again. That's because these are really "pseudo-random." They're generated by algorithms that use the previous number elaborately sliced and diced to get the next. It's unpredictable by human standards, but perfectly predictable to the computer. So, the "range" of your random number generator algorithm becomes important when you're doing this.

I found that you can get really random numbers by subscribing to a service that gets these via monitoring radioactive decay of some element. They know that half of the atoms will break down in a half-life of time, but individual atoms are supposed to be unpredictable.

For most purposes -- how many arrow simulations are you doing after all? -- the pseudo randoms are just as good. Probably better than dishonest coins, lopsided dice or biased spinners.

Ken G
2015-Jun-20, 05:44 AM
Yes, I agree that all three of those methods are essentially equivalent. Surely there are much more important factors to weigh when playing any game that is at all interesting!

DaveC426913
2015-Jun-20, 06:03 AM
Assuming no fixing or errors, the three are equivalent.
But it's a big assumption. A better question might be which of them is more or less prone to fixing or errors.

Rolling 2D10 is pretty er dicey. Someone a while back did a study on dice, making, I think, a million rolls on a thousand dice (D6s). He found them to be widely varying in their randomness due to manufacturing. This could spell trouble for the 2 D10, if the 10x multiplier die happens to be biased.

Ken G
2015-Jun-20, 06:26 AM
But there remain additional issues:
1) How biased are the dice? If it took a thousand rolls per dice to discover the bias, probably not very much! After all, in most games, the trick is not turning a 10% of winning into a 10.1% chance, it's knowing how to avoid situations where you have only a 10% chance of winning in the first place.
2) What if the dice are biased, but you don't know the bias? If you are not playing a game that involves using some dice for thousands of rolls, then you are not going to know the bias, and neither will your opponents. If no one knows the bias, then the bias plays no role, for it does not change any of the probabilities that the players would calculate, and none gain any advantage that could not just as easily have been a disadvantage.
That's why I say, forget the random number generator, and just look for better strategy, unless the game you are playing is a mindless gambling game-- in which case, you should ask, isn't there something more interesting to do?

Shaula
2015-Jun-20, 06:36 AM
Is the random number generator an actual hardware RNG or a pseudo-random number generator? As DonM435 says the outputs from the two can be quite different. The trouble with PRNGs is that they are all basically flawed in some way and generally what you do is trade ease of use or speed off against how statistically sound your PRNG is. Then there is the issue of weak seeds, spotting them and avoiding them. In short unless you are careful then, for large volumes of numbers, the PRNG is inferior to fair dice. And there are some classes of PRNGs (linear congruential generators, I am looking at you!) that are just awful but still sometimes used. See RANDU (https://en.wikipedia.org/wiki/RANDU)

cjameshuff
2015-Jun-20, 12:03 PM
Also note that the better PRNGs use quite a bit of state other than the previous random number, giving much longer streams of random numbers before repeating, and allowing a given number to appear multiple times in the sequence. A LCG PRNG using 32 bit numbers is limited to a period of 2^32, a bit over 4 billion numbers before repeating (if properly designed so all numbers are visited before repeating). The Mersenne Twister PRNG has a period of 2^19937 - 1...you're never going to use up more than a tiny fraction of the period.

There are many other ways for flaws in pseudorandom number streams to show up, and tools exist for performing empirical testing of PRNGs:
https://en.wikipedia.org/wiki/TestU01

There are also common flaws in how they are used. For example, take a pseudorandom number from 0 to 255 and use it to create a number from 0 to 99. A common approach is to use integer modulo operations to wrap the input around, but this means that the ranges 0-55, 100-155, and 200-255 are mapped to 0-55, while only 56-99 and 156-199 map to 56-99...you'll have 3/2 times as many random numbers in the 0-55 range. This becomes less important with bigger random numbers, but can still create a bias that is noticeable in the long run.

Solfe
2015-Jun-20, 03:23 PM
Yes, I agree that all three of those methods are essentially equivalent. Surely there are much more important factors to weigh when playing any game that is at all interesting!

There are a lot more interesting things out there... True!

I am trying to think of a way to reply, that isn't' too crazy or out there. This online game is a fantasy game and I discovered a bug. I am pretty certain the bug has nothing to do with how random numbers are generated, but in how situations are evaluated. I have another player trying to explain the whole thing to me, but he has descended into naming things like "polygonal numbers" and all sorts of other fancy things about random numbers that I believe are irrelevant. I haven't said so, but man, it looks like that to me. My math skill suck.

This game has monsters. The monsters come in types: spider-like, quadrupeds, magical, giants, undead, and so on. Some of these monster types are immune to certain things, you can't elbow lock a cow, you can't make a zombie bleed to death, giants can't be kicked in the face unless they are lying down, etc. The game mechanics for these immunities are/should be straight-forward.

If you kick at a giant, you get a random number plus or minus some modifiers and are told the results. Usually, you hit the legs and feet. You never kick it in the face because the game "knows" you are 6 feet tall and the giant it 50 feet tall. Additionally, if you enter the command "Kick Giant In Face", you get a random number attack roll as normal but it is modified so that this always fails. In all cases the character is shown the random number and the modifiers. Basically, kicking a giant in the face results in an attack roll (1-100 randomly) minus a number that is larger than 100. Your chance of success is zero. Make sense?

Now here is the scenario: One type of undead monster happens to also be magical. It casts spells, both defense and offensive. It also occasional swings a weapon. One of it's defensive spells renders it immune to low level spells. If, on the odd chance a weak spell would hit, instead of doing damage, it removes the defensive spell. The monster "knows" this is a good spell to have, so it will take the time to recast the spell instead of attacking. This wastes time for the monster.

Here is the bug: My character has a spell that should not affect undead creatures at all. What should happen is "test" - is this monster undead? If yes, this attack roll is modified to always fail. When the monster casts it's "immune to magic spell", the "is this monster undead" test is not happening at all. The result is the monster loses it's "immunity to magic" and stands there recasting the "immunity to magic" spell. I can hit so frequently, that I can "freeze" the monster by making it try an ineffective action.

This has nothing to do with randomness, right? This is poor implementation because a random number of 1 to 100 should have a number larger that 100 subtracted from it but this isn't happening.

Ken G
2015-Jun-20, 03:39 PM
This has nothing to do with randomness, right? This is poor implementation because a random number of 1 to 100 should have a number larger that 100 subtracted from it but this isn't happening.Yes, this is exactly what I'm talking about-- the vagaries of the random number generation is a complete red herring to the process of creating good strategy for the game. It is a kind of a bug, yes, but you don't even have to view it as a bug-- view it as a flaw in the intelligence of the undead monster (who said they were smart?). The monster might have a desire to maintain its magic shield, and lacks the logical reasoning skill to think "hey, I don't need a magic shield against spells that can't hurt me." They just think "drat, I've lost my magic shield, better replace it." Thus, you can keep them busy doing things an intelligent opponent would not bother to do. That's just good strategy.

Another way to say it is, there are several forms of immunity to a spell-- if a spell can't hurt you, then you are in some sense immune to it, but if that spell can knock down your magic shield, then even though the spell itself cannot hurt you, it can affect you. You can interpret it as saying that the magic shield itself also lacks intelligence-- it in some sense uses its power to defeat any spell it encounters, not bothering to restrict to spells that can hurt its user.

You can even imagine real-world analogs to this. For example, imagine fighting someone else who had a sword, when all you have is a bucket of water. Pretty hopeless battle, yes? But if that other person is also wearing a full suit of armor, which should make them even tougher, now you have a chance to win. Even though the person was not vulnerable to water, so did not need the suit of armor, the armor becomes a liability if you throw the bucket of water onto it. Now the person has a water-logged suit of armor, slowing them down even more, and maybe some of the joints seize up as they take in water (I don't know what would really happen). Maybe they are so slowed that you can outmaneuver them, perhaps get them to trip and fall and be unable to get up. I'm making all this up, but the point is, we can imagine situations where an over-invulnerability can actually be turned into a liability, like a monster having to stop to replace a spell it never needed in the first place.

Solfe
2015-Jun-20, 07:07 PM
Since random has nothing to do with the first scenario, let me ask a question of quality (I think.) about the other two scenarios. When a person rolls a set of dice and makes a list of pre-rolled numbers, this is exactly the same is as me rolling dice when needed, so long as we use the same dice.

In theory, the game host could take my dice in the morning, roll a bunch of numbers on the same table and hand the dice back to me. There really shouldn't be any difference in what he does and what I could do with the same set of dice.

What confuses me is, if someone looks at the whole list of pre-generated numbers, could that person make a quality judgement about the list of numbers and come to a different conclusion about fairness than a person using the dice as needed? Basically, let's assume I am rolling the dice as needed and I don't remember the die rolls accurately.

This is completely subjective right? One person has a complete list and another person has faulty memory and confusing events (Yeah, a 100 again! The dragon is dead!).

Ken G
2015-Jun-20, 08:25 PM
What confuses me is, if someone looks at the whole list of pre-generated numbers, could that person make a quality judgement about the list of numbers and come to a different conclusion about fairness than a person using the dice as needed?No, it's still the same. To analyze randomness, you'd need a long list of outcomes to analyze. It doesn't matter if you watched the outcomes get rolled, or were just handed the list, as long as that's how the list was generated.


Basically, let's assume I am rolling the dice as needed and I don't remember the die rolls accurately. If you have faulty memory, that's clearly worse than the actual list that were rolled. Most people will tend to imagine that dice are weighted against them if the rolls are imperfectly remembered. In fact, that would be a nice experiment-- keep track of the dice rolls in some game that involves lots of them, and then at the end ask all the players (privately) to rate the overall good or bad luck they had in the game, relative to the other players. Perhaps rank the players in order of the luck they had. Don't be surprised if they all underestimate their own good fortune!

JohnD
2015-Jun-20, 10:02 PM
For use in research, when patients, animals or other items must be allocated randomly to one or other regime, published lists of random numbers have been available for many years.
The Rand Coporation's was one of the earliest: http://www.rand.org/pubs/monograph_reports/MR1418.html
It's still valid. You or your referee could save timeby using such a table.

John

Solfe
2015-Jun-21, 01:57 AM
For use in research, when patients, animals or other items must be allocated randomly to one or other regime, published lists of random numbers have been available for many years.
The Rand Coporation's was one of the earliest: http://www.rand.org/pubs/monograph_reports/MR1418.html
It's still valid. You or your referee could save timeby using such a table.

John

That is crazy! I had no idea.

Solfe
2015-Jun-21, 02:07 AM
That is crazy! I had no idea.

Oh, man. Check out the review on Amazon.com (http://www.amazon.com/Million-Random-Digits-Normal-Deviates/dp/0833030477/ref=sr_1_1?ie=UTF8&qid=1434852420&sr=8-1&keywords=0833030477&pebp=1434852422519&perid=1QX8QZ7E612CTJ4FNHNK).

Shaula
2015-Jun-21, 04:18 AM
Oh, man. Check out the review on Amazon.com (http://www.amazon.com/Million-Random-Digits-Normal-Deviates/dp/0833030477/ref=sr_1_1?ie=UTF8&qid=1434852420&sr=8-1&keywords=0833030477&pebp=1434852422519&perid=1QX8QZ7E612CTJ4FNHNK).
Some of them are pure genius. Especially the one asking for an index.

JohnD
2015-Jun-21, 09:30 AM
Solfe,
What is "crazy"?
That experiments and trials that strive, mightily to peer through the fog of chance and bias to find a true result, should introduce randomness?
The objective is to more reduce the inherent bias in a trial organised by people, who have opinions and beliefs, by ensuring that the groups are not inherently more or less likely to be affected by the trial, and reveal an objective result.
You could start by reading this article on the "Double Blind Randomised Trial", the DBRT that is the Gold Standard of modern scientific method: http://www.cancerresearchuk.org/about-cancer/find-a-clinical-trial/what-clinical-trials-are/randomised-trials

John

swampyankee
2015-Jun-21, 10:51 PM
Donald Knuth,in his classic Art of Computer Programming, had a lot about random number generators. Tricky to get right, very easy to get wrong.

grapes
2015-Jun-22, 03:18 AM
Donald Knuth,in his classic Art of Computer Programming, had a lot about random number generators. Tricky to get right, very easy to get wrong.
Volume 2 :)

Jens
2015-Jun-22, 04:08 AM
What confuses me is, if someone looks at the whole list of pre-generated numbers, could that person make a quality judgement about the list of numbers and come to a different conclusion about fairness than a person using the dice as needed?

I think they could, but in some cases, so could the person with the real die. For example, suppose that the die has a piece of lead on one end so that it often comes up with a 6. If you had the list beforehand, you would probably notice that. If you just picked up the die and threw it, you would likely not notice that, though after a number of rolls you might. Also, if you physically examined it you might notice. So I don't think it's a difference between the two methods, just that the second method makes it a bit easier to do an inspection.

DonM435
2015-Jun-22, 04:18 AM
You can run statistics on a generated list to determine whether the numbers differ significantly from a uniform distribution.

Sometimes a random number list will have a particular number appear twice (or more) consecutively, but that's not necessarily a violation of randomness. It should happen now and again, at a frequency dependent upon the range of the numbers.

JohnD
2015-Jun-22, 08:02 AM
I'm told that when Apple introduced the iPod, with it's "shuffle" option, they gave it a rather good random number generator (RNG) to indicate which "chune" to play next.
Then they started to get complaints that the machines had played two songs from the same album in sequence, or even the same song twice over (as Don says).
To mollify their users who did not understand 'random', they destroyed the perfection of the RNG, by compelling it to check if the next song had been played recently.

John

Ken G
2015-Jun-22, 09:36 AM
To mollify their users who did not understand 'random', they destroyed the perfection of the RNG, by compelling it to check if the next song had been played recently.
Though in fairness, users don't really care if it is random, they legitimately don't want to hear the same song twice in a row! Ideally, there would be a random distribution that is not uniform, but rather is weighted toward songs the user prefers, and is also weighted to avoid repeats. It's hard to know what the user prefers unless you have them rate the songs, but it is easy to avoid repetitions.

cjameshuff
2015-Jun-22, 11:12 AM
Shuffling is a specific operation, a reordering of a list, that shouldn't produce repetition no matter what PRNG you use. If they were originally playing random selections from a list and not removing them from the list, they weren't shuffling.

mkline55
2015-Jun-22, 12:13 PM
Shuffling is a specific operation, a reordering of a list, that shouldn't produce repetition no matter what PRNG you use. If they were originally playing random selections from a list and not removing them from the list, they weren't shuffling.

I think the problem occurs when the end of the list is reached and it is reshuffled. The last entry of the first set may become the first entry of the second set, so it appears twice in a row.

grapes
2015-Jun-22, 12:40 PM
Shuffling is a specific operation, a reordering of a list, that shouldn't produce repetition no matter what PRNG you use. If they were originally playing random selections from a list and not removing them from the list, they weren't shuffling.
If you view the process sort of as a deck of cards that gets dealt out in its entirety.

Of course, casinos have taken steps to conteract card-counters such as re-shuffling before the end of the deck, even after every play if they can do it and keep the game moving.

So, the music-player deals a song, then re-shuffles the list. If you have N songs, it's 1/N that you're going to get the same song--every time. You're apt to get a re-play every time you play N songs.

That's easy to fix though, just weight the more recently played by a function of how long it's been since it was played. The last song, maybe the last five songs, could have zero weight.

swampyankee
2015-Jun-22, 04:07 PM
Volume 2 :)

It's on my shelf. I had volume 3, but a former coworker never returned it.

Knuth is such a great writer on the subject.

DonM435
2015-Jun-22, 06:00 PM
Bear with me, there's some practical advice at the end of this discourse. Well, maybe. Probably.


Away back at the dawn of the modern age, I had a project developed in Windows 3.1 and written in QBasic. The project grew in usefulness, and was successively adapted to QuickBasic and Basic 7.0, then eventually rewritten in Visual Basic 3, and adapted to subsequent versions. I was pleased to find that Microsoft had not altered their random number generator: It still gave the same results with the same calls and the same initial seed (or the default seed). This simplified my testing (to prove that the new version gave the same results as the old), as my old benchmarks still were valid.

I just now loaded Visual Basic 6, and told it to Debug.Print Rnd(). I got 0.7055475.

Next, I tested it in MS Word 2010. What you do is:
Open a document. You will be ignoring said document hereafter.
Select the Developer tab. (I think that you have to alter your default Settings to even see this tab.)
Select the Visual Basic icon at the far left of the menu bar.
Add a line to the Sub Macro1 code that you see on screen:
Debug.Print Rnd()
Then, Press [F5] to run the macro.

You will see in the debug window below:
0.7055475

I knew this would work, because upon occasion Iíve developed simple VB6 code on any version of Microsoft Office that was handy. Iím quite sure that you can test this in Excel, Access or other Microsoft applications, and you'll get the same, because VBA (Visual Basic for Applications) is at the root of each.

Next, I loaded Visual Basic .NET 2010. I executed the statement
MsgBox(Convert.ToString(Rnd()))
And got
0.7055475

I donít have QBasic around anymore, but as I said, I know that its random number implementation was giving the same numbers as did the earlier Visual Basics. Therefore, we have this particular algorithm unchanged from at least the early 1990s.

I have MS Word 2013 and Visual Basic 2012 on other computers, but won't bother testing those. Still, I'll bet you get the same result.

If I took the trouble to do the same thing with Visual C++ or Visual C#, I wouldn't be too surprised to get the same number. Depends upon who wrote the initial algorithm for those languages.

By the way, if you then ask for another random number in any of these systems, itíll use the previous number as the new seed, and will give you 0.533424. All subsequent numbers will be the same on all systems, absent a re-seeding.


Now, what does this mean to you? Iím glad you asked that question.

If someone were to say ďWe have a tie for first place [or, the prize, the job, etc.]. To break it, Iíll be thinking of a number between 1 and 10, which Iíve obtained fairly and randomly ÖĒ

If this guy used a Microsoft product, of which thereís a pretty good chance, without re-seeding the random number generator, heíd be using the formula:

Random_Integer = CInt(Int((10 * Rnd()) + 1))

And so would get 8. Trust me. If youíre in this situation, pick 8.

If your adversary happened to pick 8 as well and the host gets another number for tie-break, itíll be a 6. That should clinch your victory.

You can run a loop like this to get a series of numbers between 1 and 10 inclusive:

For i = 1 To 100
Debug.Print CInt(Int((10 * Rnd()) + 1))
Next


If someone were to simulate a two-dice roll with an un-re-seeded Microsoft random number generator, heíd be getting two integers between 1 and 6, which will come out as 5 and then 4, so you should prepare for a 9.

Chuck
2015-Jun-22, 08:55 PM
I still have QBasic and ran it in DosBox. I got 0.7055475 too.

DonM435
2015-Jun-22, 09:30 PM
Cool. Thanks for checking that. (I'll bet that the old Apple, Radio Shack, Commodore and Atari versions of Basic might differ ... unless they had a common ancestor.)

There was an old GW-Basic on the first (pre-Windows) PC that I worked with at the office -- seemed about 90% compatible with QBasic: I used the former's manual with the latter. I suspect that it would give the same result.

Chuck
2015-Jun-22, 09:59 PM
GWBasic gives me .1213501.

DonM435
2015-Jun-22, 10:56 PM
Interesting. So the Microsoft random number algorithm still in use must date back to about 1985 (QuickBasic), but not earlier.

grapes
2015-Jun-22, 11:18 PM
Change is good, I suppose:

Description of the RAND function in Excel

https://support.microsoft.com/en-us/kb/828795

cjameshuff
2015-Jun-22, 11:34 PM
Change is good, I suppose:

Description of the RAND function in Excel

https://support.microsoft.com/en-us/kb/828795

And that's not even the worst thing that could happen...Excel has a long history of performing weird and buggy transformations on its data, truncating to 16 bit integers, printing 65535 as 100000, etc. The idea that people trust Excel to reliably perform numeric computations (specifically, the computations they intend it to perform) is a bit horrifying.

cjameshuff
2015-Jun-22, 11:41 PM
By the way, when MS fixed Excel's RAND to use an implementation that passed the Diehard tests, they evidently didn't actually test it, because there was another bugfix a little later to fix it again so it wouldn't return negative numbers:
https://support.microsoft.com/en-us/kb/834520

Solfe
2015-Jun-23, 02:02 AM
Solfe,
What is "crazy"?


Crazy that it is still in print. And presumably useful.

DonM435
2015-Jun-23, 03:33 AM
When I was a schoolteacher, I didn't trust myself to call on the kids unpredictably and fairly, so I wrote a program to accept a list of names and print one after another according to a random number. Had to do this on an IBM-360 mainframe at the time. It had some advantages. It assured that they'd be called upon to speak equally in the long run (some wanted to be called, others to be ignored!) so I couldn't be accused of playing favorites. You couldn't relax once called, as you might still be next on this list.

Other teachers liked the idea, so I made runs to produce lists for them. Explaining the program was interesting for the class, I think.

An early version had a bug, and as a result, the first kid's name got printed a few thousand times, over many pages. Rather than scrap the printout, I gave it to him. "You can use this for bookcovers, eh?" Other kids requested a similar effort!