Go First Dice

http://www.ericharshbarger.org/dice/go_first_dice.html

by pubby • 4 years ago

116 44 4 years ago

ericharshbarger.org

sacrosanct• 4 years ago

Am I missing something here? Site just redirects to https://phpwebhosting.com/not-configured.html?target_host=tr...

LVB• 4 years ago

Links to article for me.

1MachineElf• 4 years ago

The correct webpage seems to load fine for me on Brave 1.45.127 (Chromium 107.0.5304.110), Android 11. It is, however, unencrypted. Maybe something is intercepting your HTTP connection and redirecting you?

luckylion• 4 years ago

phpwebhosting.com seems to be what responds on https for that host.

praptak• 4 years ago

There's another dice puzzle which can also be named "go first" dice.

There exist three dice where A beats B, B beats C and C beats A, statistically speaking. So if you consistently throw A and B, A has a higher chance of rolling a greater number than B, etc.

Kind of rock-paper-scissors, so whoever "goes first" and picks the die will (statistically) lose against a smart opponent who chooses second.

HelloNurse• 4 years ago

They are called intransitive dice, and it's just about the opposite problem: as unfair as possible.

Wikipedia lists sets: https://en.wikipedia.org/wiki/Intransitive_dice

VikingCoder• 4 years ago

A friend and I had some manufactured, 20 years ago. We thought about selling them, but had no idea how much interest there would be. My friend did the math to come up with 6-sided ones that had the most uneven odds we could find, and each dice summed to the same number, and all the numbers 1-24 were each used once, and the numbers 1, 2, 3, and 4 were each on a different die, making them easy to identify. We colored them red, green, blue, and then maybe yellow?, if I remember correctly, to also try to make them easy to identify. If I remember correctly, 1 and 3 were fair, and 2 and 4 were fair, which we thought was also neat, because it would help you "prove" that the dice were fair, heh.

roywiggins• 4 years ago

Also available from the same shop as the linked set!

https://www.mathartfun.com/dSpecial.html

supernewton• 4 years ago

Some notes

- Permutation-fairness is likely too strong of a condition at anything other than serious competitive tournaments. When playing a game casually, usually the group first sits down in a circle and then chooses someone to go first, taking turns clockwise from there; then if the method for choosing the first player is first-player-fair then it is also place-fair.

- Although having to sometimes resolve ties is annoying, there is one major benefit of choosing turn order by rolls of the same dice: You are guaranteed that any non-fairness in the dice do not affect turn order determination.

adql• 4 years ago

I mean, if you already accepted that you want to carry with you N amount of dice to solve the ordering of N participants, you can just

* Roll N sided die to decide first (result telling you which player in order is the first)

* Roll n-1 side die to decide second

* Roll n-2 side die to decide 3rd

* ...etc

Same amount of dice rolls, but dices at least can be used for something other than single purpose.

quickthrower22• 4 years ago

For up to 50 players: Roll 2d10 for a number 0-99. Ignore top 100 mod p (reroll). Otherwise chosen player is r mod p. r is result, p is number of players.

PointyFluff• 4 years ago

I don't understand why sites like this are not HTTPS, yet.

I'm not giving you a security exception to read your blog.

Let's Encrypt is free.

pessimizer3• 4 years ago

I don't understand why they would be, in general. The content isn't interesting for snoops. I supposed it could screw you if you had an elaborate Murder She Wrote plan to kill someone that relied on a math trick, and visiting this particular page was enough for the jury to convict.

umanwizard2• 4 years ago

It’s not only about privacy, it’s also about the ability for shady public wifi endpoints to inject ads or malware.

Wowfunhappy• 4 years ago

Let's Encrypt is free.

Free of financial cost perhaps, but not free of effort. Let's Encrypt is a pain to set up and maintain on a self-hosted website, if you don't maintain websites professionally and don't have experience.

People lament the centralization of the web, but this https-or-the-highway mantra is contributing to exactly that! Because there is a way to truly get https "for free", and it's to throw up your site on Github Pages or Squarespace. Or just use Facebook.

pessimizer3• 4 years ago

