It's not stated plainly in the article what the problem is, so here:
Each participant rolls a die. For there to be no possibility of a tie, no die can share a face number with another die—every face across all dice must be unique. For it to be fair, the distribution of numbers across all faces must be such that no die has an advantage over another die—the odds of rolling the highest number must be exactly the same for each die. The problem is in finding the combination of faces across five dice that satisfies these constraints. One difficulty of this is that each added player changes the whole equation—the odds get recalculated and new faces must be chosen. The secondary goal is to minimize the number of faces on the die.
The key part is that they have to be fair when any subset of the dice is rolled together, not just when all five are rolled. Also if the dice are allowed to be different sizes then it's easier as well.
Came here also to point this out, because there is an easy to find solution that lacks only this property. I find this restriction somewhat unsatisfying though, because the easy solution does have the property that, for any smaller number of players, there is a subset that is fair for them (so you could manufacture these dice and resolve any number of players up to the number you have).
Requiring same size doesn't make it harder; you can take any solution and inflate the dice (take the lcm of all the sizes, duplicate the face numbers).
edit: oops i just double checked my construction and while they give equal go-first probabilities they don't give equal permutation probabilities...
This is very much missing from the article. It makes the math problem more interesting, but the practical solution is much easier.
There are possibly other applications in navigation, radio communication, or other domains that might make this a more interesting problem than just figuring out game ordering.
Thank you, I didn't really understand what they were talking about.
Personally, I feel there is an easier approach: Take a regular 12-sided die, assign numbers modulo N (N being the amount of players). Now you assign the first turn fairly for 2, 3, 4, 6 or 12 players. Add a d20 and that covers 5 or 10 players, too.
This made me think of a hypothetical game where the players roll dice to determine their order of turns. The rolling will continue until every player is assigned a turn. If some other player rolls multiple times in the middle then that player gets multiple turns. So for example with a 6 sided die and 2 players, faces 1, 3, 5 correspond to player 1 and 2, 4, 6 to player 2. They roll dice and the rolls come out as 1, 1, 5, 3, 5, 2. That means player 1 will get a turn 5 times per round while player 2 gets 1 turn. To make it fairer, player 2 would receive some sort of advantage corresponding to the lack of turns compared to player 1. The game would be designed in such a way that novices would prefer getting multiple turns in a round while experts would prefer to get a single turn for themselves and maximizing the total number of turns per round.
"Die" is a common singular form of "dice". The relative prevalence of "die" vs "dice" for this is regionally dependent. In general, English can't make up its mind with a lot of things involving words which end in a "sss" sound.
Die is singular, dice is plural. 1 die, 2 dice, 3 dice, …
It used to be something people were corrected on, but these days dice is accepted as the singular too and die is starting to be seen as a little antiquated.
But if you had those 3 dice but only 2 players you could not just have each player grab one of them and roll. If one of them happened to grab #1 they would only win 1/3 of the time instead of the desired 1/2.
With 2 players they would have to use just #2 and #3.
That's because the way I came up with those numbers is as follows.
1. Number the players 1, 2, and 3. We want #1 to win exactly 1/3 of the time. We could do that by given them a 3-sided die 1 1 H1, where all the numbers on the other dice are lower than H1 and higher than 1.
2. In the cases where #1 rolls 1, we want #2 to win half the time. Give them a 2-sided die 2 H2 where the remaining die has all numbers between 2 and H2.
3. Assuming the remain die is also 2-sided we will need a total of 6 different numbers. Using 1-6 our set of dice is (1 1 6), (2 5), (3 4).
4. Most people would probably prefer that they all have the same number of sides instead of 3, 2, 2. LCM of those is 6, so double the 3-sided and triple the two 2-sided: (1 1 1 1 6 6), (2 2 2 5 5 5), (3 3 3 4 4 4).
5. People might object to having the same number more than once on a die. We have 18 total sides so lets renumber from 1-18. Our 4 1s become 1-4, our 3 2s become 5-7, and so on, given the set of 3 6-sided dice at the start.
It seems pretty clear that this generalizes to more than 3 players, with the more players the more sides the dice will have. But all of those suffer from that annoyance of needed to exclude specific dice when you are trying to decide the starting order for less than the maximum number of players.
Do the dice in the article avoid that annoyance? I have no idea how I would go about making something like that.
Also note that my dice only determine who goes first. It would be really nice if they could be used to determine complete order. Mine fail for that because #1 is always either the highest or the lowest.
It would be possible to use #1s number on a losing roll to give their place: 1 2 means they go second and 3 4 they go third. You could even print something on the dice saying that, but I think most people would find it more elegant if it was a simple highest goes first, second highest second, and so on.
Do the dice in the article do that, or are they also just solving the who goes first problem?
A set of permutation fair dice work for any subset of dice and players. So a 4-dice perm-fair set allows any three dice to be used and is guaranteed to be perm-fair for 3 as well.
The “Go First” name is catchy for laypeople, but permutation fairness is the strongest and most interesting property.
There are sets we call “all subset place fair” which means any subset of the dice can be used and can fairly choose 1st, 2nd, and so forth, but this property is slightly weaker and doesn’t always make every ordering equally likely for every subset.
there seems to be no need to match number of dice with number of players - for example in 2 players the second player throwing second die (2,3) is really a noop as outcome is decided by the first player's die (1,4)
I suspect all the other rules plus that one would make it unsolvable at least in some cases like probably in the case of 2. It also brings to mind distributed consensus of cryptocoins (pardon for mentioning crypto :)
The big open question is whether a set of 5 (permutation fair) 30-sided dice exists.
I’ve been working on that on and off since 2012. I picked it up again about a month ago and have made dramatic speed improvements to my search, but exhausting the whole space I’m searching will still take my computer an estimated 70 years.
Well I’m first exhausting some promising regions of the search space which should complete in less than 2 weeks. After that I strongly suspect a solution doesn’t exist (for the column grouped space I’m searching).
If it were just a matter of a few thousand dollars of computer time (say, less than $5000) the money would already be spent and I’d have an answer.
We’ll see, I may build the tooling to distribute the search and enlist help from others interested.
It’s only been about 2 weeks since I was able to drop the runtime from “age of the universe” levels to just decades.
If you're being serious, i assume its because its primarily a novelty problem, and the economic investment of 4000 computers isn't worth it just for the bragging rights of solving the problem.
Roll dice as if you're rolling a fractional base six number of indefinite precision, stopping when one player wins.
A roll of 5, 2, and 4 is treated like 5.24
So if Alex and Bob both roll a '3', they just keep extending the precision until one is higher.
You may ask what this gives you over just re-rolling ties. Well, this preserves order. For example, if several people are rolling initiative, and there's a few rerolls for ties, you may end up with this initiative sequence:
John: 5
Betsy: 4
Alex: 3.16
Bob: 3.15
Phil: 2
If Alex and Bob had to reroll, the order can get confusing. It also gives you a magnitude: Betsy rolled 100% better than Phil, but Alex only came in 0.3% better than Bob.
Reminds me of how my wife, at the start of the pandemic, beat me TWELVE TIMES IN A ROW in rock-paper-scissors for going first playing Azul. That's like... anyways, she lost all of the Azul games, so I guess we're even.
I had a buddy like you. When he was drunk, I could look in his eyes and think, "I chose rock last, so now he'll choose paper to beat rock again." And I won the vast majority of the time (in a drinking game that involved dice).
Also, there's a Simpsons episode: Bart thinks "I'll pick rock. NOTHING beats rock!", and Lisa thinks "He ALWAYS picks rock...".
If all you have a coin there is a simple algorithm that's equivalent to sorting by random real numbers in [0, 1].
1. All players flips a coin.
2. Players that got heads go before players that got tails, forming (up to) two groups.
3. If a group has more than one player go back to #1 to determine the order within that group.
It's not a finite process though - it could go on forever if really unlucky. But this is unavoidable, since the number of permutations on n players with n > 2 has factors not divisible by 2 there is no finite series of n coin tosses that could without any bias create a permutation, as the number of outcomes is 2^n.
I think it's more about guaranteeing the whole sequence, rather than who goes first?
At least for two players, if you use a two sided die (a coin), have player one win ties on ones, player two win ties of twos - and otherwise highest wins - then that is trivially done?
I would have to do a little more math to see if it generalizes by induction... I'm not sure you would get a guaranteed sequence - but I think at least guaranteed fair winner works by just increasing the die (7, 9 and 11 would be tricky because if physics again... I suppose. Unless you just ignore highest tie for missing player (reroll on extremely rare 9 9s on a d10 for nine players)?
Ed: I suppose we break smaller ties, by letting closest and highest win (for ten players, 4, 6 and 7 roll 5 - 6 is closest and over/highest of the close players to 5, then come 7?)
Ed2: nevermind we end up biased towards "high" players that often win on "high" ties, like 5 or 6.
> I think it's more about guaranteeing the whole sequence, rather than who goes first?
What do you mean? The question is who goes first.
As a matter of practice, what happens in a board game is that everyone takes a position around the board before choosing who goes first. If turns proceed in a fixed sequence, that position will determine the sequence. If the order of turns is specified by the game (for example, many feature a turn order track), then that order will be used. You never need to decide on a sequence longer than one person.
But even if that wasn't the case, the article couldn't be more explicit:
> Eric Harshbarger was asked by a board game designer if he could come up with dice that would determine who goes first — without the possibility of a tie.
> The idea was simple: settle the first turn quickly and get on with the game.
This from the article appears somewhat questionable:
>> “It was a question that did not have an obvious answer and that's something that a mathematician will often jump at.”
The problem they're bragging about solving is using dice to quickly and unambiguously select one of five options with equal probability.
The obvious answer should be that you roll a single 10- or 20-sided die, divide by 2 or 4, round up, and there you have it.
From a site selling the dice: "With these dice all players will have an equal chance of ranking first, second, third and fourth. And only one roll is required."
Wikipedia distinguishes between "go first fair" and "permutation fair". I believe Harshbarger wanted to find permutation fair dice.
Pretty sure he means this:
- assume heads beats tails
- if both players get opposite results (HT, TH) then the winner is obvious
- if both players get heads, player A is the winner
- if both players get tails, player B is the winner.
Except that as a sibling comment mentions; that generalizes to any size of group - for six players you could roll one d6, and have "that" player go first.
But apparently the constraints are: every player rolls one die once.
> But apparently the constraints are: every player rolls one die once.
That doesn't eliminate the natural scheme, it just adds some useless die rolls. You can have each of two players flip a coin and choose player A when player A flips heads or player B when player A flips tails.
Useless depends on context here; I believe the idea is that each player gets a feeling of agency (they go in the order dictated by "their" luck, not leaving the decision to someone elses roll).
The most pragmatic would probably be to shuffle N cards from ace(one) through N - and let everyone draw).
So it was more of a physical problem rather than a mathematical one [1]:
> Harshbarger says he and his colleagues always knew the dice were mathematically possible.
> The mystery was whether that mathematical solution could be translated into the physical geometry of a die — something that could actually be manufactured and rolled.
> “I knew there was a solution with something crazy like 1,440 sides for each die,” he said. “That's not makeable.”
I think it is not a matter of whether it is more of a "physical problem" or a "mathematical one". They knew a solution existed but it was physically unfeasible, which prompted them to mathematically optimize the solution by using fewer sides. They found a solution using only 120 sides, and a lower bound of 30 is known but brute-forcing it is still computationally expensive.
Can somebody explain why not just make a die with 5! sides, and roll it once to decide the order? With each side having a unique order printed e.g. 12345 -> 12354 -> ...
Especially, that 120-sided dice are already invented and commercially available.
Because the question isn’t can you make a rice with 5! Sides but can you make it so 5 players can roll simultaneously individual dice with a minimal number of sides per dice and never tie and always be fair.
Sure you can fly a helicopter to the top of Everest, but it’s not the same as climbing Everest even if the outcome is the same.
From the article: "During a dinner conversation at a gaming convention in 2012, Eric Harshbarger was asked by a board game designer if he could come up with dice that would determine who goes first — without the possibility of a tie. The idea was simple: settle the first turn quickly and get on with the game."
The original challenge was to design dice (I assume a single die would satisfy the requirement since the number of dice wasn't the point) that would quickly determine which of five players would go first. Nothing about the challenge required that there be five dice. A five-sided die would certainly be the simplest way, and would be marginally faster than having five players each roll a separate die and then compare the numbers.
The provenance doesn’t matter because they settled on a difficult mathematical problem to solve because it was difficult to solve and would require clever solutions that answered more fundamental mathematical questions than the banal problem of choosing who goes first in a game. That was just the framing that motivated the larger math question, in which the number of dice does matter, because it’s a more interesting question.
I wanted to say "You actually can't fly a helicopter to the top of Everest, the air is too thin", but apparently it's been done exactly twice. Stripped down specially chopper and ideal weather conditions.
> Can somebody explain why not just make a die with 5! sides, and roll it once to decide the order?
Hey, that’s a good idea—now we just need to decide who rolls the die. …Well, if we had a set of die that each player could roll one of, and the highest number rolled gets to roll the 120-sided die. Of course, we’d have to ensure that there’s no chance of a tie.
Or, like my gaming group does. Just roll again between whoever ties. And in the extremely rare event that you tie again, roll again. And if youve managed to get to the heat death of the universe and have tied three times, roll a fourth time.
And for the pedants, you arent rolling every microsecond for millennia to make it plausibly likely that you have that many ties. You are rolling a handful of times before a game.
Its an interesting math problem to solve, but its way more effort to solve than the real world solutions.
This is an interesting problem (for mathematicians and a few more of us) and I'm sure Matt Parker will cover this in a video soon and I'll love his explanation.
But for a mechanism to ship in a physical game? Big dice are difficult and expensive. Printing a deck of card that has the number 1 (or 0) to N on it will always be cheaper and has solved the problem for at least N up to 52.
> The search was enormous — there were more possible designs than atoms in the universe
PopSci journalists must get so excited every time they get to write about a math result with a combinatorial flavor, letting them use their favorite "wow factor" phrase.
I might be missing something, but a single 6 sided die can have all permutations for 3 players; a 24 sided die for 4 players; a 120 sided die has all permutations necessary for 5 players. Each one of these would even firmly support fewer players.
By the time you got to 120 sides you probably couldn’t label the sides with the order and would need a lookup table or something. That’s a disadvantage, I suppose.
You can take the product of the permutations as the result.
The only problem with that is that you need to pick an order to roll the dice in order to pick the order to rank the players.
But happily, we have a set of dice that pick the order to roll the dice. Now we only need to pick an order to roll the dice to pick the order to roll the dice to pick the order to play.
For those as confused as me, I'm pretty sure this isn't "new". Numberphile talked about doing even better than this several years ago: https://www.youtube.com/watch?v=5q32heFz1bs
According to the wikipedia article linked at https://news.ycombinator.com/item?id=49559416 this discovery is from around the same time as that video came out. This submission should be tagged (2023).
ETA: Oh I just looked at the linked article again and it was just published. Weird.
My naive first idea was that (for two people) one set would have even numbers and the other odds. But then the even number person is more likely to win. So it's something around which numbers are on which dice.
I was wondering that too - it seems you start with a linked list of sorts, and then evenly distribute the links to the dice. But I’ve obviously not thought it out.
I think I'm having trouble understanding why this is so complicated/requires so many sides.
If I imagine a 3-sided die, for simplicity, you should be able to have this result if the sets are [1,5,9],[2,6,7],[3,4,8]. And so on for larger numbers of players. Why doesn't this work?
You might want to check that your proposed solution works at all before suggesting the problem is trivial. What's the probability that the first die goes first with your numbers?
You also can't generally "and so on" constrained combinatorial arrangements like this.
I certainly would have, had I suggested the problem trivial! I'll keep that in mind for if I suggest things are trivial rather than suggesting I lack understanding.
> You also can't generally "and so on" constrained combinatorial arrangements like this.
I know you can't generally but in the specific case I proposed you can (3 sets of 3, 4 sets of 4, 5 sets of 5, each dice taking one ordinal of each set).
You might want to check that your proposed generalization criticism applies to the generalization at all before suggesting the arrangement doesn't work :)
You're saying you knew the thing you wrote for n=3 specifically was wrong and just wanted someone else to confirm? I don't know man, I'm not really buying it. I think you did the classic dismissive nerd thing[1] and hedged it like this for plausible deniability.
I don't get the gotcha you're trying to do. Yes, the simple pattern you posted can be extended, but it has very little to do with the problem. If you had suggested [1,2,3] [4,5,6] [7,8,9] worked I would still have made my comment; I think the fact that you found a pattern that could be extended easily should have itself been a counter-indicator. Compare with something like the Fano plane[2].
I would want you to take away from this that posting the thing you came up with in "20 seconds" isn't as neutral a contribution to conversation as you thought. Things are often complicated and worth engaging with. It would have been cool if you kept going far enough to see there's a nice argument that it's actually impossible to solve it with n-sided dice for n people if n>2.
Do you think the dismissive nerd thing is, like, a goal people set out to do?
You seem to have spent your time around sufficiently many unpleasant people that you see their behavior everywhere, even when explicitly corrected. I'm sorry for that.
Could I have independently gone through and rigorously deconstructed my solution? Sure, and we would all be poorer for it. See, there's another, valuable reason people say what I said beside the "classic dismissive nerd thing".
For every person with a question, there's probably 5 more with the same question who didn't ask. By writing down questions like I did, and inviting their answer to be written down, that provides education not only to me but to anyone who reads it after having similar thought.
I consider that sufficiently valuable to create, that I am willing to accept a handful of people criticizing me for "doing the dismissive nerd thing".
So yes. I knew the thing I wrote was wrong, I didn't know why/how, and I wrote it down as is rather than just going off on a personal side quest to come up with some generalized proof. And I would do it again.
"I'm having trouble understanding why this is so complicated" could be interpreted in a non-dismissive way but it defaults to dismissive. And when it comes with a supposed solution attached, and that solution is really simple, that reinforces it sounding dismissive.
I by no means was suggesting that the trivial solution I, a non-mathematician, thought up in 20 seconds was somehow out of reach to a math professor who spent years on the problem. I knew I was wrong.
I didn't see why until I actually went through the solutions by hand.
Only the people who can't make eye contact with others interpreted your comment as hostile. Unfortunately, that describes a high number of people on this site.
I didn't read it as dismissive. I think the "Why doesn't this work?" at the end is key, implying they know they're probably wrong, but don't know why. It's pretty common to form and present hypothesis like this, hoping that anyone who knows the actual theory can easily provide a counterexample showing why it's wrong. It's not at all intended to be dismissive.
Why does that default to dismissive for you? It absolutely did not come off that way for me and I’m wondering if it’s because of experience or culture or something else.
You could, but that would just dodge the problem they want to solve.
They're not actually interested in determining who goes first or anything practical like that. The article even implicitly admits as much. After all, you could just use normal dice and roll again on ties or, like you suggested, come up with an extra protocol built on top of them.
"We want dice that determine who goes first without a tie" is just a catchier way of saying "We want N dice that all have the same probability of showing the higher number but zero probability of a tie," which is an interesting mathematical problem.
If anyone wants a practical way to decide who goes first, in a single roll, with no possibility of a tie, this works:
For 2 players, the dealer rolls a standard 6-sided die, and the result determines who goes first:
1, 2, 3 => Player A
4, 5, 6 => Player B
For 3 players, the dealer rolls a standard 6-side die:
1, 2 => Player A
3, 4 => Player B
5, 6 => Player C
For 4 players, the dealer rolls a standard d20 die:
1, 2, 3, 4, 5 => Player A
6, 7, 8, 9, 10 => Player B
11, 12, 13, 14, 15 => Player C
16, 17, 18, 19, 20 => Player D
For 5 players, the dealer rolls a standard d20 die:
1, 2, 3, 4 => Player A
5, 6, 7, 8 => Player B
9, 10, 11, 12 => Player C
13, 14, 15, 16 => Player D
17, 18, 19, 20 => Player E
If the dealer has a tetrahedral (d4) die, they can use that instead for the 4-player problem.
This is really all you need to decide who goes first. It's perfectly fair. It uses standard dice that most people already have in their game drawer.
The article is actually about a different, much harder problem about the full playing order. You don't actually need that extra complexity to decide who goes first.
Why does everyone need a dice? Just number each player from 1 to 5 and use a 5 sided die (or 234*5 = 120 faces if you want to cover 2 to 5 players)?
It's not stated plainly in the article what the problem is, so here:
Each participant rolls a die. For there to be no possibility of a tie, no die can share a face number with another die—every face across all dice must be unique. For it to be fair, the distribution of numbers across all faces must be such that no die has an advantage over another die—the odds of rolling the highest number must be exactly the same for each die. The problem is in finding the combination of faces across five dice that satisfies these constraints. One difficulty of this is that each added player changes the whole equation—the odds get recalculated and new faces must be chosen. The secondary goal is to minimize the number of faces on the die.
Article was really poor in stating this clearlly, to the extent it made no sense to me. Thank you.
Really a trash article in general, revealing none of the solution, and not even exploring the problem in any way.
The solution is left as an exercise for the reader. Giving away more would spoil the fun for the curious!
The key part is that they have to be fair when any subset of the dice is rolled together, not just when all five are rolled. Also if the dice are allowed to be different sizes then it's easier as well.
Came here also to point this out, because there is an easy to find solution that lacks only this property. I find this restriction somewhat unsatisfying though, because the easy solution does have the property that, for any smaller number of players, there is a subset that is fair for them (so you could manufacture these dice and resolve any number of players up to the number you have).
Requiring same size doesn't make it harder; you can take any solution and inflate the dice (take the lcm of all the sizes, duplicate the face numbers).
edit: oops i just double checked my construction and while they give equal go-first probabilities they don't give equal permutation probabilities...
This is very much missing from the article. It makes the math problem more interesting, but the practical solution is much easier.
There are possibly other applications in navigation, radio communication, or other domains that might make this a more interesting problem than just figuring out game ordering.
Thank you, I didn't really understand what they were talking about.
Personally, I feel there is an easier approach: Take a regular 12-sided die, assign numbers modulo N (N being the amount of players). Now you assign the first turn fairly for 2, 3, 4, 6 or 12 players. Add a d20 and that covers 5 or 10 players, too.
That would preclude everyone from having a throw. Which is likely more fair but doesn't feel fair.
This made me think of a hypothetical game where the players roll dice to determine their order of turns. The rolling will continue until every player is assigned a turn. If some other player rolls multiple times in the middle then that player gets multiple turns. So for example with a 6 sided die and 2 players, faces 1, 3, 5 correspond to player 1 and 2, 4, 6 to player 2. They roll dice and the rolls come out as 1, 1, 5, 3, 5, 2. That means player 1 will get a turn 5 times per round while player 2 gets 1 turn. To make it fairer, player 2 would receive some sort of advantage corresponding to the lack of turns compared to player 1. The game would be designed in such a way that novices would prefer getting multiple turns in a round while experts would prefer to get a single turn for themselves and maximizing the total number of turns per round.
You mean you roll a single die and use the value to index an array of players?
That’s the pragmatic solution. The article is about an interesting mathematical puzzle, not actually solving a real problem.
Also, an n-sided die is fair for 2 to n players if you discard rolls above the number of players.
The article states:
So, not entirely just a math puzzle. But probably dice only math nerds will buy (:I agree the math problem does not map well to a real problem players are having.
> But probably dice only math nerds will buy (:
You don't have to buy them to use them. For example I own a baggie of D(4-20) dice but I don't and have never played tabletop RPGs.
This set may end up too expensive for my "i know i'll never use it" budget, but other than that I'd get one.
But how do you choose who gets to throw that die? /s
Is there are a reason why you mention die, not dice, so many times in your post? Do you actually mean die? Honest question since it's repeated.
"Die" is a common singular form of "dice". The relative prevalence of "die" vs "dice" for this is regionally dependent. In general, English can't make up its mind with a lot of things involving words which end in a "sss" sound.
Die is singular, dice is plural. 1 die, 2 dice, 3 dice, …
It used to be something people were corrected on, but these days dice is accepted as the singular too and die is starting to be seen as a little antiquated.
Thanks came looking for this explanation
This Wikipedia article goes over things:
* https://en.wikipedia.org/wiki/Go_First_Dice
As well as the pages of the project:
* http://gofirstdice.ericharshbarger.org/
A physical example of dice (USD 35):
* https://www.mathartfun.com/thedicelab.com/GFD5.html
* https://www.youtube.com/shorts/yMtTqiAhol8
* UK store: https://mathsgear.co.uk/collections/dice/products/go-first-d...
In addition to the above 5-player go first, they also have 4- and 3-player go first:
* https://www.mathartfun.com/dSpecial.html
Interesting. For 3 players this set of 3 6-sided dice would work:
But if you had those 3 dice but only 2 players you could not just have each player grab one of them and roll. If one of them happened to grab #1 they would only win 1/3 of the time instead of the desired 1/2.With 2 players they would have to use just #2 and #3.
That's because the way I came up with those numbers is as follows.
1. Number the players 1, 2, and 3. We want #1 to win exactly 1/3 of the time. We could do that by given them a 3-sided die 1 1 H1, where all the numbers on the other dice are lower than H1 and higher than 1.
2. In the cases where #1 rolls 1, we want #2 to win half the time. Give them a 2-sided die 2 H2 where the remaining die has all numbers between 2 and H2.
3. Assuming the remain die is also 2-sided we will need a total of 6 different numbers. Using 1-6 our set of dice is (1 1 6), (2 5), (3 4).
4. Most people would probably prefer that they all have the same number of sides instead of 3, 2, 2. LCM of those is 6, so double the 3-sided and triple the two 2-sided: (1 1 1 1 6 6), (2 2 2 5 5 5), (3 3 3 4 4 4).
5. People might object to having the same number more than once on a die. We have 18 total sides so lets renumber from 1-18. Our 4 1s become 1-4, our 3 2s become 5-7, and so on, given the set of 3 6-sided dice at the start.
It seems pretty clear that this generalizes to more than 3 players, with the more players the more sides the dice will have. But all of those suffer from that annoyance of needed to exclude specific dice when you are trying to decide the starting order for less than the maximum number of players.
Do the dice in the article avoid that annoyance? I have no idea how I would go about making something like that.
Also note that my dice only determine who goes first. It would be really nice if they could be used to determine complete order. Mine fail for that because #1 is always either the highest or the lowest.
It would be possible to use #1s number on a losing roll to give their place: 1 2 means they go second and 3 4 they go third. You could even print something on the dice saying that, but I think most people would find it more elegant if it was a simple highest goes first, second highest second, and so on.
Do the dice in the article do that, or are they also just solving the who goes first problem?
A set of permutation fair dice work for any subset of dice and players. So a 4-dice perm-fair set allows any three dice to be used and is guaranteed to be perm-fair for 3 as well.
The “Go First” name is catchy for laypeople, but permutation fairness is the strongest and most interesting property.
There are sets we call “all subset place fair” which means any subset of the dice can be used and can fairly choose 1st, 2nd, and so forth, but this property is slightly weaker and doesn’t always make every ordering equally likely for every subset.
there seems to be no need to match number of dice with number of players - for example in 2 players the second player throwing second die (2,3) is really a noop as outcome is decided by the first player's die (1,4)
Yes, that bothered me. I think I’d want to add a rule that says the final order isn’t completely decided until all players have rolled.
I suspect all the other rules plus that one would make it unsolvable at least in some cases like probably in the case of 2. It also brings to mind distributed consensus of cryptocoins (pardon for mentioning crypto :)
The big open question is whether a set of 5 (permutation fair) 30-sided dice exists.
I’ve been working on that on and off since 2012. I picked it up again about a month ago and have made dramatic speed improvements to my search, but exhausting the whole space I’m searching will still take my computer an estimated 70 years.
Only 70 years? If that's the case, why isn't it solved yet? Just rent 4,000 computers and have it done in less than a week.
Well I’m first exhausting some promising regions of the search space which should complete in less than 2 weeks. After that I strongly suspect a solution doesn’t exist (for the column grouped space I’m searching).
If it were just a matter of a few thousand dollars of computer time (say, less than $5000) the money would already be spent and I’d have an answer.
We’ll see, I may build the tooling to distribute the search and enlist help from others interested.
It’s only been about 2 weeks since I was able to drop the runtime from “age of the universe” levels to just decades.
Posting it here will almost certainly lead to a "May the best clanker win" contest, you realize!
If someone wants to beat me to either a solution, or proving no solutions exists, then by all means :-)
I think it's an extraordinarily hard problem computationally, even with exceptional theoretical backing.
Where people may be able to beat me is if no solution exists-- there may be some highly nontrivial, but findable unsatisfiability argument.
If you're being serious, i assume its because its primarily a novelty problem, and the economic investment of 4000 computers isn't worth it just for the bragging rights of solving the problem.
Roll dice as if you're rolling a fractional base six number of indefinite precision, stopping when one player wins.
A roll of 5, 2, and 4 is treated like 5.24
So if Alex and Bob both roll a '3', they just keep extending the precision until one is higher.
You may ask what this gives you over just re-rolling ties. Well, this preserves order. For example, if several people are rolling initiative, and there's a few rerolls for ties, you may end up with this initiative sequence:
If Alex and Bob had to reroll, the order can get confusing. It also gives you a magnitude: Betsy rolled 100% better than Phil, but Alex only came in 0.3% better than Bob.The point of this thing is you never need to reroll ties
But in this method you're technically not rerolling the tie; you're keeping it and extending the precision.
Sure, it's pointless, and some may feel that's a drawback...
Reminds me of how my wife, at the start of the pandemic, beat me TWELVE TIMES IN A ROW in rock-paper-scissors for going first playing Azul. That's like... anyways, she lost all of the Azul games, so I guess we're even.
I had a buddy like you. When he was drunk, I could look in his eyes and think, "I chose rock last, so now he'll choose paper to beat rock again." And I won the vast majority of the time (in a drinking game that involved dice).
Also, there's a Simpsons episode: Bart thinks "I'll pick rock. NOTHING beats rock!", and Lisa thinks "He ALWAYS picks rock...".
I feel honored being compared to both a drunk buddy and Bart Simpson in a single comment!
If you want to buy these, they are commercially available https://mathartfun.com/dSpecial.html
(no affiliation)
I think there have been discussions about some of these sets here as well.
What a cool company. They’ve got the coolest nerdiest things.
I’m loving the non-transitive dice. My son’s birthday is in (checks calendar) ten months, but he’s getting these dice now anyway. So cool.
If all you have a coin there is a simple algorithm that's equivalent to sorting by random real numbers in [0, 1].
It's not a finite process though - it could go on forever if really unlucky. But this is unavoidable, since the number of permutations on n players with n > 2 has factors not divisible by 2 there is no finite series of n coin tosses that could without any bias create a permutation, as the number of outcomes is 2^n.Normal url: https://www.cbc.ca/radio/asithappens/dice-mystery-board-game...
I think it's more about guaranteeing the whole sequence, rather than who goes first?
At least for two players, if you use a two sided die (a coin), have player one win ties on ones, player two win ties of twos - and otherwise highest wins - then that is trivially done?
I would have to do a little more math to see if it generalizes by induction... I'm not sure you would get a guaranteed sequence - but I think at least guaranteed fair winner works by just increasing the die (7, 9 and 11 would be tricky because if physics again... I suppose. Unless you just ignore highest tie for missing player (reroll on extremely rare 9 9s on a d10 for nine players)?
Ed: I suppose we break smaller ties, by letting closest and highest win (for ten players, 4, 6 and 7 roll 5 - 6 is closest and over/highest of the close players to 5, then come 7?)
Ed2: nevermind we end up biased towards "high" players that often win on "high" ties, like 5 or 6.
> I think it's more about guaranteeing the whole sequence, rather than who goes first?
What do you mean? The question is who goes first.
As a matter of practice, what happens in a board game is that everyone takes a position around the board before choosing who goes first. If turns proceed in a fixed sequence, that position will determine the sequence. If the order of turns is specified by the game (for example, many feature a turn order track), then that order will be used. You never need to decide on a sequence longer than one person.
But even if that wasn't the case, the article couldn't be more explicit:
> Eric Harshbarger was asked by a board game designer if he could come up with dice that would determine who goes first — without the possibility of a tie.
> The idea was simple: settle the first turn quickly and get on with the game.
This from the article appears somewhat questionable:
>> “It was a question that did not have an obvious answer and that's something that a mathematician will often jump at.”
The problem they're bragging about solving is using dice to quickly and unambiguously select one of five options with equal probability.
The obvious answer should be that you roll a single 10- or 20-sided die, divide by 2 or 4, round up, and there you have it.
From a site selling the dice: "With these dice all players will have an equal chance of ranking first, second, third and fourth. And only one roll is required."
Wikipedia distinguishes between "go first fair" and "permutation fair". I believe Harshbarger wanted to find permutation fair dice.
Pretty sure he means this: - assume heads beats tails - if both players get opposite results (HT, TH) then the winner is obvious - if both players get heads, player A is the winner - if both players get tails, player B is the winner.
If you're going to specify that the number of players is 2, there is no advantage over the much simpler system of:
Flip one coin. If heads, player A is the winner. If tails, player B is the winner.
Except that as a sibling comment mentions; that generalizes to any size of group - for six players you could roll one d6, and have "that" player go first.
But apparently the constraints are: every player rolls one die once.
> But apparently the constraints are: every player rolls one die once.
That doesn't eliminate the natural scheme, it just adds some useless die rolls. You can have each of two players flip a coin and choose player A when player A flips heads or player B when player A flips tails.
Useless depends on context here; I believe the idea is that each player gets a feeling of agency (they go in the order dictated by "their" luck, not leaving the decision to someone elses roll).
The most pragmatic would probably be to shuffle N cards from ace(one) through N - and let everyone draw).
But that doesn't involve dice.
So it was more of a physical problem rather than a mathematical one [1]:
> Harshbarger says he and his colleagues always knew the dice were mathematically possible.
> The mystery was whether that mathematical solution could be translated into the physical geometry of a die — something that could actually be manufactured and rolled.
> “I knew there was a solution with something crazy like 1,440 sides for each die,” he said. “That's not makeable.”
[1] https://www.cbc.ca/radio/asithappens/dice-mystery-board-game...
I think it is not a matter of whether it is more of a "physical problem" or a "mathematical one". They knew a solution existed but it was physically unfeasible, which prompted them to mathematically optimize the solution by using fewer sides. They found a solution using only 120 sides, and a lower bound of 30 is known but brute-forcing it is still computationally expensive.
Reword it as “the smallest possible set where X is still true” and you combine both.
Can somebody explain why not just make a die with 5! sides, and roll it once to decide the order? With each side having a unique order printed e.g. 12345 -> 12354 -> ...
Especially, that 120-sided dice are already invented and commercially available.
Because the question isn’t can you make a rice with 5! Sides but can you make it so 5 players can roll simultaneously individual dice with a minimal number of sides per dice and never tie and always be fair.
Sure you can fly a helicopter to the top of Everest, but it’s not the same as climbing Everest even if the outcome is the same.
From the article: "During a dinner conversation at a gaming convention in 2012, Eric Harshbarger was asked by a board game designer if he could come up with dice that would determine who goes first — without the possibility of a tie. The idea was simple: settle the first turn quickly and get on with the game."
The original challenge was to design dice (I assume a single die would satisfy the requirement since the number of dice wasn't the point) that would quickly determine which of five players would go first. Nothing about the challenge required that there be five dice. A five-sided die would certainly be the simplest way, and would be marginally faster than having five players each roll a separate die and then compare the numbers.
The provenance doesn’t matter because they settled on a difficult mathematical problem to solve because it was difficult to solve and would require clever solutions that answered more fundamental mathematical questions than the banal problem of choosing who goes first in a game. That was just the framing that motivated the larger math question, in which the number of dice does matter, because it’s a more interesting question.
How do you decide who gets to roll the single die?
Gee, you need a way to rank the players to decide.
I wanted to say "You actually can't fly a helicopter to the top of Everest, the air is too thin", but apparently it's been done exactly twice. Stripped down specially chopper and ideal weather conditions.
I get the impression one of the unwritten requirements is that each player gets to roll their own die
120 sided dice roll for a long time and don't have much room for printing
And how do you decide who is going to throw that one die?
Literally doesn't matter, player closest to dice at the moment you open the box.
That's why you need those 5 dice to decide it.
> Can somebody explain why not just make a die with 5! sides, and roll it once to decide the order?
Hey, that’s a good idea—now we just need to decide who rolls the die. …Well, if we had a set of die that each player could roll one of, and the highest number rolled gets to roll the 120-sided die. Of course, we’d have to ensure that there’s no chance of a tie.
Hmm… this idea has legs…
Or, like my gaming group does. Just roll again between whoever ties. And in the extremely rare event that you tie again, roll again. And if youve managed to get to the heat death of the universe and have tied three times, roll a fourth time.
And for the pedants, you arent rolling every microsecond for millennia to make it plausibly likely that you have that many ties. You are rolling a handful of times before a game.
Its an interesting math problem to solve, but its way more effort to solve than the real world solutions.
This is an interesting problem (for mathematicians and a few more of us) and I'm sure Matt Parker will cover this in a video soon and I'll love his explanation.
But for a mechanism to ship in a physical game? Big dice are difficult and expensive. Printing a deck of card that has the number 1 (or 0) to N on it will always be cheaper and has solved the problem for at least N up to 52.
> The search was enormous — there were more possible designs than atoms in the universe
PopSci journalists must get so excited every time they get to write about a math result with a combinatorial flavor, letting them use their favorite "wow factor" phrase.
I might be missing something, but a single 6 sided die can have all permutations for 3 players; a 24 sided die for 4 players; a 120 sided die has all permutations necessary for 5 players. Each one of these would even firmly support fewer players.
By the time you got to 120 sides you probably couldn’t label the sides with the order and would need a lookup table or something. That’s a disadvantage, I suppose.
I think the (implied) constraint is that each person gets to roll one die, and the highest die roll wins.
You can take the product of the permutations as the result.
The only problem with that is that you need to pick an order to roll the dice in order to pick the order to rank the players.
But happily, we have a set of dice that pick the order to roll the dice. Now we only need to pick an order to roll the dice to pick the order to roll the dice to pick the order to play.
But ...
What about the site? Mostly text, with [load images] buttons. I like that!
CBC is the BBC of Canada. This is the light version of the site for those that have limited data I suppose. It is nice.
For those as confused as me, I'm pretty sure this isn't "new". Numberphile talked about doing even better than this several years ago: https://www.youtube.com/watch?v=5q32heFz1bs
According to the wikipedia article linked at https://news.ycombinator.com/item?id=49559416 this discovery is from around the same time as that video came out. This submission should be tagged (2023).
ETA: Oh I just looked at the linked article again and it was just published. Weird.
It didn’t mention the underlying theory? Is it just that these large dimensions reduce the collision probability?
My naive first idea was that (for two people) one set would have even numbers and the other odds. But then the even number person is more likely to win. So it's something around which numbers are on which dice.
If you had two dice, one with odds 1->11, and the other 2->12, and you made 1 beat 12, they would have even chances of winning then, right?
I was wondering that too - it seems you start with a linked list of sorts, and then evenly distribute the links to the dice. But I’ve obviously not thought it out.
I think I'm having trouble understanding why this is so complicated/requires so many sides.
If I imagine a 3-sided die, for simplicity, you should be able to have this result if the sets are [1,5,9],[2,6,7],[3,4,8]. And so on for larger numbers of players. Why doesn't this work?
This is not exactly perfectly fair - appears that the first player wins 11/27 times and the other two win 8/27 each.
Ah. Now that I go through it it makes sense. You're right.
You might want to check that your proposed solution works at all before suggesting the problem is trivial. What's the probability that the first die goes first with your numbers?
You also can't generally "and so on" constrained combinatorial arrangements like this.
I certainly would have, had I suggested the problem trivial! I'll keep that in mind for if I suggest things are trivial rather than suggesting I lack understanding.
> You also can't generally "and so on" constrained combinatorial arrangements like this.
I know you can't generally but in the specific case I proposed you can (3 sets of 3, 4 sets of 4, 5 sets of 5, each dice taking one ordinal of each set).
You might want to check that your proposed generalization criticism applies to the generalization at all before suggesting the arrangement doesn't work :)
Didn’t they do the exact opposite of suggesting the problem was trivial?
You're saying you knew the thing you wrote for n=3 specifically was wrong and just wanted someone else to confirm? I don't know man, I'm not really buying it. I think you did the classic dismissive nerd thing[1] and hedged it like this for plausible deniability.
I don't get the gotcha you're trying to do. Yes, the simple pattern you posted can be extended, but it has very little to do with the problem. If you had suggested [1,2,3] [4,5,6] [7,8,9] worked I would still have made my comment; I think the fact that you found a pattern that could be extended easily should have itself been a counter-indicator. Compare with something like the Fano plane[2].
I would want you to take away from this that posting the thing you came up with in "20 seconds" isn't as neutral a contribution to conversation as you thought. Things are often complicated and worth engaging with. It would have been cool if you kept going far enough to see there's a nice argument that it's actually impossible to solve it with n-sided dice for n people if n>2.
[1] https://xkcd.com/793/ [2] https://en.wikipedia.org/wiki/Combinatorial_design
Do you think the dismissive nerd thing is, like, a goal people set out to do?
You seem to have spent your time around sufficiently many unpleasant people that you see their behavior everywhere, even when explicitly corrected. I'm sorry for that.
Could I have independently gone through and rigorously deconstructed my solution? Sure, and we would all be poorer for it. See, there's another, valuable reason people say what I said beside the "classic dismissive nerd thing".
For every person with a question, there's probably 5 more with the same question who didn't ask. By writing down questions like I did, and inviting their answer to be written down, that provides education not only to me but to anyone who reads it after having similar thought.
I consider that sufficiently valuable to create, that I am willing to accept a handful of people criticizing me for "doing the dismissive nerd thing".
So yes. I knew the thing I wrote was wrong, I didn't know why/how, and I wrote it down as is rather than just going off on a personal side quest to come up with some generalized proof. And I would do it again.
Saying “I'm having trouble understanding” is not the same thing as “this is trivial”.
"I'm having trouble understanding why this is so complicated" could be interpreted in a non-dismissive way but it defaults to dismissive. And when it comes with a supposed solution attached, and that solution is really simple, that reinforces it sounding dismissive.
That wasn't my intention.
I by no means was suggesting that the trivial solution I, a non-mathematician, thought up in 20 seconds was somehow out of reach to a math professor who spent years on the problem. I knew I was wrong.
I didn't see why until I actually went through the solutions by hand.
Only the people who can't make eye contact with others interpreted your comment as hostile. Unfortunately, that describes a high number of people on this site.
I didn't read it as dismissive. I think the "Why doesn't this work?" at the end is key, implying they know they're probably wrong, but don't know why. It's pretty common to form and present hypothesis like this, hoping that anyone who knows the actual theory can easily provide a counterexample showing why it's wrong. It's not at all intended to be dismissive.
Why does that default to dismissive for you? It absolutely did not come off that way for me and I’m wondering if it’s because of experience or culture or something else.
Couldn’t you just assign a number to each of n players and then roll an n sided die, whichever player’s number it lands on gets to go first?
You could, but that would just dodge the problem they want to solve.
They're not actually interested in determining who goes first or anything practical like that. The article even implicitly admits as much. After all, you could just use normal dice and roll again on ties or, like you suggested, come up with an extra protocol built on top of them.
"We want dice that determine who goes first without a tie" is just a catchier way of saying "We want N dice that all have the same probability of showing the higher number but zero probability of a tie," which is an interesting mathematical problem.
You can also just draw lots.
I like how the article contains 0 useful information about the problem beyond the title.
Better source: http://www.ericharshbarger.org/dice/go_first_dice.html
TFA claims it's "new" in 2026, but the current state of the art seems to still be that of 2022.
I bought actual dice like these in 2024 from https://mathsgear.co.uk/collections/dice/products/go-first-d...
So well, is TFA just a big pile of slop?
> So well, is TFA just a big pile of slop?
It is a pile of slop and I am surprised that your comment is downvoted.
I don't know why would HN crown prefer this pile of journo fluff to the article by, you know, the guy who actually made the thing.
Oh, Eric is a friend of mine. I've got a set of five non-uniform go first dice that he 3D printed for me.
Dude runs a mean D&D campaign too. And his Lego mural and sculpture portfolio are something to behold: http://www.ericharshbarger.org/lego/portfolio.html
There are those who claim that LLMs can do math. Shouldn't they have come up with the 30-face dice yesterday?
You can just pull tokens out of a bag to generate a random sequence of virtually any length. Am I missing something? Why make it so complicated?
How do you decide who is going to pull the tokens?
If anyone wants a practical way to decide who goes first, in a single roll, with no possibility of a tie, this works:
For 2 players, the dealer rolls a standard 6-sided die, and the result determines who goes first:
For 3 players, the dealer rolls a standard 6-side die: For 4 players, the dealer rolls a standard d20 die: For 5 players, the dealer rolls a standard d20 die: If the dealer has a tetrahedral (d4) die, they can use that instead for the 4-player problem.This is really all you need to decide who goes first. It's perfectly fair. It uses standard dice that most people already have in their game drawer.
The article is actually about a different, much harder problem about the full playing order. You don't actually need that extra complexity to decide who goes first.