How can I generate “Go First” Dice for N dice?
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
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.
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>x, 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.
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:
- it's symetrical
- the "cleanest" graphs seem to be generated when max_number % (nplayers*nsides) == 0