I believe the reason backgammon has six points to a board is because
dice have six sides. In ancient times dice were one of the few means
to randomly select choices for games. But today we have computers to
randomly select numbers between any range. I am wondering what a board
with seven points per quadrant and a so-called 7-sided dice be like to
play. All the same rules of regular backgammon would apply except that
the game board would be a point longer in each quadrant and the dice
would randomly choose a number from 1 to 7 inclusive. I thought
a computer or other electronic device would be needed to randomly pick
a number from 1 to 7, but now I am wondering if this could be done with
regular 6-sided dice. My question is, using as few six-sided dice as
needed, could players randomly select between the numbers 1 through 7?
For example, I know how to randomly select a number from 1 to 18 inclusive
using just two dice:
1st dice as shown multiplied by 2nd dice at face value
1 or 6 -> 1 1 = 1 , 2 = 2, etc.
2 or 5 -> 2
3 or 4 -> 3
Any help? Suggestions?
--
Douglas Zander |
dza...@solaria.sol.net |
Milwaukee, Wisconsin, USA |
It's not possible to guarantee doing it in a finite number of throws.
If your strategy required throwing the die n times, then you would have
6^n different cases, but this number is not evenly divisible by 7 for
any n. (Contrast with 1-18, where you have n=2 and 18 divisible by 6^2
= 36.)
Of course, it's possible to create some potentially unending strategy.
You can throw two dice colored red and blue, which gives you 36
possibilities. If it's double-6, then rethrow the dice until you get
something other than double-6 (which might take forever). Once you're
done with that, you've got 35 cases which you can break down into seven
equal sets. (The simplest way that I can see to do that is to label it
by the number of the red die if the two dice are unequal and "7" if the
dice are equal.)
Or go down to your local fantasy gaming store and buy a pair of
octahedral dice with eight faces instead of six and block one side off
of each side.
-Matthew
--
Matthew Daly mwd...@pobox.com
My opinions may have changed, but not the fact that I am right - Ashleigh Brilliant
The views expressed here are not necessarily those of my employer, of course.
--- Support the anti-Spam amendment! Join at http://www.cauce.org ---
>summary: using 6-sided dice, choose between 7 choices randomly.
> I believe the reason backgammon has six points to a board is because
>dice have six sides. In ancient times dice were one of the few means
>to randomly select choices for games. But today we have computers to
>randomly select numbers between any range.
The pseudo-random numbers generated by computers are not the same as
tossing a die. For example, *ALL* such computer generated "random"
sequences must repeat; this won't happen with a real die. The computer
generated numbers are deceptively similar however.
>I am wondering what a board
>with seven points per quadrant and a so-called 7-sided dice be like to
>play. All the same rules of regular backgammon would apply except that
>the game board would be a point longer in each quadrant and the dice
>would randomly choose a number from 1 to 7 inclusive. I thought
>a computer or other electronic device would be needed to randomly pick
>a number from 1 to 7, but now I am wondering if this could be done with
>regular 6-sided dice. My question is, using as few six-sided dice as
>needed, could players randomly select between the numbers 1 through 7?
>For example, I know how to randomly select a number from 1 to 18 inclusive
>using just two dice:
>1st dice as shown multiplied by 2nd dice at face value
>1 or 6 -> 1 1 = 1 , 2 = 2, etc.
>2 or 5 -> 2
>3 or 4 -> 3
This doesn't work! First, it is impossible to get a prime number bigger
than 6; you can't get a 7, 11, 13, nor a 17 with this method. Furthermore,
the numbers that do occur are not equi-probable. E.g. The only way to
get a 1 is to roll a 1 on the first die and a 1 or 6 on the second die.
The probability of this happening is (1/6)*(2/6) = 1/18. You can get
a 6 by (die1 = 6 and die2 = 1 or 6), (die1 = 3 and die2 = 2 or 5),
or (die1=2 and die2 = 3 or 4). This probability is 3*(1/18) = 1/6.
It is possible to get 18 equi-probable choices from a single roll of
2 dice. Map each distinct non-double to the integers from 1 through 15.
Map the doubles 11 and 22 to 16, 33 and 44 to 17, and 55 and 66 to 18.
The problem with using dice to get 7 equi-probable choices is that no
power of 6 is divisible by 7. Thus, we can't assign every possibility
to a number; if we roll an unassigned possibility, then we must roll
again. We can get 7 equi-probable choices from 2 dice by assigning
2 of distinct non-doubles to the integers 1 through 6. Assign one
remaining non-double and two of the doubles to 7.
--
Glenn C. Rhoads http://remus.rutgers.edu/~rhoads/
Rutgers University Phone: (732) 445-4869
Dept. of Computer Science email: rho...@paul.rutgers.edu
Piscataway, NJ
This is a bit more difficult than it appears. In your example to select
between 1 and 18, the probability of any number coming up is not the same as
every other number. That is, you are twice as likely to roll a value of 2
as you are to roll a value of 1. (To roll a 1 with your method, the dice
would have to come up as 1-1 or 1-6. To roll a 2, the dice could be any of
1-2, 1-5, 2-1 or 2-6.) Even worse, there is no way to roll a value of 7,
11, 13 or 17, since these are all prime numbers and you can't produce them
by multipling values from the face of a dice.
Even if you rolled 3 dice and added the values, you would have similar
problems.
>It's not possible to guarantee doing it in a finite number of throws.
>If your strategy required throwing the die n times, then you would have
>6^n different cases, but this number is not evenly divisible by 7 for
>any n. (Contrast with 1-18, where you have n=2 and 18 divisible by 6^2
>= 36.)
>
>Of course, it's possible to create some potentially unending strategy.
>You can throw two dice colored red and blue, which gives you 36
>possibilities. If it's double-6, then rethrow the dice until you get
>something other than double-6 (which might take forever). Once you're
>done with that, you've got 35 cases which you can break down into seven
>equal sets. (The simplest way that I can see to do that is to label it
>by the number of the red die if the two dice are unequal and "7" if the
>dice are equal.)
It's not really any more unending than having to reroll cocked dice.
:
:>I am wondering what a board
:>with seven points per quadrant and a so-called 7-sided dice be like to
:>play. All the same rules of regular backgammon would apply except that
:>the game board would be a point longer in each quadrant and the dice
:>would randomly choose a number from 1 to 7 inclusive. I thought
:>a computer or other electronic device would be needed to randomly pick
:>a number from 1 to 7, but now I am wondering if this could be done with
:>regular 6-sided dice. My question is, using as few six-sided dice as
:>needed, could players randomly select between the numbers 1 through 7?
:
:>For example, I know how to randomly select a number from 1 to 18 inclusive
:>using just two dice:
:>1st dice as shown multiplied by 2nd dice at face value
:>1 or 6 -> 1 1 = 1 , 2 = 2, etc.
:>2 or 5 -> 2
:>3 or 4 -> 3
:
:This doesn't work! First, it is impossible to get a prime number bigger
:than 6; you can't get a 7, 11, 13, nor a 17 with this method. Furthermore,
:
oops! you are correct, this does not work what I meant was to multiply the
first die by 6 after subtacting 1 (after mapping) then adding the second die:
1 or 6 -> 0
2 or 5 -> 1 multiply by 6 then add second die
3 or 4 -> 2
( (die1 - 1) * 6 ) + die2
I believe this is perfectly random, yes? :-)
:The problem with using dice to get 7 equi-probable choices is that no
:power of 6 is divisible by 7. Thus, we can't assign every possibility
:to a number; if we roll an unassigned possibility, then we must roll
:again. We can get 7 equi-probable choices from 2 dice by assigning
:2 of distinct non-doubles to the integers 1 through 6. Assign one
:remaining non-double and two of the doubles to 7.
did I mention that you may use as many dice as you wanted?
Anyways, I think you are correct. It is just plain impossible, no?
:
:--
:Glenn C. Rhoads http://remus.rutgers.edu/~rhoads/
:Rutgers University Phone: (732) 445-4869
:Dept. of Computer Science email: rho...@paul.rutgers.edu
:Piscataway, NJ
Glenn Rhoads <rho...@sonora.rutgers.edu> wrote in article
<6h0n5o$2...@sonora.rutgers.edu>...
>
> The pseudo-random numbers generated by computers are not the same as
> tossing a die. For example, *ALL* such computer generated "random"
> sequences must repeat; this won't happen with a real die. The computer
> generated numbers are deceptively similar however.
Umm... actually, non-repeating pseudo-random sequences do exist:
Assume 'r' is a repeating sequence of pseudo-random numbers with an
unknown cycle length. For 'n':th number 'r(n)' in the sequence, if
'Parity(n)=0', let 's(n)=r(n)', otherwise let 's(n)=RandMax-r(n)'.
Then 's' is a non-repeating sequence of pseudo-random numbers.
Because the parity function is a non-repeating function, modulating
any repeating sequence with it will make the resulting sequence non-
repeating. Proof left for the reader as an exercise :-)
terv: Risto Lankinen
dza...@solaria.sol.net (Douglas Zander) writes:
> did I mention that you may use as many dice as you wanted?
> Anyways, I think you are correct. It is just plain impossible,
> no?
-----------------------------------------------------------------
It's possible, but complicated. By using seven dice or rolling a
die seven times and counting the number of occurances of each
number 1..6, you would be partitioning 7 objects into 6 groups.
The total number of combinations possible would be 12C6 or 924.
You would then convert the combination to a value between 0 and
923 and take the modulus of that value divided by 7 and add 1 to
the result.
-----------------------------------------------------------------
Derek Asari
eq...@cleveland.freenet.edu
> yes, but couldn't a *totally* random device be constructed that is based
> on either 1) a resister/capacitor pair that will guarentee total
> randomness? my computer science professor claimed once that there was a
> way to produce real random numbers by using a resistor/capacitor pair
> that would take advantage of some physics principle where you can not
> be certain of how much resistance is in a resistor at any point in time.
> 2) could we time how long it takes for a switch to be pressed and then use
> that time (in micro-second increments) to seed a random generator, thus
> assuring true random numbers based on the time interval that a button is
> pressed on a device.
It's possible, but not practical. It takes time to get truly random numbers
in the real world. You have to clear your measuring device, for example,
in order to make sure you aren't influenced by the previous bit. This is
true whether or no you're throwing dice or taking some quantum mechanical
measurement.
If you're timing how long it takes a switch to be pressed in micro-second
increments, then obviously you've got to have something pressing that
switch in intervals that take significantly longer than a micro-second,
which is a bit of time for a computer that it could be using to generate
pseudo-random numbers. And of course, using that as a seed of a pseudo-random
number generator means that the numbers you get are only pseudo-random, not
truly random.
Of course, this is a good way of insuring that you don't generate the same
sequence of random numbers every time you turn on the computer, and this
is in fact done for some computers. (My old Apple ][ couldn't do it,
though. That annoyed me.)
-- Randall M! Gee, Keeper of Gummi Wisdom
(g...@math.berkeley.edu)
>Matthew Daly wrote in message
><36e7d330....@newsserver.rdcs.kodak.com>...
>>I'll never forget the time that dza...@solaria.sol.net (Douglas Zander)
>>said:
>>
>>>summary: using 6-sided dice, choose between 7 choices randomly.
[...]
>>>For example, I know how to randomly select a number from 1 to 18 inclusive
>>>using just two dice:
>>>1st dice as shown multiplied by 2nd dice at face value
>>>1 or 6 -> 1 1 = 1 , 2 = 2, etc.
>>>2 or 5 -> 2
>>>3 or 4 -> 3
>>>
>>>Any help? Suggestions?
>
>This is a bit more difficult than it appears. In your example to select
>between 1 and 18, the probability of any number coming up is not the same as
>every other number. That is, you are twice as likely to roll a value of 2
>as you are to roll a value of 1. (To roll a 1 with your method, the dice
>would have to come up as 1-1 or 1-6. To roll a 2, the dice could be any of
>1-2, 1-5, 2-1 or 2-6.) Even worse, there is no way to roll a value of 7,
>11, 13 or 17, since these are all prime numbers and you can't produce them
>by multipling values from the face of a dice.
It can be rectified. If your first die was X and the second die was Y,
then let Z be (X/2 - 1), rounded up if necessary. 6Z+Y is a uniform
distribution on 1-18.
>>Of course, it's possible to create some potentially unending strategy.
>>You can throw two dice colored red and blue, which gives you 36
>>possibilities. If it's double-6, then rethrow the dice until you get
>>something other than double-6 (which might take forever). Once you're
>>done with that, you've got 35 cases which you can break down into seven
>>equal sets. (The simplest way that I can see to do that is to label it
>>by the number of the red die if the two dice are unequal and "7" if the
>>dice are equal.)
>
>It's not really any more unending than having to reroll cocked dice.
I disagree. The crucial issue is whether there is a finite number of
rolls in which you can be assured that an acceptible result will be
obtained. This can not be done in the "roll until you don't get double
sixes" question, since for any number n, there is a (1/36)^n probability
that you will roll double sixes n times. By contrast, if you roll
cocked dice, your reroll will be much more careful and your third roll
(if needed) would be so controlled that the probability of recocking
would be nil.
ObPuzzle: The method listed here gives you a probability distribution
that might be described as (1/7, 1/7, 1/7, 1/7, 1/7, 1/7, 1/7). Using
only an unbiased die, give a method for finding _any_ probability
distribution. For instance, if I decided upon being doubled that I
would drop with probability sqrt(1/5), take with probability 1/pi, and
otherwise take and immediately redouble, how would I use a die to decide
which method to use?
I think one can safely assume that even with the most careless roll there
will be a finite probability of cocked dice as well, ensuring that in
principle the cases are equal.
Also, I disagree to the ...which may take forever... part. The probability
of an infinite series of double-6 (or cocked dice) will be 0. However the
procedure may take arbitrarily long.
|> ObPuzzle: The method listed here gives you a probability distribution
|> that might be described as (1/7, 1/7, 1/7, 1/7, 1/7, 1/7, 1/7). Using
|> only an unbiased die, give a method for finding _any_ probability
|> distribution. For instance, if I decided upon being doubled that I
|> would drop with probability sqrt(1/5), take with probability 1/pi, and
|> otherwise take and immediately redouble, how would I use a die to decide
|> which method to use?
Partition the interval 0-1 into subintervals of length each corresponding
to the desired probabilities (eg [0,sqrt(1/5)], [sqrt(1/5), sqrt(1/5)+1/pi],
[sqrt(1/5)+1/pi,1] ).
Then throw the die repeatedly and using 6 as 0 consider the results to be
the digits of a hexary fraction. After some finite time, often after just
a throw or two, this fraction can be seen to fall within one of the intervals,
and the corresponding action should be taken.
Spend 5 or 10 minutes practising hexary arithmetic before trying this out
over the table :-)
--
stein....@fou.telenor.no - http://www.fou.telenor.no/fou/ttkust
<snip>
> >>
> >>>For example, I know how to randomly select a number from 1 to 18 inclusive
> >>>using just two dice:
> >>>1st dice as shown multiplied by 2nd dice at face value
> >>>1 or 6 -> 1 1 = 1 , 2 = 2, etc.
> >>>2 or 5 -> 2
> >>>3 or 4 -> 3
> >>>
> >>>Any help? Suggestions?
> >
> >This is a bit more difficult than it appears. In your example to select
> >between 1 and 18, the probability of any number coming up is not the same as
> >every other number. That is, you are twice as likely to roll a value of 2
> >as you are to roll a value of 1. (To roll a 1 with your method, the dice
> >would have to come up as 1-1 or 1-6. To roll a 2, the dice could be any of
> >1-2, 1-5, 2-1 or 2-6.) Even worse, there is no way to roll a value of 7,
> >11, 13 or 17, since these are all prime numbers and you can't produce them
> >by multipling values from the face of a dice.
>
> It can be rectified. If your first die was X and the second die was Y,
> then let Z be (X/2 - 1), rounded up if necessary. 6Z+Y is a uniform
> distribution on 1-18.
>
> >>Of course, it's possible to create some potentially unending strategy.
> >>You can throw two dice colored red and blue, which gives you 36
> >>possibilities. If it's double-6, then rethrow the dice until you get
> >>something other than double-6 (which might take forever). Once you're
> >>done with that, you've got 35 cases which you can break down into seven
> >>equal sets. (The simplest way that I can see to do that is to label it
> >>by the number of the red die if the two dice are unequal and "7" if the
> >>dice are equal.)
> >
> >It's not really any more unending than having to reroll cocked dice.
>
> I disagree. The crucial issue is whether there is a finite number of
> rolls in which you can be assured that an acceptible result will be
> obtained. This can not be done in the "roll until you don't get double
> sixes" question, since for any number n, there is a (1/36)^n probability
> that you will roll double sixes n times. By contrast, if you roll
> cocked dice, your reroll will be much more careful and your third roll
> (if needed) would be so controlled that the probability of recocking
> would be nil.
>
> ObPuzzle: The method listed here gives you a probability distribution
> that might be described as (1/7, 1/7, 1/7, 1/7, 1/7, 1/7, 1/7). Using
> only an unbiased die, give a method for finding _any_ probability
> distribution. For instance, if I decided upon being doubled that I
> would drop with probability sqrt(1/5), take with probability 1/pi, and
> otherwise take and immediately redouble, how would I use a die to decide
> which method to use?
>
> -Matthew
>
Similar formulas can be used to choose among any number N of choices if N is
of the form (2^p)(3^q) where p and q are nonnegative integers. The general
problem has me stumped even if N is limted to integers, let alone
transcendentals ... I don't see how the problem can ever be solved for the
latter in a finite number of rolls. It probably would not be too hard to
work out a method that would converge to the desired result ... which reminds
me of a story.
Professor Algorithm was asked by his computer science students what he meant
by the phrase, "for all practical purposes." He responded by asking all the
men in the class to line up on one side of the room, and all the women on the
other.
"Now suppose," he said, "that I asked each group to move half the distance to
the center of the room, then half the remaining distance, and so on .... As
you bright students know, the groups would never meet in theory."
"However," he smiled, "in a relatively small number of iterations... you
would be close enough for all practical purposes!"
-----== Posted via Deja News, The Leader in Internet Discussion ==-----
http://www.dejanews.com/ Now offering spam-free web-based newsreading
All such devices have problems with the philosophical issues of what
"totally random" or "true random" means. If you know how it works, it
isn't really random. And if you don't know how it works, how can you
tell if it is really random or just apparently random?
The pragmatic approach is a converse Turing test, claiming that
"apparently random" is good enough. Get some output and do statistical
analysis on it. If it looks random, it is random. For cyclical
computer-generated sequences, this implies that it is a requirement that
the cycle be substantially(?) longer than any intended statistical test
or actual use.
Somebody else posted a solution which uses 35 out of 36 possibilities
from 2 dice, but is a little complicated. On the other hand, it will
usually give you 1 - 7 in one throw.
Here's a method which will be a little slower but will get there and
is fairly easy to implement:
Throw 2 dice:
Dice 1 = 1,2, or 3 and Dice 2 = Any
-> Result = number on dice 2
Dice 1 = 4,5, or 6 and Dice 2 = 1
-> Result = 7
Dice 1 = 4,5, or 6 and Dice 2 = 2,3,4,5 or 6
-> Throw again
- Gerry
>Any help? Suggestions?
>
>--
> Douglas Zander |
> dza...@solaria.sol.net |
> Milwaukee, Wisconsin, USA |
===========================================================
http://indigo.ie/~gerryq/Brewster/brewster.htm
Brewster Kaleidoscopic Screensaver for Windows 95
The only saver that simulates a real kaleidoscope
===========================================================
> Somebody else posted a solution which uses 35 out of 36 possibilities
> from 2 dice, but is a little complicated. On the other hand, it will
> usually give you 1 - 7 in one throw.
>
> Here's a method which will be a little slower but will get there and
> is fairly easy to implement:
>
> Throw 2 dice:
>
> Dice 1 = 1,2, or 3 and Dice 2 = Any
> -> Result = number on dice 2
>
> Dice 1 = 4,5, or 6 and Dice 2 = 1
> -> Result = 7
>
> Dice 1 = 4,5, or 6 and Dice 2 = 2,3,4,5 or 6
> -> Throw again
>
Or, just get yourself an 8-sided die, and roll it once, rerolling on an 8. Simplest
method I've seen so far, and also the most likely to get you results in the fewest
rolls.
Keith.
> :The problem with using dice to get 7 equi-probable choices is that no
> :power of 6 is divisible by 7. Thus, we can't assign every possibility
> :to a number; if we roll an unassigned possibility, then we must roll
> :again.
Rhoads is correct.
> :We can get 7 equi-probable choices from 2 dice by assigning
> :2 of distinct non-doubles to the integers 1 through 6. Assign one
> :remaining non-double and two of the doubles to 7.
( I don't get it. )
> did I mention that you may use as many dice as you wanted?
> Anyways, I think you are correct. It is just plain impossible, no?
This may work for you. Roll two dice. There are 36 outcomes. 7 x 5 + 1
Reroll if the odd outcome occurs, otherwise convert the
roll ( 2-12 ) to a 1 thru 7.
Rolled Occurs Maps to
2 1 2
3 2 3
4 3 4
5 4 5
6 5 6
7 6 7 **Special
8 5 1
9 4 2
10 3 3
11 2 4
12 1 5
How to handle the special case.
Mark a face on a die. If you roll a 7 and that
marked face is showing, re-roll.
(Or add a varient to the game, the unlucky player
loses his turn in this case :-) )
> :
> :--
> :Glenn C. Rhoads http://remus.rutgers.edu/~rhoads/
> :Rutgers University Phone: (732) 445-4869
> :Dept. of Computer Science email: rho...@paul.rutgers.edu
> :Piscataway, NJ
>
>
> --
> Douglas Zander |
> dza...@solaria.sol.net |
> Milwaukee, Wisconsin, USA |
>
Steve Hammer sha...@isd.net
000=0, 001=1, 010=2, 011=3, 100=4, 101=5, 110=6, 111=7
Just re-roll when you get 000. You could even make a rule that would
allow you to use the 000 without affecting the distribution of numbers.
For example, you could say that a 000 was the same as the last number
rolled.
-=Gabriel=-
::> I believe the reason backgammon has six points to a board is because
::>dice have six sides. In ancient times dice were one of the few means
::>to randomly select choices for games. But today we have computers to
::>randomly select numbers between any range.
::The pseudo-random numbers generated by computers are not the same as
::tossing a die. For example, *ALL* such computer generated "random"
::sequences must repeat; this won't happen with a real die. The computer
::generated numbers are deceptively similar however.
: yes, but couldn't a *totally* random device be constructed that is based
: on either 1) a resister/capacitor pair that will guarentee total
: randomness? my computer science professor claimed once that there was a
: way to produce real random numbers by using a resistor/capacitor pair
: that would take advantage of some physics principle where you can not
: be certain of how much resistance is in a resistor at any point in time.
: 2) could we time how long it takes for a switch to be pressed and then use
: that time (in micro-second increments) to seed a random generator, thus
: assuring true random numbers based on the time interval that a button is
: pressed on a device.
In principle, one could build a randomizing device but every such attempt
I've heard about produced much worse results than any decent pseudo-random
generator. It should be possible to combine the two to get a sequence
that is even better than either alone and avoid the non-repetitiveness
of the psuedo-random sequence. To get a *totally* unpredictable random
device seems to require that you make use of some random quantum
phenomenon, perhaps the random decay of some sub-atomic particle.
But I have no idea of how to build one, that is, if it is technically
feasible.
::The problem with using dice to get 7 equi-probable choices is that no
::power of 6 is divisible by 7. Thus, we can't assign every possibility
::to a number; if we roll an unassigned possibility, then we must roll
::again...
: did I mention that you may use as many dice as you wanted?
: Anyways, I think you are correct. It is just plain impossible, no?
It is impossible to do with a finite bound on the number of rolls.
:> The pseudo-random numbers generated by computers are not the same as
:> tossing a die. For example, *ALL* such computer generated "random"
:> sequences must repeat; this won't happen with a real die. The computer
:> generated numbers are deceptively similar however.
:Umm... actually, non-repeating pseudo-random sequences do exist:
:Assume 'r' is a repeating sequence of pseudo-random numbers with an
:unknown cycle length. For 'n':th number 'r(n)' in the sequence, if
:'Parity(n)=0', let 's(n)=r(n)', otherwise let 's(n)=RandMax-r(n)'.
:Then 's' is a non-repeating sequence of pseudo-random numbers.
:Because the parity function is a non-repeating function, modulating
:any repeating sequence with it will make the resulting sequence non-
:repeating. Proof left for the reader as an exercise :-)
Sorry, but this doesn't work. You've managed to lengthen the period
but it still repeats.
A simple application of the pigeon-hole principle shows that a
deterministically generated sequence on a finite state machine
MUST repeat. You can use any computable function you like.
Proof: see any basic text on automata theory.
>> did I mention that you may use as many dice as you wanted?
>> Anyways, I think you are correct. It is just plain impossible,
>> no?
>-----------------------------------------------------------------
>It's possible, but complicated. By using seven dice or rolling a
>die seven times and counting the number of occurances of each
>number 1..6, you would be partitioning 7 objects into 6 groups.
>The total number of combinations possible would be 12C6 or 924.
>You would then convert the combination to a value between 0 and
>923 and take the modulus of that value divided by 7 and add 1 to
>the result.
>-----------------------------------------------------------------
This doesn't work. Rolling a die 7 times produces 6^7 possibilities.
6^7 is not divisible by 7, thus there is no way to partition all
the possibilities into 7 equi-probable sets. It's impossible with
a finite bound on the number of rolls because no power of 6 is
divisible by 7.
Incidentally, there are 12C5 = 792 ways to partition 7 distinct objects
into 6 groups. 792 is not divisible by 7 and even if it were, your
proposed method wouldn't work because all partitions are not
equi-probable. You can see this with just two dice; the partition
1 2 can occur two ways while the partition 1 1 can occur in only one
way.
Well, his example won't repeat. But you are also right in saying "a
deterministically generated sequence on a finite state machine
MUST repeat." The key is that it's not a finite state machine as explained
here because the machine can hold arbitrarily large n. As far as this
pertains to the question, which is can you generate really random numbers,
it doesn't matter anyways because modulating the sequence by parity won't
make them any more random, just because they don't repeat. If you
considered that random, you'd have to consider the parity function itself a
random production of 0's and 1's. :-)
Just because it happens with probability 0 doesn't mean it can't take
forever.
}If you're timing how long it takes a switch to be pressed in micro-second
}increments, then obviously you've got to have something pressing that
}switch in intervals that take significantly longer than a micro-second,
}which is a bit of time for a computer that it could be using to generate
}pseudo-random numbers. And of course, using that as a seed of a pseudo-random
}number generator means that the numbers you get are only pseudo-random, not
}truly random.
}
}Of course, this is a good way of insuring that you don't generate the same
}sequence of random numbers every time you turn on the computer, and this
}is in fact done for some computers. (My old Apple ][ couldn't do it,
}though. That annoyed me.)
It could. The Apple II has a counter in low memory which increments while
it is waiting for keyboard input. This can be used as a random number
seed, and is used as such in INTBASIC. Applesoft (being a Microsoft
product) used different locations for the random number seed, but two
peeks and pokes could solve that.
Of course, this information probably comes 10 years too late! :-)
--
Matthew T. Russotto russ...@pond.com
"Extremism in defense of liberty is no vice, and moderation in pursuit
of justice is no virtue."
>| :> The pseudo-random numbers generated by computers are not the same as
>| :> tossing a die. For example, *ALL* such computer generated "random"
>| :> sequences must repeat; this won't happen with a real die. The
>| :> computer generated numbers are deceptively similar however.
>| :Umm... actually, non-repeating pseudo-random sequences do exist:
>|
>| :Assume 'r' is a repeating sequence of pseudo-random numbers with an
>| :unknown cycle length. For 'n':th number 'r(n)' in the sequence, if
>| :'Parity(n)=0', let 's(n)=r(n)', otherwise let 's(n)=RandMax-r(n)'.
>| :Then 's' is a non-repeating sequence of pseudo-random numbers.
>|
>| :Because the parity function is a non-repeating function, modulating
>| :any repeating sequence with it will make the resulting sequence non-
>| :repeating. Proof left for the reader as an exercise :-)
>| Sorry, but this doesn't work. You've managed to lengthen the period
>| but it still repeats.
>|
>| A simple application of the pigeon-hole principle shows that a
>| deterministically generated sequence on a finite state machine
>| MUST repeat. You can use any computable function you like.
>| Proof: see any basic text on automata theory.
>Well, his example won't repeat.
Any computer implementation will repeat. That is the point I was making,
any computer generated sequence must repeat.
> But you are also right in saying "a
>deterministically generated sequence on a finite state machine
>MUST repeat."
And that is precisely why a computer generated sequence will repeat.
>The key is that it's not a finite state machine as explained
>here because the machine can hold arbitrarily large n.
Then his method as described is not implementable on a computer and
hence doesn't pertain to what I said. To quote my earlier post
" *ALL* such computer generated "random" sequences must repeat"
His example does not refute this. Nor is any refutation possible
for the reasons already mentioned.
Also, the existence of a non-repeating sequence doesn't mean one
could actually generate it. How are you supposed to generate the
sequence if the function used is not computable?
It can. But it won't. Is that a satisfactory answer? :-)
--
David A. Karr "Groups of guitars are on the way out, Mr. Epstein."
ka...@shore.net --Decca executive Dick Rowe, 1962
>ObPuzzle: The method listed here gives you a probability distribution
>that might be described as (1/7, 1/7, 1/7, 1/7, 1/7, 1/7, 1/7). Using
>only an unbiased die, give a method for finding _any_ probability
>distribution. For instance, if I decided upon being doubled that I
>would drop with probability sqrt(1/5), take with probability 1/pi, and
>otherwise take and immediately redouble, how would I use a die to decide
>which method to use?
My solution rot-13'd for those who want to work it out for themselves...
Gb trarengr na rirag jvgu neovgenel cebonovyvgl, rkcerff gur cebonovyvgl
nf n (cbgragvnyyl vasvavgr) "qrpvzny" va onfr 6. Abj, ercrngrq ebyyf bs
n fgnaqneq qvr, cersvkrq jvgu "0." jvyy trarengr n frpbaq fhpu ahzore,
nf ybat nf lbh gnxr n ebyy bs 6 gb pbeerfcbaq gb n qvtvg 0. Fgbc nf fbba
nf lbhe trarengrq ahzore vf rvgure pyrneyl yrff guna, be pyrneyl terngre
guna gur pubfra cebonovyvgl. Yrff guna vzcyvrf fhpprff, terngre guna
vzcyvrf snvyher.
--
Julian Hayward 'Booles' on FIBS jul...@ratbag.demon.co.uk
+44-1344-640656 http://www.ratbag.demon.co.uk/
---------------------------------------------------------------------------
"A monk is expected to be awarded the contract for a 12.2 mile stretch
of the M4 motorway..." - Constructor's World
---------------------------------------------------------------------------
>summary: using 6-sided dice, choose between 7 choices randomly.
>
> I believe the reason backgammon has six points to a board is because
>dice have six sides. In ancient times dice were one of the few means
>to randomly select choices for games. But today we have computers to
>randomly select numbers between any range. I am wondering what a board
>with seven points per quadrant and a so-called 7-sided dice be like to
>play. All the same rules of regular backgammon would apply except that
>the game board would be a point longer in each quadrant and the dice
>would randomly choose a number from 1 to 7 inclusive. I thought
>a computer or other electronic device would be needed to randomly pick
>a number from 1 to 7, but now I am wondering if this could be done with
>regular 6-sided dice. My question is, using as few six-sided dice as
>needed, could players randomly select between the numbers 1 through 7?
>For example, I know how to randomly select a number from 1 to 18 inclusive
>using just two dice:
>1st dice as shown multiplied by 2nd dice at face value
>1 or 6 -> 1 1 = 1 , 2 = 2, etc.
>2 or 5 -> 2
>3 or 4 -> 3
>
>Any help? Suggestions?
>
>--
> Douglas Zander |
> dza...@solaria.sol.net |
> Milwaukee, Wisconsin, USA |
Amusing how many responses and how many ideas were posted. Some
posters even know group theory. Others propose special dice or
complicated schemes. Yet it is quite simple using two standard dice of
different color.
The dice generate a random number 0-35 in a base 6 number system. The
white die is the units digit (with 6 standing for zero), and the red
die is the 6's digit (again 1,2,3,4,5,0). Compute the number 6 * red +
white. You throw out the value zero, using only N = 1,2,3,...,35, and
take your final value n = N mod 7. (mod 7 means divide by 7 and use
only the remainder).
Those who have learned how number systems work will find this
technique immediately obvious. Those who don't will catch on with a
bit of practice.
Well, the function f(n)=n never repeats. So you can say that a computer
can't generate it by the same logic. Which I suppose is technically true.
But you can generate the sequence for as many values as you would ever
need. And calling the function f(n) = n "not computable" is sort of
ridiculous, just because a finite computer can't get arbitrarily high.
The function f(n)=n IS computable, because it can be computed by a Turing
machine. That Turing machine has an infinite amount of memory -- or at
least O(log n) memory, if you prefer.
However, a computer is not a universal Turing machine, because it has a
finite (constant, O(1)) memory, say, a 1 Gigabit (yes, bit) hard drive.
Thus the computer is no more powerful than a finite automaton with
2^(10^9) states.
That's why the computer doesn't work as a tool for proving what is
computable. Ironic, eh?
This really has nothing to do with backgammon anymore, so followups are
set only to rec.puzzles.
--
==================================================================
Mike Soss Please remove the Spanish word
in my address before mailing.
==================================================================
>| >Well, his example won't repeat.
>|
>| Any computer implementation will repeat. That is the point I was making,
>| any computer generated sequence must repeat.
>|
>|
>| > But you are also right in saying "a
>| >deterministically generated sequence on a finite state machine
>| >MUST repeat."
>|
>| And that is precisely why a computer generated sequence will repeat.
>|
>|
>| >The key is that it's not a finite state machine as explained
>| >here because the machine can hold arbitrarily large n.
>|
>| Then his method as described is not implementable on a computer and
>| hence doesn't pertain to what I said. To quote my earlier post
>| " *ALL* such computer generated "random" sequences must repeat"
>| His example does not refute this. Nor is any refutation possible
>| for the reasons already mentioned.
>|
>| Also, the existence of a non-repeating sequence doesn't mean one
>| could actually generate it. How are you supposed to generate the
>| sequence if the function used is not computable?
>Well, the function f(n)=n never repeats.
From what follows, I assume you mean compute f(n) = n over the domain of
positive integers (you can't store a real number).
>So you can say that a computer can't generate it by the same logic.
> Which I suppose is technically true.
It can't generate all positive integers.
>But you can generate the sequence for as many values as you would ever
>need.
I agree. I never made any claim to the contrary. I'm saying that a
computer generated sequence of numbers must repeat and that is all I am
saying. That certainly doesn't mean it might not take a very long time
before it repeats.
>And calling the function f(n) = n "not computable" is sort of
>ridiculous, just because a finite computer can't get arbitrarily high.
Having arbitrarily large integers is not the problem. f(n) is computable
but what you are trying to do is compute *every* integer; this is an
entirely different function and it is not computable.
A function is "computable" iff there is a Turing machine that for any
given input always halts with the correct answer on its tape.
You can certainly compute f(n)=n for any integer you like no matter how
large; the Turing machine tape is infinite so there is no storage problem.
There is a Turing machine that for any input n, will halt with the correct
answer on it. I.e. f(n) is computable.
The function you are trying to compute is
Input: nothing
Output: every integer.
There can be no Turing machine that eventually halts with every integer
appearing on its tape (if it halted after a finite amount of time, then
because the integers are infinite, there must be some integer that hasn't
been written to the tape). Thus, this function is not turing-computable.
I'm not sure if this clears it up for you. If not, you'll have to learn
about Turing machines and computability.
In any case, the only point I was originally making was that all computer
generated sequences of numbers must eventually repeat. That doesn't
mean that the period (i.e. length) of a sequence might be extremely long;
so long that it would take an unreasonable amount of time for your
computer to output the entire sequence. By unreasonable amount of time
I mean lifetimes, centuries, millions of years, etc. But it still
must repeat!
> In article <6h1uus$g...@bgtnsc02.worldnet.att.net>,
> Randall M! Gee <g...@math.berkeley.edu> wrote:
>
> }Of course, this is a good way of insuring that you don't generate the same
> }sequence of random numbers every time you turn on the computer, and this
> }is in fact done for some computers. (My old Apple ][ couldn't do it,
> }though. That annoyed me.)
>
> It could. The Apple II has a counter in low memory which increments while
> it is waiting for keyboard input. This can be used as a random number
> seed, and is used as such in INTBASIC. Applesoft (being a Microsoft
> product) used different locations for the random number seed, but two
> peeks and pokes could solve that.
>
> Of course, this information probably comes 10 years too late! :-)
Ah, see, but it has to take keyboard input. What I was trying to do was
to have the boot program on my disk display a random pretty picture each
time it booted, and, of course, whenever I booted it, it would generate the
same random picture. My Apple ][ didn't have a clock in it, so I couldn't
use that. So I ended up "randomly" generating a seed and saving it for the
next time it booted up.
And, just to keep this at least tangentally appropiate for
rec.games.backgammon, how many people learned backgammon from their
Apple ][s?
The idea of using binary dice (i.e. coins) is clever but I disagree with your
last suggestion ... if 000 is the same as the last number rolled, then the
chance of getting the same result on two consecutive rolls is doubled!! If
my last roll was 7, then I know 7 is twice as likely as any other number to
come up on the next roll.
This won't affect the overall distribution but it DOES "affect the
distribution of numbers" because it results in a non-random distribution.
Otherwise, you could just pick numbers 1,2,3,4,5,6,7 in that order and
restart when you got to 7 ... that also would "not affect the distribution of
numbers" in the sense of producing approximately the same number of
occurrences of each possible outcome. :-)
If you can use non-six-sided dice, the solution is even easier: use a
seven sided die. What would a seven sided die look like? A dremel with
7 sides. It's basically a spinning top with a polygonal
"circumference". When the top stops spinning, it falls on one of the
sides. You can make as many sides as you want.
For that matter, you could use a spinning wheel, a spinning arrow, or
seven chips in a bag.
-=Gabriel=-
The reason I suggested six-sided dice rather than coins is that the
original question asked whether it could be done with six-sided dice.
If you can us something other than six-sided dice, the problem is
easier. Use something like a seven-sided dremel. (I'm not sure of the
spelling. It's a polygonal "top" used for playing some Jewish game of
"Put and Take". Mexicans use something similar for their game of "Put
and Take".)
> I disagree with your
> last suggestion ... if 000 is the same as the last number rolled,
> then the
> chance of getting the same result on two consecutive rolls is
> doubled!!
I was simply looking for a way to avoid the problem of arbitrarily long
re-rolls of 000s. You method of rotating through all the numbers is
probably better. It would still, however, allow the players to know
that a particular number was more likely to occur on the next roll than
the others. Either way, players would simply adjust their playing to
the new probabilities the same way they would adjust their playing to
the new number of points per quadrant. For instance, the six point
might become as important in a 7 point per quadrant game as the 5 point
is now.
A seven-sided regular polyhedron does not exist.
We can make something that looks like a 3-sided ruler
that we roll or something like an unsharpened pencil that
may have seven faces. But an unstated assumption is that
only regular polyhedra qualify as dice.
There are 5 of them:
4 faces (equilateral triangles)
6 faces (squares)
8 faces (equilateral triangles)
12 faces (regular pentagons)
20 faces (equilateral triangles)
As has been made clear, the number of cells in the sample space can
be expressed (4^a)*(6^b)*(8^c)*(12^d)*(20^E) where letters are any
integers: 0, 1 ,2, 3,...
Then we can never get a multiple of 7 as the number of cells,
even taking any combination of any number of different dice.
SO, the idea of taking two ordinary dice mod 7, which gives
36 outcomes, one more than 35, a multiple of seven, is as
close as we are going to come. This scenario, mod 7, gives,
8 = 1, 9 = 2, 10 = 3, 11 = 4, 12 = 5, as well as 1, 2, 3, 4, 5, 6, 7
pips being themselves. Notice that all seven numbers come up
5 times for a total of 35 cells. But seven comes up the sixth time.
Some very clever ways have already been put forth to circumvent
all this, like 3 binary dice, etc. My own suggestion is to have a third
die that is blank on five faces and has an "X" on the sixth face. Three
die are rolled, 2 ordinary and the one with an "X." The X-die only
comes into play when a 7 is rolled. If an X and 7 show, the roll is a
do-over. Otherwise, the X-die is ignored.
NS
>ObPuzzle: The method listed here gives you a probability distribution
>that might be described as (1/7, 1/7, 1/7, 1/7, 1/7, 1/7, 1/7). Using
>only an unbiased die, give a method for finding _any_ probability
>distribution. For instance, if I decided upon being doubled that I
>would drop with probability sqrt(1/5), take with probability 1/pi, and
>otherwise take and immediately redouble, how would I use a die to decide
>which method to use?
Nice puzzle!
SPOILER WARNING
It suffices to show that you can use a die to decide between two events
with any probability distribution. For example, if you have three
events A, B, and C, then you can add the probabilities for A and B together
and first decide between AB or C. If the procedure decides for AB, then
you can repeat the procedure to decide between A and B. This generalizes
to any number of possible events.
To decide between events with probabilities A and B:
Express A as infinite binary fraction (in actuality you would keep
extending a finite fraction until the procedure halts with a decision).
Note that you only need a binary fraction for one of the probabilities;
since the two binary fractions must sum to 1, you can get one binary
fraction from the other by flipping all the bits! For example,
suppose A was .11010001... then B would be .00101110...
Let a roll of 1, 2, or 3 be a 0 and let 4, 5, or 6 be a 1.
Process the bits of A from left to right.
Roll the die.
If it matches the bit of A, then move to the next bit and roll again.
If you roll a 0 and the bit is 1, then decide for A.
If you roll a 1 and the bit is 0, then decide for B.
It's not hard to see that this works. This procedure decides for the
event whose probability is A if and only if the rolls match some initial
(possibly empty) part of the bit fraction for A and ends with a 0 roll
where the corresponding bit is a 1. If the 1's in the bit fraction for
A occur in locations i1, i2, i3, ..., then the probability of this
happening is (1/2)^i1 + (1/2)^i2 + (1/2)^i3 + ... which is precisely
the bit fraction for probability A! (I.e. it decides for the event with
probability A)
Similarly, the procedure decides for the event corresponding to probability
B iff the rolls end at some 0 bit of A. The 0 bits of A correspond to 1
bits of B so that the probability of deciding for the event is the binary
fraction for B.
Puzzle: How can you decide between two events of any probability
(totaling 1 of course!) using a LOADED die? That is, given ANY
non-zero probabilities for each of the 6 sides of a die, use rolls
of the die to decide between two events of any probability.
Oh, anybody can do it with unlimited time available. I thought the problem
called for an ELEGANT solution!
I was very impressed with this solution, although it uses three dice,
whereas most use two. The most common was to roll two dice, and, using
different methods, use 5 different outcomes for each number from one to 7,
and reroll on the 36th outcome. Until now, it was the least likely (1/36)
to require a reroll (contrary to someone's belief that using an 8-sided
die, and rerolling on 8 was least likely, as this has probability of 1/8).
This method however, is even less likely (1/216) to require a reroll, and
much simpler, if you have the most basic knowledge of binary. To the poser
of this problem, I recommend this solution.
-----------
Oops, I forgot, there is a 1/8 chance of rolling a 000, not 1/216, as I
stated. This makes it as likely to require a reroll as using an 8-sided
die, but it is still much simpler, if you know binary. You could also flip
a coin three times, designating heads as 1 and tails as 0. Despite the
likelyhood of having to reroll, I would still use this if I were to play
that backgammon variant. This is the most ingenious solution yet. So
ingenious that even I didn't think of it! (A lot of things get that
honour.)
Matthew Daly wrote in message <35396d6b....@news.frontiernet.net>...
>
>The object, I presume, is to come up with the smallest expected number of
>rolls. Here are the three strategies:
>
>(A) Roll two colored dice, reroll 66, otherwise use 7 if dice are equal or
>red die otherwise
>(B) Roll three colored dice, express as binary, reroll 000, otherwise use
>binary number
>(C) Roll one octal die, reroll 8, otherwise use number.
>
>Rolling two dice, there is a 35/36 chance that (A) will pay off, as
>opposed to a 1 - (1/8)^2 = 63/64 chance that (C) will pay off, so that is
Actually, (C) will pay off 1 - (1/8) = 7/8 chance (because you are only
rolling one die.)
So (A) has the best pay-off here.
>clearly the preferable method (except that it paints outside the lines,
>since the people asked how to do it with a six-sided die). (B) is clearly
>inferior to both, as there is a 7/8 chance that three rolls won't be
>enough, plus it's unintuitive to translate 6 values into binary and then
>translate that back into a number from 1-7 IMHO.
Well, (B) might not be intuitive for some people; others would find it
trivial. There is a slightly easier way, of couse.
Rather than using 3 colored dice with binary values on the face, use 3 dice
with different values. The first die would have three faces with a value of
1; three faces with a value of 0. The second die would have values of 2 and
0. The third die values if 4 and 0. Then just add. (You still need to
re-roll with a value of 0 of course.)
>
>But if we're going to paint outside the lines, then I've got a better
>solution. The original poster wanted to test whether backgammon would
>play differently with more than six points per board. So, instead of
>moving up to seven points, why not test the hypothesis on eight-point
>boards and use normal unadulterated octal dice?
You could lengthen (or shorten) the quadrants of the board w/o changing the
dice as well.
>I was very impressed with this solution, although it uses three dice,
>whereas most use two. The most common was to roll two dice, and, using
>different methods, use 5 different outcomes for each number from one to 7,
>and reroll on the 36th outcome. Until now, it was the least likely (1/36)
>to require a reroll (contrary to someone's belief that using an 8-sided
>die, and rerolling on 8 was least likely, as this has probability of 1/8).
>This method however, is even less likely (1/216) to require a reroll, and
>much simpler, if you have the most basic knowledge of binary. To the poser
>of this problem, I recommend this solution.
The object, I presume, is to come up with the smallest expected number of
rolls. Here are the three strategies:
(A) Roll two colored dice, reroll 66, otherwise use 7 if dice are equal or
red die otherwise
(B) Roll three colored dice, express as binary, reroll 000, otherwise use
binary number
(C) Roll one octal die, reroll 8, otherwise use number.
Rolling two dice, there is a 35/36 chance that (A) will pay off, as
opposed to a 1 - (1/8)^2 = 63/64 chance that (C) will pay off, so that is
clearly the preferable method (except that it paints outside the lines,
since the people asked how to do it with a six-sided die). (B) is clearly
inferior to both, as there is a 7/8 chance that three rolls won't be
enough, plus it's unintuitive to translate 6 values into binary and then
translate that back into a number from 1-7 IMHO.
But if we're going to paint outside the lines, then I've got a better
solution. The original poster wanted to test whether backgammon would
play differently with more than six points per board. So, instead of
moving up to seven points, why not test the hypothesis on eight-point
boards and use normal unadulterated octal dice?
-Matthew
>But if we're going to paint outside the lines, then I've got a better
>solution. The original poster wanted to test whether backgammon would
>play differently with more than six points per board. So, instead of
>moving up to seven points, why not test the hypothesis on eight-point
>boards and use normal unadulterated octal dice?
Disclaimer: I'm not a good player.
On the other hand, I have kept official
score in clubs like the Mayfair in NYC
where the best in the world gambled
multiway for thousands and that was
in the late sixties and early seventies.
I'm going to define "good gambling game."
Chess is not a good gambling game,
because the stronger player can win
almost all the time ruling out masochism,
mental breakdown, boredom, which
are not uncommon in U.S. chess
circles. (Maybe now the novice can
bring a dedicated silent partner. And
chess will become a ggg.)
A good gambling game is one in which
there is a balance of luck and skill that
keeps novices in action.
No-limit poker is a not a good gambling
game, because a novice goes broke when
the expert is able to "turn the cube" from
1 to 64.
Limit poker is a ggg, because the expert
is not always able to protect his/her hand.
I mention poker because
I understand it a little.
What's my point?
You've altered the question.
The ggg nature of backgammon, as
we know it, depends on the
unique properties of six,
probably the perfect number
(pun intended), because of its divisibility
properties, etc., giving more options
to the player, making the game complex,
mysterious, alluring to the novice, yet
allowing him/her to escape almost certain
disaster and win games (that should have
been dropped, having less than 1/3 chance)
with miracle rolls, 17 to 1, 35 to 1 .
Backgammon is a ggg hustle. In each
generation, before computers,
backgammon captured the interest,
imagination, and money of the idle rich.
My concluding point is that:
Primes like seven would be ugly.
A 35-1 shots may become 35-0 shots.
A composite like eight with so much
duplication of 2's would be uninteresting.
NS
I recommended 6-sided dice because that's how the original question was
posed. If I could use something other than 6-sided dice I would have
recommended something like a short seven-sided pencil.
-=Gabriel=-
Caspa.
>
>The pseudo-random numbers generated by computers are not the same as
>tossing a die. For example, *ALL* such computer generated "random"
>sequences must repeat; this won't happen with a real die. The computer
>generated numbers are deceptively similar however.
>
>
For another challenge, what is the best approach (if any) for
generating a random number using just your thoughts? That is, what
mental process could one go through that would generate a random shake
of dice.
At the cost of precision dice, this may be a useful question.
>In rec.puzzles article <6h0n5o$2...@sonora.rutgers.edu>,
>rho...@sonora.rutgers.edu (Glenn Rhoads) wrote:
>:dza...@solaria.sol.net (Douglas Zander) writes:
>:
>:>summary: using 6-sided dice, choose between 7 choices randomly.
>:
>:> I believe the reason backgammon has six points to a board is because
>:>dice have six sides. In ancient times dice were one of the few means
>:>to randomly select choices for games. But today we have computers to
>:>randomly select numbers between any range.
>:
>:The pseudo-random numbers generated by computers are not the same as
>:tossing a die. For example, *ALL* such computer generated "random"
>:sequences must repeat; this won't happen with a real die. The computer
>:generated numbers are deceptively similar however.
>:
> yes, but couldn't a *totally* random device be constructed that is based
> on either 1) a resister/capacitor pair that will guarentee total
> randomness? my computer science professor claimed once that there was a
> way to produce real random numbers by using a resistor/capacitor pair
> that would take advantage of some physics principle where you can not
> be certain of how much resistance is in a resistor at any point in time.
> 2) could we time how long it takes for a switch to be pressed and then use
> that time (in micro-second increments) to seed a random generator, thus
> assuring true random numbers based on the time interval that a button is
> pressed on a device.
That's Random!
jc
All email sent to the address used for this post is deleted unread
(although headers may be used in my spam filters). To reach my real
email box, send to personal@ at the above domain.
>>:The pseudo-random numbers generated by computers are not the same as
>>:tossing a die. For example, *ALL* such computer generated "random"
>>:sequences must repeat; this won't happen with a real die. The computer
>>:generated numbers are deceptively similar however.
It would not be difficult to design a pseudo-random function which
would repeat only after (say) 10^1000 calls. Such a function need not
even be very complicated or slow with present-day hardware.
What, though, if we wanted to repeat only after at least GoogolPlex
calls? ( GoogolPlex = 10^Googol = 10^(10^100) ). Can this be done in
a relatively short and fast program?
By fast, I mean that there would be a lower bound on the calculation
time as well as the length of the program.
- Gerry
===========================================================
http://indigo.ie/~gerryq/Brewster/brewster.htm
Brewster Kaleidoscopic Screensaver for Windows 95
The only saver that simulates a real kaleidoscope
===========================================================
>>:The pseudo-random numbers generated by computers are not the same as
>>:tossing a die. For example, *ALL* such computer generated "random"
>>:sequences must repeat; this won't happen with a real die. The computer
>>:generated numbers are deceptively similar however.
Something that occurred to me during my last post:
If the restriction on computation time is lifted, surely computers can
indeed produce a pseudo-random sequence that never repeats? For
example, successive digits in the expansion of PI. An infinite number
of seeds could also be generated, at the cost of even more computation
time, as follows:
// Computer pseudo-random that is slow but never repeats
// i and seed are stored between calls
// May be necessary to increase storage capacity occasionally...
{
i = i + seed
return the i-th decimal digit of PI
: For another challenge, what is the best approach (if any) for
: generating a random number using just your thoughts? That is, what
: mental process could one go through that would generate a random shake
: of dice.
: At the cost of precision dice, this may be a useful question.
I would pick a 9 or 10 digit number at random (as best I could), take
the remainder mod 43, throw out the number and start again if there was
no remainder and otherwise take the remainder again (mod 6). I assert
that this method would be pretty darned random.
I am aware that I am violating the predetermined amount of time rule
suggested for dice.
Jonathan
Except it would be pretty easy to have a couple of ten digit numbers
(telephone numbers?) memorized that would give you those "cars" when you
really need them.
TCH
> >The pseudo-random numbers generated by computers are not the same as
> >tossing a die. For example, *ALL* such computer generated "random"
> >sequences must repeat; this won't happen with a real die. The computer
> >generated numbers are deceptively similar however.
>
> For another challenge, what is the best approach (if any) for
> generating a random number using just your thoughts? That is, what
> mental process could one go through that would generate a random shake
> of dice.
The method I like to use is to stop a stopwatch calibrated to the
nearest hundredth of a second, preferably when I am not watching the
display while I push the button. This is good enough for flipping a
coin, or rolling a 6-sided die.
--
David Grabiner, grab...@math.lsa.umich.edu
http://www.math.lsa.umich.edu/~grabiner
Shop at the Mobius Strip Mall: Always on the same side of the street!
Klein Glassworks, Torus Coffee and Donuts, Projective Airlines, etc.
Sorry... you have "just your thoughts". No stopwatch or anything else!
>The ggg nature of backgammon, as
>we know it, depends on the
>unique properties of six,
>probably the perfect number
>(pun intended), because of its divisibility
>properties, etc., giving more options
>to the player, making the game complex,
>mysterious, alluring to the novice, yet
>allowing him/her to escape almost certain
>disaster and win games (that should have
>been dropped, having less than 1/3 chance)
>with miracle rolls, 17 to 1, 35 to 1 .
The actual cutoff is closer to 20% chance. (It depends on the
position; it can be as low as 3/16, or as high as 1/4.)
ObPuzzle: Give examples, and explain the 20%.
Seth
Yeah. 3 to 1 (not 1/3).
20% = 1/5 and thus is 4 to 1.
Assuming no gammons or backgammons
in the offing, for every 5 games, on the
average, if one always drops, one is -5 units.
If one always takes, the expected value is
E = 4*(-2) + 1*(+2) = -6, close to breakeven,
especially considering that one holds the cube
(and even may have a shot at a gammon).
NS
TC has touched on the essence of the problem.
One may not be in total control of one's thoughts.
Even subconsciously, one may be tempted or
capitulate to a desire to roll, say "boxcars"
(double sixes).
Machines do not have such problems.
One chess position reached by Kasparov
and Big Blue in their first match would have
put enormous psychological pressure on a
human opponent. Big Blue, unfazed, found the
only line that allowed it to draw by exposing its king,
something GM's rejected at first sight. The move
seemed counterintuitive and ordinarily would have
been suicidal.
In science fiction, machines, like HAL, do have
psychological aspects. Until they do in life, we, humans,
can obtain very long strings of pseudorandom digits that
do not contain repeating strings of sufficient length by
means of reseeding, using the computer's clock.
More to the point, a pseudorandom string may
have substrings of repeating digits and still be
useful in the originally intended way. In particular
applications (like rolling dice) a generated
sequence may need only satisfy distributional
properties to achieve pseudorandomness. And
if repeating strings do begin to come into play,
one could theoretically alter a string and run it
backwards, sort of using the string itself as a
second-order seed.
Humans cannot be trusted to generate any random
strings mentally, since psychologically we are pre-
disposed to creating patterns where there are none,
not recognizing what is random.
An example is the "Bombs Over London" phenominon,
explained this way. In WW II, when caught in an air raid,
many Londoners ran away from the creators (divots)
left by previously dropped bombs, under the assumption
that bombs divots tended to cluster. However, postbellum
tests of many grids, revealed distribution of bombs
satisfied criteria for randomness.
NS
[Take vs. drop]
>>The actual cutoff is closer to 20% chance. (It depends on the
>>position; it can be as low as 3/16, or as high as 1/4.)
>>
>>ObPuzzle: Give examples, and explain the 20%.
>
>Yeah. 3 to 1 (not 1/3).
>20% = 1/5 and thus is 4 to 1.
>
>Assuming no gammons or backgammons
>in the offing, for every 5 games, on the
>average, if one always drops, one is -5 units.
>If one always takes, the expected value is
>E = 4*(-2) + 1*(+2) = -6, close to breakeven,
>especially considering that one holds the cube
>(and even may have a shot at a gammon).
3 to 1: any endgame position where white has a 75% chance of winning
on one roll; if he fails, black wins. It is breakeven whether black
takes or drops. (E.g. White has one man on the 6 point, black one man
on the 3 point.)
3/16: Black and white each have one man one the 6 point. A take is
breakeven (due to ownership of the cube).
20%: Consider the following game (a very simplified one): The score
starts at 50. A coin is tossed; heads, the 1 is added to the score,
tails, 1 is subtracted from the score. At 100, white wins; at 0,
black wins. (It can easily be seen that the score is white's percent
chance of winning in the absence of a cube.) In that game, 80 (and
20) are the breakeven points for doubling/dropping.
The difference between 20% and the 25% usually given is the value of
the ownership of the cube. If it's worthless (e.g. endgame, you win
in one roll if your opponent doesn't win first) then you need 25%. If
it has maximum value (you can redouble at 75%, the cube your opponent
gets back will be worthless) then 3/16 suffices (as seen above). In a
complex early or midgame, 20% is correct (of course, calculating
probability of winning in such a position is nontrivial, and gammons
change the numbers anyway).
Seth
There have been a couple of postings with examples, but so far no
posting giving a derivation for the 3/16, 1/4, or 1/5 figures. The
answers build on each other, starting with the 1/4 figure, so that's
where we'll begin. The discussion assumes no gammons and a cube
starting on 1.
Why do people usually refer to 25% as the drop point?
When you're faced with a cube, you have the choice between dropping and
taking, so you want to calculate your expected results from dropping
with the expected results (or equity) from taking and pick the most
favorable choice.
If you drop, you lose 1 point all the time, so your equity is -1. If
you take, and never use the cube, then if your chance of winning is p,
your equity is the equity you get if you win times the chance of
winning, plus the equity you get when you lose times the chance of
losing, or p*2 + (1-p)*-2 = 2p -2 + 2p = 4p -2.
You take the cube if this equity is greater than the equity of dropping,
so you take if:
4p-2 > -1
4p > 1
p > .25
So the drop point is 25%. What's most important to remember about this
is that you have to win 25% of the games after taking the cube. If
you're never going to use the cube again, then this is the same as a 25%
cubeless winning percent. If you're going to use the cube again, then
you still need to win 25% of the games, but it isn't the same as 25%
cubeless. (If you find yourself in a position in which you win 85% of
the time without the cube, then you can double and win the game, not
risking those 15% losses.)
Why can you sometimes take when you win a little as 3/16ths of the time?
To answer this we first need to address the question of how winning 25%
with the cube translates to a cubeless winning percent. To do this,
we'll use a mathematical model called "continous" backgammon. In a
continuous game, one never goes from 65% winning chances to 80% winning
chances without at some point having a winning chance of every value in
between. This is different from backgammon because it affects the value
of owning the cube. If your opponent's drop point is 25%, then you gain
the most from doubling when you win 75% of the time. If you never jump
from 65% to 80% winning chances, then you can always double at exactly
75% winning chances and get the most possible value from owning the
cube.
How do we translate 25% winning chances with the cube to a cubeless
winning chance in continuous backgammon? We can see that if your ideal
doubling point is 75%, and your cubeless winning chances are 75%, then
your chances of winning with the cube are 100%. You'll double, and your
opponent can drop giving you the win, or your oppponent can take, but by
the definition of the drop point, taking gives you the same expected
winnings as dropping, so no matter what your opponent does your expected
winnings in the game are as if you won the game on the current cube
level.
What if you're not exactly at the drop point? If your ideal doubling
point is 75% and you win 25% of the time cubeless, then you're 1/3rd of
the way from losing (0%) to winning (75%), so you win 1/3rd of the
time. (This is a result of statistical studies of something called
random walks in space.) In general, if your cash point (100% minus your
opponent's take point) is C, and your cubeless winning percent is P,
then your winning percent with the cube is P/C. To solve for the take
point, we set this equal to 25% (you still need to win 25% of the games
when using the dube) and solve for P, to get P = .25 * C.
Why can one sometimes take with as little as 3/16ths (about 18%) winning
chances?
If when you redouble you're giving your opponent a dead cube, then your
ideal doubling point is 75%, as we calculated above. If you can always
reach this point exactly then the game is continuous. As we saw above
you need to win .25 * .75, or 1/4 * 3/4 or 3/16ths of the games in order
to take the cube.
As others have already posted, there is such a position in backgammon,
where you always exactly reach your cash point and you're giving your
opponent a dead cube. If each player has a checker on the 6 point, the
side on roll wins 75% immediately. If they don't bear off, the other
side wins 75% of the time, so is exactly at the cash point.
Why is the take point in a continous game of backgammon equivalent to
winning 20% cubeless?
To take the cube in a continous game, you need to have a cubeless
winning percent of .25 * C, where C is the cash point. If you're giving
your opponent a live cube, then this cash point C is equal to 1 minus
the drop point, which is .25 * C.
.25 * C = 1 - C
1.25 * C = 1
C = 1/1.25 = .80
If your cash point is 80%, your take point is .25 * 80 = 20%.
In a continous backgammon game, the drop point is 20%. Real backgammon
games aren't continuous so you don't always get full value out of owning
the cube. In most positions you can take with approximately 22%
cubeless winning chances.
To summarize, the take point for a dead cube is 25%, if you can always
redouble efficiently and give you opponent a dead cube, your take point
is 3/16ths or 18.75%, the take point for a live cube in a continuous
game is 20%, and in practice in real backgammon one can usually take
with 22% cubeless chances. (All these figures still assume no gammons.)
-Michael J. Zehr
I've read that humans are very bad random number generators. That's one
of the reasons so many people are suspicious of the dice in the on-line
programs: there's a mismatch between true random sequences and what they
think a true random sequence should look like.
On the other hand, there are aspects of human behavior that might be
pretty random, such as the exact number of times our eyes blink in a
minute, or the exact number of sperm produced in a single emission. Two
people could sit there and count each other's eye blinks over time
modulo 6 or something.
-=Gabriel=-
Or I could take my wife to a clothing store and ask her which dress
she likes best.
No - I didn't really mean to write that...I'm just in a strange mood.
I really meant...oh, never mind.
Jon
>I've read that humans are very bad random number generators. That's one
>of the reasons so many people are suspicious of the dice in the on-line
>programs: there's a mismatch between true random sequences and what they
>think a true random sequence should look like.
This is a trick that one can use on the SATs and similar tests: you will
never find four questions in a row with the same answer, though the
probability of that happening were the answers truly random would suggest
that it would be likely to happen at least once over the course of the
test.
--
Jeff Pack <book...@brown.edu>
Brown University, Class of 1999 I refuse the unpoetic existence.
St. Anthony Hall, K'96 The universe will contain passion and
17th-century digital boy grace, even if I have to make it myself...
>
>On the other hand, there are aspects of human behavior that might be
>pretty random, such as the exact number of times our eyes blink in a
>minute, or the exact number of sperm produced in a single emission. Two
>people could sit there and count each other's eye blinks over time
>modulo 6 or something.
>
That does seem more practical than counting the spermatozoa, but would
it be as much fun?