Reiner Knizia uses distributions that are meant to have this quality (or get close enough to make people happy), most notably in Ra. Ra is an auction game where each player gets the name number of bidding tokens. Each token has a unique number on it, and you can only use a single token to bid, ensuring that there are never ties.

Ra is an example, but he uses it elsewhere. He's a math PhD who often writes in his books about how to break down these problems, and I wonder if he approached it the same way or reached the same conclusion.

https://boardgamegeek.com/boardgame/12/ra

munificent• 4 years ago

I love that they put so much work into trying to solve this when there is an equally trivially simple mechanical solution that works just as well and easily scales up to any number of users:

1. Put consecutive numbered tiles in an opaque bag.

2. Each person reaches in and blindly grabs a tile.

3. Play proceeds in the order of tiles.

You can think of dice rolling as simple random sampling with replacement. It's naturally good at generating combinations. Drawing from a bag is random sampling without replacement. It's naturally good at generating permutations.

Using a system that generates combinations to generate uniformly distributed random permutations is a super fun mathematical exercise and I'm sure this brought plenty of joy to the authors. But if you're just trying to design a physical mechanism to generate permutations, it'll be an easier starting point if you do sampling without replacement.

In fact, if you do want to generate permutations with dice, a simple (but laborious) way to do it is:

1. Choose an arbitrary ordering for the players.

2. For each player, roll a die. If the value rolled is the same as any value rolled by a previous player, re-roll. Continue to re-roll until a unique value is rolled.

3. Play proceeds in the order of values each player rolled.

You'll probably want to use d20 or some dice with a large number of faces relative to the number of players in order to minimize collisions and re-rolling.

I'm not 100% certain, but I believe this will generate an unbiased ordering where the order of players in step 1 has no effect on the resulting order determined in step 3.

nvader• 4 years ago

to generate permutations with dice, a simple (but laborious) way to do it is

Of course, the article rules this out, and requires a single roll.

I can vaguely imagine a system where what the authors describe will come in handy. Let's say you have a group of n distributed agents that collaborate over multiple rounds, and they need to establish a fair order of precedence for each consecutive round. Let's say each agent issues a message each round, and a "counter" decides the order that those messages resolve.

In that case, you can (pre-)assign each agent a pseudorandom go-first die. They can tag their messages with the results of their go-first die, and the counter can now resolve the messages in a fair order.

If you publish the PRNG seeds for all agents, so that every agent has it, they can all be counters. This means that every agent will resolve the messages in a deterministic order every round, and over all the rounds, the processing will be fair. Seems like a useful property.

cochne• 4 years ago

It might still be if interest from a computational viewpoint. For instance what if you need to compute a fair and random ordering for many many elements of a set? Then the dice method is more parallelizable than the bag method.

someweirdperson• 4 years ago

The limitation is getting the entropy. Where do you get that from in parallel?

Supermancho• 4 years ago

In fact, if you do want to generate permutations with dice, a simple (but laborious) way to do it...in a single roll

A single die of <#players>! sides. 4 players = 24 sided die, each side has an order permutation. Impractical, but doable. Excepting for all the other arbitrary requirements.

This is all an elaborate exercise borne of someone's idle time, so it's best not to put too much into it. They already did that work.

jml7c5• 4 years ago

It's worth noting that they primarily pursue this as a pleasurable puzzle, not for any practical payoff to the problem of player primacy:

We both understood that this was really a "solution looking for a problem" (there are plenty of perfectly acceptable ways to quickly determine who might go first in a game), but mathematically, wouldn't it be great if a set of dice could be created [...]

chris_st• 4 years ago

Did you plan that phenomenal "p" alliteration?

bo10242• 4 years ago

There might be a slick method to prove your final approach works to generate a uniformly random permutation. First, it's easy to prove if the number of players, n, equals the number of sides of the die, m. Because a random permutation is characterized as the first player equally likely to land in any spot, along with the permutation among the remaining n-1 players into the remaining n-1 slots being uniformly random. If n=m, then the first player's number that they pick determines where they end up in the permutation. And by induction, the remaining players pick a permutation uniformly from the remaining slots. The base case of n=m=1 is immediate.

