How can I generate "Go First" Dice for N dice?

Question

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.

Answer 1

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=4, 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