9

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:

  • Any roll of two or more dice will never result in a tie.
  • Any die rolled against any other die in the set has an equal chance of "win/lose" against said die.

Here is the numbering for the four dice mentioned: 

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)

Question

I stink at math. I'm stumped. Given the above information, I'd like to be able to generate lists of integers ("dice") given a number of 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 "fairness" of each die is really what I'm looking for.

I assure you this isn't homework. This is simply a determined geek, annoyed by a seemingly trivial puzzle that just won't leave me alone... and for some reason, I can't seem to get it right.

I'm sure there's some relatively trivial math, and a basic algorithm involved here, and that's what I'm looking for. What terminology should I search for, if this is obvious to you? Because to me, it's not.

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

anonymous coward
  • 12,594
  • 13
  • 55
  • 97
  • It appears it will only be fair if `X` is divisible by `N`. Otherwise, one or more of the dice will be lopsided. – corsiKa Sep 07 '12 at 21:47
  • 1
    So you imply there is a way of generating such a set of dice for any number of players and any number of sides per die? I doubt that. – Qnan Sep 07 '12 at 21:49
  • Perhaps the sides of the dice are determined programmatically. That makes perfect sense, and is in my scribbles, and I realize I left it out. – anonymous coward Sep 07 '12 at 21:50
  • 1
    I think you should be able to figure it out mathematically... – Onlyjus Sep 07 '12 at 21:51
  • 1
    Obviously I was relying too heavily on the example provided, and wrote the signature in a silly way. The point is to generate the numbers, and I shall attempt to rewrite the question with less emphasis on the number of sides. – anonymous coward Sep 07 '12 at 21:51
  • For a given number of players, do you just need one set of dice that satisfies the constraints? – David Sep 07 '12 at 22:02
  • Indeed. players=2 could generate two 2-sided "dice" for all I care. The importance to me is "fairness". Thus, those two two-sided "dice" (coins?) would actually have values [1,4] and [2,3] if using numbers starting from "1". Does that make sense? – anonymous coward Sep 07 '12 at 22:04
  • @anonymouscoward [1,4] and [2,3] both sum to 5, so this isn't a solution (see rule 1: "Any roll of two or more dice will never result in a tie."). – Andy Hayden Sep 07 '12 at 22:14
  • @hayden I think that restriction means that if any number of players throw one die each (once), there will be no ties. – David Sep 07 '12 at 22:18
  • @hayden, as I understand there are four dice for up to four player. Each player rolls just one die. – Kwariz Sep 07 '12 at 22:19
  • Your second rule does not match the one found on the linked site : "Second, and here was the tricky part in designing the dice, regardless of what subset of dice are rolled against one another, each player will always have an equal chance of rolling the high number (and thus being the "starting player"). Put another way, two, three, or four players may each take one of the dice, roll it, and each will always have a 1/2, 1/3, or 1/4 chance, respectively, of having the highest result." – Kwariz Sep 07 '12 at 22:24
  • @Kwariz I'm not sure I understand. I believe myself to be saying the same thing, given any number of dice, rather than 4 specifically. As in the example, D1 has the same chance against D2, D3, D4, individually. The odds change (technically) as the number of dice increase, yes -- but, any two die, against each other, are "fair". Am I making sense? I'm not sure at the moment how to re-word the second rule, but I'd be glad to edit it. – anonymous coward Sep 08 '12 at 05:56
  • @Kwariz Perhaps it was my use of the word "chance", not meaning "odds" technically, but "fair likelihood" or some such. – anonymous coward Sep 08 '12 at 05:57

2 Answers2

5

This is a (computationally) difficult problem. It's not enough, as it may look at first, that the expected value of each die is the same (although it curiously is, in the example you gave). It's necessary that each die "wins" on 50% of all the instances of the dot product of each die element.

The fact that the article refers that a mathematician generated the example you gave "by hand" makes me a bit more comfortable in suggesting the following brute-force approach:

