Generate N number of "Go First" dice

3

Background

As described here http://www.ericharshbarger.org/dice/#gofirst_4d12, "Go First" Dice is a set of four dice, each with unique numbering, so that:

  • There will never be a tie. Each die has a unique set of numbers.
  • Regardless of what subset of dice are rolled against one another, each player will always have an equal chance of rolling the high number.

Here is the specific numbering for the four dice mentioned, as an example:

DICE COUNT: 4
FACE COUNT: 12
D1: 1,8,11,14,19,22,27,30,35,38,41,48
D2: 2,7,10,15,18,23,26,31,34,39,42,47
D3: 3,6,12,13,17,24,25,32,36,37,43,46
D4: 4,5, 9,16,20,21,28,29,33,40,44,45

(via)

Goal

Without requiring any particular result, I would like to be able to generate a set of N "Go First" dice... Such that, example output might look like so (formatted, python console):

    >>> generate_dice(players=4)
    [[1,8,11,14,19,22,27,30,35,38,41,48],
     [2,7,10,15,18,23,26,31,34,39,42,47],
     [3,6,12,13,17,24,25,32,36,37,43,46],
     [4,5,9,16,20,21,28,29,33,40,44,45]]    

The number of sides here is chosen just for example purposes, because it matches the other example given. The number of sides of the dice can be determined by the algorithm used.

Ideally the solution would be in Python, but I can also read PHP, Javascript, some Ruby, quite well.

I'm honestly puzzling over this, and would love to understand what terminology/math I should have studied to figure this out. I've tried to explain it before, but seem to be having trouble not using words that imply too many things about what should be generated, and what odds should be, etc. I'm specifically interested in being able to generate "a set of N 'Go First' dice".

Extra

Here's some ugly python, to "prove" the dice, and perhaps give an example.

def fair_chance(die1, die2):
    wins = 0
    losses = 0
    ties = 0
    for i in die1:
        for x in die2:
            if cmp(i, x) < 0: 
                losses += 1                
            if cmp(i, x) > 0:
                wins += 1
            if cmp(i, x) == 0:
                ties += 1
    if wins == losses and losses != 0 and ties == 0:
        return True
    return False

Give the above example dice:

D1 = [1,8,11,14,19,22,27,30,35,38,41,48]
D2 = [2,7,10,15,18,23,26,31,34,39,42,47]
D3 = [3,6,12,13,17,24,25,32,36,37,43,46]
D4 = [4,5, 9,16,20,21,28,29,33,40,44,45]

fair_chance(D1, D2)  # True
fair_chance(D1, D3)  # True
fair_chance(D1, D4)  # True
fair_chance(D2, D3)  # True
fair_chance(D2, D4)  # True
fair_chance(D3, D4)  # True

Thus, the function generate_dice should work, such that output in a Python shell would look like this:

>>> dice = generate_dice(players=4)
>>> D1 = dice[0]
>>> D2 = dice[1]
>>> D3 = dice[2]
>>> D4 = dice[3]
>>> fair_chance(D1, D2)
True
>>> fair_chance(D1, D3)
True
>>> fair_chance(D1, D4)
True
>>> fair_chance(D2, D3)
True
>>> fair_chance(D2, D4)
True
>>> fair_chance(D3, D4)
True

i_desire_the_dice

Posted 2012-09-08T06:37:55.670

Reputation: 41

Question was closed 2016-01-27T17:47:44.920

What is the objective winning criterion?

– Peter Taylor – 2012-09-08T18:58:42.573

Also note: your "proving" code only checks pairs, but the spec requires that "Regardless of what subset of dice are rolled against one another, each player will always have an equal chance of rolling the high number" (my emphasis). – Peter Taylor – 2012-09-09T07:45:48.347

It's fairly easy to prove a basic constraint on the number of sides the dice must have (assuming they each have the same number of sides). If we have N dice each having D sides and we want a fair result for any 1 < M <= N subset, we require D^M == 0 (mod M). Therefore D must be a multiple of the Nth primorial number.

– Peter Taylor – 2012-09-20T20:36:51.850

Answers

1

My python is a little rusty because I haven't used it in a very long time, but how about something like this:

def generate_dice(count, sides = 12):
  dice = []
  for i in range(count):
    dice.append([])

  value = 0
  for sindex in range(sides):
    if sindex % 2:
      for dindex in range(count):
        value += 1
        dice[dindex].append(value)
    else:
      for dindex in reversed(range(count)):
        value += 1
        dice[dindex].append(value)
  return dice

The pattern here is simpler than the one you linked, but it appears to work as long as the number of sides on the dice is even. I originally did this in C# and then converted it to python.

DarkTygur

Posted 2012-09-08T06:37:55.670

Reputation: 36

The spec requires that "Regardless of what subset of dice are rolled against one another, each player will always have an equal chance of rolling the high number"; your generate_dice with count=3 and sides=12 produces dice which are fair in pairs but in triples win in proportion 584:572:572. – Peter Taylor – 2012-09-09T07:44:54.587

1

Well, I believe that this deals with telescoping series. As it turns out, the number of dice and number of sides you use is very important. For example, try to make 4, 4 sided dice that fits the same requirement.

Using the numbers from 1 to 16, one of the dice has to get the number 16. Which ever dice has 16 already has a 25% chance of landing on the highest number when all 4 are rolled. However, the chance that any particular dice is first must = 25%. Thus, the remaining numbers must have 0% chance of being the highest number. This makes the first dice [1,2,3,16]. However this doesn't fit the requirement that when rolling 2 dice, you still have a equal probability of going first. Now you only have 25% instead of 50%. Thus when you have 4 dice, you must have more than 4 sides for these requirements to work.

I think the fact that they used 4 d12 is not just by chance. I would bet it's the minimum number of sides for 4 dice that works. I think if 4d8 or 4d6 worked, they would have just done that, because it's simpler to prove correct.

Thus, with 4 dice, you need a number of sides which is >=12 to meet all the properties.

In the example, the die with the highest number (48) has only a 1/12 of getting that number. Since this die has a 1/12 of going first, it should also have a 1/12 of going last, so it gets a (1).

Notice that the relative order of the numbers of each dice forms a sort of palindrome of pairs. (1 4) (3 2) (3 2) (3 2) (3 2) (1 4) the first dice sequence This is obviously on purpose. I'd check to see if other palindromes have the same property.

Derp

Posted 2012-09-08T06:37:55.670

Reputation: 11

Your analysis is slightly flawed. In your case of rolling 4 dice, the die with the 16 doesn't have to be [1,2,3,16] because it's rolled against 3 others. If it's e.g. [4,5,6,16] and one of the others is [1,2,x,y] then it can only win with the 16. I believe it's still impossible to make 4 4-side dice which work (at a guess you would need to use http://oeis.org/A003418 for the number of sides), but proving it requires a more detailed analysis or a different insight.

– Peter Taylor – 2012-09-20T19:50:45.133

Different insight posted as a comment to the question. – Peter Taylor – 2012-09-20T20:37:25.547