Skip to Content
 

Probabilistic Selection Mechanism

10 replies [Last post]
Thu, 03/09/2006 - 13:16
Nando
Offline
Joined: 07/22/2008

Here's a puzzle. If anyone can offer an elegant solution, that will make me very happy.

I'd like a one-step mechanism (and if it requires two steps, then with each step implemented as consistently and symmetrically as possible) by which a single item is chosen out of two distinct groups, but according to two simple rules and two simple constraints.

First, the setup:
I'd like to have two distinct groups, one (always) homogenous and one (often) heterogenous. To keep things simple and general, assume two groups of colored cubes. The cubes in the homogenous group are all Black and the cubes in the heterogenous group are colored Green, Yellow, or Red. There are no other identifying characteristics on the cubes. (The positioning of the cubes on the board could be used in the solution if necessary. For example, the cubes could be placed in, and identified by, an ordinal position. This is not ideal, though.)

Second, the rules:
1. Of the two groups, I want the chosen cube to tend to come from the smaller group, and I want that tendency to increase as the difference between the groups' sizes increases.

2. If the chosen item is from the heterogenous group, I want the chosen cube to tend to come from the largest sub-group. (This rule is less important than the first. Really, I would only expect this to hold when the largest sub-group is a majority. In fact, straight-up random is probably fine. :P Just kidding, random is not preferred.)

