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.

13
  • 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 7, 2012 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 7, 2012 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. Sep 7, 2012 at 21:50
  • 1
    I think you should be able to figure it out mathematically...
    – Onlyjus
    Sep 7, 2012 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. Sep 7, 2012 at 21:51

2 Answers 2

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
4
  • 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 9, 2012 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. Sep 10, 2012 at 1: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, 2012 at 1: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... Sep 10, 2012 at 1: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
1
  • 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 9, 2012 at 13:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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