Now the slick proof for the case m > n is to add m-n extra "dummy" players. They get to pick after the n players have picked. By the above argument, we get a uniformly random permutation of the m total players, including the dummy players. But when we remove any subset of players from a uniformly random permutation -- in this case, the dummy players -- we are left with a uniformly random permutation on the rest.

LordDragonfang• 4 years ago

Surprised no one has mentioned this, but the lexically-canonical version of this uses straws of different length.

https://en.wiktionary.org/wiki/draw_straws

https://en.wiktionary.org/wiki/draw_the_short_straw

lisper3• 4 years ago

If the value rolled is the same as any value rolled by a previous player, re-roll. Continue to re-roll until a unique value is rolled.

This gives an advantage to earlier players because it gives them "first dibs" on higher numbers. In the extreme, if the first player rolls the highest number, no one can subsequently beat them no matter what they roll.

gavinsyancey• 4 years ago

This is also true for lower numbers. It evens out so each player is equally likely to end up with each number.

bo10242• 4 years ago

If you consider n players and an n-sided die, you'll see this isn't true in that case. The first player has an exactly equal chance to be first, second, ..., last.

lowbloodsugar2• 4 years ago

We'll need a way to decide who goes first when deciding who goes first!

lowbloodsugar2• 4 years ago

Well, I think your second example has problems (already noted by others), but also: get out of here with your sensible and boring practicalities! This is a great article and a worthy quest!

CobrastanJorji• 4 years ago

Can I ask a dumb question? I understand the permutation argument for why using 5 six-sided dice can't possibly be fair, but looking at the serpentine example, I'm having trouble intuiting why. At a glance, removing any one of those dice looks pretty fair.

dubya• 4 years ago

If you look at just the first 5 dice and compute the probability that player one rolls lowest, of the 6^4 combinations of rolls the other players can make: 1 beats all 6^4; 16 beats 4^4, 17 beats 4^4, 32 beats 2^4, 33 beats 2^4, and 48 beats nothing. So player 1 is lowest 1840 out of 6^5, or ~23.7%.

A similar argument shows player 5 rolls lowest 1414 out of 6^5, or only 18.2% of the time.

I don't have a good intuitive explanation though.

saghm• 4 years ago

I used to play at low level but officially sanctioned Magic: The Gathering tournaments at a local shop, and there was no official policy for deciding who would play first, My understanding is that this is even the case at higher-level prize tournaments, and I think generally only high profile matches are live streamed (e.g. ones with well-known players or the final few rounds after most people are eliminated), and I read an article from a professional player a few years back about how sometimes people try to get away with things when the traditional "high roll" method is used (i.e. each player rolls their own die and the highest roll goes first, with repeats for ties), like bringing extremely large dice that essentially don't roll so much as just flop once, making it easy to toss in a way to force a given result. I'd also seen people use "evens and odds", where one person calls even or odd and the other rolls a die, with the choice of whether to go first going to the person who called if they were right and to the roller if not, but this still gives the person rolling some influence if they're unscrupulous. The article proposed that having one player call evens or odds but having _both_ players roll would eliminate any ability for cheating (assuming both players roll at once), since even being able to choose your result exactly would not be able to affect the chance of the sum being even or odd without knowing what your opponent would roll.

jakebasile• 4 years ago

When I played (extremely low level) MTG back in the day, we just flipped a coin. It seemed to work well enough!

jgrahamc• 4 years ago

I really enjoyed reading this but the way I’ve always done this is number the players and roll and single die.

adenozine• 4 years ago

My wife and I play a game with dice called 100.

You roll two dice, and you have to decide which permutation to keep, and it gets added to your score. So, if I roll [3,1] then I can add 13 or 31 to my score. The aim is to take turns and get closest to 100 without going over, and you can pass your turn if you think you're close enough.

It can also be played with more dice, ie 1000, 10000, but it gets easier the more dice there are.

devindotcom• 4 years ago

I too love the effort put into solving this problem. It's a totally different mindset from my own and clearly they get a lot of satisfaction from it. I myself would be satisfied with understanding that it is possible but non-trivial to do this, and immediately propose a trivial alternative like choosing from a deck of playing cards. Society needs both kinds of people! (and everyone in between)

Go First Dice

Related Stories