import itertools

nplayers=4
nsides=2
max_number=8

assert nplayers*nsides <= max_number
assert nsides % 2 == 0 #otherwise x^x (dot product) is not even, so half_wins_fairness always fails

iterations=[]
def half_wins_fairness( dice1,dice2 ):
    dice1_wins= map( lambda x: x[0]>x[1], itertools.product(dice1,dice2) )
    dice_wins_prob= float(sum(dice1_wins))/len(dice1_wins)
    #probs.append(dice_wins_prob)
    return dice_wins_prob==0.5

def fair( all_dice ):
    all_fair= True
    for d1,d2 in itertools.combinations( all_dice, 2):
        if not half_wins_fairness(d1,d2):
            all_fair=False
    return all_fair

for i,dice_pattern in enumerate(itertools.permutations(range(max_number), nplayers*nsides)):
    #cut dice pattern into dices
    dice= [dice_pattern[p*nsides:(p+1)*nsides] for p in range(nplayers)]
    if fair(dice):
        print dice
        iterations.append(i)

def discrete_derivative(l):
    last=0
    for i,x in enumerate(l):
        tmp= x
        l[i]=x-last
        last=tmp

#discrete_derivative(iterations)
#import pylab
#pylab.plot(iterations)
#pylab.show()

The complexity here is n^n, so this, by itself, only solves your problem for very low numbers of nplayers and nsides. However, by uncommenting the commented lines, you can inspect a plot of the fairness of the dice along the dot product iterations, which seems to have a lot of patterns, suggesting that several heuristics can be used to speed up this search, or maybe even find a general solution.

EDIT

changed the code for improved graphing. Here's some pics, in case someone is particularly adept at spotting patterns.

nplayers=2, nsides=2, max_number=8 nplayers=2, nsides=2, max_number=8 nplayers=2, nsides=4, max_number=8 nplayers=2, nsides=4, max_number=8 nplayers=4, nsides=2, max_number=8 nplayers=4, nsides=2, max_number=8

Some initial observations:

  1. it's symetrical
  2. the "cleanest" graphs seem to be generated when max_number % (nplayers*nsides) == 0
loopbackbee
  • 21,962
  • 10
  • 62
  • 97
  • This only checks that they are fair in pairs, so I think it would produce answers that have the same problem that my (now deleted) answer had: if you had n players for n > 2, not all the players would have a 1/n chance of winning. Or did I miss something? – David Sep 09 '12 at 13:50
  • @David It's relatively straightforward to prove that the chance of each player winning is 1/n if each dice has 1/2 chance against each of the others, by counting the permutations of the winning order of the n players. – loopbackbee Sep 10 '12 at 01:26
  • That's definitely not true in general. For instance, if you had four players and the dice were [1,2,3,22,23,24];[4,5,6,19,20,21];[7,8,9,16,17,18]; and [10,11,12,13,14,15], then any die has a 1/2 chance against each of the others. But if all four players throw a die, the player with [1,2,3,22,23,24] still has a 1/2 chance of winning rather than 1/4. (Of course, the OP's question doesn't actually ask for the 1/n condition, but the linked site gives it as part of the definition for these dice.) – David Sep 10 '12 at 01:32
  • @David you're right it seems this does not hold. Apparently, the simulation of the dot product of the n dice must be performed. I'm not sure why calculating the probability of the permutations of the winning order gives a different result... – loopbackbee Sep 10 '12 at 01:44
0

For the record, this answer on codegolf has a straightforward algorithm that seems to work for at least any time that the number of sides on the dice are even: https://codegolf.stackexchange.com/a/7238/5376

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
Community
  • 1
  • 1
anonymous coward
  • 12,594
  • 13
  • 55
  • 97
  • I haven't checked it, but according to a comment on codegolf, this has the same problem that my original answer did: if three people are playing, they do not each have a 1/3 chance of winning. – David Sep 09 '12 at 13:46