-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

From: "Robert A. LaBudde" <ral@LCFLTD.COM>
> At 09:27 AM 8/13/02 -0700, Brian wrote:

Err... Brendan, but yeah.

> >I'm sorry, I just have to. :o)  Has anyone considered making
> >normalized dice?
> >
> >The problem with truely random dice is that it can make certain
> >games boring.  For instance:  playing Risk, some of my friends and
> >I have discovered that we will occasionally get on streaks of
> >really bad rolling, where we should have little or no resistance
> >to our force, yet our 30 some armies get devastated by no more
> >than 7 enemy armies.
> >
> >So, one of my friends, who is a computer scientist came up with
> >the idea to make dice that biased, not completely altered, but
> >biased the roll such that there was not equal probability of
> >hitting any number after the first roll.  Instead there was a
> >weighting towards numbers which had been rolled less often.
>
> This is called "equidistribution" or "uniformity", which is
> commonly confused with "randomness", even by experts.
>
> What does "random" mean? It means that there is zero
> autocorrelation to high order, or the spectrum is near-"white".
> This does not require equidistribution.
>
> For example, the sequence {1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,...} is
> perfectly equidistributed, but not random.
>
> The term "uniform random numbers" should be used to indicated the
> presence of both attributes.
>
> >Anyway, making a random number to sort with is not too difficult.
> >It's the making a weighting system without to heavily or too
> >lightly biasing the dice that's the problem.  Since this principle
> >doesn't conform to natural law, there is no predefined formula set
> >that can be used for this.
> >
> >So, does anyone see how to do this easily?
>
> This type of solution is called a quasi-random sequence. It's quite
> easy to do. A simple method is to just use the fractional part of
> k*sqrt(2), k=1,2,3,...  Obviously this just translates into a
> multiplicative-congruential generator of a type.
>
> A better method for a PIC in assembler is to use a Hammersley
> sequence:
>
> For each k=1,2,3,...
>
> 1. Express k in binary (e.g., "6" = "1100"). (This is easy on a
> PIC!) 2. Reflect the number to give a binary fraction (e.g., for
> "6" -> "0011"). (This is also easy on a PIC).
> 3. Express the answer as a number x in [0,1].
> 4. If you want a die roll from 1..6, use 6*x+1 as your value.
>
> Very simple, but it gives equidistribution to O(1/N) and has high
> apparent randomness (i.e., low autocorrelations).
>
> By the way, this sequence of numbers is superior for any purpose to
> any form of pseudorandom numbers. The equidistribution even on
> subsets is asymptotically guaranteed, it gives more accurate
> answers in estimation problems. It also has guaranteed low
> autocorrelations.

I have got to say that that is the best answer that I have ever heard
about this subject, though I am having some difficulty understanding
your algorithm.

First, does your algorithm take a random seed?  From here, it looks
like it doesn't.  Or is a random seed in this case used by forcing a
specific value as a starting point?

> 1. Express k in binary (e.g., "6" = "1100"). (This is easy on a
> PIC!)

Ok, so use the common dice numbers multiplied by 2?

> 2. Reflect the number to give a binary fraction (e.g., for "6" ->
> "0011"). (This is also easy on a PIC).

Yep

> 3. Express the answer as a number x in [0,1].

Meaning express the binary reflection of the each number as
0=<x=<1?

If so, how is this done in assembly, given that there are no
fractions available?

> 4. If you want a die roll from 1..6, use 6*x+1 as your value.

Is k then the result so that the generator feeds back into itself?
Or would that produce the very autocorrelations that we're attempting
to avoid?

Given that this algorithm seems not to look at previously selected
numbers, how is equidistribution guaranteed?

My original thought on the way to handle this was to generate a
random number from 0 to 255, then take all the possible numbers, and
give them catchment zones equaly distributed from 0 to 255.  Then,
the system would take the results and store them, and weight the
catchment zones accordingly.

Thanks for your input.

- --Brendan

-----BEGIN PGP SIGNATURE-----
Version: PGPfreeware 6.5.8 for non-commercial use <http://www.pgp.com>

iQA/AwUBPVlDAgVk8xtQuK+BEQIvfACgzgvIknFbzPZIEzshfgYwlFlh9JQAoIAG
pION6lw7QTV8Co2R4qKxy6ou
=k8zy
-----END PGP SIGNATURE-----

--
http://www.piclist.com#nomail Going offline? Don't AutoReply us!
email listserv@mitvma.mit.edu with SET PICList DIGEST in the body