wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> card simulation
        
(Message started by: lukes new shoes on Nov 27^th, 2002, 4:34pm)

Title: card simulation
Post by lukes new shoes on Nov 27^th, 2002, 4:34pm

what would be the best way to simulate the selection of a random card (from a standard pack of 52 cards) by rolling dice to generate the outcome?

Title: Re: card simulation
Post by Kozo Morimoto on Nov 27^th, 2002, 5:21pm

Other than using a 52 sided die? 4 sided die & 13 sided die?

Title: Re: card simulation
Post by SWF on Nov 27^th, 2002, 7:30pm

I believe a 52-sided die could be made by chopping the corners of polyhedron with the soccer-ball pattern of faces. The soccer-ball (truncated isocahedron) has 32 faces and 20 corners, so chopping off the corners forms 20 new faces for a total of 52. However, they would not be equally likely to come up when this was rolled.

It seems pretty clear to me that the intent of the question is to use a 6-sided die, and to make each of 52 different selections equally likely. By "best" way, it could mean easiest or the method requiring the fewest rolls on average.

Maybe the easiest is to roll 3 times. Multply the first roll by 36, add 6 times the second roll, and add the third roll. This gives a number from 1 to 216. If the number is greater than 208, roll all three again, and repeat until a value from 1 to 208 is obtained. The remainder when dividing this number by 52 is a random value from 0 to 51, which can be used to select a random card.

The expected number of rolls required can be slightly reduced at the expense of additional complexity.

Title: Re: card simulation
Post by wowbagger on Nov 28^th, 2002, 8:27am

Kozo:
How would you use your 4-die and your 13-die?

on 11/27/02 at 19:30:50, SWF wrote:

It seems pretty clear to me that the intent of the question is to use a 6-sided die, and to make each of 52 different selections equally likely. By "best" way, it could mean easiest or the method requiring the fewest rolls on average.

To me it's not at all clear that the solution is supposed to use only 6-sided dice. It's not stated, so you're free to choose - ok, let's restrict ourselves to dice that actually exist. Is there a 13-sided die?
The condition that every card be chosen with the same probability is a must if one understands the question's use of "random" to mean uniformly distributed.

on 11/27/02 at 19:30:50, SWF wrote:

Maybe the easiest is to roll 3 times. Multply the first roll by 36, add 6 times the second roll, and add the third roll. This gives a number from 1 to 216.

Actually it gives a number from 43 to 258, right?
Considering the minimum value obtained, we arrive at 216 distinct values (surprise!), only 8 of which have us repeat the whole procedure. That's an efficiency of about 96% - quite good, but is there an even better way?
I'll think about it tonight if I can't sleep. :)

Title: Re: card simulation
Post by towr on Nov 28^th, 2002, 8:51am

on 11/28/02 at 08:27:18, wowbagger wrote:

Normal dice are 2,4,6,8,10,12,20. You can pretty much make any dice though, but it'll look odd, and role even odder, which is why they're hard to make..

If you had a 13 dice , the 4 dice could give the color, and the 13 dice the number.

if you use a 6,8 and 10-die you can get 97.5% chance at a good cast in the first try.. (480 values, 468 of which give you a card)

Title: Re: card simulation
Post by wowbagger on Nov 28^th, 2002, 8:59am

So if you have a 20-sided die handy and don't care to roll it 13 times:
You can do it in exactly 13 rolls.

It's always nice to have a solution that precludes any chances of never terminating. :D

BTW: I remember that I've already seen a 100-sided "die". Well, it looks almost like a sphere of course.

Title: Re: card simulation
Post by towr on Nov 28^th, 2002, 9:11am

I find it hard to see how they could make a balance 100-sided die.. There's now way to make it from regular faces in a regular way..
hmm.. actually, you could make it as a sort of disc.. a 50 sided piramid with it's base on another 50 sided piramid..

of course you can make a similar thing with 26 faces on each side.. Which gives you a balanced 52 sided die.. (But it won't role all that well, and will be horrid in gameplay, not to mention large)

Title: Re: card simulation
Post by wowbagger on Nov 28^th, 2002, 9:48am

The 100-sided die was actually made up of (at least) two parts: an outer shell an an inner part with the numbers on the faces.

I think it works like this: The inner part is free to move within the shell, while the shell always stops "rolling" with the same spot on top, marking one of the faces of the inner part by a circle as the result. But I really can't remember the details...

Wait, I found a pic on the net: http://www.deigames.com/100sided.html

Title: Re: card simulation
Post by SWF on Nov 28^th, 2002, 11:59am

Oops, I forgot to subtract 42. I incorrectly converted from how this would be done in C++ where the "dice" are numbered from 0 to 5.

The consensus seems to be that the question meant to include "dice" other than cubes. However I still find it hard to believe somebody who can't find a deck of cards would have all those dice.

With two rolls (8d and 20d) a card can be picked 97.5% without additional rolls.
With three rolls (6d, 20d, 20d) 99.67% of the time. With four rolls (6d, 20d, 20d, 20d) 99.9917%.

If the goal is to minimize expected number of rolls required. The expected number of times is 2.0513 by using 8d and 20d, and rerolling both if you fail on the first try. A better expectation is obtained (2.047 rolls expected) with a slight modification:

If 8d and 20d give a value greater than 156, the remainder is a random value from 1 to 4. If the remainder is 4, reroll both dice as before. If it is 1 to 3, combine it with a roll of 20d to give a value from 1 to 60. If greater than 52, remainder is a random value from 1 to 8, which is like a free roll from the 8d. Combine with a roll from the 20d and proceed as from the beginning of the process.

Title: Re: card simulation
Post by Kozo Morimoto on Nov 28^th, 2002, 4:46pm

I'm still trying to figure out some non base-10 solution. Using a 6 sided die, you can simulate 2 sided die (odss/evens) and 3 sided die (1-6,2-5,3-4 pairs) and of course the 6 sided die. Maybe some mixture of weird base-n type solution?

You should be able to make any n sided die by getting a cylindrical shape with the required number of sides? (with the ends sharpened to a point of course) This is how they normally do a 3 sided die - 3 sided cylinder with pointy ends. Sort of looks like a pencil with both ends sharpened.

Title: Re: card simulation
Post by luke's new shoes on Nov 29^th, 2002, 1:14am

it depends how u intepret the question. the best way to do it might be the most efficient way, or an easy to remember way might be the best way to someone else.

Title: Re: card simulation
Post by wowbagger on Nov 29^th, 2002, 2:23am

on 11/29/02 at 01:14:07, luke's new shoes wrote:

an easy to remember way might be the best way to someone else.

I like that interpretation. In this context it would be very useful to have a 13-sided die.

Here in Germany many traditional card games use a deck with fewer cards (and different names for J,Q,K): the numbers run from 7 on upwards while there are still four suits. I know the solution to this modification is below your standards, but I felt like sharing some trivia. :)