Third, the constraints:
1. It should work if the heterogenous group iincludes one color or as many as four colors. (If you can only get three, I'll take it!)

2. It should work with small group sizes. I think probably not more than 6 cubes in either group, or 12 total.

Example 1:
Group 1: BBBB
Group 2: GGGYYR

In this situation, I would like the B group (meaning any B cube) to be identified a little more than half of the time. If the B group is not chosen, I would like a G cube to be most-likely chosen. (Or, better perhaps, for the R cube to be least-likely chosen.)

Example 2:
Group 1: BBBBBB
Group 2: GGY

In this situation, I would like the B group to be identified fairly infrequently. I would like a G cube indicated most of the time.

So that's it. Any ideas are greatly appreciated, but remember the goals: identify 1 cube according to the rules, quickly, and elegantly. Thanks for reading.

Top
Thu, 03/09/2006 - 13:45
#1
sedjtroll
sedjtroll's picture
Offline
Joined: 07/21/2008
Probabilistic Selection Mechanism

Does it have to be only 'most of the time'? Why not make the rules hard and fast - you take the cube from the largest subsection of the smallest group, period?

One idea might be to drop the groups of cubes into a bag, and draw from the bag. this would work well for the 'largest subgroup' part. It doesn't help the 'smallest group' requirement though.

Aha! Are you familiar with the "Cosmic Ashtray" thing from Andromeda (I hate that nickname)? You could have one of those, and use it as follows...

Put BOTH groups under it, and then use it to choose one cube randomly... then REMOVE all cubes of that group from consideration.

So in practice, you would shake up all the cubes under the thing, and 'draw' one out to see which type you DON'T get, then keep drawing them out until you get a cube that's NOT of the first type.

In your examples:
1. There is BBBBGGGYYR in the cup. Chances are about 6/10 that you will get a non-B cube the first time, in which case you would keep going until you get a B cube (or realistically, abort and just take a B cube). However, about 4 times in 10 a B cube will come out first, in which case you keep going until a non-B cube comes out. So ignoring further B cubes that come out, you have a 3/6 chance to get G and 1/6 chance of getting R.

2. There is BBBBBBGGY in the cup. Now there's a 6/9 chance that B will come out first, disqualifying it. When that happens there's a 2/3 chance of getting G and 1/3 of getting Y. About 3 times in 9 a B won't come out first, in which case you'd get B.

How's that???

- Seth

Top
Thu, 03/09/2006 - 20:43
#2
Kreitler
Offline
Joined: 12/31/1969
Re: Probabilistic Selection Mechanism

Yikes! That's an evil problem! Sedj's answer is pretty good, and I think it indicates that you're looking at multiple steps for your solution (either that, or a clever spatial layout).

Is there a fixed maximum number of cubes? Better yet, is there some sort of "unused" or "discard" pile? If so, you can use that to simplify the "heterogeneous vs homogeneous" part of the decision.

Suppose you have 15 black cubes total and 5 each of red, green, and yellow. These are "maximum" values -- you can never have more than this in the game ever.

Those currently in use are seperated into two bags: homogeneous (black) and hetergeneous (all others). The unused cubes of both types are mixed together in a "discard" bag.

For example, suppose there are 6 black cubes in use and 4 red, 3 green, and 2 yellow:

Bag #1 (in use, homogeneous): BBBBBB
Bag #2 (in use, heterogeneous): RRRR GGG YY
Bag #3 (unused, both): Bx9, Rx1, Gx2, Yx3

Step 1: draw a cube from bag #3 (unused/discard). If it's black, go to step 2a. If it's colored, goto step 2b.

Step 2a: draw 1 cube from bag #1 (in use, homogeneous).

Step 2b: draw 1 cube from bag #2 (in use, heterogeneous).

As you use the cubes and discard them, place them in bag #3.

This has some nice properties. You only ever need 2 draws to get your final cube. Also, if you draw a homogeneous cube in step 1, you draw from the homogeneous bag in step 2, etc -- so there's no "not" logic required by the player.

The big downside is that you must properly "seed" the discard bag at the start of the game. Depending on your design, this may not be possible.

Great problem, though.

Edit
I just realized I'm an idiot. If you draw homogeneous in step 1, there's no need for step 2.
Brilliant -- I wonder what the outcome will be if I draw from a bag filled only with black cubes... :P

Mark

Top
Fri, 03/10/2006 - 15:20
#3
MattMiller
Offline
Joined: 12/31/1969
Probabilistic Selection Mechanism

Quote:
I just realized I'm an idiot. If you draw homogeneous in step 1, there's no need for step 2.

Not really. If you don't do step 2, the number of cubes in the available-black-cube bag doesn't change, while the number in the discard bag decreases by one (until you put the black cube back into it). But that's probably not how it should work -- the number of cubes in the available bag should decrease, while the number in the discard bag should stay the same.

There is another potentially sticky problem. Depending on how the game works, some of the cubes might be in use somewhere (e.g. on the board or in a player's possession) at the time that a new one must be drawn. The absence of these guys from any bag might mess up the probabilities. In theory, for example, the game might reach a point when every black cube is either in use or in the discard bag, leaving the black-cube bag empty. Draw a black cube from the discard bag under these circumstances and you're in a pickle.

Still, if the rest of the game can be designed to accomodate it, I think this three-bag approach is the most elegant solution proposed so far.

Interesting puzzle.

-- Matt

Top
Fri, 03/10/2006 - 15:31
#4
sedjtroll
sedjtroll's picture
Offline
Joined: 07/21/2008
Probabilistic Selection Mechanism

As I've discussed with Nando in chat... I think the best solution is an opposed die roll.

Roll a Black die representing the black cubes, and a White die representing the non-black cubes. Add the number of B cubes to the B die roll, add the number of non-B cubes to the W die roll. Whichever side has a higher total "wins". The other side takes a Casulty (loses a cube).

So, if B wins, you have to figure out which color loses a cube... in this case roll 1d6 for each color, adding the number of cubes of that color present. Highest total loses a cube.

All this rolling is done at once, as each color represents 1 player, so it's not as clunky as it sounds.

- Seth

Top
Sun, 03/12/2006 - 14:37
#5
applejuicefool
Offline
Joined: 12/31/1969
Probabilistic Selection Mechanism

Shake up all the cubes and line them up randomly in a line.

Ex: You have B B B R R R R R Y Y G, so you shake them up and line them up: B R Y B G R B R R Y R

Starting at the left, note the set of the first cube. It's from the homogeneous set in this case.

The chosen cube is the first cube from the left in the other set. In this case, the first red cube.

If your cubes had been BBBB and RGY and had been arranged

B B R B G Y B, the chosen cube would have been the red cube.

Technically this has 4 steps,

1) Shake up the cubes
2) Arrange the cubes
3) Note the first cube
4) Find the first cube of the other set

