[HN Gopher] Go First Dice
___________________________________________________________________
Go First Dice
Author : pubby
Score : 99 points
Date : 2022-11-19 12:53 UTC (2 days ago)
(HTM) web link (www.ericharshbarger.org)
(TXT) w3m dump (www.ericharshbarger.org)
| munificent wrote:
| 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 wrote:
| > 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 wrote:
| 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 wrote:
| The limitation is getting the entropy. Where do you get that
| from in parallel?
| Supermancho wrote:
| > 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 wrote:
| 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 [...]
| jgrahamc wrote:
| I really enjoyed reading this but the way I've always done this
| is number the players and roll and single die.
| praptak wrote:
| 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.
| roywiggins wrote:
| Also available from the same shop as the linked set!
|
| https://www.mathartfun.com/dSpecial.html
| HelloNurse wrote:
| 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 wrote:
| 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.
| [deleted]
| sacrosanct wrote:
| Am I missing something here? Site just redirects to
| https://phpwebhosting.com/not-configured.html?target_host=tr...
| luckylion wrote:
| phpwebhosting.com seems to be what responds on https for that
| host.
| LVB wrote:
| Links to article for me.
| 1MachineElf wrote:
| 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?
| supernewton wrote:
| 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 wrote:
| 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.
| quickthrower2 wrote:
| 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.
| madcaptenor wrote:
| Doesn't this work for up to 100 players?
| quickthrower2 wrote:
| Yes, but at 51 to 75 it does get a bit tedious with the
| frequent algorithmic misses :-)
| [deleted]
| pessimizer wrote:
| 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
| CobrastanJorji wrote:
| 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.
| adenozine wrote:
| 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.
| saghm wrote:
| 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.
| PointyFluff wrote:
| 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.
| Wowfunhappy wrote:
| > 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.
| pessimizer wrote:
| 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.
| umanwizard wrote:
| It's not only about privacy, it's also about the ability for
| shady public wifi endpoints to inject ads or malware.
| nayuki wrote:
| Yup. I was at Atlanta airport and clicked on a bunch of
| links from the HN front page. All the pages that were sent
| over unencrypted HTTP got invasive ads injected into them.
| All the pages over HTTPS were fine.
| pessimizer wrote:
| It's good for everybody to use ssl, but people writing
| essays about their hobbies aren't responsible for shady
| public wifi endpoints.
|
| At least in FF there's a setting to force you to click
| through a full page warning to enable visiting a site
| without ssl. I use it, so I can be aware of my risks.
| umanwizard wrote:
| They're not "responsible" in the sense that I don't think
| it's not some kind of moral failing. I'm just pointing
| out that it's _not true_ that having TLS on this site
| wouldn't be useful to anyone. It would, and the webmaster
| enabling, despite not required, would be appreciated.
___________________________________________________________________
(page generated 2022-11-21 23:01 UTC)