Title: Re: card simulation
Post by Kozo Morimoto on Nov 29^th, 2002, 5:57am

OK how about how about using the first die with odd/even for red/black. Then using 3 dice of 1-6/2-5/3-4 triplet, you can generate a base-3 number between 1 to 27 (inclusive), so you have probability of 1/27 to re-roll to get something between 1 to 26.

Title: Re: card simulation
Post by Chronos on Dec 1^st, 2002, 9:24pm

Quote:

So if you have a 20-sided die handy and don't care to roll it 13 times:
You can do it in exactly 13 rolls.

It's always nice to have a solution that precludes any chances of never terminating.

I would dispute this. With 13 rolls of a d20, you have 20¹³ possible rolls. You're saying that you can map those rolls to the set {1..52} such that the same number of rolls maps to each number? That would require that 20¹³ be an exact multiple of 52, which of course it's not. Unless you have some die which is a multiple of 13, you cannot generate a uniform random card in a guaranteed-bounded number of rolls.

I've seen d100s, too, by the way... The ones I saw looked pretty much like golf balls. I'm almost certain that they're not perfectly fair, but they're a good enough approximation for most purposes.

By the way: I suspect that the optimal solution (i.e., minimum expected number of rolls) will never do things like using a single roll for red/black. That's throwing away information which you may as well use elsewhere. By the same token, assuming we're restricting ourselves to the standard dice set of 4,6,8,10,12,20, we might as well not use the 4, 6, or 10 at all, since these can be simulated by other dice with bonus information thrown in for free.

Title: Re: card simulation
Post by wowbagger on Dec 2^nd, 2002, 3:48am

on 12/01/02 at 21:24:10, Chronos wrote:

You're right. I retract my proposition. Always makes me wonder how I fall for a mantrap I've actually discerned already.
Interestingly, this seems to have gone unnoticed for quite a while...

Quote:

By the way: I suspect that the optimal solution (i.e., minimum expected number of rolls) will never do things like using a single roll for red/black. That's throwing away information which you may as well use elsewhere. By the same token, assuming we're restricting ourselves to the standard dice set of 4,6,8,10,12,20, we might as well not use the 4, 6, or 10 at all, since these can be simulated by other dice with bonus information thrown in for free.

I see your point and I agree. Do you think that, by this very argument, one can claim that the optimal solution will use the d20 only?

Maybe one should define two distinct optimal (in the minimum expected number of rolls sense) solution problems:
Firstly using d6 only (as they are most likely available to anyone wanting to simulate random selection of a card using dice), secondly using the set {4, 6, 8, 10, 12, 20}.

Title: Re: card simulation
Post by towr on Dec 2^nd, 2002, 5:23am

If you role a d20 13 times only 20 times out of 8.192*10¹⁶ would you need to rerole, if that worth the bother (which it isn't in any real-life situation)
A normal dice is probably less fair..

Title: Re: card simulation
Post by Chronos on Dec 6^th, 2002, 12:13am

Quote:

I see your point and I agree. Do you think that, by this very argument, one can claim that the optimal solution will use the d20 only?

That depends. Do you mean the solution for the specific deck-of-cards problem, or the solution for simulating an arbitrary die? In the latter case, we definitely don't want to restrict ourselves to the d20: A d12 will do a much better job of simulating a d12 than a d20 will.

I suspect that we'll also want to keep the d12 around for the 52 problem, but I can't prove it. I likewise suspect-without-proof that we can safely junk the d8. At worst, we can simulate a d8 with two rolls of a d20, and with oodles of extra information.

Title: Re: card simulation
Post by wowbagger on Dec 6^th, 2002, 1:45am

on 12/06/02 at 00:13:30, Chronos wrote:

That depends. Do you mean the solution for the specific deck-of-cards problem, or the solution for simulating an arbitrary die?

I was referring to the deck-of-cards problem. Even in this case the optimal solution doesn't always use the d20 only - if you consider the number of cards a variable.