but I think they flow pretty elegantly. The primary difficulty I see would be arranging the cubes blindly, but simply closing your eyes as you do it would solve this problem.

-AJF

Top
Sun, 03/12/2006 - 15:37
#6
sedjtroll
sedjtroll's picture
Offline
Joined: 07/21/2008
Probabilistic Selection Mechanism

applejuicefool wrote:
Shake up all the cubes and line them up randomly in a line...
Starting at the left, note the set of the first cube. It's from the homogeneous set in this case...
The chosen cube is the first cube from the left in the other set.

This is precisely what the 'cosmic ashtray' idea did.

- Seth

Top
Sun, 03/12/2006 - 19:53
#7
Gogolski
Gogolski's picture
Offline
Joined: 07/28/2008
Probabilistic Selection Mechanism

[OFF TOPIC sorry, I know...]
I like a game of cosmic ashtray... The strategy is in finding out what other players want have them change cards with you when you want what they are offering... Or have them not pick you if they've got nothing interesting to offer...
[/OFF TOPIC sorry, I know...]

[Half on topic now...]
I don't understand completely what you are looking for, but here's something that might or might not interest you:

1) Players select and add cubes:
Each round, every player secretly selects what cube he is going to add. (Black=B, Green=G, Yellow=Y, Red=R)
2) Reveal cubes and add to group:
Each player puts his cube in the right group (or easier: a colored pawn is moved on a track....)
3) Resolve which cube is choosen:
=> If B is the first or last on the track (=when black has most or least number of cubes), Black is choosen.
=> If black is not first or last on the track, you have to pick Y, G or R, you pick the one which is highest on the track.

Every turn/round, players have limited influence on which cube is going to be taken. Whit black being taken in both most- and least-cubes, it can give a bluffing twist. (I presume that black is some kind of special cube/option, or that it counts for any of the three colors)
[/Half on topic now...]

Yeah, whatever, I don't know how this system fits into the larger structure or mechanics of the game, so it's kind of difficult to give good advise...

Cheese!

Top
Mon, 03/13/2006 - 00:32
#8
applejuicefool
Offline
Joined: 12/31/1969
Probabilistic Selection Mechanism

Quote:
This is precisely what the 'cosmic ashtray' idea did.

True, and I realized that after I posted.

They're the same probabilistically but my method saves steps.

Alternatively, you could simply roll all the cubes. The one nearest you indicates the disqualified group, then you choose the closest member of the other group to you. Ties? Choose the one further left as a tiebreaker.

It's just one roll and knowing how to read it.

-AJF

Top
Mon, 03/13/2006 - 02:48
#9
sedjtroll
sedjtroll's picture
Offline
Joined: 07/21/2008
Probabilistic Selection Mechanism

applejuicefool wrote:
Quote:
This is precisely what the 'cosmic ashtray' idea did.

They're the same probabilistically but my method saves steps.
Well, not really, the "Shake up all the cubes and line them up randomly in a line" Is what the ashtray does. It shakes them up and craps them out in a line. :)

Top
Mon, 03/13/2006 - 23:00
#10
applejuicefool
Offline
Joined: 12/31/1969
Probabilistic Selection Mechanism

sedjtroll wrote:
applejuicefool wrote:
Quote:
This is precisely what the 'cosmic ashtray' idea did.

They're the same probabilistically but my method saves steps.
Well, not really, the "Shake up all the cubes and line them up randomly in a line" Is what the ashtray does. It shakes them up and craps them out in a line. :)

Ok, I didn't know what the ashtray thing was that you were talking about. I looked it up on BGG and it is a very similar mechanic to what I have in mind. Guess it's just a matter of whether you find rolling a handful of cubes or fooling with a finicky (looking) ashtray to be an easier mechanic.

-AJF

Top
Syndicate content


forum | by Dr. Radut