Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[Witherweaver]

On the topic of choosing random numbers, I came across an interesting phenomenon when working on my thesis.

I had to choose points on the surface of a sphere to evaluate a function.  I could choose more points to get more constraints to (hopefully) get a more accurate solution down the line.  So at first I figured, well, there sphere can be parameterized by an angle in [0,2\pi] and an angle in [0, \pi].  So, let's draw two random numbers from that range and look at

<cos(theta)cos(phi), sin(theta)cos(phi), sin(phi)>

However, a uniform distribution of the angles will not actually lead to "uniformly" spaced points on the unit sphere.  The reason, of course, is that the sphere is curved and the area element (sin(phi)*dtheta*dphi) is maximal around the equator and minimal around the poles.  So the points would "bunch" up, which ultimately lead to a higher probability of rank deficiency in a big matrix as more and more points were chosen.

It took me a while to understand that was what was going on (though it's clear once you think about it).  I ended up taking a more quasirandom approach.  (Taking points that were solutions to some standard polynomial family (Legendre I guess)). 

I think I will not spoiler this post.

[Donald X.]

I don't think there's anything to pursue here unless they post the relevant code. If they do then interested parties can look to see if they can find a bug. There could certainly be a bug, but the chance of someone perceiving flaws in the RNG is large whether or not there's a bug; it doesn't tell us much.

[eHalcyon]

I'm so tired of seeing people complain online about the "stupid RNG" in their game of choice.

Except in games like Chess and Prismata, where whining about the RNG is just for the sake of irony.

Traversing parts of the game state tree that neither player truly thought about is very similar to RNG.  It's an argument I've heard made.

Also, there's RNG in whether buying a 5th Scorchzilla will make my computer overheat so do I just buy a Steelsplitter instead? Life's hard.

By Richard Garfield no less, and I find it a very compelling argument:



He starts talking about luck via complexity at 8:30.  He talks about chess a bit shortly after 10:20 (and more specifically at 11:20).  The whole talk is very interesting.

[Deadlock39]

There could certainly be a bug, but the chance of someone perceiving flaws in the RNG is large whether or not there's a bug.

This is really the most important point to make here.

I've posted this once before, but I think it is a good article, so here it is again.

http://www.wired.com/2012/12/what-does-randomness-look-like/

Maybe there is something wrong with their shuffler, and maybe there isn't.  It's definitely not something that is going to be remotely possible to determine by observation.

[Witherweaver]

They should just make it nonrandom and see if everyone thinks it's more random.

[Witherweaver]

Well, nonpseudo and nonquasi

[Witherweaver]

But really, a standard

rand() % N

for not large N is biased towards lower numbers or something, right? 

[eHalcyon]

They should just make it nonrandom and see if everyone thinks it's more random.

I think we've had this conversation before.   It depends on what kind of non-random.  If it makes them win more, then yeah, it's totally more random.

[michaeljb]

But really, a standard

rand() % N

for not large N is biased towards lower numbers or something, right? 

Right, assuming the number of integers rand() can return is not a multiple of N.

Example, if rand() gives a truly random number in the range [0,6], and N is 3, 0 is a more likely result than 1 or 2:

rand() -> rand() % 3

0 -> 0
1 -> 1
2 -> 2

3 -> 0
4 -> 1
5 -> 2

6 -> 0

[qmech]

But really, a standard

rand() % N

for not large N is biased towards lower numbers or something, right? 

Yes, that was the problem with FFTA.

On the topic of choosing random numbers, I came across an interesting phenomenon when working on my thesis.

I had to choose points on the surface of a sphere to evaluate a function.

High dimensional spheres (really balls, because I want to include the interior) are really weird.  The unit ball in n dimensions has volume O(1/(sqrt(n))^n), which is ridiculously small; the ball with volume 1 is quite large, with radius on the order of sqrt(n).  If you look at slices through this ball in some fixed direction, then almost all of the volume of the ball lies in a slab of constant width near the equator (independent of the dimension, even though the radius of the ball is growing to keep the total volume correct).  This is true in every direction, so most of the volume is in the centre right?  No, it's in a thin shell near the surface, as the volume further in than that shell is exponentially small.

[Kirian]

It took me a while to understand that was what was going on (though it's clear once you think about it).  I ended up taking a more quasirandom approach.  (Taking points that were solutions to some standard polynomial family (Legendre I guess)).

I'm not a mathematician, but wouldn't it be safe to choose random x, y, z, then scale that to the unit vector?  I'm positive there's going to be a reason that doesn't work, but I'm not sure what it would be.

[Witherweaver]

It took me a while to understand that was what was going on (though it's clear once you think about it).  I ended up taking a more quasirandom approach.  (Taking points that were solutions to some standard polynomial family (Legendre I guess)).

I'm not a mathematician, but wouldn't it be safe to choose random x, y, z, then scale that to the unit vector?  I'm positive there's going to be a reason that doesn't work, but I'm not sure what it would be.

That still might not uniformly cover the area.  But any way, I had to parameterize with angles for the calculation, so it was natural to use those. 

[Kirian]

http://mathworld.wolfram.com/SpherePointPicking.html

Amusingly, my method works if x, y, and z are chosen by Gaussian distribution, not linear distribution.  (Eq 16 in that link)

[werothegreat]

Once we figure out quantum computing, this will all be trivial.

[Davio]

I once made a method that did new Random() every time it was called, but the gaps between the calls were so small that it often used the same seed!

A simple seed is often based on time, like number of milliseconds since 1970. Now this in itself isn't a huge problem, but it is exacerbated by inaccurate system and operating system clocks.

And while this sort of thing can be a problem, it's highly unlikely to be a problem when the calls are spread out over not just seconds but minutes.

Humans suck at seeing randomness.  This is likely to be true until the end of time.

That is true, but it's also easy to screw up your implementation. You could also be using a simplified implementation (new Random()) when you can use a better one (new SecureRandom()) for instance.

[Cave-o-sapien]

Slightly off-topic, but related:

One of the interesting side-effects of the card areas (hand, in-play, discard, deck etc.) and shuffling rules in Dominion is that cards can get segregated from each other or clumped together. Very rarely are you shuffling your entire deck. You may just be shuffling 1/3 of your deck, so even with an ideal shuffler your deck is not going to be truly randomized.

Has anyone attempted to model this behavior? It would make a great paper.