Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

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
share|improve this question
    
What is the objective winning criterion? –  Peter Taylor Sep 8 '12 at 18:58
    
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 Sep 9 '12 at 7:45
    
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 Sep 20 '12 at 20:36
add comment

2 Answers 2

up vote 1 down vote accepted

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.

share|improve this answer
    
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 Sep 9 '12 at 7:44
add comment

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.

share|improve this answer
    
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 oeis.org/A003418 for the number of sides), but proving it requires a more detailed analysis or a different insight. –  Peter Taylor Sep 20 '12 at 19:50
    
Different insight posted as a comment to the question. –  Peter Taylor Sep 20 '12 at 20:37
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.